A concurrent approach to the periodic event scheduling problem. (September 2020)

• Record Type: Journal Article
• Authors: Borndörfer, Ralf; Lindner, Niels; Roth, Sarah
• Is Part Of: Journal of rail transport planning & management. Volume 15(2020)
• Publication Date: 2020-09
• Subjects: Periodic event scheduling problem -- Periodic timetabling -- Mixed integer programming; Railroads -- Periodicals; Railroads -- Planning -- Periodicals; Railroads -- Management -- Periodicals; Railroads; Railroads -- Management; Railroads -- Planning; Periodicals; 385.068
• DOI: 10.1016/j.jrtpm.2019.100175
• Languages: English
• ISSNs: 2210-9706

Abstract

Abstract: We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib. Highlights: A concurrent solver for the Periodic Event Scheduling Problem (PESP). Combines many state-of-the-art techniques in periodic timetabling. Computes current best primal and dual bounds for all PESPlib instances.