|
Real-Life Locomotive Planning: New Formulations, Algorithms and Computational Results B. Vaidyanathan, R.K. Ahuja, J. Liu, and L. Shughart, Transportation Research B, 147-168. 2008 In this paper, we develop new formulations for the locomotive planning problem (LPP) which is one of the most important railroad optimization problems. The objective of the LPP is to assign a consist (a set of locomotives) to each train in a pre-planned train schedule so as to provide sufficient locomotive power to pull the trains from their origins to their respective destinations at minimal cost. This assignment plan should be repeated every week. In an earlier paper, we developed a new formulation for locomotive planning and proposed a novel two-phase approach using linear, integer, and network programming. That formulation determines the set of active and deadheading locomotives for each train, light traveling locomotives from power sources to power sinks, and specifies which inbound train and outbound trains can directly connect without excessive switching of the locomotives, referred to as consist busting. Controlling consist busting in an important aspect of that formulation. However, that formulation did not incorporate all the real-world constraints needed to generate a fully implementable solution. In this paper, we extend that approach on several dimensions by adding new constraints to the planning problem desired by locomotive directors, and by developing additional formulations necessary to transition solutions of our models to practice. The new constraints include (i) reducing consist busting to almost zero; (ii) accounting for locomotives visiting shops after breakdowns and returning to active duty after repairs; (iii) locomotives leaving a railroad’s network to enter a connecting railroad’s network, and returning at possibly other locations. We propose two formulations for this generalized locomotive planning problem: consist formulation, and hybrid formulation. We also describe a ways of incrementally transitioning from an old plan to the new plan suggested by this model which we term as incremental planning. Finally, we report computational tests of these models on the data provided to us by a major US railroad and we comment on some insightful results. |