Models and Algorithms of Real-Time Vehicle Rescheduling Problems under Schedule Disruptions

by Li, Jingquan.

A vehicle-based service system might be susceptible to unexpected costs and delays due to unforeseen events, such as a vehicle breakdown, a traffic accident, a medical emergency, depot overload, road work, etc. In such situations, a priori algorithmic solution may be deteriorated and fleet plans may need to be adjusted in real-time as a function of the dynamic system state. I consider real-time logistics management problems where a vehicle breaks down in the midst of operation. First, a backup vehicle needs to be determined to pick up the passengers/cargo from the breakdown vehicle, and from the breakdown point completing the remaining portion of the planned trip. This backup vehicle can be dispatched from the depot or from the vehicles currently in service. In the former case, it may impose a significant delay if the depot is far away from the breakdown location. In the latter case, the vehicle used as backup may have to change its own schedule. Trips uncompleted by this backup vehicle may have to be further covered by other vehicles. Thus, a good solution should be acquired in conjunction with the status of all other vehicles in the entire network. Yet, the new schedule may be considerably different from the original one after rescheduling is done. These changes may make the crew-rescheduling problem challenging, since it is essential to ensure that all crews know the itinerary of their new trips. Furthermore, the vehicle breakdown may not only delay the current trip that is directly affected by the disruption but also other trips that the breakdown vehicle has to cover in the network. As a result, some of the delayed trips may have to be cancelled. A good approach should consider operating cost, fixed vehicle cost, delay cost, schedule disruption cost as well as trip cancellation cost simultaneously. This real-time logistics management problem has not been properly addressed in the literature. 12 The major contributions of this study are the modeling and formulation of this real-time vehicle rescheduling problem, and the development of some fast algorithms to solve it quickly. The exact algorithms or heuristics are proposed based on the different requirements and assumptions of the problem. 13