A Lagrangian heuristic for the real-time vehicle rescheduling problem

Jing-Quan Li, Pitu B. Mirchandani and Denis Borenstein

Transportation Research Part E: Logistics and Transportation Review, 2009, vol. 45, issue 3, 419-433

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.

Keywords: Vehicle; scheduling; Schedule; disruption; Lagrangian; heuristic; Rescheduling (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554508001166
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:45:y:2009:i:3:p:419-433

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().