Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem
Existing deep reinforcement learning (DRL) based methods for solving the capacitated vehicle routing problem (CVRP) intrinsically cope with homogeneous vehicle fleet, in which the fleet is assumed as repetitions of a single vehicle. Hence, their key to construct a solution solely lies in the selection of the next node (customer) to visit excluding the selection of vehicle. However, vehicles in real-world scenarios are likely to be heterogeneous with different characteristics that affect their capacity (or travel speed), rendering existing DRL methods less effective. In this paper, we tackle heterogeneous CVRP (HCVRP), where vehicles are mainly characterized by different capacities. We consider both min-max and min-sum objectives for HCVRP, which aim to minimize the longest or total travel time of the vehicle(s) in the fleet. To solve those problems, we propose a DRL method based on the attention mechanism with a vehicle selection decoder accounting for the heterogeneous fleet constraint and a node selection decoder accounting for the route construction, which learns to construct a solution by automatically selecting both a vehicle and a node for this vehicle at each step. Experimental results based on randomly generated instances show that, with desirable generalization to various problem sizes, our method outperforms the state-of-the-art DRL method and most of the conventional heuristics, and also delivers competitive performance against the state-of-the-art heuristic method, i.e., SISR. Additionally, the results of extended experiments demonstrate that our method is also able to solve CVRPLib instances with satisfactory performance.
Code (1)
Tasks
DecoderDeep Reinforcement Learningreinforcement-learningReinforcement Learning (RL)Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
An End-to-End Learning Approach for Solving Capacitated Location-Routing Problems
The capacitated location-routing problems (CLRPs) are classical problems in combinatorial optimization, which require simultaneously making location and routing decisions. In CLRPs, the complex constraints and the intric…
Reinforcement LearningA Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone
Reinforcement learning has recently shown promise in learning quality solutions in many combinatorial optimization problems. In particular, the attention-based encoder-decoder models show high effectiveness on various ro…
Combinatorial OptimizationComputational EfficiencyDecoderDeep Reinforcement Learning+3Using Reinforcement Learning for the Three-Dimensional Loading Capacitated Vehicle Routing Problem
Heavy goods vehicles are vital backbones of the supply chain delivery system but also contribute significantly to carbon emissions with only 60% loading efficiency in the United Kingdom. Collaborative vehicle routing has…
reinforcement-learningReinforcement LearningA new Hyper-heuristic based on Adaptive Simulated Annealing and Reinforcement Learning for the Capacitated Electric Vehicle Routing Problem
Electric vehicles (EVs) have been adopted in urban areas to reduce environmental pollution and global warming as a result of the increasing number of freight vehicles. However, there are still deficiencies in routing the…
Deep Reinforcement Learning for Routing a Heterogeneous Fleet of Vehicles
Motivated by the promising advances of deep-reinforcement learning (DRL) applied to cooperative multi-agent systems we propose a model and learning procedure to solve the Capacitated Multi-Vehicle Routing Problem (CMVRP)…
Deep Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)