A Global Method for Crew Planning in Railway Applications
Crew planning is a typical problem arising in the management of large transit systems (such as railway and airline companies). Given a set of train services to be performed every day, the problem calls for a set of crew rosters covering the train services
- PDF / 11,885,714 Bytes
- 20 Pages / 439.37 x 666.14 pts Page_size
- 21 Downloads / 285 Views
Abstract . Crew planning is a typi cal problem arising in the management of large transit systems (such as railway and airline companies). Given a set oftrain services to be performed every day , the problem calls for a set of crew rosters covering the train services at minimum cost . Although the cost may depend on several factors, the main objective is to minimize the number of cr ews needed to perform the rosters. The process of constructing the rosters from the train services has been historically subdivided into three indepe ndent phases, called pairing generation, pairing optimization , and rostering optimization , as is the case for the approach presented in Caprara et al. (1999a) for the Italian railways. In that paper, it is suggested that a feedback between the last two phases may significantly improve the quality of the final solution. In this paper, we illustrate the implementation of a new crew planning system within the EU Project TRIO. In particular, we describe the design of a new module for pairing generation, as weil as an effective technique for integrating the pairing and rostering optimization phases into a unique one. The improvements over the previous approach are shown through computational results on real-world instances.
1
Introduction
Crew planning is a typical problem arising in the management of large transit systems (such as railway and airline companies). In this paper, we focus on the problem arising in railway applications, and in particular at Ferrovie dello Stato SpA (FS for short), the Italian railway company. As input, one is given a set D of depots, where the available crews are located, and a planned timetable for the train services (i.e., both the actual journeys for passengers or freight, and the transfers of empty trains or equipment between different st ations) t o be performed every day of a certain time period. Each t rain service is first split into a sequence of trips, defined as segments of t rain journeys which must be ser viced by t he same crew without rest. Each t rip is characterized by a departure time, a departure station, an arrival time, an arrival station, a travel distance, and possibly by additional attributes. All the times are expressed in minutes from 1 to 1440 (I.e., 24 S. Voß et al. (eds.), Computer-Aided Scheduling of Public Transport © Springer-Verlag Berlin Heidelberg 2001
18
Caprara, Monaci, and Toth
hours). During the given time period each crew can perform e roster, defined as a cyclic sequence of trips whose operational cost and feasibility depend on several rules laid down by union contracts and company regulations. To ensure that each daily occurrence of a trip is performed by one crew, for each roster whose length is, say, k days, k crews are needed. In fact, in a given calendar day each of these crews performs the activities of a different day of the roster. Moreover, in consecutive calendar days each crew performs the activities of (cyclically) consecutive days of the roster. The crew planning problem then consists of finding a set
Data Loading...
