Research On Stochastic Combination Optimization Model And Algorithm For Dynamic Relocation Of Shared Electric Vehicles

The electric car-sharing service has a trillion-scale industrial development prospect and brings millions of tons of carbon reduction benefits every year,which is of great benefit to boosting national economic and social development.However,the current operational process of shared electric vehicles is hindered by the problems of low order demand satisfaction rate,long waiting time for users,imbalance of supply and demand between regions,and high fleet operating costs.To promote the large-scale application of the electric car-sharing services,the dynamic dispatching problem of shared electric vehicles should be solved.Hence,this paper conducts research from three dimensions including analysis of influencing factors,optimization modeling,and solving algorithm.The main research contents are as follows:First,the analysis of the influencing factors of fleet dynamic dispatching begins by sorting out the different application scenarios of shared electric vehicles,and the typical characteristics of fleet dynamic dispatching under four different development modes are defined.Focusing on the two modes of single task dispatching and multiple tasks dispatching,the influencing factors of the fleet dynamic dispatching process are defined.The results find that the dynamic dispatching process of shared electric vehicles mainly involves two types of deterministic factors and random factors.Among them:(1)The deterministic factors include "inherent capacity of parking spaces at each station",“the number of vehicles available in the station”,“the number of vehicles available in the region”,“station-charging pile-parking lots configuration in each region”,“charging time”,and “charging cost”;(2)The random factors include“driving distance”,“driving time”,“power consumption”,“order revenue”,“regional order demand”.Secondly,in order to model the decision-making process of dynamic dispatching of shared electric vehicles,a stochastic combinatorial optimization theoretical model of dynamic dispatching of shared electric vehicles is proposed.Starting from the combing of the modeling framework,the stochastic combination optimization modeling of fleet dynamic dispatching is divided into two parts: “Deterministic transformation of the effect of random factors” and “Dynamic dispatching stochastic combination optimization model”.In order to deterministically transform the role of two random influencing factors of “trip demand” and “power consumption”,a prediction model of micro-travel service demand combined with long-short-term memory network and Granger causality test,and a power consumption calculation and prediction model based on vehicle longitudinal dynamics and machine learning are constructed respectively.Based on this,a theoretical data-driven stochastic combinatorial optimization model of dynamic dispatching of shared electric vehicles is constructed for the “time-sharing” and “on-demand” modes,including optimization objectives,decision variables,objective functions,and constraints.The research results show that:(1)The constructed micro-travel service demand prediction model and vehicle real-time power consumption prediction model have high prediction accuracy and good interpretability;(2)The stochastic combinatorial optimization theoretical model can more realistically restore the dynamic dispatching decision-making process of shared electric vehicles.Thirdly,in order to solve the uneven distribution problem of vehicles among stations,a fleet single-task dynamic dispatching optimization algorithm for“time-sharing” rental mode is proposed.By introducing the L4/L5-level automatic formation cruise technology into the existing electric vehicle sharing system,the vehicle relocation process between stations is carried out in advance,and the redundant vehicles at the vehicle surplus station are assigned to autonomously form a fleet to the vehicle shortage station for vehicle replenishment,in order to meet user’s order demand for pickup and return of the car in the next time period as much as possible.Based on the time-sharing oriented fleet single-task dynamic scheduling random combination optimization theoretical model,a multi-stage scheduling optimization algorithm of “demand forecasting-station judgment-vehicle relocation"based on the integer linear programming model is designed to minimize the total driving distance and carbon emissions of each round of dispatching.The research results show that:(1)The multi-stage dispatching optimization algorithm can maximize the satisfaction rate of users’ trip demand;(2)The proposed “regional autonomy” dispatching principle can decompose large-scale problems into small-scale problems and achieve rapid solutions;(3)Taking the minimum total driving distance and minimum carbon emission of each round of dispatch as the optimization goal,the above research has reference value for relevant participants in the future green transportation system.Finally,in order to solve the multi-task dynamic autonomous dispatching problem of charging,dispatching,regional repositioning,and parking of shared electric vehicles in the future on-demand trip system,a dynamic dispatching optimization algorithm for fleet multi-tasking is proposed.The Markov Decision Process is adopted to model the dispatching process of shared electric vehicles.The trip order assignment and charging task assignment are modeled as the maximum weight matching problem,and the regional repositioning task is quantified as the network maximum flow problem.The above two models are solved by Kuhn-Munkres algorithm and Edmond-Karp algorithm respectively.Then a new cumulative reward function for balancing enterprise order revenue and user trip satisfaction is further designed,and the back-propagation-deep neural network is adopted to fit the long-term return of each dispatch task.Finally,to verify the effectiveness of the algorithm above,taking the existing algorithm as a basic example,based on the open-source dataset of Didi Chuxing’s “Gaia Project”,four simulation examples are designed.The numerical results show that:(1)Compared with the“revenue-preferred” instant reward function,the new “revenue-user satisfaction”instant reward function increases the total order revenue while reducing the average user waiting time;(2)By conducting regional dispatching in advance realizing timely replenishment of vehicles in areas in short supply,the total order revenue can be increased by 47.98% and the average user waiting time can be reduced;(3)By summing up the state value function fit by the back-propagation-deep neural network and the instant reward function,the obtained new cumulative reward function can further achieve a small increase of 2.78% in total order revenue.In summary,to solve the dynamic dispatching problem of shared electric vehicles,a stochastic combinatorial optimization model that integrates deep reinforcement learning,bipartite graphs,and maximum flow is proposed,and a solution algorithm integrating Deep Q Network,Kuhn-Munkres algorithm and Edmond-Karp algorithm is designed,which can further reduce the user’s waiting time while maximizing the order fulfillment,and improve the circulation and utilization rate of the fleet,in order to realize the improvement of both user experience and operating income during the operation of the electric car-sharing service system.