Feasibility-Aware Masked Transformer for the Pickup-and-Delivery Problem with Time Windows (Student Abstract)

The Pickup-and-Delivery Problem with Time Windows (PDPTW) is a time-constrained variant of the vehicle-routing problem (VRP). Complex time constraints make it difficult to solve using existing NCO methods. In this paper, we present the Feasibility-Aware Masked Transformer (FAM-Trans) specialized for PDPTW. FAM-Trans integrates a lightweight side encoder with a context-aware embedding scheme that effectively captures temporal dependencies. A dynamic key-value module continuously updates node embeddings as the route progresses. During inference, a feasibility-guided post-inference filtering strategy suppresses constraint violations without post-hoc repair. Experiments on standard PDPTW benchmarks show that FAM-Trans outperforms NCO baselines by 20~35% in solution quality and constraint satisfaction.

Authors

• Kaede Saito Keio University
• Ryota Higa National Institute of Advanced Industrial Science and Technology NEC Data Science Research Laboratories
• Hiromu Imura NEC Corporation
• Masaaki Kondo Keio University

Keywords

No keywords are indexed for this paper.