Virginia Commonwealth University
Effective Network Partitioning to Find MIP Solutions to the Train Dispatching Problem
Abstract
dc:description.abstractEach 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Mathematical Sciences
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Snellings, Christopher
- Contributors dc:contributor
-
- Paul Brooks
Subjects
dc:subject × 2Rights
dc:rights- Statement dc:rights
-
- © The Author
Identifiers
dc:identifier.*- Identifier
- https://scholarscompass.vcu.edu/etd/3285