Robust transshipment problem under consistent flow constraints

Networks, vol. 83, pp. 53–82

Abstract

Abstract In this article, we study robust transshipment under consistent flow constraints. We consider demand uncertainty represented by a finite set of scenarios and characterize a subset of arcs as so‐called fixed arcs. In each scenario, we require an integral flow that satisfies the respective flow balance constraints. In addition, on each fixed arc, we require equal flow for all scenarios. The objective is to minimize the maximum cost occurring among all scenarios. We show that the problem is strongly ‐complete on acyclic digraphs by a reduction from the ‐Sat problem. Furthermore, we prove that the problem is weakly ‐complete on series‐parallel digraphs by a reduction from a special case of the Partition problem. If in addition the number of scenarios is constant, we observe the pseudo‐polynomial‐time solvability of the problem. We provide poly‐nomial‐time algorithms for three special cases on series‐parallel digraphs. Finally, we present a polynomial‐time algorithm for pearl digraphs.

Authors 3

1. Christina Büsing Aachen Combinatorial Optimization

   RWTH Aachen University

   Affiliation as printed

   Combinatorial Optimization RWTH Aachen University Aachen Germany

   Combinatorial Optimization, RWTH Aachen University, Aachen, Germany

2. Arie M. C. A. Koster Aachen Discrete Optimization

   RWTH Aachen University

   Affiliation as printed

   Discrete Optimization RWTH Aachen University Aachen Germany

   Discrete Optimization, RWTH Aachen University, Aachen, Germany

3. Sabrina Schmitz corresponding Aachen Combinatorial Optimization

   RWTH Aachen University

   Affiliation as printed

   Combinatorial Optimization RWTH Aachen University Aachen Germany

   Combinatorial Optimization, RWTH Aachen University, Aachen, Germany