Each year the Railway Applications Section (RAS) of the Institution for Operations Research and the Management Sciences (INFORMS) posits a research problem to the world in the form of a competition. For 2012, the contest involved solving the Train Dispatching Problem (TDP) on a realistic 85 edge network for three different sets of input data. This work is an independent attempt to match or improve upon the results of the top three finishers in the contest using mixed integer programming (MIP) techniques while minimizing the use of heuristics. The primary focus is to partition the network in a manner that reduces the number of binary variables in the formulation as much as possible without compromising the ability to satisfy any of the contest requirements. This resulted in the ability to optimally solve this model for RAS Data Set 1 in 29 seconds without any problem-specific heuristics, variable restrictions, or variable fixing. Applying some assumptions about train movements allowed the same Data Set 1 solution to be found in 5.4 seconds. After breaking the larger Data Sets 2 and 3 into smaller sub-problems, solutions for Data Sets 2 and 3 were 28% and 1% better, respectively, than those of the competition winner. The time to obtain solutions for Data Sets 2 and 3 was 90 and 318 seconds, respectively.
| Identifer | oai:union.ndltd.org:vcu.edu/oai:scholarscompass.vcu.edu:etd-4284 |
| Date | 19 June 2013 |
| Creators | Snellings, Christopher |
| Publisher | VCU Scholars Compass |
| Source Sets | Virginia Commonwealth University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Theses and Dissertations |
| Rights | © The Author |
Page generated in 0.0018 seconds