Joint Multi-Vehicle Routing and Multi-Drone Scheduling for a Hybrid Drone-Assisted Last-Mile Delivery System in Smart Cities

Drone-assisted last-mile delivery is adopted in smart cities to enhance the logistics service performance in terms of reducing the delivery time and cost while improving the user satisfaction. General vehicles without on-board drones and advanced vehicles equipped with multiple drones are simultaneously scheduled to perform the delivery tasks. There exists a hybrid multi-vehicle routing problem with multi-drones (HMVRPMD) that has not been well investigated in the previous works. Particularly, we take into account sufficient real-world considerations on the vehicle, drone and customer sides to make our problem more applicable. We design the optimal routing for two kinds of the vehicles, the optimal launch locations where the drones depart from the associated vehicles, and the optimal sequence of locations for the drones to visit multiple customers in each flight. We first evaluate the user satisfaction of a customer with respect to different package arrival time, according to the time window constraint, and then introduce a penalty cost function to calculate the accumulated loss in the total user satisfaction. We aim to minimize the weight sum of the penalty cost and total delivery cost of all employed vehicles and drones. To address the HMVRPMD, we present a bee-foraging learning particle swarm optimization algorithm with a comprehensive local search strategy. We particularly design the encoding and decoding strategies to efficiently cope with the route segmentation problem according to the vehicle types and the number of drones carried. Furthermore, we adopt the comprehensive local search strategy mixed with three kinds of neighbour search operations to enhance the search ability of the algorithm. Finally, extensive experimental results demonstrate that compared with the baseline algorithms, our algorithm has great advantages in both the convergence speed and algorithm accuracy.