Composite algorithm based on Clarke – Wright and local search for the traveling salesman problem

Komarudin, Sandiego F. Parhusip

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish
Title of host publication2019 the 5th International Conference on Industrial and Business Engineering, ICIBE 2019
PublisherAssociation for Computing Machinery
Pages87-90
Number of pages4
ISBN (Electronic)9781450376532
DOIs
Publication statusPublished - 27 Sep 2019
Event5th International Conference on Industrial and Business Engineering, ICIBE 2019 - Hong Kong, Hong Kong
Duration: 27 Sep 201929 Sep 2019

Publication series

NameACM International Conference Proceeding Series

Conference

Conference5th International Conference on Industrial and Business Engineering, ICIBE 2019
CountryHong Kong
CityHong Kong
Period27/09/1929/09/19

Keywords

  • Clarke Wright (CW)
  • Composite Algorithm
  • Heuristic
  • Local Search
  • Optimization
  • Traveling Salesman Problem (TSP)

Fingerprint Dive into the research topics of 'Composite algorithm based on Clarke – Wright and local search for the traveling salesman problem'. Together they form a unique fingerprint.

  • Cite this

    Komarudin, & Parhusip, S. F. (2019). Composite algorithm based on Clarke – Wright and local search for the traveling salesman problem. In 2019 the 5th International Conference on Industrial and Business Engineering, ICIBE 2019 (pp. 87-90). (ACM International Conference Proceeding Series). Association for Computing Machinery. https://doi.org/10.1145/3364335.3364388