Crew Scheduling: from Planning towards Operations
Speaker
Abstract
| During the last decade, many Operations Research models and techniques have been developed to solve planning problems arising in the railway industry. The main challenge for the OR community in the coming decades is to develop models and algorithms for optimization problems during the operations. A good example is the crew scheduling problem, which is the topic of this presentation. At NS (the largest Dutch railway operator), the crew scheduling problem is solved once a year from scratch. A dedicated commercial solver (TURNI) is used for this purpose. Later on, during the year, there are every day modifications in the crew schedules necessary. This is mainly caused by maintenance activities on the infrastructure resulting in tracks which are out of service for some time. As a consequence, a modified timetable is run, and rolling stock and crew schedules become infeasible. To repair the crew schedule, re-scheduling is necessary. This problem is called the Crew Re-Scheduling Problem (CRSP), which is still a planning problem but very close to operations. We give a formal definition of the CRSP. Furthermore, we show that we can formulate it as a large-scale set covering problem, which can be solved with an algorithm based on column generation techniques. This algorithm has been initially implemented in a prototype. After successful tests, it has been implemented in the commercial crew scheduling package CREWS. Since August 2006, the re-scheduling algorithm in CREWS has been used on a regular basis to re-schedule drivers. In this presentation, we will give a short demonstration how this algorithm is used by the planners of NS. Finally, we will spend some words on the possibilities and difficulties to use such an algorithm during the operations. |
| Contact information: |
| Naima Zerhane |
