基于双向构造策略的神经组合优化模型

doi:10.19678/j.issn.1000-3428.0252115

摘要/Abstract

摘要： 组合优化问题在物流路径规划等领域具有重要应用价值,但其解空间随问题规模呈指数级扩张,导致传统方法面临严峻挑战。近年来基于强化学习的神经组合优化方法能够在保持较短求解耗时的同时,使解质量接近传统求解器的水平。主流方法POMO(Policy Optimization with Multiple Optima)通过对称性优化增强了训练稳定性,但其单向序列生成机制仍存在双重局限:一方面,传统构造式方法难以充分挖掘问题对称性特征;另一方面,终点信息无法有效参与远端节点的决策过程。针对这一问题,提出了基于双向构造策略(BCS)的BCS-POMO模型,通过起点与终点双向并行构造解序列,动态选择更有把握的扩展方向,避免模型因单向构造而陷入两难的抉择之中。该模型利用构造序列对称性实现权重参数共享,并通过批量并行计算提升效率。实验表明,BCS-POMO有效强化了终点信息在构造过程中的决策辅助作用,在旅行商问题(TSP)和有容量约束的车辆路径问题(CVRP)上分别使误差降低了16%和18%,验证了双向构造策略对终点信息利用的有效性和对称性建模的优势。

关键词: 组合优化问题, 神经组合优化方法, 注意力机制, 强化学习, 旅行商问题, 有容量约束的车辆路径问题

Abstract: Combinatorial optimization problems have important applications in areas such as logistics path planning; however, their solution space exponentially expands with the problem size, leading to severe challenges for traditional methods. In recent years, neural combinatorial optimization methods based on reinforcement learning have been able to achieve solution quality close to that of traditional solvers while keeping the solution computation time short. The mainstream method, called Policy Optimization with Multiple Optima (POMO), enhances the training stability through symmetry optimization; however, its unidirectional sequence generation mechanism still suffers from two limitations: the traditional constructive method cannot fully exploit the symmetry features of the problem easily and the endpoint information cannot effectively participate in the decision-making process of the remote node. To address this problem, this paper proposes a Bidirectional Construction Strategy (BCS)-based POMO model, named BCS-POMO, which dynamically selects the extension direction with higher confidence by constructing the solution sequence in parallel from the start and end points, avoiding models that are caught in a dilemma owing to unidirectional constructions. The model exploits the symmetry of the construction sequence to achieve weight parameter sharing and improves efficiency through batch parallel computation. Experimental results show that the BCS-POMO effectively reinforces the role of endpoint information as a decision aid in the construction process, which reduces the error by 16% and 18% for the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), respectively, verifying the effectiveness of the bidirectional construction strategy in exploiting endpoint information and the advantages of symmetry modelling.

Key words: combinatorial optimization problem, neural combinatorial optimization method, attention mechanism, reinforcement learning, Traveling Salesman Problem (TSP), Capacitated Vehicle Routing Problem (CVRP)

中图分类号:

TP183

王朝扬, 孙未未. 基于双向构造策略的神经组合优化模型[J]. 计算机工程, 2026, 52(10): 73-80.

WANG Chaoyang, SUN Weiwei. Neural Combinatorial Optimization Model Based on Bidirectional Construction Strategy[J]. Computer Engineering, 2026, 52(10): 73-80.

https://www.ecice06.com/CN/Y2026/V52/I10/73

参考文献

[1] COOK W J, CUNNINGHAM W H, PULLEYBLANK W R,et al. Combinatorial optimization[M]. New York, USA: John Wiley & Sons, Inc., 2010.
[2] 刘振宏, 蔡茂诚. 组合最优化算法和复杂性[M]. 北京: 清华大学出版社, 1988. LIU Z H, CAI M C. Combinatorial optimization algorithms and complexity[M]. Beijing:Tsinghua University Press, 1988. (in Chinese)
[3] HOCHBA D S. Approximation algorithms for NP-hard problems[J]. SIGACT News, 1997, 28(2): 40-52.
[4] 王扬, 陈智斌, 吴兆蕊, 等. 强化学习求解组合最优化问题的研究综述[J]. 计算机科学与探索, 2022, 16(2): 261-279. WANG Y, CHEN Z B, WU Z R, et al. Review of reinforcement learning for combinatorial optimization problem[J]. Journal of Frontiers of Computer Science & Technology, 2022, 16(2): 261-279. (in Chinese)
[5] MAO H Z, SCHWARZKOPF M, VENKATAKRISHNAN S B, et al. Learning scheduling algorithms for data processing clusters[C]//Proceedings of the ACM Special Interest Group on Data Communication. New York, USA: ACM Press, 2019: 270-288.
[6] VAZIRANI V V. Approximation Algorithms[M]. Berlin, Germany: Springer, 2003.
[7] KARIMI-MAMAGHAN M, MOHAMMADI M, MEYER P, et al. Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art[J]. European Journal of Operational Research, 2022, 296(2): 393-422.
[8] HELSGAUN K. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems[EB/OL]. [2024-01-15]. http://akira.ruc.dk/~keld/research/LKH-3/LKH-3_REPORT.pdf.
[9] KONSTANTAKOPOULOS G D, GAYIALIS S P, KECHAGIAS E P. Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification[J]. Operational Research, 2022, 22(3): 2033-2062.
[10] OPTIMIZATION I G. Gurobi optimizer reference manual[EB/OL]. [2024-01-15]. https://www.gurobi.com.
[11] HOPFIELD J J, TANK D W. "Neural" computation of decisions in optimization problems[J]. Biological Cybernetics, 1985, 52(3): 141-152.
[12] BELLO I, PHAM H, LE Q V, et al. Neural combinatorial optimization with reinforcement learning[EB/OL]. [2024-01-15]. https://arxiv.org/abs/1611.09940.
[13] VINYALS O, FORTUNATO M, JAITLY N. Pointer networks[EB/OL]. [2024-01-15]. https://arxiv.org/abs/1506.03134.
[14] KOOL W, HOOF H, GROMICHO J, et al. Deep policy dynamic programming for vehicle routing problems[C]//Proceedings of International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Berlin, Germany: Springer, 2022: 190-213.
[15] ZHANG W, DIETTERICH T G. A reinforcement learning approach to job-shop scheduling[C]//Proceedings of the 14th International Joint Conference on Artificial Intelligence. New York, USA: ACM Press, 1995: 1114-1120.
[16] 刘全, 翟建伟, 章宗长, 等. 深度强化学习综述[J]. 计算机学报, 2018(1): 1-27. LIU Q, ZHAI J W, ZHANG Z C, et al. A survey on deep reinforcement learning[J]. Chinese Journal of Computers, 2018(1): 1-27. (in Chinese)
[17] 郭田德, 韩丛英, 唐思琦. 组合优化机器学习方法[M]. 北京: 科学出版社, 2019. GUO T D, HAN C Y, TANG S Q. Machine learning methods for combinatorial optimization[M]. Beijing: Science Press, 2019. (in Chinese)
[18] VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all you need[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems. New York, USA: ACM Press, 2017: 6000-6010.
[19] WILLIAMS R J. Simple statistical gradient-following algorithms for connectionist reinforcement learning[J]. Machine Learning, 1992, 8(3): 229-256.
[20] KWON Y D, CHOO J, KIM B, et al. POMO: policy optimization with multiple optima for reinforcement learning[EB/OL]. [2024-01-15]. https://arxiv.org/abs/2010.16011.
[21] ZHOU J N. Generalizable neural solvers for vehicle routing problems[D]. Singapore: Nanyang Technological University, 2025.
[22] KIM M, PARK J, PARK J. Sym-NCO: leveraging symmetricity for neural combinatorial optimization[EB/OL]. [2024-01-15]. https://arxiv.org/abs/2205.13209.
[23] ZHOU J N, WU Y X, SONG W, et al. Towards omni-generalizable neural methods for vehicle routing problems[EB/OL]. [2024-01-15]. https://arxiv.org/pdf/2305.19587.
[24] KWON Y D, CHOO J, YOON I, et al. Matrix encoding networks for neural combinatorial optimization[EB/OL]. [2024-01-15]. https://arxiv.org/abs/2106.11113.
[25] KOOL W, HOOF H, WELLING M. Attention, learn to solve routing problems![EB/OL]. [2024-01-15]. https://arxiv.org/abs/1803.08475?context=stat.ML.
[26] APPLEGATE D L, BIXBY R E, CHVÁTAL V, et al. The traveling salesman problem: a computational study[M]. Princeton, USA: Princeton University Press, 2007.
[27] HELSGAUN K. An effective implementation of the Lin-Kernighan traveling salesman heuristic[J]. European Journal of Operational Research, 2000, 126: 106-130.

选择文件类型/文献管理软件名称

选择包含的内容