Journal Discrete Optimization, 2006

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

Giovanni Righini · Matteo Salani

Paper

Abstract

This paper introduces a bounded bi-directional dynamic programming algorithm for the elementary shortest path problem with resource constraints (ESPPRC), exploiting symmetry to reduce the state-space and improve computational efficiency. The approach provides significant speedups compared to standard forward dynamic programming and is relevant to column generation in vehicle routing.

Dynamic ProgrammingVehicle RoutingCombinatorial Optimization

BibTeX

@article{righini2006symmetry,
  title={Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints},
  author={Righini, Giovanni and Salani, Matteo},
  journal={Discrete Optimization},
  volume={3},
  number={3},
  pages={255--273},
  year={2006},
  publisher={Elsevier}
}