TRAFFIC INFORMATION

Field of the Invention

The present invention relates to methods for providing information regarding traffic conditions within a road network in an area covered by an electronic map, the electronic map comprising a plurality of segments representing roads of the road network. The invention also extends to systems, and particularly to servers, for performing such methods.

Background

Drivers are always searching for the fastest route to their destination and as roads become more congested there is therefore an increasing demand for reliable and up-to-date traffic information. It has been possible for many years to receive traffic information in a variety of ways, for example, via television or radio broadcasts, or text messaging services. Flowever, with the increasing use of on-board navigation systems, such as portable navigation devices (“PNDs"), it is more desirable for the traffic information to be integrated within the navigation system so that a driver can immediately see if there is congestion on a route, and thus choose to navigate around it, or so that the navigation system can plan an alternative route through a road network avoiding the congestion.

Traffic Message Channel (“TMC") is one technology for delivering relevant traffic and travel information to vehicles travelling within a road network. For instance, TMC may help in identifying traffic congestions and blockages, which information may in turn be used for providing improved navigation guidance, e.g. for guiding vehicles along alternative routes through the road network that are less congested. In order to implement TMC, a number of small radio devices (TMC sources) are typically placed at certain strategic junctions within the road network. These radio devices transmit, typically via conventional FM radio broadcasts, TMC messages regarding traffic incidents within the road network. For example, the messages may suitably comprise information regarding the type and location of a traffic incident as well as information about the expected duration of the incident and the extent of the road network that is affected. There are number of vendors that provide such TMC services in different countries but generally the TMC messages are transmitted in substantially the same format, e.g. a format certified by the central Traffic Information Services Association (TISA). The TMC messages that are transmitted by the TMC sources can therefore be received using a suitable antenna and then processed to provide the relevant traffic-related content, e.g. for output and/or display to a navigation system.

Most modern navigation systems include an electronic map that represents the road network within which the vehicle is currently travelling in. Thus, what is generally desired when implementing TMC is to be able to incorporate the traffic information obtained from the TMC service into the electronic map, e.g. so that it can then be suitably implemented within the electronic map to visualise the traffic conditions and/or for route planning. In order to implement traffic information from the TMC service into an electronic map, the TMC message content must therefore be suitably processed and interpreted. In some cases, the navigation system itself comprises an antenna so that the navigation system can receive the TMC messages directly. However, in this case, there may be a relatively high processing burden on the navigation system, as well as a bandwidth limit on the amount of TMC messages that can be received. Furthermore, because TMC messages are typically sent over the FM radio network there may be instances where the navigation system is out of signal such that it may not always be possible for the navigation device to receive TMC messages and the driver may therefore only periodically receive relevant traffic updates. Accordingly, more often, TMC messages are processed on a remote server that receives the TMC messages for processing, and then updates an electronic map accordingly, so that the updated electronic map including the TMC information can then be provided to a navigation system of a vehicle over a suitable wireless data connection (e.g. GPRS, EDGE, UMTS, CDMA, etc.). This may allow for a more constant stream of traffic information to be provided to the vehicles within the road network. This may also allow for better control over the quality of the traffic data since traffic information can be processed and monitored centrally on the server to ensure that the traffic conditions are reliably mapped onto the road network defined within the electronic map.

However, there can still be various difficulties associated with this approach.

Accordingly, the Applicants believe that there remains room for improvement in this regard.

Summary

From a first aspect there is provided a method for providing information regarding traffic conditions within a road network in an area covered by an electronic map, the electronic map comprising a plurality of segments representing roads of the road network, the method comprising:

obtaining, from a traffic data source having a known position relative to the road network, traffic data including information indicative of traffic conditions at a location within the road network, wherein the location is defined within the traffic data using one or more road name(s) included in the traffic data, and wherein the traffic data further includes the position of the traffic data source relative to the road network;

identifying within an electronic map covering the area a set of one or more road(s) within the road network that fall within a predefined distance of the position of the traffic data source;

determining which of the road(s) within the set best matches the road name(s) included in the traffic data to determine a traffic point location representing the location of the traffic conditions within the electronic map; and

providing information indicative of the traffic conditions for inclusion into the electronic map at the determined traffic point location. Thus, embodiments of the present invention may allow for traffic data that is received from one or more traffic data sources (such as TMC radio devices) installed within the road network to be processed in order to determine where the traffic information included in the traffic data should be included within an electronic map. For instance, the traffic data may generally be received from a number of different providers and may not be directly compatible with the data stored within the electronic map. For example, the real-world location, e.g. a junction or roundabout within the road network, at which the traffic conditions are being reported is normally defined within the traffic data source using the names of intersecting roads at that location. Flowever, the road names included within the traffic data used to define the location of the traffic event often do not directly match the road names that are included within the electronic map. Also, it will be appreciated that the position of the traffic data source does not necessarily (and typically will not) correspond to the location of the traffic event, as the traffic data source can be quite far away from the actual junction where the traffic event is occurring. Conventionally, it can therefore be difficult to determine the traffic point location where the traffic information should be added into the electronic map.

According to embodiments of the invention, a set of possibly matching roads falling within a predefined distance of the traffic source is first identified, and a name matching algorithm is then applied to determine which of the road names defined within the electronic map best matches the road names included within the traffic data. The location of the traffic conditions can then be matched to the correct position within the electronic map.

Advantageously, in embodiments, this can be done automatically, without any human intervention. Prior to this, where the traffic source data was incompatible with the map data, the traffic data would have to be sent to a cartographer for manual editing. Thus, embodiments of the present invention may allow for a significant reduction in man hours (and cost) as well as processing time associated with implementing traffic data into an electronic map, potentially allowing in turn for better more up-to-date traffic information to be provided. Furthermore, the present techniques may offer a more scalable approach, which may be desirable as the traffic data source coverage increases.

The invention also extends to systems for performing such methods. Accordingly, from a second aspect there is provided a system for providing information regarding traffic conditions within a road network in an area covered by an electronic map, the electronic map comprising a plurality of segments representing roads of the road network, the system comprising processing circuitry operable to:

obtain, from a traffic data source having a known position relative to the road network, traffic data including information indicative of traffic conditions at a location within the road network, wherein the location is defined within the traffic data using one or more road name(s) included in the traffic data, and wherein the traffic data further includes the position of the traffic data source relative to the road network;

identify within an electronic map covering the area a set of one or more road(s) within the road network that fall within a predefined distance of the position of the traffic data source; determine which of the road(s) within the set best matches the road name(s) included in the traffic data to determine a traffic point location representing the location of the traffic conditions within the electronic map; and

provide information indicative of the traffic conditions for inclusion into the electronic map at the determined traffic point location.

This further aspect of the present invention can and preferably does include any one or more or all of the preferred and optional features of the invention described herein in respect of any other aspects or embodiments of the invention, as appropriate. For example, even if not explicitly stated, the system may comprise means for carrying out any step or steps described in relation to the method herein in any of its aspects or embodiments, and vice versa. The means for carrying out any of the steps described in relation to the method or system may comprise one or more processors and/or processing circuitry. The present invention is therefore preferably a computer implemented invention, and any of the steps described in relation to any of the aspects or embodiments of the invention may be carried out under the control of a set of one or more processors and/or processing circuitry.

The system and/or one or more processors and/or processing circuitry may be at least part of a server or a navigation device. The steps of the method of the present invention in any of its aspects or embodiments may therefore be carried out in part by a server and/or in part by a navigation device. For example the steps of the method may be performed exclusively on a server, or some on a server and the others on a navigation device in any combination, or exclusively on a navigation device. Performance of one or more of the steps on the navigation device may reduce any bandwidth required for network communication. Flowever, performing the steps on the server may be efficient and may reduce the computational burden placed on a navigation device. This also allows for central quality control over the traffic information and for updated traffic information to be provided to a plurality of navigation devices at substantially the same time. Thus, at least in some preferred embodiments, the steps are performed on a server. Accordingly the invention can encompass a server arranged to provide information regarding traffic conditions within a road network in an area covered by an electronic map, the electronic map comprising a plurality of segments representing roads of the road network.

Embodiments of the invention relate to providing traffic information regarding the traffic conditions on a road network including a plurality of roads (or road elements) along which vehicles can travel. Flowever, in principle, the techniques presented herein may also be applied more generally to any navigable networks including a plurality of navigable elements along which vehicles can travel and which may be subject to congestion. So, although the navigable network may in embodiments comprise a road network, wherein each navigable element represents a road or a portion of a road, e.g. between two adjacent intersections of the road network, the navigable network is not limited to a road network, and may comprise, for example, a network of foot paths, cycle paths, rivers, etc. Thus, while embodiments of the present invention are described with particular reference to roads, it should be realised that the invention may also be applicable to other navigable elements, such as segments of a path, river, canal, cycle path, tow path, railway line, or the like. Thus, any reference to a“road" or "road network" may be replaced by a corresponding reference to a“navigable element" or“navigable network" or any specific type or types of such navigable elements or network.

The road network may be covered by, i.e. represented by, an electronic map, e.g. in a manner that is generally known in the art. An electronic map (or mathematical graph, as it is sometimes known), in its simplest form, is effectively a database containing data representative of nodes, most commonly representative of road intersections, and lines between those nodes representing the roads between those intersections. In more detailed digital maps, lines may be divided into segments defined by a start node and end node.

These nodes may be“real" in that they represent a road intersection at which a minimum of three lines or segments intersect, or they may be "artificial" in that they are provided as anchors for segments not being defined at one or both ends by a real node to provide, among other things, shape information for a particular stretch of road or a means of identifying the position along a road at which some characteristic of that road changes, e.g. a speed limit. In practically all modern digital maps, nodes and segments are further defined by various attributes which are again represented by data in the database. For example, each node will typically have geographical coordinates to define its real-world position, e.g. latitude and longitude. Nodes will also typically have manoeuvre data associated therewith, which indicate whether it is possible, at an intersection, to move from one road to another; while the segments will also have associated attributes such as the maximum speed permitted, the lane size, number of lanes, whether there is a divider in-between, etc.

The present invention generally relates to providing information regarding traffic conditions within the road network covered by the electronic map. For example, it may be desired to incorporate information regarding traffic conditions, or a‘traffic event’, within the road network such as congestion (traffic jams), blockages, accidents, etc., into the electronic map to allow this information to be suitably used, e.g. either for display to a user of a navigation system, or by the navigation system for route planning purposes. So, the information indicative of the traffic conditions may generally include any suitable and desired information regarding e.g. the nature of the traffic conditions, as well as the geospatial extent and expected duration thereof.

Information regarding traffic conditions within the road network may be provided by a number of traffic data sources that are installed at various known (fixed) locations throughout the road network. For instance, in embodiments, each traffic data sources may comprise a radio beacon installed at a certain location within the road network that is operable to broadcast traffic data messages containing information regarding the current traffic conditions within the vicinity of the traffic data source. Typically such traffic data sources may transmit messages over the conventional FM radio range. Flowever, in principle, any suitable wireless communication protocol may be used to transmit the traffic data, including, among others, Digital Audio Broadcasting or satellite radio. For example, the traffic data sources may comprise part of a known Traffic Message Channel (“TMC") system operating within the road network. In this case, the traffic data may comprise one or more TMC messages. However, other arrangements would of course be possible.

Thus, the invention comprises a step of obtaining, from a traffic data source having a known location relative to the road network, traffic data including information indicative of traffic conditions at one or more location(s) within the road network. Each location can be defined within the traffic data using one or more road name(s) that are included in the traffic data. The traffic data also includes the location of the traffic data source relative to the road network. In some embodiments, the step of obtaining the source data may comprise accessing the data, i.e. the data being previously received and (at least temporarily) stored. The method may further comprise storing the received source data before proceeding to carry out the other steps of the present invention. It will be appreciated that the step of receiving the source data need not take place at the same time or place as the other step or steps of the method. For instance, in preferred embodiments, the traffic data from a plurality of traffic data sources within a road network will be received by a central server for processing.

The traffic data may generally include any suitable information indicative of traffic conditions at one or more traffic point location(s) within the road network that is desired to be included into the electronic map. The traffic data may, for example, include information regarding the nature of the traffic conditions at a particular location within the road network. The traffic data may also include any other suitable and desired information, e.g. regarding the extent and expected duration of the traffic conditions within the network. The location of the traffic conditions is thus a real-world location, e.g. a junction or a roundabout, at which the traffic conditions are currently being experienced. This location may be defined within the traffic data using the names of the roads on which the traffic conditions exist, or more often (e.g. where the traffic point location is a junction or a roundabout) using the names of the intersecting roads leading to a particular junction, etc. That is, the location of the traffic conditions is generally defined with reference to one or more road names that are included within the traffic data. The traffic point location may, for example, generally correspond to a certain road (element) or junction within the road network.

The traffic data also includes the position of the traffic data source relative to the road network which may typically be defined using the geospatial co-ordinates, e.g. latitude and longitude, of the traffic data source. It will be appreciated that the location of the traffic data source is typically fixed within the road network. For example, the traffic data sources are generally installed at a number of strategic locations, e.g. junctions, within the road network.

It will also be appreciated that the position of the traffic data source does not generally therefore correspond to the actual location of the traffic event.

The names of the roads within the road network are also generally defined (and stored) within the electronic map. However, often, the road names in the map data are provided in a format that is somehow incompatible with that of the traffic data so that there may not be a direct match between a road name included in the traffic data and the road name for the same road as defined in the electronic map. Thus, in order to implement the traffic information into the electronic map it is necessary to try to match the road names in the traffic data to those within the electronic map.

It is expected that a traffic condition being reported by a certain traffic data source will relate to a road that is in the general vicinity of that traffic data source. Thus, once the traffic data has been obtained, the invention proceeds to identify a set of roads within the electronic map that fall within a predefined distance of the location of the traffic data source. For instance, all roads within the electronic map that fall within a predefined radius of the traffic data source, or falling within a predefined polygon extending around the traffic data source, may be included within the set. The predefined distance may be set or selected as desired. For example, in some cases, the predefined distance may be set or selected based on the spacing between traffic data sources throughout the network. It will be appreciated that the predefined distance may generally be defined either in terms of a real distance (e.g. in kilometres), or in terms of a number of road segments, etc.

Thus, a set comprising a plurality of roads falling within a predefined distance of the traffic data source can be identified. From this set, the invention then proceeds to determine which of the roads of the electronic map‘best’ matches the roads included within the traffic data. In this way, the location of the traffic event within the electronic map, i.e. a‘traffic point location’ representing the location at which the traffic conditions should be added onto the electronic map, may be suitably determined.

For example, a suitable name matching algorithm may be used to look for matches between the road names included in the traffic data and those within the electronic map. In general, any suitable matching algorithm may be used. For instance, where the road names are included within the traffic data and/or electronic map as a text (alphanumeric) string, the matching algorithm may compare the strings, or at least a part thereof, to look for name matches.

In embodiments, the name matching algorithm may proceed by analysing the road names included in the traffic data and/or electronic map, and preferably both, in order to identify and exclude any common prefixes, suffixes, abbreviations or road name separators.

In this way, the road names can be tidied up to remove potentially superfluous and confusing information making it easier to identify matches. For instance, a road“Western Street", could be alternatively represented as“Western St.’’, or“Western Strt”, etc. Removing the suffix completely helps to prevent this potential inconsistency. That is, determining which of the road(s) within the set best matches the road name(s) included in the traffic data may comprise processing the road names included within the traffic data and/or within the electronic map in order to identify prefixes, suffixes, abbreviations or road name separators. These elements can be excluded when determining which of the road(s) within the set best matches the road name(s) included in the traffic data. Thus, the name matching may be performed based on the processed, or tidied up, road names. It is also contemplated that machine learning approaches may be used, for example, a machine learning algorithm that has been trained using suitable road name data may be used to help determine the‘best’ match. This may help (further) increase the likelihood of finding a match, e.g. by allowing“fuzzy" matching to be performed.

Once the location of the traffic conditions within the electronic map has been suitably determined, information indicative of the traffic conditions at the traffic point location(s) can then be provided for inclusion into the electronic map. For instance, the invention may then involve further steps of updating the electronic map to include the traffic information. The updated electronic map may then be provided for output, e.g. to a navigation system, or a user thereof. For example, the electronic map including the traffic conditions may be provided for display on a display device of a navigation system. Additionally, or alternatively, the electronic map including the traffic conditions may be used by the navigation system for route planning.

In general, within a given road network, there will be a plurality of traffic data sources providing traffic data regarding traffic conditions at various different locations throughout the road network. Thus, the invention may be performed for traffic data obtained from multiple different traffic data sources and for traffic conditions occurring at multiple different locations within the network. Thus, in embodiments, the traffic data may be obtained from one or more traffic data source(s) (and the traffic data from each traffic data source may thus include the position of that traffic data source). The steps of the invention described herein, according to any of its embodiments, may thus be performed for each set of traffic data that is obtained.

In this way, a plurality of traffic point locations within the road network may be identified and included within the electronic map. Also, traffic conditions normally have some extent through a road network. Thus, the same traffic event may be reported by multiple different traffic data sources so that a plurality of traffic point locations associated with the same traffic event may be identified within the electronic map.

In order to analyse the extent of the traffic conditions throughout the road network it may be desired to identify one or more traffic paths extending between any (and preferably all) identified traffic point locations. For instance, a traffic path within the road network may be created by connecting a plurality of traffic point locations identified within the electronic map together in sequence. Again, according to embodiments, this can be performed

automatically, without requiring human intervention.

For instance, a suitable chaining algorithm may be used for identifying on which route(s) (within the electronic map) the traffic path should be created. For example, given two traffic point locations within the electronic map, a traffic segment may be created, wherein the traffic segment comprises one or more roads in the road network extending between the two traffic point locations. For instance, a distance may be calculated from one of the traffic point locations to the other along the roads in the road network in order to identify a chain of road elements between the two traffic point locations. A plurality of traffic segments may be created using all of the traffic point locations within the electronic map. The plurality of traffic segments can then be joined together to create the entire traffic path extending through the road network.

These steps may generally take into account the locations of the chains as well as the direction of traffic flow restrictions and road types, etc., which are generally available within the electronic map. For instance, in order to create a chain of road elements between two traffic point locations (a traffic segment), a chaining algorithm may be used that, starting from a first traffic point location (i.e. a first road element), proceeds to traverse the network to attempt to create a connected chain of road elements from the first traffic point location to a second traffic point location. At each junction along the road network, the algorithm may thus (attempt to) add a connected road element to build a chain. For junctions where there are multiple plausible connected road elements (which is most often the case), the algorithm may then select which one to add to the chain. For instance, to do this, a comparison may be made between all plausible road elements at the road junction with the previous road element already included in the chain.

Thus, in embodiments, creating a traffic segment may comprise: providing as input a first traffic point location; and building a chain between the first traffic point location and a second traffic point location by traversing the road network starting from the first traffic point location and at each junction in the road network adding connected road elements to the chain. When there are multiple road elements connected to a junction, a step of comparing one or more road attributes of the multiple road elements with the previous road element added in the chain may be performed to select which of the road elements to add to the chain.

The comparison may, for example, take into account various road attributes such as: the direction of traffic flow, the road type, the route number of the road element, the route name of the road element, the street name of the road element and the form of the roadway. For example, in some cases, a comparison can be made using each of these attributes in turn. The chaining may be performed in a generally heuristic manner. Flowever, it is also contemplated that machine learning approaches may be used for the chaining.

The chaining algorithm may be run for all pairs of traffic point locations identified within the road network to create a plurality of traffic segments. Similar algorithms may then be used to join the traffic segments together to create a traffic path extending through the road network.

Thus, embodiments of the invention may provide a tool for automatically generating traffic paths for inclusion into an electronic map. Prior to this, all of the editing required to create such traffic paths was performed manually with a significant associated cost in terms of man power as well as processing time.

It will be appreciated that the present invention is preferably a computer-implemented invention. Any of the steps described in relation to any of the aspects or embodiments of the invention may therefore suitably be carried out under the control of a set of one or more processors and/or suitable processing circuitry. The processing circuitry may generally be implemented either in hardware or software, as desired.

For instance, and without limitation, the means or processing circuitry for carrying out any of the steps described in relation to the method or system may comprise one or more suitable processor or processors, controller or controllers, functional units, circuitry, processing logic, microprocessor arrangements, etc., that are operable to perform the various steps or functions, etc., such as appropriately dedicated hardware elements (processing circuitry) and/or programmable hardware elements (processing circuitry) that can be programmed to operate in the desired manner. Thus, it will be appreciated that the methods in accordance with the present invention may be implemented at least partially using software.

Accordingly, it will be seen that, when viewed from further aspects and in further embodiments, the present invention extends to a computer program product comprising computer readable instructions adapted to carry out any or all of the method described herein when executed on suitable data processing means. The invention also extends to a computer software carrier comprising such software. Such a software carrier could be a physical (or non-transitory) storage medium or could be a signal such as an electronic signal over wires, an optical signal or a radio signal such as to a satellite or the like.

The present invention in accordance with any of its further aspects or embodiments may include any of the features described in reference to other aspects or embodiments of the invention to the extent it is not mutually inconsistent therewith.

It should be noted that references to a location, a position, or a road name, etc., herein should generally be understood to refer to data indicative of these factors unless the context demands otherwise. The data may be in any way indicative of the relevant feature, and may be directly or indirectly indicative thereof. Thus any reference to such features may be replaced by a reference to data indicative thereof.

Various features of embodiments of the invention will be described in further detail below.

Figures

Various aspects of the teachings of the present invention, and arrangements embodying those teachings, will hereafter be described by way of illustrative example with reference to the accompanying drawings, in which:

Figure 1 is a flow chart illustrating a method for creating traffic paths for inclusion within an electronic map according to an embodiment of the present invention;

Figure 2 illustrates an example of a method according to an embodiment of the present invention; and

Figure 3 illustrates an example of a method for creating a traffic segment within a road network according to an embodiment of the present invention. Description

Traffic Message Channel (“TMC") is a technology for delivering traffic and travel information to road vehicle drivers. It helps in identifying traffic congestions and blockages, which information can in turn be used to provide navigation guidance along different routes in the road network in accordance with the current traffic conditions, thus helping to better optimise navigation guidance and route planning for the driver. For this purpose, small TMC radio devices are placed near strategic junctions within the road network. In order to implement TMC within an electronic map, suitable traffic paths may be created over the roads within the electronic map based on the traffic data received from the TMC radio devices.

Creating traffic paths within an electronic map can be very difficult. For instance, as mentioned above, the location of traffic events is normally defined within the traffic data by reference to one or more associated road names. Flowever, it is often the case (as much as 80% of the time) that the road names with the traffic data do not directly match with any of the road names used in the electronic map. Also, the traffic point locations are often quite far removed from each other making it difficult to see how these locations should be connected to create a traffic path. So, conventionally, in order to create such traffic paths, the traffic data is sent to a cartographer for editing, with the cartographer identifying the complete route for the traffic path manually. This can be both expensive and slow and is not easily scalable to larger road networks with increased TMC coverage.

Thus, embodiments of the present invention may provide a tool for automatically determining the position of traffic events (i.e. traffic point locations) within an electronic map and then creating traffic paths accordingly. For instance, embodiments of the present invention relate to a tool than runs suitable algorithms for translating the traffic data and identifying the route (e.g. roads, junctions, roundabouts) on which the traffic path should be created. The traffic path can then be automatically created on the electronic map without human intervention. In this way, traffic conditions can be implemented within an electronic map faster, and at lower cost, than conventional manual approaches. This approach can also readily be adapted globally for any source data, e.g. in any language.

Figure 1 is a flow chart illustrating a method for creating traffic paths for inclusion within an electronic map according to an embodiment of the present invention.

In a first step, traffic data is obtained from one or more TMC sources within the road network (step 101 ). The traffic data received from each TMC source includes information regarding the current traffic conditions within the road network, as well as an indication of the location at which the traffic conditions are occurring. The location of the traffic conditions is typically conveyed using the road names of intersecting roads around the traffic point location. Flowever, often, the road names included within the traffic data do not exactly match with any road names inside the electronic map.

For example, it is often the case that different naming conventions or abbreviations may be used between the traffic data source and the map data (which is typically created after surveys and data received by different authentic sources like Government agencies, etc.). Table 1 below gives just some examples of possible differences between road names received from the TMC source compared to the map data:

Table 1 - Examples of Road names received

The traffic data received from the TMC source also contains the position of the TMC source within the road network, e.g. defined in terms of the longitude and latitude. It will be appreciated that although the position of the TMC source will typically be relatively close to the traffic point location, the position of the TMC source is simply the location of the radio device and bears no direct relation to the location of the traffic conditions that are being reported thereby. So, although the location of the TMC source may give a rough idea of the location of the traffic event, the position of the TMC source does not itself correspond to the actual location of the traffic event.

The method then proceeds by fetching all of the road names in the electronic map falling within a specified radius (e.g. 1 kilometre) of the position of the TMC source (step 102). This gives a list of road names defined in the electronic map that are within the vicinity of the TMC source for which it is therefore possible for a match to be found with the road names included in the traffic data for defining the traffic point location within the electronic map. This is illustrated in Figure 2. Figure 2 illustrates a road network that is represented by an electronic map and that includes a traffic data source 200. The traffic data source 200 is transmitting traffic information regarding a traffic event having a traffic point location 204 within the vicinity of the traffic data source 200. A boundary 202 can thus be drawn at a specified radius around the traffic data source 200 in order to identify a set of roads within the electronic map that might possibly match the road names that are being reported with the traffic data and that may therefore be used to determine the appropriate traffic point location 204.

A name matching algorithm can then be run to look for a match between these road names and the road names included in the traffic data in order to identify the position of the traffic point location within the electronic map (step 103). The name matching algorithm is run for every road that is found within a given radius of a TMC source, in order to find the junction or roundabout within the road network as defined by the electronic map on which the traffic event is to be plotted.

Normally, every road within the road network has a road name, typically within the local language, or sometimes in a translated form of a common language such as English. A road name can have some part of it as prefix or suffix, which may be commonly identified.

The presence and types of prefix or suffix that are commonly found generally vary from country to country. For example, in the United States of America, road names typically include a suffix such as“Street",“Boulevard", etc. So, if a road name is“Lincoln Street", the word“Street" may be identified as the suffix. On the other hand, in some countries, such as Cyprus, it is more common for road names to include a prefix such as“Parados",“Plateia", “Leoforos", etc. So, if a road name is“Leoforos Omirou", then the word“Leoforos" (which means Street in English) is identified as the prefix. Some part of the road name, including the prefix and suffix, can also some part abbreviated. For example, some commonly identified or sampled abbreviations might include“NE" for“Northeast", or“SW" for“Southwest", etc.. Also, it might happen that some road names include separators such as a dash or slash 7".

Given this, the basic input for the name matching algorithm may include a list of common prefixes, suffixes, abbreviations and road name separators, which may be set based on the country of interest. The name matching algorithm then acts to compare the road names given in the traffic data to the road names in the map database, e.g. using suitable “string" matching technology. The name matching algorithm is thus generally able to compared road names entered in any language (e.g. Arabic, Greek, Mandarin). During the matching, the algorithm may exclude any prefix, suffix, abbreviations and separators from both the road names in the map database and given in the traffic data in order to increase the likelihood of there being a successful match. If a match is found for any two or more roads, the search is positive, and the traffic point location within the electronic map can thus be identified. It will be appreciated that even with all these inputs and logic, it is still possible that we don’t get an exact name match with the TMC Source for all of the sampled Roads from map. However, the name matching algorithm significantly increases the likelihood of being able to match road names.

In order to connect identified traffic point locations within the electronic map, a chaining algorithm is run. The chaining algorithm generates a traffic segment connecting two traffic point locations together (step 104). All of the chains of the traffic segments are then gathered together in proper sequence in order to create one single traffic path within the electronic map (step 105). Thus, a full chain of traffic segments is created in one go that joins all of the identified traffic point locations together. For instance, after the name matching algorithm is run, there is a list of traffic point locations, e.g. road junctions or roundabouts, for inclusion within the electronic map. The chaining algorithm is thus deployed in order to connect these traffic point locations together. The chaining algorithm thus creates a chain of road elements between two traffic point locations within the electronic map. In order to make a chain, the chaining algorithm thus needs at least two traffic point locations. So, the name matching algorithm should at least identify two points on a traffic path to get some result from chaining algorithm. It will be appreciated that in the best case the extreme points of the traffic path are used for the chaining algorithm so that a complete traffic path can be created. However, the chaining algorithm may generally chain any two points. It can also make a chain even if there are a few unidentified points.

Thus, the basic inputs for the chaining algorithm are two traffic point locations within the electronic map, and one or more roads leading from one of the traffic point locations to the other. The one or more roads leading from one of the traffic point locations to the other may be found by calculating a distance of adjacent roads from one of the traffic point locations to the next nearest traffic point location. In order to make chains of road elements, the chaining algorithm may generally take into account the name of previous road in chain, direction of traffic flow restrictions and type of road (for example, major roads or high/freeways may be preferred).

For example, Figure 3 illustrates an example of a method for creating a traffic segment extending between a first traffic point location 301 and a second traffic point location 302. The chaining algorithm starts with a first road element 303 associated with the first traffic point location 301 . This is then extended to a first road junction 304. In the example illustrated in Figure 3, there is only a single connected road element 305 at the first road junction 304, so this is added to the chain. However, at the next road junction 306, there are now two connected road elements. In order to select the road element 307 to be added to the chain, the chaining logic makes a comparison between each of the plausible road elements at the junction and the previous road element 305 already included in the chain. This comparison may, for example, comprise comparing (in order): the direction of traffic flow, the functional road class (e.g. motorway, major road, etc.), the route number of the road element, the route name of the road element, the street name of the road element and the form of the road way (e.g. single carriageway, dual carriageway, slip road, etc.). The selected road element 307 is then added to the chain, and so on, until the chaining is complete, and a chain (traffic segment) extending between the first and second traffic point locations has been created.

In some cases the chaining logic may fail, e.g. if there are no matches at a particular junction. In that case, where no road element can be selected to be added to the chain, the chaining logic is then broken to give a‘partial’ chain. Generally, the chaining algorithm may be performed for all (pairs of) traffic point locations, in both directions. So, if the chaining algorithm results in only a partial chain extending from a first traffic point location to a second traffic point location, it may be possible that the chain is completed when chaining in the opposite direction from the second traffic point location to the first traffic point location.

A generally heuristic approach has been described in the examples above. However, it will be appreciated that in other embodiments machine learning approaches may be used in order to locate traffic point locations and/or make chaining with more accuracy.

Although the present invention has been described with reference to various embodiments, it will be understood by those skilled in the art that various changes in form and detail may be made without departing from the scope of the invention as set forth in the accompanying claims. It should also be noted that whilst the accompanying claims set out particular combinations of features described herein, the scope of the present invention is not limited to the particular combinations hereafter claimed, but instead extends to encompass any combination of features or embodiments herein disclosed irrespective of whether or not that particular combination has been specially enumerated in the accompanying claims at this time.