A hybrid based genetic algorithm for solving the clustered generalized traveling salesman problem
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.
Other publications
Evaluation of Feature Selection Methods in Estimation of Precipitation Based on Deep Learning Artificial Neural Networks
Precipitation is the most important element of the water cycle and an indispensable element of water resources management. This paper aims to model the monthly precipitation in 8 precipitation observation stations. The effects and role of different feature weights pre-processing methods (Weight by deviation, Weight by PCA, Weight by correlation, and Weight by Support Vector Machine) on artificial intelligence modeling were investigated.
A Comparison of different crossover operators in genetic algorithms for clusters shortest-path tree problem
The clustered shortest-path tree (CluSPT) problem is an extension of the classical shortest path problem, given a graph with the nodes partitioned into several mutually exclusive and collectively exhaustive clusters looks for a shortest-path spanning tree from a predefined source node to all the other nodes of the graph, with the property that every cluster should generate a connected subgraph.
A comprehensive survey on the generalized traveling salesman problem
The generalized traveling salesman problem (GTSP) is an extension of the classical traveling salesman
problem (TSP), and 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 problem, distribution of medical supplies, urban waste collection management, airport selection and routing the courier airplanes, image retrieval and ranking, digital garment manufacturing, etc.
0 Comments