Simultaneous assignment of locomotives and cars to passenger trains
成果类型：
Article
署名作者：
Cordeau, JF; Soumis, F; Desrosiers, J
署名单位：
Universite de Montreal; HEC Montreal; Universite de Montreal; Universite de Montreal; Polytechnique Montreal
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.49.4.531.11226
发表日期：
2001
页码：
531-548
关键词：
摘要：
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.