Real-time vehicle rerouting problems with time windows

Jing Quan Li, Pitu B. Mirchandani, Denis Borenstein

Research output: Contribution to journalArticlepeer-review

102 Scopus citations


This paper introduces and studies real-time vehicle rerouting problems with time windows, applicable to delivery and/or pickup services that undergo service disruptions due to vehicle breakdowns. In such problems, one or more vehicles need to be rerouted, in real-time, to perform uninitiated services, with the objective to minimize a weighted sum of operating, service cancellation and route disruption costs. A Lagrangian relaxation based-heuristic is developed, which includes an insertion based-algorithm to obtain a feasible solution for the primal problem. A dynamic programming based algorithm solves heuristically the shortest path problems with resource constraints that result from the Lagrangian relaxation. Computational experiments show that the developed Lagrangian heuristic performs very well.

Original languageEnglish (US)
Pages (from-to)711-727
Number of pages17
JournalEuropean Journal of Operational Research
Issue number3
StatePublished - May 1 2009
Externally publishedYes


  • Lagrangian heuristic
  • Rerouting
  • Schedule recovery
  • Vehicle routing

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Real-time vehicle rerouting problems with time windows'. Together they form a unique fingerprint.

Cite this