Template-Type: ReDIF-Paper 1.0
Author-Name: van Lieshout, R.N.
Author-Name-Last: van Lieshout
Author-Name-First: Rolf
Author-Name: Mulder, J.
Author-Name-Last: Mulder
Author-Name-First: Judith
Author-Name: Huisman, D.
Author-Name-Last: Huisman
Author-Name-First: Dennis
Author-Person: phu27
Title: The Vehicle Rescheduling Problem with Retiming
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.
Length: 20
Creation-Date: 2016-11-01
File-URL: https://repub.eur.nl/pub/95143/EI2016-37.pdf
File-Format: application/pdf
Series: RePEc:ems:eureir
Number: EI2016-37
Keywords: Vehicle rescheduling, retiming, Lagrangian heuristic
Handle: RePEc:ems:eureir:95143