A combinatorial approximation algorithm for supply chain network flow-problem

作者：Chiou Suh Wen^*

来源：Applied Mathematics and Computation, 2007, 186(2): 1526-1536.

DOI：10.1016/j.amc.2006.07.144

• supply chain network flow
• combinatorial approximation algorithm
• simplicial decomposition
• the minimum-cost flow

In this paper we develop a new combinatorial approximation algorithm for a supply chain network containing the manufacturers, retailers and consumers. Given any positive epsilon, an epsilon-optimal supply chain network flow problem is to find a product flow whose congestion value is no more than (1 + epsilon.) 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.

• 出版日期2007-3-15
• 单位东华大学