有禁飞区的时间依赖型车辆与无人机协同配送路径优化

Time-dependent vehicle routing problem with drones considering no-fly zones

中文关键词  禁飞区  时间依赖型  车辆与无人机协同配送  遗传变邻域搜索算法

英文关键词  no-fly zones  time-dependent  vehicle routing problem with drones  genetic algorithm and variable neighborhood search

中文摘要

      本文针对有禁飞区的时间依赖型车辆与无人机协同配送路径问题, 综合考虑分时段禁飞的无人机禁飞区域、车辆行驶速度连续变化、车辆及无人机能耗等因素, 以车辆派遣成本、车辆能耗成本、无人机能耗成本之和最小为目标建立优化模型. 根据问题特征, 设计遗传变邻域搜索算法对其进行求解. 针对遗传算法易早熟、局部搜索能力较差等缺陷, 将变邻域搜索算法与其结合以增强算法的局部搜索能力, 引入自适应邻域搜索次数以增强对种群的搜索深度, 采用精英保留策略不断改进最优解. 通过多组算例验证了算法的有效性, 并分析了配送模式、禁飞区数量、车辆行驶速度变化对配送方案的影响, 结果表明禁飞区及车辆速度等因素在很大程度上影响物流配送成本.研究成果不仅丰富了车辆与无人机协同配送的场景, 拓展了VRP问题的研究, 也为物流企业制定配送方案提供了依据.

英文摘要

      The paper is about the time-dependent vehicle routing problem with drones considering no-fly zones. We take the factors such as the no-fly zones of drones, continuous change of vehicle speed, the energy consumption of vehicles and drones into account. To minimize the sum of vehicle fixed cost, energy consumption cost of vehicles and energy consumption cost of drones, an optimization model is presented to describe the problem. We combine variable neighborhood search algorithm with genetic algorithm to enhance the local search ability of the algorithm and address the defects of genetic algorithm such as premature maturity and poor local search ability. At the same time, the adaptive neighborhood search number is introduced to enhance the search depth of the population, and the elite retention strategy is used to continuously improve the optimal solution. The effectiveness of the algorithm is verified through multiple sets of arithmetic cases, and the effects of distribution mode, the number of no-fly zones, vehicle speed variation on the delivery scheme are analyzed. The results show that the factors such as time-varying no-fly zones and vehicle speed largely affect the delivery cost. The research results not only enrich the scenarios of cooperative delivery of vehicles and drones, expand the research of VRP problems, but also provide a basis for logistics enterprises to develop delivery plans.