應用蟻群最佳化演算法求解無容量限制p轉運點中位問題

Apply Ant Colony Optimization for Solving Uncapacitated P-Hub Median Problem

馬綱廷(Kang-Ting Ma)

指導教授 ： 丁慶榮

元智大學/工程學院/工業工程與管理學系/碩士(2008年)

https://doi.org/10.6838/YZU.2008.00112

摘要

由於受到經濟全球化的影響，使得長距離貨物運輸的需求逐漸增加，企業為了降低運輸成本以提升核心競爭力，便將運輸功能外包第三方物流業者。有鑑於軸輻式運輸網路可以減少沒有效率的航線，並且能提升運具的使用率，故在運輸產業已被廣泛的應用。由於轉運點的區位會影響到外部服務網路的效率，此外，轉運點設施的建構成本很高，故使得規劃轉運點的區位成為了一項重要的議題。
「p轉運點中位問題」同時探討了轉運點的區位與非轉運點的分派。當網路中的節點與轉運點數目增加時，求得確定解將會十分耗時，甚至會有無法求解的狀況，故近年來許多學者採用萬用啟發式演算法，以期望在較短的時間內求得近似最佳解。蟻群最佳化演算法具有多點搜尋與快速適應的優點，使得該演算法在組合最佳化問題有很好的表現，然而在探討p轉運點中位問題時，卻很少有作者採用。本研究修改傳統蟻群最佳化演算法，並針對p轉運點中位問題需要同時解決「轉運點的區位」與「顧客點的分派」的特性，以達成軸輻式運輸網路之「總運輸成本最小化」的目標。本研究針對「無容量限制下單一分派p轉運點中位問題」與「無容量限制下多重分派p轉運點中位問題」進行參數之敏感度分析與標竿測試例題的求解。本研究所提出之演算法在單一分派問題中，於AP測試例題中，8個尚未找到最佳解之測試例題裡，有3個超越文獻最佳解；在多重分派問題中，在所有已知最佳解之測試例題中，均能求得最佳解。從演算的結果顯示本研究所提出之演算法在求解效果上較文獻中其他方法具有競爭力。

關鍵字

軸輻式網路 ； 轉運點中位問題 ； 蟻群最佳化演算法 ； 物流管理

並列摘要

Demand of long hual transportation is increasing as a result of economic globalization. Hence, enterprises outsource the transportation function to the third party logistic, 3PL in order to elevate core competence. Hub and spoke network is adopted by transportation industry due to the cost of international transportation is expensive. Since location of hubs would affect efficiency of entire transportation network, and high fixed cost of hub facilities are expensive, location of hub has became an important issue. It is extremely hard to solve exactly p-hub median problem, while number of nodes and hubs are increasing. Hence, in recent years, metaheuristic algorithms such as Ant Colony Optimization Algorithm, ACO or Genetic Algorithm, GA are adopted, and solve the problem in reasonable time. Especially ACO has shown outstanding performance in the combinatorial optimization problem, but few literature of p-hub median problem employs ACO. In this paper, a metaheuristic algorithm base on ACO is proposed, which contains solution construction of location of hubs and allocation of non-hubs and a local search mechanism as well. The objective of p-hub median problem is to minimize the total transportation cost. This paper not only treats uncapacitated single allocation p-hub median problem, but also treats uncapacitated multiple allocation p-hub median problem. In AP data set of single allocation problem, our algorithm obtains several novel solutions and the objective value in three out of eight non-optimal solution instances. In multiple allocation problem, our algorithm obtains optimal solutions in both CAB or AP data set. As the computational results, the proposed algorithm is not only effective, but also efficient. Hence, it should be a feasible method to deal with uncapacitated p-hub median problem.

並列關鍵字

Hub and Spoke Network ； P-hub Median Problem ； Ant Colony Optimization ； Logistic Management

參考文獻

7.陳家和、丁慶榮，「應用二階段蟻群演算法求解P-中位問題之研究」，運輸學刊，十九卷第四期，頁383-404，2007。

5.林正章、吳俊霖，「路線貨運業內部營運規劃之研究」，運輸計劃季刊，第三十一卷第四期，頁739-764，2002。

16.Abdinnour-Helm, S., “A Hybrid Heuristic for the Uncapacitated Hub Location Problem”, European Journal of Operational Research, 106, pp.489-499, 1998.

17.Abdinnour-Helm, S., “Using Simulated Annealing to Solve the P-hub Median Problem”, International Journal of Physical Distribution & Logistics Management, 31, pp. 203-220, 2001.

18.Alumur, S. and Kara, B. Y., “Network Hub Location Problems: The State of the Art”, European Journal of Operational Research, 190, pp.1-21, 2008.