基于改进MAML与GVAE的容量约束车辆路径问题求解方法

doi:10.11772/j.issn.1001-9081.2024111589

《计算机应用》唯一官方网站 ›› 2025, Vol. 45 ›› Issue (11): 3642-3648.DOI: 10.11772/j.issn.1001-9081.2024111589

• 先进计算 • 上一篇

基于改进MAML与GVAE的容量约束车辆路径问题求解方法

张焱鹏¹^,², 赵于前¹^,²(), 张帆¹^,², 丘腾海¹^,³, 桂瑰¹^,², 余伶俐¹^,²

^1.中南大学自动化学院，长沙 410083
^2.工业智能与系统教育部重点实验室（中南大学），长沙 410083
^3.中国科学院自动化研究所，北京 100190

收稿日期:2024-11-11 修回日期:2025-02-14 接受日期:2025-02-20 发布日期:2025-02-26 出版日期:2025-11-10
通讯作者: 赵于前
作者简介:张焱鹏（1999—），男，黑龙江齐齐哈尔人，硕士研究生，主要研究方向：深度强化学习、组合优化
张帆（1989—），男，副教授，博士，主要研究方向：图像处理、激光制造
丘腾海（1991—），男，博士研究生，主要研究方向：群体智能决策、多智能体强化学习
桂瑰（1979—），女，教授，博士，主要研究方向：人工智能、大数据模型、智能交通系统
余伶俐（1983—），女，教授，博士，主要研究方向：智能车辆路径规划、导航控制。
基金资助:
国家重点研发计划项目(2022YFE0112300);湖南省重点研发计划项目(2023GK2021);湖南省重点研发计划项目(2024JK2028)

Capacitated vehicle routing problem solving method based on improved MAML and GVAE

Yanpeng ZHANG¹^,², Yuqian ZHAO¹^,²(), Fan ZHANG¹^,², Tenghai QIU¹^,³, Gui GUI¹^,², Lingli YU¹^,²

^1.School of Automation，Central South University，Changsha Hunan 410083，China
^2.Key Laboratory of Industrial Intelligence and Systems，Ministry of Education （Central South University），Changsha Hunan 410083，China
^3.Institute of Automation，Chinese Academy of Sciences，Beijing 100190，China

Received:2024-11-11 Revised:2025-02-14 Accepted:2025-02-20 Online:2025-02-26 Published:2025-11-10
Contact: Yuqian ZHAO
About author:ZHANG Yanpeng， born in 1999， M. S. candidate. His research interests include deep reinforcement learning， combinatorial optimization.
ZHANG Fan， born in 1989， Ph. D.， associate professor. His research interests include image processing， laser manufacturing.
QIU Tenghai， born in 1991， Ph. D. candidate. His research interests include collective intelligence decision-making， multi-agent reinforcement learning.
GUI Gui， born in 1979， Ph. D.， professor. Her research interests include artificial intelligence， big data models， intelligent transportation systems.
YU Lingli， born in 1983， Ph. D.， professor. Her research interests include intelligent vehicle path planning， navigation control.
Supported by:
National Key Research and Development Program of China(2022YFE0112300);Key Research and Development Program of Hunan Province(2023GK2021)

摘要/Abstract

摘要：

基于深度强化学习（DRL）的车辆路径规划方法以其求解速度快、端到端等优势受到广泛关注，但现有方法大多局限于对节点分布均匀和数量固定问题的求解，当面临节点不平均分布以及节点数变化的情况时，求解效果有所下降。针对这一问题，提出一种基于改进模型无关的元学习（MAML）和图变分自编码器（GVAE）的元学习框架，旨在通过元训练得到一个良好的初始化模型，并针对数据集外分布的任务进行快速微调，从而提升模型的泛化性能；此外利用GVAE初始化元学习框架的参数，以进一步提升元学习效果。实验结果表明，所提方法可以较好地处理不同节点分布情况下的车辆路径问题（VRP），在面对不同节点数量问题时也有较好的表现，在5种任务上的平均偏差率较未使用元学习的方法降低了0.45个百分点。利用元学习框架可有效提升强化学习的效果，与先进求解器相比，所提框架在保证成本接近的前提下可有效缩短求解时间。

关键词: 车辆路径问题, 深度强化学习, 元学习, 图变分自编码器, 组合优化, 策略梯度方法

Abstract:

Deep Reinforcement Learning （DRL）-based vehicle routing planning methods have garnered significant attention for their rapid solving speed and end-to-end processing capabilities. However， most existing methods are limited to scenarios with uniformly distributed nodes and fixed node numbers， demonstrating performance degradation when handling unevenly distributed nodes or varying numbers of nodes. To address this issue， a meta-learning framework based on improved Model-Agnostic Meta-Learning （MAML） and Graph Variational AutoEncoder （GVAE） was proposed to obtain a well-initialized model through meta-training， and perform quick fine-tuning for out-of-distribution tasks， improving the model's generalization performance. Besides， a GVAE was employed for initializing parameters of the meta-learning framework to further enhance the effect of meta-learning. Experimental results show that the proposed method can handle Vehicle Routing Problems （VRPs） with different node distributions， performs well when dealing with varying numbers of nodes. The average gap across five tasks reduced by 0.45 percentage points compared to the method that does not use meta-learning. It can be seen that the proposed meta-learning framework enhances the effect of reinforcement learning， achieves comparable solution quality to state-of-the-art solvers while significantly shortening computation time.

Key words: Vehicle Routing Problem (VRP), Deep Reinforcement Learning (DRL), meta-learning, Graph Variational AutoEncoder (GVAE), combinatorial optimization, policy gradient method

中图分类号:

TP181

张焱鹏, 赵于前, 张帆, 丘腾海, 桂瑰, 余伶俐. 基于改进MAML与GVAE的容量约束车辆路径问题求解方法[J]. 计算机应用, 2025, 45(11): 3642-3648.

Yanpeng ZHANG, Yuqian ZHAO, Fan ZHANG, Tenghai QIU, Gui GUI, Lingli YU. Capacitated vehicle routing problem solving method based on improved MAML and GVAE[J]. Journal of Computer Applications, 2025, 45(11): 3642-3648.

图/表 5

参考文献 28

[1]	季彬，周赛琦，张政.分支定价方法求解带二维装箱约束的车辆路径问题［J］.控制理论与应用，2023，40（3）：409-418.
	JI B， ZHOU S Q， ZHANG Z. Branch-and-price approach for solving the vehicle routing problem with two-dimensional loading constraints［J］. Control Theory and Applications， 2023， 40（3）： 409-418.
[2]	BOGYRBAYEVA A， MERALIYEV M， MUSTAKHOV T， et al. Machine learning to solve vehicle routing problems： a survey［J］. IEEE Transactions on Intelligent Transportation Systems， 2024， 25（6）： 4754-4772.
[3]	李熠胥，胡蓉，吴绍云，等.三阶段拉格朗日启发式算法求解带同时取送货的绿色车辆路径问题［J］.控制与决策，2023，38（12）： 3525-3533.
	LI Y X， HU R， WU S Y， et al. Three-stage Lagrangian heuristic algorithm for solving green vehicle routing problem with simultaneous pickup and delivery［J］. Control and Decision， 2023， 38（12）： 3525-3533.
[4]	罗佳，李朝锋.基于残差图卷积网络与深度强化学习的需求可拆分车辆路径优化算法［J］.控制理论与应用，2024，41（6）：1123-1136.
	LUO J， LI C F. The split delivery vehicle routing optimization with the residual graph convolutional network and deep reinforcement learning［J］. Control Theory and Applications， 2024， 41（6）： 1123-1136.
[5]	BELLO I， PHAM H， LE V Q， et al. Neural combinatorial optimization with reinforcement learning［EB/OL］. ［2024-06-12］..
[6]	NAZARI M， OROOJLOOY A， TAKÁČ M， et al. Reinforcement learning for solving the vehicle routing problem［C］// Proceedings of the 32nd International Conference on Neural Information Processing Systems. Red Hook： Curran Associates Inc.， 2018： 9861-9871.
[7]	KOOL W， VAN HOOF H， WELLING M. Attention， learn to solve routing problems！［EB/OL］. ［2024-09-25］..
[8]	XIN L， SONG W， CAO Z， et al. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems［C］// Proceedings of the 35th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2021： 12042-12049.
[9]	PENG B， WANG J， ZHANG Z. A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems［C］// Proceedings of the 2019 International Symposium on Intelligence Computation and Applications， CCIS 1205. Singapore： Springer， 2020： 636-650.
[10]	KWON Y D， CHOO J， KIM B， et al. POMO： policy optimization with multiple optima for reinforcement learning［C］// Proceedings of the 34th International Conference on Neural Information Processing Systems. Red Hook： Curran Associates Inc.， 2020： 21188-21198.
[11]	JIANG Y， CAO Z， WU Y， et al. Multi-view graph contrastive learning for solving vehicle routing problems［C］// Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence. New York： JMLR.org， 2023： 984-994.
[12]	CHEN X， TIAN Y. Learning to perform local rewriting for combinatorial optimization［C］// Proceedings of the 33rd International Conference on Neural Information Processing Systems. Red Hook： Curran Associates Inc.， 2019： 6281-6292.
[13]	WU Y， SONG W， CAO Z， et al. Learning improvement heuristics for solving routing problems［J］. IEEE Transactions on Neural Networks and Learning Systems， 2022， 33（9）： 5057-5069.
[14]	MA Y， LI J， CAO Z， et al. Learning to iteratively solve routing problems with dual-aspect collaborative transformer［C］// Proceedings of the 35th International Conference on Neural Information Processing Systems. Red Hook： Curran Associates Inc.， 2021： 11096-11107.
[15]	ZHAO J， MAO M， ZHAO X， et al. A hybrid of deep reinforcement learning and local search for the vehicle routing problems［J］. IEEE Transactions on Intelligent Transportation Systems， 2021， 22（11）： 7208-7218.
[16]	KIPF T N， WELLING M. Variational graph auto-encoders［EB/OL］. ［2024-12-01］..
[17]	PAN S， HU R， LONG G， et al. Adversarially regularized graph autoencoder for graph embedding［C］// Proceedings of the 27th International Joint Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2019： 2609-2615.
[18]	GROVER A， ZWEIG A， ERMON S. Graphite： iterative generative modeling of graphs［C］// Proceedings of the 36th International Conference on Machine Learning. New York： JMLR.org， 2019： 2434-2444.
[19]	HOTTUNG A， KWON Y D， TIERNEY K. Efficient active search for combinatorial optimization problems［EB/OL］. ［2024-07-09］..
[20]	BI J， MA Y， WANG J， et al. Learning generalizable models for vehicle routing problems via knowledge distillation［C］// Proceedings of the 36th International Conference on Neural Information Processing Systems. Red Hook： Curran Associates Inc.， 2022： 31226-31238.
[21]	刘颖，雷研博，范九伦，等.基于小样本学习的图像分类技术综述［J］.自动化学报，2021，47（2）：297-315.
	LIU Y， LEI Y B， FAN J L， et al. Survey on image classification technology based on small sample learning［J］. Acta Automatica Sinica， 2021， 47（2）： 297-315.
[22]	FINN C， ABBEEL P， LEVINE S. Model-agnostic meta-learning for fast adaptation of deep networks［C］// Proceedings of the 34th International Conference on Machine Learning. New York： JMLR.org， 2017： 1126-1135.
[23]	NICHOL A， ACHIAM J， SCHULMAN J. On first-order meta-learning algorithms［EB/OL］. ［2024-04-12］..
[24]	ZINTGRAF L， SHIARLI K， KURIN V， et al. Fast context adaptation via meta-learning［C］// Proceedings of the 36th International Conference on Machine Learning. New York： JMLR.org， 2019： 7693-7702.
[25]	PATACCHIOLA M， BRONSKILL J， SHYSHEYA A， et al. Contextual squeeze-and-excitation for efficient few-shot image classification［C］// Proceedings of the 36th International Conference on Neural Information Processing Systems. Red Hook： Curran Associates Inc.， 2022： 36680-36692.
[26]	VIDAL T. Hybrid genetic search for the CVRP： open-source implementation and SWAP^* neighborhood［J］. Computers and Operations Research， 2022， 140： No.105643.
[27]	HELSGAUN K. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems［R/OL］. ［2024-06-01］..
[28]	MANCHANDA S， MICHEL S， DRAKULIC D， et al. On the generalization of neural combinatorial optimization heuristics［C］// Proceedings of the 2022 Joint European Conference on Machine Learning and Knowledge Discovery in Databases， LNCS 1371. Cham： Springer， 2023： 426-442.

方法		100G		150U		150G		200U		200G		均值
方法		成本	Gap/%	成本	Gap/%	成本	Gap/%	成本	Gap/%	成本	Gap/%	成本	Gap/%
专业求解器	HGS^［26］	12.653	0.00	19.146	0.00	15.398	0.00	21.914	0.00	18.845	0.00	17.591	0.00
专业求解器	LKH3^［27］	12.769	0.92	19.330	0.96	15.544	0.95	22.148	1.07	19.028	0.97	17.764	0.98
深度强化学习	AM^［7］	13.734	8.54	21.434	11.95	17.130	11.25	24.673	12.59	21.103	11.98	19.615	11.50
	POMO^［10］	13.010	2.82	19.810	3.47	15.914	3.35	22.720	3.68	19.531	3.64	18.197	3.44
	POMO-reptile^［23］	13.014	2.85	19.797	3.40	15.911	3.33	22.734	3.74	19.533	3.65	18.198	3.45
本文方法	without GVAE	12.969	2.50	19.768	3.25	15.902	3.27	22.642	3.32	19.510	3.53	18.158	3.22
	with GVAE	12.960	2.43	19.736	3.08	15.897	3.24	22.602	3.14	19.448	3.20	18.129	3.05
	with GVAE+使用微调	12.952	2.36	19.725	3.02	15.880	3.13	22.591	3.09	19.436	3.14	18.117	2.99

方法		100G		150U		150G		200U		200G		均值
方法		成本	Gap/%	成本	Gap/%	成本	Gap/%	成本	Gap/%	成本	Gap/%	成本	Gap/%
专业求解器	HGS^［26］	12.653	0.00	19.146	0.00	15.398	0.00	21.914	0.00	18.845	0.00	17.591	0.00
专业求解器	LKH3^［27］	12.769	0.92	19.330	0.96	15.544	0.95	22.148	1.07	19.028	0.97	17.764	0.98
深度强化学习	AM^［7］	13.734	8.54	21.434	11.95	17.130	11.25	24.673	12.59	21.103	11.98	19.615	11.50
	POMO^［10］	13.010	2.82	19.810	3.47	15.914	3.35	22.720	3.68	19.531	3.64	18.197	3.44
	POMO-reptile^［23］	13.014	2.85	19.797	3.40	15.911	3.33	22.734	3.74	19.533	3.65	18.198	3.45
本文方法	without GVAE	12.969	2.50	19.768	3.25	15.902	3.27	22.642	3.32	19.510	3.53	18.158	3.22
	with GVAE	12.960	2.43	19.736	3.08	15.897	3.24	22.602	3.14	19.448	3.20	18.129	3.05
	with GVAE+使用微调	12.952	2.36	19.725	3.02	15.880	3.13	22.591	3.09	19.436	3.14	18.117	2.99

方法		求解时间/min					平均求解时间/min
方法		100G	150U	150G	200U	200G	平均求解时间/min
专业求解器	HGS^［26］	13.00	36.00	36.00	48.00	48.00	36.00
专业求解器	LKH3^［27］	10.00	30.00	30.00	42.00	42.00	30.00
深度强化学习	AM^［7］	3.00	7.00	7.00	15.00	14.00	9.20
	POMO^［10］	0.15	0.43	0.43	0.87	0.80	0.54
	POMO-reptile^［23］	0.15	0.43	0.43	0.87	0.80	0.54
本文方法	without GVAE	0.15	0.43	0.43	0.87	0.80	0.54
	with GVAE	0.15	0.43	0.43	0.87	0.80	0.54
	with GVAE+使用微调	0.67	2.10	2.10	3.90	3.80	2.50

方法		求解时间/min					平均求解时间/min
方法		100G	150U	150G	200U	200G	平均求解时间/min
专业求解器	HGS^［26］	13.00	36.00	36.00	48.00	48.00	36.00
专业求解器	LKH3^［27］	10.00	30.00	30.00	42.00	42.00	30.00
深度强化学习	AM^［7］	3.00	7.00	7.00	15.00	14.00	9.20
	POMO^［10］	0.15	0.43	0.43	0.87	0.80	0.54
	POMO-reptile^［23］	0.15	0.43	0.43	0.87	0.80	0.54
本文方法	without GVAE	0.15	0.43	0.43	0.87	0.80	0.54
	with GVAE	0.15	0.43	0.43	0.87	0.80	0.54
	with GVAE+使用微调	0.67	2.10	2.10	3.90	3.80	2.50

基于改进MAML与GVAE的容量约束车辆路径问题求解方法

Capacitated vehicle routing problem solving method based on improved MAML and GVAE

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 28

相关文章 15

编辑推荐

Metrics

[1]	齐巧玲, 王啸啸, 张茜茜, 汪鹏, 董永峰. 基于元学习的标签噪声自适应学习算法[J]. 《计算机应用》唯一官方网站, 2025, 45(7): 2113-2122.
[2]	薛天宇, 李爱萍, 段利国. 联合任务卸载和资源优化的车辆边缘计算方案[J]. 《计算机应用》唯一官方网站, 2025, 45(6): 1766-1775.
[3]	许鹏程, 何磊, 李川, 钱炜祺, 赵暾. 基于Transformer的深度符号回归方法[J]. 《计算机应用》唯一官方网站, 2025, 45(5): 1455-1463.
[4]	严一钦, 罗川, 李天瑞, 陈红梅. 基于关系网络和Vision Transformer的跨域小样本分类模型[J]. 《计算机应用》唯一官方网站, 2025, 45(4): 1095-1103.
[5]	王华华, 黄梁, 陈甲杰, 方杰宁. 基于深度强化学习的低轨卫星多波束子载波动态分配算法[J]. 《计算机应用》唯一官方网站, 2025, 45(2): 571-577.
[6]	王靖, 方旭明. Wi-Fi7多链路通感一体化的功率和信道联合智能分配算法[J]. 《计算机应用》唯一官方网站, 2025, 45(2): 563-570.
[7]	富坤, 应世聪, 郑婷婷, 屈佳捷, 崔静远, 李建伟. 面向小样本节点分类的图数据增强方法[J]. 《计算机应用》唯一官方网站, 2025, 45(2): 392-402.
[8]	卫琳, 李金阳, 王亚杰, 和孟佯. 算力网络中基于多维资源度量和重调度的高可靠匹配方法[J]. 《计算机应用》唯一官方网站, 2025, 45(11): 3632-3641.
[9]	缪孜珺, 罗飞, 丁炜超, 董文波. 基于全局状态预测与公平经验重放的交通信号控制算法[J]. 《计算机应用》唯一官方网站, 2025, 45(1): 337-344.
[10]	黄云川, 江永全, 黄骏涛, 杨燕. 基于元图同构网络的分子毒性预测[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2964-2969.
[11]	周毅, 高华, 田永谌. 基于裁剪优化和策略指导的近端策略优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2334-2341.
[12]	马天, 席润韬, 吕佳豪, 曾奕杰, 杨嘉怡, 张杰慧. 基于深度强化学习的移动机器人三维路径规划方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2055-2064.
[13]	李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
[14]	吴郅昊, 迟子秋, 肖婷, 王喆. 基于元学习自适应的小样本语音合成[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1629-1635.
[15]	李炫锋, 刘晟材, 唐珂. 机会约束的多选择背包问题的遗传算法求解[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1378-1385.