AbstractWhen 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