doc/html/readme.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<HTML>

<!--
 Routino documentation - algorithm

 Part of the Routino routing software.

 This file Copyright 2008-2011 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see http://www.gnu.org/licenses/.
-->

<HEAD>
<TITLE>Routino : Software</TITLE>
<META http-equiv="Content-Type" content="text/html; charset=UTF-8">
<LINK href="style.css" type="text/css" rel="stylesheet">
</HEAD>

<BODY>

<!-- Header Start -->

<div class="header" align="center">

<h1>Routino : Software</h1>

<hr>
</div>

<!-- Header End -->

<!-- Content Start -->

<div class="content">

<h2><a name="H_1_1" title="Introduction"></a>Routino Introduction</h2>

Routino is an application for finding a route between two points using the
dataset of topographical information collected by
<a class="ext" title="OpenStreetMap" href="http://www.openstreetmap.org/">http://www.OpenStreetMap.org</a>.

<p>

Starting from the raw OpenStreetMap data (in the form of the '.osm' XML files
available on the internet) a custom database is generated that contains the
information useful for routing.  With this database and two points specified by
latitude and longitude an optimum route (either shortest or quickest) is
determined.  The route is calculated for OpenStreetMap highways (roads, paths
etc) using one of the common forms of transport defined in OpenStreetMap (foot,
bicycle, horse, motorcar, motorbike etc).

<p>

When processing the OpenStreetMap data the types of highways are recorded and
these set default limits on the types of traffic allowed.  More specific
information about permissions for different types of transport are also recorded
as are maximum speed limits.  Further restrictions like one-way streets, weight,
height, width and length limits are also included where specified. Additionally
a set of properties of each highway are also recorded.  The processing of the
input file is controlled by a configuration file which determines the
information that is used.

<p>

When calculating a route the type of transport to be used is taken into account
to ensure that the known restrictions are followed.  Each of the different
highway types can further be allowed or disallowed depending on preferences.
For each type of highway a default speed limit is defined (although the actual
speed used will be the lowest of the default and any specified in the original
data).  To make use of the information about restrictions the weight, height,
width and length of the transport can also be specified.  Further preferences
about road properties (e.g. paved or not) can also be selected.  The simplest
type of turn restrictions (those formed from an initial way, a node and a second
way) are also obeyed.

<p>

The result of calculating the route can be presented in several different ways.
An HTML file can be produced that contains a description of the route to take
with instructions for each of the important junctions.  The contents of the file
are created based on a set of translations specified in a configuration file.
The route is also available in a
<a class="ext" title="GPX format" href="http://www.topografix.com/gpx.asp">GPX (GPS eXchange) XML format</a>.
format file containing either every point and highway segment (a track file) or
just a waypoint and translated instructions for the important junctions (a route
file).
Additionally there are two plain text files that contain all data points or just
the important ones (intended for debugging and further processing).

<p>

One of the design aims of Routino was to make the software are flexible as
possible in selecting routing preferences but also have a sensible set of
default values.  Another design aim was that finding the optimum route should be
very fast and most of the speed increases come from the carefully chosen and
optimised data format.


<h2><a name="H_1_2"></a>Disclaimer</h2>

The route that is calculated by this software is only as good as the input data.

<p>

Routino comes with ABSOLUTELY NO WARRANTY for the software itself or the route
that is calculated by it.


<h2><a name="H_1_3"></a>Demonstration</h2>

A live demonstration of the router for the UK is available on the internet:
<br>
<a title="Routino demo" href="http://www.routino.org/uk/">http://www.routino.org/uk/</a>

<p>

The source code download available below also includes a set of files that can
be used to create your own interactive map.

<p>

The interactive map is made possible by use of the OpenLayers Javascript
library from <a class="ext" href="http://www.openlayers.org" title="OpenLayers">http://www.openlayers.org/</a>.


<h2><a name="H_1_4"></a>Documentation</h2>

A full set of
<a href="index.html" title="Documentation">documentation</a>
is available that describes how to install and use the programs as well as
what should go in the configuration files and how it works.


<h2><a name="H_1_5"></a>Status</h2>

Version 1.0 of Routino was released on 8th April 2009.
<br>
Version 1.1 of Routino was released on 13th June 2009.
<br>
Version 1.2 of Routino was released on 21st October 2009.
<br>
Version 1.3 of Routino was released on 21st January 2010.
<br>
Version 1.4 of Routino was released on 31st May 2010.
<br>
Version 1.4.1 of Routino was released on 10th July 2010.
<br>
Version 1.5 of Routino was released on 30th October 2010.
<br>
Version 1.5.1 of Routino was released on 13th November 2010.
<br>
Version 2.0 of Routino was released on 30th May 2011.
<br>
Version 2.0.1 of Routino was released on 7th June 2011.
<br>
Version 2.0.2 of Routino was released on 26th June 2011.
<br>
Version 2.0.3 of Routino was released on 4th August 2011.

<p>

The full version history is available in the NEWS file.


<h3><a name="H_1_5_1" title="Changes"></a>Changes in Version 2.0</h3>

<dl>
  <dt>Bug fixes:
  <dd>Fix mis-spelling with surface=asphalt tag
  <br>Routes between two waypoints on the same segment now work.
  <br>Fix reading of numeric entities from XML files (store as UTF-8 internally).
  <br>Fix turn description in HTML file (angles were biased to the right).
  <br>Fix possibility of occasionally missing turn information from output files.

  <dt>Test cases:
  <dd>Added test cases for routing in slim and non-slim modes.

  <dt>Documentation:
  <dd>Update documentation to reflect changes in program usage and function.
  <br>Install the license file in the documentation directory.

  <dt>OSM tagging
  <dd>Process the tags associated with turn restriction relations.
  <br>Remove the roundabout type from the parsing.
  <br>Add parsing of mini-roundabouts.

  <dt>Configuration Files:
  <dd>Update profiles with new options related to turn restrictions.

  <dt>Web pages:
  <dd>Change to OpenLayers v2.10.
  <br>Visualiser can display turn restrictions.
  <br>Put the profile information into separate files and auto-generate them.

  <dt>planetsplitter:
  <dd>Store information about turn restriction relations.
  <br>Quite a large code re-organisation - now faster and uses less memory.

  <dt>router:
  <dd>Take turn restriction relations into account when routing.
  <br>Continue same direction of travel at each waypoint.
  <br>Add a new option to specify an initial direction to start travel.

  <dt>filedumper:
  <dd>Print out statistics about what highways are included in the database.
</dl>

<h4><a name="H_1_5_1_1"></a>Changes in Version 2.0.1</h4>

<dl>
  <dt>Bug fixes:
  <dd>Turn relations that specify missing nodes/ways are deleted (don't crash).
  <br>Shorten the messages printed by planetsplitter to keep below 80 characters.

  <dt>Code improvements
  <dd>Various code tidy-ups and 32/64 bit node and index improvements.

  <dt>OSM tagging
  <dd>Check whether node/way/relation IDs fit in 32-bits (code ready for 64-bits).
</dl>

<h4><a name="H_1_5_1_2"></a>Changes in Version 2.0.2</h4>

<dl>
  <dt>Bug fixes:
  <dd>Fix error with handling ferry routes (were ignored).
  <br>Force roundabouts to be one-way (was present in v1.5.1).
  <br>Handle super-nodes with no segments when processing (don't crash).

  <dt>Code improvements
  <dd>Use C99 standard by default and fix related warnings.
  <br>More code tidy-up for 32/64 bit node and index types.
  <br>Free some memory in various places (not serious leaks).
</dl>

<h4><a name="H_1_5_1_3"></a>Changes in Version 2.0.3</h4>

<dl>
  <dt>Bug fixes:
  <dd>Handle start node being a super-node with no previous segment (don't crash).
  <br>Make stricter checks against the profile when finding the closest segment.
  <br>Find a valid route if the start and end point are the same location.
  <br>Choose the better route if one with and one without super-nodes are available.
</dl>


<h3><a name="H_1_5_2"></a>License</h3>

This program is free software: you can redistribute it and/or modify it under
the terms of the
<a class="ext" title="Affero GPLv3" href="http://www.fsf.org/licensing/licenses/agpl-3.0.html">GNU Affero General Public License</a>
as published by the Free Software Foundation; either version 3 of the License,
or (at your option) any later version.

<p>

It is important to note that for this program I have decided to use the
<em>Affero GPLv3</em> instead of just using the GPL.  This license adds
additional requirements to anybody who provides a networked service using this
software.


<h3><a name="H_1_5_3"></a>Copyright</h3>

Routino is copyright Andrew M. Bishop 2008-2011.


<h2><a name="H_1_6"></a>Download</h2>

The <a title="Download directory" href="http://www.routino.org/download/">download directory</a>
contains the latest version of the source code.


</div>

<!-- Content End -->

<!-- Footer Start -->

<div class="footer" align="center">
<hr>

<address>
&copy; Andrew M. Bishop = &lt;amb "at" gedanken.demon.co.uk&gt;
</address>

</div>

<!-- Footer End -->

</BODY>

</HTML>
1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
2	<HTML>
3
4	<!--
5	Routino documentation - algorithm
6
7	Part of the Routino routing software.
8
9	This file Copyright 2008-2011 Andrew M. Bishop
10
11	This program is free software: you can redistribute it and/or modify
12	it under the terms of the GNU Affero General Public License as published by
13	the Free Software Foundation, either version 3 of the License, or
14	(at your option) any later version.
15
16	This program is distributed in the hope that it will be useful,
17	but WITHOUT ANY WARRANTY; without even the implied warranty of
18	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19	GNU Affero General Public License for more details.
20
21	You should have received a copy of the GNU Affero General Public License
22	along with this program. If not, see http://www.gnu.org/licenses/.
23	-->
24
25	<HEAD>
26	<TITLE>Routino : Software</TITLE>
27	<META http-equiv="Content-Type" content="text/html; charset=UTF-8">
28	<LINK href="style.css" type="text/css" rel="stylesheet">
29	</HEAD>
30
31	<BODY>
32
33	<!-- Header Start -->
34
35	<div class="header" align="center">
36
37	<h1>Routino : Software</h1>
38
39	<hr>
40	</div>
41
42	<!-- Header End -->
43
44	<!-- Content Start -->
45
46	<div class="content">
47
48	<h2><a name="H_1_1" title="Introduction"></a>Routino Introduction</h2>
49
50	Routino is an application for finding a route between two points using the
51	dataset of topographical information collected by
52	<a class="ext" title="OpenStreetMap" href="http://www.openstreetmap.org/">http://www.OpenStreetMap.org</a>.
53
54	<p>
55
56	Starting from the raw OpenStreetMap data (in the form of the '.osm' XML files
57	available on the internet) a custom database is generated that contains the
58	information useful for routing. With this database and two points specified by
59	latitude and longitude an optimum route (either shortest or quickest) is
60	determined. The route is calculated for OpenStreetMap highways (roads, paths
61	etc) using one of the common forms of transport defined in OpenStreetMap (foot,
62	bicycle, horse, motorcar, motorbike etc).
63
64	<p>
65
66	When processing the OpenStreetMap data the types of highways are recorded and
67	these set default limits on the types of traffic allowed. More specific
68	information about permissions for different types of transport are also recorded
69	as are maximum speed limits. Further restrictions like one-way streets, weight,
70	height, width and length limits are also included where specified. Additionally
71	a set of properties of each highway are also recorded. The processing of the
72	input file is controlled by a configuration file which determines the
73	information that is used.
74
75	<p>
76
77	When calculating a route the type of transport to be used is taken into account
78	to ensure that the known restrictions are followed. Each of the different
79	highway types can further be allowed or disallowed depending on preferences.
80	For each type of highway a default speed limit is defined (although the actual
81	speed used will be the lowest of the default and any specified in the original
82	data). To make use of the information about restrictions the weight, height,
83	width and length of the transport can also be specified. Further preferences
84	about road properties (e.g. paved or not) can also be selected. The simplest
85	type of turn restrictions (those formed from an initial way, a node and a second
86	way) are also obeyed.
87
88	<p>
89
90	The result of calculating the route can be presented in several different ways.
91	An HTML file can be produced that contains a description of the route to take
92	with instructions for each of the important junctions. The contents of the file
93	are created based on a set of translations specified in a configuration file.
94	The route is also available in a
95	<a class="ext" title="GPX format" href="http://www.topografix.com/gpx.asp">GPX (GPS eXchange) XML format</a>.
96	format file containing either every point and highway segment (a track file) or
97	just a waypoint and translated instructions for the important junctions (a route
98	file).
99	Additionally there are two plain text files that contain all data points or just
100	the important ones (intended for debugging and further processing).
101
102	<p>
103
104	One of the design aims of Routino was to make the software are flexible as
105	possible in selecting routing preferences but also have a sensible set of
106	default values. Another design aim was that finding the optimum route should be
107	very fast and most of the speed increases come from the carefully chosen and
108	optimised data format.
109
110
111	<h2><a name="H_1_2"></a>Disclaimer</h2>
112
113	The route that is calculated by this software is only as good as the input data.
114
115	<p>
116
117	Routino comes with ABSOLUTELY NO WARRANTY for the software itself or the route
118	that is calculated by it.
119
120
121	<h2><a name="H_1_3"></a>Demonstration</h2>
122
123	A live demonstration of the router for the UK is available on the internet:
124	<br>
125	<a title="Routino demo" href="http://www.routino.org/uk/">http://www.routino.org/uk/</a>
126
127	<p>
128
129	The source code download available below also includes a set of files that can
130	be used to create your own interactive map.
131
132	<p>
133
134	The interactive map is made possible by use of the OpenLayers Javascript
135	library from <a class="ext" href="http://www.openlayers.org" title="OpenLayers">http://www.openlayers.org/</a>.
136
137
138	<h2><a name="H_1_4"></a>Documentation</h2>
139
140	A full set of
141	<a href="index.html" title="Documentation">documentation</a>
142	is available that describes how to install and use the programs as well as
143	what should go in the configuration files and how it works.
144
145
146	<h2><a name="H_1_5"></a>Status</h2>
147
148	Version 1.0 of Routino was released on 8th April 2009.
149	<br>
150	Version 1.1 of Routino was released on 13th June 2009.
151	<br>
152	Version 1.2 of Routino was released on 21st October 2009.
153	<br>
154	Version 1.3 of Routino was released on 21st January 2010.
155	<br>
156	Version 1.4 of Routino was released on 31st May 2010.
157	<br>
158	Version 1.4.1 of Routino was released on 10th July 2010.
159	<br>
160	Version 1.5 of Routino was released on 30th October 2010.
161	<br>
162	Version 1.5.1 of Routino was released on 13th November 2010.
163	<br>
164	Version 2.0 of Routino was released on 30th May 2011.
165	<br>
166	Version 2.0.1 of Routino was released on 7th June 2011.
167	<br>
168	Version 2.0.2 of Routino was released on 26th June 2011.
169	<br>
170	Version 2.0.3 of Routino was released on 4th August 2011.
171
172	<p>
173
174	The full version history is available in the NEWS file.
175
176
177	<h3><a name="H_1_5_1" title="Changes"></a>Changes in Version 2.0</h3>
178
179	<dl>
180	<dt>Bug fixes:
181	<dd>Fix mis-spelling with surface=asphalt tag
182	<br>Routes between two waypoints on the same segment now work.
183	<br>Fix reading of numeric entities from XML files (store as UTF-8 internally).
184	<br>Fix turn description in HTML file (angles were biased to the right).
185	<br>Fix possibility of occasionally missing turn information from output files.
186
187	<dt>Test cases:
188	<dd>Added test cases for routing in slim and non-slim modes.
189
190	<dt>Documentation:
191	<dd>Update documentation to reflect changes in program usage and function.
192	<br>Install the license file in the documentation directory.
193
194	<dt>OSM tagging
195	<dd>Process the tags associated with turn restriction relations.
196	<br>Remove the roundabout type from the parsing.
197	<br>Add parsing of mini-roundabouts.
198
199	<dt>Configuration Files:
200	<dd>Update profiles with new options related to turn restrictions.
201
202	<dt>Web pages:
203	<dd>Change to OpenLayers v2.10.
204	<br>Visualiser can display turn restrictions.
205	<br>Put the profile information into separate files and auto-generate them.
206
207	<dt>planetsplitter:
208	<dd>Store information about turn restriction relations.
209	<br>Quite a large code re-organisation - now faster and uses less memory.
210
211	<dt>router:
212	<dd>Take turn restriction relations into account when routing.
213	<br>Continue same direction of travel at each waypoint.
214	<br>Add a new option to specify an initial direction to start travel.
215
216	<dt>filedumper:
217	<dd>Print out statistics about what highways are included in the database.
218	</dl>
219
220	<h4><a name="H_1_5_1_1"></a>Changes in Version 2.0.1</h4>
221
222	<dl>
223	<dt>Bug fixes:
224	<dd>Turn relations that specify missing nodes/ways are deleted (don't crash).
225	<br>Shorten the messages printed by planetsplitter to keep below 80 characters.
226
227	<dt>Code improvements
228	<dd>Various code tidy-ups and 32/64 bit node and index improvements.
229
230	<dt>OSM tagging
231	<dd>Check whether node/way/relation IDs fit in 32-bits (code ready for 64-bits).
232	</dl>
233
234	<h4><a name="H_1_5_1_2"></a>Changes in Version 2.0.2</h4>
235
236	<dl>
237	<dt>Bug fixes:
238	<dd>Fix error with handling ferry routes (were ignored).
239	<br>Force roundabouts to be one-way (was present in v1.5.1).
240	<br>Handle super-nodes with no segments when processing (don't crash).
241
242	<dt>Code improvements
243	<dd>Use C99 standard by default and fix related warnings.
244	<br>More code tidy-up for 32/64 bit node and index types.
245	<br>Free some memory in various places (not serious leaks).
246	</dl>
247
248	<h4><a name="H_1_5_1_3"></a>Changes in Version 2.0.3</h4>
249
250	<dl>
251	<dt>Bug fixes:
252	<dd>Handle start node being a super-node with no previous segment (don't crash).
253	<br>Make stricter checks against the profile when finding the closest segment.
254	<br>Find a valid route if the start and end point are the same location.
255	<br>Choose the better route if one with and one without super-nodes are available.
256	</dl>
257
258
259	<h3><a name="H_1_5_2"></a>License</h3>
260
261	This program is free software: you can redistribute it and/or modify it under
262	the terms of the
263	<a class="ext" title="Affero GPLv3" href="http://www.fsf.org/licensing/licenses/agpl-3.0.html">GNU Affero General Public License</a>
264	as published by the Free Software Foundation; either version 3 of the License,
265	or (at your option) any later version.
266
267	<p>
268
269	It is important to note that for this program I have decided to use the
270	<em>Affero GPLv3</em> instead of just using the GPL. This license adds
271	additional requirements to anybody who provides a networked service using this
272	software.
273
274
275	<h3><a name="H_1_5_3"></a>Copyright</h3>
276
277	Routino is copyright Andrew M. Bishop 2008-2011.
278
279
280	<h2><a name="H_1_6"></a>Download</h2>
281
282	The <a title="Download directory" href="http://www.routino.org/download/">download directory</a>
283	contains the latest version of the source code.
284
285
286	</div>
287
288	<!-- Content End -->
289
290	<!-- Footer Start -->
291
292	<div class="footer" align="center">
293	<hr>
294
295	<address>
296	© Andrew M. Bishop = <amb "at" gedanken.demon.co.uk>
297	</address>
298
299	</div>
300
301	<!-- Footer End -->
302
303	</BODY>
304
305	</HTML>