Method of planning a route to a destination

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.

1 . A method of planning a route to a destination, comprising the steps: 
 (a) using a map database that defines roads in terms of route segments and includes a fixed, pre-defined, time-independent cost associated with each different route segment in the map database;    (b) using software that enables a route to be planned to a destination and that calculates an estimated cost of reaching that destination using one or more route segments;    wherein using the software involves planning a route by automatically using a combination of (i) time-dependent costs for one or more of the route segments in the route, such that a cost is applied to traversing a particular route segment that is appropriate for the specific time when it is planned to be traversed and (ii) the fixed, pre-defined, time-independent costs, for those route segments in the route that are not defined by the time-dependent costs.    
     
     
         2 . The method of  claim 1  in which the time-dependent cost associated with a particular route segment relates to vehicle speed or route segment transit times that have been measured or inferred and are not fixed and pre-defined.  
     
     
         3 . The method of  claim 1  in which the fixed, pre-defined, 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.  
     
     
         4 . The method of  claim 3  in which the time-independent costs are used in combination with the time dependent costs, for those route segments that are defined by both time-independent and time-dependent costs.  
     
     
         5 . The method of  claim 1  in which the cost associated with a particular route is the estimated time taken to reach the destination.  
     
     
         6 . The method of  claim 1  in which the cost associated with a particular route is the fuel usage associated with that route.  
     
     
         7 . The method of  claim 1  in which the cost associated with a particular route is the chargeable financial cost associated with that route.  
     
     
         8 . The method of  claim 1  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.  
     
     
         9 . The method of  claim 8  in which the menu list includes one or more of the following items: transit time for the route; financial cost for the route, fuel useage over the route; stationary traffic.  
     
     
         10 . The method of  claim 1  in which the software calculates the cost of the route as part of a cost minimisation algorithm.  
     
     
         11 . The method of  claim 1  in which an estimated cost of reaching a destination for a particular driver of a vehicle is a function of a driving profile associated with that driver.  
     
     
         12 . The method of  claim 11  in which measuring actual vehicle traffic flows or movement data is derived from GPS tracks stored by a GPS based navigation device in a vehicle travelling along the route segments.  
     
     
         13 . The method of  claim 12  in which GPS tracks are sent over a cellular wireless network directly by the device to a traffic monitoring system.  
     
     
         14 . The method of  claim 11  in which the GPS tracks are sent directly by the device to a traffic monitoring system.  
     
     
         15 . The method of  claim 12  in which the GPS tracks are sent by mobile telephone connected to the device over a piconet or other form of connection.  
     
     
         16 . The method of  claim 12  in which the GPS tracks are sent by the device when it is docked with a PC to a traffic monitoring system.  
     
     
         17 . The method of  claim 11  in which measuring actual vehicle traffic flows or movement is achieved by measuring the location of mobile telephones.  
     
     
         18 . The method of  claim 17  in which the location of mobile telephones is obtained by passively monitoring signalling traffic from the mobile telephones to basestations.  
     
     
         19 . The method of  claim 11  in which measuring actual vehicle traffic flows or movement is achieved using loop sensors in roads.  
     
     
         20 . The method of  claim 11  in which measuring actual vehicle traffic flows or movement is achieved using camera-based systems.  
     
     
         21 . The method of  claim 11  in which measuring actual vehicle traffic flows or movement is achieved using vehicles equipped with radio beacons.  
     
     
         22 . The method of  claim 11  in which the time-dependent costs are dynamically updateable.  
     
     
         23 . The method of  claim 22  in which the time-dependent costs are dynamically updateable in real-time.  
     
     
         24 . The method of  claim 1  in which the time-dependent costs associated with a route segment are a function of the time of day or night.  
     
     
         25 . The method of  claim 1  in which the time-dependent costs associated with a route segment are a function of the days of the week.  
     
     
         26 . The method of  claim 1  in which the time-dependent costs associated with a route segment are a function of public holidays.  
     
     
         27 . The method of  claim 1  in which the time-dependent costs associated with a route segment are a function of school holidays.  
     
     
         28 . The method of  claim 1  in which the time-dependent costs associated with a route segment are a function of any event that will likely impact on route segment costs.  
     
     
         29 . The method of  claim 1  in which the time-dependent costs associated with a route segment are a function of any future situation about which it is possible to infer a likely impact on route segment cost.  
     
     
         30 . The method of  claim 1  in which the destination includes two or more destinations.  
     
     
         31 . The method of  claim 1  in which the method is performed by a GPS based navigation device.  
     
     
         32 . A navigation device programmed with: 
 (a) a map database that defines roads in terms of route segments and includes a fixed, pre-defined time-independent cost associated with each different route segment in the map database; and    (b) software that enables a route to be planned to a destination and that calculates an estimated cost of reaching that destination using one or more route segments;    wherein the device can plan a route by automatically using a combination of (i) time-dependent costs for one or more of the route segments in the route, such that a cost is applied to traversing a particular route segment that is appropriate for the specific time when it is planned to be traversed and (ii) the fixed, pre-defined, time-independent costs, for those route segments in the route that are not defined by the time-dependent costs.    
     
     
         33 . The device of  claim 32  in which the device calculates the lowest cost route to the destination.  
     
     
         34 . The device of  claim 32  in which the device plans fastest route.  
     
     
         35 . The device of  claim 32  in which the device plans a route with the lowest fuel usage.  
     
     
         36 . The device of  claim 32  in which the device plans a route with the lowest financial charges.  
     
     
         37 . The device of  claim 32  in which time-dependent costs are pushed to the device.  
     
     
         38 . The device of  claim 32  in which time-dependent costs are sent to the device on request by the device.  
     
     
         39 . The device of  claim 37  in which the time-dependent costs received by the device are restricted to a class of road types.  
     
     
         40 . The device of  claim 32  in which the device includes time dependent costs on the same memory that includes the map database.  
     
     
         41 . The device of  claim 32  in which the device accesses the time-dependent costs, which are held on a remote server.  
     
     
         42 . The device of  claim 41  in which the device can be docked with an internet connected computer and receives the time-dependent costs from the remote server via the internet connected computer.  
     
     
         43 . The device of  claim 41  in which the remote server sends to the device a cost associated with moving from a start to the destination.  
     
     
         44 . The device of  claim 41  in which the server receives a real-time traffic feed that enables it to supplement the time-dependent costs with recent data.  
     
     
         45 . The device of  claim 41  in which the device receives real-time or recent traffic data or congestion information from the server and automatically uses that data or information to re-calculate the optimal route.  
     
     
         46 . The device of  claim 41  in which (a) both the device and the server each separately use the time-dependent costs; 
 (b) the device informs the server of the lowest costs route that it has calculated; and    (c) the server sends a notification to the device if the lowest cost route it has calculated is different from the route that the device has calculated.    
     
     
         47 . The device of  claim 46  in which the server sends a notification to the device that defines solely the difference between the routes.  
     
     
         48 . The device of  claim 41  in which: 
 (a) both the device and the server each separately use the time-dependent costs;    (b) the device identifies road segments for which recent data is valuable and requests that recent data from the server.    
     
     
         49 . The device of  claim 32  in which the device can suggest an optimal start time for a journey.  
     
     
         50 . The device of  claim 32 , in which the device is a GPS based navigation device.  
     
     
         51 . The device of  claim 32 , in which the device is a mobile telephone with location finding system.  
     
     
         52 . The device of  claim 32  in which the location finding system is GPS.  
     
     
         53 . The device of  claim 32 , in which the device is permanently embedded into a motor vehicle.  
     
     
         54 . A traffic monitoring system that measures traffic speed or transit time data as a function of time and generates a historic database of time-dependent traffic speeds or transit times for segments of roads; and shares at least some of that database or its contents to enable the method of  claim 1  to be performed.  
     
     
         55 . A digital map of a region, the map including data defining road segments, together with data defining time-dependent costs associated with at least some of the road segments, adapted to enable the method of  claim 1  to be performed when used by route planning software.  
     
     
         56 . A motor vehicle including an embedded navigation system operable to plan a route using the method of  claim 1.