DOI
https://doi.org/10.25772/SYTB-M126
Defense Date
2013
Document Type
Thesis
Degree Name
Master of Science
Department
Mathematical Sciences
First Advisor
Paul Brooks
Abstract
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.
Rights
© The Author
Is Part Of
VCU University Archives
Is Part Of
VCU Theses and Dissertations
Date of Submission
December 2013