Multiple-Relational Attention for Vehicle Routing Problem with Simultaneous Delivery-Pickup

The simultaneous delivery-pickup vehicle routing problem(VRPSDPTW) is a NP-hard problem, which has a wide application in modern logistics and distribution. A mathematical model is established to minimize the total vehicle cost, the total time cost and the customer dissatisfaction cost, then a multiple-relational attention RL(MARL) algorithm is proposed, involving the improved transformer-based model that provides dynamic-aware context embedding through an attention aggregation module on multiple relational structures. Experimental results conducted on standardized instances show that the MARL algorithm is able to couduct high-quality solutions in short computational time and outperforms the heuristic and learning-based algorithm comparisons.