The Multi-visits Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery Service

doi:10.1007/s40305-023-00471-7

Abstract

Abstract: The development of convergent technology makes the drone expected to become a commercial delivery method for terminal logistics distribution. Although the industry has begun to experiment with the coordinated transportation of drones and vehicles, some limited assumptions have been made to reduce the complexity of synchronization. This paper studies the mathematical formulations and efficient solution methodologies for the multi-visits drone-vehicle routing problem with simultaneous pickup and delivery service (MDVRPSPD), whose objective is to minimize the distance traveled by drones and vehicles and the total number of drones used. To solve the MDVRPSPD problem, a three-stage solution method is designed. Firstly, the scalable K-means++ algorithm is used to determine the vehicle’s parking location, and we optimize the vehicle’s driving route by traveling salesman problem (TSP) modeling; then, the classic tabu search algorithm is extended to arrange the schedule of drones which consider multi-visits and simultaneous pickup and delivery service. Meanwhile, a set of extensive computational experiments are conducted to demonstrate the efficiency of developed heuristics and the superiority of drone-vehicle delivery system on delivery issues.

Key words: Pickup and delivery services, Vehicle routing, Drone routing, Mixed integer programming, K-means++, Tabu search

CLC Number:

Si Zhang, Lu Li. The Multi-visits Drone-Vehicle Routing Problem with Simultaneous Pickup and Delivery Service[J]. Journal of the Operations Research Society of China, 2024, 12(4): 965-995.

TrendMD

References

[1] Yuen, K.F., Wang, X.Q., Ng, L.T.W., Wong, Y.D.: An investigation of customers’ intention to use self-collection services for last-mile delivery. Transp. Policy. 66, 1-8(2018)
[2] Roy, S.K.: Transportation problem with multi-choice cost and demand and stochastic supply. J. Oper. Res. Soc. China 4(2), 193-204(2016)
[3] Aggarwal, S., Kumar, N.: Path planning techniques for unmanned aerial vehicles: a review, solutions, and challenges. Comput. Commun. 149, 270-299(2019)
[4] 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) (2019). https://doi.org/10.3390/drones3030066.
[5] 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). https://doi.org/10.1016/j.cor.2020.105004
[6] Dorling, K., Heinrichs, J., Messier, G.G., Magierowski, S.: Vehicle routing problems for drone delivery. IEEE Trans. Syst. Man Cybern. Syst. 47(1), 70-85(2018)
[7] Torabbeigi, M., Lim, G.J., Kim, S.J.: Drone delivery scheduling optimization considering payloadinduced battery consumption rates. J. Intell. Robot. Syst. 97(3-4), 471-487(2020)
[8] Cheng, C., Adulyasak, Y., Rousseau, L.M.: Drone routing with energy function: formulation and exact algorithm. Transp. Res. Part B Methodol. 139, 364-387(2020)
[9] Liu, Z.L., Sengupta, R., Kurzhanskiy, A.: A power consumptionmodel formulti-rotor small unmanned aircraft systems. In: International Conference on Unmanned Aircraft Systems, pp. 310-315(2017).
[10] 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)
[11] Agatz, N., Bouman, P., Schmidt, M.: Optimization approaches for the traveling salesman problem with drone. Transp. Sci. 52(4), 965-981(2018)
[12] Bouman, P., Agatz, N., Schmidt, M.: Dynamic programming approaches for the traveling salesman problem with drone. Networks 72(4), 528-542(2018)
[13] 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)
[14] Dell’Amico, M., Montemanni, R., Novellani, S.: Algorithms based on branch and bound for the flying sidekick traveling salesman problem. Omega 104, 102493(2021). https://doi.org/10.1016/j.omega.2021.1024931
[15] 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)
[16] Wang, Z., Sheu, J.B.: Vehicle routing problem with drones. Transp. Res. Part B Methodol. 122, 350-364(2019)
[17] 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)
[18] 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)
[19] Luo, Z.H., Poon, M., Zhang, Z.Z., Liu, Z., Lim, A.: The multi-visit traveling salesman problem with multi-drones. Transp. Res. Part C Emerg. Technol. 128, 103172(2021). https://doi.org/10.1016/j.trc.2021.103172
[20] 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. 9, 374-388(2016)
[21] 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)
[22] Yu, H., Solvang, W.D.: Improving the decision-making of reverse logistics network design part I: a MILP model under stochastic environment. Lecture Notes in Electrical Engineering, pp. 431-438(2018).
[23] Behmanesh, E., Pannek, J., Pannek, J.: Taguchi analysis for improving optimization of ontegrated forward/reverse logistics. J. Oper. Res. Soc. China (2022). https://doi.org/10.1007/s40305-021-00380-7
[24] Baniasadi, P., Foumani, M., Smith-Miles, K., Ejov, V.: A transformation technique for the clustered generalized traveling salesman problem with applications to logistics. Eur. J. Oper. Res. 285(2), 444-457(2020)
[25] Mac, Q.J.: Some methods for classification and analysis of multi variate observations. In: Proc of Berkeley Symposium on Mathematical Statistics and Probability, pp. 282-297(1967).
[26] Vovan, T., Nguyenhoang, Y., Danh, S.: An automatic fuzzy clustering algorithm for discrete elements. J. Oper. Res. Soc. China (2022). https://doi.org/10.1007/s40305-021-00388-z
[27] Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large scale traveling-salesman problem. Oper. Res. 2(4), 393-410(1954)
[28] Jain, A.K.: Data clustering: 50 years beyond K-means, pattern recognition letters. Comput. Sci. 31(8), 651-666(2010)
[29] Cui, X.L., Zhu, P.F., Yang, X., Li, K.Q., Ji, C.Q.: Optimized big data K-means clustering using MapReduce. J. Supercomput. 70(3), 1249-1259(2014)
[30] Arthur, D., Sergei, V.: K-means++: the advantages of careful seeding. Comput. Sci. (2007). https://doi.org/10.5555/1283383.1283494
[31] Wang, H.F., Chen, Y.Y.: A genetic algorithm for the simultaneous delivery and pickup problems with time window. Comput. Ind. Eng. 62(1), 84-95(2012)
[32] Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533-549(1986)
[33] Clarke, G., Wright, J.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12(4), 568-581(1964)
[34] Gendreau, M., Hertz, A., Laporte, G.: A tabu search heuristic for the vehicle routing problem. Manag. Sci. 40(10), 1276-1290(1994)
[35] Renaud, J., Laporte, G., Boctor, F.F.: A tabu search heuristic for the multi-depot vehicle routing problem. Comput. Oper. Res. 23(3), 229-235(1996)
[36] Gendreau, M., Laporte, G., Musaraganyi, C., Taillard, E.D.: A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Comput. Oper. Res. 26(12), 1153-1173(1999)
[37] Ho, S.C., Gendreau, M.: Path relinking for the vehicle routing problem. J. Heuristics 12(1-2), 55-72(2006)
[38] Xiong, H., Yan, H.L.: A three-phase tabu search heuristic for the split delivery vehicle routing problem. Syst. Eng. Theory Pract. 35(5), 1230-1235(2015)
[39] Lai, D.S.W., Demirag, O.C., Leung, J.M.Y.: A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transp. Res. Part E Logist. Transp. Rev. 86, 32-52(2016)
[40] Montane, F.A.T., Galvao, R.D.: A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Comput. Oper. Res. 33(3), 595-619(2006)
[41] Zachariadis, E.E., Tarantilis, C.D., Kiranoudis, C.T.: A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. Expert Syst. Appl. 36(2), 1070-1081(2009)
[42] Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254-265(1987)