by Per Kreuger and Martin Aronsson
Efficient railyard shunting is essential to cargo transporters in rail networks. In this article we explore methods of handling the situation where the capacity of the shunting yard is insufficient to handle all outgoing trains.
Sweden's largest rail cargo operator, Green Cargo, performs mainly three types of cargo transport: postal services consisting of fast point-to-point transports; system train services dedicated to large flows for particular customers; and wagon-load services. Railyard shunting occurs mainly for the third type.
In the wagon-load system, individual wagons are routed from point to point through a rail network generally consisting of five shunting yards of varying sizes throughout Sweden. Wagons are transported in trains that are assembled and disassembled at the shunting yards, each of which typically handles three or four incoming trains per hour. The flow of wagons through the network varies from day to day depending on demand.
Railyard Shunting
At the shunting yard, incoming trains are scheduled to arrive at fixed times but can use the entry group as a buffer and preparation area. Each incoming train is pushed over the barrier, where wagons are separated and roll down to the shunting group. Here switches are operated so as to distribute the wagons to a number of destination tracks. Figure 1 shows the layout of the medium-sized shunting yard.
There are several limited resources at the shunting yard:
-
the entry group must be able to accommodate all incoming trains
-
the barrier has a fixed capacity in terms of wagons per hour
-
the shunting group limits the number of trains that can simultaneously be assembled.
Under 'normal' operation, a unique departing train is assembled at each destination track and departs at a predetermined time. In practice, this is not always feasible, since the capacity of the shunting group is in most cases too small for peak hour loads. To handle this, temporary trains are assembled and routed back to the entry group for re-shunting. This solution, however, leaves us with the following two considerations: which wagons should be combined into a temporary train, and when should this be routed back to the entry group and re-shunted?
Resource Considerations
We note that without temporary trains, the flow from incoming trains to outgoing trains is fixed. Figure 2 shows a small example of a typical flow and the corresponding Gantt chart and resource usage histogram.
With temporary trains, wagons destined for distinct departing trains may be routed to a single temporary train to reduce the capacity utilisation of shunting group. In order for this to be feasible, there must be sufficient time to the scheduled departure of each wagon to allow it to be re-shunted. The entry group and barrier must also be able to accommodate the corresponding additional tasks. Figure 3 shows the original flow, the modified flow with an additional temporary train and the resulting reduction in track resource utilisation.
A Tentative Solution
One possible model is to use a multi-commodity flow model as follows. Encode the destination train of each wagon as its commodity and allow incoming wagons to flow either directly to their destination or to a temporary train.
An outgoing train has potential inflows from each incoming train containing wagons destined for it and from all temporary trains. Temporary trains have individual flow conditions for each commodity. For each incoming train and commodity the sum of flows directly to the destination and to the temporary trains must be equal to that transported by the train. For each outgoing train the sum of flows from incoming and temporary trains must equal that transported by the train.
The scheduling constraints are augmented with tasks for each potential temporary train. Departure and duration for such tasks are constrained by the transferred commodities. Flow through temporary trains is restricted by the latest departure, which is in turn constrained by transferred commodities.
The model is implemented as a constraint program enforcing the multi-commodity flow conditions and scheduling constraints. In addition, the solver ensures that at any given time, at most one temporary train can be active.
Preliminary Results
Trial runs have been performed using real case data from a number of actual shunting sites in Sweden. For each such case the expected arrival and departure times were used. A small number of potential temporary trains with large arrival and departure time windows was introduced. The original flows in the case data were relaxed to allow each wagon to either flow directly to its destination or to a temporary train, which in turn has possible flows to each outgoing train.
For one temporary train and eight outgoing trains, correct solutions are computed in the order of seconds and for up to three temporary trains and on the order of forty outgoing trains, correct solutions are computed in the order of minutes.
Figure 4 shows the resulting schedules without and with temporary trains. The upper parts are Gantt diagrams of the arrival group (green), barrier (violet) and shunting group tracks (orange). The lower parts show histograms of the number of shunting-group tracks simultaneously being occupied by trains. In the right part of the figure, temporary trains are represented by blue bars. Note how the histogram is spread out (levelled) in time at the cost of a slightly higher load on the entry group and barrier resources used for re-shunting.
Conclusions
The proposed model is quite tentative and despite the fact that so far it has scaled fairly well, it is not clear that constraint programming is the best approach to solve this type of problem. Local search heuristics or an integer programing model may in the end turn out to be more practical. It has also been pointed out to us that the problem has certain similarities with register allocation problems in compiler design.
Link:
http://www.sics.se/iam/
Please contact:
Martin Aronsson and Per Kreuger
SICS, Sweden
Tel: +46 8 6331500
E-mail: Martin.Aronsson
sics.se or Per.Kreugersics.se
