Decomposing the Train-Scheduling Problem into Integer-Optimal Polytopes

Masoud Barah (), Abbas Seifi () and James Ostrowski ()
Additional contact information
Masoud Barah: Department of Industrial and Systems Engineering, University of Tennessee, Knoxville, Tennessee 37996
Abbas Seifi: Department of Industrial Engineering and Management Systems, Amirkabir University of Technology, Tehran 15875, Iran
James Ostrowski: Department of Industrial and Systems Engineering, University of Tennessee, Knoxville, Tennessee 37996

Transportation Science, 2019, vol. 53, issue 3, 763-772

Abstract: This paper presents conditions for which the linear relaxation for the train-scheduling problem is integer optimal. These conditions are then used to identify how to partition a general problem’s feasible region into integer-optimal polytopes. Such an approach yields an extended formulation that contains far fewer binary variables. Our computational experiments show that this approach results in significant computational savings. Moreover, this approach scales well when the train-scheduling problem is modeled using smaller time increments, allowing for higher fidelity models to be solved without significantly increasing the required computational time.

Keywords: nonperiodic train-scheduling problem; space–time network; integer-optimal polytopes (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0848 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:3:p:763-772

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().