The Periodic Event Scheduling Problem (PESP) is the method of choice for real-world periodic timetabling in public transport. Its MIP formulation has been studied intensely for the case of uniform modules, i.e., when all events have the same period. In practice, multiple periods are equally important. Yet, the powerful methods developed for uniform modules generally fail for the multi-module case. We analyze a certain type of Diophantine equation systems closely related to the multi-module PESP. Thereby, we identify a structure, so-called sharp trees, that allows to solve the system in O(n2) time if the modules form a linear lattice. Based on this we develop the machinery to solve multi-module PESPs on real-world scale. In our computational results the new MIP-formulations considerably improve the solvability of multi-module PESPs. © 2010 Springer-Verlag.

Galli, L., Stiller, S. (2010). Strong formulations for the multi-module PESP and a quadratic algorithm for graphical diophantine equation systems. Springer [10.1007/978-3-642-15775-2_29].

Strong formulations for the multi-module PESP and a quadratic algorithm for graphical diophantine equation systems

Galli L.;
2010

Abstract

The Periodic Event Scheduling Problem (PESP) is the method of choice for real-world periodic timetabling in public transport. Its MIP formulation has been studied intensely for the case of uniform modules, i.e., when all events have the same period. In practice, multiple periods are equally important. Yet, the powerful methods developed for uniform modules generally fail for the multi-module case. We analyze a certain type of Diophantine equation systems closely related to the multi-module PESP. Thereby, we identify a structure, so-called sharp trees, that allows to solve the system in O(n2) time if the modules form a linear lattice. Based on this we develop the machinery to solve multi-module PESPs on real-world scale. In our computational results the new MIP-formulations considerably improve the solvability of multi-module PESPs. © 2010 Springer-Verlag.
2010
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
338
349
Galli, L., Stiller, S. (2010). Strong formulations for the multi-module PESP and a quadratic algorithm for graphical diophantine equation systems. Springer [10.1007/978-3-642-15775-2_29].
Galli, L.; Stiller, S.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/1000275
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact