<a
<h1>Table of Contents</h1>
1 - <a href="#intro">Introduction</a><br>
2 - <a href="#sample">The sample/test DB</a><br>
3 - <a href="#create">Creating VirtualRouting Tables</a><br>
4 - <a href="#from_to">Solving classic Shortest Path problems</a><br>
5 - <a href="#multi">Solving multi-destination Shortest Path problems</a><br>
6 - <a href="#tsp">Solving TSP (traveling salesman) problems</a><br>
<br><hr>
<h1><a name="intro">1 -
Previous versions of SpatiaLite traditionally supported a <b>pure SQL routing module</b> that was named <a
Since version <b>5.0.0</b> a brand new <b>routing module</b> (more advanced and sophisticated) is available, that is called <b>VirtualRouting</b>.<br>
The now obsolete <b>VirtualNetwork</b> is still supported by version <b>5.0.0</b> so as to not cause an abrupt break to already existing applications, but will presumably be discontinued in future versions.<br>
Using <b>VirtualRouting</b> instead of <b>VirtualNetwirk</b> is warmly recommended for any new development.
<h2>Theoretical foundations - an ultra-quick recall</h2>
All <b>Routing algorithms</b> (<i>aka</i> <b>Shortest Path</b> algorithms) are based on the mathematics of the <a theory</a> or to be more precise: on <b>Weighted Graphs</b>.
<br>
<img alt="network">
<br>
A topologically valid <b>Network</b> is a dataset that fulfills the following requirements:
<ul>
<li>All items in the dataset are called <b>Links</b> (<i>aka</i> <b>Arcs</b>), and are expected to represent some oriented connection joining two <b>Nodes</b>.<br>
<u>Example</u>: in the above figure Link <b>L3</b> connects Nodes <b>N2</b> and
<li>So all <b>Links</b> are always expected to explicitly reference a <b>Start-Node</b> (<i>aka</i> <b>Node-From</b>) and an <b>End-Node</b> (<i>aka</i> <b>Node-To</b>).
<ul>
<li>Links are always <b>oriented</b>, and their natural direction is <b>From-To</b>:
<ul>
<li>in an <b>unidirectional</b> Network each Link is an <b>one-way</b> connection.<br>
If the connection is available in the opposite direction a second Link must be explicitly declared.<br>
<u>Example</u>: Link <b>X1</b> goes from Node <b>A</b> to Node <b>B</b>, and Link <b>X2</b> goes from Node <b>B</b> to Node
<li>in a <b>bidirectional</b> Network all Links are assumed to establish a connection in both directions.<br>
Definiting an <b>one-way connection</b> requires an appropriate attribute to be set (see below).</li>

<li>The <b>Start-</b> and <b>End-Node</b> could eventually be the same, and in this case we'll have a <b>self-closed</b> Link.</li>
<li>Network's Links <b>can</b> eventually define a linear Geometry (<b>LINESTRING</b>) going from the <b>Start-Node</b> to the <b>End-Node</b>, but this is an optional feature, not a mandatory requirement.</li>
<li>What is absolutely mandatory is that each <b>Link</b> must explicitly reference its

<li>A Network supporting Geometries is a <b>Spatial Network</b>; otherwise a Network lacking any Geometry is a <b>Logical Network</b>.
<ul>
<li>In a <b>Spatial Network</b> all Links <b>must</b> have a corresponding Geometry.</li>
<li>In a <b>Logical Network</b> all Links <b>are strictly forbidden</b> to have any Geometry.</li>
<li>In a <b>Spatial Network</b> both the <b>StartPoint</b> and <b>EndPoint</b> of each Link's <b>LINESTRING</b> are always expected to exactly coincide with the corresponding

<li>In a <b>Spatial Network</b> all references to the same <b>Node</b> by different Links <b>must</b> be an exact match.<br>
<u>Example</u>: Node <b>N5</b> is shared by Links <b>L3</b>, <b>L6</b>, <b>L7</b>, <b>L9</b> and <b>L10</b>, so all their corresponding LINESTRINGS are expected to have the corresponding extremity (<b>Start-</b> or <b>End-</b>, depending on the orientation) points that must exactly match the other.<br>
A <b>topological inconsistency</b> exists if any of these conditions are not satisfied, which leads to an <b>invalid</b> Network.</li>
<li>In a <b>Spatial Network</b> two
<li>Accordingly to the above premises, <b>Nodes</b> are never expected to be explicitly declared in a separate Table.<br>
Just a single Table declaring all <b>Links</b> is required in order to fully define a topologically valid Network.<br>
All the Nodes can then be easily extracted from the Links' definitions and the coordinates for each Node can be directly set by extracting the extreme Point of the corresponding Linestrings.<br>
If any mismatch is detected this surely means that the Network is invalid.</li>
<li>A <b>Link</b> may legitimately self-intersect itself (e.g. forming a loop), as shown in the above figure by Link <b>L15</b> (orange spot).</li>
<li>Two <b>Links</b> may legitimately intersect where no Node exists, as exemplified on the above figure by Links <b>L4</b> and <b>L7</b> (green spot).<br>
This usually happens when one of the two Links overpasses the other, or where some technical restriction exists (e.g. two insulated wires in an Electrical Network).</li>
<li><b>Links</b> aren't strictly required to be associated with any specific attribute, but the following attributes are almost universally supported:
<ul>
<li>a <b>name</b> identifying the Link.<br>
<u>Examples</u>: the <i>road toponym</i> in a <b>road network</b>, or the <i>river name</i> in an <b>hydrographic
<li>one (or even more) appropriate <b>cost value</b>(s).<br>
<u>Example</u>: the <i>time</i> required to traverse the Link (may be distinguished between pedestrians, bicycles, cars, lorries and so on).</li>
<li>a pair of <b>boolean flags</b> (<b>from-to</b> and <b>to-from</b>) are intendend to specify if the Link can be traversed on both directions or just in one

</ul>
<h4>Logical conclusions</h4>
Any topologically valid <b>Network</b> (irrespective of whether it is a <b>Spatial</b> or <b>Logical</b> type) is a valid <b>Graph</b>.<br>
A Network allowing the support (direct or indirect) of some appropriate <b>cost value</b> is a valid <b>Weighted Graph</b>, and can consequently support <b>Routing algorithms</b>.<br>
All Routing algorithms are intended to identify the <b>Shortest Path</b> solution connecting two <b>Nodes</b> in a <b>weighted graph</b> (<i>aka</i> <b>Network</b>).<br><br>
the term <b><i>Shortest can be easily misunderstood.<br>
Due to historical reasons the most common application field for Routing algorithms is related to <b>Road Networks</b>, but also many other kinds of Networks exist:
<ul>
<li>Hydrographic Networks.</li>
<li>Gas / Water / Oil Networks.</li>
<li>Electrical Networks.</li>
<li>Telecomunication Networks.</li>
<li>Social or Economical Networks representing relationships between individuals or companies.</li>
<li>Epidemiological Networks representing the propagation of infective diseases between individuals or groups.</li>

<br>
In all the above cases we certainly have valid Networks supporting Routing algorithns, but not all of them can imply something like a <i>spatial distance</i> (<i>geometric length</i>) or a <i>travel time</i>.<br>
In the most general acception <b>costs</b> can be represented by any reasonable physical quantity.<br>
So a more generalized definition is assuming that Routing algorithms are intended to identify <b>lesser cost</b> solutions on a <b>weighted graph</b>.<br>
The exact interpretation of the involved <b>costs</b> (<i>aka</i> <b>weights</b>) strictly depends on the very specific nature of each Network.
<h3>The Dijkstra's algorithm</h3>
This well known <a isn't necessarily the fastest one, but it always ensures <b>full correctness</b>:
<ul>
<li>Any Node-to-Node connection identified by Dijkstra's is certainly ensured to be <b>optimal</b>.<br>
In other words, no connetction presenting a lower cost can conceptually exist.</li>
<li>When Dijsjtra's fails to identify a solution this surely means that no solution is possible.</li>
</ul>
<h3>The A* algorithm</h3>
Many alternative Routing algorithms have been invented during the years.<br>
All them are based on heuristic assumptions and are intended to be faster than Dijkstra's, but none of them can ensure <b>full correctness</b> as Dijkstra's does.<br>
The <a algorithm</a> applies a mild heuristic optimization, and can be a realistic alternative to Dijkstra's in many cases.<br><br>
<hr>
<h1><a name="sample>2 - The sample/test
You are expected to follow the current tutorial about <b>VirtualRouting</b> by directly testing all SQL queries discussed below on behalf of the <a DB that you can download from here</a><br><br>
The sample DB contains the full <b>road network</b> of <b>Tuscany Region (Italy)</b> (<a dataset</a>) kindly released under the <b>CC-BY-SA 4.0</b> licence terms.<br>
The contents stored into the sample database were opportunely rearranged, and are still subject to the initial <b>CC-BY-SA 4.0</b> clauses (<i>derived work</i>).
<br><br>
<ul>
<li>all road names are stored within the <b>toponyms</b> Table.<br>
the same road name could be used in different Municipalities, so the <b>toponyms</b> Table relationally references the <b>municipalities</b> Table (via <b>PRIMARY</b> / <b>FOREIGN KEY</b> relationships).</li>
<li>the <b>roads</b> Spatial Table contains about <b>380,000</b> Links, and has the following columns:
<ul>
<li><b>id</b>: unique identifier of each Link (<b>PRIMARY
<li><b>node_from</b> and <b>node_to</b>: Node identifiers.
The original dataset adopts very long an complex alphanumeric Node codes; the integer Node IDs were obtained by calling the <b>CreateRoutingNodes()</b> SQL function discussed in a following section.</li>
<li><b>id_toponym</b>: relational reference to the corresponding road name contained into the <b>toponyms</b> Table (<b>FOREIGN
<li><b>speed_kmh</b>: the estimated average speed supported by the Link, expressed in
<u>Note</u>: <b>negative</b> speeds intend a forbidden Link.</li>
<li><b>oneway_fromto</b> and <b>oneway_tofrom</b>: boolean flags intended to state if a Link can be traversed in both directions or just in a single direction (<b>one-way</b>).<br>
<u>Note</u>: all Links declaring <b>oneway_fromto=0</b> and <b>oneway_tofrom=0</b> are intended to be always forbidden.</li>
<li><b>cost</b>: the <b>time</b> expressed in <b>seconds</b> required to traverse each Link.<br>
<u>Note #1</u> all costs were calculated accordingly to the following formula: <b>cost = ((ST_Length(geom) / 1000.0) / speed_kmh) * 3600.0</b><br>
<u>Note #2</u> all <b>86,400.0</b> cost values (equivalent to 1 day) approximate an <b>infinitive cost</b> thus intending a <b>forbidden</b> Link.</li>
<li><b>geom</b>: a <b>3D Linestring</b> representing the Geometry of each Link.<br>
<u>Note</u>: the original dataset is just <b>2D</b>; elevations (<b>Z</b> coordinates) were interpolated by draping the dataset over an <a DEM (10m X 10m

<li>the <b>roads_vw</b> Spatial View is just intended to fully resolve all relational references between <b>roads</b>, <b>toponyms</b> and <b>municipalities</b>, thus allowing for easier SQL queries.</li>
<li>the <b>house_nr</b> Spatial Table contains about <b>1,480,000</b> House Numbers, and has the following columns:
<ul>
<li><b>id</b>: unique identifier of each House Number (<b>PRIMARY
<li><b>id_road</b>: relational reference to the corresponding Link contained into the <b>roads</b> Table (<b>FOREIGN
<li><b>label</b>: the textual label fully qualifying each House Number.</li>
<li><b>geom</b>: a <b>3D Point</b> representing the Geometry of each House Number.<br>
<u>Note #1</u>: also in this case all elevations (<b>Z</b> coordinates) were interpolated by draping the dataset over the same DEM as above.<br>
<u>Note #2</u>: strictly specking the House Numbers are not part of the Road Network; they are include into the sample/test database just because they'll be useful in some of the examples explained in below paragraphs.</li>

<li>the <b>house_nr_vw</b> Spatial View is just intended to fully resolve all relational references between <b>house_nr</b>, <b>roads</b>, <b>toponyms</b> and <b>municipalities</b>, thus allowing for easier SQL queries.</li>
</ul>
<br>
 <hr>
<h1><a name="create">3 - Creating VirtualRouting
All VirtualRouting queries are based on some <b>VirtualRouting Table</b>, and in turn any VirtualRouting Table is based on some appropriate <b>Binary Data Table</b> supporting an efficient representation of the underlying Network.<br>
So we'll start first by creating such tables.<br><br>
The old and now superseded <b>VirtualNetwork</b> required using a separate CLI tool (<b>spatialite_network</b>) in order to properly initialize a VirtualNetwork Table and its companion Binary Data Table;
alternatively <b>spatialite_gui</b> supported a <b>GUI wizard</b> for the same task. Since version <b>5.0.0</b> now SpatiaLite directly supports a specific <b>CreateRouting()</b> SQL function.
<verbatim>
SELECT CreateRouting('byfoot_data', 'byfoot', 'roads_vw', 'node_from', 'nodeto', 'geom', NULL);

SELECT CreateRouting_GetLastError();
------------------------------------
ToNode Column "nodeto" is not defined in the Input Table
</verbatim>
<u>Note</u>: this first query (based on the <i>reduced form</i> of <b>CreateRouting</b>) contains an intended error causing a failure and thus raising an exception.<br>
CreateRouting() can fail for multiple reasons, and by calling <b>CreateRouting_GetLastError()</b> you can easily identify the exact reason why the most recent call to CreateRouting() failed.<br>
<verbatim>
SELECT CreateRouting('byfoot_data', 'byfoot', 'roads_vw', 'node_from', 'node_to', 'geom', NULL, 'toponym', 1, 1);
-------------
1

SELECT CreateRouting_GetLastError();
------------------------------------
NULL
</verbatim>
This second attempt is finally successful, and now CreateRouting() returns <b>1</b> (<i>aka</i> <b>TRUE</b>), and as you can easily check now the Database contains two new Tables: <b>byfoot</b> and <b>byfoot_data</b>.<br>
<u>Note</u>: after a successful call to CreateRouting() <b>CreateRouting_GetLastError()</b> will always return <b>NULL</b>.<br><br>
You've just used one of the <i>partially reduced form</i> of CreateRouting(); let's see in more depth all the arguments and their meaning:
<ol>
<li><i>byfoot_data</i>: the name of the Network Binary Data Table to be created.</li>
<li><i>byfoot</i>: the name of the VirtualRouting Table to be created.</li>
<li><i>roads_vw</i>: the name of the <b>Spatial Table</b> or <b>Spatial View</b> representing the underlying Network.<br>
<u>Note</u>: in this case we actually used a Spatial View.</li>
<li><i>node_from</i>: name of the column (in the above Table or View) expected to contain <b>node-from</b> values.</li>
<li><i>node_to</i>: name of the column (in the above Table or View) expected to contain <b>node-to</b> values.</li>
<li><i>geom</i>: name of the column (in the above Table or View) expected to contain <b>Linestrings</b>.<br>
We could have legitimately passed a <b>NULL</b> value for this argument in the case of a <b>Logical
<li><i>NULL</i>: name of the column (in the above Table or View) expected to contain <b>cost</b> values.<br>
In this case we have passed a <b>NULL</b> value, and consequently the <b>cost</b> of each Link will be assumed to be represented by the <b>geometric length</b> of the corresponding Linestring.<br>
<u>Note #1</u>: in the case of Networks based on <b>longitudes</b> and <b>latitudes</b> (<i>aka</i> <b>geographic</b> Reference Systems) the geometry length of all Linestrings will be precisely <b>measured on the ellipsoid</b> by applying the most accurate <b>geodesic formulae</b> and will be consequently expressed in <b>meters</b>. In any other case (<b>projected</b> Reference Systems) lengths will be expressed in the <b>measure unit</b> defined by the Reference System (e.g. <b>meters</b> for <b>UTM</b> projections and <b>feet</b> for <b>NAD-ft</b> projections).<br>
<u>Note #2</u>: the <b>geom-column</b> and <b>cost-column</b> arguments are never allowed to be <b>NULL</b> at the same time.</li>
<li><i>toponym</i>: name of the column (in the above Table or View) expected to contain <b>road-name</b> values.<br>
It could be legitimately set to <b>NULL</b> if all Links are anonymous.</li>
<li><i>1</i>: a boolean flag intended to specify if the Network must support the <b>A* algorithm</b> or not (set to <b>TRUE</b> by default).</li>
<li><i>1</i>: a boolean flag intended to specify if all Network's Links are assumed to be <b>bidirectional</b> or not (assumed to be <b>TRUE</b> by default).</li>
</ol>
<table bgcolor="#c0ffc0" cellspacing="10" cellpadding="6"><tr><td>
<h3>Technical note</h3>
The internal encoding adopted by the <b>Binary Data Table</b> is unchanged and is the same for both <b>VirtualNetwok</b> and <b>VirtualRouting</b>.<br>
You can safely base a <b>VirtualRouting Table</b> on any existing Binary Data
Table created by the <b>spatialite-network</b> CLI tool, exactly as you can base a <b>VirtualNetwork Table</b> on any Binary Data Table created by the <b>CreateRouting()</b> SQL function.
<verbatim>
CREATE VIRTUAL TABLE test_network USING VirtualNetwork('some_data_table');

CREATE VIRTUAL TABLE test_routing USING VirtualRouting('some_data_table');
</verbatim>
In order to manually create your Virtual Tables you just have to execute an appropriate <b>CREATE VIRTUAL TABLE ... USING Virtual... (...)</b> statement.
<h4>Warning</h4>
In the case of <b>Spatial Networks</b> based on any <b>geographic</b> Reference System (using <b>longitudes</b> and <b>latitudes</b>) there is an important difference between Binary Data Tables created by the <b>spatialite_network</b> GUI tool and  Binary Data Tables created by the <b>CreateRouting()</b> SQL function when <b>costs</b> are implicitly based on the geometric length of the Link's Linestring:
<ul>
<li>the <b>spatialite_network</b> CLI tool (and the <b>GUI wizard</b> implemented by previous versions of <b>spatialite_gui</b>) compute the Linestring's length as an <b>angular distance</b> expressed in
<li>the <b>CreateRouting()</b> SQL function computes the Linestring's length as a <b>linear distance</b> expressed in <b>metres</b> by applying the most accurate <b>geodesic formulae</b> on the ellipsoid.</li>
</ul>

<verbatim>
SELECT CreateRouting('bycar_data', 'bycar', 'roads_vw', 'node_from', 'node_to', 'geom', 'cost', 'toponym', 1, 1, 'oneway_fromto', 'oneway_tofrom', 0);
--------------------
1
</verbatim>
After calling yet another time <b>CreateRouting()</b> now the Database contains two further Tables: <b>bycar</b> and <b>bycar_data</b>.<br>
This time you've used the <i>complete form</i> of CreateRouting(); let's see in more depth all the arguments and their meaning:
<ol>
<li><i>bycar_data</i>: same as above.</li>
<li><i>bycar</i>: same as above.</li>
<li><i>roads_vw</i>: same as above.</li>
<li><i>node_from</i>: same as above.</li>
<li><i>node_to</i>: same as above.</li>
<li><i>geom</i>: same as above.</li>
<li><i>cost</i>: same as above.
In this case we have referenced a column preloaded with values corresponding to the <b>time</b> measured in <b>seconds</b> required to traverse each Link.</li>
<li><i>toponym</i>: same as above.</li>
<li><i>1</i>: same as above (<i>A*
<li><i>1</i>: same as above (<i>bidirectional
<li><i>oneway_fromto</i>: name of the column (in the above Table or View) expected to contain boolean flags specifying if each Link can be traversed in the <b>from-to</b> direction or not.</li>
<li><i>oneway_tofrom</i>: name of the column (in the above Table or View) expected to contain boolean flags specifying if each Link can be traversed in the <b>to-from</b> direction or not.<br>
<u>Note #1</u>: both <b>from-to</b> and <b>to-from</b> column names can be legitimately set as <b>NULL</b> if no <b>one-way</b> restrictions apply to the current Network.<br>
<u>Note #2</u>: Networks of the <b>unidirectional</b> type are never enabled to reference <b>one-way</b> columns (they should always be set to
<li><i>0</i>: a boolean flag intending an <b>overwrite authorization</b>.
<ul>
<li>If set to <b>FALSE</b> an exception will be raised if the <b>Binary Data Table</b> and/or the <b>VirtualRouting Table</b> do already exist.</li>
<li>If set to <b>TRUE</b> eventually existing Tables will be preventively dropped immediately before starting the execution of

</ol>
<br>
<table bgcolor="#ffffc0" cellspacing="10" cellpadding="6"><tr><td>
<h3>Highlight: where you are</h3>
You've just created two VirtualRouting Tables based on different settings; both them are perfectly valid and reasonable, but they are intended for different purposes:
<ul>
<li><b>byfoot</b> is specifically intended for <b>pedestrians</b>:
<ul>
<li>all Links are always assumed to be accessible in <b>both directions</b>; there are no <b>one-ways</b> and no <b>forbidden</b> Links.</li>
<li>the <b>cost</b> of each Link is directly represented by its geometric <b>length</b>, which is consistent with the assumption of an almost constant speed substantially immune from adverse road conditions and traffic congestion.</li>

<li><b>bycar</b> is specifically intended for <b>motor vehicles</b>:
<ul>
<li>many Links are expected to be accessible in <b>both directions</b> but others could easily be subject to <b>one-way</b> restrictions or even be completely
<li>the cost of each Link is expressed as an estimated <b>travel time</b>, because the expected speeds can greatly vary accordingly to specific road conditions, traffic congestion and legal regulations.</li>

</ul>
<br>
<u>Conclusion</u>: a single VirtualRouting Table can't be able to adequately support support the specific requirements and expectations of different users.<br>
Defining more Routing Tables with different settings for the same Network usually is a good design choice leading to more realistic results.<br>

</table>
<br><br>
<h3>Utility function for automatically setting NodeFrom and NodeTo IDs</h3>
Sometimes it could eventually happen to encounter some <b>Spatial Network</b> representation being fully topologically consistent but completely lacking any definition about <b>NodeFrom</b> and <b>NodeTo</b> identifiers.<br>
In this specific case you can successfully recover a perfectly valid Network by calling the <b>CreateRoutingNodes()</b> SQL function.
<verbatim>
SELECT CreateRoutingNodes(NULL, 'table_name', 'geom', 'node_from', 'node_to');
_________________________
1
</verbatim>
Let's examine all arguments and their meaning:
<ol>
<li><i>NULL</i>: name of the <b>Attached-DB</b> containing the Spatial Table.<br>
It can be legitimately set to <b>NULL</b>, and in this case the <b>MAIN</b> DB is assumed.</li>
<li><i>table_name</i>: name of the Spatial Table.</li>
<li><i>geom</li>: name of the column ((in the above Table) containing
<li><i>node_from</i>: name of the column to be added to the above Table and populated with appropriate <b>NodeFrom</b> IDs.</li>
<li><i>node_to</i>: name of the column to be added to the above Table and populated with appropriate <b>NodeTo</b> IDs.<br>
<u>Note</u>: both <b>NodeFrom</b> and <b>NodeTo</b> columns should not be already defined in the above Table.</li>
</ol>
<b>CreateRoutingNodes()</b> will return <b>1</b> (<i>aka</i> <b>TRUE</b>) on success; an exception will be raised on failure.<br>
<u>Note</u>: you can call <b>CreateRouting_GetLastError()</b> so to precisely identify the cause accounting for failure.<br><br><br>
<table bgcolor="#c0ffc0" cellspacing="10" cellpadding="6"><tr><td>
<h3>Handling dynamic Networks</h3>
Sometimes it happens that a Network could be subject to rather frequent changes: some new Links require to be added, obsolete Links require to be removed, other Links may assume a different Cost, one-ways could be reversed, the discipline of pedestrian areas could be modified and so on.<br>
A VirtualRouting Table is always based on a companion Binary Data Table, that is intrinsically <b>static</b>, and consequently you are required to re-create both them from time to time in order to support all recent changes affecting the underlaying Network.<br>
The optimal frequency for cyclically refreshing the Routing Tables strictly depends on specific requirements, but the two overall approaches are commonly adopted:
<ol>
<li><b>low frequency refresh</b>: best fit for slowly evolving Networks.<br>
In this case re-creating the Network Tables once a month / week / day could be reasonably enough.
Recreating the Tables from scratch usually requires several seconds (or even less, depending on the number of Links).<br>
The refresh activities could be opportunely planned at low traffic hours (e.g. during the night), and <b>CreateRouting()</b> could be usefully called by enabling the <b>overwrite</b> option.</li>
<li><b>medium-high frequency refresh</b>: best fit for quickly evolving Networks.<br>
Re-creating the Network Tables once per hour (or even more frequently) could be strictly required, and frequent <b>out of service</b> periods while waiting for the refresh process to complete could easily be unacceptable.<br>
In this case you could usefully adopt a <b>multi-threaded strategy</b>:
<ul>
<li><b>thread #1</b> (<i>the reader</i>): this first thread is intended to service any incoming Routing request. It will be always active, and will target a well known VirtualRouting Table (e.g. <b>my_routing</b> based on
<li><b>thread #2</b> (<i>the writer</i>): this second thread is just intended to re-create both Network Tables at predefined intervals, and it will sleep between an interval and the other.<br>
When this thread awakens will re-create both Network Tables by using different names, and will overwrite the standard ones just at the very end of the process (activating a semaphore during this short-timed last step is highly recommended).<br>
Something like this pseudo-code exemplifies:
<verbatim>
SELECT CreateRouting('new_my_routing_data', 'new_my_routing', ...);

--> start the semaphore so to lock the other thread

BEGIN;
DROP TABLE my_routing;
DROP TABLE my_routing_data;
SELECT CloneTable('MAIN', 'new_my_routing_data', 'my_routing_data', 0);
CREATE VIRTUAL TABLE my_routing USING VirtualRouting('my_routing_data');
DROP TABLE new_my_routing;
DROP TABLE new_my_routing_data;
COMMIT;

--> remove the semaphore
</verbatim>
<u>Note</u>: strictly respecting the above sequence of SQL operations is absolutely required.</li>

</ol>

</table>
<br>
<table bgcolor="#ffb060" cellspacing="10" cellpadding="6"><tr><td>
<h3>Warning: how to correctly drop Network Tables</h3>
When dropping a VirtualRouting Table and its companion Binary Data Table following the correct sequence of SQL commands is paramount.<br>
Failing to strictly respect the expected sequence will surely cause you several troubles and severe headaches, and will possibly lead to an irremediably corrupted database.
<ol>
<li>you are always expected to DROP first the VirtualRouting Table.</li>
<li>you can safely DROP the companion Binary Data Table only once it's no longer referenced by the VirtualRouting Table.</li>
<li>by following the reverse sequence you'll directly create an <b>orphan</b> VirtualRouting Table that cannot be accessed any longer, and that will consequently refuse to be dropped.<br>
Be warned !!</li>
</ol>

</table>
<br><br>
<hr><br>
<h1><a name="from_to">4 - Solving classic Shortest Path
The most classic Shortest Path problem requires to identify the optimal connection between an <b>Origin Node</b> and a <b>Destination Node</b>.<br>
We can easily translate such a problem into a simple SQL query targeting some VirtualRouting Table.
<verbatim>
SELECT *
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = 183286;
</verbatim>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">Algorithm</th><th bgcolor="#d0d0a0">Request</th><th bgcolor="#d0d0a0">Options</th><th bgcolor="#d0d0a0">Delimiter</th><th bgcolor="#d0d0a0">RouteId</th><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">PointFrom</th><th bgcolor="#d0d0a0">PointTo</th><th bgcolor="#d0d0a0">Tolerance</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
<tr>
<td>Dijkstra</td><td>Shortest &#91;dec=44, hex=2c&#93;</td><td align="right">0</td><td align="right">178731</td><td align="right">300.912208</td><td>BLOB sz=272
</tr>
<tr>
align="right">0</td><td align="right">224014</td><td align="right">178731</td><td PIETRO ARETINO</td>
</tr>
<tr>
align="right">0</td><td align="right">224446</td><td align="right">182885</td><td MARGARITONE</td>
</tr>
<tr>
align="right">0</td><td align="right">224414</td><td align="right">178880</td><td MARGARITONE</td>
</tr>
</table>
<br>
Let's quickly examine the resultset returned by the above Routing query:
<ul>
<li>the <b>first row</b> (<i>aka</i> header row) has a special interpretation, and is intended to summarize the travel solution as a whole.</li>
<li>all the <b>following rows</b> represent a single Link required to build the solution (optima path); Links are ordered accordingly to the travel direction connecting the Origin and the Destination.</li>
<li>columns <b>Algorithm</b>, <b>Request</b>, <b>Options</b>, <b>Delimiter</b>, <b>PointFrom</b>, <b>PointTo</b>, <b>Tolerance</b> and <b>Geometry</b> are always set to <b>NULL</b> except that in the first row of the resultset:
<ul>
<li>column <b>Algorithm</b> accounts for the Routing Algorithm used by the current query (<i>Dijkstra's</i> or
<li>column <b>Request</b> specifies the exact nature of the current query (in this specific case <i>Shortest
<li>we'll ignore for now columns <b>Options</b>, <b>Delimiter</b>, <b>PointFrom</b>, <b>PointTo</b> and <b>Tolerance</b>: their respective meanings will be explained in following paragraphs.</li>
<li>column <b>Geometry</b> contains a <b>LINESTRING</b> representation of the whole travel solution.<br>
<u>Note</u>: on <b>Logical Networks</b> (not supporting Geometries) <b>Geometry</b> will always be

<li>we'll ignore for now column <b>RouteId</b>; its meaning will be explained in following paragraphs.</li>
<li>column <b>RouteRow</b> simply is the progressive number of the row in the travel solution (always <b>0</b> in the header row).</li>
<li>column <b>Role</b> can be <i>Route</i> (header row) or <i>Link</i> (all following rows).</li>
<li>column <b>LinkRowid</b> references the <b>ROWID</b> of the corresponding Link (always set to <b>NULL</b> in the header row).</li>
<li>column <b>NodeFrom</b> and <b>NodeTo</b> have the following interpretation:
<ul>
<li>in the header row they correspond to he <b>Origin</b> and <b>Destination</b> Nodes.</li>
<li>in all the following rows they are intended to specify the direction of the current Link.</li>

<li>column <b>Cost</b> has the following interpretation:
<ul>
<li>in the header tow it corresponds to the <b>total cost</b> of the travel.</li>
<li>in all the following rows it represents the specific cost of the current Link.</li>

<li>column <b>Name</b> contains the description of the current Link (usually a road name), and is always <b>NULL</b> in the header row.<br>
<u>Note</u> it could be always be <b>NULL</b> if the VirtualRouting Table does not supports names.</li>

</ul>
<br><br>
Testing the return connection just requires swapping the Origin and the Destination; in this example you'll just request the meaningful columns:
<verbatim>
SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeTo = 178731 AND NodeFrom = 183286;
</verbatim>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
<tr>
<td align="right">183286</td><td align="right">178731</td><td align="right">300.912208</td><td>BLOB sz=272
</tr>
<tr>
<td align="right">224414</td><td align="right">183286</td><td align="right">178880</td><td MARGARITONE</td>
</tr>
<td align="right">224446</td><td align="right">178880</td><td align="right">182885</td><td MARGARITONE</td>
</tr>
<tr>
<td align="right">224014</td><td align="right">182885</td><td align="right">178731</td><td PIETRO ARETINO</td>
</tr>
</table>
<br>
If you remember, the <b>byfoot</b> VirtualRouting Table has no <b>one-ways</b>, and consequently the return path exactly corresponds to the first one, except in that all directions are now reversed.
<br><br><br>
Now you'll go to test the same connections, but this time you'll target the <b>bycar</b> VirtualRouting Table that fully supports <b>one-ways</b>:
<verbatim>
SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM bycar
WHERE NodeFrom = 178731 AND NodeTo = 183286;
</verbatim>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
<tr>
<td align="right">178731</td><td align="right">183286</td><td align="right">101.815552</td><td>BLOB sz=2032
</tr>
<tr>
<td align="right">224014</td><td align="right">178731</td><td align="right">182885</td><td PIETRO ARETINO</td>
</tr>
<tr>
<td align="right">224446</td><td align="right">182885</td><td align="right">178880</td><td MARGARITONE</td>
</tr>
<tr>
<td align="right">219171</td><td align="right">178880</td><td align="right">178732</td><td FRANCESCO CRISPI</td>
</tr>
<tr>
<td align="right">219058</td><td align="right">178732</td><td align="right">178754</td><td FRANCESCO CRISPI</td>
</tr>
<tr>
<td align="right">225888</td><td align="right">178754</td><td align="right">183461</td><td FRANCESCO CRISPI</td>
</tr>
<tr>
<td align="right">225887</td><td align="right">183461</td><td align="right">182800</td><td FRANCESCO CRISPI</td>
</tr>
<tr>
<td align="right">223935</td><td align="right">182800</td><td align="right">182799</td><td LUCA SIGNORELLI</td>
</tr>
<tr>
<td align="right">226038</td><td align="right">182799</td><td align="right">183456</td><td LUCA SIGNORELLI</td>
</tr>
<tr>
<td align="right">225832</td><td align="right">183456</td><td align="right">183444</td><td LUCA SIGNORELLI</td>
</tr>
<tr>
<td align="right">225831</td><td align="right">183444</td><td align="right">183554</td><td LUCA SIGNORELLI</td>
</tr>
<tr>
<td align="right">225765</td><td align="right">183554</td><td align="right">183954</td><td LUCA SIGNORELLI</td>
</tr>
<tr>
<td align="right">225766</td><td align="right">183954</td><td align="right">183905</td><td LUCA SIGNORELLI</td>
</tr>
<tr>
<td align="right">225979</td><td align="right">183905</td><td align="right">183626</td><td SENZA NOME</td>
</tr>
<tr>
<td align="right">224905</td><td align="right">183626</td><td align="right">183128</td><td SENZA NOME</td>
</tr>
<tr>
<td align="right">224897</td><td align="right">183128</td><td align="right">183286</td><td MARGARITONE</td>
</tr>
</table>
<verbatim>
SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM bycar
WHERE NodeTo = 178731 AND NodeFrom = 183286;
</verbatim>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
<tr>
<td align="right">183286</td><td align="right">178731</td><td align="right">103.305259</td><td>BLOB sz=944
</tr>
<tr>
<td align="right">224414</td><td align="right">183286</td><td align="right">178880</td><td MARGARITONE</td>
</tr>
<tr>
<td align="right">219171</td><td align="right">178880</td><td align="right">178732</td><td FRANCESCO CRISPI</td>
</tr>
<tr>
<td align="right">219058</td><td align="right">178732</td><td align="right">178754</td><td FRANCESCO CRISPI</td>
</tr>
<tr>
<td align="right">224538</td><td align="right">178754</td><td align="right">181972</td><td ANTONIO GUADAGNOLI</td>
</tr>
<tr>
<td align="right">222575</td><td align="right">181972</td><td align="right">181971</td><td ANTONIO GUADAGNOLI</td>
</tr>
<td align="right">224967</td><td align="right">181971</td><td align="right">182891</td><td ANTONIO GUADAGNOLI</td>
</tr>
<tr>
<td align="right">224168</td><td align="right">182891</td><td align="right">183057</td><td MACALLE'</td>
</tr>
<tr>
<td align="right">224167</td><td align="right">183057</td><td align="right">183056</td><td MACALLE'</td>
</tr>
<tr>
<td align="right">224174</td><td align="right">183056</td><td align="right">182941</td><td RODI</td>
</tr>
<tr>
<td align="right">224059</td><td align="right">182941</td><td align="right">182001</td><td RODI</td>
</tr>
<tr>
<td align="right">222637</td><td align="right">182001</td><td align="right">182000</td><td PIETRO ARETINO</td>
</tr>
<tr>
<td align="right">222636</td><td align="right">182000</td><td align="right">178731</td><td PIETRO ARETINO</td>
</tr>
</table>
<br>
As you can easily notice, the optimal paths returned by the <b>bycar</b> VirtualRouting Table the paths in opposite directions strongly differ between them, and both are completely different from the path returned by querying <b>byfoot</b>.<br>
A quick glance at the below map will surely help to understand better what's really happening.<br>
This is a central area of the town of Arezzo around the archaeological ruins of the Roman Amphitheater; circulating by car is discouraged and is subject to many one-way restrictions. Not surprisingly, moving by foot is the faster option.
<br><br>
<img alt="fig1">
<ul>
<li>yellow path: pedestrians</li>
<li>green path: car, direct direction</li>
<li>red path: car, return direction</li>
</ul>
<br>
<table bgcolor="#c0ffc0" cellspacing="10" cellpadding="6"><tr><td>
<h3>Linestrings returned by VirtualRouting</h3>
All LINESTRING Geometries created by any VirtualRouting will always contain <b>M values</b>:
<ul>
<li>if the underlaying Network's Geometries are <b>XY</b> then <b>XYM</b> Linestrings will be returned.</li>
<li>if the underlaying Network's Geometries are <b>XYZ</b> then <b>XYZM</b> Linestrings will be returned.</li>
<li>if the underlaying Network's Geometries are <b>XYM</b> or <b>XYZM</b> then  Linestrings returned into the resultset will maintain the same dimensions as in the underlaying Network.</li>
<li>in any case the <b>M</b> values will be appropriately set so to represent the <u>partial cost</u> corresponding to each vertex.
(if the input Linestrings already contains M-values they'll be overwritten).</li>
</ul>
<br>
In other words, all Linestrings returned by VirtualRouting can effectively support <b>LR</b> (<i>Linear Referencing</i>) SQL functions, as in the following examples:
<verbatim>
SELECT ST_Locate_Between_Measures(<geometry>, 30.0, 45.0);

SELECT ST_Locate_Between_Measures(<geometry>, 80.0, 95.0);
</verbatim>
The side map graphically shows the estimated positions respectively seconds after starting (yellow dotted line) and seconds after starting (green dotted line).<br>
(assuming the same path returned by the latest <b>bycar</b> query).
</td>
<td><img alt="fig2"></td>
</tr>
</table>
<br>
<h2>Playing with VirtualRouting configurable options</h2>
Several aspects of VirtualRouting can be freely customized.
<verbatim>
UPDATE byfoot SET Algorithm = 'A*';

SELECT Algorithm, Options, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = 183286;
</verbatim>
If you remember in all the previous examples the <b>Dijkstra's</b> algorithm was used; now (after executing the above <b>UPDATE</b>) all Shortest Path queries will be based on the alternative <b>A*</b> algorithm.<br>
If you wish to select again the Dijkstra's algorithm you just have to execute<br> <b>UPDATE byfoot SET Algorithm = 'DIJKSTRA';</b>.<br><br>
The following table shows the resultset returned by the previous Shortest Path query; please notice the value in the <b>Algorithm</b> column.
<br><br>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">Algorithm</th><th bgcolor="#d0d0a0">Options</th><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
align="right">178731</td><td align="right">183286</td><td align="right">300.912208</td><td>BLOB sz=272
</tr>
<tr>
align="right">224014</td><td align="right">178731</td><td align="right">182885</td><td PIETRO ARETINO</td>
</tr>
<tr>
align="right">224446</td><td align="right">182885</td><td align="right">178880</td><td MARGARITONE</td>
</tr>
<tr>
align="right">224414</td><td align="right">178880</td><td align="right">183286</td><td MARGARITONE</td>
</tr>
</table>
<br><br><br>
You can eventually configure the resultset returned the VirtualRouting queries.
<verbatim>
UPDATE byfoot SET Options = 'NO LINKS';

SELECT Algorithm, Options, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = 183286;
</verbatim>
After setting <b>Options='NO LINKS'</b> the resultset will simply contain the header row, and all the following rows will be suppressed.<br>
<u>Note</u>: producing a reduced resultset is expected to be someway faster.<br>
The following table shows the resultset returned by the previous Shortest Path query; please notice the value in the <b>Options</b> column.
<br><br>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">Algorithm</th><th bgcolor="#d0d0a0">Options</th><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
<tr>
<td>A*</td><td>No Links</td><td align="right">178731</td><td align="right">183286</td><td align="right">300.912208</td><td>BLOB sz=272
</tr>
</table>
<br><br><br>
<verbatim>
UPDATE byfoot SET Options = 'NO GEOMETRIES';

SELECT Algorithm, Options, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = 183286;
</verbatim>After setting <b>Options='NO GEOMETRIES'</b> the resultset will contain all rows, but all Geometries will be suppressed.<br>
<u>Note</u>: this too is expected to be someway faster.<br>
The following table shows the resultset returned by the previous Shortest Path query; please notice the value in the <b>Options</b> column.
<br><br>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">Algorithm</th><th bgcolor="#d0d0a0">Options</th><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
<tr><td>A*</td><td>No Geometries</td><td align="right">178731</td><td align="right">183286</td><td
</tr>
<tr>
align="right">224014</td><td align="right">178731</td><td align="right">182885</td><td PIETRO ARETINO</td>
</tr>
<tr>
align="right">224446</td><td align="right">182885</td><td align="right">178880</td><td MARGARITONE</td>
</tr>
<tr>
align="right">224414</td><td align="right">178880</td><td align="right">183286</td><td MARGARITONE</td>
</tr>
</table>
<br><br><br>
<verbatim>
UPDATE byfoot SET Options = 'SIMPLE';

SELECT Algorithm, Options, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = 183286;
</verbatim>Setting <b>Options='SIMPLE'</b> has the same effect than setting both <b>NO LINKS</b> and <b>NO GEOMETRIES</b> at the same time.<br>
<u>Note</u>: this is expected to be the fastest setting.<br>
The following table shows the resultset returned by the previous Shortest Path query; please notice the value in the <b>Options</b> column.
<br><br>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">Algorithm</th><th bgcolor="#d0d0a0">Options</th><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
<tr>
align="right">178731</td><td align="right">183286</td><td
</tr>
</table>
<br>
Finally, if you wish to select again the initial standard setting you just have to execute<br> <b>UPDATE byfoot SET Options = 'FULL';</b>.<br><br>
<hr><br>
<h1><a name="multi">5 - Solving multi-destination Shortest Path
A very interesting feature supported by the Dijkstra's Algorithm is that it robustly ensures that when a destination is reached all the destinations presenting a <b>lesser cost</b> have already been reached in some previous step of the process.<br>
This allows to efficiently support <b>multiple destinations</b> Shortest Path queries.
You simply have to specify a <b>single origin Node</b> and an <b>arbitrary list of destination Nodes</b> in a single Dijkstra's execution.<br><br>
<u>Note</u>: executing a multi-destination Shortest Path query requires a <b>processing time</b> that isn't the <u>sum of all individual timings for each destination</u>, but simply is the <u>time required to reach the most costly of all destinations in the list</u>.<br>
This isn't rigorously true in the case of the VirtualRouting specific implementation, because arranging the resultset to be returned and creating all the individual Linestrings for each destination will surely impose some further overhead, but nonetheless it remains confirmed that executing a single multi-destination query will surely be  noticeably faster then executing many sparse single-destination queries.
<verbatim>
SELECT Algorithm, Request, Options, Delimiter, RouteId, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = '183286,290458,181999,184030,124622,183882,178754';
</verbatim>
As you can easily notice, a <b>multiple-destinations</b> query has the same identical form of any usual Shortest Path query, except in that <b>NodeTo</b> now corresponds to a comma-separated list.<br>
The following table shows the resultset returned by the previous multi-destination Shortest Path query.
<br><br>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">Algorithm</th><th bgcolor="#d0d0a0">Request</th><th bgcolor="#d0d0a0">Options</th><th bgcolor="#d0d0a0">Delimiter</th><th bgcolor="#d0d0a0">RouteId</th><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
<tr>
<td>Dijkstra</td><td>Shortest &#91;dec=44, hex=2c&#93;</td><td align="right">0</td><td align="right">178731</td><td align="right">183882</td><td align="right">154.750839</td><td>BLOB sz=240
</tr>
<tr>
align="right">0</td><td align="right">222636</td><td align="right">178731</td><td align="right">182000</td><td PIETRO ARETINO</td>
</tr>
<tr>
align="right">0</td><td align="right">225527</td><td align="right">182000</td><td align="right">183882</td><td LICIO NENCETTI</td>
</tr>
<tr>
align="right">1</td><td align="right">178731</td><td align="right">184030</td><td align="right">176.364755</td><td>BLOB sz=304
</tr>
<tr>
align="right">1</td><td align="right">224014</td><td align="right">178731</td><td align="right">182885</td><td PIETRO ARETINO</td>
</tr>
<tr>
align="right">1</td><td align="right">224862</td><td align="right">182885</td><td align="right">182043</td><td MARGARITONE</td>
</tr>
<tr>
align="right">1</td><td align="right">226070</td><td align="right">182043</td><td align="right">184030</td><td SANT'AGOSTINO</td>
</tr>
<tr>
align="right">2</td><td align="right">178731</td><td align="right">178754</td><td align="right">224.677095</td><td>BLOB sz=240
</tr>
<tr>
align="right">2</td><td align="right">219045</td><td align="right">178731</td><td align="right">178732</td><td ASSAB</td>
</tr>
<tr>
align="right">2</td><td align="right">219058</td><td align="right">178732</td><td align="right">178754</td><td FRANCESCO CRISPI</td>
</tr>
<tr>
align="right">3</td><td align="right">178731</td><td align="right">181999</td><td align="right">260.132354</td><td>BLOB sz=240
</tr>
<tr>
align="right">3</td><td align="right">224014</td><td align="right">178731</td><td align="right">182885</td><td PIETRO ARETINO</td>
</tr>
<tr>
align="right">3</td><td align="right">224446</td><td align="right">182885</td><td align="right">178880</td><td MARGARITONE</td>
</tr>
<tr>
align="right">3</td><td align="right">225800</td><td align="right">178880</td><td align="right">181999</td><td FRANCESCO CRISPI</td>
</tr>
<tr>
align="right">4</td><td align="right">178731</td><td align="right">183286</td><td align="right">300.912208</td><td>BLOB sz=272
</tr>
<tr>
align="right">4</td><td align="right">224014</td><td align="right">178731</td><td align="right">182885</td><td PIETRO ARETINO</td>
</tr>
<tr>
align="right">4</td><td align="right">224446</td><td align="right">182885</td><td align="right">178880</td><td MARGARITONE</td>
</tr>
<tr>
align="right">4</td><td align="right">224414</td><td align="right">178880</td><td align="right">183286</td><td MARGARITONE</td>
</tr>
<tr>
align="right">178731</td><td
</tr>
<tr>
align="right">178731</td><td
</tr>
</table>
<br>
Let's quickly examine the resultset returned by the above <b>multi-destinations</b> query.
<ul>
<li>the overall layout is almost exactly the same as you've already seen in the case of <b>single-destination</b> queries, but in this case more individual travel solutions are grouped altogether.</li>
<li>the <b>first row</b> of the resultset is someway exceptional, and is the unique row of the resultset presenting <b>NOT NULL</b> values in the <b>Algorithm</b>, <b>Request</b>, <b>Options</b> and <b>Delimiter</b> columns.</li>
<li>the <b>RouteId</b> column is intended to group together all rows belonging to same travel solution (<i>aka</i> <b>Route</b>).<br>
Routes are progressively numbered and are ordered accordingly to their <b>total
<li>the <b>RouteRow</b> column has the same interpretation as in single-destination resultsets, and is intended to progressively order in the correct sequence all Links connecting the Origin and the Destination of each Route.<br>
<b>RouteRow=0</b> always identifies the header row of each travel solution.</li>
</ul>
<br>
<u>Notice</u>: the last two rows in the resultset reports <b>Unreachable NodeTo	</b> in the <b>Role</b> column, thus implying a <b>forbidden connection</b>.<br>
This was purposely intended: Nodes <b>290458</b> and <b>124622</b> are located on Elba and Giglio islands. The underlaying Network is based on that don't supports ferry connections, so any travel solution between the islands and the mainland will always fail.
<br><br><br>
Also <b>multi-destinations</b> queries can be customized, but the configuration rules slightly differ from what you have already seen in the case of single-destination.
<ul>
<li><b>Algorithm</b>: only <b>Dijkstra</b> is supported by multi-destination; any attempt to use the alternative <b>A*</b> algorithm will simply return an empty resultset.</li>
<li><b>Options</b>: the usual <b>FULL</b>, <b>SIMPLE</b>, <b>NO LINKS</b> and <b>NO GEOMETRIES</b> are supported and will have the same effect as in single-destination queries.</li>
</ul>
<verbatim>
UPDATE byfoot SET Options = 'SIMPLE';

SELECT Algorithm, Request, Options, Delimiter, RouteId, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = '183286,290458,181999,184030,124622,183882,178754';
</verbatim>
The following table shows the resultset returned by the same multi-destination query used in the previous example after enabling the <b>SIMPLE</b> option.
<br><br>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">Algorithm</th><th bgcolor="#d0d0a0">Request</th><th bgcolor="#d0d0a0">Options</th><th bgcolor="#d0d0a0">Delimiter</th><th bgcolor="#d0d0a0">RouteId</th><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
<tr>
<td>Dijkstra</td><td>Shortest &#91;dec=44, hex=2c&#93;</td><td align="right">0</td><td align="right">178731</td><td align="right">183882</td><td
</tr>
<tr>
align="right">1</td><td align="right">178731</td><td align="right">184030</td><td
</tr>
<tr>
align="right">2</td><td align="right">178731</td><td align="right">178754</td><td
</tr>
<tr>
align="right">3</td><td align="right">178731</td><td align="right">181999</td><td
</tr>
<tr>
align="right">4</td><td align="right">178731</td><td align="right">183286</td><td
</tr>
<tr>
align="right">178731</td><td
</tr>
<tr>
align="right">178731</td><td
</tr>
</table>
<br>
The map below graphically shows the previous <b>multi-destinations</b> queries.
<br><br>
<img alt="fig3">
<ul>
<li>Red star: the Origin Node.</li>
<li>Green dots: the Destination Nodes.</li>
<li>Yellow lines: all individual travel solutions.</li>
</ul>
<br>
<table bgcolor="#ffb060" cellspacing="10" cellpadding="6"><tr><td>
<h3>Dangerous pitfalls related to multiple destination lists</h3>
SQL syntax directly allows to specify lists of  multiple values, so may be you are now wondering about writing the <b>multiple destinations</b> query tested in the previous examples this way:
<verbatim>
SELECT Algorithm, Request, Options, Delimiter, RouteId, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo IN (183286, 290458, 181999, 184030, 124622, 183882, 178754);
</verbatim>
There is a very good reason discouraging from doing such a thing, let's see why.<br>
<b>SQLite</b> will process a request written this way by repeatedly calling VirtualRouting passing each time a single Destination; and consequently <b>VirtualRouting</b> will never receive the critical information that a single monolithic request was intended to be executed in a single shot. So the request context will be easily misinterpreted, and any expected speed benefit will be completely frustrated.
<h3>Beware</h3>
<b>Never ever</b> attempt to define a list of multiple destinations using the standard SQL syntax <b><i>WHERE NodeTo IN because this will certainly cause many unexpected troubles.<br>
Badly formatted resultsets will be then returned, may be containing wrong results. <b>You are warned</b>.<br><br>

<br>
<table bgcolor="#c0ffc0" cellspacing="10" cellpadding="6"><tr><td>
<h3>How to correctly format multiple destinations lists</h3>
VirtualRouting always expects to receive a <b>multi-destinations</b> list as a <b>TEXT</b> string containing tightly packed values separated by a conventional <b>delimiter</b> (usually represented by a <b>comma</b>).<br>
Examples of <b>well formatted</b> multi-destinations lists:
<verbatim>
'1,2,3,4,5,10,100,1000,100000'   -- integer Node IDs

'A100B,A100F,B250Z,C010M,Z999A'  -- alphanumeric Node Codes
</verbatim>
Examples of <b>badly formatted</b> multi-destinations lists:
<verbatim>
'  1, 2, 3, 4 , 5 , 10, 100, 1000, 100000  '   -- integer Node IDs

'  A100B, A100F , B250Z , C010M, Z999A  '      -- alphanumeric Node Codes
</verbatim>
<u>Note</u>: all whitespaces immediately preceding or following the <b>delimiter</b> will be considered to be integral part of the value itself.<br>
This will have no adverse consequences in the case of integer values, but can easily have catastrophic effects on alphanumeric values.
<h3>Defining a custom delimiter</h3>
Sometimes it could be useful setting up a delimiter different from <b>comma</b>.
<verbatim>
UPDATE byfoot SET Delimiter = '*';

SELECT Delimiter FROM byfoot;
------------------
* [dec=42, hex=2a]
</verbatim>
You simply have to execute an <b>UPDATE</b> statement by specifying the new delimiter value.<br><br>

<br><br>
<hr><br>
<h1><a name="tsp">6 - Solving TSP (traveling salesman)
<b>TSP</b> (<a Salesman Problem</a>) is a well known Operations Research problem.
<br><br>
<table bgcolor="#c0ffc0" cellspacing="10" cellpadding="6"><tr><td>
<h3>The Traveling Salesman Problem</h3>
<b><i>Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city
<br><br>

<br>
<u>Note:</u> the terms and are universally used for historical reasons, but you should avoid to literally intend both them.<br>
The term in this specific context intends any possible kind of <u><i>moving (pedestrian, vehicle, passenger or whatever else), exactly as simply stands for any <i><u>generic on a given Network.
<br><br>
We can conceptualy split TPS in two halves:
<ol>
<li>computing all distances between pairs of <i>cities</i>. This is a typical <b>ShortestPath</b> problem, and we can duly use the Dijkstra's algorithm for this.</li>
<li>then we have to check all possible <b>permutations</b> / <b>combinations</b> so to identify the optimal TSP solution.</li>
</ol>
Unhappily there is a practical difficulty in such a straight approach; the number of combinations will grow extremely fast as the number of increases.<br>
Simply computing the complete TSP solution for about ten cities will require a <b>very long time</b> even using a supercomputer.<br>
And attempting to compute a TSP solution for about hundred cities will require a <b>practically infinite</b> time.
<br><br>
However solving TSP is highly desirable in many application fields: <b>logistics</b> (just think about courier companies as DHL, FedEX, UPS or TNT), <b>field maintenance</b> / <b>assistance</b>, <b>waste collection</b>, <b>schoolbus</b> / <b>shared taxi services</b> etc.<br>
Many algorithms have been invented during last decades intended to produce practical although approximate / imperfect TSP solutions in a reasonably short time.
Many of them strongly depend on <a and / or <a
<br><br>
<b>VirtualRouting</b> supports two different TSP algorithms:
<ul>
<li><b>TSP NN</b> (<i>aka</i> <b><i>Nearest
This <a algorithm</a> is straightforward simple and very fast; it can effectively solve huge TSP solutions (thousand <i>cities</i> or even more) in a very short time.<br>
<u>Short description</u>:
<ul>
<li>starting from the <u><i>base the goes to the presenting the <i><u>lesser connection
<li>the already visited is cancelled from the list, and then the goes to the next presenting the <i><u>lesser connection
<li>the cycle continues until all  in the list have been visited.</li>
<li>finally, the returns to his/her initial <u><i>base
</ul>
<u>Note</u> it's very unlike that TSP NN could find the <b>optimal</b> solution, but it can quickly find some reasonable <b>approximate</b> solution (<i>few is surely better than nothing</i>).<br>
In the most unlucky case TSP NN could possibly return the <b>worst solution</b>, but the specific implementation adopted by VirtualRouting checks against this possibility:
<ul>
<li>each TSP NN is always computed twice by randomly choosing a different <u><i>base and then normalizing the solution; the best of the two solutions is then returned.</li>
<li>this simple but effective precaution robustly ensures that the <b>worst solution</b> will never be returned, and just implies a moderately increased execution time.</li>

<li><b>TSP GA</b> (<i>aka</i> <b><i>Genetic
This <a algorithm</a> is much more complex and sophisticated, and is directly inspired by biological concepts such as <b>sexual reproduction</b>, <b>genetic mutations</b> and <b>natural selection</b>.<br>
<u>Short description</u>:
<ul>
<li>a first initial set of solutions (<i><u>the is created by using TSP NN after randomly choosing the <u><i>base and then normalizing each solution.</li>
<li>then during each step of the execution loop pairs of solutions <i><u>sexually giving birth to <u><i>children reproduction is subject to <u><i>chromosome and <i><u>random
<li>for each the <i><u>natural eliminates all poorly fit individuals from the and consequently only the best fit individuals can further propagate their to the next
<li>after a certain number of (let's say about some hundredth iterations) the <b>optimal solution</b> (or at least a <b>fairly good sub-optimal solution</b>) should finally emerge, and so the loop can exit.</li>

<li><u>Note</u>: TSP GA is usually expected to identify better solutions than TSP NN can do, but it will surely require much more time to complete.</li>
</ul>
<br><br>
Let's now examine a practical example of TSP solving using VirtualRouting.
<verbatim>
UPDATE byfoot SET Request = 'TSP';

SELECT Algorithm, Request, Options, Delimiter, RouteId, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = '183286,181999,184030,183882,178754';
</verbatim>
A VirtualRouting <b>TSP</b> query has the same identical form of a <b>multi-destination</b> query; the <i><u>base city<u></i> is always expected to correspond to <b>NodeFrom</b> and all other to be visited are expected to be enumerated into a <b>multi-destination</b> list assigned to <b>NodeTo</b>.
<u>Note</u>: you must explicitly set the current <b>Request</b> as <b>TSP</b>, <b>TSP NN</b> or <b>TSP GA</b> (TSP and TSP NN are synonyms).
<br><br>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">Algorithm</th><th bgcolor="#d0d0a0">Request</th><th bgcolor="#d0d0a0">Options</th><th bgcolor="#d0d0a0">Delimiter</th><th bgcolor="#d0d0a0">RouteId</th><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
<tr>
<td>Dijkstra</td><td>TSP &#91;dec=44, hex=2c&#93;</td><td align="right">0</td><td align="right">0</td><td>TSP align="right">178731</td><td align="right">178731</td><td align="right">1254.433933</td><td>BLOB sz=2000
</tr>
<tr>
align="right">1</td><td align="right">178731</td><td align="right">184030</td><td align="right">176.364755</td><td>BLOB sz=304
</tr>
<tr>
align="right">2</td><td align="right">224014</td><td align="right">178731</td><td align="right">182885</td><td PIETRO ARETINO</td>
</tr>
<tr>
<tr>
align="right">2</td><td align="right">224862</td><td align="right">182885</td><td align="right">182043</td><td MARGARITONE</td>
</tr>
<tr>
align="right">2</td><td align="right">226070</td><td align="right">182043</td><td align="right">184030</td><td SANT'AGOSTINO</td>
</tr>
<tr>
align="right">2</td><td align="right">184030</td><td align="right">181999</td><td align="right">139.114938</td><td>BLOB sz=496
</tr>
<tr>
align="right">3</td><td align="right">226071</td><td align="right">184030</td><td align="right">182629</td><td GIUSEPPE GARIBALDI</td>
</tr>
<tr>
align="right">3</td><td align="right">225512</td><td align="right">182629</td><td align="right">182933</td><td ITALIA</td>
</tr>
<tr>
align="right">3</td><td align="right">225511</td><td align="right">182933</td><td align="right">181999</td><td ITALIA</td>
</tr>
<tr>
align="right">3</td><td align="right">181999</td><td align="right">183286</td><td align="right">217.672885</td><td>BLOB sz=688
</tr>
<tr>
align="right">4</td><td align="right">222635</td><td align="right">181999</td><td align="right">181998</td><td ITALIA</td>
</tr>
<tr>
align="right">4</td><td align="right">224780</td><td align="right">181998</td><td align="right">183560</td><td DELL'ANFITEATRO</td>
</tr>
<tr>
align="right">4</td><td align="right">225827</td><td align="right">183560</td><td align="right">183286</td><td DELL'ANFITEATRO</td>
</tr>
<tr>
align="right">4</td><td align="right">183286</td><td align="right">178754</td><td align="right">378.313684</td><td>BLOB sz=272
</tr>
<tr>
align="right">5</td><td align="right">224414</td><td align="right">183286</td><td align="right">178880</td><td MARGARITONE</td>
</tr>
<tr>
align="right">5</td><td align="right">219171</td><td align="right">178880</td><td align="right">178732</td><td FRANCESCO CRISPI</td>
</tr>
<tr>
align="right">5</td><td align="right">219058</td><td align="right">178732</td><td align="right">178754</td><td FRANCESCO CRISPI</td>
</tr>
<tr>
align="right">5</td><td align="right">178754</td><td align="right">183882</td><td align="right">188.216831</td><td>BLOB sz=400
</tr>
<tr>
align="right">6</td><td align="right">224538</td><td align="right">178754</td><td align="right">181972</td><td ANTONIO GUADAGNOLI</td>
</tr>
<tr>

<td align="right">6</td><td align="right">224537</td><td align="right">181972</td><td align="right">182000</td><td DEL NINFEO</td>
</tr>
<tr>
align="right">6</td><td align="right">225527</td><td align="right">182000</td><td align="right">183882</td><td LICIO NENCETTI</td>
</tr>
<tr>
align="right">6</td><td align="right">183882</td><td align="right">178731</td><td align="right">154.750839</td><td>BLOB sz=240
</tr>
<tr>
align="right">7</td><td align="right">225527</td><td align="right">183882</td><td align="right">182000</td><td LICIO NENCETTI</td>
</tr>
<tr>
align="right">7</td><td align="right">222636</td><td align="right">182000</td><td align="right">178731</td><td PIETRO ARETINO</td>
</tr>
</table>
<br>
Let's now quickly examine the resultset returned by any TSP query:
<ul>
<li>the general layout is more or less the same as you've already seen in the case of <b>ShortestPath</b> queries.</li>
<li>the <b>first row</b> of the resultset is someway exceptional, and is the unique row of the resultset presenting <b>NOT NULL</b> values in the <b>Algorithm</b>, <b>Request</b>, <b>Options</b> and <b>Delimiter</b> columns.<br>
It contains the <b>TSP solution</b> as a whole: column <b>Cost</b> is the <u>total cost</u> and column <b>Geometry</b> is the <u>overall solution
<li>columns <b>RouteId</b> and <b>RouteRow</b> have the same interpretation as in <b>multi-destination ShortestPath</b> queries, but in this specific case each corresponds to a connection between two
All are order accordingly to the running sequence of the TSP solution. <b>RouteId=0</b> identifies the overall TSP solution.</li>
</ul><br><br>
<verbatim>
UPDATE byfoot SET Request = 'TSP GA';

SELECT Algorithm, Request, Options, Delimiter, RouteId, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = '183286,181999,184030,183882,178754';
</verbatim>
If you wish to get a <b>TSP GA</b> solution you simple have to set <b>Request</b> as <b>TSP GA</b>; and you can set again <b>Request</b> as <b>TSP</b> or <b>TSP NN</b> to revert back to the simpler / faster algorithm.
<br>
Also in the case of TSP you can eventually activate the usual <b>Options</b> already explained in the ShortestPath examples.
<verbatim>
UPDATE byfoot SET Request = 'TSP', Options = 'NO LINKS';

SELECT Algorithm, Request, Options, Delimiter, RouteId, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = '183286,181999,184030,183882,178754';
</verbatim>
The following table shows the resultset returned by the same TSP query used in the previous example after enabling the <b>NO LINKS</b> option. <br><br>
<table border="1" bgcolor="#ffffcf" cellspacing="4" cellpadding="6">
<tr><th bgcolor="#d0d0a0">Algorithm</th><th bgcolor="#d0d0a0">Request</th><th bgcolor="#d0d0a0">Options</th><th bgcolor="#d0d0a0">Delimiter</th><th bgcolor="#d0d0a0">RouteId</th><th bgcolor="#d0d0a0">RouteRow</th><th bgcolor="#d0d0a0">Role</th><th bgcolor="#d0d0a0">LinkRowid</th><th bgcolor="#d0d0a0">NodeFrom</th><th bgcolor="#d0d0a0">NodeTo</th><th bgcolor="#d0d0a0">Cost</th><th bgcolor="#d0d0a0">Geometry</th><th
<tr>
<td>Dijkstra</td><td>TSP NN</td><td>No Links</td><td>, &#91;dec=44, hex=2c&#93;</td><td align="right">0</td><td align="right">0</td><td>TSP align="right">178731</td><td align="right">178731</td><td align="right">1254.433933</td><td>BLOB sz=2000
</tr>
<tr>
align="right">1</td><td align="right">178731</td><td align="right">184030</td><td align="right">176.364755</td><td>BLOB sz=304
</tr>
<tr>
align="right">2</td><td align="right">184030</td><td align="right">181999</td><td align="right">139.114938</td><td>BLOB sz=496
</tr>
<tr>
align="right">3</td><td align="right">181999</td><td align="right">183286</td><td align="right">217.672885</td><td>BLOB sz=688
</tr>
<tr>
align="right">4</td><td align="right">183286</td><td align="right">178754</td><td align="right">378.313684</td><td>BLOB sz=272
</tr>
<tr>
align="right">5</td><td align="right">178754</td><td align="right">183882</td><td align="right">188.216831</td><td>BLOB sz=400
</tr>
<tr>
align="right">6</td><td align="right">183882</td><td align="right">178731</td><td align="right">154.750839</td><td>BLOB sz=240
</tr>
</table>
<br><br><br>
The map below graphically shows the previous <b>TSP</b> queries.
<br><br>
<img alt="fig4">
<ul>
<li>Red star: the (from where the begins his/her trip.</li>
<li>Green dots: the to be visited.</li>
<li>Yellow line: the TSP solution (that is always a circular path).</li>
</ul><br>
<table bgcolor="#ffb060" cellspacing="10" cellpadding="6"><tr><td>
<h3>Warning: how to correctly handling TSP resultsets with spatialite_gui</h3>
You should never forget or overlook that both <b>TSP NN</b> and <b>TSP GA</b> are <u><i>heuristic heavily relying on <u><i>random<i></u> choices.<br>
This could easily have the practical consequence that resolving twice (or even more times) the same identical TSP query could eventually return different resultsets.<br>
There is nothing intrinsically wrong in this, it simply is a direct consequence of using we are simply bargaining <b>exactness</b> and <b>reproducibility</b> for <b>quickness</b>.<br><br>
<b>spatialite_gui</b> on its own adopts a <b>paged strategy</b> when showing huge resultsets; this requires repeating again the initial SQL query each time that a <b>new page of 500 rows</b> has to be shown on the current window panel.<br>
The two things don't go together well; so don't be surprised when eventually discovering that <b>spatialite_gui</b> will behave bizarrely while presenting some resultset returned by a TSP query.
<verbatim>
UPDATE byfoot SET Request = 'TSP';

CREATE TABLE my_tsp_solution AS
SELECT Algorithm, Request, Options, Delimiter, RouteId, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = '183286,181999,184030,183882,178754';

...  <now query "my_tsp_solution" using spatialite_gui>  ...

DROP TABLE my_tsp_solution;
</verbatim>
<u>Hint</u>: resolving this puzzling issue is however basically simple:
<ol>
<li>you simply have to take a <b>static snapshot</b> of your TSP resultset by using the <b>CREATE TABLE <i>name</i> AS <i>TSP
<li>then you can freely examine the above snapshot.</li>
<li>and finally you can duly <b>DROP</b> the snapshot once it's no longer useful.</li>
</ol>

</table>
<br>
<table bgcolor="#c0ffc0" cellspacing="10" cellpadding="6"><tr><td>
<h3>More about Linear Referencing and VirtualRouting Linestrings</h3>
You have already seen in a previous example that all LINESTRINGs created by VirtualRouting support the <b>M</b> coordinate intended as a <b>progressive cost</b> for each vertex. And you already know the they can support <b><i>linear (<b>LR</b>) SQL functions.<br>
Let's now go in further depth.
<h3>Trajectory objects</h3>
A <b>Trajectory</b> is any Linestring supporting <b>M coordinates</b> with a continuously increasing trend.<br>
In simpler words, the <b>M-value</b> of each vertex (except the last one) must be <b>lesser</b> than the M-Value of the next vertex.
<verbatim>
SELECT * FROM my_tsp_solution WHERE ST_IsValidTrajectory(geometry) = 1;
-------------------
1
</verbatim>
As you can easily check by calling <b>ST_IsValidTrajectory()</b> every Linestring created by VirtualRouting is a <b>valid Trajectory</b>.
<verbatim>
SELECT ST_TrajectoryInterpolatePoint(Geometry, 100.0)
FROM my_tsp_solution
WHERE RouteId = 0;
</verbatim>
So you just have to call <b>ST_TrajectoryInterpolatePoint()</b> in order to create a POINT precisely located on the Linestring at the given <b>cost</b>.
<br><br><hr><br><br>
The side map graphically shows the estimated positions every 100m assuming the same path returned by the latest TSP query.
</td><td>
<img alt="fig5">

<hr><br>
<a