EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3985. Integrated Vehicle Circulation and Periodic Timetabling Optimization with SMT
Invited abstract in session WA-54: Network Design and Line Planning for Public Transportation 2, stream Public Transport Optimization.
Wednesday, 8:30-10:00Room: S01 (building: 101)
Authors (first author is the speaker)
| 1. | Florian Fuchs
|
| Institute for Transport Planning and Systems, ETH Zurich | |
| 2. | Thomas Spanninger
|
| D BAUG, ETH Zurich | |
| 3. | Francesco Corman
|
| ETH Zurich |
Abstract
Our study presents a novel approach to optimizing the Periodic Timetabling Problem (PESP) and Vehicle Circulation in the Rhätische Bahn Network (RhB-Network) using Satisfiability Modulo Theories (SMT). Like traditional Mixed Integer Programming (MIP), our methodology utilizes the Event Activity Network (EAN) to model railway timetable events and activities. However, our approach encodes the PESP and vehicle circulation constraints within an SMT framework, extending SAT with difference logic. This extension allows for high-resolution time calculations, addressing the scalability limitations of existing SAT methods. Furthermore, we use selectable activities, enhancing the model's capability to incorporate vehicle circulation effectively during train scheduling and routing. Empirical analysis on a large scale, Swiss Railway Network reveals that although MIP and SMT solvers show comparable performance on smaller instances, the SMT solver significantly outperforms on larger scales, consistently finding optimal solutions. In particularly challenging instances, we achieve a reduction in computation time by a factor of 100 or more, illustrating the value of SMT-based methods in solving complex scheduling problems and advancing public transport optimization.
Keywords
- Timetabling
- Transportation
- Algorithms
Status: accepted
Back to the list of papers