The Vehicle Rescheduling Problem with Retiming

Rolf van Lieshout, Judith Mulder and Dennis Huisman ()

No EI2016-37, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: When a vehicle breaks down during operation in a public transportation system, the remaining vehicles can be rescheduled to minimize the impact of the breakdown. In this paper, we discuss the vehicle rescheduling problem with retiming (VRSPRT). The idea of retiming is that scheduling flexibility is increased, such that previously inevitable cancellations can be avoided. To incorporate delays, we expand the underlying recovery network with retiming possibilities. This leads to a problem formulation that can be solved using Lagrangian relaxation. As the network gets too large, we propose an iterative neighborhood exploration heuristic to solve the VRSPRT. This heuristic allows retiming for a subset of trips, and adds promising trips to this subset as the algorithm continues. Computational results indicate that the heuristic performs well. While requiring acceptable additional computation time, the iterative heuristic finds improvement over solutions that do not allow retiming in one third of the tested instances. By delaying only one or two trips with on average 4 minutes, the average number of cancelled trips is reduced with over 30 percent.

Keywords: Vehicle rescheduling; retiming; Lagrangian heuristic (search for similar items in EconPapers)
Pages: 20
Date: 2016-11-01
New Economics Papers: this item is included in nep-cmp and nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/95143/EI2016-37.pdf (application/pdf)

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:ems:eureir:95143

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).