Efficient Neural Neighborhood Search for Pickup and Delivery Problems
Authors: Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Hongliang Guo, Yuejiao Gong, Yeow Meng Chee
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our N2S is generic, and extensive experiments on two canonical PDP variants show that it can produce state-of-the-art results among existing neural methods. Moreover, it even outstrips the well-known LKH3 solver on the more constrained PDP variant. |
| Researcher Affiliation | Collaboration | 1National University of Singapore 2Singapore Institute of Manufacturing Technology, A*STAR 3Institute of Marine Science and Technology, Shandong University 4Institute for Infocomm Research, A*STAR 5South China University of Technology |
| Pseudocode | Yes | Algorithm 1 n-step PPO with CL strategy Algorithm 2 N2S-A Inference |
| Open Source Code | Yes | Our implementation for N2S is available online1. 1Code is available at https://github.com/yining043/PDP-N2S. |
| Open Datasets | Yes | We evaluate N2S on PDTSP and PDTSP-LIFO... where the node coordinates of instances are randomly and uniformly generated in the unit square [0, 1] [0, 1]... We further evaluate our N2S on benchmark instances, including all the ones from [Renaud et al., 2002] for PDTSP and the ones with size |V| ≥ 201 from [Carrabs et al., 2007] for PDTSP-LIFO |
| Dataset Splits | No | The paper specifies training and test datasets ('All baselines are evaluated on a test dataset with 2,000 instances'), but does not explicitly mention a separate validation dataset split or its size/proportion in the main text. |
| Hardware Specification | Yes | Our experiments were conducted on a server equipped with 8 RTX 2080 Ti GPU cards and Intel E5-2680 CPU @ 2.4GHz. |
| Software Dependencies | No | The paper mentions 'Adam optimizer' but does not specify version numbers for any programming languages, libraries, or other software components used in the experiments. |
| Experiment Setup | Yes | Our N2S is trained with E = 200 epochs and B = 20 batches per epoch using batch size 600. We set n=5, Ttrain =250 for the n-step PPO with κ=3 mini-batch updates and a clip threshold ϵ=0.1. Adam optimizer is used with learning rate ηθ =8·10−5 for πθ, and ηϕ =2·10−5 for vϕ (decayed β = 0.985 per epoch). The discount factor γ 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 ρCL to 2, 1.5, 1 for the three problem sizes, respectively. |