TIME-EFFICIENT TRAFFIC ROUTING SYSTEM

• US 20160003631A1
• Filed: 02/21/2014
• Published: 01/07/2016
• 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
• Granted Patent: US 9,752,885 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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, carried out by a processing platform of a vehicle navigation system, comprising:

identifying a plurality of candidate route segments for a vehicle;

obtaining speed metrics associated with the candidate route segments corresponding to first and second traffic states, wherein the second traffic state is a prospective state occurring after the first traffic state; and

identifying a 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 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 the speed metrics of the second traffic state relative to the first traffic state.

2. The method of claim 1, wherein the step of identifying a route plan comprises:

identifying an intermediate destination for the vehicle;

identifying 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 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 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 a schedule comprises:

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

allocating time for customer activities at the intermediate destination; and

identifying 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 a schedule comprises:

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

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

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

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

allocating 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 time for customer activities comprises allocating a time period no greater than the threshold transit time minus the sum of the first and second transit times.

6. A computer program product comprising a processor-readable storage medium having encoded therein one or more software programs configured for execution by a processing platform, the one or more software programs comprising instructions to implement the steps of the method of claim 1.

7. Apparatus for providing vehicle navigation services comprising:

a memory; and

at least one processor operably coupled to the memory and configured to;

identify a plurality of candidate route segments for a vehicle;

obtain speed metrics associated with the candidate route segments corresponding to first and second traffic states, wherein the second traffic state is a prospective state occurring after the first traffic state; and

identify a 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 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 the speed metrics of the second traffic state relative to the first traffic state.

8. The apparatus of claim 7, wherein coincident to identifying a route plan the processor is 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.

9. The apparatus of claim 8, wherein coincident to identifying a schedule the processor is 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.

10. The apparatus of claim 8, wherein coincident to identifying a schedule the processor is 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.