EUVIMEDEUVIMED entdecken
Crossref

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

Zhanhong Fang, Jinbiao Chen, Jiahai Wang, Zizhen Zhang

ACM Transactions on Intelligent Systems and Technology · 30.10.2026

DOI: 10.1145/3861015 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Intelligent Systems and Technology, online erschienen am 30.10.2026. Verfasst von Zhanhong Fang und 3 weiteren Autor:innen. Die Arbeit nennt 52 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Fang, Z., Chen, J., Wang, J., & Zhang, Z. (2026). Learning Improvement Heuristic via Spatio-Temporal Encoder for Pickup and Delivery Problem with Time Windows. ACM Transactions on Intelligent Systems and Technology. https://doi.org/10.1145/3861015

Vancouver

Fang Z, Chen J, Wang J, Zhang Z. Learning Improvement Heuristic via Spatio-Temporal Encoder for Pickup and Delivery Problem with Time Windows. ACM Transactions on Intelligent Systems and Technology. 2026. doi:10.1145/3861015

BibTeX
@article{Fang2026,
  author = {Fang, Zhanhong and Chen, Jinbiao and Wang, Jiahai and Zhang, Zizhen},
  title = {Learning Improvement Heuristic via Spatio-Temporal Encoder for Pickup and Delivery Problem with Time Windows},
  journal = {ACM Transactions on Intelligent Systems and Technology},
  year = {2026},
  doi = {10.1145/3861015}
}
Kostenlos starten →