SOLVING REAL-LIFE LOCOMOTIVE SCHEDULING PROBLEMS
The locomotive scheduling problem (or the locomotive assignment problem) is to assign a consist (a set of locomotives) to each train in a pre-planned train schedule so as to provide them sufficient power to pull them from their origins to their destinations. Locomotive scheduling problems are amon...
| Main Authors: | , , , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
2003
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/1799 |
| _version_ | 1826212619972771840 |
|---|---|
| author | Ahuja, Ravindra Liu, Jian Orlin, James Sharma, Dushyant Shughart, Larry |
| author_facet | Ahuja, Ravindra Liu, Jian Orlin, James Sharma, Dushyant Shughart, Larry |
| author_sort | Ahuja, Ravindra |
| collection | MIT |
| description | The locomotive scheduling problem (or the locomotive assignment problem) is to assign a consist
(a set of locomotives) to each train in a pre-planned train schedule so as to provide them sufficient power
to pull them from their origins to their destinations. Locomotive scheduling problems are among the most
important problems in railroad scheduling. In this paper, we report the results of a study of the locomotive
scheduling problem faced by CSX Transportation, a major US railroad company. We consider the
planning version of the locomotive scheduling model (LSM), where there are multiple types of
locomotives and we need to decide the set of locomotives to be assigned to each train. We present an
integrated model that determines the set of active and deadheaded locomotives for each train, light
traveling locomotives from power sources to power sinks, and train-to-train connections (specifying
which inbound train and outbound trains can directly connect). An important feature of our model is that
we explicitly consider consist-bustings and consistency. A consist is said to be busted when the set of
locomotives coming on an inbound train is broken into subsets to be reassigned to two or more outbound
trains. A solution is said to be consistent over a week with respect to a train, if the train gets the same
locomotive assignment each day it runs. We give a mixed integer programming (MIP) formulation of the
problem that contains about 197 thousand integer variables and 67 thousand constraints. An MIP of this
size cannot be solved to optimality or near-optimality in acceptable running times using commercially
available software. Using problem decomposition, integer programming, and very large-scale
neighborhood search, we developed a solution technique to solve this problem within 30 minutes of
computation time on a Pentium III computer. When we compared our solution with the solution obtained
by the software in-house developed by CSX, we obtained a savings of over 400 locomotives, which
translates into savings of over one hundred million dollars annuall |
| first_indexed | 2024-09-23T15:28:56Z |
| format | Working Paper |
| id | mit-1721.1/1799 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:28:56Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | mit-1721.1/17992019-04-11T03:51:41Z SOLVING REAL-LIFE LOCOMOTIVE SCHEDULING PROBLEMS Ahuja, Ravindra Liu, Jian Orlin, James Sharma, Dushyant Shughart, Larry locomotive scheduling problem CSX transportation locomotive scheduling model (LSM) The locomotive scheduling problem (or the locomotive assignment problem) is to assign a consist (a set of locomotives) to each train in a pre-planned train schedule so as to provide them sufficient power to pull them from their origins to their destinations. Locomotive scheduling problems are among the most important problems in railroad scheduling. In this paper, we report the results of a study of the locomotive scheduling problem faced by CSX Transportation, a major US railroad company. We consider the planning version of the locomotive scheduling model (LSM), where there are multiple types of locomotives and we need to decide the set of locomotives to be assigned to each train. We present an integrated model that determines the set of active and deadheaded locomotives for each train, light traveling locomotives from power sources to power sinks, and train-to-train connections (specifying which inbound train and outbound trains can directly connect). An important feature of our model is that we explicitly consider consist-bustings and consistency. A consist is said to be busted when the set of locomotives coming on an inbound train is broken into subsets to be reassigned to two or more outbound trains. A solution is said to be consistent over a week with respect to a train, if the train gets the same locomotive assignment each day it runs. We give a mixed integer programming (MIP) formulation of the problem that contains about 197 thousand integer variables and 67 thousand constraints. An MIP of this size cannot be solved to optimality or near-optimality in acceptable running times using commercially available software. Using problem decomposition, integer programming, and very large-scale neighborhood search, we developed a solution technique to solve this problem within 30 minutes of computation time on a Pentium III computer. When we compared our solution with the solution obtained by the software in-house developed by CSX, we obtained a savings of over 400 locomotives, which translates into savings of over one hundred million dollars annuall 2003-01-27T17:49:33Z 2003-01-27T17:49:33Z 2003-01-27T17:49:33Z Working Paper http://hdl.handle.net/1721.1/1799 en_US MIT Sloan School of Management Working Paper;4389-02 383049 bytes application/pdf application/pdf |
| spellingShingle | locomotive scheduling problem CSX transportation locomotive scheduling model (LSM) Ahuja, Ravindra Liu, Jian Orlin, James Sharma, Dushyant Shughart, Larry SOLVING REAL-LIFE LOCOMOTIVE SCHEDULING PROBLEMS |
| title | SOLVING REAL-LIFE LOCOMOTIVE SCHEDULING PROBLEMS |
| title_full | SOLVING REAL-LIFE LOCOMOTIVE SCHEDULING PROBLEMS |
| title_fullStr | SOLVING REAL-LIFE LOCOMOTIVE SCHEDULING PROBLEMS |
| title_full_unstemmed | SOLVING REAL-LIFE LOCOMOTIVE SCHEDULING PROBLEMS |
| title_short | SOLVING REAL-LIFE LOCOMOTIVE SCHEDULING PROBLEMS |
| title_sort | solving real life locomotive scheduling problems |
| topic | locomotive scheduling problem CSX transportation locomotive scheduling model (LSM) |
| url | http://hdl.handle.net/1721.1/1799 |
| work_keys_str_mv | AT ahujaravindra solvingreallifelocomotiveschedulingproblems AT liujian solvingreallifelocomotiveschedulingproblems AT orlinjames solvingreallifelocomotiveschedulingproblems AT sharmadushyant solvingreallifelocomotiveschedulingproblems AT shughartlarry solvingreallifelocomotiveschedulingproblems |