Back to search

Virginia Commonwealth University

Effective Network Partitioning to Find MIP Solutions to the Train Dispatching Problem

Abstract

dc:description.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.

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 × 2

Rights

dc:rights
Statement dc:rights
  • © The Author

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Virginia Commonwealth University
Base URL
scholarscompass.vcu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Snellings, Christopher. Effective Network Partitioning to Find MIP Solutions to the Train Dispatching Problem. Thesis thesis, https://doi.org/10.25772/SYTB-M126