Abstract: SUDVs are not suitable for long-distance delivery. To increase the scope of delivery services, the trucks can be matched with SUDVs to complete the “last mile delivery task”, which poses new challenges to the vehicle routing optimization problem. Considering the characteristics of the limited number of delivery vehicles, the urban transport with considerable package and the restrictions on truck parking, a large vehicle (LV)-SUDV routing optimization problem is proposed, by which SUDVs can be replenished by LVs. A mixed integer programming model is established with the objective of minimum total distance. In this mode, one LV carries multiple SUDVs for distribution, SUDVs deliver directly to the customer, and SUDVs can replenish goods at the LVs and perform multiple deliveries. Besides, a hybrid genetic large neighborhood search algorithm is designed for this model, and a large neighborhood search algorithm is added to optimize the individual based on the genetic algorithm. In the algorithm optimization process, first the path of the SUDV is optimized, and then the path of the LV optimized based on the path of the SUDVs. Numerical experiments show that for small-scale problems, the proposed algorithm takes up to 6% of the CPLEX solution time to obtain the optimal solution. On the modified Solomon data, the proposed algorithm has an average 95.5% advantage in calculation results compared with genetic algorithms, and an average 7.2% advantage in calculation results compared with large neighborhood search algorithms. Besides, the greater the amount of data, the greater the advantage of the calculation results.

Key words: small unmanned delivery vehicle (SUDV), multi-trip delivery, vehicle routing optimization, hybrid genetic algorithm large neighborhood search algorithm