模因算法求解同时取送货车辆-无人机协同路径优化问题
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP312;U15

基金项目:

国家自然科学基金项目(62103062).


Memetic algorithm for vehicle-drone collaborative routing problem with simultaneous pickup and delivery
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    针对多访问同时取送货车辆-无人机协同路径优化问题(MV-VDCRP-PD), 考虑无人机单次飞行可访问多个客户、客户时间窗、同时送取货以及车辆速度受路网影响等约束, 以最小化配送成本为目标, 建立MV-VDCRP-PD数学模型. 为有效求解该问题, 提出一种基于遗传算法与自适应大邻域搜索算法的模因算法(MA). 在MA中, 一个个体编码为包含一个客户序列和一个客户访问模式序列; 定义惩罚函数以判定个体是否违反问题约束, 提出修正方法以保证解的可行性; 为实现算法在解空间的大范围搜索, 设计基于客户点的交叉算子以生成新个体; 同时, 基于问题特征设计4种破坏算子和4种修复算子以寻找更高质量个体; 此外, 采用种群更新策略保证种群的质量和可行解的占比. 最后, 在不同规模算例上进行仿真和对比实验以验证所提出MA的有效性.

    Abstract:

    This paper focuses on a multi-visit vehicle-drone collaborative routing problem with simultaneous pickup and delivery (MV-VDCRP-PD), in which constraints such as multi-visit per flight, time windows, simultaneous pickup and delivery, and vehicle’s varying speeds influenced by road networks are considered. Taking minimizing the delivery cost as the optimization objective, we first formulate a mathematical model for the MV-VDCRP-PD. Then, to effectively solve the problem, a memetic algorithm (MA) based on the genetic algorithm and adaptive large neighbourhood search algorithm is proposed. In the MA, an individual is encoded as containing two sequences, a customer sequence and a customer visiting pattern sequence. To check whether the individual violates the problem constraints and ensure its feasibility, a penalty function and a modification method are proposed. To guarantee the exploration ability of the MA, a customer-based crossover operator is presented to generate new individuals. Meanwhile, based on the problem characteristics, four destroy operators and four repair operators are developed with the purpose of finding better individuals. In addition, a population update strategy is proposed to guarantee the population quality and the proportion of feasible solutions. Finally, experimental tests and comparisons are carried out on different instances to verify the effectiveness of the proposed MA.

    参考文献
    相似文献
    引证文献
引用本文

王俊皓,李晓玲,段浩浩,等.模因算法求解同时取送货车辆-无人机协同路径优化问题[J].控制与决策,2025,40(11):3287-3299

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2025-04-05
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2025-10-14
  • 出版日期: 2025-11-20
文章二维码