2
$\begingroup$

I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). What are the ways to find next best paths (path is a sequence of trips and transfers from source to destination)? I have few ideas about it:

  1. Find best path, then exclude trips (from path) from transportation network and rerun algorithm. (It's not clear for me how to choose new departure time).
  2. Find best path P, then rerun algorithm with adjusted departure time so it's not possible to use P. (I think some good paths may be missed here)

What is the way to find next best paths?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

There are standard algorithms for finding the $k$ shortest paths in a graph: you provide $k$, and it returns the shortest path, second-shortest path, ..., up to the $k$th shortest path. See https://en.wikipedia.org/wiki/K_shortest_path_routing. I'd suggest that as a natural place to start.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.