Motivation

A* Search is an algorithm that uses heuristics to speed up shortest path queries. To make a correct query with A* from to on a Graph we need a heuristic that is a lower bound for the real distance to t: . The better is (= the bigger the heuristic value is), the better is the speedup.

Graphs with public transit (Public Transit Graphs, PTG) have edges for fast connections that only operate a few times a day. This means that depending on the departure time, the travel time of the edge is either very short or very long (if you depart shortly before the train departs, you can take the train, if you depart after the train departed you either have to wait for the next connection or you have to walk). This makes it hard to find good lower bounds of such edges due to their high fluctuation of their travel time. Consequently, A* does not result in a good speedup on such graphs.

The main idea of this approach is to identify a set of edges with a high fluctuation of travel time and to find a good heuristic for . We can then query differently on these two sets using a combination of A* in and Dijkstra in … *or something like that @TODO.

Assumptions & Conditions

Given a graph

Given a subset

Given a subset with

and we define

Levels of Layers and Edges

We also call the subsets layers with level .

We define levels of edges in a path as follows:

We denote the level of a path if .

For and the layer condition is true:

alternatively:

Heuristics

We also require a heuristic :

  • is an admissable heuristic with

First Take: The most naive and Simple PTG-A*

Q is a priority function, pi(v,l) is a heuristic function, d[v] shortest distance to v found

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Q.clear()
Q.add(s, 0, 0, pi(s,0))
while(!Q.empty()) 
    u, l_max, l_curr, dist = Q.pop()
    for (e=(u,v) : outgoingEdges(u)) 
        if (d[u] + len(e) < d[v]) 
            l_edge = level(e, l_curr)
            // stay in same level
            if (l_curr == l_edge) 
                d[v] = d[u] + len(e)
                Q.update(v, l_max, l_curr, d[v] + pi(v, l_edge))
            // ascend to higher level (if it was not visited yet)
            else if (l_curr < l_edge && l_max < l_edge) {
                d[v] = d[u] + len(e)
                Q.update(v, l_edge, l_edge, d[v] + pi(v, l_edge))
            // descend to lower level
            else if (l_curr > l_edge && l_max <= l_curr) {
                d[v] = d[u] + len(e)
                Q.update(v, l_max, l_edge, d[v] + pi(v, l_edge))

The Algorithm is a normal A* search algorithm on edges and a normal Dijkstra on edges . The edges are considered as edges from either or depending on what the current level is. Note, that there is no stopping criteria whatsover yet und the current approach will check and try to relax all reachable edges.

Correctness

Is PTG-A* correct and finds the shortest path from to ? Intuition says yes. There’s not stopping criteria. We’re doing A* or Dijsktra on the whole graph and we should find the shortest path between and because of line 7:

d[v] = d[u] + len(e)

Case 1: Shortest path

A* is correct.

Case 2: Shortest path

A*, then correct Dijsktra.

Case 3: Shortest path

A, then Dijkstra, then A.

Second Take: Stopping PTG-A*

Simple PTG-A* is basically a mix of a Dijsktra and A* that traverses the whole graph and all its edges. Can we stop the search after relaxing our target ? Namely, can we add line 5 as follows?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Q.clear()
Q.add(s, 0, 0, pi(s,0))
while(!Q.empty()) 
    u, l_max, l_curr, dist = Q.pop()
    if (u == t) break
    for (e=(u,v) : outgoingEdges(u)) 
        if (d[u] + len(e) < d[v]) 
            l_edge = level(e, l_curr)
            // stay in same level
            if (l_curr == l_edge) 
                d[v] = d[u] + len(e)
                Q.update(v, l_max, l_curr, d[v] + pi(v, l_edge))
            // ascend to higher level (if it was not visited yet)
            else if (l_curr < l_edge && l_max < l_edge) {
                d[v] = d[u] + len(e)
                Q.update(v, l_edge, l_edge, d[v] + pi(v, l_edge))
            // descend to lower level
            else if (l_curr > l_edge && l_max <= l_curr) {
                d[v] = d[u] + len(e)
                Q.update(v, l_max, l_edge, d[v] + pi(v, l_edge))

Correctness

We will find a proof by contradiction - but first a neat corollar!

Corollar Shortest-Path-Order

Let be a shortest path from to and . For every vertex it is .

Proof:

Which is exactly the definition of feasibility of heuristics!

Back to trying to prove correctness of PTG-A*

Case 1: Shortest path with

Let be the shortest path found by PTG-A* and .

If it is a contradiction to the correctness of A*. Therefore, . With no loss of generality we assume

with and .

If

bla

@TODO why are IPE PNGs so awful?

Let vertex be the first vertex that is in . Vertex definitely exists because vertex . Let and . When is relaxed, vertex will be updated in the queue with . But when relaxing edge , vertex will be updated with . As the key values in are monotonically increasing and is smaller than it will be extracted from the queue before with the correct distance. This is a contradiction ↯

If

bla

Let edge be the last edge in and edge the last edge in . When is relaxed, vertex will be updated in the queue with . But when relaxing edge , vertex will be updated with . As the key values in are monotonically increasing and is smaller than it will be popped (?) from the queue before with the correct distance. This is a contradiction ↯

Case 2: Shortest path

The proof in Case 1 makes use of the fact that key values in a shortest path are monotonically increasing. More importantly, when a vertex with key of value is extracted from the queue and , then we can be sure that all vertices were already relaxed before. How does this change with a shortest Path that has edges from .

Observations of Key Values on Shortest Paths

  1. When relaxing edges the key values are always smaller than edges
  2. 1+2 is monotonically increasing
  3. But we know the key values when visiting and are also increasing. This means that as soon we relax an edge from , we will find the path

Let be the shortest path found by PTG-A* and . Let edge be the last edge of .

bla

It is . Vertex was found and relaxed when extracting with . We know because otherwise (see the key value observations) the PTG-A* would have found the shortest path .

But when relaxing edge we update vertex with so it has to be extracted before vertex is extracted through path . This is a contradiction ↯

Adding Labels to the Queue

The algorithm PTG-A* updates labels of vertices (as in line 12, 16, 20). The algorithm works correctly if you update a label with if . Otherwise, we will add the new label additionally to the old one to the queue. But there should be some cases in which we can also update a label even though .

Therefore, we analyze all cases where

  • is already in the queue and
  • is the new label we want to update/add to the queue.

In every case we have to check whether we need to

  • keep or
  • remove and
  • add or
  • ignore

Let be the shortest path from to . Let and be the paths from to vertex that create and .

if

  • remove
  • add

Proof:

Therefore, the shortest path does not use the subpath . Thus, cannot be a subpath of and we can remove .

if

  • keep
  • ignore

Proof:

Therefore, the shortest path does not use the subpath . (Actually, the algorithm will not even attempt to ever add because of line 7 in the code).

Thus, cannot be a subpath of and we can ignore .

if

  • If
    • keep
    • ignore

Proof:

Therefore, the shortest path does not use the subpath . Thus, cannot be a subpath of and we can ignore .

  • If
    • remove
    • add

Proof:

Therefore, the shortest path does not use the subpath . Thus, cannot be a subpath of and we can remove .

if

  • keep
  • ignore

Proof:

Therefore, the shortest path does not use the subpath . Thus, cannot be a subpath of and we can ignore .

if

  • If
    • remove
    • add

Therefore, cannot be a subpath of and we can remove .

  • If
    • keep
    • ignore

Therefore, cannot be a subpath of and we can ignore .

if

  • remove
  • add

Therefore, cannot be a subpath of and we can ignore .

if

  • keep
  • ignore

Therefore, cannot be a subpath of and we can ignore .

if

  • If
    • remove
    • add

Therefore, cannot be a subpath of and we can remove .

  • If
    • keep
    • ignore

Therefore, cannot be a subpath of and we can ignore .

Conclusion Regarding Dominating Labels

Looking at the results above we either remove and add or we keep and ignore . Therefore, we either update (remove and add) or keep (keep and ignore) the label.

update
  keep
  keep
  update
keep
  update
  keep
update
  keep
  update
  keep

Due to line 7 in the code, many cases do not even need to be checked because the algorithm would never try to add those labels anyways.