dc.contributor.author
Masing, Berenike
dc.contributor.author
Lindner, Niels
dc.contributor.author
Ebert, Patricia
dc.date.accessioned
2024-10-10T05:34:34Z
dc.date.available
2024-10-10T05:34:34Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/45210
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-44922
dc.description.abstract
The optimization of periodic timetables is an indispensable planning task in public transport. Although the periodic event scheduling problem (PESP) provides an elegant mathematical formulation of the periodic timetabling problem that led to many insights for primal heuristics, it is notoriously hard to solve to optimality. One reason is that for the standard mixed-integer linear programming formulations, linear programming relaxations are weak, and the integer variables are of pure technical nature and in general do not correlate with the objective value. While the first problem has been addressed by developing several families of cutting planes, we focus on the second aspect. We discuss integral forward cycle bases as a concept to compute improved dual bounds for PESP instances. To this end, we develop the theory of forward cycle bases on general digraphs. Specifically for the application of timetabling, we devise a generic procedure to construct line-based event-activity networks and give a simple recipe for an integral forward cycle basis on such networks. Finally, we analyze the 16 railway instances of the benchmark library PESPlib, match them to the line-based structure, and use forward cycle bases to compute better dual bounds for 14 out of the 16 instances.
en
dc.format.extent
33 Seiten
dc.rights
This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
dc.rights.uri
https://creativecommons.org/licenses/by/4.0/
dc.subject
Periodic event scheduling problem
en
dc.subject
Periodic timetabling
en
dc.subject
Cycle spaces
en
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik
dc.title
Forward and Line-Based Cycle Bases for Periodic Timetabling
dc.type
Wissenschaftlicher Artikel
dc.date.updated
2024-10-04T08:25:34Z
dcterms.bibliographicCitation.doi
10.1007/s43069-023-00229-0
dcterms.bibliographicCitation.journaltitle
Operations Research Forum
dcterms.bibliographicCitation.number
3
dcterms.bibliographicCitation.originalpublishername
Springer International Publishing
dcterms.bibliographicCitation.volume
4
dcterms.bibliographicCitation.url
https://doi.org/10.1007/s43069-023-00229-0
refubium.affiliation
Mathematik und Informatik
refubium.affiliation.other
Institut für Mathematik
refubium.resourceType.isindependentpub
no
dcterms.accessRights.openaire
open access
dcterms.isPartOf.eissn
2662-2556
refubium.resourceType.provider
DeepGreen