Righini, G., and Salani, M. (2009)

Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming, Computers & Operations Research 36(4):1191-1203.

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

doi:10.1016/j.cor.2008.01.003 (click here for the full paper)