原文传递
基于深度强化学习的油耗最小化车辆路径规划方法
| 论文题名： | 基于深度强化学习的油耗最小化车辆路径规划方法 |
| 关键词： | 货物运输;车辆路径规划;深度强化学习;油耗最小化 |
| 摘要： | 油耗最小化的车辆路径问题（Capacitated Vehicle Routing Problem Minimizing Fuel Consumption，fc-cvrp）是容量受限车辆路径问题（CVRP）的一个变种。在该问题中，存在多辆同质车辆、多个客户点和一个仓库点，车辆均从仓库点出发，对客户点进行送货，所有客户点仅被访问一次，最终车辆均回到仓库点，完成客户点的货物运输。与传统车辆路径问题最小化路径长度不同，该问题以最小化油耗为目标，其中，油耗与距离、车辆当前载重呈非线性关系。因此，司机在选择下一个访问点时，需要权衡当前点到下一个点的距离，此外还需考虑车辆的当前载重，使得最终路径总油耗最小。 该问题的目标函数是非线性的，导致问题解空间大，求解复杂，此外，主流算法——精确算法和元启发式算法，难以利用以前求解问题实例的先验知识，对新的问题实例进行求解。近年来，深度学习算法在解决运筹优化问题中得到了广泛的应用，求解速度快、效果好。为了解决上述难点，本文使用深度强化学习求解fc-cvrp。 首先，本文将fc-cvrp归结为序列到序列问题。其次，建立相应的马尔科夫模型并且论证了该问题的马尔科夫性质，提出一种深度强化学习算法——Route Planner。根据问题特点，基于Transformer模型搭建策略网络框架，对框架中的编码器和解码器进行了设计及其超参数的优化。本文提出负奖励作为训练的基础，并根据带基线的策略梯度算子设计了Route Planner算法的损失函数，对策略网络进行训练，目标是通过训练获取一种同时考虑两点间距离和车辆当前载重，以合理选择访问节点的策略。最后实现了Route Planner在短时间内得出解质量较高的效果。 根据文献的实例生成方法，本文针对问题实例的三种不同规模均生成一百个测试问题实例。本文使用的对比算法有基于Cplex求解器开发的精确算法、文献的启发式算法Saving和BI、本文开发的元启发式算法SA。实验结果表明，Route Planner算法在短时间（1s）内取得的结果较优，并且在测试数据集的解均值、获胜率和求解时间的指标上，算法性能表现优异。通过算法对比，本文验证了Route Planner算法在实时响应场景下的有效性和优越性。 此外，本文对Route Planner算法进行了结果可视化及大量的数据实验。训练曲线的可视化验证了Route Planner训练的收敛性；解路径的可视化探究了构造解时的特征和倾向。数据实验验证了Route Planner的迁移学习能力，并据此辅助收敛了大规模油耗最小化车辆路径规划问题实例的训练及测试其泛化性能；证实了Route Planner可以通过更长时间的随机采样得到更好的结果。威尔克森符号秩检验验证了Route Planner算法与表现较好基线算法之间的差异性。 |
| 作者： | 詹钊涵 |
| 专业： | 机械工程 |
| 导师： | 魏丽军;郭芳名 |
| 授予学位： | 硕士 |
| 授予学位单位： | 广东工业大学 |
| 学位年度： | 2022 |
检索历史
应用推荐
