A Lagrangian Heuristic for the Real-Time Vehicle Rescheduling Problem

Authors

Jing-Quan Li
Pitu B. Mirchandani
Denis Borenstein

Document Type

Journal Article

Publication Date

2009

Subject Area

operations - scheduling, infrastructure - vehicle, planning - methods, planning - signage/information, economics - operating costs, mode - mass transit

Keywords

Vehicle scheduling, Transit, Scheduling, Schedule disruption, Rescheduling, Real time information, Public transit, Public passenger vehicles, Operating costs, Numerical solutions, Numerical analysis, Mass transit, Local transit, Heuristic methods, Cost of operation

Abstract

When a public transit vehicle breaks down on a scheduled trip, one or more vehicles need to be rescheduled to serve that trip and other service trips originally scheduled for the disabled vehicle. In this paper, the vehicle rescheduling problem (VRSP) is investiaged to consider operating costs, schedule disruption costs, and trip cancellation costs. The VRSP is proven to be NP-hard, and a Lagrangian relaxation based insertion heuristic is developed. Extensive computational experiments on randomly generated problems are reported. The results show that the Lagrangian heuristic performs very well for solving the VRSP.

Comments

Transportation Research Part E Home Page: http://www.sciencedirect.com/science/journal/13665545

Recommended Citation

Li, Jing-Quan, Mirchandani, Pitu, Borenstein, Denis, (2009). A Lagrangian Heuristic for the Real-Time Vehicle Rescheduling Problem. Transportation Research Part E: Logistics and Transportation Review, Volume 45, Issue 3, pp 419-433.