跳到主要內容

臺灣博碩士論文加值系統

(44.192.247.184) 您好!臺灣時間:2023/01/30 12:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:呂國瑞
研究生(外文):Kuo-Rui Lu
論文名稱:應用貪婪隨機自適應搜尋法求解多階容量限制下單一分派p轉運點中位問題
論文名稱(外文):Apply Greedy Randomized Adaptive Search Procedures for Solving Capacitated Single Allocation p-Hub Median Problem with Multiple Capacity Levels
指導教授:丁慶榮丁慶榮引用關係
指導教授(外文):Ching-JungTing
口試委員:顏上堯徐旭昇
口試委員(外文):Shang-YaoYanChiuh-ChengChyu
口試日期:2012-7-19
學位類別:碩士
校院名稱:元智大學
系所名稱:工業工程與管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
畢業學年度:100
語文別:中文
論文頁數:107
中文關鍵詞:軸輻式網路容量限制下單一分派p轉運點中位問題貪婪隨機自適應搜尋法拉氏鬆弛法多容量層級
外文關鍵詞:Multiple capacity levelsHub-and-Spoke NetworkCapacitated single allocation p-Hub Median ProblemGRASPLagrangian relaxation
相關次數:
  • 被引用被引用:0
  • 點閱點閱:258
  • 評分評分:
  • 下載下載:7
  • 收藏至我的研究室書目清單書目收藏:0
不同國家間之企業來往頻繁以及國際化經濟快速地發展,再加上國內經營條件的限制、市場需求變化,使得許多企業紛紛將其業務觸角拓展至國外,形成企業中功能型部門因原物料或地理位置所需而座落於不同的國家或地區,進而形成了如何將分散於多國之間的資源藉由供應鏈網路運輸來整合、分派的議題;再者,由於轉運設施的設置屬於高額成本的投資,且屬於企業策略性決策,故使得規劃轉運點的區位成為了一項重要的議題。
「單一分派轉運點區位問題」同時探討轉運點區位的設置與顧客點的分派外,還需考量最適的轉運點數,而單一分派p轉運點中位問題則屬於此問題之特例;依場站容量限制上,可區分為有容量限制(capacitated)與無容量限制(Uncapacitated)等限制,而本研究為了增加該問題之適用性及彈性,增加了多個容量層級可供選擇以探討多階容量限制下單一分派p轉運點中位問題。當網路中的節點數及轉運點候選數增加時,使用正確解法求解將會十分耗時,故近幾年來大多學者採用啟發式演算法,以期望於合理的時間內求得近似最佳解。貪婪隨機自適應搜尋法對於組合最佳化問題有很好的求解效果,故本研究希望發展一個以貪婪隨機自適應搜尋法以及拉氏鬆弛法為基之演算法,以討論上述之多階容量限制下單一分派p轉運點中位問題,並求解標竿例題澳洲郵局(AP)。結果顯示在多階容量限制下單一分派p轉運點中位問題中,提出之演算法均能求解大多數例題至最佳,並能在合理的時間內找到近似最佳解。因此,本研究所提出之演算法適合探討多階容量限制下單一分派p轉運點中位問題,且求解效果相較文獻中之其他方法具有競爭力,並將進行大型例題的測試以確認所提出方法之效率及穩健。
Hub and spoke network has been used in telecommunications and transportation systems. In such a network, the decisions on the location transshipment points, where the flows between origin-destination (O/D) pairs are consolidated, and the paths for sending the flows between the O/D pairs have to be determined. The capacitated single allocation p-hub median problem (CSApHMP) is to decide the locations of the p hubs with capacity restriction and the allocation of non-hub nodes.
In this research, an extension of the classical capacitated single allocation p-hub median problem is studied, in which the size of the hubs is part of the decision making process, called capacitated single allocation p-hub median problem with multiple capacity levels (CSApHMPMC). A set of capacities is assumed to be available to select for each candidate hub. We formulate the problem as a 0-1 integer programming model. A Lagrangian relaxation (LR) approach and a greedy randomized adaptive search procedure (GRASP) algorithm are proposed to solve the CSApHMPMC). The Lagrangian function that we formulated decomposed the original problem into smaller subproblems that can be solved easier. Computational experiments with Australia Post (AP) data set (ranging from 10 to 50 nodes and five capacity levels) from literature are performed for both proposed algorithms. We also use Gurobi to solve the small size instance for comparison. For all tested instance, GRASP can obtain optimal solutions in most of the instances and obtain more optimal solutions than those by LR approach. In the future, larger size instances should be tested to confirm the efficiency and robustness of our proposed algorithms.
摘要 i
ABSTRACT ii
第一章 緒論 1
1.1 研究背景和動機 1
1.2 研範圍和目的 3
1.3 研究架構 4
第二章 文獻探討 6
2.1多階容量限制下單一分派p轉運點中位問題 6
2.2 貪婪隨機自適應搜尋法 12
2.2.1 GRASP建構解方法 13
2.2.2 受限制候選清單 14
2.2.3 區域搜尋 16
2.3 小結 18
第三章 多階容量限制下單一分派p轉運點中位問題 20
3.1 多階容量限制下單一分派p轉運點中位問題 21
3.1.1模式假設 22
3.1.2 數學模式 22
3.2拉氏鬆弛法 24
3.2.1演算步驟 26
3.3貪婪隨機自適應搜尋法 27
3.3.1互動式GRASP 32
3.3.2 解編碼之方法 35
3.3.3區域搜尋法 35
3.4 小結 37
第四章 結果分析 39
4.1 測試例題介紹 39
4.2 參數設定與分析 41
4.2.1拉氏鬆弛法之參數分析 42
4.2.2 GRASP之參數分析 42
4.3例題測試結果及分析 46
4.4 小結 58
第五章 結論與未來研究建議 60
5.1 結論 60
5.2未來研究建議 61
參考文獻 62
附錄A LR在|Qk|=1之演算結果 67
附錄B LR之演算結果 68
附錄C Reactice GRASP 之演算結果 88
1.林智勇,「具容量限制之p-Hub中位問題之研究」,成功大學交通管理科學研究所,碩士論文,2004。
2.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.
3.Aykin, T., “Lagrangian relaxation based approach to capacitated hub-and-spoke network design problem”, European Journal of Operational Research, 79, pp. 501-523, 1994.
4.Binato, S., Hery, W.J., Loewenstern, D. and Resende., M.G.C., “A greedy randomized adaptive search procedure for job shop scheduling”, In P. Hansen and C.C. Ribeiro (Editors), Essays and surveys on metaheuristics. Kluwer Academic Publishers, 2001.
5.Bresina, J. L., “Heuristic-biased stochastic sampling”, Proceedings of the National Conference on Artificial Intelligence, 1, pp. 271-278, 1996.
6.Bundschuh, M., Klabjan, D. and Thurston, D.L. “Modeling robust and reliable supply chains”, University of Illinois, U.S.A., 2003.
7.Campbell, J. F., “Integer programming formulations of discrete hub location problems”, European Journal of Operational Research, 72, pp. 387-405, 1994.
8.Campbell, J. F., Ernst, A. T. and Krishnamoorthy, M., “Hub location problems”, Facility Layout: Applications and Theory (Editors: Drezner, Z., and Hamacher, H. W.), Springer-Verlag. New York, pp. 373-407, 2004.
9.Carello, G., Della Croce, F., Ghirardi, M. and Tadei, R., “Solving the hub location problem in telecommunication network design: A local search approach”, Networks, 44, pp. 94-105, 2004.
10.Chen, J. F., “A heuristic for the uncapacitated multiple allocation hub location problem”, Journal of the Chinese Institute of Industrial Engineers, 23, pp. 371-381, 2006.
11.Contreras, I., Diaz, J. A., and Fernandez, E., “Lagrangean relaxation for the capacitated hub location problem with single assignment”, OR Spectrum, 31, pp. 483-505, 2009.
12.Contreras, I., Diaz, J. A., and Fernandez, E., “Branch and price for large-scale capacitated hub location problems with single assignment”, INFORMS Journal on Computing 23, pp. 41-55, 2011.
13.Contreras, I., Cordeau, J. F. and Laporte, G., “Exact solution of large-scale hub location problems with multiple capacity levels”, Transportation Science, pp. 1-21, 2012. DOI: http://dx.doi.org/10.1287/trsc.1110.0398
14.Correia, I. and Captivo, M.E., “A Lagrangean heuristic for a modular capacitated location problem”, Annals of Operations Research, 122, pp. 141-161, 2003.
15.Correia, I., Nickel, S. and Saldanha-da-Gama, F., “Single-assignment hub location problems with multiple capacity levels”, Transportation Research Part B, 44, pp. 1047-1066, 2010.
16.Correia, I., Nickel, S. and Saldanha-da-Gama, F., “Hub and spoke network design with single-assignment, capacity decisions and balancing requirements”, Applied Mathematical Modelling, 35, pp. 4841-4851, 2011.
17.da Graca Costa, M., Captivo, M.E. and Climaco, J., “Capacitated single allocation hub location problem - A bi-criteria approach”, Computers &; Operations Research, 35, pp.3671-3695, 2008.
18.Delmaire, H., Diaz, J.A., Fernandez, E. and Ortega, M., “Reactive GRASP and tabu search based heuristics for the single source capacitated plant location problem”, INFOR Journal, 37, pp. 194-225, 1999.
19.Ernst, A. T. and Krishnamoorthy, M., “Solution algorithms for the capacitated single allocation hub location problem”, Annals of Operations Research, 86, pp. 141-159, 1999.
20.Elhedhli, S. and Wu, H., “A Lagrangean heuristic for hub-and-spoke system design with capacity selection and congestion”, INFORMS Journal on Computing, 22, pp. 282-296, 2010.
21.Feo, T.A. and Resende, M.G.C., “A probabilistic heuristic for a computationally difficult set covering problem”, Operations Research Letters, 8, pp. 67-71, 1989.
22.Festa, P. and Resende, M.G.C., “An annotated bibliography of GRASP, Part I: Algorithms”, International Transactions in Operational Research, 16, pp. 1-24, 2009.
23.Garey, M. R. and Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York, 1979.
24.Hart, J.P. and Shogan, A.W., “Semi-greedy heuristics: An empirical study”, Operations Research Letters, 6, pp.107-114, 1987.
25.Holmberg, K., “Solving the staircase cost facility location problem with decomposition and piecewise linearization”, European Journal of Operational Research, 75, pp. 41-61, 1994.
26.Holmberg, K. and Ling, J., “A Lagrangean heuristic for the facility location problem with staircase costs”, European Journal of Operational Research, 97, pp. 63-74, 1997.
27.Klincewicz, J.G., “Avoiding local optima in the p-hub location problem using tabu search and GRASP”, Annals of Operations Research, 40, pp. 283-302, 1992.
28.Klincewicz, J.G. , “Enumeration and search procedures for a hub location problem with economies of scale”, Annals of Operations Research , 110, pp. 107-122, 2002.
29.Labbe, M., Yaman, H. and Gourdin, E., “A branch and cut algorithm for the hub location problems with single assignment”, Mathematical Programming, 102, pp. 371-405, 2005.
30.Mockus, J., Eddy, W., Mockus. A., Mockus, L. and Reklaitis, G., Bayesian Heuristic approach to discrete and global optimization. Kluwer Academic Publishers, Netherlands, 1996.
31.O’Kelly, M. E., “A quadratic integer program for the location of interacting hub facilities”, European Journal of Operational Research, 32, pp. 393-404, 1987.
32.Paris, M. and Ribeiro, C.C., “Reactive GRASP: An application to a matrix decomposition problem in TDMA traffic assignment”, INFORMS Journal on Computing, 12 , pp. 164-176, 2000.
33.Perez, M., Almeida, F. and Marcos Moreno-Vega, J., “A hybrid GRASP-Path Relinking algorithm for the capacitated p - Hub median problem”, Lecture Notes in Computer Science, 3636 , pp. 142-153, 2005.
34.Resende, M.G.C., Pitsoulis, L.S. and Pardalos, P.M., “Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP”, Discrete Applied Mathematics, 100, pp. 95-113, 2000.
35.Rodriguez, V., Alvarez, M.J., Barcos, L., “Hub location under capacity constraints”, Transportation Research Part E, 43 , pp. 495-505, 2007.
36.Snyder, L. V. and Daskin, M. S., “Reliability models for facility location: The expected failure cost case”, Transportation Science, 39, pp. 400-416, 2005.
37.Stanimirović, Z., “A genetic algorithm approach for the capacitated single allocation p-hub median problem”, Computing and Informatics, 29, pp. 117-132, 2010.
38.Yaman, H., “Star p-hub median problem with modular arc capacities ”, Computers &; Operations Research, 35, pp.3009-3019, 2008.
39.Yaman, H. and Carello, G., “Solving the hub location problem with modular link capacities”, Computers &; Operations Research, 32, pp. 3227-3245, 2005.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top