Location Referencing for Dummies

This article explains different location referencing methods in regard to suitability for systems dealing with traffic information and consisting of multiple subsystems, being developed and run by different parties.

Location is a point, linear section along a road or an area on Earth, which we want to address.

Location Reference is a message (depicted as a postcard in images below) by which provider describes a location to a consumer.

Location Referencing Method is set of data and rules, which the provider uses to write the location reference and the consumer to read it.

Provider is an entity publishing location references. In this article is provider depicted as my grandmother.

Consumer is an entity, receiving the location reference and trying to understand what location it describes. It is depicted as myself in teenage with a guitar.

My grandmother using outdated location set

My grandmother lived in Radslavice, a village close to town Přerov. In 1985, she asked me to buy some screws. Her description (location reference) of the hardware shop was: Go to Přerov, find Baťa shop and 50 m from there is a hardware shop, where I shall get the screws.

So I went to Přerov and got lost, because there was no Baťa building. I had no idea that 40 years ago had been the company Baťa transferred to state ownership and 4 years later was renamed to Svit, renaming most of the shops to Obuv (Shoes). It did not help me much, that about 6 years later would most of the shops be again renamed to Baťa.

When I went back to my Radslavice, I explained to my grandma, that she is using very outdated location set and should update it.

Drawing

Two weeks later I visited my grandma with my younger brother (playing the clarinet). This time it was his turn to go to hardware shop - any my grandma did use exactly the same location reference as before - referring to non-existent Baťa shop.

From this I have learned, that it is not easy to update even very outdated location set.

Heading to problems with Nation Traffic Information Centre

Jaroslav Zvára was a professional dreamer dreaming about drivers, reporting traffic events to a call centre, roadworks and closures being registered in one central system. His strange habit to turn the dreams into reality meant in 2005 that there was ongoing project called JSDI (United system of traffic information) including all relevant state organizations and that there was built NDIC (National Traffic Information Centre), where was all the systems gathered and stored in central data stored.

When he called me, that all the systems in JSDI will be using one common map data set called Global Network, I got scared. Reminding the large block schema of NTIC exchanging data with many different organizations using systems developed by various companies I told him: “You are heading into big trouble.” and explained to him, that at the moment the Global Network map will be about to be updated, it will be very difficult task, as it requires too many different organizations and developers to update the maps at the very same hour. Jaroslav did not care and the system was built assuming all participants would share exactly the same version of Global Network.

Drawing

Few years later the problem appeared exactly as I predicted and update of Global Network map in all participating subsystems was delayed about one and half a year.

From this I have learned, that complexity of map updates with shared map location referencing grows with number of participants.

Anyway, I have to admit, that at that time, there was no better feasible alternative to location referencing using shared map, as dynamic location referencing methods were not mature enough yet.

Location referencing using shared map

The reality (depicted as a globe) is described by means of a map. Road segments are represented by so called “features”, each feature having in the same version of the map unique ID. Long road consisting of multiple road segments is represented as list of feature IDs, e.g. [1235, 1236, 1238].

Provider and consumer must have exact copy of such a map. As the IDs are changing between versions of a map, it means it must be exactly the same version.

If my grandma wants to describe a location, she would write following location reference:

  • map: GlobalNetwork
  • version: 2012-02
  • ids: [1235, 1236, 1238]

I, as a consumer, would get the location reference, check, that the map provider and version used is what I have in my own system currently implemented, and then would use the list of IDs to find the location my grandma wanted to describe.

Used data sets:

  • map (exact copy for provider and consumer)

Drawing

pros (assuming, both parties have exactly the same version of the map)

  • very simple structure of location reference
  • precise description of the location
  • simple and cheap encoding and decoding
  • 100% success rate when decoding the location

cons

  • all participants must use exactly the same map version
  • vendor lock in - all participants are forced to use the same map provider
  • difficult coordination of map updates when systems are run by different subjects
  • translation of location references from one version to another is not easy
  • using historical location references is practically impossible

Coordinate map update is difficult, because there are different subjects, each having independent budgets and management and each have to agree with system provider on the update. If we take into account private companies consuming the data, they often struggle with the costs related to purchasing new map licence. This often result in using different map and degraded location referencing decoding success rate and precision.

Location referencing using predefined location set

Predefined location set location referencing is based on an agreement between provider and consumer what locations can be referred to. Typical example is ALERT-C location tables as used in broadcasting traffic information via RDS-TMC, but very similar rules apply to any predefined location set alternatives.

  1. provider and consumer agree on set of locations to be used (LOC TAB).
  2. to use specific map vendor and specific version of a map and location table, map vendor must provide so called LINK data, which provides location reference of each predefined location from LOC TAB in given map version.

Encoding location reference

  1. my grandma creates a location in her map as before with shared map
  2. using LINK data tries to find out, what predefined location(s) it fits best to. It may happen, that there is no such predefined location and sometime it is described by multiple predefined locations.
  3. assuming some predefined location id was found, location reference is created:

Location reference:

  • LOCTAB: 6 (refers to specific country and predefined location set provider)
  • Version: 3.0 (specific version of location table)
  • primary point: 1024
  • extent: 3
  • direction: +

Decoding location reference

  1. I check, that the loctab number and version is exactly the same which my LINK data supports. If it does not match, I am unable to decode.
  2. Using LINK data I create resulting location from primary point, extent and direction, getting list of feature IDs in my map data.

Used data set:

  • LOC TAB (often provided for free, sometime for relatively small fee)
  • provider map data
  • LINK data for provider map (relating exactly to given LOC TAB number and version)
  • consumer map data
  • LINK data for consumer map (relating exactly to given LOC TAB number and version)

Drawing

pros

  • relatively simple structure of location reference
  • Historical location (based on older version of predefined locations) are sometime usable

cons

  • encoding and decoding process is not simple
  • inexact description of the location (decoded location is often larger)
  • some locations cannot be described (if they are not in predefined location set)
  • all participants must use exactly the same version of LOC TAB and related LINK information to their map
  • if some map vendor does not provide LINK data for used LOC TAB version on time, consumer cannot decode any location

Predefined location set location referencing is not suitable for internal description of all locations in the system, as it often fails to describe some locations or describes them inexactly.

On the other hand ALERT-C location table location referencing is most popular at commercial consumers, who do not have to purchase map of the provider. The costs of this is that some (mostly less important) locations and events cannot be decoded.

Taking into account, that map vendors release maps at different pace and that LINK data are provided with some delay, fully coordinated map updates at all parties is always delayed few month.

Dynamic location referencing

Dynamic location referencing (sometime referred to as “on-the-fly”) breaks the requirement to share any map data between provider and consumer (the only requirement is that both maps are describing the same area).

The trick is, that the location reference is sort of query, which when applied to consumer map finds out the location meant be the location reference (the query can also correctly recognize, that described location cannot be described in consumer map as there are no related features present).

There multiple dynamic location referencing methods:

  • AGORA-C
  • TPEG-Loc
  • OpenLR
  • ULR

Following description is using simplified OpenLR

Encoding location:

  1. my grandma creates a location in her map as before with shared map
  2. using software (e.g. open sourced version by TomTom) she creates OpenLR location reference for it.

The location reference could look like::

  • From node: [16.9854, 52.3218]
  • To node: [17.001, 52.3112]
  • FRC: 1st class

What can be read as

  1. find a junction close to coordinates [16.9854, 52.3218]
  2. find a junction close to coordinates [17.001, 52.3112]
  3. using path-finding, find a route from first to the end node, using only 1st class roads or better
  4. (there are additional attributes, which can shorten the path, insert intermediate routing point etc.)

The correct result is either features in consumer map, representing referred location, or finding, that described location cannot be found in consumer map (it is better to tell “I do not know” than finding and old road following described highway).

Used data sets:

  • map at provider (any vendor and version)
  • map at consumer (any vendor and version)

Drawing

Regarding quality values TomTom states (and values seem to be proven by independent tests):

The TomTom implementation was tested with encoding and decoding in a TomTom environment with different maps from different versions and different vendors. The tests used line locations being covered by TMC and also on non-TMC roads. The test results cover the accuracy of the OpenLR™ method and the code size: success rates with maps from same vendor are above 98% with more than 50% error detection rates and above 93% for cross map vendor with error detection rates also above 50%. TMC road stretches show a higher success rate. The average size is 16-20 Bytes per location.

pros

  • any party can update maps at any moment
  • encoded and decoded locations are very precise
  • Historical locations can be decoded at any time
  • 100% success rate when both parties have the same map vendor and version
  • almost 100% success rate on ALERT-C encoded (typically covering most important roads)

cons

  • encoding and decoding process is not simple (but there exists open source code for it)
  • location reference is a bit complex (not extremely)
  • locations can be in some cases misinterpreted

Do not bother your grandma with OpenLR

Each task and solution shall be done by proper person, technology and at proper time.

My grandma was real master at technology of baking cakes - pizza sized poppy seed pie was her masterpiece. I was always able to locate it very quickly and made related location reference obsolete within half an hour.

If you are a person influencing development of traffic information systems, I propose you to

  1. create inventory of your troubles related to location referencing methods
  2. evaluate options available today
  3. make some of the troubles obsolete

Comments !

PREVIOUS    NEXT