Method and apparatus for probe-based routing

• US 10,033,624 B2
• Filed: 11/14/2013
• Issued: 07/24/2018
• Est. Priority Date: 11/14/2013
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: Rolf, Daniel, Karge, Bjorn, Praetz, Ullrich, Jehlicka, Prokop
• Primary Examiner(s): Lazaro, David
• Assistant Examiner(s): Shaw, Robert
• Application Number:
  US14/080,569
• Publication Number:
  US 20150134850A1
• Time in Patent Office: 1,713 Days
• 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: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length

Abstract

An approach is provided for providing routing calculations and route guidance based on geographic positioning and/or other sensor data from one or more mobile devices independent of map data. A routing platform processes and/or facilitates a processing of one or more probe data samples associated with at least one mobile device to determine one or more device tracks. The routing platform processes and/or facilitates a processing of the one or more device tracks to determine at least one tessellation, wherein the at least one tessellation is a subdivision of a plane or sphere into one or more tiles and a plurality of segments. The routing platform further determines one or more relationships between one or more of the plurality of segments based, at least in part, on a mapping of the one or more device tracks against the at least one tessellation.

Claims

1. A method comprising:

processing, by an apparatus, one or more probe data samples associated with at least one mobile device to determine one or more device tracks;

processing, by the apparatus, the one or more device tracks to determine at least one tessellation, wherein the at least one tessellation is a division of a plane or sphere into tiles and each edge of each of the tiles is subdivided into a plurality of segments;

dividing the one or more device tracks using the tiles, by the apparatus, into one or more legs each of which intersects two of the plurality of segments of a respective one of the tiles;

determining, by the apparatus, one or more bundles in the respective tile, wherein each of the one or more bundles includes an area enclosed by the two segments on two different edges in the respective tile and by one or more straight lines linking end points of the two segments;

generating, by the apparatus, a travel time curve for each of the one or more bundles based on a plurality of travel times between the two segments of the respective bundle at a given time without reference to waypoints of the one or more device tracks; and

determining, by the apparatus, a route made of a subset of the one or more bundles based on the travel time curve and one or more criteria,

wherein the one or more criteria include one or more cost functions, a shortest path routing, a fastest path routing, one or more fuel consumption functions, one or more favored road types, one or more speed limits, a number of lanes, one or more access restrictions, one or more hours of a day, a day of a week, a real-time latency, one or more vehicle trajectory properties, or a combination thereof.

2. A method of claim 1, further comprising:

estimating a traverse time over the route at the given time by adding the respective travel time curve.

3. A method of claim 1, further comprising:

determining the route through a network based, at least in part, on at least one bundle-to-bundle transition across the tiles, wherein the at least one bundle-to-bundle transition includes one of the segments shared by two of the bundles.

4. A method of claim 1, further comprising:

determining the at least one tessellation, the one or more tiles, the plurality of segments, or a combination thereof based, at least in part, on latitude/longitude coordinates, one or more probe data sampling intervals, or a combination thereof associated with the one or more device tracks.

5. A method of claim 1, further comprising:

weighing the one or more bundles based, at least in part, on one or more of the one or more legs intersecting multiple segments of the plurality of segments, wherein the route is further determined based on the weighting,

wherein the one or more probe data samples include, at least in part, a device session identification, a recording time, a latitude/longitude, or a combination thereof associated with the at least one mobile device.

6. A method of claim 5, further comprising:

filtering off erroneous and maliciously generated probe data samples via the weighting; and

determining the one or more device tracks based, at least in part, on the respective device session identification, recording time, latitude/longitude, or a combination thereof associated with the one or more probe data samples.

7. A method of claim 1, further comprising:

determining whether the one or more device tracks are valid based, at least in part, on one or more consistency rules, one or more constraints, one or more plausible travel trajectories, or a combination thereof,

wherein the one or more legs are further based, at least in part, on the one or more tracks being valid.

8. A method of claim 7, wherein the one or more constraints include, at least in part, at least one minimum number of probes per the one or more tracks, at least one minimum length of the one or more tracks, a distance and duration between probes matching a speed of the probes, or a combination thereof.

9. A method of claim 1, further comprising:

processing the one or more bundles to determine at least one cost-function associated with a shortest path route, an estimated travel time, an amount of fuel consumption, a favored road type, a popular route, or a combination thereof,

wherein the route is further based, at least in part, on the at least one cost-function.

10. A method of claim 1, further comprising:

filtering the one or more device tracks based, at least in part, on a time of day, a vehicle type, a specific provider, a real-time latency, one or more vehicle trajectory properties, or a combination thereof to determine one or more traffic patterns,

wherein the route is further based, at least in part, on the filtering.

11. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs,

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,

process one or more probe data samples associated with at least one mobile device to determine one or more device tracks;

process the one or more device tracks to determine at least one tessellation, wherein the at least one tessellation is a division of a plane or sphere into tiles and each edge of each of the tiles is subdivided into a plurality of segments;

divide the one or more device tracks using the tiles into one or more legs each of which intersects two of the plurality of segments of a respective one of the tiles;

determine one or more bundles in the respective tile, wherein each of the one or more bundles includes an area enclosed by the two segments on two different edges in the respective tile and by one or more straight lines linking end points of the two segments;

generate a travel time curve for each of the one or more bundles based on a plurality of travel times between the two segments of the respective bundle at a given time without reference to waypoints of the one or more device tracks; and

determine a route made of a subset of the one or more bundles based on the travel time curve and one or more criteria,

wherein the one or more criteria include one or more cost functions, a shortest path routing, a fastest path routing, one or more fuel consumption functions, one or more favored road types, one or more speed limits, a number of lanes, one or more access restrictions, one or more hours of a day, a day of a week, a real-time latency, one or more vehicle trajectory properties, or a combination thereof.

12. An apparatus of claim 11, wherein the apparatus is further caused to:

estimate a traverse time over the route at the given time by adding the respective travel time curve.

13. An apparatus of claim 11, wherein the apparatus is further caused to:

determine at least one navigable route through a network based, at least in part, on at least one bundle-to-bundle transition across the tiles, wherein the at least one bundle-to-bundle transition includes one of the segments shared by two of the bundles.

14. An apparatus of claim 11, wherein the apparatus is further caused to:

determine the at least one tessellation, the one or more tiles, the plurality of segments, or a combination thereof based, at least in part, on latitude/longitude coordinates, one or more probe data sampling intervals, or a combination thereof associated with the one or more device tracks.

15. An apparatus of claim 11, wherein the one or more probe data samples include, at least in part, a device session identification, a recording time, a latitude/longitude, or a combination thereof associated with the at least one mobile device.

16. An apparatus of claim 15, wherein the apparatus is further caused to:

determine the one or more device tracks based, at least in part, on the respective device session identification, recording time, latitude/longitude, or a combination thereof associated with the one or more probe data samples.

17. An apparatus of claim 11, wherein the apparatus is further caused to:

determine whether the one or more device tracks are valid based, at least in part, on one or more consistency rules, one or more constraints, one or more plausible travel trajectories, or a combination thereof,

wherein the one or more legs are further based, at least in part, on the one or more tracks being valid.

18. An apparatus of claim 17, wherein the one or more constraints include, at least in part, at least one minimum number of probes per the one or more tracks, at least one minimum length of the one or more tracks, a distance and duration between probes matching a speed of the probes, or a combination thereof.

19. An apparatus of claim 11, wherein the apparatus is further caused to:

process the one or more bundles to determine at least one cost-function associated with a shortest path route, an estimated travel time, an amount of fuel consumption, a favored road type, a popular route, or a combination thereof,

wherein the route is further based, at least in part, on the at least one cost-function.

20. An apparatus of claim 11, wherein the apparatus is further caused to:

filter the one or more device tracks based, at least in part, on a time of day, a vehicle type, a specific provider, a real-time latency, one or more vehicle trajectory properties, or a combination thereof to determine one or more traffic patterns,

wherein the route is further based, at least in part, on the filtering.