Looking for a adjustable routing script

Hi everybody,

I’m not the biggest programmer, and I searched the internet quite a while to find something which is suitable for my problem, fortunately without success. Maybe someone here can give me a hint. My problem is the following:

We have four Water-Rescue-Units in our county, in case of an alarm, the two nearest units should be alarmed. Up till now we have a map of our county which we created by our own knowledge an intuition with areas marked, which unit to alarm.

We found out that this map isn’t correctly on several places…

My plan is to use a program which generates a list of the driving time of all points on a geographic grid and tells there which are the quickest two units to each point. As this calculation is for an emergency service we need to change some parameters for the routing:

  • ignoring one-way-roads and turn restrictions
  • use of foot-ways / cycle-ways / tracks as long as they are wide enough and have a road condition which is good enough
  • avoiding ferries, ignoring removable barriers (poles, lift-gate…) but adding some extra time to the calclulation for opening the barriers

We do not need the complete graph of the routing, we only need the estimated traveling time, but for many points.

Hope someone can help us here, thanks in advance:

Mirko

My knowledge of all the routing engines and their configuration is rather limited and I believe someone will suggest much better solution :), but here is mine approach:

Instead of using grid, you can actually compute in advance the driving times from any point in a map to each of the four Water-Rescue-Units using Spreading activation algorithm:
https://en.wikipedia.org/wiki/Spreading_activation#Examples

this will require you to work with the osm dataset as a mathematical graph (i.e. streets/paths/ways are edges and intersections/junctions are nodes).

In your case, you will compute the spreading activation four times - each time starting from a node which corresponds to a particular Water-Rescue-Unit location. When all computations are finished, for each node N(i) in the graph you will have four values (ti1, ti2, ti3, ti4). Value ti1 tells you the time it takes from the particual node N(i) to Water-Rescue-Unit No.1.

When there is accident in point N(i), you pick out of (ti1, ti2, ti3, ti4) those two values, which are lowest and notify correspoding two Water-Rescue-Units.

Advantages of this approach:

  • Activation spreading computation can run effectively in parallel (e.g., using map-reduce)
  • The times are computed in advance for each junction/intersection of roads on the map

Disadvantages:

  • you have to store the osm data in efficient manner so that you can query the graph quickly when computing the spreading activation iterations
  • you have to create good heuristics which will tell how an activation energy amount is split on a node toward neighbouring nodes (e.g., take into account all the driving rules).
  • when graph is altered (e.g., road is closed), you have to recompute all the times from scratch.

You could run OSRM (http://project-osrm.org/) with a custom Lua profile (to ignore one-way restrictions, use cycleways, ignore ferries etc.), then run the /matrix call to find distances.

Bear in mind that OSM usually doesn’t have width information for footways, cycleways and tracks.