Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learning

Abstract

Recently, there is an emerging trend to apply deep reinforcement learning to solve the vehicle routing problem (VRP), where a learnt policy governs the selection of next node for visiting. However, existing methods could not handle well the pairing and precedence relationships in the pickup and delivery problem (PDP), which is a representative variant of VRP. To address this challenging issue, we leverage a novel neural network integrated with a heterogeneous attention mechanism to empower the policy in deep reinforcement learning to automatically select the nodes. In particular, the heterogeneous attention mechanism specifically prescribes attentions for each role of the nodes while taking into account the precedence constraint, i.e., the pickup node must precede the pairing delivery node. Further integrated with a masking scheme, the learnt policy is expected to find higher-quality solutions for solving PDP. Extensive experimental results show that our method outperforms the state-of-the-art heuristic and deep learning model, respectively, and generalizes well to different distributions and problem sizes.

arXiv commentThis paper has been accepted at IEEE Transactions on Intelligent Transportation Systems

References in corpus (6)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Neural Combinatorial Optimization with Reinforcement Learning
• Attention, Learn to Solve Routing Problems!
• Learning to Perform Local Rewriting for Combinatorial Optimization
• Learning Improvement Heuristics for Solving Routing Problems
• Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems

Cited by in corpus (11)

• Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem
• Neural Airport Ground Handling
• NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
• Efficient Neural Neighborhood Search for Pickup and Delivery Problems
• Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
• RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark
• Learning for routing: A guided review of recent developments and future directions
• Learning Large Neighborhood Search Policy for Integer Programming
• Deep Reinforcement Learning for Demand Driven Services in Logistics and Transportation Systems: A Survey
• SED2AM: Solving Multi-Trip Time-Dependent Vehicle Routing Problem using Deep Reinforcement Learning
• Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning