A BENDERS DECOMPOSITION APPROACH FOR THE LOCOMOTIVE AND CAR ASSIGNMENT PROBLEM

One of the many problems faced by railroad transportation companies is optimizing the utilization of the available stock of locomotives and cars. In this paper, the authors describe a decomposition method for the simultaneous assignment of rail 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. An exact algorithm is proposed, 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 in 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.

• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Corporate Authors:

  Institute for Operations Research and the Management Sciences (INFORMS)

  901 Elkridge Landing Road, Suite 400
  Linthicum, MD  United States  21090-2909
• Authors:
  • Cordeau, J-F
  • Soumis, F
  • Desrosiers, J
• Publication Date: 2000-5

Language

• English

Media Info

• Features: Figures; References; Tables;
• Pagination: p. 133-149
• Serial:
  • Transportation Science
  • Volume: 34
  • Issue Number: 2
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Algorithms; Cost estimating; Locomotive utilization; Optimization; Passenger trains; Passenger transportation; Railroad cars; Railroad transportation
• Uncontrolled Terms: Benders decomposition; Minimum cost equipment cycles
• Subject Areas: Finance; Freight Transportation; Passenger Transportation; Railroads; Vehicles and Equipment;

Filing Info

• Accession Number: 00794469
• Record Type: Publication
• Files: TRIS
• Created Date: Jun 6 2000 12:00AM