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.
To describe the current status:
The data is stored in a MySQL database, modeled as GTFS (General (Google) Transit Feed Specification)
I'm getting the direct routes by simply querying the database (join of a two temp tables, I find it as efficient enough)
Currently it's done in PHP, but I can re-work it in Java, if needed
So, when there are direct connections between two points, all is fine. 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:
About the graph solving part, I can make an application in Java using jGraphT, cache the results (they change once in every few months maybe), and use them in PHP (or call the application through PHP).
If I'm not clear enough, please ask.
I know that this is done so many times (almost any train website has the solutions), 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.
Thank you.
