Title: Variable neighbourhood search algorithms for asymmetric travelling salesman problems

Authors: Ittiporn Piriyaniti; Pisut Pongchairerks

Addresses: Industrial Engineering Program, Sirindhorn International Institute of Technology, Thammasat University, P.O. Box 22, Thammasat Rangsit Post Office, Pathumthani, 12121, Thailand ' Production Engineering Program, Faculty of Engineering, Thai-Nichi Institute of Technology, 1771/1 Pattanakarn Rd., Suanluang, Bangkok, 10250, Thailand

Abstract: The aim of the research is to find the best neighbourhood structures for the shaking step and the local search step in the variable neighbourhood search algorithm (VNS) when applied to the asymmetric travelling salesman problem (ATSP). Many variants of the VNS algorithm are proposed based on their neighbourhood structures. The performances of these VNS algorithms are tested with the benchmark instances of the ATSP, one of the best known logistics problems.

Keywords: asymmetric TSP; travelling salesman problem; ATSP; variable neighbourhood search; VNS; NP-hard; combinatorial problems; neighbourhood structures; logistics.

DOI: 10.1504/IJOR.2013.056104

International Journal of Operational Research, 2013 Vol.18 No.2, pp.157 - 170

Available online: 13 Aug 2013 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article