TL;DR
This paper introduces a novel reinforcement learning (RL) approach for the Pickup-and-Delivery Traveling Salesman Problem (PDTSP). By designing "feasible operators" that always transform one valid tour into another, the method efficiently searches for optimal routes while strictly adhering to pickup-before-delivery constraints, outperforming existing methods in both solution quality and computational efficiency.
What Problem Does This Paper Address?
The Pickup-and-Delivery Traveling Salesman Problem (PDTSP) is a complex optimization challenge where a vehicle must visit a set of pickup locations before their corresponding delivery locations, all while minimizing total travel distance. This problem is significantly harder than the standard Traveling Salesman Problem (TSP) due to the added "precedence constraints" (pickup must precede delivery). Traditional Operations Research (OR) methods struggle to scale to larger PDTSP instances because the vast majority of possible routes are infeasible, leading to excessive computation. While recent reinforcement learning approaches have been applied to TSPs, they often explore infeasible solutions, making them inefficient for PDTSP. This paper aims to bridge this gap by developing an RL framework that intelligently navigates the solution space, ensuring feasibility at every step.
Methods
The core innovation of this paper lies in its "operator design" for reinforcement learning. Instead of using generic operators that might generate invalid routes, the authors propose a set of five "admissible operators" that are guaranteed to transform a feasible PDTSP tour into another feasible tour. These operators are categorized into two types:
- Node-Exchange Operators (NxO): These operators swap individual nodes within a tour.
- Intra-Block NxO: Swaps nodes within a "block" of consecutive pickup nodes or consecutive delivery nodes.
- Inter-Block NxO: Swaps a pickup node from one block with a delivery node from another block.
- Node Pair-Exchange NxO: Swaps entire pickup-delivery node pairs.
- Block-Exchange Operators (BxO): These operators swap entire blocks of nodes.
- Same-Type Block-Exchange: Swaps two blocks of the same type (e.g., two pickup blocks).
- Mixed-Type Block-Exchange: Swaps a pickup block with a delivery block.
These operators are used as actions within a reinforcement learning framework. The agent learns a policy to select these operators, starting from an initial feasible tour (constructed using a simple heuristic), to iteratively improve the tour's cost while maintaining feasibility. The reward function is based on the reduction in travel cost.
Datasets
The paper uses PDTSP instances sourced from the Grubhub Test Instance Library. These instances are generated by uniformly sampling node locations from a unit square, and the travel cost between nodes is the Euclidean distance. The experiments are conducted on instances with varying numbers of nodes, specifically |N| = 11, 21, 41, 61, and 101.
Key Insights and Ideas
- Feasibility as a Constraint, Not an Obstacle: The most significant insight is the shift from exploring a vast, infeasible solution space to intelligently navigating a confined, feasible one. By designing operators that inherently preserve feasibility, the RL agent can focus on optimization rather than error correction.
- The Power of Block Operations: Swapping entire blocks of pickup or delivery nodes (BxO) proves to be a powerful mechanism for exploring the solution space efficiently, especially when compared to only swapping individual nodes.
- Operator Equivalence: The paper demonstrates that their proposed node-exchange operators are equivalent to existing heuristic operators from prior work, validating their approach.
- RL for Structured Optimization: This work showcases how RL can be effectively applied to problems with strong structural constraints (like precedence constraints) by carefully designing the action space.
Key Results
The proposed "Learn to Tour" (L2T) algorithm demonstrates superior performance compared to several baselines, including Google OR-Tools, Gurobi, Pointer Networks, Transformers, and LKH3.0.
- Solution Quality: L2T consistently finds shorter tours, achieving an average travel cost that is significantly lower (up to 10.3% shorter than Google OR-Tools and Gurobi for |N| ≥ 41) and outperforming all methods for larger instances (|N| = 61, 101).
- Computational Efficiency: While L2T-Naive (using a naive operator) becomes very slow with increasing problem size, the proposed L2T with admissible operators shows better scalability. The paper highlights that individual operators (like L2T-B1, L2T-B2) converge faster but yield worse solutions, whereas the unified operator set in L2T achieves a good balance between speed and solution quality.
- Handling Capacitated PDTSP: The method is also shown to be effective for the Capacitated PDTSP (multi-vehicle scenario), finding a better solution than OR-Tools within a given time limit.
Limitations and Future Work
- Training Time: While L2T is computationally efficient at inference, the training process for RL can still be time-consuming, especially for larger instances. The paper notes that L2T-Naive's training time increases drastically due to exploring infeasible solutions.
- Generalization: The paper focuses on one-to-one pickup-and-delivery scenarios. Extending the framework to more complex PDTSP variants (e.g., multi-commodity, time windows, or many-to-many relationships) could be a valuable future direction.
- Operator Design: The paper proposes a specific set of admissible operators. Exploring alternative or more sophisticated operator designs could further enhance performance.
- Dynamic Environments: The current work addresses static PDTSP instances. Adapting the learned policies to dynamic environments where requests arrive over time is a promising avenue for future research.
Summary updated