應用柔性演算法於一次性配送有限產能廠址選擇問題之研究

Integrated use of soft computing and clustering for capacitated clustering single-facility location problem with one-time delivery

劉修豪(Liu, Hsiu Hao)

指導教授 ： 葉維彰

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

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

摘要

在現實生活中，廠址選擇是一個在任何產業界皆非常重要而且常見的議題，這一類的問題在學術上稱為有限產能的分群廠址選擇問題（Capacitated Clustering Location Problem, CCP）。CCP主要是在一群已知的顧客點中，找尋已知所需數量之配銷中心 (Distribution center, DC)的最佳位置。廠址選擇需要考量的成本包含許多，但在過去研究中，最主要考量的目標為最小化從每個DC到每個所屬的顧客點的距離之加總，使得整體運送成本能降到最低。如此挑選DC的準則在於，每當顧客有需求時可以保證從DC到顧客點的運送距離為最小，實際的應用如：消防局、醫院等的設置，符合此種配送貨物或是提供服務的運送方式在本研究中我們稱之為「分批配送」，但並非所有產業或是公司之配送方式都如上述，某些行業必須在固定的時間一次出貨給所有的顧客才返回DC，實際的應用包含：超商生鮮商品的補給車、送報員、郵差等，此種首次被提出應用於廠址選擇問題的配送方式模型，在本研究中稱為「一次性配送」。在此概念下的場址選擇問題目標則為最小化從DC出發後，走完每個顧客點再回到DC的距離加總，一次性配送的運送方式將可以視為旅行銷售員問題做處理以求出最短迴路。
由於CCP是個NP-hard問題，本研究將提出一個混合式的分群演算法：簡化群體演算法結合調和平均數分群法 (SSOKHM)，在需求限制下來挑選特定數量DC的最佳位置，並在分群後，使用貪婪演算法來獲得每群之最短迴路以最小化整體之運送成本。這也是簡化群體演算法首次使用於廠址選擇問題上。
透過實驗結果與其他三種混合式分群法做驗證，顯示無論在分群的結果及整體運送成本上，SSOKHM演算法都具有相當穩定且優異的成效。且同時本研究在貪婪法後加入了一個檢查機制：交換局部搜尋(Exchange local search)，此機制可以透過移動顧客點所屬的分群，使廠址選擇更加精確藉此來節省公司之運送成本。
關鍵詞：分群場址選擇、簡化群體演算法、調和平均數分群、旅行銷售員問題

關鍵字

分群場址選擇 ； 簡化群體演算法 ； 調和平均數分群 ； 旅行銷售員問題

並列摘要

How to set up the distribution centers not only a very general and important issue but also a quite profound knowledge for many different industries in real life. This kind of problem called capacitated clustering location problem (CCP), then the previous literature, the target of the location problem is to minimize the sum of distances from each cluster centers to all customers in their cluster and the practical application of this type, for example: logistics centers, police stations, etc., this approach of shipping called “batch delivery”.
However, some types of business or the company shipping methods are different from the above. The distribution centers must ship goods to all customers in its cluster or cluster in a cycle time, such as postman, newsman, etc., this approach of shipping is called “one-time delivery”. One-time delivery can be modeled as a Travelling Salesman Problem (TSP). This type of problem is rarely discussed in the former literature.
In order to solve this practical problem, a new hybrid clustering algorithm, Simplified Swarm Optimization combining with K-harmonic means (SSOKHM) is proposed in this paper for the CCP with one-time delivery and using greedy algorithm for the TSP to find the shortest loop and obtain the target: minimize shipping costs. An exchange local search is an inspection mechanism which adds after greedy algorithm. Proposed method is applied to several facility location problems from OR library and compared with other hybrid clustering algorithm.
Numerical results show that the proposed approach (SSOKHM) performance is better than using other hybrid clustering algorithms in terms of shipping costs. Finally, we embed the exchange local search for each hybrid clustering algorithm. The results are presented that this inspection mechanism can be work in capacity constraint to enhance the performance of the solution and demonstrate the usefulness of this approach in CCP.
Keywords: Capacitated Clustering Location Problem, Simplified Swarm Optimization (SSO), K-harmonic Means (KHM), Travelling Salesman Problem

並列關鍵字

Capacitated Clustering Location Problem ； Simplified Swarm Optimization (SSO), ； K-harmonic Means (KHM) ； Travelling Salesman Problem

參考文獻

[1] Cooper, L., Location–allocation problems. Operations Research, 1963. 11: p. 331–343.

[2] Cooper L., The transportation–location problems. Operations Research, 1972. 20: p. 94–108.

[3] Cooper L. Heuristic methods for location–allocation problem. SIAM Review, 1964. 6: p. 37–53.

[4] Chen, C.H., Ting, C.J., Combining Lagrangian heuristic and Ant Colony System to solve the Single Source Capacitated Facility Location Problem, Transportation Research Part, 2008: p. 1099–1122.

[5] Osman, I.H., Christofides, N., Capacitated clustering problems by hybrid simulated annealing and tabu search, International Transactions in Operational Research. 1994. 1 (3): p. 317–336.