Solving Unsplittable Network Flow Problems with Decision Diagrams

Hosseinali Salemi () and Danial Davarnia ()
Additional contact information
Hosseinali Salemi: Department of Industrial and Manufacturing Systems Engineering, Iowa State University, Ames, Iowa 50011
Danial Davarnia: Department of Industrial and Manufacturing Systems Engineering, Iowa State University, Ames, Iowa 50011

Transportation Science, 2023, vol. 57, issue 4, 937-953

Abstract: In unsplittable network flow problems, certain nodes must satisfy a combinatorial requirement that the incoming arc flows cannot be split or merged when routed through outgoing arcs. This so-called no-split no-merge requirement arises in unit train scheduling where train consists should remain intact at stations that lack necessary equipment and manpower to attach/detach them. Solving the unsplittable network flow problems with standard mixed-integer programming formulations is computationally difficult due to the large number of binary variables needed to determine matching pairs between incoming and outgoing arcs of nodes with no-split no-merge constraint. In this paper, we study a stochastic variant of the unit train scheduling problem where the demand is uncertain. We develop a novel decision diagram (DD)-based framework that decomposes the underlying two-stage formulation into a master problem that contains the combinatorial requirements and a subproblem that models a continuous network flow problem. The master problem is modeled by a DD in a transformed space of variables with a smaller dimension, leading to a substantial improvement in solution time. Similar to the Benders decomposition technique, the subproblems output cutting planes that are used to refine the master DD. Computational experiments show a significant improvement in solution time of the DD framework compared with that of standard methods.

Keywords: decision diagrams; network optimization; mixed integer programs; unit trains; transportation (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1194 (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:57:y:2023:i:4:p:937-953

Access Statistics for this article

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