## 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…