A combinatorial approximation algorithm for supply chain network flow problem

摘要

In this paper we develop a new combinatorial approximation algorithm for a supply chain network containing the manufacturers, retailers and consumers. Given any positive ε, an ε-optimal supply chain network flow problem is to find a product flow whose congestion value is no more than (1 + ε) times the minimum congestion by shipping products from manufacturers to retailers and from retailers to consumers. We propose a new combinatorial approximation algorithm with the application of simplicial decomposition to find the optimal proportions for current product flow and the minimum-cost flows while a tighter computation bound is achieved in decreasing the values of congestion and the potential function. Numerical computations for variants of the combinatorial approximation algorithm are conducted on three-tiered supply chain networks where significant savings in computations are gained from the proposed algorithm.