Generating routes to optimise traffic flow

• US 10,345,109 B2
• Filed: 09/15/2014
• Issued: 07/09/2019
• Est. Priority Date: 09/15/2013
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom Navigation B.V (TomTom NV)
• Inventors: Witte, Nikolaus, Kannenberg, Oliver, Kesting, Arne
• Primary Examiner(s): Badii, Behrang
• Assistant Examiner(s): Greene, Daniel L
• Application Number:
  US15/022,002
• Publication Number:
  US 20160223348A1
• Time in Patent Office: 1,758 Days
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality

Abstract

A method is disclosed for determining a route in an area covered by an electronic map, the map comprising a plurality of segments representing navigable segments of a navigable network in the area covered by the electronic map. The method involves generating a plurality of routes through the navigable network between a first location and a second location, determining a relative traffic flow value for each of the routes using data indicative of a relative current capacity of segments of the navigable network, and selecting a given one of the routes from the plurality of routes for use in navigating between the first location and the second location. The probability of a given one of the plurality of routes being selected is based on the determined relative flow value for the route.

Claims

1. A method of determining a route in an area covered by an electronic map, the electronic map comprising a plurality of segments representing navigable segments of a navigable network in the area covered by the electronic map, the method comprising:

generating, using a processor, a plurality of routes through the navigable network between a first location and a second location, the generating comprising, selecting, as the plurality of routes, a subset of possible routes between the first location and the second location, the plurality of routes including a first route that is most optimal among the possible routes for a specified route parameter and at least one other route from among the possible routes having the specified route parameter within a predetermined range of the first route;

determining, using the processor, a relative traffic flow value for each of the routes using data indicative of a current capacity of segments of the navigable network, the relative traffic flow value for each route being indicative of a traffic flow value for the route relative to a total traffic flow value for all of the plurality of routes;

randomly selecting, using the processor, a given one of the routes from among the plurality of routes for use in navigating between the first location and the second location with a probability of selecting each route being based on the determined relative flow value for the route, so that any route among the plurality of routes can be selected with a probability that is proportional to the flow rate for the route relative to the total traffic flow value for all of the plurality or routes; and

outputting, using the processor, data indicative of the selected route.

2. The method of claim 1, wherein the first location is a location at or ahead of current location along a predetermined route being navigated.

3. The method of claim 1, wherein the specified route parameter is a time for traveling a given route or a distance of the given route.

4. The method of claim 1, wherein the current capacity data of each navigable segment that is used in determining the flow values for the routes is indicative of the current capacity of the segment relative to a maximum capacity for the segment.

5. The method of claim 1, wherein the current capacity data for each navigable segment used in determining the flow values for each of the routes is based at least in part on live capacity data.

6. The method of claim 1, wherein the relative flow values determined for each of the plurality of routes are based on a flow along each of the routes under conditions of maximum flow between the first and second locations via the plurality of routes between the first location and the second location.

7. The method of claim 1, wherein the probability for selecting a given route is proportional or corresponds to the flow value for the route.

8. The method of claim 1, further comprising receiving the current capacity data over a telecommunications network.

9. The method of claim 1, wherein said outputting comprises outputting the selected route to a user.

10. The method of claim 1, wherein said outputting comprises providing a set of navigation instructions for guiding a user along the selected route.

11. The method of claim 1, wherein the method is carried out by a navigation device.

12. A system, comprising one or more processors and a memory storing an electronic map, the electronic map comprising a plurality of segments representing navigable segments of a navigable network in a area covered by the electronic map, the one or more processors being arranged to:

generate a plurality of routes through the navigable network between a first location and a second location, the generating comprising, selecting, as the plurality of routes, a subset of possible routes between the first location and the second location, the plurality of routes including a first route that is most optimal among the possible routes for a specified route parameter and at least one other route from among the possible routes having the specified route parameter within a predetermined range of the first route;

determine a relative traffic flow value for each of the routes using data indicative of a current capacity of segments of the navigable network, the relative traffic flow value for each of the routes being indicative of a traffic flow value for the route relative to a total traffic flow value for all of the plurality of routes;

randomly select a given one of the routes from among the plurality of routes for use in navigating between the first location and the second location with a probability of selecting each route being based on the determined relative flow value for the route, so that any route among the plurality of routes can be selected with a probability that is proportional to the flow rate for the route relative to the total traffic flow value for all of the plurality of routes; and

output data indicative of the selected route.

13. The system of claim 12, wherein the system is a mobile device.

14. The system of claim 13, wherein the system is a portable navigation device.

15. The system of claim 13, wherein the mobile device is arranged to store data indicative of time-dependent historical capacity of segments of the navigable network.

16. The system of claim 15, wherein the mobile device is communicatively coupled to a server and arranged to receive the current capacity of segments of the navigable network from the server.

17. The system of claim 16, wherein the mobile device is arranged to receive the current capacity of a road segment of the segments of the navigable network when live data differs from the historical capacity for the road segment.

18. A non-transitory computer readable medium comprising instructions which, when executed by one or more processors of a system, cause the system to perform a method of determining a route in an area covered by an electronic map, the electronic map comprising a plurality of segments representing navigable segments of a navigable network in the area covered by the electronic map, the method comprising:

generating, using a processor, a plurality of routes through the navigable network between a first location and a second location, the generating comprising, selecting, as the plurality of routes, a subset of possible routes between the first location and the second location, the plurality of routes including a first route that is most optimal among the possible routes for a specified route parameter and at least one other route from among the possible routes having the specified route parameter within a predetermined range of the first route;

determining, using the processor, a relative traffic flow value for each of the routes using data indicative of a current capacity of segments of the navigable network, the relative traffic flow value for each route being indicative of a traffic flow value for the route relative to a total traffic flow value for all of the plurality of routes;

randomly selecting, using the processor, a given one of the routes from among the plurality of routes for use in navigating between the first location and the second location with a probability of selecting each route being based on the determined relative flow value for the route, so that any route among the plurality of routes can be selected with a probability that is proportional to the flow rate for the route relative to the total traffic flow value for all of the plurality of routes; and

outputting, using the processor, data indicative of the selected route.