METHOD OF PLANNING A ROUTE TO A DESTINATION

• US 20140163849A1
• Filed: 12/20/2013
• Published: 06/12/2014
• Est. Priority Date: 10/10/2005
• Status: Active Grant

• Current Assignee: TomTom Navigation B.V (TomTom NV)
• Original Assignee: TomTom International BV (TomTom NV)
• Inventors: Adam, Thomas Bruce Watson, Atkinson, Ian Malcolm, Dixon, Michael Joseph
• Granted Patent: US 10,724,870 B2
• Time in Patent Office: Days
• US Class Current: 701/118
• 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: G08G 1/00 Traffic control systems for road vehicles arrangement of road signs or traffic signals E01F9/00 ; automatic vehicle control B62D
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data
• CPC Class Codes: G08G 1/096883 where input information is obtained using a mobile device, e.g. a mobile phone, a PDA
• CPC Class Codes: G08G 1/0969 having a display in the form of a map

Abstract

The present invention combines the geographical coverage possible with fixed, pre-defined route segment costs (e.g. the legal speed limit) with, wherever possible, richer time dependent costs. A user of, for example, a portable navigation device, can therefore continue route planning as before to virtually any destination in a country covered by the stored map database, but wherever possible, can also use traffic data with time-dependent costs, so that the effect of congestion with any time predictability can be accurately taken into account as an automatic, background process. It leaves the user to simply carry on driving, following the guidance offered by the navigation device, without needing to be concerned about congestion that exists now, and whether it will impact his journey.

Claims

1-56. -56. (canceled)

57. A routing system, comprising memory storing a map database that defines roads in terms of route segments, the map database including:

a fixed, predefined time-independent cost associated with each different route segment in the map database; and

a historical time-dependent cost, for each of a plurality of time windows, associated with at least some of the route segments in the map database, the cost relating to an average vehicle speed or transit time along the route segment measured or inferred from historical vehicle traffic flow or movement obtained by a traffic monitoring system,

the routing system being arranged to receive updated time-dependent costs for one or more route segments for at least one of a current and future time based on an identification of currently congested route segments by the traffic monitoring system, and

the routing system being programmed with software comprising a routing algorithm that enables a route to be planned to a destination at a specific time using one or more route segments and that calculates an estimated cost of reaching that destination by automatically using;

(i) the time-dependent cost for a route segment if available, the time-dependent cost being a received updated cost for the specific time when the route segment is planned to be traversed or, if an updated cost has not been received, the historical cost for the appropriate time window;

or (ii) the fixed, predefined time-independent cost for a route segment if a time-dependent cost for the route segment is not available in the map database.

58. The routing system of claim 57 in which the fixed, predefined time-independent cost associated with a particular route segment has not been measured or inferred from actual vehicle traffic flow or movement but instead is a function of:

(i) the type of road associated with that route segment;

or (ii) the speed limit applicable to that route segment.

59. The routing system of claim 57 in which the cost associated with a particular route is at least one of:

an estimated time taken to reach the destination;

a fuel usage associated with the route; and

a chargeable financial cost associated with the route.

60. The routing system of claim 57 in which the cost associated with a particular route is of a type that an end-user can select from a menu list displayed on a computing device.

61. The routing system of claim 57 in which the software calculates the cost of the route as part of a cost minimisation algorithm.

62. The routing system of claim 57 in which the historical time-dependent costs are a function of at least one of:

a time of day or night;

the days of the week;

public holidays;

school holidays; and

any event that will likely impact on route segment costs.

63. The routing system of claim 57 in which the routing system is one of:

a GPS based portable navigation device;

a mobile telephone with a location finding system; and

a device permanently embedded into a motor vehicle.

65. A system comprising:

a routing system as claimed in claim 57; and

a traffic monitoring system as claimed in claim 64.

64. A traffic monitoring system comprising a processing module arranged to process data representative of vehicles moving along roads in a designated geographical area, the roads being defined in a map database in terms of route segments, to measure traffic speed or transit time data as a function of time, wherein the processing module is arranged to:

generate a database of historical time-dependent traffic speeds or transit times for at least some route segments in the map database, the data associated with a route segment comprising an average traffic speed or transit time along the route segment for each of a plurality of time windows;

identify currently congested route segments on which the current traffic speed or transit time is less than expected; and

predict a traffic speed or transit time for a future time for at least one currently congested route segment based on a comparison of recently observed traffic speeds or transits times for the at least one segment with the historical average traffic speed or transit time for the appropriate time window.

66. A method of planning a route to a destination, comprising:

using a map database that defines roads in terms of route segments, the map database including;

a fixed, predefined time-independent cost associated with each different route segment in the map database; and

a historical time-dependent cost, for each of a plurality of time windows, associated with at least some of the route segments in the map database, the cost relating to an average vehicle speed or transit time along the route segment measured or inferred from historical vehicle traffic flow or movement obtained by a traffic monitoring system;

receiving updated time-dependent costs for one or more route segments for at least one of a current and future time based on an identification of currently congested route segments by the traffic monitoring system; and

using software comprising a routing algorithm that enables a route to be planned to a destination at a specific time using one or more route segments and that calculates an estimated cost of reaching that destination by automatically using;

(i) the time-dependent cost for a route segment if available, the time-dependent cost being a received updated cost for the specific time when the route segment is planned to be traversed or, if an updated cost has not been received, the historical cost for the appropriate time window;

or (ii) the fixed, predefined time-independent cost for a route segment if a time-dependent cost for the route segment is not available in the map database.

67. The method of claim 66 in which the fixed, predefined time-independent cost associated with a particular route segment has not been measured or inferred from actual vehicle traffic flow or movement but instead is a function of:

(i) the type of road associated with that route segment;

or (ii) the speed limit applicable to that route segment.

68. The method of claim 66 in which the cost associated with a particular route is at least one of:

an estimated time taken to reach the destination;

a fuel usage associated with the route; and

a chargeable financial cost associated with the route.

69. The method of claim 66 in which the cost associated with a particular route is of a type that an end-user can select from a menu list displayed on a computing device.

70. The method of claim 66 in which the software calculates the cost of the route as part of a cost minimisation algorithm.

72. A non-transitory computer-readable medium storing computer software that, when executed on a computer, causes the computer to perform the method of claim 66.

71. A method in which data representative of vehicles moving along roads in a designated geographical area, the roads being defined in a map database in terms of route segments, is processed by a processing module of a traffic monitoring system to measure traffic speed or transit time data as a function of time, the method comprising:

generating a database of historical time-dependent traffic speeds or transit times for at least some route segments in the map database, the data associated with a route segment comprising an average traffic speed or transit time along the route segment for each of a plurality of time windows;

identifying currently congested route segments on which the current traffic speed or transit time is less than expected; and

predicting a traffic speed or transit time for a future time for at least one currently congested route segment based on a comparison of recently observed traffic speeds or transits times for the at least one segment with the historical average traffic speed or transit time for the appropriate time window.

73. A non-transitory computer-readable medium storing computer software that, when executed on a computer, causes the computer to perform the method of claim 71.