Loading...
research article
Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming
We present an exact optimization algorithm for the Orienteering Problem with Time Windows (OPTW). The algorithm is based on bi-directional and bounded dynamic programming with decremental state space relaxation. We compare different strategies proposed in the literature to guide decremental state space relaxation: our experiments on instances derived from the literature show that there is no dominance between these strategies. We also propose a new heuristic technique to initialize the critical vertex set and we provide experimental evidence of its effectiveness
Type
research article
Authors
Publication date
2009
Published in
Volume
36
Issue
4
Start page
1191
End page
1203
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
February 15, 2008
Use this identifier to reference this record