Data di Pubblicazione:
2006
Citazione:
Dynamic programming for the orienteering problem with time windows / G. Righini, M. Salani. - Crema (CR) : Università degli Studi di Milano - Polo Didattico e di Ricerca di Crema, 2006 Mar.
Abstract:
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.
Tipologia IRIS:
08 - Relazione interna o rapporto di ricerca
Keywords:
Keywords: Combinatorial optimization; traveling salesman problem; shortest path problem;
dynamic programming.
Elenco autori:
G. Righini, M. Salani
Link alla scheda completa:
Link al Full Text: