Efficient Neural Neighborhood Search for Pickup and Delivery Problems

We define $h_{i}$ as the linear projection of its node features $l(x_{i})$ for any $x_{i}\in V$ with output dimension $d_{h}=128$.

By extending the absolute positional encoding in the vanilla Transformer Vaswani et al. (2017), the cyclic positional encoding (CPE) was proposed in Ma et al. (2021b), which enables Transformer to encode cyclic sequences (as our PDP solutions) more accurately. The PFE $g_{i}$ with output dimension $d_{g}=128$ are initialized by CPE as follows,

where superscript $d$ of ${g_{i}}^{(d)}$ refers to the $d$-th dimension of $g_{i}$, and the scalar $z(i)$ as well as the angular frequency $\omega_{d}=\frac{2\pi}{T_{d}}$ are defined accorting to Eq. (3) and Eq. (4), respectively.

According to Ma et al. (2021b), directly fusing the two sets of embeddings (i.e., $h_{i}\!+\!g_{i}$) may cause undesired noises to the vanilla self-attention. As shown in Figure 3(a), they thus proposed the DAC-Att in ways that each embedding set independently computes attention scores and shares the other aspect to learn dual-aspect representations. Different from it, we propose a simple and generic mechanism by incorporating a multilayer perception (MLP). As shown in Figure 3(b), besides the original self-attention scores (the orange squares), multiple auxiliary attention scores learned from other feature embeddings (the blue squares) are leveraged and fed into an element-wise MLP, which allows it to synthesize heterogeneous attention relationships into comprehensive ones. We call it Synthesis Attention (Synth-Att). It is able to not only leverage more attention scores from various feature embeddings, but also achieve competitive performance to DAC-Att with less computation costs. Below, we present more details.

In our N2S, PFEs are used to generate multi-head auxiliary attention scores as follows,

where $W^{Q_{\text{aux}}}_{m}\in\mathbb{R}^{d_{g}\times d_{q}},W^{K_{\text{aux}}}_{m}\in\mathbb{R}^{d_{g}\times d_{k}}$ are trainable matrices for each head $m$. We set $m=4$ and $d_{q}=d_{k}=d_{g}/m$.

The Syn-Att is defined as follows,

In specific, it first computes the multi-head self-attention scores $\alpha_{i,j,m}^{\text{self}}$ for NFEs based on the trainable matrices $W^{Q}_{m}\in\mathbb{R}^{d_{h}\times d_{q}}$ and $W^{K}_{m}\in\mathbb{R}^{d_{h}\times d_{k}}$ for head $m$ using Eq. (7) as

Thereafter, the attention scores $\alpha^{\text{aux}}$ and $\alpha^{\text{self}}$ are fed into a three-layer MLP with structure ($2m\times 2m\times m$) to compute the synthesized multi-head attention scores as follows,

The scores are then normalized to $\tilde{\alpha}_{i,j,m}$ through Softmax, which are further used to calculate the attention values for each head as Eq. (9). Finally, the outputs are given by Eq. (10) with trainable matrix $W^{O}\in\mathbb{R}^{md_{v}\times d_{h}}$ ($d_{v}=d_{h}/m$).

We stack $L$ ($L$=3) encoders, each of which is the same as the Transformer encoder, except that the vanilla multi-head self-attention is replaced with our multi-head Synth-Att and we use the same instance normalization layer as Ma et al. (2021b). Note that the auxiliary attention scores $\alpha_{i,j,m}^{\text{aux}}$ are only computed once and shared among all stacked encoders to reduce the computation costs.

Given the enhanced embeddings $\{\hat{h}_{i}\}_{i=1}^{|V|}$ and the set $\mathcal{H}(t,K)$, the removal decoder outputs a categorical distribution over $n$ requests for removal action. In specific, it first computes a score $\lambda_{i}$ for each $x_{i}\in V$ indicating the closeness between node $x_{i}$ and its neighbors as

where $\text{pred}(x_{i})$ and $\text{succ}(x_{i})$ refer to the predecessor and the successor nodes of $x_{i}$, respectively, and $W^{Q}_{\lambda}\in\mathbb{R}^{d_{h}\times d_{h}}$, $W^{K}_{\lambda}\in\mathbb{R}^{d_{h}\times d_{h}}$. We use multi-head technique to obtain $\lambda_{i,1}$ to $\lambda_{i,m}$. Then the decoder aggregates the scores for each pickup-delivery pair ($i^{+},i^{-}$) based on a three-layer MLP_λ,

where the MLP structure is ($2m\!+\!4$, 32, 32, 1), scalar $c(i)$ counts the frequency of request $(i^{+},i^{-})$ being selected for removal in the past $K$ steps, and $\mathds{1}_{\text{last}(t)=i^{\prime}}$ is a binary variable indicating whether request $i^{\prime}$ was selected at the $t$-th last step. An activation layer ${\hat{\Lambda}}\!=\!C\cdot\text{Tanh}(\tilde{\Lambda})$ is then applied ($C\!=\!6$), followed by Softmax to normalize the distribution which is then used to sample a node pair ($i^{+},i^{-}$) as removal action.

Given a request $(i^{+},i^{-})$ for removal, the reinsertion decoder outputs the joint distribution that reinserts the two nodes back to the solution. We first define two scores $\mu^{\text{p}}(x_{\alpha},x_{\beta})$ and $\mu^{\text{s}}(x_{\alpha},x_{\beta})$ for a node $x_{\alpha}$ indicating the degree of preference of accepting a node $x_{\beta}$ as its new predecessor and successor nodes, respectively,

where $W^{Q_{\text{p}}}_{\mu},W^{Q_{\text{s}}}_{\mu}\!\in\!\mathbb{R}^{d_{h}\times d_{h}}$, and $W^{K_{\text{p}}}_{\mu},W^{K_{\text{s}}}_{\mu}\!\in\!\mathbb{R}^{d_{h}\times d_{h}}$. Again, we use multiple heads. Based on the scores, the decoder predicts the distribution of reinserting node $i^{+}$ after node $j$, and reinserting node $i^{-}$ after node $k$ using $\text{MLP}_{\mu}$,​

where the MLP structure is ($4m$, 32, 32, 1). Note that here $\text{pred}(\cdot)$ and $\text{succ}(\cdot)$ should be considered in the new solution where nodes $i^{+},i^{-}$ have already been removed. Afterwards, ${\hat{\mu}}=C\cdot\text{Tanh}(\tilde{\mu})$ is applied and infeasible choices are masked as $-\infty$ before normalizing by Softmax. Finally, a node pair $(j,k)$, as the reinsertion action, is sampled according to the resulting distribution to indicate the positions of reinserting the node-pair $(i^{-},i^{+})$ back to the solution.

Given the embeddings $\{\tilde{h}_{i}^{(L)}\}_{i=0}^{|V|}$ from policy network $\pi_{\theta}$, the critic network first enhances them by a vanilla multi-head attention layer (with $m=4$ heads) to get $\{y_{i}\}_{i=0}^{|V|}$. The enhanced embeddings are then fed into a mean-pooling layer in Wu et al. (2021) to aggregate the global representation of all embeddings into each individual one as

where we use trainable matrices $W_{v}^{\textit{Local}},W_{v}^{\textit{Global}}\in\mathbb{R}^{d_{h}\times\frac{d_{h}}{2}}$. Lastly, the state value $v(s_{t})$ is output by a four-layer MLP in Eq. (17) with structure (129, 128, 64, 1). Here, $f(\delta^{*})$ is added as an additional input to $\text{MLP}_{v}$.

We train N2S for $E$ epochs and $B$ batches per epoch, where the training dataset $\mathcal{D}_{b}$ is randomly generated on the fly with the uniform distribution (line 3). Following Ma et al. (2021b), we introduce a similar CL strategy (in lines 4 to 6) to further ameliorate the training. In specific, it improves the randomly generated solutions $\{\delta_{i}\}$ to $\{\delta^{\prime}_{i}\}$ by running the current policy $\pi_{\theta}$ for $T={e}/{\rho^{CL}}$ steps. The improved solutions $\{\delta^{\prime}_{i}\}$ with higher quality are then used to initialize the first state $s_{0}$. In such a way, the hardness level of neighborhood search is gradually increased per epoch following the idea of curriculum learning. The remaining algorithm follows the original design of the n-step PPO, where we present the reinforcement learning loss function in Eq. (18), and the baseline loss function of critic in Eq. (19), respectively. Here, we clip the estimated value $\hat{v}(s_{t})$ around the previous value estimates using $v_{\phi}^{clip}(s_{t^{\prime}})=clip\left[v_{\phi}(s_{t^{\prime}}),v_{old}(s_{t^{\prime}})-\varepsilon,v_{old}(s_{t^{\prime}})+\varepsilon\right]$.

Our N2S is trained with $E\!=\!200$ epochs and $B\!=\!20$ batches per epoch using batch size 600. We set $n\!=\!5$, $T_{\text{train}}\!=\!250$ for the $n$-step PPO with $\kappa\!=\!3$ mini-batch updates and a clip threshold $\epsilon\!=\!0.1$. Adam optimizer is used with learning rate $\eta_{\theta}\!=\!8\!\times\!10^{-5}$ for $\pi_{\theta}$, and $\eta_{\phi}\!=\!2\!\times\!10^{-5}$ for $v_{\phi}$ (decayed $\beta\!=\!0.985$ per epoch). The discount factor $\gamma$ is set to 0.999 for both PDPs. We clip the gradient norm to be within 0.05, 0.15, 0.35, and set the curriculum learning $\rho^{CL}$ to 2, 1.5, 1 for the three problem sizes, respectively.

Table 3 shows the results on PDTSP. In the first group, we compare N2S with Heter-AM (greedy and sampling), and DACT. Compared to Heter-AM (5k), our N2S with only 1k steps attains lower gaps with less time for all sizes. Although DACT offers the best gap on PDTSP-21, its performance drops significantly as the problem size increases, partly because its decoder is less efficient than our node-pair removal and reinsertion ones when tackling larger-scale problems. Instead, our N2S achieves higher performance and consistently dominates DACT in terms of both the gaps and the time on PDTSP-51 and PDTSP-101. In the second group, our augmented N2S-A is compared to the upgraded Heter-POMO method with three variants⁹⁹9Heter-POMO (gr.), Heter-POMO-A (gr.), Heter-POMO-A (3k) refer to: greedily generate $|V|$ solution; greedily generate $|V|$ solutions with 8 augments; sample $|V|\times$3k solutions with 8 augments.. It is shown that even with only 1k steps, our N2S-A attains a significantly smaller gap than all three Heter-POMO variants, by almost an order of magnitude. Although Heter-POMO-A (gr.) tends to be competitive with fast speed, the gap is hard to be further reduced by increasing inference time if we refer to Heter-POMO-A (3k). Moreover, our N2S-A (2k) keeps abreast of, or even slightly exceeds the strong LKH3 solver, achieving gaps of -0.03% and -0.01% with less time on PDTSP-51 and PDTSP-101, respectively. Those gaps are further reduced to -0.04% and -0.20% with more steps, i.e., 3k.

In Table 4, we report the results on PDTSP-LIFO. Due to the more constrained search space, DACT failed to work well (see Table 6). Therefore, we mainly compare our N2S-A with Heter-POMO (the best neural baseline in Table 3) and the LKH3 solver. As exhibited, the advantages of neural methods over LKH3 have been further enhanced on this harder problem, where our approach consistently outperforms Heter-POMO for all sizes. Compared to LKH3, our N2S-A with 3k steps presents superior performance again, and attains gaps of -0.64% and -1.47% on PDTSP-LIFO-51 and PDTSP-LIFO-101, respectively.

We replace the proposed Synth-Att in our N2S encoder with vanilla-Att and DAC-Att, respectively. Using only one GPU card, we report the number of model parameters, time, and gaps for solving 2,000 PDTSP-51 instances with 3k steps in Table 5. As exhibited, Synth-Att attains slightly smaller gaps than DAC-Att with much fewer computation costs, and considerably lower gaps than vanilla-Att with slight extra computation costs.

To highlight the desirability of our two decoders, we replace the trainable decoders with hand-crafted ones (i.e., random and the $\epsilon$-greedy with $\epsilon\!=\!0.1$) while ensuring feasibility. We gather the results on PDTSP-51 and PDTSP-LIFO-51 with 3k steps in Table 6 where mark ‘✓’ means our proposed decoder is used (the one without augments) and mark ‘✗’ means the decoder in the parentheses is used instead. As revealed, the methods of retaining at least one trainable decoder always attain much lower gaps than the ones equipped with only hand-crafted decoders. The method with both trainable decoders (i.e., N2S) achieves the best performance. We also notice that DACT fail to solve PDTSP-LIFO well. This might be because its decoder considers removing and reinserting only one node instead of a pickup-delivery node pair in each action, which is a serious limitation for more constrained PDPs. For example, on PDTSP-LIFO, over 92% of the action space need to be masked for DACT, which leads to extremely low efficiency.