@mraross commented on Tue Mar 06 2018

Take time-dependent and time-independent turn restrictions into account when computing best route.
Turn restrictions are often conditional as in No Left Turn 4 PM - 6PM weekdays

Time-independant turn restrictions are sourced from the BC Digital Road Atlas

@mraross commented on Thu Mar 08 2018

An example is a road that is closed to oversized vehicles in winter.

@mraross commented on Thu May 24 2018

Given outcome of time-dependent routing algorithm evaluation, decide whether or not to proceed with time-dependent routing.

@mraross commented on Fri Jun 01 2018

Issue moved to bcgov/ols-router #3 via ZenHub

@mraross commented on Sat Dec 23 2017

routeOptimizer.api.gov.bc.ca is an asynchronous api like CPF. A user submits a route to be optimized and gets a jobID immediately in response. They can then poll for status and, when the results are ready, they are returned (so no need to go to download page). Unlike CPF, the route optimizer only allows one route in a single request.
This allows routeOptimizer to handle optimizations that take longer than our reverse proxy timeout period which is currently one minute. It also allows us to specify various forms of the Vehicle Routing Problem such as 600 stops (e.g., home care clients) served by 12 vehicles (e.g., home care providers), each with its own depot (e.g., provider residence).

The route optimizer api replaces the need for the route optimization javascript library but it does put more load on our servers.
We still need to determine maximum allowed complexity of a given problem (e.g., maxRouteStops<globalMaxRouteStops where maxRouteStops=stopCount * vehicleCount). When we learn the relationship between problem complexity and execution time, we can specify limits in terms of time.

The current router optimizer can be limited to a TSP that can be solved within 10 seconds (e.g., 12 stops?).

@mraross commented on Mon Dec 25 2017

We can decide on server-side vs client-side optimizer when we get to low priority tasks

@mraross commented on Wed Nov 16 2016

Will need to load latest ferry schedules and require client to provide a start date/time. Real-time schedule changes/delays are out of scope.

We expect the ferry schedule will be available in General Transit Feed Service (GTFS) format. For details, see https://developers.google.com/transit/

@cmhodgson commented on Wed Nov 16 2016

Some initial questions:

• how do we get the ferry schedule and how often does it update, and by what mechanism?
• does graphhopper support time-of-day based queries with dynamic costs such as this?

@mraross commented on Wed Nov 16 2016

Don't know where or how. Could break estimate into two parts:

1. Ferry schedule data prep (largely unknown effort)
2. Using ferry schedule in route planning (largely known effort)

There are also two levels of ferry scheduling:

1. Static- based on seasonally published schedules
2. Dynamic -based on notifications of sailing delays or cancellations

@cmhodgson commented on Fri Nov 18 2016

It doesn't look like Graphhopper supports time-of-day based routing. I don't think it can be hacked on because we need to know the current time (based on the segments traversed so far) in order to determine the cost of a given segment. To be efficient, the routing algorithm needs to maintain a current time as it walks around the graph, otherwise we might have to recalculate it at every step.

@mraross commented on Fri Mar 03 2017

When computing best route, the Route Planner needs to take into account the following:

1. User-defined start time
2. Time-dependent turn restrictions
3. Time-dependent road restrictions
4. Scheduled and real-time road events
5. Ferry schedules
6. Historic traffic congestion

Taking these factors into account will require:

"... a practical algorithm that, while robust to user preferences, is able to integrate global changes of the time-dependent metric (e. g., due to traffic updates or user restrictions) faster than previous approaches, while allowing subsequent queries that enable interactive applications."
Source: https://arxiv.org/pdf/1512.09132.pdf

@mraross commented on Thu May 24 2018

This looks like a promising approach to implementation:

Dynamic Time-Dependent Routing in Road Networks Through Sampling
http://drops.dagstuhl.de/opus/volltexte/2017/7897/pdf/OASIcs-ATMOS-2017-3.pdf

Intriguingly Simple and Efficient Time-Dependent Routing in Road Networks
https://arxiv.org/pdf/1606.06636.pdf

Experimental implementation of TD-S (based on RoutingKit)
https://github.com/ben-strasser/td_p

Experimental implementation of FlowCutter (used in TD-S)
https://github.com/ben-strasser/flow-cutter-pace16

Customizable Contraction Hierararchies (CCH)
https://arxiv.org/pdf/1402.0402.pdf

C++ Implementation of CCH
https://github.com/RoutingKit/RoutingKit

Computing tree decompositions with tree cutter
https://arxiv.org/pdf/1709.08949.pdf

Graph cutting with Pareto Optimization (FlowCutter)
https://arxiv.org/pdf/1504.03812.pdf

Computing tree decompositions with FlowCutter
https://arxiv.org/pdf/1709.08949.pdf

@mraross commented on Mon Mar 26 2018

More papers on time-dependent routing

Dynamic, time-dependent route planning in road networks with user preferences
https://arxiv.org/abs/1512.09132

Customizable Route Planning
http://i11www.iti.kit.edu/extra/publications/dgpw-crp-11.pdf

Computing time dependent travel times in vehicle routing problems
http://essay.utwente.nl/72040/1/20170306%20-%20Publiceren%20thesis%20van%20Mathijs.pdf

How to build a real-time vehicle route optimizer
http://www.opendoorlogistics.com/assets/pdfs/How-to-build-a-real-time-vehicle-route-optimiser.pdf

Intriguingly simple and Fast Transit Routing
https://pdfs.semanticscholar.org/a892/a54b02ce112e1302931231141a8b676b873b.pdf

Engineering Time-Dependent Many-to-Many Shortest Paths Computation
http://drops.dagstuhl.de/opus/volltexte/2010/2751/pdf/7.pdf

Vehicle routing under time-dependent travel times: the impact of congestion avoidance
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.208.3905&rep=rep1&type=pdf

The Time-Dependent Shortest Path and Vehicle Routing Problem
https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2017-57.pdf

Time-Dependent Route Planning with Generalized Objective Functions
http://algo12.fri.uni-lj.si/reg/proc/presentations/MUAQVhDxhsoheZshATmODHmQi.pdf

A Survey of Shortest Path Algorithms
https://arxiv.org/pdf/1705.02044.pdf

Dynamic Vehicular Route Guidance usingTraffic Prediction Information
https://www.hindawi.com/journals/misy/2016/3727865/

Self-aware traffic route planning
http://gamma.cs.unc.edu/TROUTE/AAAI2011-2.pdf

Time dependent route planning
https://pdfs.semanticscholar.org/f21c/47d7fac0a291647cd1211ce79349b5f47a80.pdf

@mraross commented on Tue May 22 2018

Spatio-temporal traffic flow forecasting on a city-wide sensor network
https://projekt.beuth-hochschule.de/fileadmin/projekt/magda/Presentations/GISOV2017_Kunde_Hartenstein_Sauer.pdf

Nice animation of contraction hierarchies
https://www.mjt.me.uk/posts/contraction-hierarchies/

Nice exposition of CH
http://www.fmi.uni-stuttgart.de/files/alg/teaching/s15/alg/CH.pdf

Using OSRM as a CH testing platform
http://snap.stanford.edu/class/cs224w-2014/projects2014/cs224w-10-final.pdf

@mraross commented on Thu May 24 2018

Looking ahead to road restrictions, check out:
Fast Exact Shortest Path and Distance Queries on Road Networks with Parameterized Costs
https://arxiv.org/pdf/1509.03165.pdf

@mraross commented on Fri Jun 01 2018

Issue moved to bcgov/ols-router #1 via ZenHub

@gleeming commented on Wed May 02 2018

There are road features in ITN with street names of "emergency lane". These are typically short connectors between divided segments and not at an intersection crossing. While they are useful to model for emergency vehicle routing, they are not intended for general public use and our route planner.

An example is the connector about 60m NW from 4000 Seymour Pl building on the hill between the south- and north-bound lanes of Blanshard St. More impactful cases exist on limited access divided highways, where unwanted and illegal u-turn routes can currently be created.

These emergency lanes mostly have a road class of lane (valid for general routing) so they can only be distinguish by their street name. It is possible that there are other similar types of features in ITN that should be excluded from the network.

Copy comment From: 79:
Add an isEmergencyResponder Boolean parameter. if true, route can use emergency lanes.

@mraross commented on Mon Mar 26 2018

1. Evaluate existing algorithms that support dynamic and time-dependent route planning with user preferences and make a recommendation.

2. Evaluate existing timetable-based routing algorithms to support ferry routing and make a recommendation.

3. Determine how to best integrate recommended algorithms.

4. Write up findings and recommendations in an Advanced Routing Algorithm Evaluation document

5. Implement recommended algorithms

@mraross commented on Fri Jun 01 2018

Issue moved to bcgov/ols-router #2 via ZenHub

@mraross commented on Fri Jun 01 2018

Issue moved to bcgov/ols-router #4 via ZenHub

@mraross commented on Thu May 24 2018

Given outcome of time-dependent routing algorithm evaluation, decide whether or not to proceed with time-dependent routing.

@mraross commented on Fri Jun 01 2018

Issue moved to bcgov/ols-router #3 via ZenHub

@mraross commented on Wed Jun 13 2018

Issue moved to bcgov/ols-router #7 via ZenHub

@mraross commented on Tue Jun 05 2018

Review requirements related to time-dependency and restriction scope (e.g., permitting region, geographic area, line geometry, line defined by two intersections along a road)

Model intersection traversal costs based on:

1. Type of traffic control (e.g., traffic lights, stop sign, yield sign)
2. Street types involved (e.g., highway to arterial, arterial to residential)
3. Type of traversal (e.g., straight through, left turn, right turn, roundabout)

@mraross commented on Thu Apr 27 2017

Add a penalty to route cost for each turn at an intersection. For example, turning left should be penalized more than turning right which should be penalized more than heading straight through.

Ideally, time-dependent turn penalties should be based on data coming from a Provincial Traffic Service that provides real-time and historic traffic data. If no such service is forthcoming, historic traffic data from the BC Ministry of Transportation and Infrastructure and BC municipalities should be used.

Put turn costs on a switch (disable parameter).

@cmhodgson commented on Mon May 01 2017

The code for adding intersection delays is already written. The difficulty is in fixing the data so that when the router uses the turn delays, weird things don't happen. We propose spending 1-2 days investigating the problems in the data to better understand their nature. We should the discuss them with the ITN team to see if they are interested in working towards resolving them, and/or if we need to figure out how to resolve them on our end. Issues we know about involving turn restrictions on channelized right-turn lanes would best be handled (stored) in ITN.

@mraross commented on Mon Jan 29 2018

Modelling turn restrictions
https://blog.mapbox.com/smart-directions-powered-by-osrms-enhanced-graph-model-3ae226974b2

A Hybrid Link-Node Approach for Finding Shortest Paths in Road Networks with Turn Restrictions
http://onlinelibrary.wiley.com/doi/10.1111/tgis.12133/pdf

Modelling turning restrictions in traffic network for vehicle navigation system
http://www.isprs.org/proceedings/XXXIV/part4/pdfpapers/410.pdf

Efficient Routing in Road Networks with Turn Costs
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.661.3226&rep=rep1&type=pdf

Route Planning in Road Networks with Turn Costs
http://algo2.iti.kit.edu/documents/routeplanning/volker_sa.pdf

@mraross commented on Fri Mar 03 2017

@cmhodgson commented on Fri Apr 21 2017

Support was already added for FERRY_PASSENGER.

@mraross commented on Fri Apr 21 2017

At MOTI's request, BC Ferries is going to create new ferry classes this fiscal to distinguish local from express so that routers won't jump from one the other at common docks.

@cmhodgson commented on Fri Apr 21 2017

Why would we not change ferries at a dock? What does "support" mean in terms of the geocoder? Just add them to the accepted road classes? Ferries segments don't have addressing anyway, I think we just need to ignore them at some level.

@mraross commented on Fri Apr 21 2017

I might not have the new typology right but from what I recall, OnRoute was having trouble routing with the current ferry classes and we would too if BC Ferries didn't add new ferry classes

@mraross commented on Wed Nov 16 2016

This will require polling a road event notification service (e.g.,Open511) for real-time events and updating the live road network model appropriately and unobtrusively. The BC Ministry of Transportation provides an Open511 service and BC municipalities may also provide their own.

Real-time road events include unscheduled road repairs, spills, animal encounters, accidents, mudslides, wildfires, flooding, etc. and require restrictions such as road or lane closures, reduced speed limits, or travel direction reversals. The routing algorithm should take these restrictions into account when computing best route.

Only road events that apply to all vehicles are honoured. Road events that only apply to oversized vehicles are out of scope.

Road events will include an affected area that may be specified as a geographic point, line, or area. They may also have one or more road segment ids.

@cmhodgson commented on Wed Nov 16 2016

Initial questions:

• where do we retrieve the open511 data, what mechanism to retrieve and load it
• similar to ferry scheduling problem

@mraross commented on Wed Nov 16 2016

There is an open511 web service in production that provides road incidents on BC highways. For details, see https://catalogue.data.gov.bc.ca/dataset/open511-drivebc-api

This web service is hosted and administrated by MOTI

@cmhodgson commented on Thu Nov 17 2016

The service is nice. We would need to query it regularly for updates and keep all current and future event info stored in the router app. Notable is that none of the current events listed actually include a '+delay' field, meaning that they would have no effect on the routing right now. Some past events do include this information, although the only value I saw was a relatively coarse '+30'. Certainly the service provides the information necessary to add delays where they are specified.

There is a lot of other information in the service, eg. textual descriptions of events, schedules for planned events, etc., would we do anything with that? How would this information be returned in the various output formats, and query types? Perhaps delay time should be a separate field, possibly ferry delay time should be separate from road event delay time? Do the events make an additional line of directions, or are they added to the existing lines?

We would probably want a parameter to specify whether or not to take this information into account. It also requires a date and time of travel, similarly to the ferry scheduling issue.

The application would need a separate thread to retrieve the data from the open511 service, and possibly a monitor thread to restart the data thread if it dies. CPF has more threads than this but it has a monitoring interface so you can see what is going on... I'm just worried that we need some kind of notification system to know when the app has failed to retrieve the open511 data for any reason, for too long.

@cmhodgson commented on Fri Nov 18 2016

It doesn't look like Graphhopper supports time-of-day based routing. This means we may need an entirely different approach in order to support at least scheduled events. Realistically though the time-of-day support is pretty much necessary for open511 to make sense. At very least you are making the assumption that you are leaving "now".

@mraross commented on Fri Mar 03 2017

When computing best route, the Route Planner needs to take into account the following:

1. User-defined start time
2. Time-dependent turn restrictions
3. Time-dependent road restrictions
4. Scheduled and real-time road events
5. Ferry schedules
6. Historic traffic congestion

Taking these factors into account will require:

"... a practical algorithm that, while robust to user preferences, is able to integrate global changes of the time-dependent metric (e. g., due to traffic updates or user restrictions) faster than previous approaches, while allowing subsequent queries that enable interactive applications."
Source: https://arxiv.org/pdf/1512.09132.pdf

@mraross commented on Thu May 24 2018

This looks like a promising approach to implementation:

Dynamic Time-Dependent Routing in Road Networks Through Sampling
http://drops.dagstuhl.de/opus/volltexte/2017/7897/pdf/OASIcs-ATMOS-2017-3.pdf

Intriguingly Simple and Efficient Time-Dependent Routing in Road Networks
https://arxiv.org/pdf/1606.06636.pdf

Experimental implementation of TD-S (based on RoutingKit)
https://github.com/ben-strasser/td_p

Experimental implementation of FlowCutter (used in TD-S)
https://github.com/ben-strasser/flow-cutter-pace16

Customizable Contraction Hierararchies (CCH)
https://arxiv.org/pdf/1402.0402.pdf

C++ Implementation of CCH
https://github.com/RoutingKit/RoutingKit

Computing tree decompositions with tree cutter
https://arxiv.org/pdf/1709.08949.pdf

Graph cutting with Pareto Optimization (FlowCutter)
https://arxiv.org/pdf/1504.03812.pdf

Computing tree decompositions with FlowCutter
https://arxiv.org/pdf/1709.08949.pdf

@mraross commented on Mon Mar 26 2018

More papers on time-dependent routing

Dynamic, time-dependent route planning in road networks with user preferences
https://arxiv.org/abs/1512.09132

Customizable Route Planning
http://i11www.iti.kit.edu/extra/publications/dgpw-crp-11.pdf

Computing time dependent travel times in vehicle routing problems
http://essay.utwente.nl/72040/1/20170306%20-%20Publiceren%20thesis%20van%20Mathijs.pdf

How to build a real-time vehicle route optimizer
http://www.opendoorlogistics.com/assets/pdfs/How-to-build-a-real-time-vehicle-route-optimiser.pdf

Intriguingly simple and Fast Transit Routing
https://pdfs.semanticscholar.org/a892/a54b02ce112e1302931231141a8b676b873b.pdf

Engineering Time-Dependent Many-to-Many Shortest Paths Computation
http://drops.dagstuhl.de/opus/volltexte/2010/2751/pdf/7.pdf

Vehicle routing under time-dependent travel times: the impact of congestion avoidance
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.208.3905&rep=rep1&type=pdf

The Time-Dependent Shortest Path and Vehicle Routing Problem
https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2017-57.pdf

Time-Dependent Route Planning with Generalized Objective Functions
http://algo12.fri.uni-lj.si/reg/proc/presentations/MUAQVhDxhsoheZshATmODHmQi.pdf

A Survey of Shortest Path Algorithms
https://arxiv.org/pdf/1705.02044.pdf

Dynamic Vehicular Route Guidance usingTraffic Prediction Information
https://www.hindawi.com/journals/misy/2016/3727865/

Self-aware traffic route planning
http://gamma.cs.unc.edu/TROUTE/AAAI2011-2.pdf

Time dependent route planning
https://pdfs.semanticscholar.org/f21c/47d7fac0a291647cd1211ce79349b5f47a80.pdf

@mraross commented on Tue May 22 2018

Spatio-temporal traffic flow forecasting on a city-wide sensor network
https://projekt.beuth-hochschule.de/fileadmin/projekt/magda/Presentations/GISOV2017_Kunde_Hartenstein_Sauer.pdf

Nice animation of contraction hierarchies
https://www.mjt.me.uk/posts/contraction-hierarchies/

Nice exposition of CH
http://www.fmi.uni-stuttgart.de/files/alg/teaching/s15/alg/CH.pdf

Using OSRM as a CH testing platform
http://snap.stanford.edu/class/cs224w-2014/projects2014/cs224w-10-final.pdf

@mraross commented on Thu May 24 2018

Looking ahead to road restrictions, check out:
Fast Exact Shortest Path and Distance Queries on Road Networks with Parameterized Costs
https://arxiv.org/pdf/1509.03165.pdf

@mraross commented on Sat Apr 07 2018

Add cardinal directions to start of route and start of any reversals (going out the way you came). For example: Try this route in demo app:

16357 Hwy 2, Tupper, BC
16972 201 Rd, Tupper, BC
562 188 Rd, Tupper, BC

The first instruction is:

Continue onto Hwy 2 for 1.3 km (46 seconds)

but would be more helpful if it said:

Go east along Hwy 2 for 1.3 km (46 seconds)

The first instruction after Stopover 1 is:

Continue onto 201 Rd for 4 km (5 minutes 56 seconds)

but it is actually not a continuation in the same direction but a reversal. We were going south. Now we need to go north as follows:

Go north along 201 Rd for 4 km (5 minutes 56 seconds)

or even

Turn around and go north along 201 Rd for 4 km (5 minutes 56 seconds)

@mraross commented on Fri Jan 19 2018

Add a roadSurface parameter that allows a user to prefer or avoid certain road surfaces (e.g.,pavement, gravel). This parameter is found in MapQuest and other routing APIs. By default, the route planner should prefer paved and gravel surfaces and avoid decommissioned, overgrown, and unknown surfaces.

Here's are some examples:
&roadSurface=-loose;-gravel;-rough;+paved;-decommisioned;-overgrown;-unknown
&roadSurface=+paved;+gravel

@mraross commented on Sat Feb 03 2018

This looks like a promising approach to implementation:

Fast shortest path with parameterized costs
https://arxiv.org/pdf/1509.03165.pdf

@mraross commented on Tue Mar 06 2018

Take traffic congestion into account when computing best route.

Ideally, traffic congestion should be based on data coming from a Provincial Traffic Service that provides real-time and historic traffic data. If no such service is forthcoming, historic traffic data from BC Ministry of Transportation and Infrastructure, Greater Vancouver Transportation Board (Translink), and other BC municipalities should be used.

Traffic congestion should be provided for each road segment in the form of a speed, not a time delay as suggested in:

https://www.graphhopper.com/blog/2018/04/26/travel-time-calculations-for-traffic-and-time-dependent-vehicle-routing-problems/

In other words, traffic data should contain currentSpeed and averageSpeed; not currentDelay and averageDelay. Ideally, averageSpeed will be provided for each significant time interval during the day (e.g., AM rush hour, PM rush hour, mid-day, evening, night) and for a single average day, for an average weekday and an average weekend day, or for each distinct day of the week.

For cooked data, we could derive averageSpeed based on road type and maxSpeed of road segment for each time interval. In other words, keep a table of friction factors ( 0< f <= 1), one for each road type and time interval.

For cooked real-time data, the simplest approach is to derive currentSpeed in the same way as averageSpeed but with different values.

Another approach is to make currentSpeed a function which returns a random speed from within an speed interval appropriate for the time window (e.g., AM rush, PM rush, The random selection should be done periodically (e.g., once every 5 minutes), not on every request. For example:

function currentSpeed(timestamp:DateTime, roadType:String)
if lastSpeed.isNull or (timestamp.minutes mod minuteInterval) = 0 then
lastSpeed := random speed within range of current time window for given roadType
return lastSpeed
else
return lastSpeed
endif
end function

Traffic data for designated truck routes might be a sufficient starting point.

@mraross commented on Fri Jan 19 2018

If no route that meets all road restrictions can be found, ignore road restrictions that are designated as soft, and try to find a route again. An example of a hard restriction is a vehicle height restriction due to a bridge; a soft route restriction is a vehicle height restriction due to an overhanging sign which can be temporarily raised or removed.

Weakening the attraction of designated routes may also be required to find a route.

@mraross commented on Wed Nov 16 2016

Here's a U-turn in a divided intersection:

Start: 988 Topaz Ave, Victoria, BC -123.360677,48.442561
End: 710 Redbrick St, Victoria, BC -123.368386,48.444587

https://router.api.gov.bc.ca/route.kml?points=-123.360677%2C48.442561%2C-123.368386%2C48.444587&outputSRS=4326&criteria=shortest&distanceUnit=km&apikey=yourApiKey

@cmhodgson commented on Wed Nov 16 2016

Divided intersections are currently modeled as two separate intersections. In order to support this restriction, we would need to identify that these are actually the same intersection, and/or support turn restrictions in general.

@cmhodgson commented on Wed Nov 16 2016

This is a duplicate of #69

@mraross commented on Wed Nov 16 2016

Closed issue 69. Need to know if a change to ITN data model is required to support this restriction or if we can write a script to derive this restriction for every divided road intersection and what effort would be required.

@cmhodgson commented on Thu Nov 17 2016

In the current ITN model, a U-turn at a divided intersection actually looks like two consecutive left turns, which are each possibly legal turns. It is only the two turns in succession that are not allowed, and graphhopper does not support such a restriction. We cannot disallow all cases of two left-turns in quick succession because in some places this is allowable and even necessary.

One approach would be to "pinch" the intersections together into a single point, and apply many turn restrictions to ensure correct travel, but it is not clear how well we can identify these intersections. It would also affect the visualization of the route, unless we did extra work to convert the intersection back to its non-pinched form after the routing work is done.

Another approach might be to assign identifiers to all such intersections, and prevent multiple turns made at the same intersection - but I'm not sure if we can do this restriction in graphhopper, either.

@gleeming commented on Thu Nov 17 2016

The Enhanced Intersection data managed by GeoBC for ICBC maps each physical intersection point into logical intersections. This might be useful in allowing us generate restrictions for standard double line intersection cases (1x2 or 2x2, plus possibly some turn lanes) and prevent U-turns, However interchanges and larger complex intersections (some over 100 nodes) might be too broad to allow application of generic rules.

Not sure of the cost, openness or frequency of update of the EI data, so this may not really be suitable for our needs.

@cmhodgson commented on Tue May 30 2017

Routing code should identify and prevent such u-turns at divided roads, programatically, at route-time.

@mraross commented on Fri Jun 23 2017

For example, a truck route must follow designated truck routes; in an evacuation, all vehicles must follow designate evacuation routes. Emergency vehicles may route through roads restricted to emergency vehicles; other vehicles can't.

The BC Ministry of Tranportation and Infrastructure describes designated routes as a preference ranking where each road segment has a low, medium, or high preference (or attraction) for certain types of vehicle.

Route designations may come from the BC Digital Road Atlas or directly from the BC Ministry of Transportation and Infrastructure and BC municipalities

@mraross commented on Sat Feb 03 2018

This looks like a promising approach:

Fast shortest path with parameterized costs
https://arxiv.org/pdf/1509.03165.pdf

@mraross commented on Tue Mar 21 2017

roadVoronoi takes a set of points and returns a list of (blockID, pointID) pairs, one pair for each block in DRA. This basically precomputes the nearest point to a given block for every block in DRA.

In address prep, run roadVoronoi for each occupant type (as determined by some tagging convention), and store the results

@cmhodgson commented on Tue May 30 2017

This service will use the same back-end functionality as the service area pre-processing.

@mraross commented on Thu Mar 08 2018

An example of a real-time road event is a severe storm that requires a reduction in max vehicle weight along certain roads for the next few days.

Road elevation is needed to more accurately compute distance and to determine turn restrictions for trucks that are based on slope.

@mraross commented on Tue Nov 15 2016

This requires the ability to load road segments that have a third, Z coordinate for elevation and taking elevation into account when computing distance along a road segment.

This depends on the availability of BC Digital Road Atlas road segment data containing Z coordinates.

@cmhodgson commented on Wed Nov 16 2016

We need more information about how we would get this data, what it is, and what would we do with it?

@mraross commented on Wed Nov 16 2016

Estimate the effort for loading elevation data into graph hopper from a elevation data file that graph hopper supports. Estimate the effort of transforming the elevation data into a form required by Graph hopper.

Elevation is currently accessible from the following WFS:
https://devoas1.apps.th.gov.bc.ca/ogs-geoV06/plg/ows?service=WFS&version=1.0.0&request=Getcapabilities

This is probably adequate for a pilot in a small area but we will need a more efficient format for production (e.g., file download in CSV format).

@cmhodgson commented on Thu Nov 17 2016

The Graphhopper routing algorithm supports 3-d points on the graph linework, which we load from the GeoJSON file that comes out of the geocoder processing, from ITN. We don't even need graphhopper to do anything, we would just calculate the weight of the segments based on the 3-d length rather than the 2-d length, assuming this is the goal of this ticket? We could also add a maximum grade restriction, by calculating and tagging every segment with the maximum grade?

In order to get the z-values onto the ITN we would need to conflate the MoT segments with the ITN, likely at every monthly data processing, which might be possible with FME, but might require a more complicated process. If the matching segments have different vertices, how would we distribute the Z-values along the matched segment, being careful not to affect the calculated grade? I've not yet seen a solution to this sort problem that is entirely automated.

A more realistic approach would be to calculate the 3-d distance on the MoT segments, and also potentially the maximum grade, and then add that information to the ITN road network, based on the ITN IDs - this makes the assumption that we have ITN IDs available in the MoT data, or some other way to easily match up the linestrings between ITN and MoT.

@mraross commented on Thu Dec 01 2016

I like the realistic approach of computing 2.5D distance and maximum grade on road segments using MoT roads and possibly TRIM. This does sound like something GeoBC should be doing though.

@cmhodgson commented on Fri Apr 28 2017

Have we resolved my comment from Nov 17? Do we know how we would get the z-values onto the linestrings?

@mraross commented on Fri Apr 28 2017

GeoBC said they will be adding Z to road points by end of fiscal. They will be building a new DEM to drape the road geometry over. Does graphhopper handle (x,y,z) points?

@cmhodgson commented on Mon May 01 2017

Yes. as I said earlier in the comments, graphhopper does support 3-d coordinates, we just have to tell it to do 3-d distance calcs. This should be fairly trivial, will just require some testing.

@mraross commented on Wed Nov 16 2016

Add a time-dependent penalty to route cost to account for delays at traffic lights and stop signs.

Ideally, time-dependent penalties for stop signs and traffic lights should be based on data from a Provincial Traffic Service that provides real-time and historic traffic data. If no such service is forthcoming, historic traffic data from the BC Ministry of Transportation and Infrastructure and BC municipalities should be used.

@cmhodgson commented on Wed Nov 16 2016

Doing this using the current data causes weird routing behaviour due to missing traffic impactors and missing implied turn restrictions. The data must be improved or we need to somehow fabricate missing information in order for this to work reasonably. One approach might be to add stop costs to the route after Graphhopper determines the fastest route without considering stop costs. A technical discussion will be required to determine the approach to this.

@mraross commented on Wed Nov 16 2016

MOTI is now supplying traffic impactors on highways to GeoBC on a regular basis. Maybe we could just take it into account on highways only for now. We could estimate the extent of the missing impactors in urban areas and have MOTI raise the issue with GeoBC as it does affect the quality of route plans in OnRoute.

@gleeming commented on Wed Nov 16 2016

It is more than just accurate impactor data that is required. We would still also need data for, or a way to fairly accurately generate, turn restriction information near the highways. Picture heading northbound on Douglas with a light delay at Saanich road. This will cause the route to take the turn lane right onto Saanich, then across the road (it is a single line) and immediately take the turn lane back onto Douglas northbound. It looks similar to other "4-way" intersections. In the network that route is faster once a delay is introduced, but as EComm/BCAS puts it not a manoeuver in the best interests of public safety.

@mraross commented on Wed Nov 16 2016

We could determine the extent of missing turn restrictions and feed that back to GeoBC.

Overall, we want to know what the obstacles are and get talking to the agencies that can help remove them.

@cmhodgson commented on Thu Nov 17 2016

We have identified a few classes of issues that cause problems with routing when stop delays are factored in. Even if we were able to fix all such issues, it is likely that we would discover more issues after that. We cannot reliably estimate how long it would take us to identify "enough" issues for the routing to work "acceptably." It would require an iterative approach.
The difficulty is that introducing the stop costs turns up the sensitivity of the routing network to errors in the stop costs and in the turn restrictions, significantly. In a generally grid-like road network, there are many routes across the network with near-identical distances (and thereby, times), it only takes one missing stop sign, or one free left-turn, in order to make any route including that path significantly better than all other routes.

@cmhodgson commented on Mon May 01 2017

We cannot only apply traffic impactors on highways; the result of this would be to use the "back roads" that don't have traffic impactors, because it saves you the time at the lights. As for #192 we need to investigate the problem and work with ITN on the data, then we can start making use of the already written code, which will likely require a lot of tweaking to the costing (which is calculated statically at startup, requiring a restart to change) to figure out a good balance of costs.

@cmhodgson commented on Wed May 31 2017

I have already implemented most of the code to support this. If we added some stop costs to the config tables and set them to 0 until we have better data, I could enable this code, set it up to used the configured stop costs, and it would be ready to go whenever we get the data.

@mraross commented on Mon Mar 26 2018

1. Evaluate existing algorithms that support dynamic and time-dependent route planning with user preferences and make a recommendation.

2. Evaluate existing timetable-based routing algorithms to support ferry routing and make a recommendation.

3. Determine how to best integrate recommended algorithms.

4. Write up findings and recommendations in an Advanced Routing Algorithm Evaluation document

Some algorithm references can be found in bcgov/api-specs#153

@mraross commented on Wed Nov 16 2016

Add a roadType parameter that allows a user to prefer or avoid certain road types (e.g., alley, major/minor highway, freeway, major/minor arterial, local). This parameter is found in MapQuest and other routing APIs. By default, the route planner should avoid alleys and local roads.

Here's are some examples:
&roadTypes=-local;-alley
&roadTypes=arterial;-local;-alley

@mraross commented on Sat Feb 03 2018

This looks like a promising approach to implementation:

Fast shortest path with parameterized costs
https://arxiv.org/pdf/1509.03165.pdf

@mraross commented on Wed Oct 05 2016
Currently, route directions include a leg for every road, bridge, underpass, snowshed, or tunnel traversal. This is useful detail to have when defining or editing a route. It would also be useful to have a summary or overview of route directions. onRouteBC needs such a summary to print on a commercial vehicle permit.

Add a brevity parameter that specifies the level of brevity of the directions. This parameter allows for multiple settings, two of which are needed now:

min (Default) - directions will include a leg for every road, bridge, underpass, snowshed, or tunnel traversal.

max - directions will only include one leg for each sequence of road segments that don't involve a left, right, or U-turn.

Some mid-level setting might be needed in the future (e.g., noBridges that would allow tunnels and snowsheds).

Here's an example:

if &brevity=max, the following directions would be included in the route from Vancouver to Prince Rupert:

Continue west on Hwy 16 for X km

if brevity=min, all bridge crossings should be included in directions as follows:

Continue west on Hwy 16 for 21 km
Continue west on  Prince Creek Bridge for 35 m
Continue west on Hwy 16 for 4.4 km
Continue west on Boulder Creek Bridge for 60 m
Continue west on Hwy 16 for 13 km
Continue west on Coyote Creek Bridge for 20 m
Continue west on Hwy 16 for 25 km
Continue west on Big Oliver Creek Bridge for 55 m
Continue west on Hwy 16 for 1.5 km
Continue west on Little Oliver Creek Bridge for 50 m
Continue west on Hwy 16 for 6.1 km
Continue west on Legate Creek Bridge for 80 m
Continue west on Hwy 16 for 7.7 km
Continue west on Saint Croix Creek Bridge for 40 m
Continue west on Hwy 16 for 5.6 km
Continue west on Chimdemash Creek Bridge for 75 m
Continue west on Hwy 16 for 8.2 km
Continue west on Kleanza Creek Bridge for 80 m
Continue west on Hwy 16 for 8.2 km
Continue west on Copper River Bridge for 150 m
Continue west on Hwy 16 for 6.9 km
Continue west on Dudley Little Main Bridge for 400 m
Continue west on Hwy 16 for 350 m
Continue west on Dudley Little Bridge for 250 m
Continue west on Hwy 16 for 400 m

If &brevity=max, directions don't break when the street name of the same highway route changes and the official street name is not a municipality street name. For example, a route that goes from yates and douglas st in victoria to Goldstream park will have one leg for Douglas St then one leg for Hwy 1 starting at Carey Rd and Hwy 1.

@cmhodgson commented on Thu Oct 06 2016

The direction "continue on " is standard in every navigation system I have used. However I understand this may be a requirement for onRoute to reduce the size of the directions, as they are being used as a legal description of the permitted route. In order to do this, we will need to add the route number to the street data as it is not included presently. We may need to be careful of exit ramps which include the route number - or perhaps exit/entrance ramps could also be removed from this shortened description? Perhaps a parameter "directions=minimal" or "directions=turnsOnly".

@mraross commented on Fri Oct 21 2016

Another approach is to not break directions on bridges and other street qualifiers. In other words if the name of a road segment before and after a bridge is the same, don't break the directions.

@mraross commented on Thu Dec 21 2017

We can only support about 60 route stops in about 60 seconds in the route optimizer. If we can reduce the time between pairs takes to compute inter-stop distances, we might significantly increase the number of stops.

@mraross commented on Fri Mar 03 2017

Problem statement

When computing best route, the Route Planner needs to take into account the following:

1. Start or end time
2. Multiple stops
3. User preferences
4. Vehicle type, dimensions, and configuration
5. Cargo type
6. Turn costs
7. Turn restrictions
8. Road restrictions
9. Road type and ownership
10. Truck routes and policy corridors
11. Scheduled and real-time road events
12. Ferry schedules
13. Historic traffic congestion

Turn and road restrictions may be dependent on time, vehicle type, vehicle dimensions, vehicle configuration, regional policy, and spatial extent

Taking these factors into account will require:

"... a practical algorithm that, while robust to user preferences, is able to integrate global changes of the time-dependent metric (e. g., due to traffic updates or user restrictions) faster than previous approaches, while allowing subsequent queries that enable interactive applications."
Source: https://arxiv.org/pdf/1512.09132.pdf

@mraross commented on Sun Jun 10 2018

Recent and promising:

A Fast and Tight Heuristic for A* in Road Networks
https://arxiv.org/pdf/1910.12526.pdf

Space-efficient, fast, and exact routing in time-dependent road networks
https://www.mdpi.com/1999-4893/14/3/90/pdf
https://arxiv.org/pdf/1910.12726.pdf

Towards Alleviating Traffic Congestion: Optimal Route Planning for Massive-Scale Trips
https://www.ijcai.org/proceedings/2020/0470.pdf

Framing algorithms for approximate multicriteria shortest paths
https://drops.dagstuhl.de/opus/volltexte/2020/13147/pdf/OASIcs-ATMOS-2020-11.pdf

Customizable Contraction Hierarchies with Turn Costs
https://drops.dagstuhl.de/opus/volltexte/2020/13145/pdf/OASIcs-ATMOS-2020-9.pdf

Time-Dependent Alternative Route Planning
https://drops.dagstuhl.de/opus/volltexte/2020/13144/pdf/OASIcs-ATMOS-2020-8.pdf

A Strategic Routing Framework and Algorithms for Computing Alternative Paths
https://drops.dagstuhl.de/opus/volltexte/2020/13146/pdf/OASIcs-ATMOS-2020-10.pdf

Space-efficient, fast, and exact routing in time-dependent road networks
https://www.mdpi.com/1999-4893/14/3/90/pdf
https://arxiv.org/pdf/1910.12726.pdf

Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies
https://arxiv.org/pdf/1906.11811.pdf

Alternative multicriteria routes
https://epubs.siam.org/doi/pdf/10.1137/1.9781611975499.6

Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees
http://drops.dagstuhl.de/opus/volltexte/2017/7625/pdf/LIPIcs-SEA-2017-18.pdf

Forward search in contraction hierarchies (2018)
http://harabor.net/data/papers/hs-fsich-18.pdf

Real-Time Traffic Assignment Using Fast Queries in Customizable Contraction Hierarchies
http://drops.dagstuhl.de/opus/volltexte/2018/8962/pdf/LIPIcs-SEA-2018-27.pdf

Traffic aware routing in road networks (on-demand customization)
http://www.sommer.jp/trafficrouting.pdf

Dynamic Time-Dependent Routing in Road Networks Through Sampling
http://drops.dagstuhl.de/opus/volltexte/2017/7897/pdf/OASIcs-ATMOS-2017-3.pdf

Intriguingly Simple and Efficient Time-Dependent Routing in Road Networks
https://arxiv.org/pdf/1606.06636.pdf

Experimental implementation of TD-S (based on RoutingKit)
https://github.com/ben-strasser/td_p

Experimental implementation of FlowCutter (used in TD-S)
https://github.com/ben-strasser/flow-cutter-pace16

Customizable Contraction Hierararchies (CCH)
https://arxiv.org/pdf/1402.0402.pdf

C++ Implementation of CCH
https://github.com/RoutingKit/RoutingKit

Graph cutting with Pareto Optimization (FlowCutter)
https://arxiv.org/pdf/1504.03812.pdf

Computing tree decompositions with FlowCutter
https://arxiv.org/pdf/1709.08949.pdf

Intriguingly simple and Fast Transit Routing
https://pdfs.semanticscholar.org/a892/a54b02ce112e1302931231141a8b676b873b.pdf

Connection Scan Algorithm
https://arxiv.org/pdf/1703.05997.pdf

Fast Exact Shortest Path and Distance Queries on Road Networks with Parameterized Costs
https://arxiv.org/pdf/1509.03165.pdf

@mraross commented on Fri Jun 01 2018

More papers on time-dependent routing

Dynamic, time-dependent route planning in road networks with user preferences
https://arxiv.org/abs/1512.09132

Customizable Route Planning
http://i11www.iti.kit.edu/extra/publications/dgpw-crp-11.pdf

Computing time dependent travel times in vehicle routing problems
http://essay.utwente.nl/72040/1/20170306%20-%20Publiceren%20thesis%20van%20Mathijs.pdf

How to build a real-time vehicle route optimizer
http://www.opendoorlogistics.com/assets/pdfs/How-to-build-a-real-time-vehicle-route-optimiser.pdf

Engineering Time-Dependent Many-to-Many Shortest Paths Computation
http://drops.dagstuhl.de/opus/volltexte/2010/2751/pdf/7.pdf

Vehicle routing under time-dependent travel times: the impact of congestion avoidance
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.208.3905&rep=rep1&type=pdf

The Time-Dependent Shortest Path and Vehicle Routing Problem
https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2017-57.pdf

Time-Dependent Route Planning with Generalized Objective Functions
https://algo2.iti.kit.edu/download/gen_obj_func_tch.pdf
http://algo12.fri.uni-lj.si/reg/proc/presentations/MUAQVhDxhsoheZshATmODHmQi.pdf

A Survey of Shortest Path Algorithms
https://arxiv.org/pdf/1705.02044.pdf

Dynamic Vehicular Route Guidance usingTraffic Prediction Information
https://www.hindawi.com/journals/misy/2016/3727865/

Self-aware traffic route planning
http://gamma.cs.unc.edu/TROUTE/AAAI2011-2.pdf

Time dependent route planning
https://pdfs.semanticscholar.org/f21c/47d7fac0a291647cd1211ce79349b5f47a80.pdf

@mraross commented on Tue May 22 2018

Spatio-temporal traffic flow forecasting on a city-wide sensor network
https://projekt.beuth-hochschule.de/fileadmin/projekt/magda/Presentations/GISOV2017_Kunde_Hartenstein_Sauer.pdf

Nice animation of contraction hierarchies
https://www.mjt.me.uk/posts/contraction-hierarchies/

Nice exposition of CH
http://www.fmi.uni-stuttgart.de/files/alg/teaching/s15/alg/CH.pdf

Using OSRM as a CH testing platform
http://snap.stanford.edu/class/cs224w-2014/projects2014/cs224w-10-final.pdf

@mraross commented on Thu May 24 2018

Looking ahead to road restrictions, check out:
Fast Exact Shortest Path and Distance Queries on Road Networks with Parameterized Costs
https://arxiv.org/pdf/1509.03165.pdf

@mraross commented on Fri Jun 01 2018

Issue moved to bcgov/ols-router #1 via ZenHub

@mraross commented on Fri Jun 01 2018

Issue moved to bcgov/ols-router #5 via ZenHub

@mraross commented on Sun Jun 10 2018

MOTI Traffic data
http://www.th.gov.bc.ca/trafficData/documents/TrafficReportsUserDocumentation_Apr2014.pdf
http://www.th.gov.bc.ca/trafficData/tradas/tradas.asp?loc=47-002EW

TransLink APIs for

• Regional Traffic Data System (RTDS) which provides real-time traffic data in the Greater Vancouver area including speed profiles and travel time by corridor and roadway segment
• Real Time Transit Info (RTTI)
• GTFS - Real-time
• GTFS
  https://developer.translink.ca/

Traffic congestion metrics
http://www.tac-atc.ca/sites/default/files/site/doc/Bookstore/defining-measuring-congestion.pdf

Cool traffic simulator that runs in browser
http://www.traffic-simulation.de/
http://traffic-flow-dynamics.org/

Simulation of Urban Mobility (SUMO)

• supports OSM format
  http://www.dlr.de/ts/en/desktopdefault.aspx/tabid-9883/16931_read-41000/

Toward realistic urban traffic congestion experiments using DFRouter

• a component of SUMO
  http://www.mdpi.com/1424-8220/17/12/2921/pdf

Flow architecture and benchmarking for reinforcement learning in traffic control

• uses SUMO
  https://arxiv.org/pdf/1710.05465.pdf

IEEE ITSC 2018 SUMO workshop
https://www.ieee-itsc2018.org/uploads/5/0/3/9/50391481/tutorial_on_simulation_of_urban_mobility__sumo__v2.pdf

TraffSim: A traffic simulator for investigations of congestion minimization through dynamic vehicle rerouting
http://ijssst.info/Vol-15/No-4/paper5.pdf

• supports OSM format

Proactive vehicle rerouting strategies for congestion avoidance
https://web.njit.edu/~borcea/papers/dcoss12.pdf

Traffic recovery time estimation under different flow regimes

• predicts post-incident traffic recovery time based on traffic intensity, incident duration, and incident severity (ratio of lanes closure).
  https://ac.els-cdn.com/S2095756415000653/1-s2.0-S2095756415000653-main.pdf?_tid=8a3b4824-0fed-4d44-91d4-3ad3d192ccb8&acdnat=1528518266_beb44b5515ab38020a97d061f4dddd31

Multi agent, transport simulation
https://matsim.org/

Integration of information patterns in the modelling and design of mobility management systems
https://arxiv.org/pdf/1707.07371.pdf

Towards a socially optimal multi-modal routing platform
https://arxiv.org/pdf/1802.10140.pdf

Comparison of traffic simulators
https://www.matec-conferences.org/articles/matecconf/pdf/2016/44/matecconf_ictte2016_05002.pdf

Trends in real-time traffic simulation
http://research.fh-ooe.at/files/publications/5760_journal_article.pdf

@mraross commented on Mon Jun 04 2018

While a loaded vehicle may fit on a given road segment, permitting regions may not allow such vehicle dimensions on that segment. There are multiple permitting regions in the province (e.g., Peace District, Lower Mainland, Lower Mainland OAH corridors).

@mraross commented on Fri Jun 23 2017

Some roads in the province impose restrictions on the physical dimensions, cargo, and configuration of a vehicle that can be safely accommodated. There may also be policy restrictions that may also be imposed by the transportation authority. The route planner needs to be aware of these physical and policy restrictions when routing oversized vehicles.

Road restrictions related to vehicle dimensions include max height, max width, max length, max weight, and max axle weight.

An example of a hard road restriction is a bridge clearance height. In contrast, a soft road restriction can be mitigated with human intervention (e.g., a hanging highway sign that can be temporarily removed).

Hard road restrictions may be included in the BC Digital Road Atlas or may come from an Road Restrictions API provided by the BC Ministry of Transportation and Infrastructure.

@mraross commented on Sat Feb 03 2018

This looks like a promising approach to implementation:

Fast shortest path with parameterized costs
https://arxiv.org/pdf/1509.03165.pdf

@mraross commented on Mon Jun 04 2018

This includes:

• oversize corridors (overall height, overall width, overall length)
• heavy haul corridors where vehicles may exceed permit maximums without having to request an extraordinary load permit. Increases in dimensions other than weight may be part of a heavy haul corridor definition.

[LS037]

@mraross commented on Tue Jun 05 2018

Of particular interest is the attribute schema used by TeleNav for use in their Scout in-car routing app.

@mraross commented on Wed Mar 07 2018

Some turns and S-curves in road segments are too tight for vehicles over a certain length or width.

@mraross commented on Wed Mar 07 2018

Road events will be cooked for this issue and based on actual historic open511 events.

Scheduled road events should be taken into account when computing best route.

@mraross commented on Fri Jun 02 2017

Routing to the correct block-face ensures the optimal route visits the correct side of two-way streets. This is needed when picking up or dropping off passengers and cargo, collecting garbage, watering plants, etc.

Requested by City of Vancouver

@mraross commented on Tue Jun 05 2018

Review requirements related to time-dependency and restriction scope (e.g., permitting region, geographic area, line geometry, line defined by two intersections along a road)

@mraross commented on Mon Mar 26 2018

1. Evaluate existing algorithms that support dynamic and time-dependent route planning with user preferences and make a recommendation.

2. Evaluate existing timetable-based routing algorithms to support ferry routing and make a recommendation.

3. Determine how to best integrate recommended algorithms.

4. Write up findings and recommendations in an Advanced Routing Algorithm Evaluation document

Some algorithm references can be found in bcgov/api-specs#153

@mraross commented on Fri Jun 01 2018

Issue moved to bcgov/ols-router #2 via ZenHub

@mraross commented on Thu May 24 2018

Given outcome of time-dependent routing algorithm evaluation, decide whether or not to proceed with time-dependent routing.

@mraross commented on Fri Jun 01 2018

Issue moved to bcgov/ols-router #3 via ZenHub

@mraross commented on Wed Jun 13 2018

Issue moved to bcgov/ols-router #7 via ZenHub

@mraross commented on Thu Sep 21 2017

Given a set of points, snap the points to the nearest road, find the graph voronoi and generate the appropriate set of polygons such that any point within the polygon, when snapped to the nearest road, is closer by road to its centre point than any other voronoi region.

Input parameters include:
points - a list of unique points; duplicate points will be ignored
bbox- an optional bounding box specifying the maximum extent of the road network that should be analysed. Can't be used with geomark present.
geomark - a geomark containing a single polygon that defines the maximum extent of the road network that should be analysed. Can't be used with bbox present.

router.api.gov.bc.ca/voronoi should return a list of voronoi regions where each region has a centre location and a polygon.

@mraross commented on Fri Sep 22 2017

References
Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths
http://drops.dagstuhl.de/opus/volltexte/2016/6349/pdf/LIPIcs-ESA-2016-7.pdf

@cmhodgson commented on Wed Dec 20 2017

An additional parameter would be an optional bounding polygon (using geomark) or bbox, limiting the outside bounds of the service area calculation.

@mraross commented on Thu Dec 21 2017

Should the resource be called serviceAreas or voronoi?

@mraross commented on Tue Jun 05 2018

It doesn't have to be realistic, just plausible. This will insulate us from lack of real data in the early period of the project.

Event types should include:

• road currentSpeed
• current and planned road closure of a given road segment, corridor, or geographic area
• current and planned lane closure of a given road segment, corridor or geographic area
• mandated speed reduction (e.g., as a percentage of max speed) on a given road segment, corridor, or geographic area.

@mraross commented on Tue Jun 05 2018

For a simple way to simulate traffic congestion, see section 5.1 Simulating traffic in
http://drops.dagstuhl.de/opus/volltexte/2017/7897/pdf/OASIcs-ATMOS-2017-3.pdf

Fancier approaches:

Using a Traffic Simulator for Navigation Service
https://people.eng.unimelb.edu.au/etanin/gis17c.pdf

@mraross commented on Wed Jun 06 2018

OpenTraffic includes a real-time traffic stats generator, a real-time traffic data exchange format, and OSMLR, a set of OSM tile with traffic speeds.
https://github.com/opentraffic/otv2-platform

open traffic stats from other jurisdictions
https://github.com/graphhopper/open-traffic-collection

Tom Tom real-time traffic data
https://www.tomtom.com/lib/img/REAL_TIME_TRAFFIC_WHITEPAPER.pdf

For Velocity Fields and Congestion Spreading After Incidents, see section 4.3 in:
https://www.cl.cam.ac.uk/research/srg/opera/publications/papers/2011LNCS6875.pdf

Real-Time Traffic Information Management using Stream Computing
https://pdfs.semanticscholar.org/2a59/510b3adea158588928cd813915dcd7bc0fad.pdf

Real Time Traffic Monitoring System Using Crowd Sourced GPS Data
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.866.2007&rep=rep1&type=pdf

@mraross commented on Mon Jun 11 2018

Traffic congestion metrics
http://www.tac-atc.ca/sites/default/files/site/doc/Bookstore/defining-measuring-congestion.pdf
http://www.tac-atc.ca/en/publications/ptm-dmuc-e

Circular traffic simulator
http://www.traffic-simulation.de/

Simulation of Urban Mobility (SUMO)

• supports OSM format
  http://www.dlr.de/ts/en/desktopdefault.aspx/tabid-9883/16931_read-41000/

Toward realistic urban traffic congestion experiments using DFRouter

• a component of SUMO
  http://www.mdpi.com/1424-8220/17/12/2921/pdf

Flow architecture and benchmarking for reinforcement learning in traffic control

• uses SUMO
  https://arxiv.org/pdf/1710.05465.pdf

IEEE ITSC 2018 SUMO workshop
https://www.ieee-itsc2018.org/uploads/5/0/3/9/50391481/tutorial_on_simulation_of_urban_mobility__sumo__v2.pdf

TraffSim: A traffic simulator for investigations of congestion minimization through dynamic vehicle rerouting

• supports OSM format
  http://ijssst.info/Vol-15/No-4/paper5.pdf

The impact of GPS enabled shortest path routing on mobility: a game-theoretic approach
http://ijssst.info/Vol-15/No-4/paper5.pdf

Proactive vehicle rerouting strategies for congestion avoidance
https://web.njit.edu/~borcea/papers/dcoss12.pdf

Traffic recovery time estimation under different flow regimes

• predicts post-incident traffic recovery time based on traffic intensity, incident duration, and incident severity (ratio of lanes closure).
  https://ac.els-cdn.com/S2095756415000653/1-s2.0-S2095756415000653-main.pdf?_tid=8a3b4824-0fed-4d44-91d4-3ad3d192ccb8&acdnat=1528518266_beb44b5515ab38020a97d061f4dddd31

Multi agent, transport simulation
https://matsim.org/

Integration of information patterns in the modelling and design of mobility management systems
https://arxiv.org/pdf/1707.07371.pdf

Towards a socially optimal multi-modal routing platform
https://arxiv.org/pdf/1802.10140.pdf

Comparison of traffic simulators
https://www.matec-conferences.org/articles/matecconf/pdf/2016/44/matecconf_ictte2016_05002.pdf

@mraross commented on Tue Mar 21 2017

isochrones is a resource that represents a sequence of concentric polygons representing boundaries of equal travel time from the point of origin

isodistances is a resource that represents a sequence of concentric polygons representing boundaries of equal distance from the point of origin

&point - point of origin
&zoneSize - size of zone. Units are minutes for isochrones and metres for isodistances.
&zoneCount - number of zones (polygons)
&inbound - if true, set travel direction inward to &point ; if false, set direction outward from &point

For zoneCount=3 and zoneSize=10, three polygons will be generated and total route time will be 30 minutes.

For a nice demo, see https://www.iso4app.net/

@cmhodgson commented on Fri Apr 28 2017

We still need to develop the algorithm for polygonizing the segments - if you look at graphoppers example carefully you will see it does an awful job of this, with segments of roads which are not reachable from the other segments in the isochrone being included accidentally. This may be non-trivial and is complicated by working on the graphopper "black box" network - it can probably do what we need but I need to figure out how to get it to.

@mraross commented on Mon Sep 25 2017

Here's a promising paper on how to polygonize the segments:
Scalable Isocontour Visualization in Road Networks via Minimum-Link Paths
https://arxiv.org/pdf/1602.01777.pdf

@mraross commented on Wed Jan 17 2018

If we restrict the use of this resource to display on a map that already has a DRA road layer, perhaps we can get away with returning only the points on the boundary of each time zone. If these points are displayed on the map, can a user fuse them into a boundary in their mind's eye?

Each point can have a few properties to help with the visualization:

1. Time interval (.e.g., 5 means this point is five minutes from service centre)

2. Degree (e.g., 1 means a dead-end, 2 means a two-way intersection, etc.)

3. intersectionID - DRA intersection id if point is at an intersection, null otherwise

We can also return the bbox of the boundary points that the app can use to set the map extent.

@mraross commented on Tue Jan 30 2018

Could we optionally or additionally return an isoline that connected the boundary points? Could we get away with a convex hull? The beauty of this scheme is that when you display the points as well as the isoline, you can see that the false crossings aren't part of the boundary.

@cmhodgson commented on Wed Mar 14 2018

Some questions about the params:

• Rather than using "point", should we reuse either "fromPoints" or "points", with an initial limit of only one (but possibly supporting multiple in the future)
• Do we also want to support distance-based isoContours, using ie. travelDist parameter as an alternative to travelTime? Should we integrate these parameters, eg. reuse the criteria param (criteria=fastest|shortest) and instead of travelTime/Dist use "limit" or "isoLimit" or "contourSize"? Also should we rename the service from isochrone to isocontour in this case?
• not sure about the word "zone"... contourCount? numContours?

@cmhodgson commented on Wed Mar 14 2018

Do we need configurable limits to this resource? Maximum number of zones/contours? Total maximum time/distance? Really, there shouldn't be a problem with the size of the total coverage, but I expect that calculating the contours will be the expensive part that we might want to limit to at most 10?

@mraross commented on Fri Jan 19 2018

Could call it ignoreTime. If ignoreTime=true, route is calculated without consideration of start time, time-dependent restrictions, time-dependent delays, or ferry schedules. In other words, when set to true, route travel time should be the same as for the same start/end points in versions prior to v2.0.

@mraross commented on Fri Jan 19 2018

Road travel restrictions may be specified on an area-wide basis instead of on a segment by segment basis. For example, a transport permitting authority may specify that certain road classes within its area of authority should be not be travelled on by certain vehicle profiles due to heavy rains.

@mraross commented on Sat Feb 03 2018

This looks like a promising approach to implementation:

Fast shortest path with parameterized costs
https://arxiv.org/pdf/1509.03165.pdf

@mraross commented on Fri Jan 19 2018

This allows a user to specify one or more areas of exclusion on a given route planning request.
Specify area of exclusion using an excludeAreas parameter which can take a comma-separated list of bboxes.

Take excludeAreas into account when computing best route.

@mraross commented on Tue May 02 2017

@cmhodgson commented on Thu May 04 2017

Graeme maybe you should estimate this one.

@gleeming commented on Thu May 04 2017

It is a wide open ticket, so I suggest we start with an initial analysis, maybe timebox the following at a couple of days:

• contact GeoBC to get their opinion on the state of nav data and upcoming improvements (e.g from MoT contributions)
• create a layer of candidate intersections (e.g. bi-directional crossings above a certain speed limit with no impactor/restrictions; 3+ ways near a light that may represent turn off/on lanes that could illegally skirt the intersection)
• create a layer of turning lanes and ramps that have no impactor/restrictions
• do a general overview (stats, visually) of the above layers to determine the possible extent of deficiencies in rural and urban areas
• use the current route planner to create paths through/around some of the candidates; review these to get a better understanding of the effects and severity

This analysis will only give us anecdotal evidence of the extent of problems in areas we are familiar with on the ground. It will be difficult to conclude much other than general statistics in the rest of the province, unless a more time consuming review of random routes were performed (e.g. by visually checking them against, say, Google Street View, or against the same routes output from Google).

If followup work is required to get a better assessment, that will have to be estimated separately once we know what to focus on.

@mraross commented on Mon Jun 04 2018

A assisted maneuver is a road restriction that can be mitigated by special activities. An example is allowing a wide load on a road segment by closing opposite direction and using a flag-person. MoTI permit clerks must approve all assisted maneuvers.

Add a new resource that finds a route that minimizes road restriction violations. The result should include a list of all road segments with mitigated restrictions. This may require multi-criteria optimization.

@mraross commented on Mon Jun 04 2018

Seasonal load restrictions refer to a specific type of weight limit applied to roads during periods of freezing, thawing, and heavy rains.

@mraross commented on Tue Mar 06 2018

This is dependent on a GTFS - Real Time feed of ferry schedule updates from BC Ferries.

@mraross commented on Thu May 24 2018

Given outcome of time-dependent routing algorithm evaluation, decide whether or not to proceed with time-dependent routing.