Composite Algorithm Based on Clarke - Wright and Local Search for the Traveling Salesman Problem
Pages 87 - 90
Abstract
Traveling Salesman Problem (TSP) is an NP-hard optimization problem that can be solved by a heuristic composite algorithm. A composite algorithm is a heuristic optimization model that combine tour construction algorithm and tour improvement algorithm. Clarke Wright Savings heuristic is one of the best methods that produce a good initial solution, and local search is known to be a successful operator to make an improvement solution. This paper will present a composite algorithm as a preliminary model based on Clarke wright savings and local search K-opt to solve TSP. The experimental result shows that the proposed algorithm can solve a large problem instance of Traveling Salesman Problem up to 85.900 points, with competitive results, small variations of computing time for 30 problem instances, and relatively short computing time.
References
[1]
K. Helsgaun, An Effective implementation of the Lin-Kernighan traveling talesman heuristic, Eur. J. Oper. Res. 126, 106--130 (2000).
[2]
Hougardy, S., & Schroeder, R. T. (2013.). Edge Elimination in TSP Instances, 1--14
[3]
M.W. Padberg, G. Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review 33, 60--100 (1991)
[4]
Sun, J., Wang, Y., Li, J., & Gao, K. (2011). Hybrid Algorithm Based on Chemical Reaction Optimization and Lin-Kernighan Local Search for the Traveling Salesman Problem. 2011 Seventh International Conference on Natural Computation, 3, 1518--1521. https://doi.org/10.1109/ICNC.2011.6022378
[5]
Y. Chen, P. Zhang, Optimized annealing of traveling salesman problem from the nth-nearest-neighbor distribution, Physica A 371, 627--632 (2006).
[6]
C.-N. Fiechter, A parallel tabu search algorithm for large traveling salesman problems, Discrete Appl. Math. 51, 243--26 (1994).
[7]
M. Albayrak, N. Allahverdi, N.: Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms, Expert Syst. Appl. 38, 1313--1320 (2011).
[8]
N. Mladenović, P. Hansen, Variable neighborhood search, Comput. Oper. Res. 24, 1097--1100 (1997).
[9]
J.C. Créput, A. Koukam, A memetic neural network for the euclidean traveling salesman problem. Neurocomputing 72, 1250--1264 (2009).
[10]
C.F. Tsai, C.W. Tsai, C.C. Tseng, A new hybrid heuristic approach for solving large traveling salesman problem, Inform. Sci. 166, 67--81 (2004).
[11]
X.H. Shi, Y.C. Liang, H.P.Lee, C. Lu, Q.X. Wang, Particle swarm optimization-based algorithms for TSP and generalized TSP, Inform. Process. Lett. 103, 169--176 (2007).
[12]
D. Applegate, W. Cook, A. Rohe, Chained Lin-Kernighan for large traveling salesman problems, Informs J. Comput. 15, 82--92 (2003).
[13]
M. Gendreau, A. Hertz, G. Laporte, New insertion and 0post-optimization procedures for the traveling salesman problem, Oper. Res. 40(1992)1086--1094.
[14]
S. Lin, B.W. Kernighan, An e.ective heuristic algorithm for the traveling salesman problem, Oper. Res. 21, 498--516 (1973).
[15]
Wright, J. W. (1962). Scheduling of vehicles from a central depot to a number of delivery points 6
[16]
Rohe, Andre. (2013, May 2013). VLSI Data Sets. Retrieved from http://www.math.uwaterloo.ca/tsp/vlsi/index.html
[17]
Dumitrescu, A., & Mitchell, J. S. (2003). Approximation algorithms for TSP with neighborhoods in the plane. Journal of Algorithms, 48(1), 135--159.
[18]
Tin et al. (2018). Efficient Recombination in the Salesman Heuristic, 1(1), 95--107. https://doi.org/10.1007/978-3-319-99253-2
[19]
Wang, Y., & Remmel, J. B. (2018). An iterative algorithm to eliminate edges for traveling salesman problem based on a new binomial distribution Eliminating edges for TSP, 4470--4484.
Index Terms
- Composite Algorithm Based on Clarke - Wright and Local Search for the Traveling Salesman Problem
Recommendations
Doubly-rooted stem-and-cycle ejection chain algorithm for the asymmetric traveling salesman problem
Ejection chain methods, which include the classical Lin-Kernighan LK procedure and the Stem-and-Cycle S&C reference structure, have been the source of the currently leading algorithms for large scale symmetric traveling salesman problems STSP. Although ...
Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search
The traveling salesman problem (TSP) is a classical problem in discrete or combinatorial optimization and belongs to the NP-complete classes, which means that it may be require an infeasible processing time to be solved by an exhaustive search method, ...
Expanding Neighborhood GRASP for the Traveling Salesman Problem
In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure (GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2019
398 pages
ISBN:9781450376532
DOI:10.1145/3364335
Copyright © 2019 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
In-Cooperation
- The Hong Kong Polytechnic: The Hong Kong Polytechnic University
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 September 2019
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- Ministry of Research, Technology and Higher Education of the Republic of Indonesia
Conference
ICIBE 2019
ICIBE 2019: 2019 The 5th International Conference on Industrial and Business Engineering
September 27 - 29, 2019
Hong Kong, Hong Kong
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 97Total Downloads
- Downloads (Last 12 months)20
- Downloads (Last 6 weeks)6
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in