Research On Heterogeneous Vehicle Routing Problem Based On Deep Reinforcement Learning

The vehicle routing problem is a crucial problem in the optimization of logistics transportation.Its goal is to plan a vehicle route with the lowest cost while meeting the needs of customers.Existing methods based on deep reinforcement learning to solve the capacity-constrained vehicle routing problem essentially deal with homogeneous fleets.However,vehicles may be heterogeneous in reality,which makes existing methods less efficient.The innovations of this paper are as follows:(1)For the heterogeneous vehicle routing problem,an attention mechanism based deep reinforcement learning method is proposed,with the aim of minimizing the longest travel time or total time of vehicles in the fleet.The main feature of heterogeneous vehicles is their different capacities.To meet the heterogeneous constraints,a selection decoder responsible for heterogeneous vehicles and a node selection decoder responsible for route construction are used.Both the selected vehicles and nodes constitute the actions of this step.At the same time,the Monte Carlo algorithm is used for training to improve the solution performance of the model.Experimental results based on randomly generated examples show that our method outperforms state-of-the-art deep reinforcement learning methods and most traditional heuristic methods in solving heterogeneous vehicle path planning.Solve the CVRPLIB instance with satisfactory performance.(2)An end-to-end deep reinforcement learning framework is proposed for the capacity-constrained EV routing problem,with the goal of minimizing the total driving distance of the fleet.Meanwhile,an attention model consisting of a pointer network and a graph embedding layer is developed to parameterize a stochastic policy for solving the EV routing problem.In a framework that only considers node information,a graph embedding component is added along with global information to synthesize local and global information of the graph defining the problem.The reward function is then used to evaluate the solutions produced by the agent,guiding the agent to improve accordingly.The study shows that the proposed model can effectively solve large-scale electric vehicle path planning instances that cannot be solved by current existing methods.The deep reinforcement learning method and strategy proposed in this paper combines the advantages of deep learning’s perception ability and reinforcement learning’s decision-making ability,which can effectively solve the problem of vehicle path planning with capacity constraints,and provide deep reinforcement learning methods for solving other combinatorial optimization problems.It is a useful reference and reference.