van Lieshout, Rolf N. ;
Bouman, Paul C.
Vehicle Scheduling Based on a Line Plan
Abstract
We consider the following problem: given a set of lines in a public transportation network with their round trip times and frequencies, a maximum number of vehicles and a maximum number of lines that can be combined into a vehicle circulation, does there exist a set of vehicle circulations that covers all lines given the constraints. Solving this problem provides an estimate of the costs of operating a certain line plan, without having to compute a timetable first. We show that this problem is NPhard for any restriction on the number of lines that can be combined into a circulation which is equal to or greater than three. We pay special attention to the case where at most two lines can be combined into a circulation, which is NPhard if a single line can be covered by multiple circulations. If this is not allowed, a matching algorithm can be used to find the optimal solutions, which we show to be a 16/15approximation for the case where it is allowed. We also provide an exact algorithm that is able to exploit low treewidth of the socalled circulation graph and small numbers of vehicles required to cover single circulations.
BibTeX  Entry
@InProceedings{vanlieshout_et_al:OASIcs:2018:9720,
author = {Rolf N. van Lieshout and Paul C. Bouman},
title = {{Vehicle Scheduling Based on a Line Plan}},
booktitle = {18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
pages = {15:115:14},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783959770965},
ISSN = {21906807},
year = {2018},
volume = {65},
editor = {Ralf Bornd{\"o}rfer and Sabine Storandt},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9720},
URN = {urn:nbn:de:0030drops97204},
doi = {10.4230/OASIcs.ATMOS.2018.15},
annote = {Keywords: Vehicle scheduling, integrated railway planning, (fractional) matching, treewidth}
}
2018
Keywords: 

Vehicle scheduling, integrated railway planning, (fractional) matching, treewidth 
Seminar: 

18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Issue date: 

2018 
Date of publication: 

2018 