Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming
Articolo
Data di Pubblicazione:
2009
Citazione:
Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming / G. Righini, M. Salani. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 36:4(2009), pp. 1191-1203.
Abstract:
We present an exact optimization algorithm for the Orienteering Problem with TimeWindows (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:
01 - Articolo su periodico
Keywords:
Combinatorial optimization ; Traveling salesman problem ; Shortest path problem ; Dynamic programming
Elenco autori:
G. Righini, M. Salani
Link alla scheda completa: