Premium
Randomized heuristics for the family traveling salesperson problem
Author(s) -
MoránMirabal L.F.,
GonzálezVelarde J.L.,
Resende M.G.C.
Publication year - 2014
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12026
Subject(s) - heuristics , travelling salesman problem , grasp , mathematical optimization , solver , integer programming , mathematics , path (computing) , computer science , genetic algorithm , programming language
This paper introduces the family traveling salesperson problem (FTSP), a variant of the generalized traveling salesman problem. In the FTSP, a subset of nodes must be visited for each node cluster in the graph. The objective is to minimize the distance traveled. We describe an integer programming formulation for the FTSP and show that the commercial grade integer programming solver CPLEX 11 can only solve small instances of the problem in reasonable running time. We propose two randomized heuristics for finding optimal and near‐optimal solutions of this problem. These heuristics are a biased random‐key genetic algorithm and a GRASP with evolutionary path‐relinking. Computational results comparing both heuristics are presented in this study.