A Benders Decomposition Approach for the Locomotive and Car Assignment Problem

Cordeau, Jean-François; Soumis, François; Desrosiers, Jacques
May 2000
Transportation Science;May2000, Vol. 34 Issue 2, p133
Academic Journal
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.


Related Articles

  • Max algebra and the linear assignment problem. Burkard, Rainer E.; Butkovic, Peter // Mathematical Programming;Sep2003, Vol. 98 Issue 1-3, p415 

    Analyzes the max algebra and the linear assignment problem. Basic notions of max-algebra; Linear equation system in max-algebra; Information on the minimal-dimensional realization of discrete event dynamical systems.

  • A PRIMAL-DUAL TRAFFIC ASSIGNMENT ALGORITHM. Petersen, E. R. // Management Science;Sep75, Vol. 22 Issue 1, p87 

    A new algorithm for solving the traffic assignment problem is presented. This is a primal-dual algorithm which utilizes a flow augmentation primal and a shortest path dual procedure. At each iteration a feasible solution is known together with a measure of "goodness" of the solution. It is shown...

  • TWO FALSE ENDINGS TO THE MODIFIED ASSIGNMENT PROBLEM: A SOLUTION. Hesse, Rick // Interfaces;Aug82, Vol. 12 Issue 4, p69 

    The author discusses responses to his work on the modified assignment problem, particular Bharath and Dieter Klein's comments on Stern's modification of the assignment algorithm to solve the transportation problem. The author claims that the condition described is necessary but not sufficient...

  • A Full Analytical Implementation of the PARTAN/ Frank-Wolfe Algorithm for Equilibrium Assignment. Arezki, Y.; Van Vliet, D. // Transportation Science;Feb90, Vol. 24 Issue 1, p58 

    We show that an essential step in the PARTAN variant of the Frank—Wolfe algorithm for equilibrium assignment, the calculation of a minimal step length for maintaining feasibility, can be accomplished using either analytical formulas or simple rules.


    An algorithm for the transportation problem by Hesse and Woolsey is presented. It is a way of modifying the Hungarian method for assignment problems so as to apply it to transportation problems in general. The method consists in reducing the costs matrix by row and column reductions so as to...

  • Signature Methods for the Assignment Problem. Balinski, M. L. // Operations Research;May/Jun85, Vol. 33 Issue 3, p527 

    The "signature" of a dual feasible basis of the assignment problem is an n-vector whose ith component is the number of nonbasic activities of type (I, j). This paper uses signatures to describe a method for finding optimal assignments that terminates in at most (n - 1)(n - 2)/2 pivot steps and...

  • An Algorithm for the Maximal Multicommodity Funnel-Node Flow in an Undirected Network. Martins, Ernesto Q. V.; Rosa, Mario S. // Operations Research;May/Jun85, Vol. 33 Issue 3, p537 

    We consider the maximal multicommodity funnel-node flow problem. That is, K commodities of flow must be simultaneously defined in an undirected network so that the flow of all the commodities passes through a specified node (the funnel-node) and is maximal. For this particular problem of...

  • AN ALGORITHM FOR THE THREE-INDEX ASSIGNMENT. Balas, Egon; Saltzman, Matthew J. // Operations Research;Jan/Feb91, Vol. 39 Issue 1, p150 

    We describe a branch-and-bound algorithm for solving the axial three-index assignment problem. The main features of the algorithm include a Lagrangian relaxation that incorporates a class of facet inequalities and is solved by a modified subgradient procedure to find good lower bounds, a primal...

  • THE AUCTION ALGORITHM FOR THE TRANSPORTATION PROBLEM. Bertsekas, Dimitri P.; Castanon, David A. // Annals of Operations Research;1989, Vol. 20 Issue 1-4, p67 

    The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids arc in, objects are awarded to the highest bidder....


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics