跳到主要內容

臺灣博碩士論文加值系統

(44.200.86.95) 您好!臺灣時間:2024/05/20 07:04
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:白健良
研究生(外文):Evan Edbert
論文名稱:Applying NSGA-II algorithm to vehicle routing problem with drone considering makespan and carbon emission
論文名稱(外文):Applying NSGA-II algorithm to vehicle routing problem with drone considering makespan and carbon emission
指導教授:郭人介郭人介引用關係
指導教授(外文):Ren-Jieh Kuo
口試委員:王孔政林希偉
口試委員(外文):Kung-Jeng WangShi-Woei Lin
口試日期:2021-06-02
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:工業管理系
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2021
畢業學年度:109
語文別:英文
論文頁數:53
中文關鍵詞:具無人機之車輛途程問題排程總製造時間碳排放量非支配順序基因演算法II
外文關鍵詞:Vehicle routing problem with droneMakespanCarbon emissionNSGA-II
相關次數:
  • 被引用被引用:0
  • 點閱點閱:106
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
無人機或UAV(無人駕駛飛行器)是一種不用人工操作即可直接飛行的飛行器,現今許多公司嘗試使用無人機來發展他們的物流系統,預計未來幾年運用無人機來運送貨物將會有顯著的成長。雖然無人機運送的速度已經廣為人知,但是其可行性仍存在疑問,仍需近一步的研究,儘管使用無人機來送貨在經濟上是有利的,但在環境方面的效益仍有待檢驗。
本研究提出無人機之車輛途程問題模型,此模型具有兩個目標,即最小化排程總製造時間和總運輸路線的碳排放量。在此模型中,每輛卡車都配備一架無人機並協助運送貨物,本研究目的是提出具有兩個目標的無人機之車輛途程問題的數學模型,然後用多目標基因演算法求解不同規模的問題,並使用效能指標(hypervolume, spacing)去檢查結果的優良。結果顯示,使用此演算法可以產生較好的效能指標,透過顯著性檢定結果顯示,相比於沒有使用無人機,使用無人機減少排程總製造時間和總運輸路線的碳排放量是有顯著差異的。
Drone or UAV (unmanned aerial vehicles) is an aerial vehicle capable of sustained flight without the need for a human operator onboard. Nowadays, many companies tried to develop their own delivery system with drones and the usage of drones in delivery is expected to grow significantly in the next few years. Although the speediness of the drone delivery is known already, but the feasibility of it is still questioned and still need to be studied further. Even though using drone for delivery is beneficial in economic point of view, the benefit in environmental side still needs to be tested.
In this study, a vehicle routing problem with drone (VRPD) model is proposed with two objectives to minimize the makespan and carbon emission of the delivery route. In this model, each truck is equipped with one drone to do collaboration in delivery. The objectives of this study are to propose the mathematical formulation for the VRPD with two objectives, solve it with the NSGA-II algorithm, and test the proposed algorithm with different-scale problems. Hypervolume and spacing are employed to check the quality of the solutions produced by the algorithm. The result shows that the algorithm can produce quite good result with good hypervolume and spacing values. The benefits of using drone to reduce makespan and carbon emission are tested through significance test. The result shows that the difference when using drone is significant.
CONTENTS

ABSTRACT I
摘要 II
ACKNOWLEDGEMENT III
CONTENTS IV
LIST OF FIGURES VI
LIST OF TABLES VII
CHAPTER 1 INTRODUCTION 1
1.1 Research background and motivation 1
1.2 Research objectives 1
1.3 Research constraints and scope 2
1.4 Thesis organization 2
CHAPTER 2 LITERATURE REVIEW 4
2.1 Vehicle routing problem 4
2.1.1 Vehicle routing problem with drone 4
2.1.2 Minimize makespan vehicle routing problem 5
2.1.3 Minimize carbon emission vehicle routing problem 6
2.1.4 Vehicle routing problem with time window 6
2.1.5 Vehicle routing problem with service level 7
2.1.6 Multi-objective vehicle routing problem 8
2.2 Multi-objective evolutionary algorithm 8
2.2.1 Non-dominated sorting genetic algorithm 9
CHAPTER 3 METHODOLOGY 11
3.1 Mathematical formulation for the VRPD 11
3.2 Notations 11
3.3 Mathematical formulation 14
3.4 NSGA-II for multi-objective VRPD 18
3.5 Performance evaluation 23
CHAPTER 4 EXPERIMENTAL RESULTS 25
4.1 Test instances 25
4.2 Experiment and results 26
4.3 Time complexity 39
CHAPTER 5 CONCLUSIONS AND FUTURE RESEARCH 40
5.1 Conclusions 40
5.2 Contributions 40
5.3 Future research 41
REFERENCE 42
REFERENCE

Andrea, R. D. (2014). Can drones deliver. IEEE Transactions on Automation Science and Engineering 72, (4), 647-648.
Benjamin, A., & Beasley, J. (2013). Metaheuristics with disposal facility positioning for the waste collection vehicle routing problem with time windows. Optimization Letters 7, 1433-1449.
Bento, M. d. (2008). Unmanned Aerial Vehicles An Overview. Inside GNSS, 54-61.
Boysen, N., Briskorn, D., Fedtke, S., & Schwerdfeger, S. (2018). Drone Delivery from Trucks: Drone Scheduling for Given Truck Routes. Networks: An International Journal 72, (4), 506-527.
Bulhões, T., Minh, H., Martinelli, R., & Vidal, T. (2018). The vehicle routing problem with service level constraints. European Journal of Operational Research 265, (2), 544-558.
Campbell, J. F., Sweeney II, D. C., & Zhang, J. (2017). Strategic design for delivery with trucks and drones. Unniversity of Missouri, St. Louis.
Chiang, W.-C., Li, Y., Shang, J., & Urban, T. L. (2019). Impact of drone delivery on sustainability and cost: realizing the uav potential through vehicle routing optimization. Applied Energy 242, 1164-1175.
Cordeau, J., Desaulniers, G., Desroriers, J., Solomon, M. M., & Soumis, F. (1999). The vehicle routing problem with time windows. Les Cahiers du GERAD G-99-13, 1-38.
Daknama, R., & Kraus, E. (2017). Vehicle routing with drones. Munich: arXiv preprint arXiv:1705.06431.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6, (1), 1-140.
Deb, K., Pratap, A., Argawal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, (2), 182-197.
Drugan, M. M., & Thierens, D. (2010). Path-guided mutation for stochastic pareto local search algorithms. Parallel Problem Solving from Nature - PPSN XI, Part I, 485-495.
Elabib, I., Basir, O. A., & Calamai, P. (2002). An experimental study of a simple ant colony system for the vehicle routing problem with time windows. International Workshop on Ant Algorithms ANTS, Lecture Notes in Computer Science 2463, 53-64.
Erdogan, S., & Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E 48, (1), 100-114.
Figliozzi, M. A. (2017). Lifecycle modeling and assessment of unmanned aerial vehicles (drones) CO2e emissions. Transportation Research Part D 57, 251-261.
Fleischmann, B. (1990). The vehicle routing problem with multiple use of the vehicles. Universität Hamburg, Fachbereich Wirtschaftswissenschaften.
Ghoseiri, K., & Ghannadpour, S. F. (2010). Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm. Applied Soft Computing 10, (4), 1096-1107.
GmbH, D. I. (2014, September 24). DHL Parcelcopter Launches Initial Operations for Research Purposes. Retrieved from https://www.dhl.com/en/press/releases/releases_2014/group/dhl_parcelcopter_launches_initial_operations_for_research_purposes.html.
Han, Y. Q., Li, J. Q., Liu, Z., Liu, C., & Tian, J. (2020). Metaheuristic algorithm for solving the multi-objective vehicle routing problem with time window and drones. International Journal of Advanced Robotic Systems 17, (2), 1-14.
Ho, S. C., & Haugland, D. (2004). A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers & Operations Research 31, (12), 1947-1964.
Ishibuchi, H., Imada, R., Setoguchi, Y., & Nojima, Y. (2018). How to specify a reference point in hypervolume calculation for fair performance comparison. Evolutionary Computation 26, (3), 411-440.
Jozefowiez, N., Semet, F., & Talbi, E.-G. (2008). Multi-objective vehicle routing problems. European Journal of Operational Research 189, (2), 293-309.
Kara, I., Kara, B. Y., & Yetis, M. (2007). Energy Minimizing Vehicle Routing Problem. International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science 4616, 62-71.
Kim, B.-I., Kim, S., & Sahoo, S. (2006). Waste collection vehicle routing problem with time windows. Computers & Operations Research 33, (12), 3624-3642.
Kitjacharoenchai, P., Min, B. C., & Lee, S. (2020). Two echelon vehicle routing problem with drones in last mile delivery. International Journal of Production Economics 225, 1-14.
Laporte, G. (1992). The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research 59, (3), 345-358.
Macrina, G., Pugliese, L. D., Guerriero, F., & Laporte, G. (2020). Drone-aided routing: a literature review. Transportation Research Part C 120, 1-25.
Molina, J. C., Eguia, I., Racero, J., & Guerrero, F. (2014). Multi-objective vehicle routing problem with cost and emission functions. Social and Behavioral Science 160, 254-263.
Montoya, A., Gueret, C., Mendoza, J. E., & Villegas, J. G. (2016). A multi-space sampling heuristic for the green vehicle routing problem. Transportation Research Part C 70, 113-128.
Murray, C. C., & Chu, A. G. (2015). The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transportation Research Part C 54, 86-109.
Nahum, O. E., Hadas, Y., Spiegel, U., & Cohen, R. (2014). The Real-Time Multi-Objective Vehicle Routing Problem – Case Study: Information Availability and the Quality of the Results. 93rd TRB Annual Meeting, 1-21.
Poikonen, S., & Golden, B. (2020). Multi-visit drone routing problem. Computers and Operations Research 113, 1-10.
Poikonen, S., Golden, B., & Wasil, E. A. (2019). A branch-and-bound approach to the traveling salesman problem with a drone. INFORMS Journal on Computing 31, (2), 335-346.
Poikonen, S., Wang, X., & Golden, B. (2017). The vehicle routing problem with drones: extended models and connections. NETWORKS 70, (1), 34-43.
Pollet, B. G., Staffel, I., & Shang, J. L. (2012). Current status of hybrid, battery and fuel cell electric vehicles: from electrochemistry to market prospects. Electrochimica Acta 84, 235-249.
Sacramento, D., Pisinger, D., & Ropke, S. (2019). An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C 102, 289-315.
Schaffer, J. (1985). Multiple objective optimization with vector evaluated genetic algorithms. Proceedings of the first International Conference on Genetic Algorithm and Their Applications, 93-100.
Schermer, D., Moeini, M., & Wendt, O. (2019). A matheuristic for the vehicle routing problem with drones and its variants. Transportation Research Part C 106, 166-204.
Schott, J. R. (1995). Fault Tolerant Design using Single and Multicriteria Genetic Algorithm Optimization. Massachusetts Institute of Technology.
Srinivas, N., & Deb, K. (1994). Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation 2, (3), 221-248.
Stewart, J. (2014, August 28). Google tests drone deliveries in Project Wing trials. Retrieved from BBC News: https://www.bbc.com/news/technology-28964260.
Tang, J., Pan, Z., Fung, R. Y., & Lau, H. (2009). Vehicle routing problem with fuzzy time windows. Fuzzy Sets and Systems 160, (5), 683-695.
Veldhuizen, D. A., & Lamont, G. B. (2000). On Measuring Multiobjective Evolutionary Algorithm Performance. Proceeding of the 2000 Congress on Evolutionary Competition, 204-211.
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2015). Time-window relaxations in vehicle routing heuristics. Journal of Heuristics 21, 329-358.
Wang, X., Poikonen, S., & Golden, B. (2017). The vehicle routing problem with drones: several worst-case results. Optimization Letters 11, 679-697.
Wohlsen, M. (2014, October 6). WIRED. Retrieved from https://www.wired.com/2014/06/the-next-big-thing-you-missed-delivery-drones-launched-from-trucks-are-the-future-of-shipping/
Yu, M., Nagarajan, V., & Shen, S. (2017). Minimum Makespan Vehicle Routing Problem with Compatibility Constraints. International Conference on the Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, 244-253. Padua: Springer.
Zhang, H., Zhang, Q., Ma, L., Zhang, Z., & Liu, Y. (2019). A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows. Information Sciences 490, 166-190.
Zhang, J., Lam, W. H., & Chen, B. Y. (2013). A stochastic vehicle routing problem with travel time uncertainty: trade-off between cost and customer service. Network and Spatial Economics 13, 471-496002E
電子全文 電子全文(網際網路公開日期:20260908)
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top