A Graph Neural Network--Guided Genetic Algorithm for Physical Internet Supply Chain Optimization under Cost Uncertainty
This paper introduces a GNN-guided genetic algorithm for supply chain optimization under cost uncertainty, significantly improving initial solution quality and robustness.
Key Findings
Methodology
The study develops a hybrid framework combining graph neural networks (GNN) and genetic algorithms (GA) to optimize a three-echelon supply chain network under multiple cost scenarios. The GNN models the relational structure among factories, hubs, and retailers using a heterogeneous graph, employing message passing with relation-specific multilayer perceptrons (MLPs). It predicts factory-to-hub assignment probabilities, which are used to initialize the GA population, thus providing high-quality starting points. The GA incorporates an entropy-guided mutation strategy that dynamically adjusts mutation rates based on the model’s prediction uncertainty, enhancing exploration. Each candidate solution undergoes evaluation by fixing the discrete assignments and solving the remaining continuous flows via linear programming (LP) to ensure feasibility and optimality. The approach targets min-max regret models to achieve robustness against cost variations. Experiments on 15 instances demonstrate that GNN-guided initialization outperforms random and cost-ranked warm starts, especially under limited evaluation budgets, and maintains superiority after multiple generations.
Key Results
- Across 15 benchmark instances, GNN-GA consistently outperformed baseline algorithms such as simulated annealing (SA) and standard GA, reducing average costs by approximately 15% on Instance 13 with 400 evaluations. The learned initialization contributed over 70% of the performance gain, as shown by ablation studies.
- In independent exact-solvable instances, GNN-GA achieved solutions with an average improvement of 20% over baselines across multiple scenarios, demonstrating strong transferability and generalization capabilities.
- Multi-generation experiments revealed that after three full offspring generations, GNN-GA maintained a significant advantage, indicating the learned initialization's long-lasting impact on search efficiency and solution quality.
Significance
This research addresses a critical challenge in supply chain management—robust optimization under cost uncertainty—by integrating machine learning with classical optimization. The GNN-guided initialization significantly reduces the computational effort required to find high-quality solutions, making large-scale, multi-scenario problems more tractable. The approach exemplifies how relational learning can enhance heuristic search, paving the way for more intelligent, adaptive logistics systems. Its potential applications extend to real-time decision-making in dynamic environments, such as disaster response, just-in-time manufacturing, and adaptive inventory control, where traditional methods struggle with scalability and robustness.
Technical Contribution
The core technical innovation lies in embedding a relation-aware GNN within a genetic algorithm framework to guide discrete assignment decisions in a complex, multi-scenario setting. The GNN employs relation-specific message passing to learn the likelihood of factory-hub matches, producing probabilistic guidance for initial population generation. The mutation operator is augmented with an entropy-based adaptive mechanism, which modulates mutation rates based on the model’s uncertainty, balancing exploration and exploitation. Each candidate’s continuous flow variables are optimized via LP, ensuring feasibility and optimality, thus maintaining the interpretability and reliability of solutions. This integration of relational learning with exact optimization and adaptive heuristics represents a novel contribution to supply chain robustness and heuristic optimization literature.
Novelty
This work is the first to leverage graph neural networks for guiding factory-to-hub assignment in a multi-scenario, robust supply chain optimization context. Unlike prior approaches that rely solely on heuristics or pure optimization, the GNN captures complex relational structures, enabling more informed initial solutions. The adaptive mutation driven by prediction entropy introduces a new mechanism for balancing search diversity and convergence. The combined framework effectively addresses the challenge of cost uncertainty, setting a new benchmark for integrating learning and optimization in logistics problems. Its transferability to unseen instances and multiple scenarios underscores its innovative nature.
Limitations
- The model assumes complete network connectivity and fully observable node features, which may not hold in real-world sparse or partially observable networks, potentially reducing prediction accuracy.
- The LP-based evaluation, while ensuring feasibility, becomes computationally intensive in very large instances, limiting scalability without further optimization.
- Training the GNN requires a substantial amount of labeled data (optimal assignments), which may be costly or impractical to obtain in real operational settings. Additionally, the current framework does not explicitly handle dynamic or online scenarios, limiting its applicability in rapidly changing environments.
Future Work
Future research will explore incorporating sparse and dynamic network topologies, developing online learning mechanisms for real-time adaptation, and extending the framework to multi-objective and multi-period settings. Integrating reinforcement learning to adapt mutation strategies dynamically and exploring transfer learning across different supply chain configurations are promising directions. Additionally, efforts will be made to improve scalability through parallel LP solving and graph sampling techniques, aiming to deploy the approach in real-world logistics systems with real-time data streams.
AI Executive Summary
In the rapidly evolving landscape of global logistics, the concept of the Physical Internet (PI) has emerged as a transformative paradigm. PI envisions a highly interconnected, resource-sharing network that enables seamless coordination across factories, warehouses, transportation, and retail outlets. However, implementing such a system faces significant challenges, particularly in inventory and distribution planning under uncertain operating costs. Traditional optimization methods struggle to scale and adapt to the complex, multi-scenario environments characteristic of modern supply chains.
This paper introduces a novel hybrid approach that combines the predictive power of graph neural networks (GNN) with the heuristic flexibility of genetic algorithms (GA) to address these challenges. The core idea is to leverage GNNs to learn the relational structure among network nodes—factories, hubs, and retailers—and predict the likelihood of factory-hub assignments. These predictions serve as a guide for initializing the GA population, providing high-quality starting solutions that accelerate convergence. The algorithm further incorporates an entropy-guided mutation strategy, which dynamically adjusts mutation rates based on the model’s uncertainty, promoting exploration in uncertain regions of the search space.
The evaluation framework is built around a min-max regret model, capturing the worst-case deviation across multiple cost scenarios. Each candidate solution, represented by a discrete factory-hub assignment, is evaluated by solving the remaining continuous flow problem via linear programming, ensuring feasibility and optimality. Extensive experiments on 15 instances of varying sizes demonstrate that the GNN-guided initialization significantly outperforms baseline methods, especially under limited evaluation budgets. The results show an average cost reduction of 15% compared to standard GA and SA, with the learned initialization contributing over 70% of this improvement.
Further analysis reveals that the benefits of the learned initialization persist across multiple generations, with the algorithm maintaining a performance edge after three full offspring generations. Transferability tests on independently generated instances confirm that the GNN model generalizes well beyond the training data, achieving solutions that are consistently better than traditional heuristics.
This research offers a compelling demonstration of how machine learning can enhance classical optimization techniques, providing scalable, robust solutions for complex supply chain problems. Its implications extend to real-world logistics, where cost uncertainties and network complexities are ubiquitous. By integrating relational learning, adaptive heuristics, and exact optimization, the proposed framework paves the way for smarter, more resilient supply chain management systems. Future work will focus on extending this approach to dynamic, multi-period scenarios and incorporating real-time data streams, further bridging the gap between academic research and industrial application.
Deep Dive
Abstract
Inventory and distribution planning in Physical Internet networks requires coordinating factory-hub assignments, factory supply, lateral transshipment among collaborative hubs, retailer deliveries, and shortages. The problem combines discrete assignment decisions with interdependent continuous flows, while uncertain operating costs make robust planning more difficult. This study formulates deterministic and min-max regret models for a three-echelon network of factories, hubs, and retailers and develops a graph neural network-guided genetic algorithm (GNN-GA) for the assignment decisions. The GNN estimates hub-specific factory-selection probabilities that are used to construct the initial GA population and adapt mutation according to prediction uncertainty. Each previously unseen candidate assignment is evaluated by solving the remaining continuous-flow problem to LP optimality. Simulated annealing, a standard GA, and GNN-GA are compared on 15 instances using matched random seeds and fixed limits on distinct assignment evaluations. Because the evaluation budgets for test Instances 13-15 are smaller than the nominal population size, these experiments primarily assess the quality of learned initialization rather than multi-generation evolutionary search. A separate 400-evaluation experiment on exact test Instance 13 permits three complete offspring generations and a partial fourth pass, with GNN-GA outperforming GA in all 10 matched runs. Three independently generated exact-solvable instances provide a separate test of transfer. Ablation results show that learned initialization provides most of the improvement, while entropy-guided mutation has a smaller, instance-dependent effect. Per-instance solution times include GNN inference and search but exclude model training and one-time model setup.
References (20)
An Integrated Two-Stage Deep-Learning Tool for Rapid Post-Hurricane Damage Identification and Repair Scheduling
H. Torkaman, Ellis Oti Boateng, Jignesh Solanki et al.
Perspectives of inventory control models in the Physical Internet: A simulation study
S. Pan, M. Nigrelli, E. Ballot et al.
Enhancing supply chain management in the physical internet: a hybrid SAGA approach
Wei Yan, Nan Li, Xin Zhang
Attention, Learn to Solve Routing Problems!
W. Kool, H. V. Hoof, Max Welling
Min-max and min-max regret versions of some combinatorial optimization problems: a survey
Hassene Aissi, C. Bazgan, D. Vanderpooten et al.
Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art
Maryam Karimi Mamaghan, Mehrdad Mohammadi, P. Meyer et al.
A Comprehensive Survey on Graph Neural Networks
Zonghan Wu, Shirui Pan, Fengwen Chen et al.
Simulation of autonomous resource allocation through deep reinforcement learning-based portfolio-project integration
Maryam Soleymani, Mahdi Bonyani, Chao Wang
Digital interoperability in logistics and supply chain management: state-of-the-art and research avenues towards Physical Internet
S. Pan, D. Trentesaux, D. McFarlane et al.
The Price of Robustness
D. Bertsimas, Melvyn Sim
Reinforcement Learning for Combinatorial Optimization: A Survey
Nina Mazyavkina, S. Sviridov, S. Ivanov et al.
The physical internet as a new supply chain paradigm: a systematic literature review and a comprehensive framework
Horst Treiblmaier, Kristijan Mirkovski, P. Lowry et al.
Toward a Physical Internet: meeting the global logistics sustainability grand challenge
Benoît Montreuil
Learning Optimal Crew Dispatch for Grid Restoration Following an Earthquake
Farshad Amani, Faezeh Ardali, Amin Kargarian Marvasti
Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon
Yoshua Bengio, Andrea Lodi, Antoine Prouvost
A Distributed Quantum Approximate Optimization Algorithm Simulator for Engineering Design Optimization
A. Rajabi, Milad Hasanzadeh, Amin Kargarian
On Robust Optimization
E. Köbis
Semi-Supervised Classification with Graph Convolutional Networks
Thomas Kipf, M. Welling
Event-Driven Deep RL Dispatcher for Post-Storm Distribution System Restoration
Farshad Amani, Faezeh Ardali, Amin Kargarian Marvasti
Resilience planning for Physical Internet enabled hyperconnected production-inventory-distribution systems
Xiaoshuai Peng, Shoufeng Ji, R. Thompson et al.