A hybrid-based genetic algorithm for solving the clustered generalized traveling salesman problem
Ovidiu Cosma, Petrică C. Pop, Laura Cosma

Abstract. We study the clustered generalized traveling salesman problem (CGTSP), which is an extension of the generalized traveling salesman problem (GTSP), which in turn generalizes the well-known traveling salesman problem (TSP). The investigated problem was motivated by several practical applications such as modern logistics, data clustering, internet networks, etc., and it is defined on a graph, whose set of vertices are split up into clusters, and the clusters are further partitioned into sub-clusters of vertices. The CGTSP aims to look for a minimum length tour that visits exactly one vertex from each sub-cluster with the primary constraint that all the sub-clusters belonging to each given cluster are visited contiguously. This paper describes a hybrid algorithm for solving the CGTSP that integrates Dijkstra’s shortest path algorithm and a TSP solver within a genetic algorithm. Finally, we present a new set of instances for CGTSP derived from the GTSP LIB [8]. Some preliminary computational results are stated on a set of 40 instances to assess the efficiency of our designed hybrid-based genetic algorithm.

Keywords: Hybrid algorithms, genetic algorithms, generalized traveling salesman problem, clustered generalized traveling salesman problem.

Ovidiu Cosma, Petrică C. Pop, Laura Cosma, "A hybrid based genetic algorithm for solving the clustered generalized traveling salesman problem", , 2023.

Other publications