A comprehensive survey on the generalized traveling salesman problem
Petrică C. Pop, Ovidiu Cosma, Cosmin Sabo, Corina Pop Sitar

Abstract. The generalized traveling salesman problem (GTSP) extends the classical traveling salesman problem (TSP). It is among the most researched combinatorial optimization problems due to its theoretical properties, complexity aspects, and real-life applications in various areas: location-routing problems, material flow design problems, distribution of medical supplies, urban waste collection management, airport selection and routing the courier airplanes, image retrieval and ranking, digital garment manufacturing, etc. Even though the importance of this combinatorial optimization problem was highlighted in several publications and several methods for solving it were developed, there is no survey dedicated to the GTSP. This paper aims to close this gap by providing a comprehensive survey on mathematical formulations, solution approaches, and the latest advances regarding the GTSP. The paper is organized around the following issues: problem definition, variations, and related problems, real-life applications of
the GTSP, mathematical formulations, solution approaches designed for solving the investigated problem, datasets, computational results, and comparative analysis of the performance of the existing state-of-the-art algorithms. Additionally, we discuss certain open problems and potential research directions.

Keywords: Combinatorial optimization, traveling salesman problem, generalized traveling salesman problem, mathematical formulations, heuristic and metaheuristic algorithms.

Petrică C. Pop, Ovidiu Cosma, Cosmin Sabo, Corina Pop Sitar, "A comprehensive survey on the generalized traveling salesman problem", , 2023.

Other publications