Cross Entropy based Neighborhood Reduction and Initial Tour Formation for Tabu Search on the Asymmetric Traveling Salesman Problem

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.