Whenever I travel from Tagish into Whitehorse, I’m faced with the same quandry; is shortest route the quickest route? Each option is ALMOST the same distance (~80 km); one way has lots of curves and better scenery, while the other is as close as we get to a freeway. As any gains I make in travel time to Whitehorse are eaten up in the first few blocks of city traffic anyway, the ‘ideal’ solution for the quickest OR shortest route could be found without taking the drive, using open source data and tools.
OpenStreetMap (OSM) provides up-to-date, comprehensive spatial data for everywhere in the world. The entire OSM data set (currently just shy of 40Gb) is freely available at openstreetmap.org , or you can download extracts of the data for a specified map extent, provided the area is not too large. Otherwise, bulk downloads are directed to one of several alternate mirror sites. OSM data for my neighbourhood, the ‘Golden Triangle’ of Whitehorse/Carcross/Jake’s Corner, was too large to download from the main link, so I followed the link to Overpass API to obtain the data for my desired map extents (~100Mb) . The downloaded OSM extracts can be readily imported into a database or GIS where I can derive a solution for the shortest path problem.
The dijkstra algorithm solves shortest path or fastest route for point to point connections (in 2D space). The algorithm requires the topology of the road network be known. Fortunately there are tools like QGIS, PostgreSQL/PostGIS and pgRouting that simplify construction of a topological model, enabling visualization of path alternatives and calculation of route distance and cost (time). osm2pgrouting takes care of loading OSM data into the database. For evaluating alternate route scenarios, the QGIS extension pgRoutingLayer provides routing functions directly in the QGIS interface.
sudo apt-add-repository -y ppa:ubuntugis/ppa sudo apt-add-repository -y ppa:georepublic/pgrouting sudo apt-get update sudo apt-get install postgresql-9.4-pgrouting sudo apt-get install osm2pgrouting
I have an existing QGIS, PostGIS/PostgreSQL installation[1,2,3]. Use the osm2pgrouting command to create PostGIS tables containing the topology (edges and nodes) and spatial reference data from the osm XML file :
osm2pgrouting -file map.osm \
-conf /usr/share/osm2pgrouting/mapconfig_for_cars.xml \
-dbname osmdata -user osmuser -clean
OUTPUT:
------------------------------------------------------
host=127.0.0.1 user=osmuser dbname=osmdata port=4321
connection success
Trying to load config file
Trying to parse config
Trying to load data
Trying to parse data
Split ways
Dropping tables...
Creating tables...
Nodes table created
2create ways failed:
Types table created
Way_tag table created
Relations table created
Relation_ways table created
Classes table created
Adding tag types and classes to database...
Adding relations to database...
Adding nodes to database...
Adding ways to database...
Creating topology...
NOTICE: PROCESSING:
NOTICE: pgr_createTopology('ways',1e-05,'the_geom','gid','source','target','true')
NOTICE: Performing checks, pelase wait .....
NOTICE: Creating Topology, Please wait...
NOTICE: 1000 edges processed
NOTICE: 2000 edges processed
NOTICE: 3000 edges processed
NOTICE: -------------> TOPOLOGY CREATED FOR 3053 edges
NOTICE: Rows with NULL geometry or NULL id: 0
NOTICE: Vertices table for table public.ways is: public.ways_vertices_pgr
NOTICE: ----------------------------------------------
Create Topology success
#########################
size of streets: 2102
size of splitted ways : 3053
finished
osm2pgrouting’s default configuration file includes a class structure for highways, cycleways, tracks and junctions. The alternative mapconfig_for_cars.xml is just the highways, so it was better suited for my purpose.
Next I added the OSM layers from the PostGIS database to my QGIS project. The pgRoutingLayer plugin provides an interface to run a shortest route algorithm(dijkstra). Set the required parameters for the function (source table, geometry field, cost field), choose source and target destination nodes from the map, and click ‘Run’. For shortest path, I set the cost parameter to use the length field. Using the intersection nearest my house as the source, and the junction of the two alternative routes as the target, I quickly confirmed my suspicion: the scenic route is shorter (79.9km vs. 80.43km).
But is it faster? To answer that question, I update the to_cost field in my ways table to the value of length/maxforward_speed to obtain an estimate of time (cost) for each segment of the network. Looking at the attributes, I notice the rated speed for the Alaska Highway route was 110, but the posted speed limit is 100kph. Meanwhile, the Tagish Road and Klondike Highway were rated (as posted) at 90kph. I adjusted the data to reflect more accurate travel speed and used that to calculate to_cost field. I update my cost parameter to the to_cost field and re-run the dijkstra(cost) function for the trip to find the least cost solution. Sure enough, the long route is quicker, by a whole 3 minutes (45 minutes vs 48 minutes). If I stay ahead of the School Bus !
[1]https://www.qgis.org/en/site/forusers/alldownloads.html#linux
[2]http://www.postgresql.org/download
[3]http://postgis.net/install/