I make a travel planner (or general schedule) for all public transport in my country (bus / train / air).
The state of the project is in the middle, now it’s a little difficult for me to get the more complex part of the application made.
To describe the current status:
Data is stored in a MySQL database modeled as GTFS (General (Google) Transit Feed Specification)
I get direct routes by simply querying the database (combining two temporary tables, I find this quite efficient)
This is currently being done in PHP, but I can rework it in Java if necessary
So, when there are direct connections between two points, everything is in order. The difficult part is a complete journey when there are no straight lines.
Say that the user wants to travel from city A to city D , but due to the lack of direct lines between these cities, he must go through city B and city C
How can I get optimized routes and transfers for this situation?
My ideas still gravitate towards the use of the graph, but in this case I need a time-dependent weighted weighted multigraph , and I really do not know how to implement the Time-dependent part .
As soon as the route can be executed using Dijkstra , A* or Floyd–Warshall , but since there are deviations at different times, I’m not sure how this will be implemented in order to get the optimal solution, I need to consider the duration of the segment (from A to B , B to C), transmission latency, possibly distance too.
To clarify, I do not need a single result. I want to get a daily list of all departures from city A that city D can get, if necessary, if necessary.
In principle, what I'm trying to get is something like this (taken from the Bulgarian railways or, for that matter, which railway junction), a list of all departures for the selected day, going from Sofia to Kystendil making a transfer to Radomir if necessary:
About the solution part of the graph, I can make a Java application using jGraphT , cache the results (they change once in each, possibly for several months) and use them in PHP (or call the application through PHP).
If I'm not clear enough, ask.
I know that this is done so many times (almost any train site has solutions), but I do not know under what conditions to even look.
So my question is: can someone give me a guide on how to solve this type of problem?
Or at least with what terms I should look for ideas and how to do it.
Perhaps some suggestions for other sites on the StackExchange network.
Thanks.