Simultaneous Assignment of Locomotives and Cars to Passenger Trains

Jean-François Cordeau (), François Soumis () and Jacques Desrosiers ()
Additional contact information
Jean-François Cordeau: École des Hautes Études Commerciales and GERAD, Montréal, Canada
François Soumis: École Polytechnique de Montréal and GERAD, Montréal, Canada
Jacques Desrosiers: École des Hautes Études Commerciales and GERAD, Montréal, Canada

Operations Research, 2001, vol. 49, issue 4, 531-548

Abstract: 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.

Keywords: Transportation; scheduling; vehicles: assignment of locomotives and cars; Transportation; models; network: rail; Programming; integer; algorithm; Benders decomposition: application (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (48)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.4.531.11226 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:49:y:2001:i:4:p:531-548

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().