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.