Enhanced bi-directional dynamic programming algorithm for the resource constrained shortest path problem

Abstract

We present an enhanced bi-directional dynamic programming algorithm for the resource constrained shortest path problem (RCSPP), improving upon classical bounded dynamic programming approaches through refined dominance criteria and state space relaxation strategies.

Combinatorial OptimizationDynamic ProgrammingShortest PathTransportation

BibTeX

@article{salani2024enhanced,
  title     = {Enhanced bi-directional dynamic programming algorithm for the resource constrained shortest path problem},
  author    = {Salani, Matteo and Basso, Saverio and Righini, Giovanni},
  journal   = {Transportation Research Procedia},
  volume    = {78},
  pages     = {361--368},
  year      = {2024},
  publisher = {Elsevier}
}