TY - GEN
T1 - Composite algorithm based on Clarke – Wright and local search for the traveling salesman problem
AU - Komarudin,
AU - Parhusip, Sandiego F.
N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019/9/27
Y1 - 2019/9/27
N2 - 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.
AB - 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.
KW - Clarke Wright (CW)
KW - Composite Algorithm
KW - Heuristic
KW - Local Search
KW - Optimization
KW - Traveling Salesman Problem (TSP)
UR - http://www.scopus.com/inward/record.url?scp=85076696434&partnerID=8YFLogxK
U2 - 10.1145/3364335.3364388
DO - 10.1145/3364335.3364388
M3 - Conference contribution
AN - SCOPUS:85076696434
T3 - ACM International Conference Proceeding Series
SP - 87
EP - 90
BT - 2019 the 5th International Conference on Industrial and Business Engineering, ICIBE 2019
PB - Association for Computing Machinery
T2 - 5th International Conference on Industrial and Business Engineering, ICIBE 2019
Y2 - 27 September 2019 through 29 September 2019
ER -