27

I have a database of bus/train/... stops and the arrival/departure times on each date and so on. I'm looking for a way to do a search for the fastest(shortest/cheapest/least transitions) trip between two locations. I would like to have arbitrary locations in the future, using OpenStreetMap data to do walking between stops and from stops to start/end, however for the time being I just want to find path between two stops in the database.

The problem is I can't seem to find much info about this subject, for example this Wikipedia page has a lot of text with absolutely no useful information in it.

What I've found is the GTFS format, used in Google Transit. While my city doesn't provide a public data feed (not even a private one), I already have all the important information that the GTFS contains and making a transformation would be trivial.

There is some GTFS-based software, like like OpenTripPlanner that can also do pedestrian/car/bike routing using OpenStreetMap.

However, the routing code isn't well documented (at least from I've found) and I don't need the whole thing.

All I'm looking for is some good overview of the algorithms I could use, their performance, maybe some pseudocode.

So, the question is, given a list of stops, routes and arrival/departure/travel times, how can I easily find the fastest path from stop A to stop B?

Marvin Pinto
  • 30,138
  • 7
  • 37
  • 54
lacop
  • 2,024
  • 4
  • 22
  • 36

1 Answers1

16
  1. Model your problem as a graph. Each station will be a Vertex, and each bus/train will be an Edge.
  2. create a function w:Edges->R,that indicates the time/money/... for each edge.
  3. now, you have a typical minimum path problem, which can be solved by Dijkstra algorithm, which finds minimum path to all vertices from a given source.

(*) For 'least transitions', your weight is actually 1 for each edge, so you can even optimize this by running a BFS or even bi-directional BFS instead of dijkstra, as I explained in this post [It is explained for social distance, but it is the same algorithm actually].

EDIT
as an edit to the non-static nature of the graph [for timing] you mentioned on comments [for price and number of transitions, what I have mentioned above still applies, since these graphs are static], you can use a distance vector routing algorithm, which actually meant to work for dynamic graphs, and is a distributed variation of Bellman Ford algorithm.
The algorithm idea:

  • periodically, every vertex sends its "distances vector" to its neighbors [the vector indicates how much it 'costs' to travel from the sending vertex, to each other vertex.
  • Its neighbors try to update their routing tables [through which edge is it best to move to the each target]
  • for your case, each node knows what is the fastest way to get to its neighbors, [travel time + wait time] and it [the vertex/station] adds this number to each entree in the distance vector, in order to know how to and how much time it will take, to get to the destination. When a bus leaves, the travel time should be re-calculated to all nodes [from this source], and the new vector should be sent to its neighbors
Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • Yep, you're not going to get faster than Dijkstra's algorithm mfor this unless there's constraints that you're withholding that allow for further optimization. For metrics other than time, you will need to formulate a 'weight' which is a combination of time, cost, and hassle. You may also have to leave it to the user to determine exactly what those weights are and recompute on the fly, or have a couple predetermined scenarios (100% time, 100% cheap, 50/50/0, 40/40/20, and the like) and keep a cached version of the Dijkstra lookup table. – corsiKa Aug 30 '11 at 15:47
  • 3
    Unless I'm missing something, this won't work. Dijkstra is great for a "static" graph with just the space domain, but this has time domain. For example, if you get to a node by a bus that takes 1 minute, the edges on there will be different than if it took you 5 minutes. You may miss a bus so the weights get larger because you have to wait. Also, some edges might disappear if you got to a node in a certain way (missed last bus of the day) but be there if you got there in another way. AFAIK, Dijkstra doesn't allow for this, but please correct me if I'm wrong. – lacop Aug 30 '11 at 16:13
  • 1
    @albwq: Dijkstra's algorithm doesn't handle with 'waiting' in the vertices for the next bus, you are correct about that. However, it is valid for the other two criteria you asked for: cost and number of transitions. [see my last section about even optimizing number of transitions]. – amit Aug 30 '11 at 17:45
  • @albwq: I editted my answer, and added a short description [and links] about an algorithm which is meant to handle dynamic networks – amit Aug 30 '11 at 18:43
  • Looks interesting, I'm going to try that. Thanks. – lacop Aug 30 '11 at 19:39
  • 3
    zombie answer for lost visitors: Almost all conventional algoirhtms fail on time-dependent graphs, especially with waiting times. A fast and flexible solution that actually works is [RAPTOR](http://research.microsoft.com/pubs/156567/raptor_alenex.pdf) – dube Mar 27 '15 at 18:23