研究生: |
Nguyen Minh Hien Nguyen Minh Hien |
---|---|
論文名稱: |
Heterogeneous Fleet Vehicle Routing Problem with Multiple Drones Heterogeneous Fleet Vehicle Routing Problem with Multiple Drones |
指導教授: |
喻奉天
Vincent F. Yu |
口試委員: |
Vincent F. Yu
Vincent F. Yu Yu-Chung Tsao Yu-Chung Tsao Cheng-Hung Wu Cheng-Hung Wu |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2018 |
畢業學年度: | 106 |
語文別: | 英文 |
論文頁數: | 44 |
中文關鍵詞: | Heterogeneous fleet vehicle routing problem (HFVRP) 、Multiple drones/UAV 、Traveling salesman problem (TSP) 、Mixed integer linear programming (MILP) 、Heuristic 、Greedy simulated annealing search procedure (GSASP) |
外文關鍵詞: | Heterogeneous fleet vehicle routing problem (HFVRP), Multiple drones/UAV, Traveling salesman problem (TSP), Mixed integer linear programming (MILP), Heuristic, Greedy simulated annealing search procedure (GSASP) |
相關次數: | 點閱:674 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
Unmanned aerial vehicles (UAV), or drones have attracted the interest of several large organizations in recent years such as Amazon, DHL, Parcel copter or Google, etc. Although drone has high potential to effectively improve the performance of cost and time in last-mile delivery, not too much works has put efforts on it. Furthermore, the most current research just assume that a vehicle only employs a single drone for fast delivery, it has put a significant limitation on application of drone in reality. In order to extend the flexibility, this research studies the case of vehicle routing problems for non-homogeneous fleets where each vehicle can carry multi drones for delivery. In this study, several factors such as completion time and energy consumption are considered to make the approach more asymptotic to real case. In addition, a greedy simulated annealing search procedure (GSASP) heuristic for finding solutions to practical scenarios is also developed to assist drone delivery practitioners.
Unmanned aerial vehicles (UAV), or drones have attracted the interest of several large organizations in recent years such as Amazon, DHL, Parcel copter or Google, etc. Although drone has high potential to effectively improve the performance of cost and time in last-mile delivery, not too much works has put efforts on it. Furthermore, the most current research just assume that a vehicle only employs a single drone for fast delivery, it has put a significant limitation on application of drone in reality. In order to extend the flexibility, this research studies the case of vehicle routing problems for non-homogeneous fleets where each vehicle can carry multi drones for delivery. In this study, several factors such as completion time and energy consumption are considered to make the approach more asymptotic to real case. In addition, a greedy simulated annealing search procedure (GSASP) heuristic for finding solutions to practical scenarios is also developed to assist drone delivery practitioners.
Bettinelli, A., Ceselli, A. and Righini, G. (2011). A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies 19(5), 723-740.
Bryan, V. (2014). Drone delivery: DHL ‘parcelcopter’ flies to German isle
<http://www.reuters.com/article/2014/09/24/us-deutsche-post-drones idUSKCN0HJ1ED20140924>.
Coelho, B. N., Coelho, V. N., Coelho, I. M., Ochi, L. S., Haghnazar K, R., Zuidema, D., Lima, M. S. F. and da Costa, A. R. (2017). A multi-objective green UAV routing problem.
Computers & Operations Research 88, 306-315.
Ha, Q. M., Deville, Y., Pham, Q. D. and Ha, M. H. (2018). On the min-cost Traveling Salesman Problem with Drone. Transportation Research Part C: Emerging Technologies 86, 597-621.
Imran, A., Salhi, S. and Wassan, N. A. (2009). A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem. European Journal of Operational Research 197(2), 509-518.
Leung, S. C. H., Zhang, Z., Zhang, D., Hua, X. and Lim, M. K. (2013). A meta-heuristic
algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading
constraints. European Journal of Operational Research 225(2), 199-210.
Li, X., Tian, P. and Aneja, Y. P. (2010). An adaptive memory programming metaheuristic for the heterogeneous fixed fleet vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review 46(6), 1111-1127.
Murray, C. C. and 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.
Nicas, J. and Bensinger, G. (2015). Delivery drones hit bumps on path to doorstep.
Rose, C. (Dec. 2013) Amazon’s Jeff Bezos looks to the future. http://www.cbsnews.com/news/amazons-jeff-bezos-looks-to-the-future/.
Subramanian, A., Penna, P. H. V., Uchoa, E. and Ochi, L. S. (2012). A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem. European Journal of Operational
Research 221(2), 285-295.
Stern, J. (2013). Like Amazon, UPS Also Considering Using Unmanned Flying Vehicles
<http://abcnews.go.com/Technology/amazon-ups-drone-delivery options/story?id=21086160>.
Stewart, J. (Aug. 2014). Google Tests Drone Deliveries in Project Wing Trials, BBC, London, U.K. Online. Available: http://www.bbc.com/news/technology-28964260.
Tavana, M., Khalili-Damghani, K., Santos-Arteaga, F. J. and Zandi, M. (2017). Drone shipping versus truck delivery in a cross-docking system with multiple fleets and products. Expert Systems with Applications 72, 93-107.
Toth, P. and Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia.
Wang, X., Poikonen, S. and Golden, B. (2016). The vehicle routing problem with drones: several worst-case results. Optimization Letters 11(4), 679-697.