2026-07-23T07:57:21Z https://drops.dagstuhl.de/oai

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

A Matching Approach for Periodic Timetabling Pätzold, Julius Schöbel, Anita PESP Timetabling Public Transport Matching Finite Dominating Set The periodic event scheduling problem (PESP) is a well studied problem known as intrinsically hard, but with important applications mainly for finding good timetables in public transportation. In this paper we consider PESP in public transportation, but in a reduced version (r-PESP) in which the driving and waiting times of the vehicles are fixed to their lower bounds. This results in a still NP-hard problem which has less variables, since only one variable determines the schedule for a whole line. We propose a formulation for r-PESP which is based on scheduling the lines. This enables us on the one hand to identify a finite candidate set and an exact solution approach. On the other hand, we use this formulation to derive a matching-based heuristic for solving PESP. Our experiments on close to real-world instances from LinTim show that our heuristic is able to compute competitive timetables in a very short runtime. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julius Pätzold and Anita Schöbel 2016 Is Part Of OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2016.1 urn:nbn:de:0030-drops-65251 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.1 eng https://creativecommons.org/licenses/by/3.0/legalcode