Predicting short term travel behavior with unknown destination

• US 9,983,016 B2
• Filed: 03/15/2016
• Issued: 05/29/2018
• Est. Priority Date: 03/15/2016
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Rolf, Daniel, Cajias, Raul
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): LOUIE, WAE LENNY
• Application Number:
  US15/070,480
• Publication Number:
  US 20170268894A1
• Time in Patent Office: 805 Days
• Field of Search: 701410, 701411, 701423, 701426, 701532, 701533
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• 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/36 Input/output arrangements for on-board computers

Abstract

Methods, apparatus, systems, and computer program products for predicting short term travel behavior of a user without knowing the user'"'"'s destination. In one embodiment, a method is provided. The method comprises receiving historical location information for a vehicle and querying a set of indexed partial routes. A partial route of the set of indexed partial routes has a compiled quantity assigned thereto. The method further comprises reducing the set of indexed partial routes to a set of candidate partial routes based at least in part on the historical location information and identifying a most likely partial route from the set of candidate partial routes based at least in part on the compiled quantity associated with each of the candidate partial routes.

Claims

1. A method for identifying a most likely partial route for a vehicle, the method comprising:

receiving, by an apparatus remotely located with respect to the vehicle and comprising a processor, a memory, and a communication interface configured to communicate via at least one network, historical location information for the vehicle, the historical location information provided by a vehicle apparatus onboard the vehicle, wherein (a) the vehicle apparatus comprises a location sensor, (b) at least a portion of the historical location information was generated by the location sensor, (c) the historical location information indicates a path traveled by the vehicle during the vehicle'"'"'s current travel, and (d) the path comprises a current location of the vehicle;

querying, by the apparatus, a set of indexed partial routes based at least in part on at least a portion of the path indicated by the historical information, a partial route of the set of indexed partial routes having a compiled quantity assigned thereto;

reducing, by the apparatus, the set of indexed partial routes to a set of candidate partial routes based at least in part on the path indicated by the historical location information; and

identifying, by the apparatus, a most likely partial route along which the vehicle is currently traveling from the set of candidate partial routes based at least in part on the compiled quantity associated with each of the candidate partial routes.

2. A method according to claim 1 wherein the set of indexed partial routes is built by at least:

identifying a plurality of origin-destination pairs;

assigning an individual quantity to an origin-destination pair of the plurality of origin-destination pairs;

determining a set of routes, each route of the set of routes being a route from an origin to a destination of one of the plurality of origin-destination pairs;

extracting a set of partial routes of a length N from the set of routes; and

assigning the compiled quantity to a partial route of the set of partial routes based at least in part on the individual quantity assigned to one of the plurality of origin-destination pairs, wherein the route from the origin to the destination of the origin-destination pair comprises the partial route.

3. A method according to claim 2 wherein the individual quantity is not based on probe data.

4. A method according to claim 2 wherein the individual quantity assigned to an origin-destination pair is inversely correlated to the distance between the origin and the destination.

5. A method according to claim 2 wherein the compiled quantity for the partial route is the sum of the individual quantities assigned to each origin-destination pair for which the route from the origin to the destination comprises the partial route.

6. A method according to claim 2 wherein the length N is a predetermined distance or N intersections.

7. A method according to claim 2 wherein the individual quantity indicates the probability that the user is traveling from the corresponding origin to the corresponding destination and wherein the compiled quantity indicates the probability that user is traveling along the partial route.

8. A method according to claim 2 wherein the route corresponding to an origin-destination pair is the shortest route from the origin to the destination, the fastest route from the origin to the destination, or both.

9. A method according to claim 1 wherein the historical location information is determined by a location sensor onboard the vehicle and indicates the current location of the vehicle and at least a partial travel path of the vehicle to get to the current location.

10. A method according to claim 9 wherein the travel path comprises a path the vehicle has traveled for predetermined distance, information regarding the past n intersections the vehicle has traveled through, or both.

11. A method according to claim 1 wherein the compiled quantity assigned to at least one partial route is determined based at least in part on external information.

12. A method according to claim 11 wherein the external information is based at least in part on current traffic conditions, current road conditions, traffic simulations, or a combination thereof.

13. An apparatus comprising at least one processor, a communication interface configured for communicating via at least one network, and at least one memory storing computer program code, the at least one memory and the computer program code configured to, with the processor, cause the apparatus to at least:

receive, via the communication interface, historical location information for the vehicle, the historical location information provided by a vehicle apparatus onboard the vehicle, wherein (a) the vehicle apparatus comprises a location sensor, (b) at least a portion of the historical location information was generated by the location sensor, (c) the historical location information indicates a path traveled by the vehicle during the vehicle'"'"'s current travel, and (d) the path comprises a current location of the vehicle;

query a set of indexed partial routes based at least in part on at least a portion of the path indicated by the historical information, a partial route of the set of indexed partial routes having a compiled quantity assigned thereto;

reduce the set of indexed partial routes to a set of candidate partial routes based at least in part on the path indicated by the historical location information; and

identify a most likely partial route along which the vehicle is currently traveling from the set of candidate partial routes based at least in part on the compiled quantity associated with each of the candidate partial routes.

14. An apparatus according to claim 13 wherein to build the set of indexed partial routes the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to at least:

identify a plurality of origin-destination pairs;

assign an individual quantity to an origin-destination pair of the plurality of origin-destination pairs;

determine a set of routes, each route of the set of routes being a route from an origin to a destination of one of the plurality of origin-destination pairs;

extract a set of partial routes of a length N from the set of routes; and

assign the compiled quantity to a partial route of the set of partial routes based at least in part on the individual quantity assigned to one of the plurality of origin-destination pairs, wherein the route from the origin to the destination of the origin-destination pair comprises the partial route.

15. An apparatus according to claim 14 wherein the individual quantity assigned to an origin-destination pair is inversely correlated to the distance between the origin and the destination.

16. An apparatus according to claim 14 wherein the compiled quantity for the partial route is the sum of the individual quantities assigned to each origin-destination pair for which the route from the origin to the destination comprises the partial route.

17. An apparatus according to claim 14 wherein the individual quantity indicates the probability that the user is traveling from the corresponding origin to the corresponding destination and wherein the compiled quantity indicates the probability that user is traveling along the partial route.

18. An apparatus according to claim 14 wherein the route corresponding to an origin-destination pair is the shortest route from the origin to the destination, the fastest route from the origin to the destination, or both.

19. An apparatus according to claim 13 wherein the historical location information is determined by a location sensor onboard the vehicle and indicates the current location of the vehicle and at least a partial travel path of the vehicle to get to the current location and wherein the travel path comprises a path the vehicle has traveled for predetermined distance, information regarding the past n intersections the vehicle has traveled through, or both.

20. A computer program product comprising at least one non-transitory computer-readable storage medium having computer-executable program code instructions stored therein, the computer-executable program code instructions comprising program code instructions configured to:

receive historical location information for the vehicle, the historical location information provided by a vehicle apparatus onboard the vehicle, wherein (a) the vehicle apparatus comprises a location sensor, (b) at least a portion of the historical location information was generated by the location sensor, (c) the historical location information indicates a path traveled by the vehicle during the vehicle'"'"'s current travel, and (d) the path comprises a current location of the vehicle;

query a set of indexed partial routes based at least in part on at least a portion of the path indicated by the historical information, a partial route of the set of indexed partial routes having a compiled quantity assigned thereto;

reduce the set of indexed partial routes to a set of candidate partial routes based at least in part on the path indicated by the historical location information; and

identify a most likely partial route along which the vehicle is currently traveling from the set of candidate partial routes based at least in part on the compiled quantity associated with each of the candidate partial routes.