Premium
The vehicle rescheduling problem: Model and algorithms
Author(s) -
Li JingQuan,
Mirchandani Pitu B.,
Borenstein Denis
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20199
Subject(s) - computer science , computation , auction algorithm , mathematical optimization , set (abstract data type) , vehicle routing problem , algorithm , routing (electronic design automation) , common value auction , mathematics , auction theory , computer network , statistics , revenue equivalence , programming language
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. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(3), 211–229 2007