Learning Improvement Heuristic via Spatio-Temporal Encoder for Pickup and Delivery Problem with Time Windows

Full abstract

Read the full abstract

The Pickup-and-Delivery Problem with Time Windows (PDPTW) underpins emerging logistics applications such as ride-hailing and meal-delivery services. Hard time-window constraints make the PDPTW substantially more challenging than routing variants without temporal feasibility requirements. We propose an improvement heuristic, termed “Attention Model with Spatio-Temporal Encoder” (AMSTE). Starting from an initial feasible solution, AMSTE repeatedly applies a learned remove-and-reinsert move. Its encoder processes spatial and temporal information through separate pathways and concatenates the resulting embeddings for the removal and reinsertion decoders. The decoder mask rejects moves that violate precedence, capacity, same-vehicle, or time-window constraints. We evaluate AMSTE on synthetic instances of multiple scales and conduct a zero-shot distribution-shift evaluation on the R1, C1, and RC1 benchmark subsets. The transferred policy remains feasible on all tested instances, while the larger distance gap on C1 indicates that clustered geometry constitutes a stronger shift from the R1 training distribution. On the reported synthetic PDPTW-101 setting, AMSTE obtains an objective value 4.17% below LKH3 (10k) with substantially lower measured inference-time computation; the runtime comparison is qualified because AMSTE uses GPU batch inference whereas LKH3 runs on CPU.