Research On Vehicle Dynamic Ride-sharing Matching And Route Optimization Based On Deep Q-Network

With the improvement of people’s living standards,the number of residents’ private cars has increased rapidly in recent decades,which has gradually shifted people’s demand for travel from public transportation to faster and more comfortable private taxi travel.However,limited road and energy resources cannot meet the growth of the number of private cars and people’s demand for vehicles indefinitely.On the other hand,as the number of vehicle trips increases,the traditional "one person,one car" service has very low operating efficiency,resulting in extremely low vehicle seat utilization,and simultaneously making the frequency of use vehicles higher and higher,which makes fewer and fewer people can be served.The "sharing economy" emerged in recent years has made carpooling a more popular way of travel that people can accept.Carpooling refers to that passengers on similar routes choose to travel together in the same car by sharing the travel costs.Carpooling can not only make full use of the vehicle’s own capacity,reduce the empty load rate,and effectively alleviate the problem of passengers’difficulty in getting a vehicle,but also achieve more travel demands on limited road resources,alleviate traffic congestion,reduce vehicle energy consumption,reduce exhaust emissions and promote the formation of a green urban environment.After analyzing the relevant researches on the current situation of car-sharing and its path planning problems at home and abroad,this thesis proposes a dynamic carpooling matching and path optimization algorithm based on deep Q-network(DQN),which solves the problem of falling into local optimality caused by traditional path optimization algorithms,and can complete the automatic matching between vehicles and randomly generated passenger orders and path optimization in real time through independent training and learning.After studying the various combinations of deep reinforcement learning algorithms and their characteristics,this thesis finally studies and draws on the DQN network structure,which combines the neural network with Q-learning.In DQN,the neural network is used to replace the Q table to store action value function,and the node vector input to the path output is mapped through the neural network.Expert samples are made through Markov Decision Process(MDP)to accelerate DQN convergence by imitating learning.At the same time,in order to reduce the randomness of action exploration,the priori knowledge is introduced to guide the vehicle to make choices in the training process and then improve the efficiency of the algorithm.To solve the order conflict between vehicles in the environment,this thesis adopts a task allocation algorithm based on distributed game theory.The vehicles uses their local information and interactive information between them to their respective best strategies in a distributed manner.In task allocation algorithm based on distributed game theory,the vehicles use the estimated value of each action provided by the DQN algorithm to select their conflict-free orders.Finally,the proposed algorithm was verified on the road environment of Chicago.