A matheuristic approach for the family traveling salesman problem
Open Access
- 22 September 2023
- journal article
- research article
- Published by Springer Nature in Journal of Heuristics
- Vol. 29 (4-6) , 435-460
Abstract
In the family traveling salesman problem (FTSP), there is a set of cities which are divided into a number of clusters called families. The salesman has to find a shortest possible tour visiting a specific number of cities from each of the families without any restriction of visiting one family before starting the visit of another one. In this work, the general concept of the Partial OPtimization Metaheuristic Under Special Intensification Conditions is linked with the exact optimization by a classical solver using a mathematical programming formulation for the FTSP to develop a matheuristic. Moreover, a genetic and a simulated annealing algorithm are used as metaheuristics embedded in the approach. The method is examined on a set of benchmark instances and its performance is favorably compared with a state-of-the-art approach from literature. Moreover, a careful analysis of the specific components of the approach is undertaken to provide insights into the impact of their interplay.Keywords
Funding Information
- Universität Hamburg
This publication has 48 references indexed in Scilit:
- A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithmsSwarm and Evolutionary Computation, 2011
- A multistart heuristic for the equality generalized traveling salesman problemNetworks, 2010
- Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches2010
- Improving benders decomposition using a genetic algorithmEuropean Journal of Operational Research, 2009
- POPMUSIC for a real-world large-scale vehicle routing problem with time windowsJournal of the Operational Research Society, 2009
- POPMUSIC for the point feature label placement problemEuropean Journal of Operational Research, 2009
- A genetic algorithm with a mixed region search for the asymmetric traveling salesman problemComputers & Operations Research, 2003
- A Comparison of Selection Schemes Used in Evolutionary AlgorithmsEvolutionary Computation, 1996
- Optimization by Simulated AnnealingScience, 1983
- Integer Programming Formulation of Traveling Salesman ProblemsJournal of the ACM, 1960