计算机科学与探索

作者：朱叶, 丁苍峰, 曹博浩, 陈科鑫

单位：延安大学 数学与计算机科学学院，陕西 延安 716000

关键词：组合优化问题,图神经网络,混合整数线性规划,旅行商问题

基金：国家自然科学基金（62262067）；陕西省人才项目（YAU202213065，CXY202107）；延安大学“十四五”重大科研项目（2021ZCQ012）；延安大学基金项目（YCX2024049，YDJG23-27，D2022034）。

组合优化作为数学优化领域的重要分支，致力于在有限离散解空间中寻找最优解，其在计算机科学、数学、经济学等多个领域中广泛运用。然而，随着问题规模的扩大，传统求解方法面临巨大挑战。近年来，机器学习技术的迅猛发展为组合优化研究带来新契机，尤其是图神经网络凭借其强大的结构建模能力与特征学习优势，成为解决组合优化问题的热门研究方向。为此，系统开展了图神经网络在组合优化问题中的应用研究。从组合优化问题的图表示出发，全面介绍了普通图神经网络、二部图神经网络、三部图神经网络以及超图神经网络等核心模型与算法，深入分析了其在解决具体组合优化问题场景中的应用策略与实际效果。对现有研究成果进行系统梳理与总结，客观评估了各类方法在实际应用中的优点与局限性。针对图神经网络在解决组合优化问题时存在的模型泛化性不足、可解释性差等问题，提出了未来可能的研究方向，期望为该领域的进一步发展提供新的思路与启发。

来源：2026年第2期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2026年第2期