Generating routes to optimise traffic flow
First Claim
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.
4 Assignments
0 Petitions
Accused Products
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.
-
Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14, 15, 16, 17)
-
-
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.
-
Specification