臺灣博碩士論文加值系統

無人機或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