
We replace the self-attention layers with graph neural networks (GNN)[1]} which can work with explicit edge weights, e.g. the travel times in case of the VRPTW.

We apply the GNN only to a spatial neighborhood \(\mathcal {H}_i\)  of each customer node \(i\)  which consists of a fixed number \(k\)  of nearest neighbors, thereby reducing the complexity from \(N^2\)  to \(Nk\) . Since these neighborhoods do not change we can pre-compute static node embeddings \(\tilde{x}_i^{\text{stat}}\)  in the first forward pass and keep them fixed for the complete decoding procedure:
\(\tilde{x}_i^{\text{stat}} = \operatorname{GNN}_{\text{stat}}\left(\mathcal {H}_i^{\text{stat}}\right).\) 
Stacking several such GNN layers increases the spatial resolution of the model w.r.t. the neighborhoods.

We add an additional GNN which creates a dynamic node embbedding based on the neighborhood \(\mathcal {H}_{r^{(t)}, i}\)  of route \(r\)  and node \(i\)  at step \(t\) , i.e. the incoming and outgoing edge of node \(i=2\)  in route \(r^{(t)}=(0, 2, 7, 5)\)  would be the set of edges \(\lbrace (0,2), (2,7)\rbrace \) . Accordingly:
\(\tilde{x}_i^{\text{dyn}} = \operatorname{GNN}_{\text{dyn}}\left(\mathcal {H}^{\text{dyn}}_{r^{(t)}, i}\right).\) 
The final node embedding is then created by simple summation of the embeedings:
\(\tilde{x}_i^{(t)} = \tilde{x}_i^{\text{stat}} + \tilde{x}_i^{\text{dyn}}\) .

We also introduce neighborhoods to the decoding procedure to reduce the size of the original action space of JAMPR.
We define the action neighborhood of route \(r\)  as \(\mathcal {H}^{\text{a}}_{r^{(t)}} = \mathcal {H}_j \cup \lbrace 0\rbrace \) , where \(j\)  is the last node in route \(r^{(t)}\)  and 0 is the depot. Then the new action space is given by
\(A^{\prime } = \lbrace (r, i) \in \text{feasible}(R^{(t)}_{\kappa } \times \mathcal {H}^{\text{a}}_{r\in R^{(t)}_{\kappa }}) \rbrace \) .

Finally, we follow POMO[2]} in replacing the original stochastic sampling procedure based on the softmax scores with a greedy decoding of multiple trajectories, which are created by sampling different configurations of start nodes for routes. To make the approach work with TW and multiple parallel routes we sort the nodes in the depot neighborhood \(\mathcal {H}_0\)  by the TW start time \(t_i\)  and randomly sample \(\kappa \)  start nodes from the 25% earliest. Accordingly, we finally also change the original rollout baseline of [3]} to the mean reward of the POMO trajectories.

