Learning-Augmented Optimization for Strategic Two-Echelon Spare Parts Network Design

1 Introduction

• Candidate topologies are difficult to evaluate because their inventory and shipment outcomes require an expensive lower-level model, making joint optimization computationally prohibitive at the considered scale.The strategic design partitions sites into clusters and selects a central replenishment site for each cluster.Source: §1 · p. 2
• The framework represents clusters as attributed graphs, trains an ensemble of GNN surrogates on exact evaluations, and uses variable neighborhood search to explore candidate designs.A lower quantile of ensemble predictions scores candidates, and search-discovered clusters are recombined by set partitioning before exact re-evaluation.Source: §1 · p. 3
• The framework uses exact evaluations to train the surrogate and validate the final design, while surrogate guidance explores a larger design space.The paper also assesses surrogate choice through the exact quality of designs produced during search.Source: §1 · p. 3
• Because search favors candidates with high predicted savings, the paper compares candidates using a lower ensemble-prediction quantile rather than the mean to limit the influence of optimistic errors.The study also evaluates predictive performance on search-generated candidates and under geographic distribution shift.Source: §1 · p. 3
• 30.5% higher combined savings than an optimization-based baseline constructed from exact evaluations, with average service of 99.8% across six independent replications.The case study uses Amazon’s North American fulfillment-center network.Source: §1 · p. 3

2.1 Multi-echelon spare parts inventory systems

• Multi-echelon spare-parts research develops operational and tactical models, while much of the literature treats network structure as given.Prior design work considers network structure but does not address large combinatorial design with expensive lower-level inventory evaluation.Source: §2.1 · pp. 4–5

2.2 Learning-augmented optimization for expensive network design

• Optimistic errors can matter disproportionately because search favors candidates with attractive predicted values, potentially widening the gap between predictive accuracy and decision quality.This motivates examining scoring rules when several surrogate estimates are available.Source: §2.2 · p. 6
• Learning-augmented optimization motivates evaluating predictive models by downstream decision quality, but limited work examines how surrogate representation and scoring affect combinatorial search decisions.The paper addresses this gap with graph-based surrogates, conservative scoring, combinatorial search, and exact evaluation of the final network.Source: §2.2 · p. 6

3 Problem Setting and Decision Structure

• The design selects central sites and partitions assigned leaf sites into clusters, while sites may remain in the incumbent single-echelon system.Feasible assignments are subject to operational conditions including distance requirements and minimum cluster size.Source: §3 · pp. 6–7
• Strategic, tactical, and operational decisions are coupled: topology shapes lead times and pooling, which shape inventory policies and subsequent shipment decisions.Joint optimization is computationally prohibitive because tactical and operational decisions must be repeatedly evaluated for candidate topologies.Source: §3 · p. 6
• The objective is to improve system performance over the incumbent single-echelon configuration while preserving high service, using expensive lower-level evaluation rather than geography alone to assess each topology.A topology determines both the partition of sites and the central site within each cluster.Source: §3 · p. 7

4 Lower-Level Evaluation Model

• The lower-level model evaluates a fixed two-echelon topology by determining its tactical inventory policies and induced operational shipment decisions.The present paper uses this evaluator to choose the strategic configuration, extending work that optimizes operations for a given configuration.Source: §4 · p. 7
• The model maps site assignments, central-site identity, assortments, demand, lead times, and costs to inventory, shipment, and service outcomes.For a fixed cluster, the central site replenishes from the external supplier and leaf sites replenish from the central site.Source: §4 · p. 7
• The lower-level formulation is a multi-item, multi-period mixed-integer program solved directly in the production evaluator.The model uses Sample Average Approximation, with policy and shipment constraints required to hold for every demand scenario.Source: §4 · p. 8
• Exact cluster evaluation is feasible individually but becomes prohibitively expensive when repeated across many alternative topologies.Runtime depends on factors including demand scenarios, spare parts, stocking locations, binary decisions, and cluster size.Source: §4 · p. 9
• Exact evaluations provide purchase-order spend, average stock value, and service level, and are used to label candidate clusters, assess searched networks, and re-evaluate final designs.The reported service level is the fraction of weeks in which demand is met from available stock, averaged across scenarios.Source: §4 · pp. 8–9

5.1 Exact generation and labeling of candidate clusters

• Exact cluster evaluations label candidates and provide objective coefficients for the initial network; the same operational model supplies the surrogate's training data.Clusters are generated under business feasibility requirements, including minimum size and maximum admissible central–leaf distance.Source: §5.1 · pp. 9–10

5.2 Initial feasible network via set partitioning

• The initial set-partitioning model selects nonoverlapping, exactly evaluated clusters as a strong baseline, while allowing sites without a good cluster to remain uncovered.Uncovered sites stay in the incumbent single-echelon configuration, and the model can leave sites uncovered when its finite library lacks suitable clusters.Source: §5.2 · pp. 11–12

5.3 Graph representation of candidate clusters

• Candidate clusters are attributed graphs because cluster value depends on site attributes and relationships, including proximity, assortment overlap, and central-site choice.Node features describe site characteristics; edge features capture relationships such as assortment commonality and cost interactions.Source: §5.3 · p. 12

5.4 Graph neural network surrogate

• The graph surrogate uses edge-conditioned attention message passing, permutation-invariant pooling, and an MLP to predict cluster-level cost-related metrics.This architecture preserves relationships among sites instead of treating a cluster as an unordered set of aggregate statistics.Source: §5.4 · pp. 12–13

5.5 Conservative GNN ensemble

• The conservative ensemble scores candidates with a lower quantile of member-level predicted economic values rather than their mean, reducing the influence of optimistic predictions during search.The scoring rule is evaluated by the exact quality of the network designs it produces.Source: §5.5 · pp. 13–14

5.6 Surrogate-assisted search

• Variable neighborhood search alternates diversification and local improvement, accepting a candidate when its surrogate score exceeds the incumbent's and otherwise moving to a larger neighborhood.Moves include changing central sites, transferring sites between clusters, splitting clusters, and merging or dissolving them when feasible.Source: §5.6 · p. 14

5.7 Final refinement and exact validation

• After search, set partitioning recombines visited candidate structures using arm-specific surrogate scores, and the selected network is re-evaluated with the exact lower-level model.Exact evaluation ensures reported final-network performance does not depend on surrogate approximation.Source: §5.7 · pp. 14–15

6.1 Experimental setting and evaluation protocol

• The 246-site case study compares surrogate-guided search with a constructive Net-baseline built by set partitioning over exactly evaluated clusters, and assesses resulting designs with exact lower-level evaluation.The exact cluster evaluations also provide training labels; the surrogate guides exploration rather than determining reported network performance.Source: §6.1 · pp. 15–16

6.2 Surrogate accuracy and conservative scoring

• On held-out clusters, the GNN’s average R2 was 0.955 versus XGBoost’s 0.934; 30th-percentile scoring changed average R2 only to 0.954.The GNN had the highest predictive accuracy among the models considered, while the random-split results did not establish accuracy on search-generated configurations.Source: §6.2 · p. 17, Figure 2 · p. 18

6.3 Generalization Under Distribution Shift

• Average R2 was 0.919 for large-cluster holdouts versus 0.955 for random splits, but 0.802 for central-site and 0.343–0.785 for geographic holdouts; PO-spend R2 was negative in Central and Southeast.In the conservative-score production run, the search visited 18,271 distinct cluster compositions, only 48 (0.3%) of which were in the labeled library; exact evaluation of all visited configurations would require more than 3,000 machine-hours under the stated assumption.Source: §6.3 · pp. 18–19, Table 2 · p. 20

6.4 Surrogate performance on search-generated candidates

• Across 300 search-generated clusters, the conservative GNN achieved R2 0.84 and Spearman rank correlation 0.91; among top-5% candidates, R2 fell to 0.74 and rank correlation to 0.85.Mean signed error was negative in all three strata, and 24% of top-5% candidates were overestimated.Source: §6.4 · pp. 20–21, Table 3 · p. 21
• For top-5% search candidates, the GNN achieved R2 0.74 and Spearman rank correlation 0.85, versus XGBoost’s 0.48 and 0.55.The GNN also outperformed XGBoost on randomly visited clusters: R2 0.88 and rank correlation 0.93, versus 0.82 and 0.87.Source: §6.4 · p. 21, Table 4 · p. 21
• Among top-5% search candidates, conservative scoring reduced the overestimation rate to 24%, versus 78% under mean aggregation.The candidate set and ensemble predictions were held fixed; the 30th-percentile score also had negative mean signed error across all three candidate strata.Source: §6.4 · pp. 22–23, Table 5 · p. 22

6.5 Component analysis: what drives decision quality

• Using lower-quantile scoring rather than mean aggregation increased mean exact total savings by 4.5 percentage points for XGBoost and 5.1 for GNN, while reducing overestimated selected clusters from 76% to 39% and 68% to 28%, respectively.The GNN also had higher rank correlation with exact cluster values than XGBoost under both scoring rules.Source: §6.5 · pp. 23–24
• Under mean scoring, GNN mean exact total savings were 25.4% above the Net-baseline versus 17.4% for XGBoost; under conservative scoring, they were 30.5% versus 21.9%.These are six-run means; the GNN exceeded XGBoost by 8.0 percentage points under mean scoring and 8.6 percentage points under conservative scoring.Source: §6.5 · p. 23, Table 6 · p. 24
• The distance-based p-median benchmark's economic objective was 49.9% below the Net-baseline, but comparison is cautious because it requires full eligible-site coverage while the Net-baseline permits selective participation.The Net-baseline may subsequently increase coverage through the completion procedure.Source: §6.5 · pp. 24–25

6.6 End-to-end network performance: overall results

• 30.5% mean exact total savings improvement over the exact Net-baseline after final set-partitioning recombination, up from 27.4% after GNN-guided conservative search; average service was approximately 99.8%.Both results use exact evaluation of the two-echelon lower-level model.Source: Table 8 · p. 25, §6.6 · p. 25
• Final recombination increased mean cluster count from 27 to 28 and reduced maximum cluster size from 17 to 14; the validated topology varied centralization by region.Some regions consolidated around relatively large central sites, while others retained smaller, more localized clusters.Source: §6.6 · pp. 25–26, Figure 4 · p. 26

7 Discussion and Conclusions

• 30.5% higher combined savings than the exact-cluster-evaluation optimization baseline, with average service of approximately 99.8%.The reported result is from the Amazon case study.Source: §7 · p. 26

7.1 Managerial insights

• Geographic proximity alone misses the inventory and purchasing consequences of topology, while the validated network varies in centralization across regions.The discussion favors accounting for operational and economic consequences and allowing structures to adapt to local conditions.Source: §7.1 · p. 27
• Prediction and ranking deteriorate on high-scoring search-generated candidates, so decision quality should complement conventional predictive metrics in evaluation.Component experiments also find differences in exact downstream savings across surrogate and scoring choices.Source: §7.1 · p. 27
• Learning expands candidate exploration, while set-partitioning recombination and exact lower-level evaluation support feasibility and reliable assessment.The paper presents these as complementary roles in strategic design.Source: §7.1 · p. 27

7.2 Limitations and future research

• The lower-level evaluator could add workload concentration, warehousing, transportation coordination, dynamic inventory responses, and richer shipment or expediting decisions.Alternative multi-echelon structures could also test recommendation robustness under different operating assumptions.Source: §7.2 · p. 28
• The computational study covers fulfillment centers; broader networks could examine middle-mile and last-mile facilities and their distinct roles and constraints.Source: §7.2 · p. 28
• Search-generated structures can differ from initial training configurations across geographic or operating regimes; selective exact evaluation and periodic updating are proposed for robustness.The proposed adaptive procedure aims to control additional exact evaluations.Source: §7.2 · p. 28

7.3 Concluding remarks

• The framework combines graph-based exploration, conservative scoring, recombination, and exact final validation for strategic operations problems with expensive candidate evaluations.The conclusion presents the approach as extending beyond spare parts applications.Source: §7.3 · p. 28, §7.2 · p. 28

• The appendix documents implementation details for the graph neural network surrogate introduced in Section 5.Source: A Surrogate Model Implementation Details · p. 33
• The surrogate approximates the lower-level evaluation model.Source: A Surrogate Model Implementation Details · p. 33
• Its purpose is to provide that approximation at negligible computational cost during search.Source: A Surrogate Model Implementation Details · p. 33

A.1 Architecture and outputs

• The surrogate uses an attention-based graph neural network of the GATv2 family, with cluster graphs represented by node and edge features.Source: §A.1 · p. 33
• The architecture has four graph-convolution layers with hidden dimension 32, followed by global add pooling and a two-layer multilayer perceptron.The first two graph-convolution layers use two attention heads and dropout rate 0.2; the remaining layers use a single head.Source: §A.1 · p. 33
• Service level is excluded from the surrogate targets because it varies little across evaluated clusters and remains consistently high in lower-level solutions.The implementation predicts four lower-level business metrics.Source: §A.1 · p. 33

A.2 Training details

• The 3,513-cluster graph dataset is split 80%/10%/10% into training, validation, and test sets at cluster level to prevent leakage across observations.The appendix also specifies standardization, mean-squared-error training, AdamW, and validation-based early stopping.Source: §A.2 · pp. 33–34
• Five independently initialized GNNs estimate uncertainty, and a lower-quantile score penalizes candidate savings not consistently supported across ensemble members.The member-level net economic value combines predicted cost components; the conservative score uses τ = 0.3.Source: §A.2 · p. 34

B.1 Generation of the candidate cluster library

• The candidate library combines p-center partitions across five proximity measures with varied cluster configurations, random feasible samples, and central-site variants.After exact evaluation, feasibility filtering, and deduplication, the library contains 3,513 unique feasible clusters for training and the initial set-partitioning pool.Source: §B.1 · pp. 34–35

B.2 Completion of the initial set partitioning solution

• A finite candidate-cluster library can leave sites uncovered, so the completion procedure separates isolated from non-isolated sites and builds provisional clusters for the latter.If the non-isolated set is smaller than the minimum cluster size, it is folded into the isolated set.Source: §B.2 · pp. 35–36
• Remaining sites are assigned to the nearest selected feasible center subject to distance, capacity, and site-specific restrictions; unassigned sites are left for the metaheuristic.The center must be within the maximum distance and its cluster below the maximum size.Source: §B.2 · p. 36

B.3 Variable neighborhood search: top-level algorithm

• The VNS alternates shaking with local search, returning to the first neighborhood after an improvement and otherwise advancing to the next.It retains the best solution found under the surrogate objective.Source: §B.3 · p. 37

B.4 Neighborhood structures

• The four neighborhoods swap or double-swap sites, break a cluster to create a minimum-size cluster, or merge a cluster and reassign its sites.Merge assignments use a randomized multi-criteria rule.Source: §B.4 · pp. 37–38
• After each shaking move, local search checks whether a leaf site offers a better feasible central site for each cluster under the surrogate objective.This re-optimizes center identity within clusters.Source: §B.4 · p. 38

B.5 Final set partitioning and exact validation

• Retained clusters from promising search structures form an enriched pool, and an optimal selective-coverage set partitioning model recombines them using mean or lower-quantile surrogate values.Mean-scoring arms use the mean member-level predicted economic value; conservative-scoring arms use the lower-quantile value bδ0.3.Source: §B.5 · p. 38
• The set-partitioning optimum is exact only for its surrogate-valued model; the selected network is re-evaluated with the exact lower-level model for reported business performance.Search-generated cluster coefficients are not all exact lower-level evaluations.Source: §B.5 · p. 38

B.6 Search Convergence and Dispersion

• Six independent full-pipeline replications per arm each train a five-member ensemble, run 100 VNS restarts of 100 steps, and produce one network for the reported mean and standard deviation.Arm-level statistics are computed across the six final networks.Source: §B.6 · p. 38
• Figure 5 plots normalized surrogate-objective trajectories for the ten best of 100 restarts and the distribution of final improvements relative to the Net-baseline.The diagnostic uses the Net-baseline initialization and conservative-scoring GNN ensemble; the best observed objective is scaled to 1.00.Source: §B.6 · p. 38, Figure 5 · p. 39
• High-quality solutions emerge progressively, but stochastic outcomes vary, so these plots provide descriptive evidence rather than a stability guarantee.That variability motivates replicated evaluation with exact lower-level validation.Source: §B.6 · p. 39