2026-07-23T15:20:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9720 2024-03-06T10:30:27Z ddc:004 open_access

Vehicle Scheduling Based on a Line Plan van Lieshout, Rolf N. Bouman, Paul C. Vehicle scheduling integrated railway planning (fractional) matching treewidth 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 NP-hard 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 NP-hard 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/15-approximation for the case where it is allowed. We also provide an exact algorithm that is able to exploit low tree-width of the so-called circulation graph and small numbers of vehicles required to cover single circulations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rolf N. van Lieshout and Paul C. Bouman 2018 Is Part Of OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2018.15 urn:nbn:de:0030-drops-97204 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.15 eng https://creativecommons.org/licenses/by/3.0/legalcode