Local Search for the Asymmetric Traveling Salesman Problem
作者： Paris-C. Kanellakis , Christos H. Papadimitriou
关键词: Local search (optimization) 、 Combinatorial optimization 、 Bottleneck traveling salesman problem 、 Heuristic (computer science) 、 Greedy algorithm 、 Travelling salesman problem 、 Traveling purchaser problem 、 Mathematics 、 Mathematical optimization 、 2-opt
摘要: We present an extension of the Lin-Kernighan local search algorithm for solution asymmetric traveling salesman problem. Computational results suggest that our heuristic is feasible fairly large instances. also some theoretical which guided design heuristic.
sci-hub.se 参考文章(11)
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
Christos H. Papadimitriou, The adjacency relation on the traveling salesman polytope is NP-Complete Mathematical Programming. ,vol. 14, pp. 312- 324 ,(1978) , 10.1007/BF01588973
Michael Held, Richard M. Karp, The Traveling-Salesman Problem and Minimum Spanning Trees Operations Research. ,vol. 18, pp. 1138- 1162 ,(1970) , 10.1287/OPRE.18.6.1138
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Daniel J Rosenkrantz, Richard E Stearns, Philip M Lewis, II, An analysis of several heuristics for the traveling salesman problem SIAM Journal on Computing. ,vol. 6, pp. 563- 581 ,(1977) , 10.1007/978-1-4020-9688-4_3
S. Lin, B. W. Kernighan, An Effective Heuristic Algorithm for the Traveling-Salesman Problem Operations Research. ,vol. 21, pp. 498- 516 ,(1973) , 10.1287/OPRE.21.2.498
P. C. Gilmore, R. E. Gomory, Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem Operations Research. ,vol. 12, pp. 655- 679 ,(1964) , 10.1287/OPRE.12.5.655
Christos H. Papadimitriou, Kenneth Steiglitz, ON THE COMPLEXITY OF LOCAL SEARCH FOR THE TRAVELING SALESMAN PROBLEM SIAM Journal on Computing. ,vol. 6, pp. 76- 83 ,(1977) , 10.1137/0206005
Sam Savage, Peter Weiner, A. Bagchi, Neighborhood search algorithms for guaranteeingoptimal traveling salesman tours must be inefficient Journal of Computer and System Sciences. ,vol. 12, pp. 25- 35 ,(1976) , 10.1016/S0022-0000(76)80016-5
Richard M. Karp, Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane Mathematics of Operations Research. ,vol. 2, pp. 209- 224 ,(1977) , 10.1287/MOOR.2.3.209