Please use this identifier to cite or link to this item:
Title: Cross Entropy based Neighborhood Reduction and Initial Tour Formation for Tabu Search on the Asymmetric Traveling Salesman Problem
Authors: Basu, Sumanta
Ghosh, Diptesh
Issue Date: 1-Nov-2010
Series/Report no.: WORKING PAPER SERIES;WPS No. 667/ November 2010
Abstract: The objective of this paper is to implement tabu search on moderate sized asymmetric traveling salesman problems (ATSPs). We introduce a preprocessing scheme based on the cross entropy method which al- lows us to reduce the number of arcs in the graph de ning an ATSP instance, without signi cantly a ecting the cost of the tour output by tabu search. This reduction helps us to apply tabu search methods es- pecially designed for ATSPs de ned 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:2010

Files in This Item:
File Description SizeFormat 
wps-667.pdf209.26 kBAdobe PDFThumbnail

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