考虑禁飞区与充电约束的电动汽车−无人机协同配送优化

    Electric Vehicle-Drone Cooperative Routing Optimization Considering No-Fly Zones and Charging Constraints

    • 摘要: 针对城市末端配送中电动汽车续航受限、客户时间窗、无人机禁飞区及车机发射回收同步等多重约束耦合导致的协同配送路径规划问题,研究考虑充电约束与禁飞区限制的电动汽车−多无人机协同配送优化问题。以系统总完工时间最小化为目标,构建融合车辆路径规划、无人机任务分配、充电站访问、客户时间窗、禁飞区规避及车机同步关系的混合整数规划模型,并在自适应大邻域搜索框架基础上,设计充电感知修复、基于车辆相邻行驶弧的无人机任务生成与优先分配以及局部搜索策略。基于Solomon C101算例开展数值实验。结果表明,在N6、N7和N8小规模算例中,改进ALNS算法所得完工时间均与完整枚举参考解一致;在15、20、25和30客户规模下,相较Basic-ALNS,平均完工时间分别降低1.26%、11.44%、8.45%和1.76%,其中15、20、25客户规模下的改进通过0.05显著性水平检验。在30客户规模下,改进ALNS的可行率达到60%,高于Basic-ALNS的30%。消融实验进一步表明,充电感知修复、无人机任务优先分配和局部搜索能够有效改善路径可行性和求解质量。研究结果说明,所构建模型与改进算法能够有效处理充电、时间窗、禁飞区和车机同步等多重耦合约束,为电动汽车−无人机协同末端配送优化提供有效方法。

       

      Abstract: To address the cooperative delivery routing problem in urban last-mile distribution arising from the coupled effects of limited electric vehicle range, customer time windows, drone no-fly zones, and vehicle-drone launch and recovery synchronization, an electric vehicle-multi-drone cooperative delivery optimization problem considering charging constraints and no-fly zones is investigated. A mixed-integer programming model is formulated with the objective of minimizing the system makespan by jointly incorporating vehicle routing, drone task assignment, charging-station visits, customer time windows, no-fly-zone avoidance, and vehicle-drone synchronization. Based on the adaptive large neighborhood search framework, an improved ALNS algorithm is developed by integrating a charging-aware repair strategy, an arc-based drone task generation and priority assignment mechanism, and local search operators. Numerical experiments are conducted using instances derived from the Solomon C101 benchmark. The results show that, for the small-scale N6, N7, and N8 instances, the improved ALNS obtains the same makespan as complete enumeration. For the 15-, 20-, 25-, and 30-customer instances, the average makespan is reduced by 1.26%, 11.44%, 8.45%, and 1.76%, respectively, compared with Basic-ALNS, and the improvements for the 15-, 20-, and 25-customer instances are statistically significant at the 0.05 level. For the 30-customer stress instance, the improved ALNS achieves a feasibility rate of 60%, compared with 30% for Basic-ALNS. Ablation experiments further demonstrate that the charging-aware repair, drone task priority assignment, and local search strategies effectively improve route feasibility and solution quality. The results indicate that the proposed model and improved algorithm can effectively handle the coupled constraints of charging, time windows, no-fly zones, and vehicle-drone synchronization, providing an effective approach for electric vehicle–drone cooperative last-mile delivery optimization.

       

    /

    返回文章
    返回