Time-efficient traffic routing system

• US 9,752,885 B2
• Filed: 02/21/2014
• Issued: 09/05/2017
• Est. Priority Date: 03/26/2013
• Status: Active Grant

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Sund, Matthias
• Primary Examiner(s): Badii, Behrang
• Assistant Examiner(s): TESTARDI, DAVID A
• Application Number:
  US14/767,043
• Publication Number:
  US 20160003631A1
• Time in Patent Office: 1,292 Days
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• 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

Abstract

An improved vehicle navigation system and method provides a route plan or alternative route based at least in part on evolved state information (e.g., a second traffic state, occurring some time after a first traffic state) from which time-efficiencies may be realized relative to navigation in a previous traffic state. Optionally, the route plan may identify an intermediate destination (e.g., such as a refueling or recharging station) and the schedule may allocate time for customer activities at the intermediate destination.

Claims

1. A method, comprising the steps of:

receiving, at a processing platform of a vehicle navigation system, a request for a route plan from a vehicle operably connected to the vehicle navigation system, wherein the processing platform has a processor and a memory;

identifying, at the processing platform, a plurality of candidate route segments for the vehicle;

obtaining, at the processing platform, speed metrics associated with the plurality of candidate route segments corresponding to a first traffic state and a second traffic state, wherein the speed metrics include speed limits and projected transit times associated with the plurality of candidate route segments which are stored in a database, and wherein the second traffic state is a prospective state occurring after the first traffic state;

identifying, at the processing platform, the route plan for the vehicle, the route plan defining a route from a first location to a second location comprising one or more selected segments of the plurality of candidate route segments, the route plan further defining a schedule for navigating the selected segments, wherein the schedule provides for navigating at least a portion of the selected segments in the second traffic state based on time efficiencies realized from the speed metrics of the second traffic state relative to the first traffic state;

identifying, at the processing platform, a route segment that identifies a recharging station for the vehicle within a navigable range of the vehicle;

allocating, at the processing platform, time in the route plan for recharging the vehicle at the recharging station; and

communicating, at the processing platform, the route plan to the vehicle.

2. The method of claim 1, wherein the step of identifying, at the processing platform, the route plan further comprises:

identifying, at the processing platform, an intermediate destination for the vehicle;

identifying, at the processing platform, one or more of the candidate route segments, defining a first portion of the route plan, linking the first location to the intermediate destination;

identifying, at the processing platform, one or more of the candidate route segments, defining a second portion of the route plan, linking the intermediate destination to the second location; and

identifying, at the processing platform, a schedule for navigating the first and second portions, wherein the schedule provides for navigating at least the second portion in the second traffic state.

3. The method of claim 2, wherein the step of identifying, at the processing platform, the schedule further comprises:

identifying, at the processing platform, a first transit time for navigating the first portion of the route plan in the first traffic state;

allocating, at the processing platform, time for customer activities at the intermediate destination; and

identifying, at the processing platform, a second transit time for navigating the second portion of the route plan in the second traffic state.

4. The method of claim 2, wherein the step of identifying, at the processing platform, the schedule further comprises:

identifying, at the processing platform, a threshold transit time for navigation from the first location to the second location;

identifying, at the processing platform, a first transit time for navigating the first portion of the route plan in the first traffic state;

identifying, at the processing platform, a second transit time for navigating the second portion of the route plan in the second traffic state;

calculating, at the processing platform, a sum of the first and second transit times; and

allocating, at the processing platform, time for customer activities at the intermediate destination, if the sum of the first and second transit times does not exceed the threshold transit time.

5. The method of claim 4, wherein the step of allocating, at the processing platform, the time for customer activities further comprises allocating, at the processing platform, a time period no greater than the threshold transit time minus the sum of the first and second transit times.

6. The method of claim 1, wherein the speed metrics further comprise an average transit speed.

7. The method of claim 1, wherein the navigable range is determined by a battery charge status of the vehicle.

8. The method of claim 1, wherein the second traffic state is less congested than the first traffic state.

9. An apparatus for a vehicle navigation system comprising:

one or more processing devices; and

a non-transitory computer readable storage device with computer executable instructions stored thereon that, when executed by the one or more processing devices, causes the one or more processing devices to;

receive a request for a route plan from a vehicle operably connected to the vehicle navigation system;

identify a plurality of candidate route segments for the vehicle;

obtain speed metrics associated with the plurality of candidate route segments corresponding to a first traffic state and a second traffic state, wherein the speed metrics are stored and include speed limits and projected transit times associated with the plurality of candidate route segments, and wherein the second traffic state is a prospective state occurring after the first traffic state;

identify the route plan for the vehicle, the route plan defining a route from a first location to a second location comprising one or more selected segments of the plurality of candidate route segments, the route plan further defining a schedule for navigating the selected segments, wherein the schedule provides for navigating at least a portion of the selected segments in the second traffic state based on time efficiencies realized from the speed metrics of the second traffic state relative to the first traffic state;

identify a route segment that identifies a recharging station for the vehicle within a navigable range of the vehicle;

allocate time in the route plan for recharging the vehicle at the recharging station; and

communicate the route plan to the vehicle.

10. The apparatus of claim 9, wherein coincident to identifying the route plan the one or more processing devices are configured to:

identify an intermediate destination for the vehicle;

identify one or more of the candidate route segments, defining a first portion of the route plan, linking the first location to the intermediate destination;

identify one or more of the candidate route segments, defining a second portion of the route plan, linking the intermediate destination to the second location; and

identify a schedule for navigating the first and second portions, wherein the schedule provides for navigating at least the second portion in the second traffic state.

11. The apparatus of claim 10, wherein coincident to identifying the schedule the one or more processing devices are configured to:

identify a first transit time for navigating the first portion of the route plan in the first traffic state;

allocate time for customer activities at the intermediate destination; and

identify a second transit time for navigating the second portion of the route plan in the second traffic state.

12. The apparatus of claim 10, wherein coincident to identifying the schedule the one or more processing devices are configured to:

identify a threshold transit time for navigation from the first location to the second location;

identify a first transit time for navigating the first portion of the route plan in the first traffic state;

identify a second transit time for navigating the second portion of the route plan in the second traffic state;

calculate a sum of the first and second transit times; and

allocate time for customer activities at the intermediate destination, if the sum of the first and second transit times does not exceed the threshold transit time.