Abstract—This paper proposes a problem-based heuristic performing well for solving asymmetric travelling salesman problem (ATSP), one of a well-known NP-hard problem. The basic concept of the proposed heuristic is to construct a round-trip route by moving from the current city to one of its adjacent cities systematically using a well selection procedure in its move’s direction. Based on its simple concept, this heuristic is thus very simple and can be calculated both by hand and by PC in a short time period. The experimental results show that the proposed heuristic outperforms the nearest neighbour algorithm.

Index Terms—asymmetric travelling salesman problem, ATSP, problem-based heuristic, algorithm

Cite: Jutathip Putponpai and Pisut Pongchairerks, "A Problem-Based Heuristic for Asymmetric Travelling Salesman Problems," Journal of Industrial and Intelligent Information, Vol. 3, No. 3, pp. 258-265, September 2015. doi: 10.12720/jiii.3.3.258-265