|
Introduction
-
The Double Traveling
Salesman Problem with Multiple Stacks (DTSPMS)
was introduced by
Hanne L. Petersen in 2006 in a
technical report.
-
The DTSPMS
is
NP-hard and quite more difficult to solve than the TSP.
-
There is
more information available about the first papers related to
the DTSPMS and the first problem instances generated for it
(sizes of 33 and 66 orders) in Petersen's web site:
http://www2.imm.dtu.dk/~hlp/
-
I
approached this problem on my
PhD thesis (in
Spanish). Solving
problem instances of reasonable size is computationally
intractable, so we have concentrated on heuristics.
Instances for the DTSPMS
-
The first
instances for the DTSPMS were generated by Hanne L. Petersen
and they are available in her web site:
http://www2.imm.dtu.dk/~hlp/.
-
These
instances and all the ones generated afterwards are
available in the TSP-format, that is used, for example, by
Concorde software.
-
Each
instance is determined by two .tsp files with
identical names but the last character: the file ending with
a p character contains the data corresponding to the
pickup network and the one ending with a d contains
the data corresponding to the delivery network.
-
3 sets
of 10 instances with 33, 66 and 132
orders were generated for
calibration of parameters.
These 3 sets are available here in a .zip file:
Set
C33 (10 instances with 33
orders)
Set
C66 (10 instances with 66
orders)
Set
C132 (10 instances with 132
orders)
-
We also
generated another set of 20 instances with 132 orders
to evaluate the performance of the designed heuristics for
larger instances, complementing the other two sets of
instances with size 33 and 66 that were generated in
the first papers on the DTSPMS. These 132-order instances
are available here in a .zip file:
Set
T132 (20 instances with 132
orders)
-
Recently we
have also generated other sets of instances in which pickup
and delivery locations are not generated uniformly, but they
are grouped in clusters of different sizes. We have
considered 5 types of instances and 3 sizes (33, 66 and 132
orders) and 10 instances of each type have been generated.
These instances are available here in a .zip file:
Set
Clusters (150 instances, 5 types, sizes 33, 66 and 132)
Heuristic
algorithms
-
The first
heuristic algorithms that were applied to the DTSPMS (H. L. Petersen,
2006) were Tabu Search, Simulated Annealing
and Steepest Descent, using 2
neighborhood structures to perform local search.
-
Then we
proposed 4 new different neighborhood structures that
were used, together with the two other existing ones, to
design a Variable Neighborhood Search (VNS) algorithm
for the DTSPMS. The designed neighborhood structures and the
developed algorithms are detailed in the following
references:
- A. Felipe, M.T. Ortuño, G. Tirado. The Double Traveling
Salesman Problem with Multiple Stacks: a
Variable Neighborhood Search approach. Computers & Operations Research
36: 2983-2993 (2009).
- A. Felipe, M.T. Ortuño, G. Tirado. New neighborhood structures for the Double Traveling Salesman Problem With
Multiple Stacks. TOP 17: 190-213 (2009).
Presentations
|
