The Locomotive Routing Problem

Vaidyanathan, Balachandran; Ahuja, Ravindra K.; Orlin, James B.
November 2008
Transportation Science;Nov2008, Vol. 42 Issue 4, p492
Academic Journal
Given a schedule of trains, the locomotive planning (or scheduling) problem (LPP) is to determine the minimum cost assignment of locomotive types to trains that satisfies a number of business and operational constraints. Once this is done, the railroad has to determine the sequence of trains to which each locomotive is assigned by unit number so that it can be fueled and serviced as necessary. We refer to this problem as the locomotive routing problem (LRP). The LRP is a very large scale combinatorial optimization problem, and the general version that we consider has previously been unstudied and unsolved in the research literature. In this paper, we develop robust optimization methods to solve the LRP. There are two major sets of constraints that need to be satisfied by each locomotive route: (1) locomotive fueling constraints, which require that every unit visit a fueling station at least once for every F miles of travel, and (2) locomotive servicing constraints, which require that every unit visit a service station at least once for every S miles of travel. The output of the LPP is not directly implementable because the LPP does not consider these fueling and servicing constraints. The LRP considers these constraints, and its output is therefore implementable. We model the LRP by considering alternative fueling and servicing friendly train paths (or strings) between servicing stations on the network. We formulate the LRP as an integer programming problem on a suitably constructed space-time network and show that this problem is NP-Complete. This integer programming problem has millions of decision variables. We develop a fast aggregation-disaggregation based algorithm to solve the problem within a few minutes of computational time to near optimality. Finally, we present computational results and extensive case studies of our algorithms on real data provided by a major Class I U.S. railroad


Related Articles

  • Development of a multiobjective GA for advanced planning and scheduling problem. Dayou, Liu; Pu, Yan; Ji, Yu // International Journal of Advanced Manufacturing Technology;Oct2009, Vol. 42 Issue 9/10, p974 

    In this paper, we consider an advanced planning and scheduling (APS) problem in manufacturing supply chain. The problem was formulated with mixed integer programming and three objectives are taken into account. To solve the APS model, a multiobjective genetic algorithm with local search is...

  • 50017 gears up for first work.  // Railways Illustrated;May2010, Vol. 8 Issue 5, p36 

    The article reports on the on the full length run of the 50017 Royal Oak locomotive on the Plum Valley Railway on February 6, 2010 as part of its restoration.

  • Voyager on the move.  // Railways Illustrated;May2014, Vol. 12 Issue 5, p19 

    A photograph showing the locomotive County of Staffordshire heading the driving cars from the disbanded train on March 9, 2014 is presented.

  • More DRS Class 37s returned to traffic. Furness, Ian // Railways Illustrated;Jan2012, Vol. 10 Issue 1, p27 

    The article reports that the Class 37 locomotives, 37261 and 37612, are now back in traffic in Great Britain after undergoing repairs at RVEL Derby.

  • Class 600s assist metro maintenance.  // Railways Illustrated;Nov2014, Vol. 12 Issue 11, p23 

    The article reports on the track renewal programme on line D of the Rotterdam tube system in the Netherlands in summer 2014 which involved three former NS Class 600 locomotives.

  • Shifting heavy electric locomotives in shop areas. H., J. D. // Model Railroader;Jun2011, Vol. 78 Issue 6, p18 

    The article discusses how electric locomotives receive power inside a repair shop during their servicing. It is stated that when electric locomotives are being moved around in repair shops, they are normally not under power. It is mentioned that before any mechanics could begin working on a...

  • COMBINATORIAL AND INTEGER OPTIMIZATION. Hoffman, Karla L.; Padberg, Manfred // Encyclopedia of Operations Research & Management Science;2001, p94 

    The article discusses combinatorial and integer optimization. Combinatorial optimization is the process of finding one or more best solutions in a well-defined discrete problem space. The various models of combinatorial optimization can be used to solve knapsack problems, network and graph...

  • Transformation of Course Timetablinng Problem to RCPSP. Ahmad, M.; Gourgand, M.; Caux, C. // World Academy of Science, Engineering & Technology;2012, Issue 68, p2192 

    The Resource-Constrained Project Scheduling Problem (RCPSP) is concerned with single-item or small batch production where limited resources have to be allocated to dependent activities over time. Over the past few decades, a lot of work has been made with the use of optimal solution procedures...

  • A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows. Dash, Sanjeeb; Günlük, Oktay; Lodi, Andrea; Tramontani, Andrea // INFORMS Journal on Computing;Winter2012, Vol. 24 Issue 1, p132 

    The traveling salesman problem with time windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a given time window. We present an extended formulation for the problem based on partitioning the time windows into...


Read the Article


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

Try another library?
Sign out of this library

Other Topics