  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. Similarly 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.
