Deep reinforcement learning for the vehicle routing problem with route balancing

The Vehicle Routing Problem with Route Balancing (VRPRB) is a multi-objective combinatorial optimization (MOCO) problem that aims to balance workload distribution while minimizing overall travel costs. Unlike traditional Vehicle Routing Problems (VRP), VRPRB introduces fleet size constraints to improve resource utilization and reduce operational costs. Existing deep reinforcement learning (DRL) approaches for VRP rarely address multi-objective optimization and often assume an unlimited fleet size, limiting their practical applicability. To address this issue, we propose an Equity Attention Model (E-AM), a problem-tailored DRL framework designed to generate Pareto-optimal solutions for VRPRB. Our E-AM formulates the problem as a sequential decision-making process, where each decision involves pairing a vehicle with a customer. E-AM is built on an attention-based architecture, incorporating a node encoder, a vehicle context encoder, and a decoder, with a hyper-network technique to efficiently handle multi-objective optimization. Experimental results demonstrate that our approach finds better solutions than current state-of-the-art methods on VRPRB benchmark instances while maintaining higher computational efficiency. By fully leveraging the strengths of deep reinforcement learning, our approach provides a scalable and adaptive alternative to traditional heuristic and exact algorithms, achieving high-quality solutions for complex real-world routing problems. To enhance scalability and training efficiency, we introduce a two-stage reinforcement learning strategy that enables E-AM to solve VRPRB instances with up to 1000 customers. To promote transparency and reproducibility, we have open-sourced our implementation1.