Int. J. of Industrial and Systems Engineering   »   2013 Vol.15, No.4

 

 

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

 

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

 

Available online: 18 Sep 2013

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article