Research On Vehicle Routing Problem Based On Multi-Objective Decision-Making Algorithm

Vehicle Routing Problem(VRP)can be widely used in traffic planning,logistics and transportation,road rescue,military scheduling and other optimization issues.With the continuous development of social economy in our country,the demand of solving vehicle routing problems efficiently becomes more and more urgent.Because VRP problem is a classic NP-Hard problem,using the exact exhaustive method to violently search the optimal path,the computational complexity increases exponentially with the scale of the problem.In recent years,various intelligent algorithms such as simulated annealing,genetic algorithm,artificial neural network and particle swarm emerged to simulate various evolution processes in nature and converge to feasible solutions with higher quality in a short time,which greatly improve the efficiency of solving VRP problems and obtain a wide range of applications and developments.The traditional VRP problem usually defines the number of vehicles and finding the shortest path through designated customer points.However,in real life,the total number of vehicles and the total cost of transportation,whether transportation,material transportation,road rescue,etc.,need to be optimized,so that the total distance traveled is the shortest,the transportation time is the shortest,the number of vehicles used is the least,Gasoline cost minimum consumption.Optimizing the shortest total transport route,the minimum number of vehicles and the shortest transport distance of a single vehicle are obviously typical multi-objective optimization problems.The traditional algorithm of VRP problem can not solve the problem of satisfying more than one goal and provide the user with decision-making and help.In this paper,integrating the NSGA-II algorithm and the multi-objective decisionmaking algorithm based on ideal minimum point,a multi-objective decision-making algorithm based on Knee point is proposed.The multi-objective optimization problem examples are given to prove the effectiveness of the algorithm.This algorithm can efficiently solve the target feasible solution that satisfies multiple equilibriums.On this basis,the algorithm is applied to the vehicle path planning problem.In this problem,We set the shortest total path length,the number of vehicles and the maximum path length traveled by a single vehicle as three objectives.On the basis of NSGA-II,a new chromosome coding method and chromosome cross mutation operator are designed.Use the multi-target way to plan the driving path of multiple cars.Experiments show that the proposed algorithm can efficiently solve this kind of vehicle routing problem while optimizing the shortest time,the least total path and the minimum number of vehicles,finding the solution which have the least number of vehicles and each car travels as little as possible.