探討產能設施位址選擇於大規模配銷網路之設計

Capacitated Facility Location with Application to Large-scale Distribution Network Design

張祐誠(Yu-Cheng Chang)

指導教授 ： 廖崇碩

國立清華大學/工學院/工業工程與工程管理學系/碩士(2011年)

https://doi.org/10.6843/NTHU.2011.00164

摘要

隨著中國大陸物流市場的快速成長，如何設計大規模的配銷網路成為其中最重要的研究議題之一；同時，大規模配銷網路的設計也是全球化供應鏈管理的核心問題。配銷網路設計可考慮下列兩個部分：如何選擇製造工廠和配銷中心之地點，以及決定製造工廠和配銷中心之間的最佳連結方式。在本研究中，我們探討在大規模網路中的產能設施區位選擇問題，並且將其應用在配銷網路設計上。在此網路中，每一個配銷中心有其需求，而每一個工廠有其固定的產能以提供給它所服務的配銷中心。我們的目標在選擇一群工廠集合以滿足每一個配銷中心的需求，且不能違背工廠產能上限的條件下，最小化其總成本，其中總成本包含工廠營運成本及服務成本，通常服務成本是根據工廠和配銷中心之間的距離所定義的。而這個問題最大的關鍵挑戰，為其計算複雜度是隨著配銷網路的大小規模而成指數的成長。本研究中，我們參考Kao et al. [18] (2011)之動態規劃計算方法，設計一個初始的配銷網路圖，而為了進一步趨近最佳解，我們提出區域交換的方法，修正初始配銷網路圖配對上的誤差。本研究中，結合動態規畫計算方法和區域交換技巧，可以快速且精確地求出大規模配銷網路的近似最佳解。除此之外，我們還建立一個圖形化使用者介面系統且驗證此系統的實用價值。我們的研究結果顯示此圖形化使用者介面系統可以趨近最佳解僅差一成，且我們的演算法計算時間遠小於最佳化軟體的最佳解計算時間。

關鍵字

配銷網路 ； 區位設施選擇 ； 大規模網路

並列摘要

With the rapid growth of China’s logistics market, one of the most important research issues is designing a large-scale distribution network. The question of large-scale distribution network design is also becoming central to globalization supply chain management. Distribution network design can be considered as two parts: locating manufacturing plants and distribution centers, and determine the best strategy for communications between manufacturing plants and distribution centers. In this article, we study capacitated facility location in large-scale networks and its application to distribution network design. In a distribution network, each distribution center or client has associated with a demand, and each plant or facility has a capacity that specifies the maximum service the plant can provide to its distribution centers. Our aim is to select a subset of plants such that the demand requirement of each distribution center is satisfied, the plants capacities are not violated, and the total cost, including plant operating cost and service cost, which is usually based on the metric distance between plants and distribution centers, is minimized. The key challenge is that the computational complexity grows exponentially in the network size. We refer to the dynamic programming algorithm from Kao et al. [18] (2011) to build a distribution network, and we provide local swap techniques to better approximate the optimal assignment in the distribution network. Based on the dynamic programming algorithm and local swap techniques, we present a fast and accurate approximation approach to the large-scale distribution network design. In addition, we build a graphical user interface (GUI) system and the proposed system demonstrates its practical usefulness. Our GUI system can approximate the optimum within a constant ratio, and the computation time cost of our algorithm is much faster than that of Lingo. Keywords: Distribution network; facility location; large-scale network.

參考文獻

3. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V., 2004, “Local search heuristics for k-median and facility location problems,” SIAM J. Comput., Vol. 33, No. 3, pp. 544-562.

4. Beasley, J. E., 1988, “An algorithm for solving large capacitated warehouse location problems,” European Journal of Operational Research, Vol. 33, pp. 314-325.

5. Campbell, J.F., 1990, “Locating Transportation Terminals to Serve An Expanding Demand,” Transpn. Res.-B, Vol. 24B, No. 3, pp. 173-192.

7. Chardaire, P., Sutter, A., Costa, M.C., 1996, “Solving the Dynamic Facility Location Problem,” Network, Vol. 28, pp. 117-124.

8. Charikar, M., Guha, S., 1999, “Improved combinatorial algorithm for facility location and k-median problems,” In Proceedings of 40th IEEE Symposium of Foundations of Computer Science, pp. 378-388.