Research On Dynamic Shared-taxi Dispatch Algorithm

Urban traffic problems have become a common challenge encountered by cities all over the world at present,among which the traffic jam problem is the most prominent one,resulting in a series of social,environmental and economic problems.At the same time,with the rapid development of science and technology,ridesharing mode has attracted more and more attention due to its advantages in easing traffic congestion and low-carbon environmental protection.However,the matching between vehicles and passengers remains a major challenge for online taxi-dispatch platforms.In this paper,the dynamic ridesharing problem encountered by the platform in the time section of the algorithm invocation is studied.Different from other literatures,this paper considers that vehicles have different initial positions,onboard passengers and scheduled passengers,as well as corresponding previously arranged route information,while introducing rescheduling ratio to measure the proportion of requests that can be rescheduled in the total scheduled requests.For the proposed dynamic ridesharing problem,a mixed integer model is firstly established in this paper,and then two mathematical programming based algorithms are designed,the branch and price algorithm and the Lagrangian relaxation algorithm.The sub-problems obtained by the decomposition of the two algorithms are unified,and the dynamic programming algorithm is designed to solve the sub-problems in parallel to speed up the solution.Because the optimization methods can not guarantee the feasible solution in a limited time,and the time-consuming increases sharply with the increase of the scale of the problem,an adaptive large neighborhood search heuristic algorithm(ALNS)with several new operators(revised Shaw removal,random insertion,and best insertion heuristics)is designed in this paper to solve the dynamic ridesharing problem.In this paper,instances are designed to test the mathematical programming based algorithms and the heuristic algorithms.In the comparison of heuristic algorithms,Nearest vehicle dispatch heuristic(NVD)and Best insertion heuristic(BIS)commonly used in the industry are introduced for comparison.The results show that the branch and price algorithm and the Lagrangian relaxation algorithm are significantly superior to the solver(Gurobi)in the quality and scale of solutions as well as the computation time.Besides,the branch and price algorithm obtains the best quality solution under all the instances.For heuristic algorithms,the quality of solutions obtained by ALNS algorithm is better than that of NVD and BIS,which is more significant in large-scale instances.Compared with the mathematical programming based algorithms,ALNS has an obvious time advantage,and the average gap of the solutions is within 9%.After that,a dynamic simulation framework is designed to simulate the actual application and further verifies the applicability of the proposed algorithms in the actual scene.Finally,the sensitivity analysis of the rescheduling ratio factor is carried out to provide suggestions for the ridesharing scheduling platform to balance the relationship between the total revenue of the system and user experience.