文章基本信息

标题：A Matching Approach for Periodic Timetabling
本地全文：下载
作者：Julius P{\"a}tzold ; Anita Sch{\"o}bel
期刊名称：OASIcs : OpenAccess Series in Informatics
电子版ISSN：2190-6807
出版年度：2016
卷号：54
页码：1-15
DOI：10.4230/OASIcs.ATMOS.2016.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：PESP; Timetabling; Public Transport; Matching; Finite Dominating Set