Systems and methods for digital route planning

• US 10,209,084 B2
• Filed: 05/15/2018
• Issued: 02/19/2019
• Est. Priority Date: 05/16/2017
• Status: Active Grant

• Current Assignee: Beijing Didi Infinity Technology And Development Co.Ltd.
• Original Assignee: Beijing Didi Infinity Technology And Development Co.Ltd.
• Inventors: Pan, Rui, Wang, Zheng
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): Li, Ce Li
• Application Number:
  US15/980,711
• Publication Number:
  US 20180335309A1
• Time in Patent Office: 280 Days
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G06F 15/76 Architectures of general purpose stored program computers with program plugboard G06F15/08; multicomputers G06F15/16
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A method for recommending a route includes obtaining a first start point and a first end point relating to a road network. The method also includes obtaining a route recommendation model. The method further includes determining a recommendation route from the first start point to the first end point based on the route recommendation model.

Claims

1. A method implemented on at least one device each of which has at least one processor and a storage device, the method comprising:

obtaining, by the at least one processor, a first start point and a first end point relating to a road network, wherein the first start point is acquired from a location device;

obtaining, by the at least one processor, a route recommendation model, wherein the route recommendation model is generated based on a method for generating a recommended route, the method comprising;

obtaining a second start point and a second end point relating to the road network;

obtaining a plurality of historical routes from a storage device, each of the plurality of historical routes including the second start point and the second end point;

determining a plurality of links between the second start point and the second end point;

determining primary weights of the plurality of links;

determining one or more ordinary routes from the second start point to the second end point based, at least in part, on the primary weights of the plurality of links;

adjusting primary weights of links on the one or more ordinary routes;

adjusting primary weights of links on the historical routes; and

determining the route recommendation model based on the adjusted weights of the links on the one or more ordinary routes and the adjusted weights of the links on the historical routes;

determining, by the at least one processor, a recommended route from the first start point to the first end point based on the route recommendation model; and

causing a user terminal to display the recommended route on an user interface.

2. The method of claim 1, wherein determining the primary weights of the plurality of links includes:

obtaining road network data related to the road network, the road network data including one or more road features of the plurality of links between the second start point and the second end point; and

determining the primary weights of the plurality of links based on the one or more road features of the plurality of links.

3. The method of claim 1, wherein the one or more ordinary routes are determined according to maximum margin planning (MMP) algorithm or maximum entropy inverse reinforcement learning (IRL) algorithm.

4. The method of claim 1, wherein the one or more ordinary routes are determined according to the MMP algorithm, the one or more ordinary routes being the shortest route from the second start point to the second end point.

5. The method of claim 1, wherein adjusting the primary weights of the links on the one or more ordinary routes and the primary weights on the historical routes includes:

increasing the primary weights of the links on the historical routes; and

decreasing the primary weights of the links on the one or more ordinary routes.

6. The method of claim 5, wherein

the weights of the links on historical routes are increased by first values,

the weights of the links on one or more ordinary routes are decreased by second values, and

the first values and the second values are determined based on one or more hyper-parameters and an optimization algorithm.

7. The method of claim 5, wherein

the weights of the links on historical routes are increased by third values,

the weights of the links on one or more ordinary route are decreased by fourth values, and

the third values and the fourth values are determined based on a softmax algorithm.

8. The method of claim 1, further comprising:

obtaining validation data;

determining a hit rate of the recommended route based on the validation data, the recommended route being determined based on the route recommendation model;

determining whether the hit rate is smaller than a threshold; and

in response to the hit rate being smaller than the threshold, adjusting the adjusted weights of the links on the one or more ordinary routes and the adjusted weights of the links on the historical routes.

9. The method of claim 8, further comprising:

in response to the hit rate being larger than the threshold, outputting the route recommendation model to a server.

10. A system for recommending a route, comprising:

a storage device including a set of instructions;

at least one processor in communication with the storage device, wherein when executing the set of instructions, the at least one processor is configured to cause the system to;

obtain a first start point and a first end point relating to a road network, wherein the first start point is acquired from a location device;

obtain a second start point and a second end point relating to the road network;

obtain, from a storage device, a plurality of historical routes, each of the plurality of historical routes including the second start point and the second end point;

determine a plurality of links between the second start point and the second end point;

determine primary weights of the plurality of links;

determine one or more ordinary routes from the second start point to the second end point based, at least in part, on the primary weights of the plurality of links;

adjust primary weights of links on the one or more ordinary routes;

adjust primary weights of links on the historical routes;

determine a route recommendation model based on the adjusted weights of the links on the one or more ordinary routes and the adjusted weights of the links on the historical routes;

determine a recommended route from the first start point to the first end point based on the route recommendation model; and

cause a user terminal to display an recommended route on the user interface.

11. The system of claim 10, wherein to determine the primary weights of the plurality of links, the at least one processor is further configured to cause the system to:

obtain road network data related to the road network, the road network data including one or more road features of the plurality of links between the second start point and the second end point; and

determine the primary weights of the plurality of links based on the one or more road features of the plurality of links.

12. The system of claim 10, the one or more ordinary routes are determined according to maximum margin planning (MMP) algorithm or maximum entropy inverse reinforcement learning (IRL) algorithm.

13. The system of claim 10, the one or more ordinary routes are determined according to the MMP algorithm, the one or more ordinary routes being the shortest route from the second start point to the second end point.

14. The system of claim 10, wherein to adjust the primary weights of the links on the one or more ordinary routes and adjust the primary weights on the historical routes, the at least one processor is further configured to cause the system to:

increase the primary weights of the links on the historical routes; and

decrease the primary weights of the links of the one or more ordinary routes.

15. The system of claim 14, wherein

the weights of the links on historical routes are increased by first values,

the weights of the links on one or more ordinary routes are decreased by second values, and

the first values and the second values are determined based on one or more hyper-parameters and an optimization algorithm.

16. The system of claim 14, wherein

the weights of the links on historical routes are increased by third values,

the weights of the links on one or more ordinary routes are decreased by fourth values, and

the third values and the fourth values are determined based on a softmax algorithm.

17. The system of claim 10, the at least one processor is further configured to cause the system to:

obtain validation data;

determine a hit rate of the recommended route based on the validation data, the recommended route being determined based on the route recommendation model;

determine whether the hit rate is smaller than a threshold; and

in response to the hit rate being smaller than the threshold, adjust the adjusted weights of the links on the one or more ordinary routes and the adjusted weights of the links on the historical routes.

18. A non-transitory computer readable medium storing instructions, the instructions, when executed by a computing device, causing the computing device to:

obtain a first start point and a first end point relating to a road network, wherein the first start point is acquired from a location device;

obtain a second start point and a second end point relating to the road network;

obtain, from a storage device, a plurality of historical routes, each of the plurality of historical routes including the second start point and the second end point;

determine a plurality of links between the second start point and the second end point;

determine primary weights of the plurality of links;

determine one or more ordinary routes from the second start point to the second end point based, at least in part, on the primary weights of the plurality of links;

adjust primary weights of links on the one or more ordinary routes;

adjust primary weights of links on the historical routes;

determine a route recommendation model based on the adjusted weights of the links on the one or more ordinary routes and the adjusted weights of the links on the historical routes

the route recommendation model being related to weights of a first plurality of links, the first plurality of links being between the first start point and the first end point;

determine a recommended route from the first start point to the first end point based on the route recommendation model; and

cause a user terminal to display the recommended route on an user interface.