System and method for determining passenger-seeking ride-sourcing vehicle navigation

• US 11,094,028 B2
• Filed: 12/05/2019
• Issued: 08/17/2021
• Est. Priority Date: 03/28/2018
• Status: Active Grant

• Current Assignee: Beijing Didi Infinity Technology And Development Co.Ltd.
• Original Assignee: Beijing Didi Infinity Technology And Development Co.Ltd.
• Inventors: Ke, Jintao, Wu, Guojun, Xu, Zhengtian, Yang, Hai, YiN, Yafeng, Ye, Jieping
• Primary Examiner(s): Harrington, Michael P
• Assistant Examiner(s): Clare, Mark C
• Application Number:
  US16/703,945
• Publication Number:
  US 20200175635A1
• Time in Patent Office: 621 Days
• Field of Search: 705 13
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 30/0208 Trade or exchange of goods or services in exchange for incentives or rewards
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• CPC Class Codes: G06Q 30/0605 Supply or demand aggregation
• CPC Class Codes: G06Q 30/0613 Third-party assisted
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching

Abstract

A method comprises: obtaining historical vehicle service data in an area for a time period including historical locations of passenger-seeking vehicles with respect to time, historical locations of passenger orders with respect to time, and historical trip fares with respect to pick-up locations and time; discretizing the area into a plurality of zones and discretizing the time period into a plurality of time segments; aggregating the historical vehicle service data according the zones and time segments; obtaining an expected reward for a passenger-seeking vehicle to move from zone A to each neighboring zone of the zone A based on the aggregated historical vehicle service data; and obtaining a probability of a passenger-seeking vehicle moving from zone A to a neighboring zone B based on the expected reward for the passenger-seeking vehicle to move from zone A to the each neighboring zone of the zone A.

Claims

1. A method for determining passenger-seeking ride-sourcing vehicle navigation, comprising:

obtaining historical vehicle service data in an area for a time period;

discretizing the area into a plurality of zones and discretizing the time period into a plurality of time segments;

aggregating the historical vehicle service data according to the plurality of zones and the plurality of time segments;

obtaining an expected reward for a passenger-seeking ride-sourcing vehicle to move from zone A to each neighboring zone of the zone A within one of the plurality of time segments based on the aggregated historical vehicle service data associated with one or more explanatory variables including at least an expected driver stay time, wherein the expected driver stay time comprises a historical average time for one or more passenger-seeking ride-sourcing vehicles staying in zone A within the one of the plurality of time segments;

determining a probability of the passenger-seeking ride-sourcing vehicle moving from zone A where the passenger-seeking ride-sourcing vehicle is located to a neighboring zone B based at least on the expected rewards for the passenger-seeking ride-sourcing vehicle to move from zone A to the each neighboring zone of the zone A; and

navigating the passenger-seeking ride-sourcing vehicle based on the determined probability.

2. The method of claim 1, wherein the historical vehicle service data includes historical locations of passenger-seeking ride-sourcing vehicles with respect to time, historical locations of passenger orders with respect to time, and historical trip fares with respect to pick-up locations and time.

3. The method of claim 1, wherein:

the expected reward for the passenger-seeking ride-sourcing vehicle to move from zone A to the each neighboring zone of the zone A is based on one or more explanatory variables; and

the explanatory variables comprise at least one of;

an expected pickup time, an expected trip fare, an expected passenger waiting time, an expected number of orders, an expected answer rate, or the expected driver stay time.

4. The method of claim 3, wherein:

the explanatory variables comprise one-step explanatory variables, two-step explanatory variables, and three-step explanatory variables;

the one-step explanatory variables comprise vectors of;

the expected pickup time, the expected trip fare, the expected passenger waiting time, the expected number of orders, the expected answer rate, and the expected driver stay time in zone B;

the two-step explanatory variables comprise vectors of;

the expected pickup time, the expected trip fare, the expected passenger waiting time, the expected number of orders, the expected answer rate, and the expected driver stay time in zone C, the zone C being a neighboring zone of zone B; and

the three-step explanatory variables comprise vectors of;

the expected pickup time, the expected trip fare, the expected passenger waiting time, the expected number of orders, the expected answer rate, and the expected driver stay time in zone D, the zone D being a neighboring zone of zone C.

5. The method of claim 3, wherein:

the expected pickup time for the one of the plurality of time segments comprises a historical average pick-up time for passenger-seeking ride-sourcing vehicles to pick up passengers in zone A;

the pick-up time is a time difference between a time of the passenger-seeking ride-sourcing vehicle receiving an order of a passenger and a time of the passenger being picked up by the passenger-seeking ride-sourcing vehicle; and

the order of the passenger was received within the one of the plurality of time segments.

6. The method of claim 3, wherein:

the expected trip fare for the one of the plurality of time segments comprises a historical average trip fare for passenger'"'"'s orders that were received in zone A within the one of the plurality of time segments.

7. The method of claim 3, wherein:

the expected passenger waiting time for one of the plurality of time segments comprises a historical average waiting time for passenger orders placed in zone A and received within the one of the plurality of time segments; and

the waiting time is a time difference between a time when a passenger order was placed and a time when the passenger was picked up.

8. The method of claim 3, wherein:

the expected number of orders for one of the plurality of time segments comprises a historical average number of passenger orders in zone A within the one of the plurality of time segments.

9. The method of claim 3, wherein:

the expected answer rate comprises a number of satisfied passenger orders to a number of requested passenger orders in zone A within the one of the plurality of time segments.

10. A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, cause the one or more processors to perform a method for determining passenger-seeking ride-sourcing vehicle navigation, the method comprising:

obtaining historical vehicle service data in an area for a time period;

discretizing the area into a plurality of zones and discretizing the time period into a plurality of time segments;

aggregating the historical vehicle service data according to the plurality of zones and the plurality of time segments;

obtaining an expected reward for a passenger-seeking ride-sourcing vehicle to move from zone A to each neighboring zone of the zone A within one of the plurality of time segments based on the aggregated historical vehicle service data associated with one or more explanatory variables including at least an expected driver stay time, wherein the expected driver stay time comprises a historical average time for one or more passenger-seeking ride-sourcing vehicles staying in zone A within the one of the plurality of time segments;

determining a probability of the passenger-seeking ride-sourcing vehicle moving from zone A where the passenger-seeking ride-sourcing vehicle is located to a neighboring zone B based at least on the expected rewards for the passenger-seeking ride-sourcing vehicle to move from zone A to the each neighboring zone of the zone A; and

navigating the passenger-seeking ride-sourcing vehicle based on the determined probability.

11. The non-transitory computer-readable storage medium of claim 10, wherein the historical vehicle service data includes historical locations of passenger-seeking ride-sourcing vehicles with respect to time, historical locations of passenger orders with respect to time, and historical trip fares with respect to pick-up locations and time.

12. The non-transitory computer-readable storage medium of claim 10, wherein:

the expected reward for the passenger-seeking ride-sourcing vehicle to move from zone A to the each neighboring zone of the zone A is based on one or more explanatory variables; and

the explanatory variables comprise at least one of;

an expected pickup time, an expected trip fare, an expected passenger waiting time, an expected number of orders, an expected answer rate, or the expected driver stay time.

13. The non-transitory computer-readable storage medium of claim 12, wherein:

the explanatory variables comprise one-step explanatory variables, two-step explanatory variables, and three-step explanatory variables;

the one-step explanatory variables comprise vectors of;

the expected pickup time, the expected trip fare, the expected passenger waiting time, the expected number of orders, the expected answer rate, and the expected driver stay time in zone B;

the two-step explanatory variables comprise vectors of;

the expected pickup time, the expected trip fare, the expected passenger waiting time, the expected number of orders, the expected answer rate, and the expected driver stay time in zone C, the zone C being a neighboring zone of zone B; and

the three-step explanatory variables comprise vectors of;

the expected pickup time, the expected trip fare, the expected passenger waiting time, the expected number of orders, the expected answer rate, and the expected driver stay time in zone D, the zone D being a neighboring zone of zone C.

14. The non-transitory computer-readable storage medium of claim 12, wherein:

the expected pickup time for the one of the plurality of time segments comprises a historical average pick-up time for passenger-seeking ride-sourcing vehicles to pick up passengers in zone A;

the pick-up time is a time difference between a time of the passenger-seeking ride-sourcing vehicle receiving an order of a passenger and a time of the passenger being picked up by the passenger-seeking ride-sourcing vehicle; and

the order of the passenger was received within the one of the plurality of time segments.

15. The non-transitory computer-readable storage medium of claim 12, wherein:

the expected trip fare for one of the one of the plurality of time segments comprises a historical average trip fare for passenger'"'"'s orders that were received in zone A within the one of the plurality of time segments.

16. The non-transitory computer-readable storage medium of claim 12, wherein:

the expected passenger waiting time for one of the one of the plurality of time segments comprises a historical average waiting time for passenger orders placed in zone A and were received within the one of the plurality of time segments; and

the waiting time is a time difference between a time when a passenger order was placed and a time when the passenger was picked up.

17. The non-transitory computer-readable storage medium of claim 12, wherein:

the expected number of orders for the one of the plurality of time segments comprises a historical average number of passenger orders in zone A within the one of the plurality of time segments.

18. The non-transitory computer-readable storage medium of claim 12, wherein:

the expected answer rate comprises a number of satisfied passenger orders to a number of requested passenger orders in zone A within the one of the plurality of time segments.

19. A system for determining passenger-seeking ride-sourcing vehicle navigation, comprising one or more processors and a non-transitory computer-readable storage medium storing instructions that, when executed by the one or more processors, cause the one or more processors to perform a method, the method comprising:

obtaining historical vehicle service data in an area for a time period;

discretizing the area into a plurality of zones and discretizing the time period into a plurality of time segments;

aggregating the historical vehicle service data according to the plurality of zones and the plurality of time segments;

obtaining an expected reward for a passenger-seeking ride-sourcing vehicle to move from zone A to each neighboring zone of the zone A within one of the plurality of time segments based on the aggregated historical vehicle service data associated with one or more explanatory variables including at least an expected driver stay time, wherein the expected driver stay time comprises a historical average time for one or more passenger-seeking ride-sourcing vehicles staying in zone A within the one of the plurality of time segments;

determining a probability of the passenger-seeking ride-sourcing vehicle moving from zone A where the passenger-seeking ride-sourcing vehicle is located to a neighboring zone B based at least on the expected rewards for the passenger-seeking ride-sourcing vehicle to move from zone A to the each neighboring zone of the zone A; and

navigating the passenger-seeking ride-sourcing vehicle based on the determined probability.