Update of "VirtualRouting"
Not logged in

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview

Artifact ID: 5e38c649dd49d6980ce30dd87f760c54cd32c201
Page Name:VirtualRouting
Date: 2019-12-26 16:00:19
Original User: sandro
Parent: 66bbe878ad3e27e59195123329ae664085d1eddd
Content

Back to 5.0.0-doc main page



Table of Contents

1 - Introduction
2 - The sample/test DB
3 - Creating VirtualRouting Tables
4 - Solving classic Shortest Path problems
5 - Solving multi-destination Shortest Path problems
6 - Solving Isochrone problems
7 - Solving TSP (traveling salesman) problems
8 - Solving Point-to-Point problems


1 - Introduction

Previous versions of SpatiaLite traditionally supported a pure SQL routing module that was named VirtualNetwork.

Since version 5.0.0 a brand new routing module (more advanced and sophisticated) is available, that is called VirtualRouting.
The now obsolete VirtualNetwork is still supported by version 5.0.0 so as to not cause an abrupt break to already existing applications, but will presumably be discontinued in future versions.
Using VirtualRouting instead of VirtualNetwirk is warmly recommended for any new development.

Theoretical foundations - an ultra-quick recall

All Routing algorithms (aka Shortest Path algorithms) are based on the mathematics of the Graph theory or to be more precise: on Weighted Graphs.
network
A topologically valid Network is a dataset that fulfills the following requirements:

Logical conclusions

Any topologically valid Network (irrespective of whether it is a Spatial or Logical type) is a valid Graph.
A Network allowing the support (direct or indirect) of some appropriate cost value is a valid Weighted Graph, and can consequently support Routing algorithms.
All Routing algorithms are intended to identify the Shortest Path solution connecting two Nodes in a weighted graph (aka Network).

Note: the term Shortest Path can be easily misunderstood.
Due to historical reasons the most common application field for Routing algorithms is related to Road Networks, but also many other kinds of Networks exist:
In all the above cases we certainly have valid Networks supporting Routing algorithns, but not all of them can imply something like a spatial distance (geometric length) or a travel time.
In the most general acception costs can be represented by any reasonable physical quantity.
So a more generalized definition is assuming that Routing algorithms are intended to identify lesser cost solutions on a weighted graph.
The exact interpretation of the involved costs (aka weights) strictly depends on the very specific nature of each Network.

The Dijkstra's algorithm

This well known algorithm isn't necessarily the fastest one, but it always ensures full correctness:

The A* algorithm

Many alternative Routing algorithms have been invented during the years.
All them are based on heuristic assumptions and are intended to be faster than Dijkstra's, but none of them can ensure full correctness as Dijkstra's does.
The A* algorithm applies a mild heuristic optimization, and can be a realistic alternative to Dijkstra's in many cases.


2 - The sample/test DB

You are expected to follow the current tutorial about VirtualRouting by directly testing all SQL queries discussed below with the sample/test DB that you can download from here

The sample DB contains the full road network of Tuscany Region (Italy) (Iter.Net dataset) kindly released under the CC-BY-SA 4.0 licence terms.
Allthough the contents stored in the sample database have been rearranged, it is still subject to the initial CC-BY-SA 4.0 clauses (derived work).



3 - Creating VirtualRouting Tables

All VirtualRouting queries are based on a specific VirtualRouting-Table, and in turn, the VirtualRouting-Table is based on a corresponding BinaryData-Table which, taken togeather, is an efficient representation of the underlying Network.
So we'll start first by creating these tables.

The old, and now superseded, VirtualNetwork required the use of a separate CLI tool (spatialite_network) in order to properly initialize a VirtualNetwork Table and its companion BinaryData-Table; alternatively spatialite_gui supported a GUI wizard for the same task. Since version 5.0.0, SpatiaLite supports this functionality directly, with the CreateRouting() SQL function.
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
Note: this first query (based on the minimal form of CreateRouting) deliberately contains an error causing a failure that will raise an exception.
CreateRouting() can fail for multiple reasons, and by calling CreateRouting_GetLastError() you can easily identify the exact reason why the most recent call to CreateRouting() failed.
SELECT CreateRouting('byfoot_data', 'byfoot', 'roads_vw', 'node_from', 'node_to', 'geom', NULL, 'toponym', 1, 1);
-------------
1

SELECT CreateRouting_GetLastError();
------------------------------------
NULL
This second attempt will succeed, with CreateRouting() returning 1 (aka TRUE), and as you can easily check now the Database contains two new Tables: byfoot and byfoot_data.
Note: after a successful call to CreateRouting() CreateRouting_GetLastError() will always return NULL.

Let's look, in more detail, of the minimal form of CreateRouting(); and the meaning of each argument:
  1. byfoot_data: the name of the Network BinaryData-Table to be created.
  2. byfoot: the name of the VirtualRouting-Table to be created.
  3. roads_vw: the name of the Spatial Table or Spatial View representing the underlying Network.
    Note: in this case we actually used a Spatial View.
  4. node_from: name of the column (in the above Table or View) expected to contain node-from values.
  5. node_to: name of the column (in the above Table or View) expected to contain node-to values.
  6. geom: name of the column (in the above Table or View) expected to contain Linestrings.
    In the case of a Logical Network: a NULL should be passed..
  7. NULL: name of the column (in the above Table or View) expected to contain cost values.
    In this case we have passed a NULL value, and consequently the cost of each Link will be assumed to be represented by the geometric length of the corresponding Linestring.
    Note #1: in the case of Networks based on longitudes and latitudes (aka geographic Reference Systems) the geometry length of all Linestrings will be precisely measured on the ellipsoid by applying the most accurate geodesic formulas and will consequently be expressed in meters. In any other case (projected Reference Systems) lengths will be expressed in the measure unit defined by the Reference System (e.g. meters for UTM projections and feet for NAD-ft projections).
    Note #2: the geom-column and cost-column arguments are never allowed to be NULL at the same time.
  8. toponym: name of the column (in the above Table or View) expected to contain road-name values.
    It could be legitimately set to NULL if all Links are anonymous.
  9. 1: a boolean flag intended to specify if the Network must support the A* algorithm or not (set to TRUE by default).
  10. 1: a boolean flag intended to specify if all Network's Links are assumed to be bidirectional or not (assumed to be TRUE by default).

Technical note

The internal encoding adopted by the BinaryData-Table is unchanged and is the same for both VirtualNetwok and VirtualRouting.
You can safely base a VirtualRouting-Table on any existing BinaryData-Table created by the spatialite-network CLI tool, exactly as you can base a VirtualNetwork Table on any BinaryData-Table created by the CreateRouting() SQL function.
CREATE VIRTUAL TABLE test_network USING VirtualNetwork('some_data_table');

CREATE VIRTUAL TABLE test_routing USING VirtualRouting('some_data_table');
In order to manually create your Virtual Tables you just have to execute an appropriate CREATE VIRTUAL TABLE ... USING Virtual... (...) statement.

Warning

In the case of Spatial Networks based on any geographic Reference System (using longitudes and latitudes) there is an important difference between BinaryData-Tables created by the spatialite_network GUI tool and BinaryData-Tables created by the CreateRouting() SQL function when costs are implicitly based on the geometric length of the Link's Linestring:
  • the spatialite_network CLI tool (and the GUI wizard implemented by previous versions of spatialite_gui) compute the Linestring's length as an angular distance expressed in degrees.
  • the CreateRouting() SQL function computes the Linestring's length as a linear distance expressed in metres by applying the most accurate geodesic formulas on the ellipsoid.


SELECT CreateRouting('bycar_data', 'bycar', 'roads_vw', 'node_from', 'node_to', 'geom', 'cost', 'toponym', 1, 1, 'oneway_fromto', 'oneway_tofrom', 0);
--------------------
1
After calling CreateRouting() correctly, the Database contains two further Tables: bycar and bycar_data.
This time you've used the complete form of CreateRouting(); let's see in more depth all the arguments and their meaning:
  1. bycar_data: same as above.
  2. bycar: same as above.
  3. roads_vw: same as above.
  4. node_from: same as above.
  5. node_to: same as above.
  6. geom: same as above.
  7. cost: same as above. In this case we have referenced a column preloaded with values corresponding to the time measured in seconds required to traverse each Link.
  8. toponym: same as above.
  9. 1: same as above (A* enabled).
  10. 1: same as above (bidirectional Links).
  11. oneway_fromto: name of the column (in the above Table or View) expected to contain boolean flags specifying if each Link can be traversed in the from-to direction or not.
  12. oneway_tofrom: name of the column (in the above Table or View) expected to contain boolean flags specifying if each Link can be traversed in the to-from direction or not.
    Note #1: both from-to and to-from column names can be legitimately set as NULL if no one-way restrictions apply to the current Network.
    Note #2: Networks of the unidirectional type are never enabled to reference one-way columns (they should always be set to NULL).
  13. 0: a boolean flag specifying an overwrite authorization.
    • If set to FALSE an exception will be raised if the BinaryData-Table and/or the VirtualRouting-Table already exist.
    • If set to TRUE eventually existing Tables will be, to avoid errors, dropped before starting the execution of CreateRouting().

Highlight: where you are

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:
  • byfoot is specifically intended for pedestrians:
    • all Links are always assumed to be accessible in both directions; there are no one-ways and no forbidden Links.
    • the cost of each Link is directly represented by its geometric length, which is consistent with the assumption of an almost constant speed substantially immune from adverse road conditions and traffic congestion.
  • bycar is specifically intended for motor vehicles:
    • many Links are expected to be accessible in both directions but others could easily be subject to one-way restrictions or even be completely forbidden.
    • the cost of each Link is expressed as an estimated travel time, because the expected speeds can greatly vary accordingly to specific road conditions, traffic congestion and legal regulations.

Conclusion: a single VirtualRouting-Table cannot adequately support all requirements and expectations of different users.
Defining more Routing Tables with different settings for the same Network usually is a good design choice leading to more realistic results.


Utility function for automatically setting NodeFrom and NodeTo IDs

It could happen that a Spatial Network representation is topologically consistent, but completely lacking of any NodeFrom and NodeTo definitions.
In such a case you can successfully rebuild the missing NodeFrom and NodeTo definitions from a valid Network by calling the CreateRoutingNodes() SQL function.
SELECT CreateRoutingNodes(NULL, 'table_name', 'geom', 'node_from', 'node_to');
_________________________
1
Let's examine all arguments and their meanings:
  1. NULL: name of the Attached-DB containing the Spatial Table.
    It can be legitimately set to NULL, and in this case the MAIN DB is assumed.
  2. table_name: name of the Spatial Table.
  3. geom
  4. : name of the column (in the above Table) containing Linestrings.
  5. node_from: name of the column to be added to the above Table and populated with appropriate NodeFrom IDs.
  6. node_to: name of the column to be added to the above Table and populated with appropriate NodeTo IDs.
    Note: both NodeFrom and NodeTo columns should not be already defined in the above Table.
CreateRoutingNodes() will return 1 (aka TRUE) on success; an exception will be raised on failure.
Note: you can call CreateRouting_GetLastError() so to precisely identify the cause accounting for failure.


Handling dynamic Networks

A Network could be subject to rather frequent changes, such as:
  • new Links need to be added.
  • obsolete Links are required to be removed.
  • other Links may receive a different Cost.
  • one-ways could be reversed, the discipline of pedestrian areas could be modified and so on.

A VirtualRouting-Table is always based on a companion BinaryData-Table, that is intrinsically static, and consequently you are required to re-create both of them from time to time in order to support all recent changes affecting the underlaying Network.
The optimal frequency for the refreshing of the the Routing Tables depends strictly on the specific requirements, but these two overall approaches are commonly adopted:
  1. low frequency refresh: best fit for slowly evolving Networks.
    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).
    An optional refresh activity could be planned at low traffic hours (e.g. during the night), and CreateRouting() could be optionally called by enabling the overwrite option.
  2. medium-high frequency refresh: best fit for swiftly evolving Networks.
    Re-creating the Network Tables once per hour (or even more frequently) could be strictly required, and frequent out of service periods while waiting for the refresh process to complete could easily become unacceptable.
    In such cases you could adopt a multi-threaded strategy:
    • thread #1 (the reader): 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. my_routing based on my_routing_data).
    • thread #2 (the writer): this second thread is just intended to re-create both Network Tables at predefined intervals, and it will sleep until the next interval.
      At each interval a copy of both Network Tables, will be made and, when compleated, will overwrite the original Tables (activating a semaphore during this short-timed last step is highly recommended).
      Something like this pseudo-code exemplifies:
      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
      
      Note: strictly respecting the above sequence of SQL operations is absolutely required.

Warning: how to correctly drop Network Tables

When dropping a VirtualRouting-Table and its companion BinaryData-Table strictly respecting the correct sequence of SQL commands is essential.
Failing to strictly respect this expected sequence will surely cause you several troubles and severe headaches, and will possibly lead to a completely corrupted database..
  1. first DROP the VirtualRouting-Table.
  2. the companion BinaryData-Table can only be safely DROPed after the VirtualRouting-Table has been removed.
  3. Be warned: if you DROP the BinaryData-Table first, the VirtualRouting-Table will be orphaned and can no longer be DROPed !
    You have been warned !!




4 - Solving classic Shortest Path problems

The most classic Shortest Path problem requires to identify the optimal connection between an Origin Node and a Destination Node.
We can easily translate such a problem into a simple SQL query targeting some VirtualRouting-Table.
SELECT * 
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = 183286;
AlgorithmRequestOptionsDelimiterRouteIdRouteRowRoleLinkRowidNodeFromNodeToPointFromPointToToleranceCostGeometryName
DijkstraShortest PathFull, [dec=44, hex=2c]00RouteNULL178731183286NULLNULLNULL300.912208BLOB sz=272 GEOMETRYNULL
NULLNULLNULLNULL01Link224014178731182885NULLNULLNULL94.812424NULLVIA PIETRO ARETINO
NULLNULLNULLNULL02Link224446182885178880NULLNULLNULL69.727726NULLVIA MARGARITONE
NULLNULLNULLNULL03Link224414178880183286NULLNULLNULL136.372057NULLVIA MARGARITONE

Let's quickly examine the resultset returned by the above Routing query:

Testing the return connection just requires swapping the Origin and the Destination; in this example you'll just query the needed columns:
SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeTo = 178731 AND NodeFrom = 183286;
RouteRowRoleLinkRowidNodeFromNodeToCostGeometryName
0RouteNULL183286178731300.912208BLOB sz=272 GEOMETRYNULL
1Link224414183286178880136.372057NULLVIA MARGARITONE
2Link22444617888018288569.727726NULLVIA MARGARITONE
3Link22401418288517873194.812424NULLVIA PIETRO ARETINO

As you'll remember, the byfoot VirtualRouting-Table has no one-ways, and consequently the return path corresponds to the first one, except in that all directions are now reversed.


Now you'll test the same connections, but this time you'll target the bycar VirtualRouting-Table that fully supports one-ways:
SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM bycar
WHERE NodeFrom = 178731 AND NodeTo = 183286;
RouteRowRoleLinkRowidNodeFromNodeToCostGeometryName
0RouteNULL178731183286101.815552BLOB sz=2032 GEOMETRYNULL
1Link22401417873118288513.127874NULLVIA PIETRO ARETINO
2Link2244461828851788809.654608NULLVIA MARGARITONE
3Link2191711788801787327.809952NULLVIA FRANCESCO CRISPI
4Link21905817873217875412.445626NULLVIA FRANCESCO CRISPI
5Link2258881787541834611.599865NULLVIA FRANCESCO CRISPI
6Link2258871834611828003.300590NULLVIA FRANCESCO CRISPI
7Link2239351828001827996.688786NULLVIALE LUCA SIGNORELLI
8Link2260381827991834561.294017NULLVIALE LUCA SIGNORELLI
9Link2258321834561834442.385486NULLVIALE LUCA SIGNORELLI
10Link2258311834441835543.160662NULLVIALE LUCA SIGNORELLI
11Link2257651835541839547.469917NULLVIALE LUCA SIGNORELLI
12Link2257661839541839053.236389NULLVIALE LUCA SIGNORELLI
13Link22597918390518362613.983629NULLSTRADA SENZA NOME
14Link2249051836261831285.627358NULLSTRADA SENZA NOME
15Link22489718312818328610.030792NULLVIA MARGARITONE
SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM bycar
WHERE NodeTo = 178731 AND NodeFrom = 183286;
RouteRowRoleLinkRowidNodeFromNodeToCostGeometryName
0RouteNULL183286178731103.305259BLOB sz=944 GEOMETRYNULL
1Link22441418328617888018.882285NULLVIA MARGARITONE
2Link2191711788801787327.809952NULLVIA FRANCESCO CRISPI
3Link21905817873217875412.445626NULLVIA FRANCESCO CRISPI
4Link2245381787541819727.047784NULLVIA ANTONIO GUADAGNOLI
5Link2225751819721819711.852283NULLVIA ANTONIO GUADAGNOLI
6Link22496718197118289114.273185NULLVIA ANTONIO GUADAGNOLI
7Link2241681828911830576.643309NULLVIA MACALLE'
8Link2241671830571830563.151272NULLVIA MACALLE'
9Link2241741830561829417.966870NULLVIA RODI
10Link2240591829411820016.393747NULLVIA RODI
11Link2226371820011820002.475538NULLVIA PIETRO ARETINO
12Link22263618200017873114.363408NULLVIA PIETRO ARETINO

As you can see, the optimal paths returned by the bycar VirtualRouting-Table in the opposite directions strongly differ, and both are completely different from the paths returned by querying byfoot.
A quick glance at the map below will help to understand better what's really happening.
This is a central area of the town of Arezzo around the archaeological ruins of the Roman Amphitheater; traveling by car should be avoided, due to the many one-way restrictions. Not surprisingly, going by foot is the faster option.

fig1

Linestrings returned by VirtualRouting

All LINESTRING Geometries created by any VirtualRouting will always contain M values:
  • if the underlaying Network's Geometries are XY then XYM Linestrings will be returned.
  • if the underlaying Network's Geometries are XYZ then XYZM Linestrings will be returned.
  • if the underlaying Network's Geometries are XYM or XYZM then Linestrings returned into the resultset will maintain the same dimensions as in the underlaying Network.
  • in any case the M values will be appropriately set so to represent the partial cost corresponding to each vertex. (if the input Linestrings already contains M-values they'll be overwritten).

In other words, all Linestrings returned by VirtualRouting can effectively support LR (Linear Referencing) SQL functions, as in the following examples:
SELECT ST_Locate_Between_Measures(<geometry>, 30.0, 45.0);

SELECT ST_Locate_Between_Measures(<geometry>, 80.0, 95.0);
The side map graphically shows the estimated positions respectively 30-45 seconds after starting (yellow dotted line) and 80-95 seconds after starting (green dotted line).
(assuming the same path returned by the latest bycar query).
fig2

Playing with VirtualRouting configurable options

Several aspects of VirtualRouting can be freely customized.
UPDATE byfoot SET Algorithm = 'A*';

SELECT Algorithm, Options, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = 183286;
As you'll remember in all the previous examples the Dijkstra's algorithm was used; now (after executing the above UPDATE) all Shortest Path queries will be based on the alternative A* algorithm.
If you wish to switch back to the Dijkstra's algorithm you just have to execute
UPDATE byfoot SET Algorithm = 'DIJKSTRA';.

The following table shows the resultset returned by the previous Shortest Path query; please notice the value in the Algorithm column.

AlgorithmOptionsRouteRowRoleLinkRowidNodeFromNodeToCostGeometryName
A*Full0RouteNULL178731183286300.912208BLOB sz=272 GEOMETRYNULL
NULLNULL1Link22401417873118288594.812424NULLVIA PIETRO ARETINO
NULLNULL2Link22444618288517888069.727726NULLVIA MARGARITONE
NULLNULL3Link224414178880183286136.372057NULLVIA MARGARITONE



You can also configure the resultset returned the VirtualRouting queries.
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;
After setting Options='NO LINKS' the resultset will simply contain the header row, and all of the following rows will be suppressed.
Note: producing a reduced resultset is expected to be someway faster.
The following table shows the resultset returned by the previous Shortest Path query.
Notice that value in the Options column shows you which type of resultset you are using (just as the Algorithm column shows which algorithm is active).

AlgorithmOptionsRouteRowRoleLinkRowidNodeFromNodeToCostGeometryName
A*No Links0RouteNULL178731183286300.912208BLOB sz=272 GEOMETRYNULL



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;
After setting Options='NO GEOMETRIES' the resultset will contain all rows, but all Geometries will be suppressed.
Note: this too is expected to be somewhat faster.
The following table shows the resultset returned by the previous Shortest Path query; please notice the value in the Options column.

AlgorithmOptionsRouteRowRoleLinkRowidNodeFromNodeToCostGeometryName
A*No Geometries0RouteNULL178731183286300.912208NULLNULL
NULLNULL1Link22401417873118288594.812424NULLVIA PIETRO ARETINO
NULLNULL2Link22444618288517888069.727726NULLVIA MARGARITONE
NULLNULL3Link224414178880183286136.372057NULLVIA MARGARITONE



UPDATE byfoot SET Options = 'SIMPLE';

SELECT Algorithm, Options, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = 183286;
Setting Options='SIMPLE' has the same effect than setting both NO LINKS and NO GEOMETRIES at the same time.
Note: this is expected to be the fastest setting.
The following table shows the resultset returned by the previous Shortest Path query; please notice the value in the Options column.

AlgorithmOptionsRouteRowRoleLinkRowidNodeFromNodeToCostGeometryName
A*Simple0RouteNULL178731183286300.912208NULLNULL

Finally, if you wish to revert back to the initial setting, you do this with the following query
UPDATE byfoot SET Options = 'FULL';.



5 - Solving multi-destination Shortest Path problems

An interesting feature supported by the Dijkstra's Algorithm is: when a destination is been reached, all of the lesser cost destinations have also been found.
This allows the support of multiple destinations Shortest Path queries.
All you have to do is specify a single origin Node with an arbitrary list of destination Nodes in one Dijkstra's query.

Note: executing a multi-destination Shortest Path query requires a processing time that isn't the sum of all individual timings to each destination, but simply the time required to reach the most costly destination of the list.
This isn't strictly true in the case of this VirtualRouting specific implementation, since the arrangment the resultset to be returned and creation all the individual Linestrings for each destination will surely impose some further overhead.
Nevertheless the time needed for a single multi-destination query will be less than the time needed for multiple single-destination queries.
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';
As you can see, a multiple-destinations query has the same identical form of any normal Shortest Path query, the only difference being a comma-separated list (instead of a single-entry) for NodeTo.
The following table shows the resultset returned by the previous multi-destination Shortest Path query:

AlgorithmRequestOptionsDelimiterRouteIdRouteRowRoleLinkRowidNodeFromNodeToCostGeometryName
DijkstraShortest PathFull, [dec=44, hex=2c]00RouteNULL178731183882154.750839BLOB sz=240 GEOMETRYNULL
NULLNULLNULLNULL01Link222636178731182000103.735722NULLVIA PIETRO ARETINO
NULLNULLNULLNULL02Link22552718200018388251.015117NULLVIA LICIO NENCETTI
NULLNULLNULLNULL10RouteNULL178731184030176.364755BLOB sz=304 GEOMETRYNULL
NULLNULLNULLNULL11Link22401417873118288594.812424NULLVIA PIETRO ARETINO
NULLNULLNULLNULL12Link22486218288518204337.095287NULLVIA MARGARITONE
NULLNULLNULLNULL13Link22607018204318403044.457044NULLPIAZZA SANT'AGOSTINO
NULLNULLNULLNULL20RouteNULL178731178754224.677095BLOB sz=240 GEOMETRYNULL
NULLNULLNULLNULL21Link21904517873117873276.021007NULLVIA ASSAB
NULLNULLNULLNULL22Link219058178732178754148.656089NULLVIA FRANCESCO CRISPI
NULLNULLNULLNULL30RouteNULL178731181999260.132354BLOB sz=240 GEOMETRYNULL
NULLNULLNULLNULL31Link22401417873118288594.812424NULLVIA PIETRO ARETINO
NULLNULLNULLNULL32Link22444618288517888069.727726NULLVIA MARGARITONE
NULLNULLNULLNULL33Link22580017888018199995.592204NULLVIA FRANCESCO CRISPI
NULLNULLNULLNULL40RouteNULL178731183286300.912208BLOB sz=272 GEOMETRYNULL
NULLNULLNULLNULL41Link22401417873118288594.812424NULLVIA PIETRO ARETINO
NULLNULLNULLNULL42Link22444618288517888069.727726NULLVIA MARGARITONE
NULLNULLNULLNULL43Link224414178880183286136.372057NULLVIA MARGARITONE
NULLNULLNULLNULLNULLNULLUnreachable NodeToNULL178731290458NULLNULLNULL
NULLNULLNULLNULLNULLNULLUnreachable NodeToNULL178731124622NULLNULLNULL

Let's quickly examine the resultset returned by the above multi-destinations query.
Notice: the last two rows in the resultset reports Unreachable NodeTo in the Role column, thus implying a forbidden connection.
There is a valid reason for this: Nodes 290458 and 124622 are located on Elba and Giglio islands. The underlaying Network is based on Iter.Net that don't supports ferry connections, so any travel solution between the islands and the mainland will always fail.


Also multi-destinations queries can be customized, but the configuration rules differ slightly from what you have already seen in the case of single-destination.
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';
The following table shows the resultset returned by the same multi-destination query used in the previous example after enabling the SIMPLE option.

AlgorithmRequestOptionsDelimiterRouteIdRouteRowRoleLinkRowidNodeFromNodeToCostGeometryName
DijkstraShortest PathFull, [dec=44, hex=2c]00RouteNULL178731183882154.750839NULLNULL
NULLNULLNULLNULL10RouteNULL178731184030176.364755NULLNULL
NULLNULLNULLNULL20RouteNULL178731178754224.677095NULLNULL
NULLNULLNULLNULL30RouteNULL178731181999260.132354NULLNULL
NULLNULLNULLNULL40RouteNULL178731183286300.912208NULLNULL
NULLNULLNULLNULLNULLNULLUnreachable NodeToNULL178731290458NULLNULLNULL
NULLNULLNULLNULLNULLNULLUnreachable NodeToNULL178731124622NULLNULLNULL

The map below graphically shows the previous multi-destinations queries.

fig3

Dangerous pitfalls related to multiple destination lists

SQL syntax directly allows to specify lists of multiple values, so may be you are now wondering about writing the multiple destinations query tested in the previous examples this way:
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);
There is a very good reason to discourage you from doing such a thing, let's see why:

For SQLite: NodeTo IN (183286, 290458, 181999, 184030, 124622, 183882, 178754) is considered to be 7 parameters for which VirtualRouting will be called for each.
Whereas: NodeTo = '183286,290458,181999,184030,124622,183882,178754' is considered to be 1 parameter for which VirtualRouting will be called once and search for the 7 items.

Beware

Never ever attempt to define a list of multiple destinations using the standard SQL syntax WHERE NodeTo IN (......), because this will certainly cause many unexpected 'results'.
Badly formatted resultsets will be then returned, many of which may be wrong. You are warned.


How to correctly format multiple destinations lists

VirtualRouting always expects to receive a multi-destinations list as a TEXT string containing tightly packed values separated by a conventional delimiter (usually represented by a comma).
Examples of well formatted multi-destinations lists:
'1,2,3,4,5,10,100,1000,100000'   -- integer Node IDs

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

'  A100B, A100F , B250Z , C010M, Z999A  '      -- alphanumeric Node Codes
Note: all whitespaces immediately preceding or following the delimiter will be considered to be integral part of the value itself (and thus will also be searched for).
This will have no adverse consequences in the case of integer values, but can easily have catastrophic effects on alphanumeric values.

Defining a custom delimiter

Sometimes it could be useful setting up a delimiter other than a comma.
UPDATE byfoot SET Delimiter = '*';

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

Using MakeStringList() for auto-writing a list of multiple destinations

Writing by hand a Text String corresponding to a well-formatted list of multiples destinations could easily be a boring and error prone activity (most notably if the list contains a huge number of destination Nodes).
SELECT MakeStringList(node_id)
FROM (SELECT node_from AS node_id
      FROM roads
      WHERE ST_Length(geom) >= 10000.0
      UNION
      SELECT node_to AS node_id
      FROM roads
      WHERE ST_Length(geom) >= 10000.0);
----------------------------------------
12630,12648,13645,13651,78353,79142,79453,79454,286140,286153,286763,286770,291416,291417
The SQL aggregate function MakeStringList() is specifically intended to help and simplify this task by applying a pure SQL approach.
SELECT MakeStringList(node_id, ';')
FROM (SELECT node_from AS node_id
      FROM roads
      WHERE ST_Length(geom) >= 10000.0
      UNION
      SELECT node_to AS node_id
      FROM roads
      WHERE ST_Length(geom) >= 10000.0);
----------------------------------------
12630;12648;13645;13651;78353;79142;79453;79454;286140;286153;286763;286770;291416;291417


SELECT MakeStringList(node_id, '|')
FROM (SELECT node_from AS node_id
      FROM roads
      WHERE ST_Length(geom) >= 10000.0
      UNION
      SELECT node_to AS node_id
      FROM roads
      WHERE ST_Length(geom) >= 10000.0);
----------------------------------------
12630|12648|13645|13651|78353|79142|79453|79454|286140|286153|286763|286770|291416|291417
You can eventually pass an optional second argument to MakeStringList() in order to define an alternative separator different from comma.



6 - Solving Isochrone problems

Isochrones are areas (or curves) connecting points at which something occurs or arrives at the same time.
Isochrones are usually related to Network Analysis and Routing because they allow to easily identify which specific portion of the Network can be reached starting by some origin Node spending no more than a given Cost.

As you have already seen with multi-destination queries, the Dijkstra's Algorithm robustly ensures that when a destination is reached, all the destinations presenting a lesser cost have also been collected.
This allows to efficiently support Isochrone queries. You simply have to specify a single origin Node and a Cost threshold.

Note: executing an Isochrone query requires a processing time that isn't the sum of all individual timings for each destination, but simply is the time required to reach the most costly destination.
SELECT Algorithm, Request, Role, NodeFrom, NodeTo, Cost, Geometry
FROM byfoot
WHERE NodeFrom = 181999 AND Cost <= 1000.0;
You can call an Isochrone query as supported by VirtualRouting by specifying:
The following table shows the resultset returned by the above Isochrone query.

AlgorithmRequestRoleNodeFromNodeToCostGeometry
DijkstraIsochroneSolution181999178717572.455143BLOB sz=60 GEOMETRY
NULLNULLSolution181999178718587.303779BLOB sz=60 GEOMETRY
.............
NULLNULLSolution181999184035579.786724BLOB sz=60 GEOMETRY
NULLNULLSolution181999184036642.691597BLOB sz=60 GEOMETRY

Let's quickly examine the resultset returned by the above isochrone query.
Note: isochrone queries are not affected by configurable options. Algorithm will be always assumed to be Dijsktra, and the current Options settings will be simply ignored.
SELECT ST_ConcaveHull(ST_Collect(Geometry))
FROM byfoot
WHERE NodeFrom = 181999 AND Cost <= 1000.0;
Any isochrone query will just return a Point-set; if you also wish to obtain the corresponding areal representation you just have to call ST_Collect() in order to get a monolithic MultiPoint, then calling ST_ConcaveHull() in order to get a Polygon.


The map below graphically shows the results of the previous isochrone query.

isochrone