Graph Neural Network-Driven Ant Colony Optimization for Combinatorial Problems on Graphs

Graph Combinatorial Optimization Problems (COPs) are pervasive in domains like logistics and network design, but their NP-hard nature presents a major hurdle for exact solvers. Metaheuristics such as Ant Colony Optimization (ACO) offer a viable alternative, yet their performance critically depends on manually designed, problem-specific heuristics, which limits their adaptability and efficiency. To address this, we propose the Machine Learning-enhanced Ant Colony Optimization (ML-ACO) framework, which integrates Graph Neural Networks (GNNs) and Deep Reinforcement Learning (DRL) to automate heuristic design. ML-ACO leverages a GNN to learn powerful, data-driven heuristics from the graph structure of the problem, which then guide a traditional ACO search procedure. Crucially, our framework incorporates modular designs, including distinct solution construction mechanisms for both sequential (e.g., path planning) and partition-based (e.g., graph partitioning) problems, alongside flexible modules for integrating complex real-world constraints such as path risks and task dependencies. We demonstrate the effectiveness of ML-ACO on the classic Max-Cut problem, where it improves solution quality by 10.9% over traditional ACO. Furthermore, in complex, simulated logistics scenarios, ML-ACO outperforms traditional ACO by 13.5–42.4% across key metrics, effectively handling intricate constraints. Our results validate that ML-ACO provides a versatile and powerful approach for solving complex, real-world COPs on graphs.