Method for recommending taxi passenger-searching strategy based on Markov decision process

Abstract

The invention provides a method for recommending a taxi passenger-searching strategy based on a Markov decision process. The method comprise the following steps of data preprocessing: including deleting abnormal records, determining trajectories according to blocks, and calculating the passenger carrying probability and the expected revenue of each block; modeling: using a Markov decision processto model a passenger-searching optimal strategy problem; calculating the optimal solution: Using Q-learning to solve the optimal solution; online recommendation: giving the optimal passenger-searchingstrategy in consideration of load balancing and real-time traffic conditions. The method for recommending a taxi passenger-searching strategy based on a Markov decision process provides two differentstrategies for the waiting area and the searching areas, can calculate the expected revenue of each strategy according to the historical trajectories, receives the real-time traffic conditions and processes the taxi recommendation requests by a dispatching system so that the optimal strategy recommendation can be given after a taxi passenger gets off.

Description

technical field [0001] The present invention relates to a taxi management system, and in particular to a method for recommending a taxi-finding strategy based on a Markov decision process, in particular to using a Markov decision-making process to model a taxi-finding problem, and using Q-learning Solve the optimal solution, classify and find customers, and recommend the driver's customer-seeking strategy. Background technique [0002] In recent years, with the rapid development of wireless sensor technology, GPS equipment has been widely used by taxis, and a lot of taxi trajectory information has been generated. This information is already used in many fields, such as urban calculation and route planning. [0003] Unlike buses and subways that follow a fixed route every day, each taxi driver has his own customer-seeking strategy in order to maximize revenue. By analyzing 1,500,000,000 taxi track information collected in Shanghai within one year, we found that different cu...

AI Technical Summary

Problems solved by technology

Although existing methods achieve this goal, they still have some limitations

[0005] The first is the problem of complexity: the problem of finding the optimal strategy is an NP-hard problem, the complexity of the exhaustive method is too high, and the recursive tree method affects part of the accuracy under the premise of reducing the complexity

Second, the recommendation results of existing systems rarely take into account the influence of the real-time environment

When many drivers send recommendation requests in the same place at the same time, most of the existing recommendation systems will provide the same route to these drivers without considering the competition among them

At the same time, these systems also ignore the influence of real-time road conditions, and the recommended route may pass through some very congested road sections

Even if the possibility of customers on these road sections is relatively high, it is difficult to bring higher income to drivers

Finally, the existing system does not take into account the possibility of waiting for guests nearby to bring more benefits

Images