Urban Taxi Optimization Methods Based On GPS Trajectories

Taxis play an important role in the current public transportation system,as they provide fast,secure and personalized travel for passengers.Recently,with the emergence of sharing economy,ride sharing is able to offer budget-friendly taxi service to arrange one-time shared rides on-the-fly.Moreover,ride sharing has the potential to be combined with the upcoming shared autonomous vehicles to become a new taxi service,called dynamic shared autonomous taxi.This paper explores how to improve the urban taxi utilization to provide better travel services for the urban population.To better utilize the GPS trajectory data for the taxi optimization,an adaptive GPS sampling method is first proposed to reduce the data redundancy.Then three key problems in urban taxi optimization,i.e.,cruising route recommendation for the traditional taxis,ride matching for the ride sharing vehicles,and fleet size calculation for the dynamic shared autonomous taxis,are studied.The contributions of this paper can be summarized as follows:(1)An adaptive GPS sampling method is proposed.We formulate the adaptive sampling problem as a reinforcement learning problem.A deep reinforcement learning model called ASRL is proposed to learn a GPS sampling policy network by giving rewards.To learn the reward function based on multiple features,the expert sampled trajectories are first generated to provide the demonstration.Then the IRL technique is utilized to recover the reward function from these demonstrations.The learned GPS sampling policy network is then used in an online manner to dynamically adjust the GPS sampling interval.The experiment validates that the proposed ASRL model can reduce the GPS sampling point number significantly while keeping the trajectory tracking accuracy for future use.(2)A taxi cruising route recommendation method is proposed.To identify the hotspots,a probabilistic network model is first developed to predict pick-up probability and capacity of each location by using Kalman Filtering method.The load balance between passengers and taxis are then taken into consideration when recommending the driving route.Moreover,Map Reduce and a data structure Kd S-tree are applied to improve recommendation efficiency.Experimental results validate that the proposed method can significantly reduce the taxi cruising distance.(3)A dynamic ride matching method is proposed.Given ride sharing vehicles and passengers,the method aims to dispatch the passengers to maximize the vehicles’ potential pick-up probability,subject to the passengers’ time constraints and vehicles’ capacity constraint.A grid network is first constructed to predict each grid’s pick-up probability from historical GPS trajectories.To dispatch multiple passengers,an iterated local search method is then proposed to find the solution with overall maximized potential pick-up probability for the vehicles.Moreover,we propose the data structure TKd S-tree to improve the ride matching efficiency.Experiment shows that the proposed method performed better than other methods in service rate,share rate,and rider waiting time.(4)A minimum fleet sizing method is proposed to accurately determine the fleet size for dynamic shared autonomous taxis.The travel demands are first predicted by an ensemble method that takes account of temporal correlations between regions.Then a concept called demand utility is proposed to measure the travel demands when determining the ride sharing relations.Based on the ride sharing relations,the minimum fleet size is calculated based on a trip graph by the Hopcroft-Karp algorithm.Experiment validates that by considering the travel demands in rides haring relation determination,the proposed method can significantly reduce the fleet size compared to the existing methods.Moreover,the result shows that by allowing ridesharing,the taxi fleet size can be reduced by 30%.