Optimal route calculation based upon cohort analysis

• US 7,356,407 B2
• Filed: 10/06/2005
• Issued: 04/08/2008
• Est. Priority Date: 10/06/2005
• Status: Active Grant

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: GM Global Technology Operations Incorporated (General Motors Company)
• Inventors: Roesser, Robert P., Johnson, Richard A., Dai, Xiaowen
• Primary Examiner(s): Broadhead; Brian J.
• Application Number:
  US11/244,788
• Publication Number:
  US 20070083326A1
• Time in Patent Office: 915 Days
• Field of Search: 701/208, 701/210, 340/995.19, 340/995.22
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• 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

The invention includes cohort analysis as an element of an in-vehicle navigation system. As an operator makes trips from an origin to a destination, the navigation system records various route segments chosen. These choices are compared to route segments comprising a minimal time route calculated for the trip. Segments not part of the prescribed route are collected and periodically sent along with the origin and destination to a centralized server, wherein they are stored in a database. The central server also has an extensive map database that lists many attributes for each segment not generally included in an in-vehicle database. The attributes include variables pertaining to traffic flow, e.g. speed, number of lanes, lane width; topology, e.g. possible turns at endpoints; geometry, e.g. horizontal shape, vertical curvature, and super-elevation; usage, e.g. freeway, arterial, local, residential, business; and topography, e.g. buildings, trees, open-space, facilities, and stores.

Claims

1. Method for identifying a preferred travel route for an operator of a vehicle, comprising:

providing a navigation system having a route optimization function incorporating a cohort attribute model;

selecting an origin point and a destination point; and

,

determining a travel route based upon estimated travel time, travel distance and cohort attribute information;

wherein providing a navigation system having a route optimization function incorporating a cohort attribute model comprises;

A) determining information for a plurality of vehicle operators, including;

1) creating an operator profile for each operator based upon attributes of operator-selected route segments, comprising;

a) comparing operator-selected route segments to optimal route segments for a plurality of trips;

b) capturing operator-selected route segments divergent from the optimal route segments; and

,

c) evaluating the operator-selected route segments divergent from the optimal route segments based upon attributes of the operator-selected route segments; and

,

2) capturing a plurality of operator profiles, each based upon similarity of attributes of divergent operator-selected route segments;

B) determining a plurality of categories of operators, each category defined by attributes of divergent operator-selected route segments; and

,

C) assigning each operator to one of the plurality of categories, based upon the operator profile.

2. The method of claim 1, further comprising:

D) generating navigation instructions.

3. The method of claim 2, wherein determining a travel route based upon estimated travel time, travel distance and cohort attribute information further comprises:

determining a travel route based upon operator-selectable weightings of the estimated travel time, travel distance and cohort attribute information.

4. The method of claim 1, wherein comparing operator-selected route segments to optimal route segments for each trip comprises comparing operator-selected route segments to a corresponding minimal-time route segment.

5. The method of claim 1, wherein comparing operator-selected route segments to optimal route segments for each trip comprises comparing operator-selected route segments to a corresponding minimal-distance route segment.

6. The method of claim 1, wherein the attributes comprise at least one of:

traffic flow, route topology, road geometry, road type, and topography.

7. Article of manufacture comprising:

a storage medium having a computer program encoded therein for effecting a method to identify a preferred travel route for an operator of a vehicle, the vehicle having an in-vehicle system operable to access a navigation system, and having a user interface operable to input an operator-selectable origin point and a destination point;

said computer program comprising;

code for the navigation system comprising a route optimization function incorporating a cohort attribute model;

code to determine a travel route based upon estimated travel time, travel distance, and cohort attribute information, the cohort attribute information communicable to the storage medium from a remote navigation system; and

,

code to generate navigation instructions;

wherein the remote navigation system comprises;

a remote storage medium having a computer program encoded therein for effecting a method to determine the cohort attribute information;

said computer program encoded in the remote storage medium comprising;

code to capture a plurality of operator profiles, each operator profile comprising a plurality of attributes of divergent operator-selected route segments;

code to create a plurality of clusters of operator profiles based upon similarity of the plurality of attributes of divergent operator-selected route segments;

code to determine a plurality of categories of operators based upon the clusters of operator profiles; and

,

code to assign each operator to one of the plurality of categories of operators based upon an operator profile.

8. The article of manufacture of claim 7, wherein the code to determine a travel route based upon estimated travel time, travel distance, and cohort attribute information farther comprises:

code to determine the travel route modifiable by operator-selectable weightings of the estimated travel time, travel distance, and cohort attribute information.

9. Article of manufacture, comprising:

a remote storage medium having a computer program encoded therein for effecting a method to determine cohort attribute information for a navigation system;

said computer program comprising;

code to capture a plurality of operator profiles, each operator profile comprising a plurality of attributes;

code to create a plurality of clusters of operator profiles based upon similarity of attributes and similarity of divergent operator-selected route segments;

code to determine a plurality of categories of operators based upon the clusters of operator profiles, each category defined by attributes of divergent operator-selected route segments; and

,

code to assign each operator to one of the plurality of categories of operators based upon an operator profile.