3
$\begingroup$

This is a cross-post of this StackOverflow question, (I'm not aware of linking questions between StackExchange sites). You can ignore the part about programming.

I'm making a journey planner (or a general timetable application) for all the public transport in my country (bus/train/air).

The state of the project is at midpoint, now I'm having a bit of a hard time getting the more difficult part of the application done.

Currently, I have all the stops, routes and departure/arrival times.

When there are direct connections between two points, all is fine, I can get the trips for a chosen day. The hard part is getting a complete journey when there are no direct lines.

Say the user wants to travel from city A to city D, but because there are no direct lines between those cities, he needs to pass through city B and city C.

How can I get the optimized routes and transfers for this situation?

My ideas so far a gravitating towards using a graph, but in that case I need a Time-Dependant Directed Weighted Multigraph, and I really have no idea at the moment how to implement the Time-Dependant part.

Getting just the route can be done by using Dijkstra, A* or Floyd–Warshall algorithms , but because there are departures at different times, I'm not sure how will this be implemented, to get the optimal solution. I need to take into consideration the duration of a segment (A to B, B to C), waiting time for the transfer, maybe the distance too.

Just to clarify, I don't need a single result. I want to get a daily list of all departures from city A that can get the user to city D, with transfers if needed.

Basically, what I'm trying to get is something like this (taken from Bulgarian Railways, or for that matter, whichever railway site), a list of all departures for a chosen day going from Sofia to Kystendil making transfer in Radomir if needed:

Sample Result

If I'm not clear enough, please ask.

I know that this is done so many times (almost any train website has the solution), but I don't know by which terms to even search.

So, my question is: can someone give me guidance how this type of problem is solved?

Or at least by which terms should I search for ideas and how should it be done.

Maybe some suggestions for other sites in the StackExchange network.

$\endgroup$
  • 1
    $\begingroup$ I believe that what you have here is a "travelling salesman problem". Of course, if your route planner is supposed to handle intermodal passenger transport, your computational complexity with sharply increase on each leg. Instead of calculating route by distance, you'd be calculating them based on timetables (if chosen preference is getting to the destination as soon as possible), or other vectors. $\endgroup$ – TildalWave Jul 10 '13 at 2:41
  • $\begingroup$ "Traveling salesman problem" usually is used to find the best path through vertices, taking into consideration only the distance. But in this case, the problem is way more complex because of the timetables (waiting times), number of transfers, prices ... Yes, this will be application for "Intermodal passenger transport", but that is not an issue. I'm leveraging all types of transport to the same level, because all modes of transport have the same properties: departure time, duration, distance and price, so in the end it doesn't matter if it's train, bus or airplane. $\endgroup$ – ekstrakt Jul 10 '13 at 3:43
  • $\begingroup$ Does Dijkstra really require the weights of unexplored edges to be constant? $\endgroup$ – Raphael Jul 10 '13 at 7:47
  • $\begingroup$ This sounds like it is definitely polynomial, but you need to explain which routes you want to show, as you say you don't want just the optimal one, but I assume you don't want to show all possible routes either because this could be a ridiculously huge number and most would be useless. Given a valid route, how do you decide if it should be shown? $\endgroup$ – svinja Jul 10 '13 at 11:23
  • $\begingroup$ @svinja As in the example, I need to list all shortest paths from node A to node B, for each departure time. One idea that comes to mind is to set a reference point at midnight (initial weight = 0), add all departures in form of edges, using the departure time as weight, and for each departure time to perform new search on the graph increased by an initial weight. (Example, a departure time at 01:00(am) would have weight of 60, so the search is performed with initial weight=60 added). Is there an algorithm which finds shortest path but will allow me to select the first edge manually? $\endgroup$ – ekstrakt Jul 10 '13 at 12:51