{"ID":2891393,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.17566","arxiv_id":"2507.17566","title":"A Compact Cycle Formulation for the Multiperiodic Event Scheduling Problem","abstract":"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.","short_abstract":"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 gen...","url_abs":"https://arxiv.org/abs/2507.17566","url_pdf":"https://arxiv.org/pdf/2507.17566v1","authors":"[\"Rolf Nelson van Lieshout\",\"Niels Lindner\"]","published":"2025-07-23T14:57:31Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}