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

Received: 14 May 2012
Accepted: 10 Jul 2012
Published online: 29 Jul 2014 *

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