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 !