Network models with unsplittable node flows with application to unit train scheduling

Danial Davarnia, Jean Philippe P. Richard, Ece Içyüz-Ay, Bijan Taslimi

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We study network models where flows cannot be split or merged when passing through certain nodes (i.e., for such nodes, each incoming arc flow must be matched to an outgoing arc flow of identical value). This requirement, which we call no-split no-merge (NSNM), appears in railroad applications in which train compositions can only be modified at yards where necessary equipment is available. This combinatorial requirement is crucial when formulating problems occurring in the unit train business. We propose modeling approaches to represent the NSNM requirement. In particular, we give a linear formulation of the requirement on a single node that describes the convex hull in a lifted space. We present a cut-generating linear program to obtain valid inequalities in the original space of variables and introduce a polynomial-time procedure to lift strong inequalities of lower-dimensional models into strong inequalities of the original model. In addition, we identify an exponential family of facet-defining inequalities that can be separated efficiently. To evaluate our results computationally, we study a stylized unit train problem. We compare a solution approach based on our results with one that relies on column generation.We then show that our results significantly reduce relaxation times and gaps when compared with leading commercial branch-and-cut software.

Original languageEnglish (US)
Pages (from-to)1053-1068
Number of pages16
JournalOperations research
Volume67
Issue number4
DOIs
StatePublished - 2019

Bibliographical note

Funding Information:
Funding: This work was supported by the National Science Foundation, Division of Civil, Mechanical, and Manufacturing Innovation [Grant 1200616]. Supplemental Material: The electronic companion is available at https://doi.org/10.1287/opre.2019.1864.

Publisher Copyright:
© 2019 INFORMS.

Keywords

  • Cutting planes
  • Mixed integer programs
  • Network optimization
  • Unit trains

Fingerprint

Dive into the research topics of 'Network models with unsplittable node flows with application to unit train scheduling'. Together they form a unique fingerprint.

Cite this