Please use this identifier to cite or link to this item:
Title: Preprocessing Schemes for Tabu search on Asymmetric Traveling Salesman Problem
Authors: Basu, Sumanta
Sharma, Megha
Keywords: traveling salesman problem
tabu search
cross entropy
particle swarm optimization
Issue Date: 1-Oct-2013
Series/Report no.: WORKING PAPER SERIES;WPS No. 735/ October 2013
Abstract: The objective of this paper is to implement tabu search on moderate sized asymmetric traveling salesman problems (ATSPs). We introduce preprocessing schemes based on the cross entropy and the particle swarm optimization method which allow us to reduce the number of arcs in the graph defining an ATSP instance, without significantly affecting the cost of the tour output by tabu search. This reduction helps us to apply tabu search methods especially designed for ATSPs defined on sparse graphs. We also provide a scheme to generate good initial tours for multi-start tabu search to run on large problems. We report our computational experiences on randomly generated problems as well as benchmark problems to show that our method yields good quality tours for moderate sized ATSPs much faster than conventional tabu search implementations.
Appears in Collections:2013

Files in This Item:
File Description SizeFormat 
wps_735_0.pdf382.66 kBAdobe PDFThumbnail

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.