Vehicle rescheduling problem

The vehicle rescheduling problem (VRSP) is a combinatorial optimization and integer programming problem seeking to service customers on a trip after change of schedule such as vehicle break down or major delay.

Proposed by Li, Mirchandani and Borenstein in 2007,[1] the VRSP is an important problem in the fields of transportation and logistics.

Determining the optimal solution is an NP-complete problem in combinatorial optimization[citation needed], so in practice heuristic and deterministic methods are used to find acceptably good solutions for the VRSP.

Several variations and specializations of the vehicle rescheduling problem exist: Although VRSP is related to the Single Depot Vehicle Scheduling Problem and the Multi Depot Vehicle Scheduling Problem, there is a significant difference in runtime requirements, as VRSP need to be solved in near real-time to allow rescheduling during operations, while SDVSP and MDVSP are typically solved using long running linear programming methods.

[2] Another field where VRSP is used is in transportation of goods in order to reschedule the routes when demand substantially changes[3]