原文传递
大规模车辆路径问题的深度强化学习算法研究
| 论文题名： | 大规模车辆路径问题的深度强化学习算法研究 |
| 关键词： | 大规模车辆路径;物流配送;预训练;Transformer网络;在线强化训练 |
| 摘要： | 车辆路径问题是学术界和理论界都十分关注的热点和难点问题，它在现实中是物流配送领域的核心科学问题，在理论上属于一类NP-Hard难题。尤其是近年来随着我国商务活动的规模化发展，现实中涉及到成百上千网络节点的车辆路径问题比比皆是[1]，如何快速求解这类超大规模车辆路径问题是现实物流活动对该问题理论研究提出的新要求。尽管车辆路径问题已被大量学者所关注，而且已有很多优秀的求解算法，但它们在面临相同问题结构、不同数据的实例时需要从初始解开始寻找问题内部和数据内部的潜在关系，这种操作是费时费力的。近年来，学界提出的基于深度强化学习算法通过深层网络训练后，可以避免重复寻找相同问题的内在联系，使得快速求解现实中超大规模车辆路径问题成为可能，但是当使用深度强化学习解决大规模车辆路径问题时会面临网络提取问题特征不精确和内存溢出等问题。 针对大规模车辆路径问题，本文构建了加入相对位置节点的Transformer框架，并在预训练和A2C强化学习训练完成后能有效解决这类问题。深度神经网络中，为了更精确提取到配送中心节点与顾客节点之间的内在联系，将传统Transformer框架中加入了相对位置节点，强化节点之间的内在联系。在强化学习网络中，本文通过将Actor-Critic网络变换成能够规避经验回溯的A2C网络，通过在线强化学习训练，在master节点和多个worker节点中的同步交互过程中，对机器学习网络进行迭代更新，提高其收敛效率。不仅如此，本文针对大规模车辆路径问题在深度强化学习训练中的内存溢出无法完成训练和不同规模之间不能共享训练模型等问题，设计了车辆路径问题的预训练框架。 通过实验，将基于预训练框架的加入相对位置节点的Transformer网络使用A2C进行在线强化学习训练，并与启发式和元启发式算法的求解质量对比。并且分别对预训练框架、加入相对位置节点的Transformer网络和A2C网络通过控制变量的方式，进行收敛程度实验。 研究结果表明，基于预训练框架的加入相对位置节点的Transformer网络，通过A2C强化学习进行在线训练后，在规模为100、200、300和500的带容量限制的大规模车辆路径问题的求解质量要优于求解质量较好的启发式、元启发式算法和已有的机器学习算法。虽然大规模车辆路径问题的在线训练时长依旧耗时耗力，但是训练完成以后，模型在724毫秒内能给出满意解。 |
| 作者： | 刘明洋 |
| 专业： | 管理科学与工程 |
| 导师： | 王征 |
| 授予学位： | 硕士 |
| 授予学位单位： | 大连海事大学 |
| 学位年度： | 2022 |
检索历史
应用推荐
