A Benders decomposition approach for the locomotive and car assignment problem

A Benders decomposition approach for the locomotive and car assignment problem

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: assignment
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 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.

Reviews

Required fields are marked *. Your email address will not be published.