Patent Description:
Navigation systems are available that provide users with various navigation-related functions. For example, some navigation systems are able to determine an optimum route to travel by roads between locations in a geographic region. Using input from the user, and optionally from equipment that can determine the user's physical location (such as a GPS system), a navigation system can examine various routes between two locations to determine an optimum route to travel from a starting location to a destination location in a geographic region.

To calculate an optimal route, the navigation system uses a routing algorithm. A routing algorithm searches for the route having the minimum cost. Here, cost refers to a user's preference for a route. For example, the user may desire the shortest route, the fastest route, or the most energy efficient route for traveling from an origin to a destination.

The routing algorithm uses data in a geographic database to calculate the route. The geographic database contains data that represents some of the physical geographic features in a geographic region. For example, the geographic database represents a road network using road segments and nodes. If the routing algorithm is calculating a minimum time route, the routing algorithm may retrieve road segment length and speed limit data from the geographic database. The cost per segment is the travel time, which is calculated by dividing the segment length by the speed limit associated with the segment.

To improve the minimum time route calculation, the routing algorithm may use traffic data. Some navigation systems have a database of historical traffic data, such as NAVTEQ's Traffic Patterns™ product. The historic traffic database includes data representing typical traffic speeds on roads organized by day of the week and time of the day. Route calculation using a historic traffic database is likely to be more accurate than calculating a route using speed limits or speed ranges to estimate the speed of traffic.

Route calculation using real-time traffic data is likely to be more accurate than calculating a route using a historic traffic database. In some areas, systems broadcast data messages that contain up-to-the-minute reports of traffic and road condition information. These systems broadcast the traffic data over traffic message channels on a continuous, periodic, or frequently occurring basis. Traffic message receivers decode the data and provide up-to-the-minute reports of traffic and road conditions.

One protocol for broadcasting traffic messages is the Traffic Message Channel (TMC), which is used in Europe, North America, and elsewhere. In Europe TMC is broadcast as part of the Radio Data System (RDS) and North America TMC is broadcast as part of the Radio Broadcast Data System (RBDS). Essentially RDS and RBDS are identical. Another traffic broadcast system, named Vehicle Information and Communication System ("VICS') Center, is used in Japan. Traffic and road condition information can also be transmitted using other protocols (such as Traffic Experts Protocol Group (TPEG)) and on other broadcast bearers including Digital Audio Broadcasting ("DAB"), Digital Multimedia Broadcasting ("DMB"), Hybrid Digital Radio ("HD Radio"), Digital Radio Mondiale (DRM), satellite radio, and other protocols and radio systems, such as MSN-Direct.

Some systems may transmit real-time traffic data directly to an end-user device. For example, the system may use non-broadcast transmissions, such as General Packet Radio Service (GPRS), Time Division Multiplexing (TDM), or other direct wireless transmission.

<CIT> relates to a traffic information system for predicting travel times which utilizes Internet based collecting and disseminating of information.

These as well as other aspects and advantages will become apparent to those of ordinary skill in the art by reading the following detailed description, with reference where appropriate to the accompanying drawings.

Presently preferred embodiments are described below in conjunction with the appended drawing figures, wherein like reference numerals refer to like elements in the various figures, and wherein:.

<FIG> is diagram illustrating a geographic region <NUM>. The region <NUM> may be a metropolitan area, such as the New York metropolitan area, the Los Angeles metropolitan area, or any other metropolitan area. Alternatively, the region <NUM> may be a state, province, or country, such as California, Illinois, France, England, or Germany. Alternatively, the region <NUM> can be a combination of one or more metropolitan areas, states, countries, and so on. Located in the region <NUM> is a road network <NUM>.

A traffic broadcast system <NUM> is also located in the region <NUM>. The traffic broadcast system <NUM> transmits data <NUM> regarding traffic and road conditions in the region <NUM>, sometimes referred to as traffic messages. The traffic broadcast system <NUM> may be operated by a governmental organization or may be privately operated. The traffic broadcasting system <NUM> may broadcast messages that conform to a traffic message channel protocol, such as TMC, carried over RDS, RBDS, VICS, DAB, DMB, DRM, HD Radio, and so on. Alternatively, the traffic broadcasting system <NUM> may use non-broadcast transmissions using, for example, GPRS and TDM.

Vehicles 11A, 11B, 11C, 11D. 11n travel on the road network <NUM> in the region <NUM>. The vehicles <NUM> may include a variety of cars, trucks, and motorcycles. Some or all of the vehicles <NUM> include suitable equipment that enables them to receive the data <NUM> transmitted by the traffic broadcast system <NUM>.

The data <NUM> transmitted from the traffic broadcast system <NUM> may also be received and used in systems <NUM> that are not installed in vehicles (referred to herein as "non-vehicle systems"). These non-vehicle systems <NUM> may include workstations, personal computers, tablet computers, televisions, radio receivers, telephones, and so on. The non-vehicle systems <NUM> may receive the data <NUM> in the same manner as the vehicles, for example, by broadcast over a traffic message channel. Alternatively, the non-vehicle systems <NUM> may receive the data <NUM> by other means, such as over telephone lines, over the Internet, via cable, and so on. The systems in the vehicles <NUM> and the non-vehicle systems <NUM> that receive the data <NUM> may include various different computing platforms.

<FIG> shows the components of the traffic broadcast system <NUM> and one of the vehicles <NUM> shown in <FIG>. The traffic broadcast system <NUM> provides for the collection of data relating to traffic and road conditions, the analysis and organization of these collected data, the formatting of the analyzed data into traffic messages, and the transmission of these traffic messages to the vehicles <NUM> in the region <NUM> on a regular and continuing basis.

The traffic broadcast system <NUM> uses various means <NUM> to obtain information about traffic and road conditions. These means <NUM> may include sensors located in or near the roads in the road network <NUM>, aerial sensors, sensors in vehicles <NUM>, radar, as well as other technologies. A traffic operator located at the traffic broadcast system <NUM> may also obtain information about traffic and road conditions by communicating with surveillance aircraft or vehicles, local departments of transportation, traffic management centers, other agencies, and individuals; and listening to scanners on police, fire, and emergency frequencies.

The traffic broadcast system <NUM> includes equipment and programming <NUM>(<NUM>) for collecting the data relating to traffic and road conditions in the region <NUM> from the various sensors <NUM>. This equipment and programming <NUM>(<NUM>) includes, for example, various communications links (including wireless links), receivers, data storage devices, programming that saves the collected data, programming that logs data collection times and locations, and so on.

The traffic broadcast system <NUM> also includes equipment and programming <NUM>(<NUM>) for assembling, organizing, analyzing, and formatting the collected traffic and road condition data. This programming and equipment <NUM>(<NUM>) includes storage devices, programming that statistically analyzes the collected data for potential errors, programming that organizes the collected data, and programming that uses the data to prepare messages in one or more appropriate predetermined formats.

The traffic broadcast system <NUM> also includes suitable equipment and programming <NUM>(<NUM>) for transmitting the data <NUM>. The data <NUM> can be the traffic and road condition data collected and organized by the traffic broadcast system <NUM> and/or additional data. The equipment and programming <NUM>(<NUM>) includes interfaces to transmitters, programming that communicates formatted messages at regular intervals to the transmitters, and so on.

The traffic broadcast system <NUM> also includes transmission equipment <NUM>(<NUM>). This equipment <NUM>(<NUM>) may comprise one or more FM, AM, DAB, DRM or other transmitters, including antennas, or other wireless transmitters. This equipment <NUM>(<NUM>) provides for transmitting the messages as data <NUM> throughout the region <NUM>. The transmitting equipment <NUM>(<NUM>) may be part of the traffic broadcast system <NUM>, or alternatively, the traffic broadcast system <NUM> may use equipment from other types of systems, such as cellular systems, FM radio stations, and so on, to transmit the data <NUM> to the vehicles <NUM> in the region <NUM>. The transmitting of data <NUM> includes any form of transmission, including direct wireless transmission.

<FIG> illustrates the data <NUM> for an example traffic message. The traffic message can include various kinds of data <NUM>. In the example shown in <FIG>, the data <NUM> includes the following data components: an event description <NUM>(<NUM>), a location <NUM>(<NUM>), a direction <NUM>(<NUM>), an extent <NUM>(<NUM>), a duration <NUM>(<NUM>), advice <NUM>(<NUM>), traffic pattern code <NUM>(<NUM>), and period of validity <NUM>(<NUM>).

The data <NUM> for the traffic message may also include components that provide other information <NUM>(n).

The event description component <NUM>(<NUM>) includes data that describe a type of traffic problem <NUM>(<NUM>)(<NUM>) along with data that describe a level of severity <NUM>(<NUM>)(<NUM>) of the traffic problem. The location component <NUM>(<NUM>) includes a reference number that identifies the location of the traffic problem. The direction component <NUM>(<NUM>) includes data that indicate the direction of traffic affected. The extent component <NUM>(<NUM>) includes data that identify a length of a traffic congestion queue with respect to the location <NUM>(<NUM>). The extent component <NUM>(<NUM>) implicitly defines another (e.g., a secondary location) straddling the traffic condition in terms of the number of location references in between. The advice component <NUM>(<NUM>) provides a recommendation for a diversion of route.

The traffic pattern code <NUM>(<NUM>) includes an identifier that a receiving device can use to retrieve a traffic pattern from memory. The period of validity <NUM>(<NUM>) identifies the period of time that the receiving device should use the traffic pattern identified by the code <NUM>(<NUM>) instead of a traffic pattern selected by day of week and time of day.

The traffic pattern code <NUM>(<NUM>) and the period of validity <NUM>(<NUM>) may also be transmitted separately from a traffic message. For example, the traffic pattern code <NUM>(<NUM>) and the period of validity <NUM>(<NUM>) may be transmitted alongside the traffic message to end-users of a traffic message receiver. By "alongside" it is meant that the traffic pattern code <NUM>(<NUM>) and the period of validity <NUM>(<NUM>) use a different protocol than the traffic message, but co-exist within the same transmission.

In one example, the protocol used for the traffic message is the RDS-TMC protocol, which is used on both RDS and RBDS systems, and the protocol used for the traffic pattern code <NUM>(<NUM>) and the period of validity <NUM>(<NUM>) is a proprietary protocol. The proprietary protocol is recognized by a traffic message receiver by registering the protocol as an Open Data Application ("ODA") as described in the RDS/RBDS standard. Upon registration, an application identifier ("AID") is assigned to the protocol. The traffic message receiver recognizes the application identifier without modifying the receiver.

Moreover, the traffic pattern code <NUM>(<NUM>) and the period of validity <NUM>(<NUM>) may be transmitted directly to a device, such as a navigation system. For example, the traffic pattern code <NUM>(<NUM>) and the period of validity <NUM>(<NUM>) may be transmitted to a navigation system using GPRS or TDM. Other wireless transmission protocols may be used as well. In this example, other information, such as location <NUM>(<NUM>), direction <NUM>(<NUM>), and extent <NUM>(<NUM>), may be transmitted directly to the navigation system with the traffic pattern code <NUM>(<NUM>) and the period of validity <NUM>(<NUM>).

<FIG> also depicts the components of one of the vehicles <NUM> shown in <FIG>. The vehicle <NUM> may be a car, a truck, a motorcycle, or any other type of vehicle in the region <NUM>. A navigation system <NUM> is installed in the vehicle <NUM>. The navigation system <NUM> is a combination of hardware and software components. In one embodiment, the navigation system <NUM> includes a processor <NUM>, a drive <NUM> connected to the processor <NUM>, and a non-volatile memory storage device <NUM> for storing a navigation application software program <NUM> and possibly other information. The processor <NUM> may be any type of processor suitable for navigation systems.

The navigation system <NUM> may also include a positioning system <NUM>. The positioning system <NUM> may utilize GPS-type technology, a dead reckoning-type system, or combinations of these or other positioning systems. The positioning system <NUM> may include suitable sensing devices <NUM> that measure the traveling distance, speed, direction, and so on of the vehicle <NUM>. The positioning system <NUM> may also include appropriate technology to obtain a GPS signal, in a manner which is known in the art. The positioning system <NUM> outputs a signal to the processor <NUM>. The signal from the positioning system <NUM> may be used by the navigation application software <NUM> that is run on the processor <NUM> to determine the location, direction, speed, and so on of the vehicle <NUM>.

The vehicle <NUM> includes a receiver <NUM>. The receiver <NUM> receives the data <NUM> from the traffic broadcast system <NUM>. For example, the receiver <NUM> may be an FM receiver tuned to the appropriate frequency at which the traffic broadcast system <NUM> is using to broadcast the data <NUM>. As another example, when the data <NUM> are sent by direct wireless transmission, such as cellular wireless transmission, the receiver <NUM> in the vehicle <NUM> may be similar or identical to a cellular telephone. The receiver <NUM> provides an output to the processor <NUM> so that appropriate programming in the navigation system <NUM> can utilize the data <NUM> transmitted by the traffic broadcast system <NUM> or another type of broadcast system when performing navigation functions.

<FIG> is a simplified block diagram of the receiver <NUM> that may be used in the navigation system <NUM> depicted in <FIG>. In this example, the receiver <NUM> is an RDS receiver. However, receiver design depends on the type of traffic broadcast system <NUM> transmitting the data <NUM> and, thus, the receiver <NUM> is not limited to any particular type of receiver. The receiver <NUM> includes an RDS decoder <NUM> that receives and formats the data <NUM>. The RDS decoder <NUM> provides the formatted data to a processor <NUM>. The processor <NUM> interprets the data and determines what action to take based on the data. For example, the processor <NUM> may read data from or write data to memory <NUM>. The memory <NUM> is not limited to any memory type.

While <FIG> depicts the receiver <NUM> having its own processor <NUM> and memory <NUM>, it is understood that the receiver <NUM> may share processing and memory with the navigation system <NUM> (i.e., an integrated system). For example, the receiver <NUM> may use the processor <NUM> and the non-volatile memory <NUM>. Moreover, the receiver <NUM> may have additional components not depicted in <FIG>.

Returning to <FIG>, the navigation system <NUM> also includes a user interface <NUM>. The user interface <NUM> includes appropriate equipment that allows the end-user (e.g., the driver or passengers) to input information into the navigation system <NUM>. This input information may include a request to use the navigation functions of the navigation system <NUM>. For example, the input information may include a request for a route to a desired destination, such as a point of interest. The input information may also include requests for other kinds of information.

The user interface equipment used to input information into the navigation system <NUM> may include a keypad, a keyboard, a microphone, and so on, as well as appropriate software, such as a voice recognition program. The user interface <NUM> also includes suitable equipment that provides information back to the end-user. This equipment may include a display <NUM>, speakers <NUM>, and other communication means.

The navigation system <NUM> uses a map database <NUM> stored on a storage medium <NUM>. In one example, the storage medium <NUM> is installed in the drive <NUM> so that the map database <NUM> can be read and used by the navigation system <NUM>. The storage medium <NUM> may be removable and replaceable so that a storage medium with an appropriate map database for the geographic region in which the vehicle is traveling can be used. In addition, the storage medium <NUM> may be replaceable so that the map database <NUM> on it can be updated easily. In one embodiment, the geographic data <NUM> may be a geographic database published by NAVTEQ North America, LLC of Chicago, Ill.

In one example, the storage medium <NUM> is a CD ROM disk. In another example, the storage medium <NUM> may be a PCMCIA card in which case the drive <NUM> would be substituted with a PCMCIA slot. Various other storage media may be used, including fixed or hard disks, DVD disks, or other currently available storage media, as well as storage media that may be developed in the future.

The storage medium <NUM> and the geographic database <NUM> do not have to be physically provided at the location of the navigation system <NUM>. In some examples, the storage medium <NUM>, upon which some or all of the geographic data <NUM> are stored, may be located remotely from the rest of the navigation system <NUM> and portions of the geographic data provided via a communications link, as needed.

In one type of system, the navigation application software program <NUM> is loaded from the non-volatile memory <NUM> into a Random Access Memory ("RAM") <NUM> associated with the processor <NUM> in order to operate the navigation system <NUM>. The processor <NUM> also receives input from the user interface <NUM>. The input may include a request for navigation information. The navigation system <NUM> uses the map database <NUM> stored on the storage medium <NUM>, possibly in conjunction with the outputs from the positioning system <NUM> and the receiver <NUM>, to provide various navigation functions.

The navigation application software program <NUM> may include separate applications (or subprograms) that provide these various navigation features and functions. These functions may include route calculation <NUM> (wherein a route to a destination identified by the end-user is determined), route guidance <NUM> (wherein detailed directions are provided for reaching a desired destination), map display <NUM>, and vehicle positioning <NUM> (i.e., map matching). Other functions and programming <NUM>, in addition to these, may be included in the navigation system <NUM>. The navigation application program <NUM> may be written in a suitable computer programming language such as C, C++, and Java. Other computer programming languages are also suitable.

<FIG> is a block diagram showing an example organization of data in the geographic database <NUM> depicted in <FIG>. In this example, the geographic database <NUM> is organized by data type. One way that the accessing of geographic data can be enhanced for performing various navigation functions is to provide separate collections or subsets of the geographic data <NUM> for use by each of the separate functions (e.g., <NUM>-<NUM>) in the navigation application program <NUM>. Each of these separate subsets is tailored specifically for use by one of the functions.

For instance, the route calculation function <NUM> normally requires only a portion of all the information in the geographic database <NUM> that is associated with a segment of a road. When the route calculation function <NUM> is being run, it may require information such as the speed along a road segment, turn restrictions from one road segment to another, and so on. However, the route calculation function <NUM> does not necessarily require the name of the road to calculate a route.

Similarly, when the route guidance function <NUM> is being run, some of the information associated with a segment of a road, such as the speed and turn restrictions, is not required. Instead, when the route guidance function <NUM> is being run, it uses information that includes the name of the road represented by the road segment, the address range along the road segment, any signs along the road segment, and so on.

Even further, when using the map display function <NUM>, some of the information associated with a road segment, such as the speed limits or turn restrictions, is not required. Instead, when the map display function <NUM> is run, it uses only a portion of the information associated with the road segment, such as the shapes and locations of roads, and possibly the names of the roads.

Although there may be some overlap as to the types of information used by the various navigation functions, some of the data used by these navigation functions is only used by one of the functions. If all the information relating to each road segment were associated with it as a single data entry in a single database, each data entity record would be relatively large. Thus, whenever any one of the navigation functions accessed an entity record, it would have to read into memory a significant amount of information much of which would not be needed by the navigation function. Moreover, when reading the data entity from disk, relatively few data entities could be read at a time since each data entity would be relatively large.

In order to provide the information in the geographic database <NUM> in a format more efficient for use by each of the navigation functions, separate subsets of the entire geographic database <NUM> for a given geographic region are provided for each of the different types of navigation functions to be provided in the navigation application program <NUM>. <FIG> illustrates the geographic database <NUM> comprised of separate routing data <NUM> (for route calculation), cartographic data <NUM> (for map display), maneuver data <NUM> (for route guidance), point-of-interest data <NUM> (for identifying specific points of interest, such as hotels, restaurants, museums, stadiums, airports, etc.), and junction data <NUM> (for identifying named intersections).

In addition to these types of data, the geographic database <NUM> may include navigation feature data <NUM>. This subset of data includes names of navigable features (such as roads). The geographic database may also include data subsets for postal codes <NUM> and places <NUM> (e.g., cities, states, and counties).

The geographic database <NUM> also includes traffic pattern data <NUM>. The traffic pattern data <NUM> includes a traffic pattern code that identifies a particular traffic pattern. The traffic pattern code can be any combination of numbers, letters, and symbols. A traffic pattern is associated with each traffic pattern code. A traffic pattern is data that represents the expected traffic speeds by day of the week and time of the day.

The traffic pattern data associated with a traffic pattern code (e.g., XY3Z!) may be organized in table format as shown in Table <NUM> as follows.

Column <NUM> of Table <NUM> includes a day code. The day code column includes data associated with days of the week and other days of interest. For example, the days of the week may be represented numerically (e.g., Sunday=<NUM>,. Saturday=<NUM>). As another example, the other days of interest may be assigned numerical codes, such as <NUM>=Thanksgiving, <NUM>=Easter Sunday, and so on. Other coding schemes may also be used to identify days of the week and other days of interest.

The remaining columns of Table <NUM> include time period data. The time period columns include data associated with a speed value for a period of time. For example, the period of time may be fifteen minutes. In this example, there are ninety-six time periods, each associated with a speed value. Other time period durations may also be used. The speed value may be a number representing an average speed (e.g., miles per hour (MPH), kilometers per hour (KPH), meters per second (MPS)) for the time period measured at the associated location. The speed value may also represent other values, such as the median speed for the time period measured at the associated location.

The traffic pattern data <NUM> may also be represented by a traffic pattern code associated with a graph that represents expected travel times. <FIG> is a graph <NUM> that depicts an example traffic pattern <NUM>. The traffic pattern <NUM> is defined as the speed values in time period order, which comprises an entire day for a given location code.

While the traffic pattern data <NUM> is shown stored in the geographic database <NUM>, it is understood that the traffic pattern data <NUM> may also be stored in a separate database.

The traffic pattern data <NUM> is associated with one or more locations. The locations may be represented by geographical coordinates (e.g., latitude, longitude, and optionally altitude), traffic codes (e.g., Radio Data System Traffic Message Channel (RDS-TMC) codes and Vehicle Information and Communication System (VICS) codes), road segment identifications, grid or tile identifications, and/or any other method of identifying a physical location on or adjacent to a road network in the real world.

The traffic pattern data <NUM> may be associated with roads having different functional classes. For example, a road associated with functional class <NUM> may include high volume, controlled access roads, such as expressways and freeways. Roads associated with functional class <NUM> may be high volume roads with few speed changes, but are not necessarily controlled access roads. The lower ranked roads handle correspondingly lower volumes and generally have more speed changes or lower speeds. Real-time traffic data may only be available for some road classifications, such as functional class <NUM> and <NUM>. The traffic pattern data <NUM> may be associated with the lower functional class roads as well as roads associated with functional class <NUM> and <NUM>.

The geographic database <NUM> may not include all of these subsets. Moreover, the geographic database <NUM> may include other subsets of data <NUM>.

<FIG> is a flowchart of a method <NUM> for selecting one or more traffic patterns when traffic conditions are abnormal at a location. Abnormal traffic conditions for a location are traffic conditions differing from the traffic pattern data <NUM> associated with the location at a current time period. During normal traffic conditions, the navigation system <NUM> uses the traffic pattern data <NUM> associated with the location and current time period. However, during abnormal traffic conditions occurring at the location, the traffic pattern associated with the location is not representative of traffic conditions.

At block <NUM>, the traffic broadcast system <NUM> receives information regarding abnormal traffic conditions for a particular section of a road network. The abnormal conditions may be that traffic is moving faster or slower than expected. The abnormal conditions may be caused by a traffic accident, construction, weather conditions, special events, sporting events, and so on. The traffic broadcast system <NUM> may receive the information regarding the abnormal conditions from the sensors <NUM> or other communication means, such as communication from local departments of transportation, emergency responders, and other agencies.

At block <NUM>, the traffic broadcast system <NUM> identifies a traffic pattern that approximates the abnormal conditions. The traffic broadcast system <NUM> identifies an existing traffic pattern that is associated with other locations during normal traffic conditions. For example, if the traffic pattern assigned to the current time period for a location indicates an expected travel time of 45mph and the current travel time for the location is 30mph, the traffic broadcast system <NUM> identifies a traffic pattern that indicates an expected travel time of 30mph for the current time period. If there is more than one traffic pattern that indicates an expected travel time of 30mph for the current time period, the traffic broadcast system <NUM> may select the traffic pattern that is expected to most closely match conditions in the subsequent time periods.

At block <NUM>, the traffic broadcast system <NUM> transmits a message that includes a code associated with the traffic pattern identified at block <NUM>. The traffic broadcast system <NUM> may broadcast a traffic message <NUM> that includes the traffic pattern code <NUM>(<NUM>). Alternatively, the traffic broadcast system <NUM> may broadcast the traffic pattern code alongside a traffic message using a proprietary protocol registered as an ODA. As yet another example, the traffic broadcast system <NUM> may send the traffic pattern code by direct wireless transmission (i.e., non-broadcast mode), such as a cellular wireless transmission (e.g., using GPRS or TDM). In this example, the traffic broadcast system <NUM> may transmit additional data to identify where abnormal traffic conditions are occurring.

Regardless of transmission type, the message also includes a period of validity. The period of validity identifies how long the traffic pattern associated with the traffic pattern code in the message should be used by the receiving device. The period of validity may include a time (e.g., <NUM>:<NUM> - <NUM>:<NUM>) or a code that represents a period of time.

Alternatively, the receiving device, such as the navigation system <NUM>, may use a default period of validity. For example, the navigation system <NUM> may use a default duration of <NUM> minutes. If the navigation system <NUM> does not receive another message from the traffic broadcast system <NUM> within the thirty minutes, the navigation system <NUM> reverts back to using traffic patterns based on day of week and time of day.

Transmitting the message with the traffic pattern code reduces the transmission costs as compared to the costs associated with transmitting real-time traffic data. Moreover, the message with the traffic pattern code may be transmitted for a class of road that is not typically associated with real-time traffic data. Thus, the navigation system receives timely updates with minimum cost.

<FIG> is a flowchart of a method <NUM> for receiving a code identifying a traffic pattern. navigation system <NUM> receives one or more traffic pattern codes from the traffic broadcast system <NUM> using the method <NUM>. Of course, other systems may receive traffic pattern codes, such as a mobile telephone, a tablet computer, and a personal computer.

At block <NUM>, the navigation system <NUM> receives a message that includes one or more traffic pattern codes. The message may also include a period of validity for using the traffic patterns associated with the codes. The message may also include data identifying the location of the abnormal traffic conditions. The receiver <NUM> of the navigation system <NUM> may receive the message via a wireless communication link.

At block <NUM>, the navigation system <NUM> receives a request for navigation features. For example, a user of the navigation system <NUM> may request a route from an origin to a destination. As another example, the user may request a map showing the user's current location. As yet another example, the user may request an estimated time to travel to a location and/or an estimated time of arrival at the location. Further still, the user may request a departure time to arrive at a location by a certain time.

At block <NUM>, the navigation system <NUM> determines whether the request for navigation features is received during the period of validity included in the message or a default time period previously stored in the navigation programming <NUM>. If not, at block <NUM>, the navigation system <NUM> selects one or more traffic patterns <NUM> stored in the geographic database <NUM> based on day of the week and time of the day to provide the navigation functions. If so, at block <NUM>, the navigation system <NUM> selects one or more traffic patterns <NUM> stored in the geographic database <NUM> based on the traffic pattern code(s) received in the message at block <NUM>.

The traffic patterns selected at block <NUM>, <NUM> may be used to calculate a route. The route calculation program <NUM> calculates a route from a starting point (also referred to as an origin) to a destination. The route calculation program <NUM> may use any suitable routing algorithm, such as the Dijkstra algorithm or the A* algorithm.

The route calculation program <NUM> uses a cost to identify an optimal route. Here, cost refers to a user's preference for a route. For example, the user may desire the shortest route, the fastest route, or the most energy efficient route for traveling from an origin to a destination. The route calculation program <NUM> may use the traffic pattern as a cost in calculating the fastest route and the most energy efficient route. The route calculation program <NUM> may also use the traffic pattern to calculate an estimate time for traveling from the origin to the destination, an estimated time of arrival, and a departure time to arrive at the destination by or before a certain arrival time.

The route calculation program <NUM> may also re-calculate the route if the user of the navigation system <NUM> is currently following a route and the navigation system <NUM> receives a message with a traffic pattern code. After performing the re-calculation, the navigation system <NUM> may provide the user with an option of routes along with the expected travel times associated with the routes allowing the user to choose whether to change routes. Alternatively, the navigation system <NUM> may select which route to use when providing route guidance.

The map display program <NUM> may use the traffic patterns to display a map that includes traffic information. For example, the map display program <NUM> may display a map where the roads are color-coded green, yellow, and red to indicate traffic conditions. After the navigation system <NUM> receives a message with a traffic pattern code, the map display program <NUM> may update the color for a portion of the road network impacted by the abnormal traffic conditions.

Once the period of validity for the traffic pattern code expires, the navigation system <NUM> reverts back to selecting traffic patterns based on day of the week and time of the day. Beneficially, the navigation system <NUM> only stores one traffic pattern database. The navigation system <NUM> does not need to store and update an event calendar. Moreover, the navigation system <NUM> does not need to assign more than one traffic pattern to a segment (i.e., the normal traffic pattern and one or more abnormal traffic patterns). Instead, as unusual conditions occur, the navigation system <NUM> receives a message identifying a traffic pattern that is already stored in the geographic database <NUM> to use for a period of time instead of the usual traffic pattern.

Claim 1:
A computer-implemented method comprising:
transmitting (<NUM>) a message (<NUM>) by a Traffic Broadcast System (<NUM>), the message comprising a location (<NUM>(<NUM>)), a traffic pattern code (<NUM>(<NUM>)) and a time period of validity (<NUM>(<NUM>));
receiving the message by a Navigation System (<NUM>); and
selecting (<NUM>) a first traffic pattern (<NUM>, <NUM>) stored in a geographic database (<NUM>), wherein the first traffic pattern (<NUM>, <NUM>) is selected based on a current time period, represents an expected traffic speed for a first location (<NUM>(<NUM>)) on a section of a road network (<NUM>) for the current time period, and is identified by a first traffic pattern code (<NUM>(<NUM>));
using the first traffic pattern (<NUM>, <NUM>) to perform a navigation system function associated with travelling in the section of the road network (<NUM>);
receiving (<NUM>) a message (<NUM>) from the Traffic Broadcast System (<NUM>) including a second traffic pattern code (<NUM>(<NUM>)) which identifies a second traffic pattern (<NUM>, <NUM>) stored in the geographic database (<NUM>), the second traffic pattern (<NUM>, <NUM>) representing an expected traffic speed for a second location (<NUM>(<NUM>)) on the road network (<NUM>) for the current time period, the second location (<NUM>(<NUM>)) being different from the first location (<NUM>(<NUM>)) on the road network (<NUM>);
during (<NUM>) a specified time period of validity (<NUM>(<NUM>)) for the second traffic pattern (<NUM>, <NUM>), using (<NUM>) the second traffic pattern (<NUM>, <NUM>) to perform the navigation system function associated with travelling in the section of the road network (<NUM>); and
after expiry of the time period of validity (<NUM>(<NUM>)), reverting to using (<NUM>) the first traffic pattern (<NUM>, <NUM>) for performing the navigation system function associated with travelling in the section of the road network (<NUM>).