EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1138. Benders Decomposition for Robust Tactical Crew Scheduling
Invited abstract in session MB-54: Crew Planning in Public Transport, stream Public Transport Optimization.
Monday, 10:30-12:00Room: S01 (building: 101)
Authors (first author is the speaker)
| 1. | Bart van Rossum
|
| Erasmus School of Economics, Erasmus University Rotterdam | |
| 2. | Twan Dollevoet
|
| Econometric Institute, Erasmus University of Rotterdam | |
| 3. | Dennis Huisman
|
| Econometric Institute, Erasmus University |
Abstract
We consider robust tactical crew scheduling for a large passenger railway operator, whose timetable is subject to minor but uncertain updates on a weekly basis. Before the start of the planning period we must select a number of templates, specifying the time windows in which crew is supposed to work. These templates must be cost-efficient whilst providing sufficient capacity for the realised updated timetables. Moreover, the templates must be compatible with the rostering process, i.e., we wish to limit the number of different templates used and ensure that there are not too many templates on early or late moments of the day. Throughout the planning period, the templates are assumed to be fixed and the updated timetable is released on a weekly basis. All tasks in the timetable must be covered using the capacity provided by the templates, or, if necessary, costly reserve capacity. We model the template selection problem as a scenario-based robust optimisation model, for which we propose a Benders decomposition algorithm. We conduct computational experiments on real-life instances from Netherlands Railways and show that our algorithm is able to solve instances featuring up to three scenarios and up to 1,000 tasks per scenario to optimality. Including more scenarios, allowing for more flexibility in choosing templates, or enlarging the template length all lead to reductions in reserve crew costs without increasing template-based crew costs.
Keywords
- Railway Applications
- Robust Optimization
- Column Generation
Status: accepted
Back to the list of papers