Circulation of railway rolling stock: a branch-and-price approach

https://doi.org/10.1016/j.cor.2006.03.019Get rights and content

Abstract

In this paper, we describe a model and a branch-and-price algorithm to determine an efficient railway rolling stock circulation on a set of interacting train lines. Given the timetable and the passengers’ seat demand, the model determines an allocation of rolling stock to the daily trips. In order to efficiently utilize the train units, they can be added to or removed from the trains at some stations along the lines. These changes in train compositions are subject to several constraints, mainly corresponding to the order of the train units within the trains. A solution is evaluated based on three criteria, i.e. (i) the service to the passengers, (ii) the robustness, and (iii) the cost of the circulation. The developed branch-and-price algorithm was tested on a number of real-life instances of NS Reizigers, the main Dutch operator of passenger trains, thereby outperforming the commercial solver CPLEX 8.0.

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 iR only a subset of the paths from Ωi 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 C++ 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)

  • F. Vanderbeck et al.

    An exact algorithm for IP column generation

    Operations Research Letters

    (1996)
  • P.-J. Fioole et al.

    A rolling stock circulation model for combining and splitting of passenger trains

    European Journal of Operational Research

    (2006)
  • N. Lingaya et al.

    Operational car assignment at VIA rail Canada

    Transportation Research B

    (2002)
  • G. Maróti et al.

    Maintenance routing for train units: the transition model. Transportation Science

    (2005)
  • J. Desrosiers et al.

    Routing with time windows by column generation

    Networks

    (1984)
  • J. Desrosiers et al.

    A column generation approach to the urban transit crew scheduling problem

    Transportation Science

    (1989)
  • M. Savelsbergh

    A branch-and-price algorithm for the generalized assignment problem

    Operations Research

    (1997)
  • C. Barnhart et al.

    Branch-and-price: column generation for solving huge integer programs

    Operations Research

    (1998)
  • F. Vanderbeck

    On Dantzig–Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm

    Operations Research

    (2000)
  • R.K. Ahuja et al.

    Network flows: theory, algorithms, and applications

    (1993)
  • C. Barnhart et al.

    Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems

    Operations Research

    (2000)
  • Cited by (105)

    View all citing articles on Scopus
    View full text