A Benders Decomposition Approach for the Locomotive and Car Assignment Problem

Jean-François Cordeau, François Soumis and Jacques Desrosiers
Additional contact information
Jean-François Cordeau: GERAD and École des Hautes Études Commerciales, 3000 chemin de la Côte-Sainte-Catherine, Montréal H3T 2A7, Canada
François Soumis: GERAD and École Polytechnique de Montréal, C.P. 6079, Succ. Centre-Ville, Montréal H3C 3A7, Canada
Jacques Desrosiers: GERAD and École des Hautes Études Commerciales, 3000 chemin de la Côte-Sainte-Catherine, Montréal H3T 2A7, Canada

Transportation Science, 2000, vol. 34, issue 2, 133-149

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

Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (56)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.34.2.133.12308 (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:ortrsc:v:34:y:2000:i:2:p:133-149

Access Statistics for this article

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