By Manuel
López-Ibáñez, Christian Blum, Jeffrey W. Ohlmann, and
Barrett W. Thomas.
Published in Applied Soft Computing, 2013. doi: 10.1016/j.asoc.2013.05.009
October 2011 (last update: July 2013)
| Table of Contents |
In combinatorial optimization, there are many problems which are similar in
underlying mathematical structure but differ according to some feature
inherent to the motivating application area. For example, many problems in
machine scheduling and vehicle routing have equivalent formulations and only
differ with respect to the optimization objective, or particular constraints.
For varying reasons, it is common for particular problems in one application
area to be thoroughly examined by many researchers, while the problem variants
in other application domains receive much less attention. Due to the
similarity in the problems, it is intuitive that it may be effective to adapt
state-of-the-art algorithms for a well-studied problem for application on a
less-studied problem variant. In this paper we confirm this intuition using
the travelling salesman problem with time windows. In this context, the
well-studied vehicle routing version minimizes travel time, while the
less-studied machine scheduling version minimizes makespan. Indeed, the
results show that the algorithms that we adapted from travel-time optimization
to makespan optimization significantly outperform the existing
state-of-the-art approaches for the minimum makespan variant.
Keywords: ant colony optimization, compressed simulated
annealing, travelling salesman problem with time windows, hybridization
Download the TSPTW instances used for the experiments.
Instances were split into two distinct sets: