Automatic Route Planner (ARP)

from Robin in January 2008: This VERY old page may provide some interesting, if not useful, background. Please see Open letter to digital map data suppliers for more recent developments in ARP applied to GPSS. You are welcome to contact me.

from 1400 Monday 16th November 1998 UK Time ...

This page is for those working closely with Robin in creation of Open solutions for Automatic Route Planning (ARP) capable of being used with GPSS.

What is an ARP ?

A good example of an Automatic Route Planner (ARP) is Microsoft's Autoroute. Other examples include Route66. These programs are normally run 'on the desk' to plan the best route to take on a journey. The user enters his Start and End destination, and the program calculates the optimum route, based normally on minimum time or distance travelled.

This type of facility has been included within Car Navigation systems for several years, but availability of suitable map data has delayed widespread use outside Japan.

For an ARP to be of practical use in car navigation, it needs to have far more detailed data than that normally found with products such as Autoroute. i.e. it is not sufficient to hold major roads and junctions between towns: it needs to hold every street that the car might need to use within a large city. This is a large quantity of data. Provision of this data, for a particular country or city, is far more difficult than provision of suitable ARP software. Also, the ARP software must be designed to hold the required data in a form suitable to process it quickly.

What is 'Link & Node' Data ?

The data needed to support an ARP is often described as 'link & node' data. This is because it simplifies the mapping of a country or city into a list of 'nodes' (locations of junctions between roads) and a list of 'links' (sections of road).

The important information about a node is its position (e.g. latitude & longitude). Other information held might include the type of feature (e.g. crossroads).

The important information about a link is the two nodes it connects. Note that most roads are two-way, and so there are two links. Other information might include the length of the section of road, and it's category - used to calculate the speed that can be travelled along it. The ARP will use this data when calculating the optimum route between two nodes.

How can GPSS use an ARP ?

GPSS can be used 'on the road' to guide you to your destination without an ARP. The most basic method is simply telling you repeatedly where the destination is relative to where you are, and the direction you are moving.

GPSS can also use a route that you have entered, to guide you between waypoints along the route - as a pilot might follow a Flight Plan.

GPSS can also use 'Route Guidance Instructions' that have been prepared offline, providing guidance to reach a destination from anywhere.

An ARP can be used in many ways, including offline, to calculate the data needed for these Route Guidance Instructions.

However, this page is concerned with an ARP capable of being used by GPSS, running 'on the road'. GPSS automatically asks for a route calculation to be performed by the ARP, and the ARP provides this route back to GPSS. GPSS then uses this route data to give instructions to the driver such as,
"at the crossroads ahead, turn left onto the B3020 towards Sunninghill"

ARP - GPSS Interface

A simple use of the DOS/Windows file system permits the ARP to be written in any programming language as either a DOS or Windows Application.

Facilities are provided within GPSS to pass a request to the ARP, and to receive the optimum route data calculated by the ARP.

Facilities are also provided in GPSS to assist testing of the ARP. These include LINKMAN, used to create link and node data by clicking on GPSS maps. GPSS test facilities are also provided to request the ARP via the keyboard.

When operated 'on the road', GPSS will normally request the ARP to calculate a route, based on the car having moved a particular distance along the route or away from the current planned route.

GPSS does this by:
1. writing the car (GPS) location, and destination location into ARPINPUT.TXT
2. writing a 'flag file' ARPLEASE.TXT to Request APR work.

The ARP will then process the request, including reading the ARPINPUT.TXT data, then deleting ARPLEASE.TXT, using its own Link & Node data, and outputting the route as a GPSS.ROO (route) and/or GPSS.RGI (Route Guidance Instruction) file. When it has written the optimum route data, it creates ARPDONE.TXT to indicate the work is done.

GPSS.EXE sees the appearance of ARPDONE.TXT, reads the GPSS.ROO or RGI data, then deletes ARPDONE.TXT.

Note that there are several ways in which different ARP designs can interact with GPSS. Changes are often made within GPSS to accomodate these designs. Other (optional) features include GPSS monitoring the ARP progress and/or the ARP displaying information - particularly when being tested with new data.

Sample Link & Node data, ARP source code

Robin is currently releasing data and software to assist those working on ARP solutions capable of being used with GPSS. To obtain samples of data, access to GPSS LINKMAN facilities, or source code of ARP algorithms, contact Robin. He will ask you to download GPSS and answer what 'Quiz Free Registration' questions you can - even if you do not have a GPS receiver. This data is only supplied to those who really intend to work on a ARP-GPSS solution.

LINKMAN facility in GPSS

Version 4.9h and later of GPSS.EXE includes a facility called LINKMAN. This is a very simple and austere means of creating Link and Node data by clicking on detailed maps. Here is a very brief explanation of use:

Run GPSS, select the required background map, and start LINKMAN by entering
`linkman
a small form will appear with a text field already holding J and 3 buttons:
NODES VALUE and OUTPUT
between NODES and VALUE is another text field with 25 in it.

To create nodes, simply click on the map. If you wish to label the node with a category such as JR=roundabout from GPSS.CAT, change J to JR before you click. Clicking on the map will append lines of data into NODES.TXT in the following format:
51.421290 -000.708866,J

to create links between nodes, first switch over to 'Link Entry Mode' by clicking on the NODES button. It will switch to LINKS and the text field J will switch to
,2,R,another road
This means 2 = two way road, R = road from GPSS.CAT, name of road.

To create a link, first choose the start point by pointing at a node, then clicking with the left mouse button. Then point to the end node and click with the right mouse button. Link data will be added to file LINKS.TXT:
51.412240 -000.710702,51.412060 -000.707256,2,R,A329 London Rd

To output the Link and Node data you have a choice of two formats.
The VALUE button selects format and toggles between VALUE and INDEX.
INDEX is the preferred format used by Robin for the 'Freeware' ARP.EXE and is output in a file called NODELINK.TXT which copies data from NODES.TXT and LINKS.TXT. VALUE outputs in the LINKNODE.TXT format. One of these files is written when you click on OUTPUT.

It must be stressed that LINKMAN is a very rudimetary facility - but as with many things - it is better than nothing :-)

Original Request For Proposal (RFP)

Robin put an RFP onto this web site in July 1997, in the hope that a suitable solution would be provided from a company already doing this type of software. Since no suitable product was found, Robin has decided to release source code into the Public Domain, to accelerate suitable ARP products being created.
You may see the original RFP by clicking here.