Taxi Dispatching Problem With Reservation Orders And Real-time Orders

Taxis,as one of the main participants involved in public transportation system,are very popular with convenience,time-efficient benefit,comfort and a wide range of doorto-door services.However,with the increasing penetration rate of taxis,operation mode of the taxi system is gradually revealing the shortcomings.Due to the growth of traffic demand and the ineffective method of taxi dispatch,it barely maintains a balance between taking a taxi quickly for passengers and taking orders with ease for idle taxis,which makes a serious effect on urban traffic.Therefore,based on the characteristics of different types of orders and the joint consideration between real-time orders and reservation orders,this paper presents a two-phase algorithm with insertion algorithm,Variable Neighborhood Search(VNS)and Reinforcement Learning(RL),which fits the operation mode of taxi dispatch system to provide theoretical and methodological guidance for taxi scheduling problem.Firstly,by combing and summarizing the domestic and foreign research about the mathematical formulation and solution algorithm of Vehicle Routing Problem(VRP),it is concluded that the studies usually take one single type of orders as the object of the research,which is difficult to match the actual situation of taxi operation system.Therefore,this paper considers the impacts of real-time orders and reservation orders on the taxi dispatching problem,and the technology roadmap of this paper is proposed.Secondly,on the basis of studying the operation mode of taxi dispatching system,the characteristics of real-time orders and reservation orders are introduced,and the joint effect of real-time orders and reservation orders on the route plans is explored.In addition,this paper also analyzes the necessity and prospect of this problem from the technical feasibility,social feasibility and practical feasibility,which provides a theoretical support for the future research on vehicle routing problem.Thirdly,based on the summary of the components and characteristics in the taxi fleet management system,the features of road network,passengers,vehicles,depots,objective function,and constraints are determined.Therefore,it builds the mathematical model of taxi dispatching problem with joint consideration of real-time orders and reservation orders.Fourthly,based on the mathematical formulation,a two-phase algorithm for dynamic taxi dispatch is presented.Because of the immediacy of real-time orders,the insertion algorithm is used to make the final route plan for the real-time order and the initial route plan of the reservation order in the first phase.In the second stage,the improved variable neighborhood search algorithm optimizes the initial route plans of unfixed reservation orders,in which reinforcement learning is introduced to change the neighborhood structure of VNS to consider the impact of future demand on the scheduling scheme.In addition,according to the spatial and temporal distribution of orders,the dispatch rules of idle taxis are determined.Finally,in order to verify the rationality of the mathematical formulation and the validity of the solution algorithm,the dataset of taxi orders in Haikou was used as the test data.And this paper uses the novel two-phase algorithm and the comparison algorithms(variable neighborhood search,tabu search algorithm and insertion algorithm)to make route plans.Objective function value,detour cost,passenger waiting cost,idle cost and acceptance rate of orders are defined as evaluation indexes to display the performance of the results.In addition,sensitivity analysis is performed on the factors about the scheduling plans to explore the impact on this problem.In this paper,there are 43 figures,14 tables and 98 references.