Efficient Utilisation of Resources in the Railway Industry by Levelling Departures and Arrivals of Trains

by Martin Aronsson

The raison d'etre of the transportation industry - moving things between locations - is also the source of a key problem; namely, that the resources necessary for operation are geographically distributed. This means scheduling can become an extremely complex problem, particularly in comparison to stationary industries, specifically traditional job-shop scheduling.

In the railway industry, the traditional method has been to first produce the timetable, and then to assign resources such as engines, cars and personnel to the scheduled transports. Nowadays assignments are done with optimisation tools that are based, for example, on network flow models.

However, since the deregulation of the railways in Sweden, and due to the limited capacity of the track resources, competition has increased among operators for attractive timetable slots. Although the commission of the European Union has stated that the European railway shall be deregulated, different countries have reached different developmental stages. Sweden has deregulated cargo traffic and some passenger traffic, and has separated railway management and slot allocation from traffic operations.

Figure 1: Efficient resource utilisation is a key factor in the railway industry (photo courtesy by Green Cargo).

The competition for track slots comes partly from varying customer demands on the railway operators, and partly from the growing interest in the efficient usage of expensive resources such as engines (see Figure 2). It is increasingly apparent that there are two ways to efficiently use resources, namely, optimal assignment of resources to tasks, and well-scheduled departure and arrival times, which facilitate efficient assignment. Before the application for timetable slots is made, each operator must find the best compromise between resource usage and customer demands. This stage in the planning process, made critical by deregulation, currently suffers from a lack of good decision-support tools, and improvements are necessary in order to facilitate good assignment in later stages.

Figure 2: Process flow, customer demands and resource utilisation requirements restrict the timetable process.

Over the last few years, SICS has addressed this early process stage. For a human, the variables of geography, time and assignment mean the problem rapidly becomes very complex. To help practitioners, SICS has developed a series of computational models for this process, in particular one constraint-programming model and one integer-programming model. The latter is currently being integrated into Sweden's largest cargo operator. The model is an extension of a network flow model, in which time windows have been incorporated, leading to a mixed-integer program. By relaxing the departure and arrival times to be within lower and upper bounds, and adding constraints that ensure that certain relations between trains still hold (eg for cars that should be decoupled and attached to another train), the tool can produce efficient rotations for the engines while moving the transport operations inside the time window. In the general case, a network flow model with time windows becomes very complex, but in practice it turns out that we can compute solutions to the generalised problem as long as the time windows are not too large. Using iterative application of the process, we have successfully computed solutions for time windows up to sixty minutes.

Figure 3: Resource utilisation as a function of time (5 days) with peaks every night.

In the stationary industry, this process of moving tasks in time to reduce the resources needed is sometimes referred to as 'levelling', since it tries to level the resource usage over time. While this is a simpler task in stationary industries, it is just as important in the transportation industry. In Figure 3, a typical resource graph is presented for a railway cargo company. It is the peaks that set the number of resources (engines) needed for the transportation stock. By using the levelling software, the resource peaks can be considerably reduced. Our full-scale tests have shown that 5-10% resource savings are within reach.

Link:
http://www.sics.se/iam/

Please contact:
Martin Aronsson, SICS
Tel: +46 8 63315 87
E-mail: martinsics.se