Page 102 - 运鑫服饰画册

PAGE/101 成都工业学院科研成果汇编

4. 无人机城市物流配送路径优化模型与算法研究

项目简介

四川省人文社科重点研究基地 - 无人机产业发展研究中心重点项目“无人机城市物流配送路径优化模型与算法研究”，
利用运筹优化相关技术，选择运筹优化领域中的数学规划法作为主要工具，建立了无人机城市物流配送路径优化模型，并
根据模型特点，设计了高效的求解算法。

无人机续航程短且载货量小，是制约无人机城市物流配送的主要瓶颈 , 而卡车 - 无人机协同配送，可以通过车辆为无
人机提供存储货物服务与充电服务，弥补了无人机的短板，并充分发挥了无人机的优势。其关键技术如下：

①卡车 - 多无人机协同配送优化技术

当前的卡车 - 无人机协同优化主要集中于考虑一辆卡车与一架无人机的协同配送问
题（TSP-D），难以满足实际需求。项目研究了卡车与多无人机协同配送问题（TSP-MD），不仅涉及到卡车与无人
机之间的协同，还涉及到多个无人机之间的协同，问题更加复杂。项目构建了卡车 - 多无人机协同配送的数学规划模型：
在总配送总时间最小化的目标下，需要满足以下约束：①每个客户仅被服务一次 ；②无人机可以是卡车车载模式或独立配
送模式，且每次独立配送只能服务一个客户，并满足最大续航里程；③无人机完成每次独立配送任务时，可以直接返回车场，
也可以返回到卡车补充货物与能量，但卡车与无人机只能在某个客户位置交汇，且在交汇点，卡车必须等待所有的无人机
返航。

②大规模分解优化技术

卡车 - 无人机配送问题是经典旅行商问题的拓展问题，属于 NP-hard 问题，求解困难，多数文献运用了启发式算法
或智能算法求解卡车 - 无人机配送问题。虽然启发式算法在可接受的时间内可以找到可行解，但是缺点是没法提供下界以
评估所获得的可行解的质量。因此，本项目根据模型的特点，设计了基于 L-shaped 型分解的精确算法，同时，运用了
T-reduction 方法加强 L-shaped 算法的收敛速度。算例测试表明，L-shaped 分解算法在解的质量与求解时间上均胜过
商业软件 Gurobi；T-reduction 方法加快了 L-shaped 分解算法的收敛速度。

技术指标

序号 指标名称 参数
针对 16 个服务点的规模，在 500s 内获得最优解，算
1 计算能力指标
法的计算时间则相比 Gurobi 降低 94.3%

项目成熟度 转化方式

成果孵化阶段 技术入股、技术服务