This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Cordeau, J.-F. Articles by Desrosiers, J. Search for Related Content

Simultaneous Assignment of Locomotives and Cars to Passenger Trains

École des Hautes Études Commerciales and GERAD, Montréal, Canada
École Polytechnique de Montréal and GERAD, Montréal, Canada
École des Hautes Études Commerciales and GERAD, Montréal, Canada
Cordeau{at}crt.umontreal.ca
soumis{at}crt.umontreal.ca
jacques{at}crt.umontreal.ca

The problem of assigning locomotives and cars to trains is a complex task for most railways. In this paper, we propose a multicommodity network flow-based model for assigning locomotives and cars to trains in the context of passenger transportation. The model has a convenient structure that facilitates the introduction of maintenance constraints, car switching penalties, and substitution possibilities. The large integer programming formulation is solved by a branch-and-bound method that relaxes some of the integrality constraints. At each node of the tree, a mixed-integer problem is solved by a Benders decomposition approach in which the LP relaxations of multicommodity network flow problems are optimized either by the simplex algorithm or by Dantzig-Wolfe decomposition. Some computational refinements, such as the generation of Pareto-optimal cuts, are proposed to improve the performance of the algorithm. Computational experiments performed on two sets of data from a railroad show that the approach can be used to produce optimal solutions to complex problems.

Subject classifications: Transportation, scheduling, vehicles: assignment of locomotives and cars; Transportation, models, network: rail; Programming, integer, algorithm, Benders decomposition: application.
History: Received January 1999; revision received February 2000; accepted March 2000.

This article has been cited by other articles:

				R. S. de Camargo, G. de Miranda Jr., and H. P. L. Luna Benders Decomposition for Hub Location Problems with Economies of Scale Transportation Science, February 1, 2009; 43(1): 86 - 97. [Abstract] [PDF]

				R. Agarwal and O. Ergun Ship Scheduling and Network Design for Cargo Routing in Liner Shipping Transportation Science, May 1, 2008; 42(2): 175 - 196. [Abstract] [PDF]

				A. Mercier A Theoretical Comparison of Feasibility Cuts for the Integrated Aircraft-Routing and Crew-Pairing Problem Transportation Science, February 1, 2008; 42(1): 87 - 104. [Abstract] [PDF]

				A. Alfieri, R. Groot, L. Kroon, and A. Schrijver Efficient Circulation of Railway Rolling Stock Transportation Science, August 1, 2006; 40(3): 378 - 391. [Abstract] [PDF]

				R. Hicks, R. Madrid, C. Milligan, R. Pruneau, M. Kanaley, Y. Dumas, B. Lacroix, J. Desrosiers, and F. Soumis Bombardier Flexjet Significantly Improves Its Fractional Aircraft Ownership Operations Interfaces, January 1, 2005; 35(1): 49 - 60. [Abstract] [PDF]

				E. Abbink, B. van den Berg, L. Kroon, and M. Salomon Allocation of Railway Rolling Stock for Passenger Trains Transportation Science, February 1, 2004; 38(1): 33 - 41. [Abstract] [PDF]

				J.-F. Cordeau, G. Stojkovic, F. Soumis, and J. Desrosiers Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling Transportation Science, November 1, 2001; 35(4): 375 - 388. [Abstract] [PDF]