Title: Hybrid population-based variable neighbourhood search and simulated annealing algorithms for asymmetric travelling salesman problems

Authors: Ittiporn Piriyaniti; Pisal Yenradee

Addresses: Industrial Engineering Program, Sirindhorn International Institute of Technology, Thammasat University, Rangsit Center, Pathum-Thani 12121, Thailand ' Industrial Engineering Program, Sirindhorn International Institute of Technology, Thammasat University, Rangsit Center, Pathum-Thani 12121, Thailand

Abstract: The asymmetric travelling salesman problem (ATSP) is a generalised travelling salesman problem that the distances between a pair of cities may not be equal in opposite directions. This problem has a close relation with real-world problems in logistics and transportation. This paper aims to enhance performances of variable neighbourhood search (VNS) algorithm by introducing population-based approach (EVNS) and simulated annealing (SA) technique to the VNS algorithm. Benchmark ATSP instances available in TSP library (TSPLIB) are used to test the performances of the proposed algorithms. Experimental results show that the solution quality can be improved significantly when the population-based approach is applied and the worse solution is accepted with some probabilities which is a mechanism of SA technique. The proposed EVNS-SA algorithm has very good performances among the algorithms for solving ATSP available in literatures.

Keywords: variable neighbourhood search; population-based VNS; asymmetric TSP; travelling salesman problem; ATSP; simulated annealing; SA.

DOI: 10.1504/IJISE.2013.057477

International Journal of Industrial and Systems Engineering, 2013 Vol.15 No.4, pp.410 - 425

Published online: 27 Dec 2013 *

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