跳到主要內容

臺灣博碩士論文加值系統

(18.97.9.172) 您好!臺灣時間:2025/02/14 03:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳昺颐
研究生(外文):Bing-yi Wu
論文名稱:有容量限制的單一分派轉運點位址問題
論文名稱(外文):The capacitated hub location problem with single allocation
指導教授:陳正芳陳正芳引用關係
指導教授(外文):Jeng-Fung Chen
學位類別:碩士
校院名稱:逢甲大學
系所名稱:工業工程與系統管理學研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
畢業學年度:94
語文別:中文
論文頁數:51
中文關鍵詞:軸幅路網轉運點位址問題模擬退火法禁忌名單
外文關鍵詞:hub-and-spokehub location problemsimulated annealingtabu list
相關次數:
  • 被引用被引用:0
  • 點閱點閱:191
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本研究所探討之有容量限制的單一分派轉運點位址問題,是軸幅路網(hub-and-spoke network)應用中的重要課題。軸輻路網之應用,藉由選擇出的中間轉運站來擔任集中、轉運的角色,轉運點之間集中了較大的運輸量,進而達到規模經濟的效益,使得總運送成本有效的降低。在軸幅路網中,轉運點(hub)間完全連結,在路網中擔任集中、轉運的角色,而非轉運點(nonhub或spoke)間必須經由連結轉運點來相互連結。在有容量限制的單一分派轉運點位址問題中,轉運點數目的決定、轉運點位址的選定及非轉運點連結轉運點的分派決策是影響效益的關鍵。本研究所探討的是單一分派的情況,研究中所追求的是決定最適的轉運點數目、選出最適的轉運點位址,並對非轉運點連結轉運點作最適的分派,以使軸幅路網之總成本最小化,此系統的總成本包括:(1)起點至轉運點(origin-hub)的收集成本;(2)轉運點間(inter hub)的運輸成本;(3)轉運點至終點(hub-destination)的配送成本;以及(4)轉運點的個別建置成本。
由於有容量限制的單一分派轉運點位址問題是NP-hard問題,求解過程相當複雜,當處理實務的大問題時,其通常無法在合理時間內求得最佳解,本研究以推導轉運點數目的下界,決定轉運點數目搜尋方式,發展轉運點位址和非轉運點分派的程序,並結合模擬退火法(simulated annealing)與禁忌名單(tabu list),以發展能在合理時間內求得近似最佳解的混合啟發式解法,以方便應用。
This research deals with the capacitated hub location problems with single allocation (CHLP-S). CHLP-S is one of the important topics in hub-and-spoke network. The CHLP-S is a decision problem, in regard to the number of hubs and location-allocation, with the hub-and-spoke network structure. Hub-and-spoke network discuss how to choose the middle hubs to serve as the role of centralizing and transporting. The bigger volume of transportation between hubs could approach the economies of scope and reduce the total cost of transportation. In a hub-and-spoke network, all hubs which act as switching points for internodal flows are interconnected and none of the nonhub nodes (i.e., spokes) are directly connected (i.e., all flow must be routed through the hubs). The key factors for designing a successful hub-and-spoke network are to determine the optimal number of hubs and to properly locate the hubs and to allocate the nonhubs to the hubs, so that the total cost is minimized. The total cost includes (1) the collection cost incurred during the transportation from nonhubs to their allocated hubs; (2) the transfer cost incurred during the transportation between hubs; (3) distribution cost incurred during the transportation from the allocated hubs to nonhubs; and (4) the costs for establishing hubs.
It is know that CHLP-S is NP-hard. When dealing with a large instance, in the worst case, it may not be possible to obtain an optimal solution in a reasonable time. In this research, an approach to derive the upper bound for the number of hubs along with a hybrid heuristic, based on the simulated annealing method, tabu lists, and improvement procedures, are to be developed. Computational characteristics of the proposed approach will be evaluated through extensive computational experiments using data sets from the literature. Comparisons will be made with the optimal solutions and best solutions found in the literature.
目錄
中文摘要 i
英文摘要 iii
目錄 v
圖目錄 vi
表目錄 vi

第一章 緒論……………………………………………………1
1.1研究背景……………………………………………………1
1.2研究目的與方法……………………………………………3
1.3研究架構……………………………………………………4
第二章 文獻探討………………………………………………5
第三章 研究方法及進行步驟…………………………………11
3.1研究假設……………………………………………………12
3.2有容量限制的單一分派轉運點位址問題模式……………12
3.3模擬退火法與禁忌搜尋法…………………………………14
3.4混合啟發式解法架構………………………………………17
3.5相關參數設定………………………………………………28
第四章 研究結果………………………………………………30
4.1測試例題介紹………………………………………………30
4.2結果與比較…………………………………………………31
第五章 結論與建議……………………………………………36
5.1結論…………………………………………………………36
5.2未來研究建議………………………………………………37
參考文獻……………………………………………………… 38

圖目錄
圖1 轉運點示意圖………………………………………………3
圖2 研究步驟流程圖……………………………………………5
圖3 模擬退火法之基本演算流程圖……………………………16
圖4 nonhub點改分派流程圖……………………………………24
圖5 混合啟發式解法的流程圖…………………………………27
圖6 100點以上AP例題最好解比較圖………………………… 35

表目錄
表1 混合啟發式解法執行50點以下AP例題比較表……………34
表2 混合啟發式解法執行100點以上AP例題比較表………… 35
[1]Abdinnour-Helm, S., 1998. A hybrid heuristic for the uncapacitated hub location problem. European Journal of Operational Research 106, 489-499.
[2]Abdinnour-Helm, S., 2001. Using simulated annealing to solve the p-hub median problem. International Journal of Physical Distribution & Logistics Management 31, 203-220.
[3]Abdinnour-Helm, S., Venkataramanan M.A., 1998. Solution approaches to hub location problems. Annals of Operational Research. 78, 31-50.
[4]Aykin, T., 1990. On a quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research 46, 409-411.
[5]Aykin, T., 1994. Largrangian relaxation based approaches to capacitated hub-and-spoke network design problem. European Journal of Operational Research 79, 501-523.
[6]Aykin, T., 1995. Networking policies for hub-and-spoke systems with application to the air transportation system. Transportation Science 29(3), 201-221.
[7]Aykin, T., 1995. The hub location and routing problem. European Journal of Operations Research 83, 201-221
[8]Azizi, N., Zolfanghari, S., 2004. Adaptive temperature control for simulated annealing: a comparative study. Computer and Operations Research 31(4), 2439-2451.
[9]Bellegundu, A.D., Chandrupatla, T. R., 1999. Optimization Concepts and Applications in Engineering. Prentice Hall.
[10]Boland, N., Krishnamoorthy M., Ernst A.T., Ebery J.,. 2004. Preprocessing and cutting for multiple allocation hub location problems. European Journal of Operational Research 155, 638-653.
[11]Bryan, D.L., O’Kelly, M.E., 1999. Hub-and-spoke networks in air transportation: an analytical review. Journal of Regional Science 39(2), 275-295.
[12]Campbell, J.F., 1994. Integer programming formulations of discrete hub location problems. European Journal of Operational Research 72, 387-405.
[13]Campbell, J.F., 1996. Hub location and the p-hub median problem. Operations Research 44(6), 923-935.
[14]Chen, J.-F., 2005a. A heuristic for the uncapacipated multiple allocation hub location problem. Journal of the Chinese Institute of Industrial Engineers. (accepted)
[15]Chen, J.-F., 2005b. A hybrid heuristc for the uncapacipated single allocation hub location problem. Omega-International Journal of Management Science. (in press)
[16]Don T., Et al., 1995. Hub and spoke networks in truckload trucking: configuration, testing, and operational concerns. Logistics and Transportation 31, 209-237.
[17]Ebery, J., Krishnamoorthy, M., Ernst A., Natashia, B., 2000. The capacitated multiple allocation hub location problem: formulations and algorithms. European Journal of Operational Research 120, 614-631.
[18]Elhedhli, S., Hu, F.X., 2005. Hub-and-spoke network design with congestion. Computers and Operations Research 6, 1615-1632
[19]Ernst A.T., Krishnamoorthy M., 1996. Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location Science 4(3), 139-154.
[20]Ernst, A.T., Krishnamoorthy, M., 1998. Exact and heuristic alogorithms for the uncapacitated multiple allocation p-hub median problem. European Journal of Operational Research 104, 100-112.
[21]Ernst, A.T., Krishnamoorthy, M., 1999. Solution algorithms for the capacitated single allocation hub location problem. Annals of Operations Research 86, 141-159.
[22]Glover, F., 1989. Tabu search. Part I, ORSA Journal on Computing 1, 190-206.
[23]Glover, F., 1990. Tabu search. Part II. ORSA, Journal on Computing 2, 14-32.
[24]James, E.R., Edward, M., 1992. Optimization Algorithms for Networks and Graphs. New York Marcel Dekker. Inc.
[25]Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P., 1983. Optimization by simulated annealing. Science 220, 671-680.
[26]Klincewicz, J.G.., 1991. Heuristics for the p-hub location problem. European Journal of Operational Research 53, 25-37.
[27]Klincewicz, J.G.., 1992. Avoiding local optima in the p-hub location problem using tabu search and GRASP. Annals of Operations Research 40, 283-302.
[28]Klincewicz, J.G.., 1997. A dual algorithm for the uncapacitated hub location problem. Location Science 4(3), 173-184.
[29]Klincewicz, J.G.., 1998. Hub location in backbone tributary network design: a review. Location Science 6, 307-335.
[30]Kuby, M.J., Gray, R.G., 1993. Hub network design problem with stopovers and feeders: Case of Federal Express. Transportation Research 27, 1
[31]Lumsden, K., Dallari, F., Ruggeri, R., 1999. Improving the efficiency of the hub and spoke system for the SKF European distribution network. International Journal of Physical Distribution & Logistics Management 29 50-64.
[32]Marin, A., 2004. Formulating and solving splittable capacitated multiple allocation hub location problems. Computers and Operations Research Available online 7 April 2005
[33]Martin, J.C., Roman, C., 2004. Analyzing competition for hub location in intercontinental aviation markets. Transportation Research 40, 135-150.
[34]Metropolis, N., Rosenbluth, A.N., Rosenbluth, M.N., Teller, A.H., 1953. Equation of state calculations by fast computing machines. The Journal of Chemical Physics 21, 1087-1092.
[35]O’Kelly, M E., Bryan, D.L., 2002. Interfacility interaction in models of hub and spook networks. Journal of Regional Science 42(1), 145-164.
[36]O’Kelly, M.E., 1987. A quadratic integer problem for the location of interacting hub facilities. European Journal of Operational Research 32, 393-404.
[37]O’Kelly, M.E., 1992. Hub facility with fixed costs. Papers in Regional Science: The Journal of RSAI. 71(3), 293-306.
[38]O’Kelly, M.E., Bryan, D., Skorin-Kapov D., Skorin-Kapov J., 1996. Hub Network design with single and multiple allocation: a computational study. Locational Science 4(3), 125-138.
[39]O’Kelly, M.E., Bryan, D.L., 1998. Hub location with flow economies of scale. Transportation Research 32(8), 605-616.
[40]O’Kelly, M.E., Skorin-Kapov D., Skorin-Kapov J., 1995. Lower bounds for the hub location problem. Managemant Science 41(4), 713-721.
[41]Osman, I.H., 1993. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research 41, 421-451.
[42]Sasaki, M., Suzuki, A., Drezner, Z., 1999. On the selection of hub airports for an airline hub-and-spoke system. Computers & Operations Research 26, 1411-1422.
[43]Skorin-Kapov D., Skorin-Kapov J., 1994. On tabu search for the location of interacting hub facilities. European Journal of Operational Research 73, 502-509
[44]Skorin-Kapov D., Skorin-Kapov J., O’kelly M.., 1996. Tight linear programming relaxations of uncapacitated p-hub median problem. European Journal of Operational Research 94, 582-593.
[45]Sohn, J., Park, S., 1997. A linear problem for the two-hub location problem. European Journal of Operational Research 100, 617-622.
[46]Sohn, J., Park, S., 1998. Efficient solution procedure and reduced size formulations for p-hub location problems. European Journal of Operational Research 108, 118-126.
[47]Toh, R.S., Higgins, R.C., 1985. The impact of hub and spoke network centralization and route monopoly on domestic airline profitability. Transportation Journal 24, 16-27.
[48]Topcuoglu H, Corut F, Ermis M, Yilmaz G., 2005. Solving the uncapacitated hub location using genetic algorithms. Computers and Operations Research 32, 967-984.
[49]Wong, D.F., Leong, H.W., Liu, C.L., 1998. Simulated Annealing for VLSI Design. Kluwer Academic Publishers.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top