具容量限制下單一指派轉運點問題研究

A Study on the Capacitated Single Allocation Hub Location Problem

李彥翰(Yan-Han Lee)

指導教授 ： 申生元

元智大學/資訊學院/資訊管理學系/碩士(2011年)

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

摘要

隨著全球化競爭的興起，資訊科技日新月異，物流系統、通訊網路等產業的重要性也日益提升。台灣地屬亞太經貿之樞紐位置，經濟仰賴出口貿易，運輸物流的機能和服務品質便成為台灣經濟的成敗因素。企業能否利用最少的成本，將物品或資訊傳遞到目的地，已經成為大家所關注的議題。因此近年來，已有諸多業者利用類似軸輻網路架構(hub-and-spoke network)進行轉運以降低營運成本，提昇企業競爭力。
本研究主要針對具容量限制之單一指派轉運點問題(CSAHLP)進行混合整數模式(Mixed Integer Programming)建構，然後提出一個最佳化結合啟發式之演算法。首先將原混合整數模式簡化成具固定成本考量之設施區為選擇及指派的問題模式(FLAPwFC)Facility Location and Allocation problem with fixed charge)，再利用LP Relaxed進行求解，根據求解之結果，對FLAPwFC模式加入限制式，重複求解，以獲得潛在的轉運點集合。然後根據潛在的轉運點集合建構FLAPwFC模式，並運用分支界限法(Branch and Bound)求解，將解到之轉運點視為原模式CSAHLP可開設之候選位址集合，再利用最佳化軟體在給定求解時間下進行求解，重複選取步驟直到設定停止條件。本研究以國際期刊上之標準例題進行測試，比較本方法和其他期刊方法的結果進行分析，而利用最佳化求解本問題時，需花費較長時間，甚至會記憶體不足，本問題雖屬長期規劃，但出現記憶體不足則無法提供企業可行的參考依據，研究測試結果顯示本論文設計之演算法可在允許時間內，提供良好之規劃品質。

關鍵字

轉運點 ； 混合整數模式規劃 ； 線性規劃鬆弛 ； 分支界限法

並列摘要

With the rise of global competition and the rapid change of information technologies, well developed logistics systems and communications networks have played important roles to upgrade competitiveness for some industries. Since Taiwan located as an economic and trade hub position of the Asia-Pacific rim, the provision of excellent logistics function and higher quality of service will be urgent issues to the development of Taiwan's economic. How to economically transport items or information from the origins to the destinations has been an attracted research topic in the last two decades. One of the transport framework known as the hub-and-spoke network has proven its ability in cost reduction and enhancement of competitiveness.
This study focused on developing a solution algorithm for solving the capacitated single allocation hub location problem (CSAHLP). We first formulate the problem as a mixed-integer programming model, and then propose an algorithm which combines heuristic and optimization methods. First, instead of solving CSAHLP directly, we construct a simplified model- the Facility Location and Allocation Problem with Fixed Charge (FLAwFC) and then solve the linear programming relaxation of FLAwFC repeatedly to build a candidate set of hub locations. Second, we try to solve the restricted FLAwFC with hubs chosen from the candidate set using a branch and bound method with limited computational time. Third, a restricted CASHLP model is then constructed with the hubs restricted to the set of hubs of all solutions obtained at the second step; the model is still solved using a B&B method but starting with the best incumbent solution found so far. The second and third steps are applied repeatedly until a stopping criterion is reached. In this study, 56 benchmark data sets were tested. Our experimental results demonstrate that our algorithm can provide good solution quality within reasonable computational effort.

並列關鍵字

Branch and Bound ； Hub ； Linear Programming Relaxation ； Mixed Integer Programming

參考文獻

[2] G.G Cornurjols, G. L. Nemhauser and L. A. Wolsey. "The uncapacitated facility location problem," In Discrete Location Theory, R.L. Francis and P. Mirchandani (eds. ). Wiley Interscience, NewYork, 1990.

[3] M. E. O'Kelly and H. J. Miller, "The hub network design problem: A review and synthesis," Journal of Transport Geography, vol. 2, pp. 31-40, 1994.

[5] S. Alumur and B. Y. Kara, "Network hub location problems: The state of the art," European Journal of Operational Research, vol. 190, pp. 1-21, 2008.

[6] S.L. Shaw, "Hub structures of major US passenger airlines," Journal of Transport Geography, vol. 1, pp. 47-58, 1993.

[8] W. Wei, "Network design issues in terabit optical internet," Communication Engineer, vol. 1, pp. 38-41, 2003.