Temporal and Spatial Attention-Based Reinforcement Learning for Vehicle Routing Problem With Mixed Backhauls and Late Penalties

The Vehicle Routing Problem with Mixed Backhauls and Late Penalties (VRPMBLP) is widely used to simulate real-world scenarios in transportation and logistics. However, the incorporation of late penalties and complex linear constraints significantly increases the difficulty of solving the problem. To overcome these challenges, this paper proposes a deep reinforcement learning model based on temporal-spatial attention. The model adopts an encoder-decoder framework. In the encoder stage, temporal and spatial attention modules are introduced, and feature fusion is achieved through a gating mechanism. This design enables the model to fully capture and represent key customer features, thereby providing richer contextual information. In the decoder stage, a local-global GRU structure is designed to integrate vehicle state information, and a multi-vehicle attention network is constructed to achieve effective order assignment. To comprehensively evaluate the effectiveness of the proposed method, extensive experiments are conducted and compared with traditional exact algorithms, metaheuristic methods, and reinforcement learning approaches. Experimental results show that the proposed model achieves near-optimal performance on small-scale datasets and reduces the average routing cost by 10% on medium and large-scale datasets. Furthermore, the model’s generalization ability is evaluated across different problem sizes and data characteristics, demonstrating strong adaptability and promising potential for practical applications.