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.

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.

Dynamic programming for the orienteering problem with time windows

G. Righini;M. Salani
2006

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.
Keywords: Combinatorial optimization; traveling salesman problem; shortest path problem; dynamic programming.
Settore MAT/09 - Ricerca Operativa
Working Paper
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.
File in questo prodotto:
File Dimensione Formato  
optw.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 176.83 kB
Formato Adobe PDF
176.83 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/6449
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact