摘要
The Traveling Salesman Problem (TSP) aims to find the shortest tour for a salesman who starts and ends in the same city and visits the remaining n - 1 cities exactly once. There are a number of common generalizations of the problem including the Multiple Traveling Salesman Problem (MTSP), where instead of one salesman, there are k salesmen and the same amount of individual tours are to be constructed. We consider the Euclidean version of the problem where the distances between the cities are calculated in two-dimensional Euclidean space. Both general the TSP and its Euclidean version are strongly NP-hard. Hence, approximation algorithms with a good practical behavior are of primary interest. We describe a general method for the solution of the Euclidean versions of the TSP (including MTSP) that yields approximation algorithms with a favorable practical behavior for large real-life instances. Our method creates special types of convex hulls, which serve as a basis for the constructions of our initial and intermediate partial solutions. Here, we overview three algorithms; one of them is for the bounded version of the MTSP. The proposed novel algorithm for the Euclidean TSP provides close-to-optimal solutions for some real-life instances.
学科与关键词
- Information in the Traveling Salesman ProblemGilad Barach; Hugo Fort; Yoni Mehlman; Fredy ZypmanApplied Mathematics, 2012, 03(08): 926-930.
- A tour construction heuristic for the travelling salesman problemHwang, CP; Alidaee, B*; Johnson, JDJournal of the Operational Research Society, 1999, 50(8): 797-809.被引 8
- An effective iterated two-stage heuristic algorithm for the multiple Traveling Salesmen ProblemZheng, Jiongzhi; Hong, Yawei; Xu, Wenchang; Li, Wentao; Chen, Yongfu*COMPUTERS & OPERATIONS RESEARCH, 2022, 143: 105772.被引 16
