Simultaneous Assignment of Locomotives and Cars to Passenger Trains
Authors:
- 1 August 2001
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 49 (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
This publication has 8 references indexed in Scilit:
- A Benders Decomposition Approach for the Locomotive and Car Assignment ProblemTransportation Science, 2000
- A Survey of Optimization Models for Train Routing and SchedulingTransportation Science, 1998
- Operational Planning of Passenger Trains in Indian RailwaysInterfaces, 1992
- Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection CriteriaOperations Research, 1981
- A Modified Benders' Partitioning Algorithm for Mixed Integer ProgrammingManagement Science, 1977
- Lagrangean relaxation for integer programming1974
- Partitioning procedures for solving mixed-variables programming problemsNumerische Mathematik, 1962
- Decomposition Principle for Linear ProgramsOperations Research, 1960