進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-1508202016420900
論文名稱(中文) 禁忌搜尋法於自駕卡車搭配無人機模式之最佳配送
論文名稱(英文) A Tabu Search Solution Algorithm for Autonomous Truck-Drone Delivery
校院名稱 成功大學
系所名稱(中) 交通管理科學系
系所名稱(英) Department of Transportation & Communication Management Science
學年度 108
學期 2
出版年 109
研究生(中文) 黃冠捷
研究生(英文) Guan-Jie Huang
學號 R56061091
學位類別 碩士
語文別 英文
論文頁數 95頁
口試委員 指導教授-胡大瀛
口試委員-魏健宏
口試委員-董啟崇
口試委員-朱致遠
口試委員-陳麗雯
中文關鍵字 禁忌搜尋演算法  自駕車  無人機  搭配無人機之旅行銷售員問題 
英文關鍵字 Tabu Search  Autonomous Vehicle  Unmanned Aerial Vehicle  Traveling Salesman Problem  Flying Sidekick Traveling Salesman Problem 
學科別分類
中文摘要 近年來,研究廣泛應用於物流領域且物流服務業者極力尋求創新的交付方式以應對時間壓力和勞動力短缺,卻於緊急情況下的物資配送尚未有完善研究。2009年8月6日至8月10日,莫拉克颱風襲擊台灣並帶來嚴重水災。莫拉克颱風引起的水災造成681人死亡及18人失蹤。更嚴重的是,洪水破壞了建築物、道路、橋樑,甚至是數個山區的唯一聯外道路。一旦山區失去聯外交通道路,空投就成為獲取食糧、物資的唯一選擇。然而,空投的資源短缺使這些村莊面臨艱困考驗。此次事件亦突顯出緊急情況下,如何應用空投並以快速且準確地援助大量備品,以滿足所有急需的民眾。
儘管有多數研究討論物流領域的車輛路徑問題,但多數都是以民眾購買日常用品之物流方面為主,然而物流同時也是發生災難時運送物資的重要工具;故本研究希望能利用創新的智慧型運輸系統,對於自駕卡車以及無人機緊急物資的運輸進行探討。本研究認為一旦發生緊急情況,透過自駕車隨時待命並且無須人員駕駛的優點,在有限的時間內將助於進行人道物流,若發生道路損毀之災害時,搭配雙無人機進行物資的投遞亦是一大幫助。然而,對於傷患而言,最重要的是快速而適度地運送醫療物資。通過優化路線和適度分配資源,自駕車與無人機進行醫療救災運輸可以有效地救助受難患者,為了提高運送醫療物資的效率,自駕車以及無人機的串聯運用應能成為該問題的最佳解決方案。
本研究開發一模型為運用雙無人機搭配自駕卡車之模式進行緊急物資運輸,將物流領域中創新的思維應用於緊急物資配送中的車輛路徑問題,考量運送時間最佳化目標下,基於禁忌搜尋演算法求解最佳路徑並與商業求解器GUROBI進行比較;結果有望為自駕車及無人機提供最佳路線。期望提供利害關係人在緊急情況下採用自駕卡車及無人機運送醫療物資有更進一步之參考及建議。
英文摘要 Between August 6, 2009, and August 10, 2009, the deadly typhoon Morakot has hit Taiwan which brought the rainfall and the worst flooding across the country. Due to the devasting flooding incident, 681 people were dead and 18 went missing. Furthermore, the flooding washed away buildings, roads, bridges, and destroyed the only way back and forth of several mountain areas. Once the villages and towns lose the important traffic, air-delivery becomes the only choice to obtain supplies. However, the shortness of the air-delivery made the villages face tough trials. In such an emergency, the most concerned in this research is delivering numerous supplies quickly, properly, and accurately to meet everyone who is in urgent need.
In recent years, most logistics service providers are desired to seek innovative delivery options to fight with time pressure and labor shortages. In that case, autonomous vehicles seem to be the most appropriate solution to solve the problem. In Singapore, Jurong Island has applied autonomous trucks because of the shortage of labor. In America, autonomous trucks are the only solution in increasing efficiency to fight against the increasing volume of freights. According to National Development Council in Taiwan, the total population from 2020 to 2065 will decrease from 23 million to 17 million. The shortage of labor will bother Taiwan. The autonomous truck can redeem the shortage of labor and increase the efficiency in transportation and safety by automotive control. All the strengths can be achieved by autonomous vehicles, that is why this research focuses on ITS technologies such as an autonomous truck.
The objective of this research aims to develop a model for delivering relief resources in an emergency using Intelligent Transportation System (ITS) such as autonomous vehicles and unmanned aerial vehicles (UAVs). This research focuses on the routing problem in emergency logistics. Logistics has been mostly utilized in the commercial field. However, logistics is also an important tool to transport relief resources when a disaster occurs.
Once the emergency occurs, autonomous vehicles can prevent the labor shortage. In limited time, UAVs are useful to do humanitarian logistics and the most important for those injuries is to deliver relief resources fast and moderately. By optimizing the route and distributing the resource moderately, relief transporting by autonomous vehicles can efficiently transport to injuries from the disaster. Despite the autonomous trucks are mostly utilize in delivering cargos, the development of the intelligent transportation system is the trends sweeping across the whole world. Thus, this research is desired to adopt autonomous trucks cooperating with two UAVs to transport supplies when an emergency occurs. To enhance the efficiency in delivering supplies, this research aims to develop a model for traveling salesman problem with two drones based on tabu search algorithm. Finally, the results are expected to present optimal routes for an autonomous truck and UAVs and be compared with a standard commercial solver, GUROBI. This research is contributed to providing some ideals for delivering relief resources in an emergency adopting the autonomous truck cooperating with two UAVs.
論文目次 Abstract i
摘要 iii
Contents iv
List of Table vi
List of Figure vii
CHAPTER 1 INTRODUCTION 1
1.1 Research Motivation and Background 1
1.2 Research Objectives 3
1.3 Research Flow Chart 3
CHAPTER 2 LITERATURE REVIEW 6
2.1 Autonomous Vehicles 6
2.2 Unmanned Aerial Vehicle (UAV) 8
2.2.1 Current States of Unmanned Aerial vehicles 8
2.2.2 Developments of Unmanned Aerial vehicles 9
2.3 Traveling Salesman Problem 10
2.3.1 Traveling Salesman Problem (TSP) 10
2.3.2 The Flying Sidekick Traveling Salesman Problem (FSTSP) 11
2.4 Vehicle Routing Problem 14
2.4.1 The Introduction of Vehicle Routing Problem 14
2.4.2 The extended problem of VRP 15
2.5 Tabu Search Method 25
2.6 Summary 28
CHAPTER 3 RESEARCH METHODOLOGY 29
3.1 Conceptual Framework 29
3.2 Problem Statement and Research Assumptions 30
3.3 Research Framework 34
3.4 Mathematical Formulation 36
3.5 Solution Algorithm 49
CHAPTER 4 NUMERICAL ANALYSIS 52
4.1 The Structure of Mathematical Model 52
4.2 The Structure of Heuristic Approach 53
4.2.1 Tabu Search Solution Algorithm 53
4.2.2 Heuristic Flowchart 57
4.3 Test Network Development 59
4.3.1 Test Network I 59
4.3.2 Test Network II 62
4.4 Results of Test Networks 64
4.4.1 Results of Test Network I Solving by GUROBI 64
4.4.2 Results of Test Network I Solving by Tabu Search Algorithm 68
4.4.3 Results of Test Network II Solving by GUROBI 70
4.4.4 Results of Test Network II Solving by Tabu Search Algorithm 72
4.5 Summary 74
CHAPTER 5 EMPIRICAL STUDY 76
5.1 Experimental Design and Setup 76
5.1.1 Experimental Design 76
5.1.2 Experimental Setup 79
5.2 Empirical Experiments 80
5.2.1 Empirical Instance with 20 Nodes 80
5.2.2 Empirical Instance with 30 Nodes 82
5.2.3 Empirical Instance with 40 Nodes 83
5.3 Results of Experimental Network 84
5.4 Summary 90
CHAPTER 6 CONCLUSIONS AND SUGGESTIONS 91
6.1 Conclusions 91
6.2 Suggestions 92
REFERENCE 93

參考文獻 REFERENCE
Agatz, N., Bouman, P., & Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science, 52(4), 965-981.
Archetti, C., Fernández, E., & Huerta-Muñoz, D. L. (2017). The flexible periodic vehicle routing problem. Computers & Operations Research, 85, 58-70.
Belgin, O., Karaoglan, I., & Altiparmak, F. (2018). Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Computers & Industrial Engineering, 115, 1-16.
Bortfeldt, A., Hahn, T., Männel, D., & Mönch, L. (2015). Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints. European Journal of Operational Research, 243(1), 82-96.
Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313.
Burer, S., & Letchford, A. N. (2012). Non-convex mixed-integer nonlinear programming: A survey. Surveys in Operations Research and Management Science, 17(2), 97-106.
Campbell, A. M., & Wilson, J. H. (2014). Forty years of periodic vehicle routing. Networks, 63(1), 2-15.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
de Freitas, J. C., & Penna, P. H. V. (2018). A Randomized Variable Neighborhood Descent Heuristic to Solve the Flying Sidekick Traveling Salesman Problem. Electronic Notes in Discrete Mathematics, 66, 95-102.
Desrochers, M., & Laporte, G. (1991). Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Operations Research Letters, 10(1), 27-36.
Erdoğan, S., & Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 48(1), 100-114.
Estrada, M. A. R., & Ndoma, A. (2019). The uses of unmanned aerial vehicles–UAV’s-(or drones) in social logistic: Natural disasters response and humanitarian relief aid. Procedia Computer Science, 149, 375-383.
García-Nájera, A., Bullinaria, J. A., & Gutiérrez-Andrade, M. A. (2015). An evolutionary approach for multi-objective vehicle routing problems with backhauls. Computers & Industrial Engineering, 81, 90-108.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533-549.
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.
Goel, A., & Gruhn, V. (2008). A general vehicle routing problem. European Journal of Operational Research, 191(3), 650-660.
Gribkovskaia, I., Laporte, G., & Shyshou, A. (2008). The single vehicle routing problem with deliveries and selective pickups. Computers & Operations Research, 35(9), 2908-2924.
Ha, Q. M., Deville, Y., Pham, Q. D., & Ha, M. H. (2018). On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 86, 597-621.
Huang, Y., Zhao, L., Van Woensel, T., & Gross, J.-P. (2017). Time-dependent vehicle routing problem with path flexibility. Transportation Research Part B: Methodological, 95, 169-195.
Joerss, M., Schröder, J., Neuhaus, F., Klink, C., & Mann, F. (2016). Parcel delivery: The future of last mile. McKinsey & Company.
Khademi, N., Balaei, B., Shahri, M., Mirzaei, M., Sarrafi, B., Zahabiun, M., & Mohaymany, A. S. (2015). Transportation network vulnerability analysis for the case of a catastrophic earthquake. International journal of disaster risk reduction, 12, 234-254.
Koç, Ç., & Laporte, G. (2018). Vehicle routing with backhauls: Review and research perspectives. Computers & Operations Research, 91, 79-91.
Lahyani, R., Coelho, L. C., & Renaud, J. (2018). Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem. OR Spectrum, 40(1), 125-157.
Lahyani, R., Khemakhem, M., & Semet, F. (2015). Rich vehicle routing problems: From a taxonomy to a definition. European Journal of Operational Research, 241(1), 1-14.
Li, H., Lv, T., & Lu, Y. (2016). The combination truck routing problem: a survey. Procedia engineering, 137, 639-648.
Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. (2014). Survey of green vehicle routing problem: past and future trends. Expert systems with applications, 41(4), 1118-1138.
Maden, W., Eglese, R., & Black, D. (2010). Vehicle routing and scheduling with time-varying data: A case study. Journal of the Operational Research Society, 61(3), 515-522.
Marinakis, Y., & Marinaki, M. (2014). A bumble bees mating optimization algorithm for the open vehicle routing problem. Swarm and Evolutionary Computation, 15, 80-94.
Montoya-Torres, J. R., Franco, J. L., Isaza, S. N., Jiménez, H. F., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115-129.
Murray, C. C., & Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109.
Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013). A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1), 1-11.
Rosenfeld, A. (2019). Are drivers ready for traffic enforcement drones? Accident Analysis & Prevention, 122, 199-206.
Wang, X., Poikonen, S., & Golden, B. (2017). The vehicle routing problem with drones: several worst-case results. Optimization Letters, 11(4), 679-697.
Watkins, S., Burry, J., Mohamed, A., Marino, M., Prudden, S., Fisher, A., . . . Clothier, R. (2019). Ten questions concerning the use of drones in urban environments. Building and Environment, 106458.
Yurek, E. E., & Ozmutlu, H. C. (2018). A decomposition-based iterative optimization algorithm for traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 91, 249-262.

論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2025-06-18起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2025-06-18起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw