臺灣博碩士論文加值系統

軸幅式路網(hub-and-spoke network)的結構，有助於總運輸成本的降低，其中影響的關鍵在於轉接點(hub)的位址與需求點(nonhub)的分派決策。本研究主要針對轉接點位址問題(hub location problem, HLP)求解，主要目的在找到最佳的轉運點位址與需求點的分派決策，使整個網路中之總運輸成本最小化。由於HLP具有NP-Complete的特性，要在短時間內求得最佳解十分困難，故文獻中大多以啟發式方法求得近似解。
SAHUB演算法，為一模擬退火法(Simulated annealing, SA)及禁忌搜尋法(Tabu search, Tabu)中之禁忌名單(Tabu list)之結合。本研究之求解方法主要應用SAHUB演算法，再加入部分之修改而提出一個新的啟發式演算法 — SAHUBR。
為了測試演算法之穩健性，本研究以文獻中之例題，分別針對單一分派與多重分派下之HLP做測試，除了在參數分析部分找到最合適之參數組合外，並與文獻演算結果做比較。研究結果顯示，本研究所提出之SAHUBR演算法，能夠快速的尋找到最佳解，具有相當不錯之求解效能。

The location of hub facilities is fundamental to the design of a “hub-and-spoke network”, as it greatly affects the total transportation costs of system. Hub is a special type of facility, which is designed to act as switching point for internal flows of a network. The problem is to determine the optimal location for the hubs and the assignments of the nonhubs to hubs that minimizes the overall transportation cost. Due to its characteristics of NP-Complete, it is difficult to obtain optimal solution within an acceptable amount of time.
In this study we consider both single and multiple allocation hub location problems. A hybrid heuristic algorithm based on the SAHUB, combining with simulated annealing(SA) and Tabu list, is developed. During the research, the parameters used in the heuristics that affect the solution quality and efficiency are analyzed and designed with a good parameter setting suggested.
The SAHUBR algorithm presented in this study compares favorably with the computational results obtained from the literature. Experimental results indicate that SAHUBR is capable of obtaining good solutions in a very small amount of time.

目 錄
封面內頁
簽名頁
授權書.........................................................................................................................iii
中文摘要....................................................................................................................iv
英文摘要.....................................................................................................................v
誌 謝........................................................................................................................vii
目 錄.......................................................................................................................viii
圖目錄.........................................................................................................................xi
表目錄........................................................................................................................xii
第一章 緒 論...................................................................................................1
1.1 研究背景與動機...........................................................................1
1.2 研究目的 …2
1.3 研究假設 3
1.4 研究方法與架構 3
1.4.1 研究方法 4
1.4.2 研究架構 5
第二章 文獻探討 6
2.1 轉接點位置問題 6
2.2 轉接點位置問題之文獻回顧 9
2.3 SAHUB演算法 10
2.3.1 起始解 11
2.3.2 移步策略 12
第三章 轉接點位置問題之求解 19
3.1 SAHUBR演算法－起始解 19
3.2 SAHUBR演算法－移步策略 21
3.3 SAHUBR演算法 24
3.4 SAHUBR演算法參數設定及收斂準則 28
第四章 結果分析 30
4.1文獻例題介紹 30
4.2 實驗數據與參數設定 31
4.2.1實驗數據 31
4.2.2 SAHUBR之參數設定 32
4.3 SAHUBR演算法參數分析 33
4.4 SAHUBR演算法與SAHUB之起始解結果比較分析…39
4.5 SAHUBR演算法與文獻演算結果比較分析 42
第五章 結論與建議 45
5.1 研究總結 45
5.2未來研究建議 46
參考文獻 47
附錄一 文獻例題最佳解 51
附錄二 SAHUBR求解單一分派之CAB例題 57
附錄三 SAHUBR求解單一分派之AP例題 64
附錄四 SAHUBR求解單一分派之 67
附錄五 SAHUBR求解多重分派之CAB例題 68
附錄六 SAHUBR求解多重分派之AP例題 75

參考文獻
1 林正章、劉志遠，”兩岸直航航線選擇使用者均衡模式之研究”，民航季刊，Vol. 1(2), pp.197-218, 1999。
2 張斐茹，”軸輻路網在國際定期貨櫃船航線之應用”，國立交通大學交通運輸研究所碩士論文，民國89年。
3 許巧鶯、王志青，”軸輻航空貨運網路之直接與轉運路線選擇”，運輸計劃季刊，Vol. 26(1) , pp.95-118, 1997。
4 熊正一，”兩岸空運直航點選擇策略之研究”，國立成功大學碩士論文，民國88年六月。
5 劉建佑，”應用自組織特徵解決無產能限制單一指派p-中心 中位問題”，朝陽科技大學工業工程與管理系碩士論文，民國91年七月。
6 劉曉君，”轉接點位置問題之啟發式解法”，大葉大學工業工程系碩士論文，民國90年六月。
7 Abdinnour-Helm S. and Venkataramanan M.A,” Soulation approaches to hub location problems,” Annals of Operational Research, Vol. 78, pp.31-50, 1998.
8 Abdinnour-Helm S.,”A hybrid heuristic for the uncapacitated hub location problem,” European Journal of Operational Research, Vol., pp.106, 489, 1998.
9 Abdinnour-Helm S.,”Using simulated annealing to solve the p-hub median problem,” International Journal of Physical Distribution & Logistics Management, Vol. l31, pp.203-220, 2001.
10 Andreas T. Ernst and Mohan Krishnamoorthy, “An exact solution approach based on shortest-paths for p-hub median problems,” Informs Journal on Computing, Vol. 10(2), pp.149-162, 1998.
11 Andreas T. Ernst and Mohan Krishnamoorthy, “Efficient algorithms for the uncapacitated single allocation p-hub median problem,” Location Science, Vol. 4(3), pp.119-154, 1996.
12 Aykin Turgut, “Largrangian relaxation based approaches to capacitated hub-and-spoke network design problem,” European Journal of Operation Research, Vol. 79, pp.501-523, 1994.
13 Aykin Turgut, “Networking policies for hub-and-spoke systems with application to the air transportation system,” Transportation Science, Vol. 29(3), pp.201-221, 1995.
14 C.K. Sydney, L.C. Chu, “A modeling framework for hospital location and service allocation,” International transactions in operational research, Vol. 7, pp.539-568, 2000.
15 Campbell James F, “Integer programming formulations of discrete hub location problems,” European Journal of Operation Research, Vol. 29, pp.387-405, 1994.
16 Campbell James F., “Location and allocation for distribution system with transshipments and transportation economies of scale,” Annals of Operations Research, Vol.40, pp.77-99, 1992.
17 Chryssi Malandraki and Robert B. Dial, “A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem,” European Journal of Operation Research, Vol.90, pp.45-55, 1996.
18 Chung Sung-hark, Young-soo Myung and Dong-wan Tcha, “Optimal design of a distributed network with a two-level hierarchical structure,” European Journal of Operation Research, Vol.62, pp.105-115, 1992.
19 Dai, Z., Cheung, T.-Y., “New heuristic approach for the p-median problem,” Journal of the Operational Research Society 48(9),950-960,1997
20 Deborah L. Bryan and Morton E. O’kelly, “Hub- and-spoke network in air transportation: An analytical review,” Journal of Reginal Science, Vol. 39(2), pp.275-295, 1999.
21 O’Kelly Morton E. and D. L. Bryan, “Hub location with flow economies of scale,” Transportation Scienc, Vol. 32(8), pp.605-616, 1998.
22 O’Kelly Morton E., “A quadratic integer problem for the location of interacting hub facilities,” European Journal of Operational Research, Vol.32, pp.393-404, 1987.
23 O’Kelly Morton E., “Hub facility with fixed costs,” Papers in Regional Science: The Journal of RSAI, Vol. 71(3), pp.293-306, 1992.
24 O’Kelly Morton E., “The location of interacting hub facilities,” Transportation Science, Vol. 20(2), pp.92-105, 1986.
25 O’Kelly Morton E., Darko Skorin-Kapov and Jadranka Skorin-Kapov, “Hub network design with single and multiple allocation a computational study,” Location Science, Vol. 4(3), pp.125-118, 1996.
26 O’Kelly Morton E., Darko Skorin-Kapov and Jadranka Skorin-Kapov, “Lower bounds for the hub location problem,” Management Science, Vol. 41(4), pp.711-291, 1995.
27 Skorin-Kapov Darko and Jadranka Skorin-Kapov,” On tabu search for the location of interacting hub facilities,” European Journal of Operational Research, Vol.73, pp.502-509, 1994