Time Dependent Shortest Path Algorithm Overview

April 29, 2011

As mentioned in my last post, I will be doing Google Summer of code project for pgRouting. Here, I will give an overview of the algorithm implementation.

pgRouting is a C++ library that provides routing functionality for postgres. I will be extending it so that it can support time dependent routing. An abstract overview of the idea is:


  • The time dependent data will be queried from postgres database.
  • Using the information, a graph will be generated
  • The core time dependent dijkstra algorithm will be run on the graph
  • The result will be returned

The input to a time-dependent shortest path problem is a directed network G = (N,A) and an arrival time function aij(t) for every arc  (i, j) ∈ A. The quantity aij(t) gives the time of arrival at j if one departs from i at time t. It is assumed that aij(t) ≥ t.
The function aij(t)−t gives the travel time along arc (i, j) if one departs at time t.

If aij(t) is non-decreasing for all (i, j) ∈ A, we say that G is a FIFO network, since in this case commodities will travel through arcs in a First-In-First-Out manner. If this is not the case the problem will be NP Complete. We will therefore assume that G is a FIFO network.

Let P(s, d) denote the set of paths between a source node s and a destination node d. The function EAsd(t) = min{ap(t) : p ∈P(s, d)} gives the earliest arrival time at node d if one leaves s at time t

The pseudo-code for solving the Single source – destination query is as follows:

Initialization:

For all i ∈ N\{s} : EAsi(t)←∞
EAss(t)←t
S ←N

Main Loop:

While S != ∅
Select i ∈ S minimizing EAsi(t) S ←S\{i}
For all j such that (i, j) ∈ A
EAsj(t)←min{EAsj(t), aij(EAsi(t))}

This will be basically a SQL C function for postgres. More updates to follow…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: