Abstract
Modern supply chain networks operate under pervasive uncertainties, including demand fluctuations, stochastic lead times, and structural disruption risks. In this paper, we propose a comprehensive graph-theoretic framework for multi-echelon supply chain optimization subject to parameterized uncertainty sets. By representing the logistics infrastructure as a weighted, capacitated directed multigraph, we formulate the network design and flow allocation problem as a robust combinatorial optimization model under polyhedral and cardinality-constrained uncertainty sets. To overcome the computational intractability inherent in min-max-min robust formulations, we develop a dual-decomposition branch-and-cut algorithm accelerated by graph-theoretic cutting planes and lazy constraint generation. Computational experiments conducted on both synthetic benchmark topologies and real-world supply chain testbeds demonstrate that our proposed approach achieves a near-optimal balance between cost efficiency and systemic resilience. Specifically, the framework reduces expected worst-case disruption costs by up to 34.8% compared to deterministic baselines while requiring only a marginal 4.2% increase in nominal operational expenditures. Furthermore, the algorithmic enhancements exhibit polynomial scaling on large-scale instances with up to 10,000 nodes, confirming the viability of the proposed method for operational decision-making in large-scale logistics networks.
