Research On The Route Optimization Of Intercity Carpooling Under Time-varying Road Network

With the rapid development of the national economy,the quality requirements of residents ’ intercity travel service have been continuously improved.Although the intercity car-hailing service can meet the needs of passengers’‘door-to-door’intercity travel,there are still problems such as poor enthusiasm of passengers for ride-sharing,poor platform billing mechanism,and insufficient combination of historical road data and real-time information to give suggestions on the departure and arrival time of passengers.In view of the above problems,this thesis studies the optimization problem of intercity network car-hailing path considering passenger preference under time-varying road network,and provides reference for the construction of intelligent intercity network car-hailing service system.First of all,this thesis combines the theory of vehicle routing problem and the existing problems of intercity network car-hailing service,introduces the definition of time axis,studies the intercity network car-hailing scheduling strategy,and designs its service system.Secondly,the discrete time dependence function based on travel time is used to represent the section impedance of time-varying road network,and the vehicle routing optimization model under time-varying road network is constructed.Firstly,the initial vehicle routing optimization model is constructed with the objective function of maximizing the economic benefits of enterprises,and the scheduling scheme of static passenger orders is obtained.Then,based on the initial scheduling scheme,the dynamic vehicle routing optimization model is constructed with the objective function of minimizing the total vehicle travel time to determine whether to respond to real-time passenger orders and improve the vehicle carrying rate.Thirdly,the branch and bound algorithm is used to solve the initial vehicle path optimization model;by using the column generation algorithm,the dynamic vehicle routing optimization model is decomposed into the main problem model and several sub-problem models,and the solution is dynamically added in the process of continuously generating ’ column’from the sub-problem to the relaxed main problem.Finally,the example is solved and analyzed.The results show that the two models and algorithms in this thesis can solve the dynamic intercity online car-hailing path optimization problem of static passenger order demand and real-time passenger order demand in the intercity online car-hailing service system,and can bring more personalized and intelligent intercity online car-hailing service to passengers.