Article ID: | iaor2002318 |
Country: | United States |
Volume: | 34 |
Issue: | 2 |
Start Page Number: | 133 |
End Page Number: | 149 |
Publication Date: | May 2000 |
Journal: | Transportation Science |
Authors: | Soumis F., Cordeau Jean-Francois, Desrosiers J. |
Keywords: | programming: assignment |
One of the many problems faced by rail transportation companies is to optimize the utilization of the available stock of locomotives and cars. In this paper, we describe a decomposition method for the simultaneous assignment of locomotives and cars in the context of passenger transportation. Given a list of train legs and a fleet composed of several types of equipment, the problem is to determine a set of minimum cost equipment cycles such that every leg is covered using appropriate equipment. Linking constraints, which appear when both locomotives and cars are treated simultaneously, lead to a large integer programming formulation. We propose an exact algorithm, based on the Benders decomposition approach, that exploits the separability of the problem. Computational experiments carried out on a number of real-life instances indicate that the method finds optimal solutions within short computing times. It also outperforms other approaches based on Lagrangian relaxation or Dantzig–Wolfe decomposition, as well as a simplex-based branch-and-bound method.