A Survey of Truck–Drone Routing Problem: Literature Review and Research Prospects

doi:10.1007/s40305-021-00383-4

Abstract

Abstract: The vehicle routing problem (VRP) has been an important research topic in operations research for decades. The major applications of the VRP arise in transportation, especially the last-mile delivery. In recent years, a growing number of logistic companies introduce drones or unmanned aerial vehicles in the delivery operations. Therefore, the truck-drone routing problem (TDRP), where trucks and drones are scheduled and coordinated to serve customers, vitalizes a new research stream in the literature. In this paper, we provide a comprehensive review on the TDRP. First, two basic models for the traveling salesman problem with drones and vehicle routing problem with drones are presented. Second, researches devoted to the TDRP are classified according to their addressed constraints and features. Third, prevalent algorithms that have been widely used in the existing literature are reviewed and described. Last, potential research opportunities are identified for future study.

Key words: Drone, Unmanned aerial vehicle, Truck-drone routing, Traveling salesman routing, Vehicle routing

CLC Number:

90B06

Yi-Jing Liang, Zhi-Xing Luo. A Survey of Truck–Drone Routing Problem: Literature Review and Research Prospects[J]. Journal of the Operations Research Society of China, 2022, 10(2): 343-377.

TrendMD

References

[1] Dukowitz, Z.:What types of drones are there? A guide to all the different drone types on the market. https://uavcoach.com/types-of-drones (2019)
[2] Otto, A., Agatz, N., Campbell, J., Golden, B., Pesch, E.:Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones:a survey. Networks 72(4), 411-458(2018)
[3] Agatz, N., Bouman, P., Schmidt, M.:Optimization approaches for the traveling salesman problem with drone. Transp. Sci. 52(4), 965-981(2018)
[4] Liu, Y., Liu, Z., Shi, J., Wu, G., Pedrycz, W.:Two-echelon routing problem for parcel delivery by cooperated truck and drone. IEEE Trans. Syst Man Cybern. Syst. (2020)
[5] JD. Jd.com's drone delivery program takes flight in rural china. https://corporate.jd.com/whatIsNewDetail?contentCode=6IhXLeeSAFLjLLlyuZatDA%3D%3D, 2016
[6] Laporte, G.:Fifty years of vehicle routing. Transp. Sci. 43(4), 408-416(2009)
[7] Vidal, T., Laporte, G., Matl, P.:A concise guide to existing and emerging vehicle routing problem variants. Eur. J. Oper. Res. 286, 401-416(2019)
[8] Dantzig, G.B., Ramser, J.H.:The truck dispatching problem. Manag. Sci. 6(1), 80-91(1959)
[9] Murray, C.C., Chu, A.G.:The flying sidekick traveling salesman problem:optimization of droneassisted parcel delivery. Transp. Res. Part C Emerg. Technol. 54, 86-109(2015)
[10] Savuran, H., Karakaya, M.:Efficient route planning for an unmanned air vehicle deployed on a moving carrier. Soft Comput. 20(7), 2905-2920(2016)
[11] Ferrandez, S.M., Harbison, T., Weber, T., Sturges, R., Rich, R.:Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. J. Ind. Eng. Manag. (JIEM) 9(2), 374-388(2016)
[12] Carlsson, J.G., Song, S.:Coordinated logistics with a truck and a drone. Manag. Sci. 64(9), 4052-4069(2018)
[13] Luo, Z., Liu, Z., Shi, J.:A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle. Sensors 17(5), 1144(2017)
[14] Poikonen, S., Wang, X., Golden, B.:The vehicle routing problem with drones:extended models and connections. Networks 70(1), 34-43(2017)
[15] Wang, X., Poikonen, S., Golden, B.:The vehicle routing problem with drones:several worst-case results. Optim. Lett. 11(4), 679-697(2017)
[16] Schermer, D., Moeini, M., Wendt, O.:A matheuristic for the vehicle routing problem with drones and its variants. Transp. Res. Part C Emerg. Technol. 106, 166-204(2019)
[17] Wang, Z., Sheu, J.-B.:Vehicle routing problem with drones. Transp. Res. Part B Methodol. 122, 350-364(2019)
[18] Sacramento, D., Pisinger, D., Ropke, S.:An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transp. Res. Part C Emerg. Technol. 102, 289-315(2019)
[19] Khoufi, I., Laouiti, A., Adjih, C.:A survey of recent extended variants of the traveling salesman and vehicle routing problems for unmanned aerial vehicles. Drones 3(3), 66(2019)
[20] Chung, S.H., Sah, B., Lee, J.:Optimization for drone and drone-truck combined operations:a review of the state of the art and future directions. Comput. Oper. Res. 123, 105004(2020)
[21] Baldacci, R., Battarra, M., Vigo, D.:Routing a Heterogeneous Fleet of Vehicles. The Vehicle Routing Problem:Latest Advances and New Challenges, pp. 3-27. Springer, Berlin (2008)
[22] Ha, Q.M., Deville, Y., Pham, Q.D., Ha, M.H.:On the min-cost traveling salesman problem with drone. Transp. Res. Part C Emerg. Technol. 86, 597-621(2018)
[23] Rich, R.:Inverting the truck-drone network problem to find best case configuration. Adv. Oper. Res. 2020, (2020)
[24] Roberti, R., Ruthmair, M.:Exact methods for the traveling salesman problem with drone. Optim. Online 55, 315-335(2019)
[25] Gonzalez-R, P.L., Canca, D., Andrade-Pineda, J.L., Calle, M., Leon-Blanco, J.M.:Truck-drone team logistics:a heuristic approach to multi-drop route planning. Transp. Res. Part C Emerg. Technol. 114, 657-680(2020)
[26] Schermer, D., Moeini, M., Wendt, O.:A branch-and-cut approach and alternative formulations for the traveling salesman problem with drone. Networks 76, 164-186(2020)
[27] Liu, J., Guan, Z., Xie, X.:Truck and drone in tandem route scheduling under sparse demand distribution. In:20188th International Conference on Logistics, Informatics and Service Sciences (LISS), IEEE, pp. 1-6, (2018)
[28] Dell'Amico, M., Montemanni, R., Novellani, S.:Drone-assisted deliveries:new formulations for the flying sidekick traveling salesman problem. Optim. Lett. 15, 1-32(2019)
[29] Murray, C.C., Raj, R.:The multiple flying sidekicks traveling salesman problem:parcel delivery with multiple drones. Transp. Res. Part C Emerg. Technol. 110, 368-398(2020)
[30] Poikonen, S., Golden, B.:Multi-visit drone routing problem. Comput. Oper. Res. 113, 104802(2020)
[31] Salama, M., Srinivas, S.:Joint optimization of customer location clustering and drone-based routing for last-mile deliveries. Transp. Res. Part C Emerg. Technol. 114, 620-642(2020)
[32] Karak, A., Abdelghany, K.:The hybrid vehicle-drone routing problem for pick-up and delivery services. Transp. Res. Part C Emerg. Technol. 102, 427-449(2019)
[33] Liu, Y., Luo, Z., Liu, Z., Shi, J., Cheng, G.:Cooperative routing problem for ground vehicle and unmanned aerial vehicle:the application on intelligence, surveillance, and reconnaissance missions. IEEE Access 7, 63504-63518(2019)
[34] Jeong, H.Y., Song, B.D., Lee, S.:Truck-drone hybrid delivery routing:payload-energy dependency and no-fly zones. Int. J. Prod. Econ. 214, 220-233(2019)
[35] FAA. No drone zone. https://www.faa.gov/UAS/resources/community_engagement/no_drone_zone (2019)
[36] Schermer, D., Moeini, M., Wendt, O.:A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations. Comput. Oper. Res. 109, 134-158(2019)
[37] Wang, D., Peng, H., Jingxuan, D., Zhou, P., Deng, T., Menglan, H.:Routing and scheduling for hybrid truck-drone collaborative parcel delivery with independent and truck-carried drones. IEEE Internet Things J. 6(6), 10483-10495(2019)
[38] Huang, H., Savkin, A.V., Huang, C.:Scheduling of a parcel delivery system consisting of an aerial drone interacting with public transportation vehicles. Sensors 20(7), 2045(2020)
[39] Kitjacharoenchai, P., Min, B.C., Lee, S.:Two echelon vehicle routing problem with drones in last mile delivery. Int. J. Prod. Econ. 225, 107598(2020)
[40] Faiz, T.I., Vogiatzis, C. et al.:Robust two echelon vehicle and drone routing for post disaster humanitarian operations. arXiv preprint arXiv:2001.06456(2020)
[41] Li, H., Wang, H., Chen, J., Bai, M.:Two-echelon vehicle routing problem with time windows and mobile satellites. Transp. Res. Part B Methodol. 138, 179-201(2020)
[42] Bakir, I., Tiniç, G.:Optimizing drone-assisted last-mile deliveries:The vehicle routing problem with flexible drones. (2020)
[43] Ulmer, M.W., Thomas, B.W.:Same-day delivery with heterogeneous fleets of drones and vehicles. Networks 72(4), 475-505(2018)
[44] Popovic, D., Kovac, M., Bjelic, N.:A MIQP model for solving the vehicle routing problem with drones. (2019)
[45] Wikarek, J., Sitek, P., Zawarczynski, L.:An integer programming model for the capacitated vehicle routing problem with drones. In:International Conference on Computational Collective Intelligence. Springer, pp. 511-520(2019)
[46] Pugliese, L.D.P., Guerriero, F.:Last-mile deliveries by using drones and classical vehicles. In:International Conference on Optimization and Decision Science. Springer, pp. 557-565(2017)
[47] Kim, M., Matson, E.T.:A cost-optimization model in multi-agent system routing for drone delivery. In:International Conference on Practical Applications of Agents and Multi-Agent Systems. Springer, pp. 40-51(2017)
[48] Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J.M.A., Brunese, P.A.:Multiple traveling salesman problem with drones:mathematical model and heuristic approach. Comput. Ind. Eng. 129, 14-30(2019)
[49] Tavana, M., Khalili-Damghani, K., Santos-Arteaga, F.J., Zandi, M.H.:Drone shipping versus truck delivery in a cross-docking system with multiple fleets and products. Expert Syst. Appl. 72, 93-107(2017)
[50] Ham, A.M.:Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming. Transp. Res. Part C Emerg. Technol. 91, 1-14(2018)
[51] Dayarian, I., Savelsbergh, M., Clarke, J.-P.:Same-day delivery with drone resupply. Transp. Sci. 54(1), 229-249(2020)
[52] Pina-Pardo, J.C., Silva, D.F., Smith, A.E.:The traveling salesman problem with release dates and drone resupply. Comput. Oper. Res. 129, 105170(2021)
[53] Peng, K., Jingxuan, D., Fang, L., Sun, Q., Dong, Y., Zhou, P., Menglan, H.:A hybrid genetic algorithm on routing and scheduling for vehicle-assisted multi-drone parcel delivery. IEEE Access 7, 49191-49200(2019)
[54] Chiang, W.C., Li, Y., Shang, J., Urban, T.L.:Impact of drone delivery on sustainability and cost:realizing the UAV potential through vehicle routing optimization. Appl. Energy 242, 1164-1175(2019)
[55] Das, D.N., Sewani, R., Wang, J., Tiwari, M.K.:Synchronized truck and drone routing in package delivery logistics. IEEE Trans. Intell. Transp. Syst. (2020)
[56] Deng, P., Amirjamshidi, G., Roorda, M.:A vehicle routing problem with movement synchronization of drones, sidewalk robots, or foot-walkers. Transp. Res. Proc. 46, 29-36(2020)
[57] Marinelli, M., Caggiani, L., Ottomanelli, M., Dell'Orco, M.:En route truck-drone parcel delivery for optimal vehicle routing strategies. IET Intell. Trans. Syst. 12(4), 253-261(2017)
[58] Luo, Z., Liu, Z., Shi, J., Wang, Q., Zhou, T., Liu, Y.:The mathematical modeling of the two-echelon ground vehicle and its mounted unmanned aerial vehicle cooperated routing problem. In:2018 IEEE Intelligent Vehicles Symposium (IV). IEEE, pp. 1163-1170(2018)
[59] Chang, Y.S., Lee, H.J.:Optimal delivery routing with wider drone-delivery areas along a shorter truck-route. Expert Syst. Appl. 104, 307-317(2018)
[60] Yurek, E.E., Ozmutlu, H.C.:A decomposition-based iterative optimization algorithm for traveling salesman problem with drone. Transp. Res. Part C Emerg. Technol. 91, 249-262(2018)
[61] Peng, K., Liu, W., Sun, Q., Ma, X., Menglan, H., Wang, D., Liu, J.:Wide-area vehicle-drone cooperative sensing:opportunities and approaches. IEEE Access 7, 1818-1828(2018)
[62] Schermer,D.,Moeini,M.,Wendt,O.:.Algorithmsforsolvingthevehicleroutingproblemwithdrones. In:Asian Conference on Intelligent Information and Database Systems. Springer, pp. 352-361, (2018)
[63] Bouman, P., Agatz, N., Schmidt, M.:Dynamic programming approaches for the traveling salesman problem with drone. Networks 72(4), 528-542(2018)
[64] Cri? san, G.C., Nechita, E.:On a cooperative truck-and-drone delivery system. Proc. Computer Sci. 159, 38-47(2019)
[65] Kim, S., Moon, I.:Traveling salesman problem with a drone station. IEEE Trans. Syst. Man Cybern. Syst. 49(1), 42-52(2018)
[66] Poikonen, S., Golden, B., Wasil, E.A.:A branch-and-bound approach to the traveling salesman problem with a drone. INFORMS J. Comput. 31(2), 335-346(2019)
[67] Kitjacharoenchai, P., Lee, S.:Vehicle routing problem with drones for last mile delivery. Proc. Manuf. 39, 314-324(2019)
[68] Tang, Z., van Hoeve, W.J., Shaw, P.:A study on the traveling salesman problem with a drone. In:InternationalConferenceonIntegrationofConstraintProgramming,ArtificialIntelligence,andOperations Research. Springer, pp. 557-564(2019)
[69] Menglan, H., Liu, W., Peng, K., Ma, X., Cheng, W., Liu, J., Li, B.:Joint routing and scheduling for vehicle-assisted multidrone surveillance. IEEE Internet Things J. 6(2), 1781-1790(2018)
[70] Poikonen, S., Golden, B.:The mothership and drone routing problem. INFORMS J. Comput. 32(2), 249-262(2020)
[71] Ha, Q.M., Deville, Y., Pham, Q.D., Hà, M.H.:A hybrid genetic algorithm for the traveling salesman problem with drone. J. Heuristics 26(2), 219-247(2020)
[72] Vásquez, S.A., Angulo, G., Klapp, M.A.:An exact solution method for the tsp with drone based on decomposition. Comput. Oper. Res. 127, 105127(2021)
[73] Tamke, F., Buscher, U.:A branch-and-cut algorithm for the vehicle routing problem with drones. Transp. Res. Part B Methodol. 144, 174-203(2021)
[74] Boccia, M., Masone, A., Sforza, A., Sterle, C.:A column-and-row generation approach for the flying sidekick travelling salesman problem. Transp. Res. Part C Emerg. Technol. 124, 102913(2021)
[75] Bouman, P., Agatz, N., Schmidt, M.:Instances for the tsp with drone (and some solutions) (2018b)
[76] Agatz, N.A.H., Schmidt, M.E., Bouman, P.C.:Tsp-d-instances:Instances and some solutions. https://zenodo.org/record/35042#.Xy3-9CgzY2w (2015)
[77] Heidelberg,U.:Tsplib.http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/XMLTSPLIB/instances/, 1995
[78] Reinelt, G.:Tsplib:a traveling salesman problem library. ORSA J. Comput. 3(4), 376-384(1991)
[79] Augerat, P., Christofides, E.:VRP problem instances 1995(1995)
[80] Solomon, M.M.:Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254-265(1987)
[81] Hahsler, M.:Traveling salesperson problem (TSP). https://www.rdocumentation.org/packages/TSP/versions/1.1-10(2020)
[82] Zenodo. Vehicle routing problem with drones instances. https://zenodo.org/record/1403150?fbclid=IwAR366Ezt5p-ax3Yf5P7uKHXkjh9pzdD4U-g8UKZI4gMprN6VKhFfFUpvIpA#.XJYfXdR6St9(2018)
[83] Archetti, C., Feillet, D., Mor, A., Speranza, M.G.:An iterated local search for the traveling salesman problem with release dates and completion time minimization. Comput. Oper. Res. 98, 24-37(2018)