簡易檢索 / 詳目顯示

回結果列表
研究生： 陳柏宏
Chen, Po-Hung
論文名稱： 緊急下配送中心區位選擇與車輛路徑規劃之兩階段式演算法建立與分析
A Two-Phase Algorithm for Relief Distribution Center Selection and Vehicle Routing under Emergency Management
指導教授： 胡大瀛
Hu, Ta-Yin
學位類別： 碩士
Master
系所名稱： 管理學院 - 交通管理科學系
Department of Transportation and Communication Management Science
論文出版年： 2014
畢業學年度： 102
語文別： 英文
論文頁數： 104
中文關鍵詞： 緊急物流 、區位路徑問題 、線上路徑更新演算法
外文關鍵詞： Emergency logistics, Location-routing problem, On-line routes improvement algorithm
相關次數： 點閱：86  下載：5 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 由於天然災害在近年來造成許多傷亡與損失，所以緊急管理的課題越來越受到重視。為了減緩在害發生後的傷亡，有效率的緊急物流扮演重要的腳色。然而，緊急物流的研究仍相當有限，故本研究欲處理緊急配送中心(Urgent Relief Distribution Centers)的區位路徑問題。其決策包含(1)設置多少URDCs(2)URDCs 設置地點(3)需求點要分配給那些URDCs(4)那些需求點被分配給配送車輛(5)需求點配送順序。此外，考慮災後發生的新需求，配送的路徑會透過線上的路徑更新演算法進行改善。 為了解決以上問題，本研究提出兩階段式演算法幫助政府單位進行決策。兩階段式演算法包含緊急配送中心區位路徑演算法與線上路徑更新演算法。緊急配送中心區位路徑演算法用來決定URDC的位置與初始路徑，線上路徑更新演算法在考慮新的需求與路網資訊後進行改善路徑。 本研究利用高雄路網進行實證研究與分析。

    The natural disasters caused enormous casualties and economic loss in recent years. Therefore, the emergency management has become more and more important. In order to mitigate the casualties after the occurrence of the disaster, effective emergency logistics is necessary. However, the planning of emergency logistics is still insufficient. This research tackles the location-routing problem of URDCs(Urgent Relief Distribution Centers). The decisions include (1) how many URDCs to locate, (2) where the location of URDCs should be and (3) which URDCs to be assign to which demand node, (4) which demand nodes to be assign to which routes and (5) in what order the demand should be served on each route. In addition, the vehicles routes will be improved by the on-line routes improvement algorithm when considering the occurrence of new demand.
    To solve these problems this research proposes a two-phase algorithm to help government agencies make decisions. The two-phase algorithm includes the URDCs location-routing algorithm and on-line routes improvement algorithm. The URDCs location-routing algorithm is proposed to determine the location of URDCs and the initial routes in first phase. The on-line routes improvement algorithm is developed to improve the routes to minimize the service time considering the updating information of demand and network condition.
    The empirical experiment is tested by using the network of Kaohsiung city.

    TABLE OF CONTENTS ABSTRACT I ABSTRACT (CHINESE) II ACKNOWLEDGEMENTS III TABLE OF CONTENTS IV LIST OF TABLES VIII LIST OF FIGURES XI CHAPTER 1 INTRODUCTION 1 1.1 Research Background and Motivation 1 1.2 Problem Statement 3 1.3 Research Objective 3 1.4 Research Flowchart 4 1.5 Overview 5 CHAPTER 2 LITERATURE REVIEW 7 2.1 Emergency Logistics 7 2.1.1 Facility Location 8 2.1.2 Relief Distribution 9 2.2 Location-Routing Problem and Solution Methods 10 2.2.1 Exact Algorithm 11 2.2.2 Heuristic Algorithm 11 2.3 The Genetic Algorithm 14 2.3.1 Origin and Characteristics 14 2.3.2 Solution Mechanism 15 2.3.3 Solution Procedure 17 2.3.4 Application 19 2.4 Summary 19 CHAPTER 3 RESEARCH METHODOLOGY 21 3.1 Problem Statement and Research Assumptions 21 3.2 The Framework of this Research 25 3.3 URDCs Location Routing Model 27 3.4 URDCs Location-routing Algorithm 32 3.4.1 Encoding and Fitness 32 3.4.2 Selection 34 3.4.3 Crossover 34 3.4.4 Mutation 36 3.4.5 The Solution Procedure of the URDCs Location Routing Algorithm 36 3.5 On-line Routes Improvement Algorithm 39 3.5.1 Encoding and Fitness 39 3.5.2 Crossover 40 3.5.3 Mutation 42 3.5.4 The Solution Procedure of the On-line Routes Improvement Algorithm 43 CHAPTER 4 PROGRAM DEVELOPMENT 46 4.1 Solution Procedure of URDCs Location Routing Algorithm 49 4.2 Solution Procedure of On-line Routes Improvement Algorithm 53 CHAPTER 5 NUMERICAL EXPERIMENTS 57 5.1 Basic Experiment 57 5.1.1 The Network of San-Min District 57 5.1.2 Problem Description and Test Environment 58 5.2 The Test of URDCs Location Routing Model 62 5.3 The Test of the Location Routing Algorithm 64 5.3.1 The Basic Test and the Illustration of Parameter Settings 64 5.3.2 The Sensitivity Analysis of the Crossover Rate 65 5.3.3 The Sensitivity Analysis of the Mutation Rate 69 5.3.4 The Sensitivity Analysis of the Eliminating Cycle 71 5.3.5 The Sensitivity Analysis of the Combination of Population Size and Number of Generations 74 5.3.6 The Result of Test of the Final Combination of the Parameters 76 5.4 The Test of On-line Routes Improvement Algorithm 78 5.4.1 The Basic Test and the Illustration of Parameter Settings 78 5.4.2 The Sensitivity Analysis of the Mutation Rate 80 5.4.3 The Sensitivity Analysis of the Eliminating Cycle 82 5.4.4 The Sensitivity Analysis of the Length of the Candidates List 84 5.4.5 The Final Combination of Parameters of On-line Routes Improvement Algorithm 86 CHAPTER 6 EMPERICAL EXPERIMENT 89 6.1 The Illustration of Empirical Experiment and Basic Test 89 6.2 Empirical Experiment of URDCs Location Routing Algorithm 94 6.2.1 Effect of the URDC Setup Cost 94 6.2.2 Effect of the Transportation Unit Cost 96 6.3 Empirical Experiment of On-line Route Improvement 97 6.3.1 Effect of Amounts of the Unknown Demand 97 6.3.2 Effect of the Duration of the Time Window 98 CHAPTER 7 CONCLUSIONS AND SUGGESTIONS 100 7.1 Conclusions 100 7.2 Suggestions 101 References 102

    Albareda-Sambola, M., Fernández, E., Laporte, G. (2007), "Heuristic and lower bound for a stochastic location-routing problem," European Journal of Operational Research, Vol 179, pp. 940-955.
    Balcik, B., Beamon, B.M. (2008), "Facility location in humanitarian relief," International Journal of Logistics Research and Applications, Vol 11, pp. 101-121.
    Barreto, S.r., Ferreira, C., Paixa˜o, J., Santos, B.S. (2007), "Using clustering analysis in a capacitated location-routing problem," European Journal of Operational Research, Vol 16, pp. 968–977.
    Caunhye, A.M., Nie, X., Pokharel, S. (2012), "Optimization models in emergency logistics: A literature review," Socio-Economic Planning Sciences, Vol 46, pp. 4-13.
    Chang, M.-S., Tseng, Y.-L., Chen, J.-W. (2007), "A scenario planning approach for the flood emergency logistics preparation problem under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Vol 43, pp. 737-754.
    Charikar, M., Guha, S. (1999), Improved combinatorial algorithms for the facility location and k-median problems. Pages 378-388. Foundations of Computer Science, 1999. 40th Annual Symposium on.
    CWB. (2009), Typhoon Database. http://rdc28.cwb.gov.tw/data.php?num=2009080804&year=2009&c_name=%B2%F6%A9%D4%A7J&e_name=MORAKOT)
    DHS. (2007), DHS risk lexicon. Pages 9. DHS risk lexicon.
    Fiedrich, F., Gehbauer, F., Rickers, U. (2000), "Optimized resource allocation for emergency response after earthquake disasters," Safety Science, Vol 35, pp. 41–57.
    Holguín-Veras, J., Pérez, N., Ukkusuri, S., Wachtendorf, T., Brown, B. (2007), "Emergency Logistics Issues Affecting the Response to Katrina: A Synthesis and Preliminary Suggestions for Improvement," Transportation Research Record: Journal of the Transportation Research Board, Vol 2022, pp. 76-82.
    Huang, S.-H. (2012), Solving the Multi-Compartments Capacitated Location Routing Problem by Genetic Algorithm. Paper presented at The Conference of Chinese Institute of Transportation.
    Laporte, G., Nobert, Y. (1981), "An exact algorithm for minimizing routing and operating costs in depot location," European Journal of Operational Research, Vol 6, pp. 224–226.
    Laporte, G., Nobert, Y., Arpin, D. (1986), "An exact algorithm for solving a capacitated location-routing problem," Annals of Operations Research, Vol 6, pp. 291-310.
    Liao, T.-Y., Wang, S.-J., Hu, T.-Y. (2011), "On-line Vehicle Routing Problems: A Hybrid Meta-Heuristic Approach," Journal of the Eastern Asia Society for Transportation Studies, Vol 9, pp. 660-675.
    Marinakis, Y., Marinaki, M. (2008), "A Bilevel Genetic Algorithm for a real life location routing problem," International Journal of Logistics Research and Applications, Vol 11, pp. 49-65.
    Mete, H.O., Zabinsky, Z.B. (2010), "Stochastic optimization of medical supply location and distribution in disaster management," International Journal of Production Economics, Vol 126, pp. 76-84.
    Nagy, G., S. Salhi. (1996), "Nested Heuristic Methods for the Location-Routeing Problem," Journal of the Operational Research Society, Vol 47, pp. 1166-1174.
    Nagy, G., Salhi, S. (2007), "Location-routing: Issues, models and methods," European Journal of Operational Research, Vol 177, pp. 649-672.
    Özdamar, L., Ekinci, E., Küçükyazici, B. (2004), "Emergency Logistics Planning in Natural Disasters," Annals of Operations Research, Vol 129, pp. 217-245.
    Perl, J., Daskin, M.S. (1985), "A WAREHOUSE LOCATION-ROUTING PROBLEM," Transportation Research Part E: Logistics and Transportation Review, Vol 19B, pp. 381-396.
    Sheu, J.-B. (2007), "Challenges of emergency logistics management," Transportation Research Part E: Logistics and Transportation Review, Vol 43, pp. 655-659.
    Sheu, J.-B., Chen, Y.-H., Lan, L.W. (2005), "A Novel Model for Quick Response to Disaster Relief " Proceedings of the Eastern Asia Society for Transportation Studies, Vol 5, pp. 2454 - 2462.
    Tuzun, D., Burke, L.I. (1999), "A two-phase tabu search approach to the location routing problem," European Journal of Operational Research, Vol 116, pp. 87-99.

    下載圖示 校內：2016-09-03公開
    校外：2016-09-03公開
    QR CODE