关键词: 时间窗, 电动车-无人机, 协同配送, 路径优化问题, 自适应大邻域搜索算法

Abstract:

With national efforts to achieve carbon neutrality goals， electric vehicles have gradually become the preferred choice for logistics enterprises. However， electric vehicles require planning additional charging routes during delivery， which results in high logistics costs. To reduce the logistics cost of the electric vehicle delivery system， integration of drones is considered into the existing delivery system， and the vehicle routing problem with time windows is investigated under the collaborative delivery mode of electric vehicle-drone. The primary goal is to determine the optimal routes for both electric vehicles and drones to minimize total costs while satisfying the customer's time window requirements. During the delivery process in this mode， electric vehicles may require recharging at charging stations due to their limited battery capacity， when drones are loaded with batteries and goods， launched from， and recovered to the depot. To solve this problem， a mixed-integer programming-based mathematical optimization model is constructed. Then， an extended adaptive large neighborhood search algorithm （EALNS） is proposed， which integrates a construction heuristic algorithm to quickly obtain the initial feasible solution. In the algorithm， new insertion criterion and removal criterion of charging station are incorporated to satisfy the battery capacity constraint， and a shortest path removal operator is designed to accelerate the algorithmic convergence. Finally， simulation experiments are conducted to demonstrate the effectiveness of the proposed model and algorithm. The experimental results show that： （1） Compared with the Gurobi solver and ALNS algorithm， the EALNS algorithm obtains a better solution with a shorter running time in solving the proposed model； （2） Compared to existing delivery systems， integrating drones into the delivery systems can yield cost savings ranging from 1.07% to 19.50%， with an average saving of 5.97%； and （3） The changes in model parameters affect the cost of the solution. Specifically， the costs of the solution decrease as the load capacity and flight duration of drones increase， or as the load capacity and battery capacity of electric vehicles increase. Furthermore， as the customer's time window constraints are tightened， the cost of the solution increases. In conclusion， a new variant of the electric vehicle routing problem with time windows is presented， verifying that integrating drones into electric vehicle delivery systems can significantly reduce logistics costs， and the proposed EALNS algorithm is effective in solving this problem.

Key words: time windows, electric vehicle-drone, collaborative delivery, routing problem, adaptive large neighborhood search algorithm