Learning Routing Policy With Spatial Awareness: A Distance-Based Attention Mechanism for Multi-Robot Routing With Time Windows in Multi-Product Delivery

Abstract

Deep Reinforcement Learning (DRL) approaches with Attention Mechanism have shown efficiency and effectiveness for combinatorial optimization problem, such as routing problem for autonomous vehicles (VRP). However, the real-world routing problems often involve intricate constraints and multiple objectives, introducing substantial complexity. Current attention mechanism uniformly treats all the points within service region, neglecting the relative spatial relationship among points, which results in unguided exploration within the large solution space of multi-objective routing problem, leading to a potential distraction dilemma where model struggles to effectively balance multiple objectives. To address this issue, we propose a Distance-Based Attention Mechanism (DBAM) that enhances spatial awareness by incorporating relative spatial relationship information into attention-based model, and implement this model to study a new multi-objective VRP variant: the Capacitated Vehicle Routing Problem with soft Time Windows for Multi-kind products delivery tasks (MKVRPsTW), in which the DRL model is trained to plan routes for a fleet of autonomous vehicles to serve customers with multi-kind products demands, while minimizing the total length, time window violation and balancing route lengths among vehicles. Experimental results reveal that DBAM outperforms the original attention-based DRL methods, graph-based DRL methods, and traditional baselines. Additionally, fine-tuning experiments for balance-oriented objectives further substantiates DBAM's flexibility and stability for quick adaptation.