带收益和时间窗的多行程卡车-无人机协同配送问题
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

F252

基金项目:

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


Multi-trip truck-drone routing problem with profits and time windows
Author:
Affiliation:

Fund Project:

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

    为了推动低空经济发展, 提高企业经济效益和“最后一公里”配送效率, 提出考虑客户收益和时间窗的多行程卡车-无人机协同配送问题. 首先, 以最大化利润为目标建立基础的混合整数规划模型(MIP), 并融入有效不等式来减少基础模型的松弛度. 然后, 提出一种高效的混合启发式算法求解该问题, 同时, 考虑到具有时间窗特征的卡车-无人机路径较为复杂, 可行性判断耗时高, 设计一种基于Segment的有效评估方法来加速路径的可行性检查, 以提高算法的求解效率. 实验结果表明: 有效不等式可将精确求解器 —— Gurobi求解模型的速度提高44 %; 其次, 在不同规模的算例中, 所提出混合启发式算法在求解效率和质量方面均优于Gurobi与两类启发式对比算法, 并表现出良好的稳定性; 此外, 通过嵌入Segment有效评估方法可减少算法95 %的求解时间.

    Abstract:

    In order to promote the development of low-altitude economy and improve the economic efficiency of enterprises and the efficiency of the “last-mile” delivery, the multi-trip truck-drone routing problem with profits and time windows is proposed. Firstly, a basic mixed-integer programming model (MIP) of the problem is established, considering the maximization of revenue, and the slack of the basic model is reduced by incorporating multiple valid inequalities. Then, an effective hybrid heuristic algorithm is proposed to solve the problem, and considering that the truck-drone paths with time windows characteristics are more complex and the feasibility checking is time-consuming, a Segment-based efficient evaluation method is designed to accelerate the feasibility checking of the paths in order to improve the solving efficiency of the algorithm. The experimental results show that the valid inequalities improve the speed of solving the model by 44 % for Gurobi; The proposed algorithm outperforms Gurobi and the two types of heuristic comparison algorithms for solving efficiency and solution quality in different sizes of instances, and exhibits good stability; Moreover, the algorithm's solving time can be reduced by 95 % by embedding the Segment-based efficient evaluation method.

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

罗永琪,陈彦如,冉茂亮.带收益和时间窗的多行程卡车-无人机协同配送问题[J].控制与决策,2025,40(6):1817-1826

复制
相关视频

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