D 2018-04-16T13:30:23.355 L VirtualRouting P 2d771f3e54e2be5d42b6dc5e6fb8a21f06d156fa U sandro W 130021 back

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

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 on behalf of 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.
The contents stored into the sample database were opportunely rearranged, and are still subject to the initial CC-BY-SA 4.0 clauses (derived work).


3 - Creating VirtualRouting Tables

All VirtualRouting queries are based on some VirtualRouting Table, and in turn any VirtualRouting Table is based on some appropriate Binary Data Table supporting an efficient representation of the underlying Network.
So we'll start first by creating such tables.

The old and now superseded VirtualNetwork required using a separate CLI tool (spatialite_network) in order to properly initialize a VirtualNetwork Table and its companion Binary Data Table; alternatively spatialite_gui supported a GUI wizard for the same task. Since version 5.0.0 now SpatiaLite directly supports a specific 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 reduced form of CreateRouting) contains an intended error causing a failure and thus raising 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 is finally successful, and now CreateRouting() returns 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.

You've just used one of the partially reduced form of CreateRouting(); let's see in more depth all the arguments and their meaning:
  1. byfoot_data: the name of the Network Binary Data 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.
    We could have legitimately passed a NULL value for this argument in the case of a Logical Network.
  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 formulae and will be consequently 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 Binary Data Table is unchanged and is the same for both VirtualNetwok and VirtualRouting.
You can safely base a VirtualRouting Table on any existing Binary Data Table created by the spatialite-network CLI tool, exactly as you can base a VirtualNetwork Table on any Binary Data 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 Binary Data Tables created by the spatialite_network GUI tool and Binary Data 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 formulae 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 yet another time CreateRouting() now 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 intending an overwrite authorization.

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 can't be able to adequately support support the specific 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

Sometimes it could eventually happen to encounter some Spatial Network representation being fully topologically consistent but completely lacking any definition about NodeFrom and NodeTo identifiers.
In this specific case you can successfully recover a perfectly 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 meaning:
  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.
  4. node_from: name of the column to be added to the above Table and populated with appropriate NodeFrom IDs.
  5. 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

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.
A VirtualRouting Table is always based on a companion Binary Data Table, that is intrinsically static, 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.
The optimal frequency for cyclically refreshing the Routing Tables strictly depends on specific requirements, but the 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).
    The refresh activities could be opportunely planned at low traffic hours (e.g. during the night), and CreateRouting() could be usefully called by enabling the overwrite option.
  2. medium-high frequency refresh: best fit for quickly 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 be unacceptable.
    In this case you could usefully 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 between an interval and the other.
      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).
      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 Binary Data Table following the correct sequence of SQL commands is paramount.
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.
  1. you are always expected to DROP first the VirtualRouting Table.
  2. you can safely DROP the companion Binary Data Table only once it's no longer referenced by the VirtualRouting Table.
  3. by following the reverse sequence you'll directly create an orphan VirtualRouting Table that cannot be accessed any longer, and that will consequently refuse to be dropped.
    Be 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 request the meaningful 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

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


Now you'll go to 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 easily notice, the optimal paths returned by the bycar VirtualRouting Table the paths in opposite directions strongly differ between them, and both are completely different from the path returned by querying byfoot.
A quick glance at the below map will surely 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; circulating by car is discouraged and is subject to many one-way restrictions. Not surprisingly, moving 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(, 30.0, 45.0); SELECT ST_Locate_Between_Measures(, 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; If you 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 select again 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 eventually 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 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; please notice the value in the Options column.

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 someway 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 select again the initial standard setting you just have to execute
UPDATE byfoot SET Options = 'FULL';.


5 - Solving multi-destination Shortest Path problems

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 lesser cost have already been reached in some previous step of the process.
This allows to efficiently support multiple destinations Shortest Path queries. You simply have to specify a single origin Node and an arbitrary list of destination Nodes in a single Dijkstra's execution.

Note: executing a multi-destination Shortest Path 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 of all destinations in the list.
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. 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 easily notice, a multiple-destinations query has the same identical form of any usual Shortest Path query, except in that NodeTo now corresponds to a comma-separated list.
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.
This was purposely intended: 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 slightly differ 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 discouraging from doing such a thing, let's see why.
SQLite will process a request written this way by repeatedly calling VirtualRouting passing each time a single Destination; and consequently VirtualRouting 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.

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 troubles.
Badly formatted resultsets will be then returned, may be containing wrong results. 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.
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 different from 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.




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 about multi-destination queries, the Dijkstra's Algorithm robustly ensures that when a destination is reached all the destinations presenting a lesser cost have already been reached in some previous step of the process.
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; An Isochrone query as supported by VirtualRouting just requires to specify:
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 eventually 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 previous isochrone query.

isochrone