Circulation of railway rolling stock: a branch-and-price approach
Introduction
The efficient circulation of railway rolling stock is an important problem for operators of passenger trains, since the rolling stock represents a huge capital investment. The rolling stock is also an investment that cannot be changed frequently, because it usually has an economic life cycle of several decades. For these reasons, it has to be decided carefully how many carriages or train units are necessary per scheduled train in order to attain a certain quality level for the passengers.
In this paper we describe a branch-and-price approach for determining efficient circulations of a number of train units on a single line or on a set of interacting lines. Here, a line is defined by two endpoints between which a fixed number of trains run up and down according to the timetable. In order to obtain per trip a better match between the supply of seats and the demand for seats, the compositions of the trains can be changed at some stations by coupling or uncoupling train units. For example, train units may be uncoupled from a train after the morning rush hours, and they may be coupled again before the afternoon rush, possibly onto another train. These shunting operations, which are carried out in the short time interval between the arrival of a train at a station and its subsequent departure, are subject to several practical rules related to the feasibility of the transitions of the train compositions.
The primary objective pursued in the planning process of a rolling stock circulation is the maximization of the service to the passengers by minimizing the expected seat shortages. Given the current timetable and the expected numbers of passengers, some seat shortages may be unavoidable, because of a limitation on the train lengths or because of a limited amount of rolling stock. Other relevant concerns are the robustness and the total cost of the rolling stock circulation.
Note that the railway system in the Netherlands is quite dense. This allows one to take into account maintenance planning and maintenance routing of train units only implicitly in the rolling stock circulations. That is, in addition to the train units that are required for operating the train services, a sufficient number of train units is reserved for maintenance. Maintenance routing is carried out in the operations by exchanging duties of individual train units [1]. Therefore, the maintenance routing problem can be ignored in the rolling stock circulation planning problem.
Although the model described in this paper is also valid for solving operational rolling stock circulation problems, the primary objective of the model is to investigate the effect of changes in some input parameters on the objectives, e.g. the number of train units allocated to a line, an additional station where units can be (un)coupled, a change in the allowable train length on some trips, etc.
Our approach is tested on several real-life instances of NS Reizigers, the main Dutch operator of passenger trains. This operator mainly uses train units to operate its train services. Train units differ from train carriages, because they can move individually in both directions without a locomotive. Fig. 1a presents a double deck train unit with four carriages and Fig. 1b presents a double deck carriage. There exists other train units of this double deck type with a different number of carriages (three carriages or six carriages), subsequently called subtypes. Such a train unit is indivisible and a train can be composed of several of those subtypes of train units. Different types of train units (e.g. double deck versus single deck), however, cannot be combined with each other in one train. It is preferable to assign only one type of train units to a line or to a set of interacting lines, since in case of disruption of the operations (e.g. a switch or electricity breakdown), the circulation will not be completely disorganized, and it will be much easier to return to the regular situation afterwards.
In this paper, we describe a branch-and-price approach for solving the rolling stock circulation problem. During the last decades, many hard integer programming problems have been successfully solved exactly with branch-and-price methods. The first papers on branch and price or Integer Programming column generation are [2], [3] on routing problems. Savelsbergh [4] presents an efficient branch-and-price algorithm for the generalized assignment problem. For a general exposition on branch and price, we refer to Vanderbeck and Wolsey [5], Barnhart et al. [6] and Vanderbeck [7].
The rolling stock circulation problem has similarities with the multicommodity flow problem (MCFP), where the flows of different commodities must be routed through a graph from supply to demand nodes without exceeding the capacities of the arcs (see e.g. [8]). In our problem, the commodities correspond to the rolling stock subtypes, and the graph is determined by the different trips that must be served. The capacity of an arc corresponds to the maximum number of carriages that can be deployed on a trip, because of the lengths of the platforms in the stations along the line.
Column generation approaches and branch-and-price algorithms have been proposed to tackle variants of the MCFP. For example, Barnhart et al. [9] present a branch-and-price-and-cut algorithm to solve an origin–destination integer MCFP. Holmberg and Yuan [10] present a column generation approach for an MCFP with side constraints. Usually, for every commodity, paths through a network are generated, where the master problem contains arc capacity constraints. In our problem, a complicating issue is the fact that we have to take into account the orders of the commodities on the arcs, as will be explained later. Therefore, we generate paths corresponding to joint flows of several commodities that meet capacity constraints as well as certain transition constraints.
The remainder of this paper is organized as follows. Section 2 describes the rolling stock circulation problem in more detail. Section 3 presents the model and an Integer Programming formulation, that is used as a benchmark for our branch-and-price approach. In Section 4, we present a Dantzig–Wolfe reformulation for the problem. Section 5 outlines the branch-and-price procedure. Section 6 discusses the results of our numerical experiments. Finally, we describe some conclusions and subjects for further research in Section 7.
Section snippets
Lines
A line is defined by two endpoints between which a fixed number of trains run up and down according to the timetable. This number of trains is determined by the circulation time of the line, including the return times at the endpoints, and the line's frequency. For example, Fig. 2 presents the railway map of the Netherlands. The bold line presents the intercity 2100 line running between Amsterdam (Asd) and Vlissingen (Vs), the 2400 line between Asd and Dordrecht (Ddr), and the 2600 line between
Transition graph
For each train, the possible changes in its composition at a station can be represented by a so-called transition graph, where the nodes represent the feasible train compositions on a trip and the arcs represent the feasible transitions between compositions at a station. Transition graphs were used also by Alfieri et al. [13]. Each train starts with an artificial trip from the depot at the departure station to the platform and ends with a trip to the depot at the arrival station of its last
Formulation
The rolling stock circulation problem (1)–(8) is suitable to apply Dantzig–Wolfe decomposition [20]. In contrast to multicommodity flow decomposition approaches in the literature (e.g. [9], [10]), where paths through the network are generated for each commodity and the capacity constraints are considered in the master problem, we decompose the problem based on the trains. Each train can be composed of several commodities, i.e. the rolling stock subtypes. In the Dantzig–Wolfe reformulation, we
Branch and price
After solving the LP relaxation, branching is needed to obtain a proven optimal integer solution. Since for each only a subset of the paths from is inserted in the master problem for solving the LP relaxation, and not necessarily all paths required for the optimal integer solution, the column generation procedure must be applied at every node of the branch-and-price tree with an appropriately modified pricing problem. These modifications to the pricing problem reflect the branching
Numerical experiments
In order to test the described procedure, we carried out several computational experiments. The experiments are performed on an IBM NetVista 6343-25G Pentium 4 1.6 GHz PC, using the Windows 98 operating system. Our algorithm is coded in and linked with the Extended LINDO/PC optimization library release 6.1 for solving the LP subproblems.
Conclusions and future research
In this paper, we presented a model to determine an efficient rolling stock circulation for a set of interacting railway lines. We developed a branch-and-price algorithm to solve the problem to proven optimality. The algorithm was tested on real-life instances of NS Reizigers, the main Dutch operator of passenger trains. The required CPU time is short, as follows from a comparison with CPLEX 8.0. Therefore, what–if analyses can be performed easily. The model can be a useful tool for planners to
References (22)
- et al.
An exact algorithm for IP column generation
Operations Research Letters
(1996) - et al.
A rolling stock circulation model for combining and splitting of passenger trains
European Journal of Operational Research
(2006) - et al.
Operational car assignment at VIA rail Canada
Transportation Research B
(2002) - et al.
Maintenance routing for train units: the transition model. Transportation Science
(2005) - et al.
Routing with time windows by column generation
Networks
(1984) - et al.
A column generation approach to the urban transit crew scheduling problem
Transportation Science
(1989) A branch-and-price algorithm for the generalized assignment problem
Operations Research
(1997)- et al.
Branch-and-price: column generation for solving huge integer programs
Operations Research
(1998) On Dantzig–Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm
Operations Research
(2000)- et al.
Network flows: theory, algorithms, and applications
(1993)
Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems
Operations Research
Cited by (105)
Passenger-oriented rolling stock scheduling in the metro system with multiple depots: Network flow based approaches
2024, Transportation Research Part B: MethodologicalNew Exact Algorithm for the integrated train timetabling and rolling stock circulation planning problem with stochastic demand
2024, European Journal of Operational ResearchDemand-driven integrated train timetabling and rolling stock scheduling on urban rail transit line
2024, Transportmetrica A: Transport ScienceDemand-oriented integration optimization of train timetabling and rolling stock circulation planning with flexible train compositions: A column-generation-based approach
2023, European Journal of Operational Research