1. 项目概述与核心价值
在物流配送领域,并行无人机调度旅行商问题(PDSTSP)正成为学术界和工业界共同关注的热点。这个问题源于城市末端配送场景中无人机与卡车的协同作业需求——部分客户点可以由无人机直接从仓库独立服务,而无需与卡车配送路线同步。这种混合配送模式能够显著提升配送效率,但同时也带来了复杂的调度优化挑战。
传统解决PDSTSP的方法主要基于元启发式算法,如遗传算法、蚁群算法等。这些算法虽然有效,但在面对大规模复杂场景时,往往存在收敛速度慢、易陷入局部最优等问题。我们团队提出的QSISRs算法创新性地将强化学习中的Q-learning机制与传统基于破坏-重建的SISRs框架相结合,实现了算法性能的显著提升。
关键突破点:QSISRs算法通过Q-learning动态调整破坏阶段的字符串移除长度和策略选择,以及在重建阶段智能选择局部搜索算子组合,使算法能够自适应不同问题特征,大幅提升搜索效率和解的质量。
2. PDSTSP问题建模与挑战
2.1 问题形式化定义
PDSTSP可以建模为一个有向完全图G=(V,E),其中:
- V = {0} ∪ C,0代表仓库,C={1,...,n}表示客户集合
- E = {(i,j) | i,j ∈ V, i≠j} 表示所有可能的边
- 配送资源包括一辆卡车和m架同质无人机
关键约束条件:
- 卡车可以服务所有客户,但必须遵循经典的TSP约束(单车辆、返回仓库)
- 无人机只能服务部分符合条件的客户(受距离和载重限制)
- 无人机每次只能携带一个包裹,必须从仓库出发并返回仓库
- 卡车和无人机的运作相互独立,不需要同步
目标函数是最小化所有客户被服务完成的最晚时间(makespan)。
2.2 问题复杂性分析
PDSTSP是经典TSP问题的扩展,具有以下特点使其更具挑战性:
- 组合爆炸:卡车路线和无人机任务分配的组合导致解空间呈指数级增长
- 资源耦合:虽然卡车和无人机独立运行,但客户分配决策会影响整体效率
- 时空约束:无人机有最大飞行距离限制,卡车有容量限制
- 多目标性:实际应用中还需考虑能耗、成本等多重目标
3. SISRs算法框架解析
3.1 基本概念与原理
SISRs(Slack Induction by String Removals)是一种基于破坏-重建的迭代局部搜索算法,其核心思想是通过有策略地移除客户(破坏阶段)再重新插入(重建阶段)来不断改进解质量。算法引入了两个关键概念:
- 容量松弛:衡量当前解中路径容量利用率的松弛程度
- 空间松弛:评估地理空间分布的均匀程度
通过移除客户可以增加这两种松弛度,为后续重建阶段创造更多改进机会。
3.2 标准SISRs流程
标准SISRs算法包含以下主要步骤:
- 初始解生成:使用简单启发式方法构造可行解
- 破坏阶段:
- 采用相邻字符串移除策略
- 随机选择移除的字符串长度
- 重建阶段:
- 使用带随机性的贪婪插入机制
- 以一定概率接受非最优插入位置
- 局部搜索:应用预定义的邻域搜索算子
- 接受准则:决定是否接受新解
4. QSISRs算法创新设计
4.1 Q-learning与元启发式的融合框架
QSISRs算法的核心创新是将Q-learning融入SISRs的各个关键决策点,形成智能化的自适应优化框架。整体架构如下图所示:

4.2 破坏阶段的强化学习设计
在破坏阶段,QSISRs针对卡车路径和无人机任务分别设计了强化学习机制:
卡车路径破坏:
- 仍采用相邻字符串移除策略
- 但移除长度不再随机确定,而是通过Q-learning动态选择
- 状态特征包括:当前解质量、迭代次数、历史改进情况等
- 动作空间为不同的移除长度选项
- 奖励函数考虑解的质量改进和计算时间
无人机任务破坏:
设计了四种移除策略:
- d-random:随机移除无人机客户
- d-adjacent:移除地理相邻的无人机客户
- d-sweep:按扇形区域扫描移除
- d-near:移除距离仓库较近的客户
通过Q-learning实时评估各策略的效果,自适应选择最优破坏策略。
4.3 重建阶段的智能优化
重建阶段在标准贪婪插入的基础上,引入了以下改进:
- Blink机制:以概率β选择非最优插入位置,平衡探索与开发
- Q-learning引导的VND:
- 设计了12种局部搜索算子
- 通过Q-learning动态选择最有潜力的算子组合
- 状态特征考虑当前解结构、搜索历史等
- 奖励函数关注改进幅度和计算成本
5. 算法实现与参数设置
5.1 Q-learning参数配置
关键参数设置如下表所示:
| 参数 | 取值 | 说明 |
|---|---|---|
| 学习率α | 0.2 | 控制Q值更新速度 |
| 折扣因子γ | 0.8 | 未来奖励的折扣率 |
| 初始探索率ε | 0.3 | 初始探索概率 |
| ε衰减率 | 0.99 | 每轮ε的衰减系数 |
| Q初始值 | 0 | Q表的初始值 |
5.2 算法超参数
其他重要参数包括:
- 破坏比例:20%-30%的客户被移除
- Blink概率β:0.1-0.3
- 最大迭代次数:1000-5000次
- 种群大小:20-50个个体
5.3 计算效率优化
为提升算法效率,采用了以下技术:
- 增量计算:只重新计算受影响路径的目标值
- 邻域缓存:存储常用邻域移动的结果
- 并行评估:利用多线程评估不同算子效果
6. 实验评估与结果分析
6.1 测试数据集
实验采用了三类测试实例:
- 标准TSPLIB实例:eil51, eil76, eil101等
- 随机生成实例:不同规模(50-500客户)和无人机比例(20%-50%)
- 真实场景实例:基于某物流公司的城市配送数据
6.2 对比算法
与以下先进算法进行对比:
- 标准SISRs
- 遗传算法(GA)
- 变邻域搜索(VNS)
- 模因算法(MA)
6.3 性能指标
评估指标包括:
- 解质量:相对差距百分比
- 计算时间:CPU秒数
- 稳定性:多次运行的标准差
- 收敛速度:达到90%最优解的迭代次数
6.4 实验结果
关键结果对比如下表所示:
| 算法 | 平均差距(%) | 计算时间(s) | 稳定性(σ) |
|---|---|---|---|
| QSISRs | 0.0 | 152 | 0.12 |
| SISRs | 1.8 | 145 | 0.35 |
| VNS | 2.5 | 210 | 0.41 |
| MA | 3.2 | 180 | 0.28 |
| GA | 4.7 | 165 | 0.53 |
实验表明,QSISRs在解质量上显著优于其他算法,同时保持了合理的计算时间。特别是在大规模实例上(>200客户),优势更加明显。
7. 实际应用建议
7.1 实施注意事项
- 问题适配:需要根据具体场景调整状态特征和奖励函数
- 训练成本:初期需要一定迭代次数让Q-learning收敛
- 参数调优:关键参数需通过实验确定最优值
- 硬件需求:大规模问题需要足够内存存储Q表
7.2 常见问题排查
-
算法收敛慢:
- 检查探索率ε设置是否合适
- 确认奖励函数设计是否合理
- 尝试增加种群规模
-
解质量不稳定:
- 增加Q-learning训练轮次
- 调整Blink概率β
- 验证状态特征的有效性
-
内存不足:
- 采用函数逼近替代Q表
- 减少状态空间维度
- 使用稀疏存储结构
8. 扩展应用方向
QSISRs框架可扩展应用于以下领域:
- 其他车辆路径问题变体
- 生产调度问题
- 资源分配优化
- 组合优化问题
在实际物流系统中,我们已将该算法应用于某电商平台的无人机-卡车协同配送系统,实现了配送效率提升15%,成本降低8%的效果。
