Nicolas Smits

Graph RL for resilient supply chains

Master’s thesis, CMUwith Arsh Bhatia and Carl D. Laird2026 – present

Disrupted supply chain

Illustrative 9-node episode. A trace exported from the trained policy replaces it.

Network design agent

Node and arc embedding

hi,hj
embeddings of the arc’s two endpoints, from two GATv2 rounds
ρk
share of the arc budget left at step k
eij
arc features: lead time, priority, cost
gψ
one MLP, shared by every candidate arc
Q(sk,aij)
predicted gain in design value V from adding arc i→j

Motivation

Supply chains survive the loss of a plant, a warehouse or a lane mostly through redundant transport links, and what a link is worth depends on what the network does after the failure. Design models usually assume a planner who re-optimises every flow once the failure is known. Real networks follow fixed rules for reordering and allocating stock, so a link that looks redundant under perfect re-planning can matter a great deal under those rules, and the reverse.

Formulation

A network of plants, warehouses and customers may gain at most K candidate arcs. Plants, warehouses and arcs fail independently for the whole horizon; warehouses reorder by an (s, S) policy and stock is allocated by lane priority. The backlog B(x, ω) of design x in failure scenario ω is the demand still unmet at the end. A design is scored by the share of baseline backlog it removes, net of a weighted arc cost:

V(x)=B0−𝔼ω[B(x,ω)]B0−λCref|𝒞|∑a∈𝒜‾caxa,maxx∈𝒳⁡V(x)

Every value is a sample average over a fixed set of failure scenarios, so the designs of one network are compared on common random numbers.

Held-out design value by network size for the learned policy, greedy search and random baselines
Held-out design value by network size, mean and 95% interval: the policy in red, greedy search in black. Shaded sizes are larger than any training network.Crop of the thesis poster; to be redrawn in the site palette.

Upper bound

Re-planning every flow optimally turns each scenario into a linear programme whose backlog is never higher than the rule's, so it bounds every design's value from above. On small generated networks it clears all backlog in more than 90% of scenarios, while the rule leaves backlog even when nothing fails. The bound is valid but it is not a stand-in for the real problem.

Median CPU time to design one network, greedy search against the learned policy, log scale
Median CPU time to design one network, on a log scale.Crop of the thesis poster; to be redrawn in the site palette.

Learned policy

Each design needs a simulation over many scenarios, and the number of designs grows combinatorially, so even greedy search takes hours at 70 nodes. The policy builds a design one arc at a time, with an explicit stop, and is rewarded by each arc's change in value, so an episode's return is the design's value. Trained once on small networks, it is applied without retraining to networks four times larger.

Amortised cost

Greedy search pays its full cost again for every network, about six CPU-hours at 70 nodes. The policy pays once, six to seven hours of training per seed, and then about one CPU-second per network, including networks four times larger than any it trained on.

Cumulative computeNetworks designedtraining,paid onceGreedy searchLearned policy
Cumulative compute against networks designed, schematic.

Architecture

The policy reads the network as a graph: seven features per node (tier, safety stock, storage and production capacity, throughput) and three per arc (lead time, priority, cost). Two GATv2 rounds give every node an embedding. For each candidate arc, one shared network reads both endpoint embeddings, the remaining budget and the arc's own features, and returns that arc's Q-value. The best arc is added only if its value is positive; otherwise the design stops:

h=fθ(X,E),Q(sk,aij)=gψ(hi‖hj‖ρk‖eij),ak={arg⁡maxa⁡Q(sk,a)if maxa⁡Q(sk,a)>0stopotherwise

No weight depends on the number of nodes or arcs, so the same 28,481 parameters design networks of 19 and 70 nodes. Training is Double DQN with experience replay.

Further reading