A Review of the Tabu Search Literature on Traveling.pdf

(557 KB) Pobierz
INDIAN INSTITUTE OF MANAGEMENT
AHMEDABAD
•
INDIA
Research and Publications
A Review of the Tabu Search Literature on Traveling
Salesman Problems
Sumanta Basu
Diptesh Ghosh
W.P. No. 2008-10-01
October 2008
The main objective of the Working Paper series of IIMA is to help faculty members,
research sta, and doctoral students to speedily share their research ndings with
professional colleagues and to test out their research ndings at the pre-publication stage.
INDIAN INSTITUTE OF MANAGEMENT
AHMEDABAD – 380015
INDIA
W.P. No. 2008-10-01
Page No. 1
IIMA
•
INDIA
Research and Publications
A Review of the Tabu Search Literature on Traveling
Salesman Problems
Sumanta Basu
1
Diptesh Ghosh
2
Abstract
The Traveling Salesman Problem (TSP) is one of the most widely studied problems in
combinatorial optimization. It has long been known to be
NP-hard
and hence research on
developing algorithms for the TSP has focused on approximate methods in addition to exact
methods. Tabu search is one of the most widely applied metaheuristic for solving the TSP. In
this paper, we review the tabu search literature on the TSP, point out trends in it, and bring
out some interesting research gaps in this literature.
Keywords:
Traveling Salesman Problems, Tabu Search
1
Introduction
Many managerial problems, like routing problems, facility location problems, scheduling problems,
network design problems, can either be modeled as combinatorial optimization problems, or solve
combinatorial optimization problems as sub-problems. A very commonly researched combinatorial
optimization problem in this and other contexts is the Traveling Salesman Problem (TSP). In a
TSP (see e.g., [37]) we are given a weighted graph with
n
nodes, and are required to nd a tour
in the graph visiting each node exactly once such that the sum of the costs of the edges or arcs in
the tour is the minimum possible. The number
n
is commonly referred to as the size of the TSP.
TSPs serve as a representation of many managerial problems, especially in logistics. Many more
problems, though not obviously related to the TSP can be modeled as TSPs. A large number of
other problems are not equivalent to solving TSPs, but solve TSPs as subproblems.
Apart from being a recurrent problem in managerial situations, the TSP is among the most
widely studied problems in combinatorial optimization. It was one of the rst problems whose
decision version was shown to be
NP-complete
(see [35]), and has been a testbed for theoretical
and computational studies ever since. Rich classes of benchmark problems exist for the TSP (see
e.g., [44, 34]), as do ecient implementations for solving reasonably large problems to optimality
(see for example, NEOS:
http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html).
The TSP is known to be
NP-hard.
This means that no known algorithm is guaranteed to
solve all TSP instances to optimality within reasonable execution time. So in addition to exact
solution approaches, a number of heuristics and metaheuristics have been developed to solve problems
approximately. Heuristics and metaheuristics trade optimality of the solutions that they output with
execution times. They are used to nd “good” quality solutions within reasonable execution times.
The term heuristic is normally used to describe an approximate solution method that is intended
for one particular optimization problem, while the term metaheuristic is used to describe a more
1
Wipro
2
IIM
Technologies, Bangalore, India; Email: sumanta.basu2@wipro.com
Ahmedabad, India; Email: diptesh@iimahd.ernet.in
W.P. No. 2008-10-01
Page No. 2
IIMA
•
INDIA
Research and Publications
general framework that can be easily adapted to solve a wide variety of problems. Metaheuristics are
normally improvement algorithms, i.e., they start with one or more feasible solutions to the problem
at hand and suggest methods for improving such solutions. Typical examples of metaheuristics
include local search, tabu search, simulated annealing, and genetic algorithms.
The literature shows that tabu search is possibly the most widely used and most successful
metaheuristic procedure to solve combinatorial optimization problems. Figure 1 shows the number
of papers published every year on tabu search implementations for the TSP and related problems. It
8
6
Frequency
4
2
0
1989
1991
1993
1995
1997
1999
2001
2003
2005
2007
Year
Figure 1: Papers dealing with tabu search implementations for the TSP and related problems
is an improvement heuristic based on local search. It starts with an initial solution to the problem,
(a tour in case of the TSP), calls it a current solution, and searches for the best solution in a
suitably dened neighborhood (a collection of tours that can be “easily” reached from the current
solution) of the solution. It then designates the best solution in the neighborhood as the current
solution and starts the search process again. Tabu search terminates when certain terminating
conditions, either involving execution time conditions, or solution quality objectives, or both, have
been met. In order to prevent tabu search from considering solutions that it has visited in recent
iterations, tabu search maintains a list of neighbor generation moves that it considers forbidden, or
tabu (hence the name, tabu search) and ignores solutions that can be reached only through tabu
moves while searching the neighborhood of a solution. Once a move enters the list of tabu moves,
it stays there for a number of tabu search iterations (called the tabu tenure of the move). The
list of tabu moves therefore changes continuously during the execution of the search, making tabu
search an adaptive memory search algorithm. Several researchers have added features that enrich
the basic tabu search algorithm described here, such as intermediate term memory structures, long
term memory structures, and aspiration criteria, which have been widely applied to tabu search
implementations for most problems like the TSP. Other features that have been proposed, but not
commonly implemented for tabu search on TSPs are strategic oscillation, path relinking, candidate
list strategies etc.
In this paper, we review the literature on application of tabu search to TSPs and problems very
closely related to it, like vehicle routing problems (VRP). We reviewed 58 papers on the application
of tabu search to these problems. The papers that we reviewed mostly appeared in print in the
last fteen years. We classify the literature based on problem size (Section 2), generation of initial
W.P. No. 2008-10-01
Page No. 3
IIMA
•
INDIA
Research and Publications
solutions (Section 3), selection of moves (Section 4), the choice of short, medium, and long term
memory structures (Section 5 through Section 7), and aspiration criteria (Section 8). We summarize
our ndings in Section 9.
2
Problem Sizes Considered
44 papers describe experimental results of using tabu search on TSPs. Table 1 provides a summary
of the maximum size of TSPs considered by dierent authors in the literature. It is interesting
to note that even though metaheuristics are meant to handle large problems, more than half the
authors deal only with TSPs with up to 100 nodes. Most of these authors have used the benchmark
problems described in [53] which contain 56 instances with 100 nodes each. Till date, we have only
seen three papers ([7], [16], and [32]) that implement tabu search on TSPs with between 500 and
1035 nodes.
Table 1: Papers implementing tabu search on TSPs and problem sizes they consider
Number of nodes
100 or less
Before 1996
[22, 39, 50]
1996 – 2000
[2, 4, 8, 13, 20,
21, 26, 30, 41,
43, 51, 62]
[3]
[5, 9, 63]
—
[27, 25]
—
[45]
[55]
[61]
2001 – 2005
[11, 31, 32, 33,
36, 56]
[12, 15]
—
—
[15]
—
—
[14, 57]
[7, 16, 32]
After 2006
[6, 38]
Total
23
101
151
201
251
301
351
401
451
– 150
– 200
– 250
– 300
– 350
– 400
– 450
or more
—
[24, 42, 46]
[17]
—
—
—
[59]
—
[49]
[1, 38]
[18]
—
—
[40]
—
—
4
8
2
3
—
2
4
4
Numbers refer to citation numbers in References list.
With the advent of more powerful computers one would expect recent papers to deal with larger
problems. However, as is evident from Table 1, this trend is not observed in practice. For example,
in the last three years, we have not encountered a single paper that implements tabu search on TSPs
with more than 400 nodes.
3
Generation of Initial Solutions
Tabu search is an improvement heuristic. It needs to start with a feasible tour in the graph describing
the TSP. 32 of the 58 papers surveyed describe the process used to obtain initial solutions. In these,
8 methods were used to generate initial solutions. These 8 methods are given below:
GRASP: (General Randomized Adaptive Search Process)
This method is a modication
of a greedy tour construction heuristic. In a greedy heuristic, a tour is constructed by growing
a path in the graph and joining the end points once the path includes all the nodes in the
graph. The rst point is randomly chosen, and the node closest to the endpoints of the path
being formed is the next point to be added to the path. In a GRASP heuristic, the point that
is added to the path being grown is not necessarily the closest one to the endpoints, but a
random one chosen from a set of points that are close enough to the endpoints of the existing
path.
W.P. No. 2008-10-01
Page No. 4
IIMA
•
INDIA
Research and Publications
RandIns: (Randomized insertion)
This method starts with a partial tour and inserts nodes
randomly into tour without forming sub-tours in between. It stops when all nodes in the
graph have been included in the tour.
NrNbr: (Nearest neighbor)
This method starts with a partial tour. It then uses a modied
Prim’s algorithm to nd a node in the graph which is not in the partial tour, and is nearest
to a node already existing in the partial tour. It then adds this node to the partial tour. If
the graph describing the TSP is not complete, there is a possibility that after the completion
of this procedure, some of the nodes remain unconnected to the tour. These nodes are then
added to the tour using the RandIns procedure (see e.g., [8]).
NrMrgr: (Nearest merger)
This method forms subtours in the graph describing the TSP. It
then modies Kruskal’s algorithm to coalasce the subtours into a complete tour.
PrNrNbr: (Probabilistic nearest neighbor)
This is a probabilistic version of nearest neigh-
borhood heuristic. It starts with a partial tour. Then, for each node already in the partial
tour, the neighboring nodes are assigned probabilities of being connected to the node. The
probability is higher for a node which has lower cost of joining to the node being considered.
The heuristic then chooses one of the neighboring nodes probabilistically and adds it to the
partial tour. It stops when all the nodes in the graph are included in the tour.
Sweep: (Sweep method)
This heuristic is suited for TSPs dened on a plane. An initial node is
chosen, and all the other nodes are order according to the angles they make with the starting
node. They are then added to the tour in the same order.
Solomon: (Solomon’s heuristic)
It is a combination of the nearest neighbor heuristic and the
sweep heuristic.
GENI: (GENeralized Insertion)
Developed by [23], it constructs a tour by inserting vertices
between two non-successive nodes in a partial tour.
Table 2: Methods of forming initial solutions for tabu search
Method
GRASP
RandIns
NrNbr
NrMrgr
PrNrNbr
Sweep
Solomon
GENI
Before 1996
—
—
—
—
—
—
[22]
[24]
1996 – 2000
[20]
[4, 55, 5, 41]
[8, 13, 20, 62,
5, 63]
—
—
—
[43]
[25]
2001 – 2005
—
[15, 57, 52]
[10, 12, 36, 31,
52]
[7]
[7]
[14]
—
—
After 2006
—
[58]
[38, 40, 49]
—
—
[40, 49, 18]
—
—
Total
1
8
14
1
1
4
2
2
Numbers refer to citation numbers in References list.
Table 2 summarizes the use of the 8 methods to form initial solutions in the tabu search literature
on the TSP. We observe that the nearest neighborhood heuristic (NrNbr) is the most common choice
followed by randomized insertion heuristic (RndIns). We feel that these heuristics are chosen because
they are the easiest to implement for TSPs, and also because given enough execution time, tabu
search is thought to be powerful enough to obtain good solutions regardless of the initial solution
presented to the search process.
4
Choice of Moves
Tabu search being an improvement heuristic moves from one solution to the next in search of an
optimal solution. The method of moving from one solution to another is described by a set of
W.P. No. 2008-10-01
Page No. 5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin