Temporally Aware Network Routing Algorithms

By | 15th February 2017

Don’t get me wrong, I like Google Maps. It helps me get from A to B via C as efficiently as possible. I have noticed a quirk though and I tested it this morning.

I live 7.24 km from my children’s school. I left at 6:16 this morning. Maps said that I would be there by 6:35 which is 19 minutes. This is a good time, this works. However as I got onto each leg of the journey another 5 or so minutes were added. I arrived at 6:55, 39 minutes travel time, which is what I have come to expect. There is a glitch in how network routing works in the real world.

Problem: If you have a network and the cost of each path (road segment between intersection and intersection) you can build up a map and apply distance vector, shortest path (Dijkstra’s Algorithm) or any number of implementations to solve for the fastest route. What all these algorithms fail to take into account is that the cost of the route is not static (and yes I am sure Google know the cost of each road segment for any given time of any given day except for maybe the alleyway in Tweebuffelsmeteenskootmorsdoodgeskietfontien). This changes the required algorithm to a dynamic node algorithm.

Solution: I would solve this using the following algorithm for short distances:

  1. Draw a circle around each target area of around half the distance from start to finish. (in my case around 3.6 km)
  2. Draw a large circle that just encloses each of these circles. This will give you your maximum path options.
  3. Generate a Markov network with time based cost functions for each jump. Remove any paths that create loops.
  4. Run a Montecarlo simulation across the nodes. (send a million cars across the chain and see which ones get the the target first)
  5. Every time a path exceeds the current fastest stop calculating and move to the next one.
  6. Store the path and start and end times and provide a few fixed path routes so the calculations can be re-used for multiple users.

Lets be honest the above solution requires a large amount of data and a large amount of computing but considering how often I travel the same road every morning and the number of the same cars I see every morning the calculations could be pre-built. And also you could pre-build them from major nodes only. Then use use specific routing to get me to one of those know nodes. The advantage is the routing can then start applying load sharing like was recently tested in San Francisco so that a portion of the cars take less optimal routes for the benefit of everyone.

Just a thought, I may build a prototype some time to test the computational load of this.