The vehicle rescheduling problem: Model and algorithms

Jing Quan Li, Pitu B. Mirchandani, Denis Borenstein

Research output: Contribution to journalArticlepeer-review

45 Scopus citations


When a vehicle on a scheduled trip breaks down, one or more vehicles need to be rescheduled to serve the customers on that trip with minimum operating and delay costs. The problem of reassigning vehicles in real-time to this cut trip as well as to other scheduled trips with given starting and ending times, is referred to as the vehicle rescheduling problem (VRSP). This paper considers modeling, algorithmic, and computational aspects of the single-depot VRSP. The paper formulates a model for this problem and develops several fast algorithms to solve it, including parallel synchronous auction algorithms. The concept of the common feasible network (CFN) is introduced to find a good set of initial "prices" for speeding up the auction algorithm. Computational experiments on randomly generated problems are described. Computational results show that, for small problems, all of the developed algorithms demonstrate very good computational performances. For large problems, parallel CFN-based auction algorithms provide the optimal solution with much smaller computation times.

Original languageEnglish (US)
Pages (from-to)211-229
Number of pages19
Issue number3
StatePublished - Oct 2007
Externally publishedYes


  • Auction algorithm
  • Parallel processing
  • Rescheduling
  • Vehicle scheduling

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'The vehicle rescheduling problem: Model and algorithms'. Together they form a unique fingerprint.

Cite this