A Compact Cycle Formulation for the Multiperiodic Event Scheduling Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913956527865856 |
|---|---|
| author | van Lieshout, Rolf Nelson Lindner, Niels |
| author_facet | van Lieshout, Rolf Nelson Lindner, Niels |
| contents | The Periodic Event Scheduling Problem (PESP) is a fundamental model in periodic timetabling for public transport systems, assuming a common period across all events. However, real-world networks often feature heterogeneous service frequencies. This paper studies the Multiperiodic Event Scheduling Problem (MPESP), a generalization of PESP that allows each event to recur at its own individual period. While more expressive, MPESP presents new modeling challenges due to the loss of a global period. We present a cycle-based formulation for MPESP that extends the strongest known formulation for PESP and, in contrast to existing approaches, is valid for any MPESP instance. Crucially, the formulation requires a cycle basis derived from a spanning tree satisfying specific structural properties, which we formalize and algorithmically construct, extending the concept of sharp spanning trees to rooted instances. We further prove a multiperiodic analogue of the cycle periodicity property. Our new formulation solves nearly all tested instances, including several large-scale real-world public transport networks, to optimality or with small optimality gaps, dramatically outperforming existing arc-based models. The results demonstrate the practical potential of MPESP in capturing heterogeneous frequencies without resorting to artificial event duplication. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_17566 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Compact Cycle Formulation for the Multiperiodic Event Scheduling Problem van Lieshout, Rolf Nelson Lindner, Niels Optimization and Control The Periodic Event Scheduling Problem (PESP) is a fundamental model in periodic timetabling for public transport systems, assuming a common period across all events. However, real-world networks often feature heterogeneous service frequencies. This paper studies the Multiperiodic Event Scheduling Problem (MPESP), a generalization of PESP that allows each event to recur at its own individual period. While more expressive, MPESP presents new modeling challenges due to the loss of a global period. We present a cycle-based formulation for MPESP that extends the strongest known formulation for PESP and, in contrast to existing approaches, is valid for any MPESP instance. Crucially, the formulation requires a cycle basis derived from a spanning tree satisfying specific structural properties, which we formalize and algorithmically construct, extending the concept of sharp spanning trees to rooted instances. We further prove a multiperiodic analogue of the cycle periodicity property. Our new formulation solves nearly all tested instances, including several large-scale real-world public transport networks, to optimality or with small optimality gaps, dramatically outperforming existing arc-based models. The results demonstrate the practical potential of MPESP in capturing heterogeneous frequencies without resorting to artificial event duplication. |
| title | A Compact Cycle Formulation for the Multiperiodic Event Scheduling Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2507.17566 |