A Method to Search the Optimal Hamiltonian Cycle with a Set of Approximations for Travelling Salesman Problem

DOI

10.2991/eame-15.2015.182How to use a DOI?

Keywords

travelling salesman problem; optimal hamiltonian cycle; frequency graph, sparse graph; depth-first graph search algorithm

Abstract

The objective of travelling salesman problem (TSP) is to find the optimal Hamiltonian cycle (OHC) and it has been proven to be NP-complete. A heuristic method is proposed for TSP. It is realized with four steps. A set of approximations are computed with the 2-opt move algorithm firstly. Secondly, a frequency graph is computed with the set of approximations. A sparse graph with small number of edges is generated in the third step. At last, the depth-first graph search algorithm is used to find the OHC or a better approximation with the sparse graph. The experimental results show that the OHC of most of the TSP instances are searched within an acceptable computation time.

Copyright

© 2015, 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  - Y. Wang
PY  - 2015/07
DA  - 2015/07
TI  - A Method to Search the Optimal Hamiltonian Cycle with a Set of Approximations for Travelling Salesman Problem
BT  - Proceedings of the 2015 International Conference on Electrical, Automation and Mechanical Engineering
PB  - Atlantis Press
SP  - 665
EP  - 668
SN  - 2352-5401
UR  - https://doi.org/10.2991/eame-15.2015.182
DO  - 10.2991/eame-15.2015.182
ID  - Wang2015/07
ER  -