A novel GRASP based on mixed k-opt method for the Traveling Salesman Problem

DOI

10.2991/emcs-16.2016.455How to use a DOI?

Keywords

Randomized Adaptive Search Procedure; traveling salesman problem; optimal algorithm; Greedy Randomized Adaptive Search Procedure; NP-complete problem

Abstract

Objective: A novel Greedy Randomized Adaptive Search Procedure was proposed in this paper to resolve the traveling salesman problem, which is proven to be NP-complete in most cases. Methods: The proposed novel algorithm has two phases. In the first phase the novel algorithm finds an initial solution of the problem with a proposed mergence feature greedy randomized method. In the second phase the expanded neighborhood adaptive search procedure was proposed to find the TSP solution. Results: The proposed algorithm was tested on numerous benchmark problems from TSPLIB. The algorithm is compared with other two algorithms and the results showed that the results of the proposed algorithm are always the best. The results were very satisfactory. Conclusion: For the majority of the instances the results were equal to the best known solution. The algorithm is suitable for the TSP. This kind of novel algorithm can be used for many aspects of object, especially for logistical problem.

Copyright

© 2016, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Ming Zheng
AU  - Hui Guo
AU  - Jie He
AU  - Guixia Liu
PY  - 2016/01
DA  - 2016/01
TI  - A novel GRASP based on mixed k-opt method for the Traveling Salesman Problem
BT  - Proceedings of the 2016 International Conference on Education, Management, Computer and Society
PB  - Atlantis Press
SP  - 1808
EP  - 1813
SN  - 2352-538X
UR  - https://doi.org/10.2991/emcs-16.2016.455
DO  - 10.2991/emcs-16.2016.455
ID  - Zheng2016/01
ER  -