# US 10,309,795 B2 · Methods and systems for generating routing policies and routes > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,309,795 B2 - Document ID: US10309795B2 - Status: Granted - Kind: B2 - Application number: 15/549,205 - Filed: 2016-02-26 - Published: 2018-01-25 - Granted: 2019-06-04 - Earliest claimed: 2015-02-26 - Assignees: Tomtom Navigation B.V. - Applicants: TomTom Navigation B.V. - Inventors: Felix Godafoss König; Heiko Schilling - Web page: https://patentgrep.com/patent/US10309795B2 ## CPC - G01C 21/3617: {using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement} - G01C 21/3415: {Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents} - G01C 21/3484: {Personalized, e.g. from learned user behaviour or user-defined profiles} - 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)} - G01C 21/3676: {Overview of the route on the road map} - G08G 1/096838: {where the user preferences are taken into account or the user selects one route out of a plurality} - G08G 1/096844: {where the complete route is dynamically recomputed based on new data} - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93}) ## Abstract A method of generating a routing policy from an origin to a destination through a navigable network, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable segments of the navigable network, each segment having associated therewith data indicative of an expected travel time along the segment. The expected travel times are used for respective segments of the electronic map to determine a route from the origin to the destination that has a shortest expected journey time using a deterministic routing algorithm. A stochastic routing algorithm is then used to generate a routing policy that maximizes the probability of arriving at the destination within a time budget from leaving the origin, wherein the time budget is based at least on said determined shortest expected journey time. A route from the origin to the destination can then be generated by applying the routing policy to a scenario in which each segment is transited in a time based on the data indicative of the expected travel time associated with the respective segment. ## Claims ### Claim 1 A method of generating a routing policy from an origin to a destination through a navigable network, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable segments of the navigable network, each segment having associated therewith data indicative of an expected travel time along the segment, the method comprising: using the expected travel times for respective segments of the electronic map to determine a route from the origin to the destination that has a shortest expected journey time using a deterministic routing algorithm; and using a stochastic routing algorithm to generate a routing policy that maximises the probability of arriving at the destination within a time budget from leaving the origin, wherein the time budget is based at least on said determined shortest expected journey time. ### Claim 2 (depends on 1) The method of claim 1, wherein the routing policy is a solution to a set of non-linear equations that determine the next segment to take at a node of the electronic map based on the travel time taken to reach the node from the origin, such that the probably of arriving at the destination within the time budget is maximised. ### Claim 3 (depends on 1) The method of claim 1, wherein the time budget is further based on one or more of: an input from the user; time of day; day of the week; distance between the origin and the destination; and conditions on the navigable network, such as traffic and weather. ### Claim 4 (depends on 1) The method of claim 1, wherein the time budget equals, or is based on, the shortest expected journey time multiplied by a scaling factor. ### Claim 5 (depends on 4) The method of claim 4, wherein the scaling factor is based on one or more of: an input from the user; time of day; day of the week; distance between the origin and the destination; and conditions on the navigable network, such as traffic and weather. ### Claim 6 (depends on 1) The method of claim 1, wherein each segment in the electronic map is connected to another segment by a node, the method further comprising: generating a route from the origin to the destination by applying the generated routing policy to a scenario in which each segment is transited in a time based on the data indicative of the expected travel time for the respective segment, such that the arrival time at a node is the sum of the expected travel times of the segments forming the route from the origin to the node. ### Claim 7 (depends on 1) A non-transitory computer readable medium comprising instructions which, when executed by at least one processor of a computing device, cause the computing device to operate according to the method of claim 1 perform a method for generating a routing policy from an origin to a destination through a navigable network, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable segments of the navigable network, each segment having associated therewith data indicative of an expected travel time along the segment, the method comprising: using the expected travel times for respective segments of the electronic map to determine a route from the origin to the destination that has a shortest expected journey time using a deterministic routing algorithm; and using a stochastic routing algorithm to generate a routing policy that maximises the probability of arriving at the destination within a time budget from leaving the origin, wherein the time budget is based at least on said determined shortest expected journey time. ### Claim 8 A method of generating a route between an origin and a destination through a navigable network, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable segments of the navigable network, each segment being connected to another segment by a node, and each segment having associated therewith data indicative of an expected travel time along the segment, the method comprising: accessing a routing policy that maximises the probability of arriving at the destination within a predetermined time budget; and generating a route from the origin to the destination by applying the routing policy to a scenario in which each segment is transited in a time based on the data indicative of the expected travel time for the respective segment, such that the arrival time at a node is the sum of the expected travel times of the segments forming the route from the origin to the node. ### Claim 9 (depends on 8) The method of claim 8, wherein the route is generated by applying the routing policy to a scenario in which each segment is transited in the expected travel time for the respective segment. ### Claim 10 (depends on 8) The method of claim 8, comprising displaying the generated route to a user on a display device. ### Claim 11 (depends on 8) The method of claim 8, comprising generating a plurality of routes from the origin to the destination, each route being generated by applying the generated routing policy to a different scenario, and wherein the time for transiting for at least some the segments differ between scenarios. ### Claim 12 (depends on 11) The method of claim 11, comprising generating a first route by applying the routing policy to a scenario in which each segment is transited in the expected travel time for the respective segment, and generating a second route by applying the routing policy to a scenario in which none or only some of the segments are transited in the expected travel time for the respective segment. ### Claim 13 (depends on 11) The method of claim 11, comprising displaying, the plurality of generated routes to a user on a display device. ### Claim 14 (depends on 13) The method of claim 13, comprising receiving a selection of one of the plurality of routing policies from the user based on the displayed plurality of generated routes. ### Claim 15 (depends on 8) The method of claim 8, comprising accessing a plurality of routing policies, each routing policy maximising the probability of arriving at the destination within a different predetermined time budget, and generating a plurality of routes from the origin to the destination by applying each of the plurality of routing policies to a scenario in which each segment is transited in a time based on the data indicative of the expected travel time for the respective segment, such that the arrival time at a node is the sum of the expected travel times of the segments forming the route from the origin to the node. ### Claim 16 (depends on 1) The method of claim 1, comprising outputting navigation instructions to guide the user from the origin to the destination based on a generated routing policy. ### Claim 17 (depends on 1) The method of claim 1, wherein the data indicative of an expected travel time along a segment associated with each segment is derived from position data collected from one or more users that have traversed the respective segment. ### Claim 18 A system for generating a routing policy from an origin to a destination through a navigable network, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable segments of the navigable network, each segment having associated therewith data indicative of an expected travel time along the segment, the system comprising one or more processors arranged to: use the expected travel times for respective segments of the electronic map to determine a route from the origin to the destination that has a shortest expected journey time using a deterministic routing algorithm; and use a stochastic routing algorithm to generate a routing policy that maximises the probability of arriving at the destination within a time budget from leaving the origin, wherein the time budget is based at least on said determined shortest expected journey time. ### Claim 19 (depends on 18) The system of claim 18, wherein the system comprises a portable navigation device or navigation device integrated in a vehicle. ### Claim 20 A system for generating a route between an origin and a destination through a navigable network, the navigable network being represented by an electronic map comprising a plurality of segments representing navigable segments of the navigable network, each segment being connected to another segment by a node, and each segment having associated therewith data indicative of an expected travel time along the segment, the system comprising one or more processors arranged to: access a routing policy that maximises the probability of arriving at the destination within a predetermined time budget; and generate a route from the origin to the destination by applying the routing policy to a scenario in which each segment is transited in a time based on the data indicative of the expected travel time associated with the respective segment, such that the arrival time at a node is the sum of the times to travel the segments forming the route from the origin to the node.