Research On The Model And Algorithm For The Dynamic Shared Taxi Scheduling Problem

With the rapid growth of people's travel demand,the contradiction between thesupply of limited taxi resources and the demand for trips is becoming more and more serious,the traditional service pattern of taxis,"one person,one taxi",makes the operation of taxi low.In order to alleviate the above problems,the concept of "taxi ride-sharing" is put forward by scholars.Through taxi ride-sharing,it can not only make full use of the taxi capacity and effectively ease the problem of taking a taxi for passengers,but also reduce the range of the taxi,save the fuel consumption,reduce the exhaust emission and improvement of the urban environment.Firstly,the domestic and foreign studies about taxi ride-sharing and vehicle scheduling problems are reviewed,and the classification and application of the taxi ride-sharing pattern and vehicle scheduling is combed.On the basis of this,the theory and method of taxi ride-sharing and vehicle scheduling are elaborated in detail,which provides a theoretical basis for the following study.Then,this paper analyzes the characteristics of road network,vehicle and passenger that are involved in the dynamic scheduling problem of combined ride taxis,and builds the dynamic scheduling model of taxi which is based on time axis and aims at minimizing the sum of total waiting time for passengers and total passenger detour time.The model takes the arrival time of passengers as the key point,divides the time axis into multiple segments,transforms the overall optimization of whole operation period into the accumulation of optimization in each time interval,and then dismantling the dynamic scheduling question of the combined taxis into a series of static scheduling problems.The model also introduces the adjustment parameters,which can automatically adjust the influence of the passenger waiting time on the target function based on the system state,so as to ensure the reasonable allocation of the taxi resources and thus achieve the overall optimization within the taxi operation period.In this paper,a double-layer optimization algorithm is designed to solve the model based on the feature of dynamic shared taxi scheduling model based on time axis.The upper-layer algorithm is mainly used to optimize the adjustment parameter values through reinforcement learning and the lower-layer algorithm is based on the adjustment parameter values obtained by the upper-layer algorithm,and then theinterpolation algorithm is used to solve the model.Finally,a shared taxi simulation simulator based on C language development environment is built.According to the simulation data,the feasibility and effectiveness of the evaluation model and algorithm are analyzed,and then the sensitivity of the algorithm is analyzed by the combination of different parameters.In the aspect of theoretical research,it can further improve the theory of the dynamic shared taxi scheduling problem;in practice,it can also provide scientific and reliable theoretical reference and technical support for the operation and management of the taxi ride-sharing.