A column generation algorithm for the vehicle routing problem with soft time windows

Abstract

We present a column generation algorithm for the vehicle routing problem with soft time windows, where time window violations are penalized. The pricing subproblem is solved with an efficient dynamic programming algorithm, and the method is embedded in a branch-and-price framework to obtain provably optimal solutions.

Vehicle RoutingColumn GenerationTime Windows

BibTeX

@article{liberatore2011column,
  title={A column generation algorithm for the vehicle routing problem with soft time windows},
  author={Liberatore, Federico and Righini, Giovanni and Salani, Matteo},
  journal={4or},
  volume={9},
  number={1},
  pages={49--82},
  year={2011},
  publisher={Springer-Verlag Berlin/Heidelberg}
}