Efficient Neural Collaborative Search for Pickup and Delivery Problems.

Area of Science:

• Operations Research
• Artificial Intelligence
• Machine Learning

Background:

• Pickup and Delivery Problems (PDPs) are complex combinatorial optimization challenges.
• Existing methods often struggle with scalability and solution quality for constrained PDP variants.

Purpose of the Study:

• To introduce Neural Collaborative Search (NCS), a novel learning-based framework for efficiently solving PDPs.
• To propose Neural Neighborhood Search (N2S), an efficient improvement model for PDPs within the NCS framework.

Main Methods:

• NCS collaboratively trains neural construction and improvement models using reinforcement learning with a shared-critic mechanism.
• N2S employs a tailored Markov decision process and custom decoders for a ruin-repair search, addressing precedence constraints.
• A light Synthesis Attention mechanism and diversity enhancement scheme optimize N2S's performance and computational efficiency.

Main Results:

• NCS and N2S demonstrate state-of-the-art performance on canonical PDP variants compared to existing neural methods.
• The proposed framework significantly outperforms the LKH3 solver, particularly on more constrained PDP instances.
• Extensive experiments validate the effectiveness and generalizability of NCS and N2S.

Conclusions:

• NCS offers a powerful and efficient learning-based framework for solving PDPs by integrating construction and improvement strategies.
• N2S provides an effective neural improvement model capable of handling complex constraints within PDPs.
• The developed methods represent a significant advancement in the application of neural networks to combinatorial optimization problems like PDPs.