A Graph Neural Network--Guided Genetic Algorithm for Physical Internet Supply Chain Optimization under Cost Uncertainty

This study develops deterministic and min–max regret models for a three-echelon Physical Internet network of factories, hubs, and retailers, integrating 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. The paper formulates deterministic and min–max regret models 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. "In the proposed method, however, the GNN does not predict shipment quantities or replace mathematical optimization. It only guides the discrete factory–hub assignment search; all continuous flows are still determined by an exact linear program for each distinct assignment."

The study makes four contributions: (1) it formulates deterministic and min–max regret PI models that integrate single-source factory assignment, factory supply, lateral hub transshipment, retailer delivery, and shortage; (2) it develops a GNN-guided GA in which learned assignment probabilities improve population initialization and adapt mutation to prediction uncertainty; (3) it evaluates the method against simulated annealing (SA), a standard GA, and a non-learning cost-ranked warm start under matched seeds and common evaluation limits; (4) it distinguishes the instances used for GNN development from held-out and independently generated tests and supplements the tight-budget held-out study with a larger-budget, multi-generation experiment.

The deterministic model minimizes the sum of fixed factory assignments, factory supply, lateral transshipment, retailer delivery, and unmet-demand penalties, subject to factory capacity, single sourcing, factory eligibility, assignment-dependent inbound flow, hub material balance, and retailer demand balance constraints. Cost uncertainty is represented by coordinated lower, nominal, and upper scenarios, with multipliers of 0.8/1/1.2 for supply and fixed-assignment costs, 0.5/1/1.5 for transshipment, 0.9/1/1.1 for delivery, and 0.7/1/1.3 for shortage. The robust plan minimizes the maximum regret over the three scenarios.

The GNN uses a heterogeneous graph with factory, hub, and retailer nodes, type-specific encoders, and relation-specific multilayer perceptrons for factory–hub, hub–factory, hub–retailer, retailer–hub, and hub–hub relations. Messages are mean-aggregated and combined through residual, layer-normalized updates with ReLU activation for two rounds with hidden dimension 32. The final factory–hub edge scorer produces a compatibility logit, and assignment probabilities are computed via softmax over eligible factories. The GNN was trained on Instances 1–9, with Instances 10–12 used for validation and model selection. The selected model achieved 75.56% hub-level accuracy on validation instances; five independent training runs produced 73.78% ± 3.76%.

A chromosome contains one eligible factory index for each hub. Once fixed, the remaining deterministic or regret problem is a continuous linear program solved with the HiGHS solver. The GNN–GA includes the most likely chromosome, samples 80% of the effective population from learned probabilities, and fills the remainder uniformly. The effective population is Peff = min Pnom, B, omega, where B is the distinct-evaluation budget, Pnom is the nominal population, and omega is the assignment-space size. Prediction entropy and mutation are defined explicitly, with mutation probability µh = min 0.20, 0.05(0.5 + 1.5eh/H) for non-singleton eligibility. Tournament selection of size 3, uniform crossover with probability 0.8, and 5% elitism are identical in GA and GNN–GA.

Fifteen benchmark instances increase from (O, H, R) = (1, 3, 2) to (15, 90, 700). Instances 1–9 provide GNN training labels, Instances 10–12 are used for model selection, and Instances 13–15 are excluded from both stages. Exact references are available through Instance 13; Instances 14–15 use best-known incumbents. The tight-budget distinct-evaluation budgets are 64 and 256 for Instances 3–4; 500 for 5–10; and 250, 150, 75, 25, and 10 for 11–15. For held-out Instances 13–15, the populations are truncated from the nominal 100 to 75, 25, and 10, and the entire budget is consumed by initialization, so these runs complete no offspring generation. Their role is to test the quality of learned initialization under severe limits.

A separate experiment increases the evaluation limit for exact held-out Instance 13 to 400, uses a population of 100, and applies 10 matched seeds, permitting three complete offspring generations and a fourth, budget-limited generation. Three additional exact-solvable instances with dimensions (3, 10, 25), (4, 12, 30), and (5, 15, 40) were generated with independent seeds 202601–202603 after the model and search settings had been selected.

Results show that GNN–GA reached the exact deterministic reference in every run on training Instances 3–9 and produced the lowest mean objective on validation Instances 10–12. On tight-budget held-out Instances 13 and 15, GNN–GA wins all 20 paired runs against the cost-ranked baseline, whereas the cost warm start wins all 20 on Instance 14, indicating the learned model is usually beneficial but not uniformly better than a simple cost rule. In the 400-evaluation Instance-13 experiment, GNN–GA outperforms GA in every matched run for both formulations after three complete offspring generations and a partial fourth pass. On the three independent exact tests, all methods solve T1 exactly; GNN–GA has the lowest mean on both T2 formulations and deterministic T3, whereas SA is strongest on T3 regret and reaches the exact reference in 10 of 20 runs.

Ablation across the 26 nonsingleton tight-budget comparisons shows that full GNN–GA is better/tied/worse than the no-GNN control in 20/6/0 cases, initialization-only in 4/20/2, and the cost warm start in 16/8/2. Learned initialization is therefore the main source of improvement, while entropy-dependent mutation offers a smaller contribution and requires sufficient budget for offspring generations. With all three methods evaluated using the same single-threaded solver implementation, the held-out per-instance time ratios are TSA/TGNN = 3.476 and TGA/TGNN = 5.265 under the selected evaluation limits, excluding GNN training, loading the trained weights, and one-time model construction.

Across held-out Instances 13–15, all 12 paired comparisons of GNN–GA with SA or GA are significant after Holm correction. Across the 26 nonsingleton instance–formulation combinations, the three-method Friedman test is significant in 19 cases. The conclusions remain limited to synthetic single-period networks, complete eligibility and connectivity, and three coordinated cost scenarios. Future work should expand the exact held-out collection, introduce sparse and externally derived topologies, train on more formulation-diverse assignment labels, and study dynamic or mixed uncertainty.

Improvements to AI Systems:

1. Hybrid Learning-Optimization Architecture: Integrate a graph neural network (GNN) as a learned heuristic to guide discrete combinatorial search (e.g., genetic algorithm), while delegating continuous subproblems to an exact linear programming solver. The AI system can solve large-scale, mixed-integer continuous problems by reducing the search space without sacrificing optimality of continuous variables.

2. Uncertainty-Aware Search Initialization and Mutation: Use GNN-predicted assignment probabilities to seed the initial population and adapt mutation rates based on prediction entropy (e.g., higher entropy → more exploration). The improved system can balance exploitation of learned patterns with exploration in uncertain regions, leading to faster convergence and robust solutions under cost variability.

3. Min-Max Regret Optimization for Robust Planning: Implement scenario-based robust optimization that minimizes worst-case regret across coordinated cost scenarios (e.g., 0.8/1/1.2 multipliers). The AI system can generate plans that are resilient to cost fluctuations, ensuring near-optimal performance even in adversarial conditions.

4. Heterogeneous Graph Representation for Multi-Echelon Networks: Encode factories, hubs, and retailers as typed nodes with relation-specific message passing (e.g., factory–hub, hub–retailer, hub–hub). The improved system can learn transferable structural patterns in supply chain networks, enabling generalization to new topologies without retraining from scratch.

5. Budget-Aware Search with Distinct-Evaluation Control: Dynamically truncate population size and number of offspring generations based on a fixed evaluation budget (e.g., Peff = min Pnom, B, Ω). The AI system can operate under strict computational constraints, making it suitable for real-time or resource-limited deployment.

6. Transferable Initialization for Cold-Start Problems: Leverage GNN-based initialization to produce high-quality starting solutions when the evaluation budget is too small for any offspring generation (e.g., only 10–75 evaluations). The improved system can deliver competitive solutions in extreme low-budget scenarios, outperforming cost-ranked heuristics in most cases.

7. Ablation-Driven Model Selection: Use systematic ablation studies (e.g., full GNN–GA vs. no-GNN, initialization-only, cost warm start) to identify which components contribute most to performance. The AI system can self-diagnose its own strengths and weaknesses, guiding future architectural improvements.

What the Improved AI System Can Do:

• Solve three-echelon Physical Internet network design problems (factory–hub–retailer) with integrated decisions on assignment, supply, lateral transshipment, and shortage penalties, under both deterministic and uncertain cost scenarios.

• Generate robust plans that minimize worst-case regret, making it suitable for logistics networks facing volatile fuel, labor, or demand costs.

• Scale to networks with up to 15 factories, 90 hubs, and 700 retailers, achieving near-exact solutions within tight evaluation budgets (as low as 10–500 linear program solves).

• Generalize to unseen network topologies and instance sizes after training on only a small set of labeled examples, as demonstrated by held-out and independently generated tests.

• Operate in real-time or embedded settings where each candidate evaluation is expensive (e.g., solving a linear program), by using learned priors to avoid wasteful search.

• Provide explainable assignment probabilities per hub, enabling human planners to audit and adjust decisions based on model confidence.

• Automatically adapt its exploration-exploitation trade-off via entropy-based mutation, improving performance when more computational budget is available.

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.