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

back

Table of Contents

1 - Introduction

Theoretical foundations - an ultra-quick recall

• All items in the dataset are called Links (aka Arcs), and are expected to represent some oriented connection joining two Nodes.
  Example: in the above figure Link L3 connects Nodes N2 and N5.
• So all Links are always expected to explicitly reference a Start-Node (aka Node-From) and an End-Node (aka Node-To).
  • Links are always oriented, and their natural direction is From-To:
    • in an unidirectional Network each Link is an one-way connection.
      If the connection is available in the opposite direction a second Link must be explicitly declared.
      Example: Link X1 goes from Node A to Node B, and Link X2 goes from Node B to Node A.
    • in a bidirectional Network all Links are assumed to establish a connection in both directions.
      Definiting an one-way connection requires an appropriate attribute to be set (see below).
  • The Start- and End-Node could eventually be the same, and in this case we'll have a self-closed Link.
  • Network's Links can eventually define a linear Geometry (LINESTRING) going from the Start-Node to the End-Node, but this is an optional feature, not a mandatory requirement.
  • What is absolutely mandatory is that each Link must explicitly reference its Nodes.
• A Network supporting Geometries is a Spatial Network; otherwise a Network lacking any Geometry is a Logical Network.
  • In a Spatial Network all Links must have a corresponding Geometry.
  • In a Logical Network all Links are strictly forbidden to have any Geometry.
  • In a Spatial Network both the StartPoint and EndPoint of each Link's LINESTRING are always expected to exactly coincide with the corresponding Nodes.
• In a Spatial Network all references to the same Node by different Links must be an exact match.
  Example: Node N5 is shared by Links L3, L6, L7, L9 and L10, so all their corresponding LINESTRINGS are expected to have the corresponding extremity (Start- or End-, depending on the orientation) points that must exactly match the other.
  A topological inconsistency exists if any of these conditions are not satisfied, which leads to an invalid Network.
• In a Spatial Network two
• Accordingly to the above premises, Nodes are never expected to be explicitly declared in a separate Table.
  Just a single Table declaring all Links is required in order to fully define a topologically valid Network.
  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.
  If any mismatch is detected this surely means that the Network is invalid.
• A Link may legitimately self-intersect itself (e.g. forming a loop), as shown in the above figure by Link L15 (orange spot).
• Two Links may legitimately intersect where no Node exists, as exemplified on the above figure by Links L4 and L7 (green spot).
  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).
• Links aren't strictly required to be associated with any specific attribute, but the following attributes are almost universally supported:
  • a name identifying the Link.
    Examples: the road toponym in a road network, or the river name in an hydrographic network.
  • one (or even more) appropriate cost value(s).
    Example: the time required to traverse the Link (may be distinguished between pedestrians, bicycles, cars, lorries and so on).
  • a pair of boolean flags (from-to and to-from) are intendend to specify if the Link can be traversed on both directions or just in one (one-way).

Logical conclusions

• Hydrographic Networks.
• Gas / Water / Oil Networks.
• Electrical Networks.
• Telecomunication Networks.
• Social or Economical Networks representing relationships between individuals or companies.
• Epidemiological Networks representing the propagation of infective diseases between individuals or groups.

The Dijkstra's algorithm

• Any Node-to-Node connection identified by Dijkstra's is certainly ensured to be optimal.
  In other words, no connetction presenting a lower cost can conceptually exist.
• When Dijsjtra's fails to identify a solution this surely means that no solution is possible.

The A* algorithm

2 - The sample/test DB

• all road names are stored within the toponyms Table.
  the same road name could be used in different Municipalities, so the toponyms Table relationally references the municipalities Table (via PRIMARY / FOREIGN KEY relationships).
• the roads Spatial Table contains about 380,000 Links, and has the following columns:
  • id: unique identifier of each Link (PRIMARY KEY).
  • node_from and node_to: Node identifiers. The original Iter.Net dataset adopts very long an complex alphanumeric Node codes; the integer Node IDs were obtained by calling the CreateRoutingNodes() SQL function discussed in a following section.
  • id_toponym: relational reference to the corresponding road name contained into the toponyms Table (FOREIGN KEY).
  • speed_kmh: the estimated average speed supported by the Link, expressed in km/h.
    Note: negative speeds intend a forbidden Link.
  • oneway_fromto and oneway_tofrom: boolean flags intended to state if a Link can be traversed in both directions or just in a single direction (one-way).
    Note: all Links declaring oneway_fromto=0 and oneway_tofrom=0 are intended to be always forbidden.
  • cost: the time expressed in seconds required to traverse each Link.
    Note #1 all costs were calculated accordingly to the following formula: cost = ((ST_Length(geom) / 1000.0) / speed_kmh) * 3600.0
    Note #2 all 86,400.0 cost values (equivalent to 1 day) approximate an infinitive cost thus intending a forbidden Link.
  • geom: a 3D Linestring representing the Geometry of each Link.
    Note: the original Iter.Net dataset is just 2D; elevations (Z coordinates) were interpolated by draping the dataset over an orographic DEM (10m X 10m cells)
• the roads_vw Spatial View is just intended to fully resolve all relational references between roads, toponyms and municipalities, thus allowing for easier SQL queries.
• the house_nr Spatial Table contains about 1,480,000 House Numbers, and has the following columns:
  • id: unique identifier of each House Number (PRIMARY KEY).
  • id_road: relational reference to the corresponding Link contained into the roads Table (FOREIGN KEY).
  • label: the textual label fully qualifying each House Number.
  • geom: a 3D Point representing the Geometry of each House Number.
    Note #1: also in this case all elevations (Z coordinates) were interpolated by draping the dataset over the same DEM as above.
    Note #2: 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.
• the house_nr_vw Spatial View is just intended to fully resolve all relational references between house_nr, roads, toponyms and municipalities, thus allowing for easier SQL queries.

3 - Creating VirtualRouting Tables

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

SELECT CreateRouting('byfoot_data', 'byfoot', 'roads_vw', 'node_from', 'node_to', 'geom', NULL, 'toponym', 1, 1);
-------------
1

SELECT CreateRouting_GetLastError();
------------------------------------
NULL

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).

CREATE VIRTUAL TABLE test_network USING VirtualNetwork('some_data_table');

CREATE VIRTUAL TABLE test_routing USING VirtualRouting('some_data_table');

SELECT CreateRouting('bycar_data', 'bycar', 'roads_vw', 'node_from', 'node_to', 'geom', 'cost', 'toponym', 1, 1, 'oneway_fromto', 'oneway_tofrom', 0);
--------------------
1

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.
    • If set to FALSE an exception will be raised if the Binary Data Table and/or the VirtualRouting Table do already exist.
    • If set to TRUE eventually existing Tables will be preventively dropped immediately before starting the execution of CreateRouting().

Utility function for automatically setting NodeFrom and NodeTo IDs

SELECT CreateRoutingNodes(NULL, 'table_name', 'geom', 'node_from', 'node_to');
_________________________
1

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
: 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.

4 - Solving classic Shortest Path problems

SELECT * 
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = 183286;

• the first row (aka header row) has a special interpretation, and is intended to summarize the travel solution as a whole.
• all the following rows 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.
• columns Algorithm, Request, Options, Delimiter, PointFrom, PointTo, Tolerance and Geometry are always set to NULL except that in the first row of the resultset:
  • column Algorithm accounts for the Routing Algorithm used by the current query (Dijkstra's or A*).
  • column Request specifies the exact nature of the current query (in this specific case Shortest Path).
  • we'll ignore for now columns Options, Delimiter, PointFrom, PointTo and Tolerance: their respective meanings will be explained in following paragraphs.
  • column Geometry contains a LINESTRING representation of the whole travel solution.
    Note: on Logical Networks (not supporting Geometries) Geometry will always be NULL.
• we'll ignore for now column RouteId; its meaning will be explained in following paragraphs.
• column RouteRow simply is the progressive number of the row in the travel solution (always 0 in the header row).
• column Role can be Route (header row) or Link (all following rows).
• column LinkRowid references the ROWID of the corresponding Link (always set to NULL in the header row).
• column NodeFrom and NodeTo have the following interpretation:
  • in the header row they correspond to he Origin and Destination Nodes.
  • in all the following rows they are intended to specify the direction of the current Link.
• column Cost has the following interpretation:
  • in the header tow it corresponds to the total cost of the travel.
  • in all the following rows it represents the specific cost of the current Link.
• column Name contains the description of the current Link (usually a road name), and is always NULL in the header row.
  Note it could be always be NULL if the VirtualRouting Table does not supports names.

SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeTo = 178731 AND NodeFrom = 183286;

SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM bycar
WHERE NodeFrom = 178731 AND NodeTo = 183286;

SELECT RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM bycar
WHERE NodeTo = 178731 AND NodeFrom = 183286;

• yellow path: pedestrians
• green path: car, direct direction
• red path: car, return direction

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).

Playing with VirtualRouting configurable options

UPDATE byfoot SET Algorithm = 'A*';

SELECT Algorithm, Options, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = 183286;

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;

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;

UPDATE byfoot SET Options = 'SIMPLE';

SELECT Algorithm, Options, RouteRow, Role, LinkRowid, NodeFrom, NodeTo, Cost, Geometry, Name
FROM byfoot
WHERE NodeFrom = 178731 AND NodeTo = 183286;

5 - Solving multi-destination Shortest Path problems

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 overall layout is almost exactly the same as you've already seen in the case of single-destination queries, but in this case more individual travel solutions are grouped altogether.
• the first row of the resultset is someway exceptional, and is the unique row of the resultset presenting NOT NULL values in the Algorithm, Request, Options and Delimiter columns.
• the RouteId column is intended to group together all rows belonging to same travel solution (aka Route).
  Routes are progressively numbered and are ordered accordingly to their total cost.
• the RouteRow 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.
  RouteRow=0 always identifies the header row of each travel solution.

• Algorithm: only Dijkstra is supported by multi-destination; any attempt to use the alternative A* algorithm will simply return an empty resultset.
• Options: the usual FULL, SIMPLE, NO LINKS and NO GEOMETRIES are supported and will have the same effect as in single-destination queries.

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';

• Red star: the Origin Node.
• Green dots: the Destination Nodes.
• Yellow lines: all individual travel solutions.

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);

'1,2,3,4,5,10,100,1000,100000'   -- integer Node IDs

'A100B,A100F,B250Z,C010M,Z999A'  -- alphanumeric Node Codes

'  1, 2, 3, 4 , 5 , 10, 100, 1000, 100000  '   -- integer Node IDs

'  A100B, A100F , B250Z , C010M, Z999A  '      -- alphanumeric Node Codes

UPDATE byfoot SET Delimiter = '*';

SELECT Delimiter FROM byfoot;
------------------
* [dec=42, hex=2a]

6 - Solving TSP (traveling salesman) problems

1. computing all distances between pairs of cities. This is a typical ShortestPath problem, and we can duly use the Dijkstra's algorithm for this.
2. then we have to check all possible permutations / combinations so to identify the optimal TSP solution.

• TSP NN (aka Nearest Neighbour)
  This first algorithm is straightforwad simple and very fast; it can effectively solve huge TSP solutions (thousand cities or even more) in a very short time.
  Short description:
  • starting from the base city the salesman goes to the city presenting the lesser connection cost.
  • the already visited city is cancelled from the list, and then the salesman goes to the next city presenting the lesser connection cost.
  • the cycle continues until all cities in the list have been visited.
  • finally, the salesman returns to his/her initial base city
  Note it's very unlike that TSP NN could find the optimal solution, but it can quickly find some reasonable approximate solution (few is surely better than nothing).
  In the most unlucky case TSP NN could possibly return the worst solution, but the specific implementation adopted by VirtualRouting checks against this possibility:
  • each TSP NN is always computed twice by randomly choosing a different base city and then normalizing the solution; the best of the two solutions is then returned.
  • this simple but effective precaution robustly ensures that the worst solution will never be returned, and just implies a moderately increased execution time.
• TSP GA (aka Genetic Algorithm).
  This alternative algorithm is much more complex and sophisticated, and is directly inspired by biological concepts such as sexual reproduction, genetic mutations and natual selection.
  Short description:
  • a first initial set of solutions (the population) is created by using TSP NN after randomly choosing the base city and then normalizing each solution.
  • then during each step of the execution loop (generation) pairs of solutions sexually reproduces giving birth to children solutions; chromosome crossovers and random mutations intrinsically affect the reproductive process.
  • for each generation the natural selection eliminates all poorly fit individuals from the population and consequently only the best fit individuals can propagate their genome to next generation.
  • after a certain number of generations (let's say about some hundredth iterations) the optimal solution (or at least a fairly good sub-optimal solution) should finally emerge, and so the loop can exit.
• Note: TSP GA is usually expected to identify better solutions than TSP NN can do, but it will surely require much more time to complete.

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';

• the general layout is more or less the same as you've already seen in the case of ShortestPath queries.
• the first row of the resultset is someway exceptional, and is the unique row of the resultset presenting NOT NULL values in the Algorithm, Request, Options and Delimiter columns.
  It contains the TSP solution as a whole: column Cost is the total cost and column Geometry is the overall solution path.
• columns RouteId and RouteRow have the same interpretation as in multi-destination ShortestPath queries, but in this specific case each route corresponds to a connection between two cities.
  All routes are order accordingly to the running sequence of the TSP solution. RouteId=0 identifies the overall TSP solution.

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';

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';

• Red star: the base-city (from where the salesman) begins his/her trip.
• Green dots: the cities to be visited.
• Yellow line: the TSP solution (that is always a circular path).

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;

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