Ideas guys? Journey Planning.

[ineedalotohelp]

Not sure if this is the right forum - but i will be coding the solution in PHP though (i think) if thats worth anything...

Im doing a bit of work surrounding the area of journey planning, and im just wondering, how the heck do they do it?

Say for example, you want to go from a residential address in London to a residential address in Paris using public transport... How would this work...

My initial ideas are that a range of transport providers provide data over web services, and the "portal" somehow collates all the available connection points and offers various routes, or the portal suggests the quickest, shortest, cheapest...etc...

I just cant grasp how code can map a path through these connection points is it just a case of having all the data and mathametically determining the distances (possibly for shortest route), but then you need information such as average speed of the vehicle you are travelling on to determine time... etc...etc..

Im just hoping someone out there has a clearer idea than i do! Does anyone have any ideas?

[FlashCreations]

I don't think PHP is the appropriate language for this. This project might be a bit beyond it's capabilities. The best I could do with PHP is maybe write some JavaScript to use the Google Maps API. Why re-invent the wheel, when Google has perfected it. I'm sure with the API you can calculate trip distances and times (but I'm not sure).

[ineedalotohelp]

I don't think PHP is the appropriate language for this. This project might be a bit beyond it's capabilities. The best I could do with PHP is maybe write some JavaScript to use the Google Maps API. Why re-invent the wheel, when Google has perfected it. I'm sure with the API you can calculate trip distances and times (but I'm not sure).

Although google does provide good distance calculation, it is based on walking or driving, and public transport is only included as beta in a select few cities.

What i am trying to determine is far simpler, but perhaps the way i put it wasn't so clear...

Anways, To simplify, lets consider this scenario of traveling by train, you wish to travel by train from point A to point B. London to Milan, for example. but to complete this journey, you will have to change trains in Paris. How does this simple process work? Would connection points be stored in a database so that every request that goes from london to milan has to go via paris (example 1), or would you have a routes logged in the database, and the code will determine the links on the fly (example 2) Or does it work some other way...

Example 1 - The database has a table called Journeys which stores all possible combinations of start points and destinations. So there would be a record linking start point of London, to destination Milan called journey 1. This would then link to another table called connections. In the connections table you would have a connection for journey 1 at paris.

Example 2 - for on the fly route planning, i would store, the cities the train stops at along the way... e.g. train 1 would go, London, Paris, Berlin. Train 2 would go Amsterdam, Paris, Milan. To determine a route using this method, i would search for all trains that go through london, and all trains that go through milan, i would then find common connection points (in this case Paris). this would determine you need to take train 1 to paris, then change to train 2 to milan.

Any further ideas? I think these methods would work, but perhaps arent the best way of doing it.

[FlashCreations]

And your probably right, they aren't the best. I believe a plane would be the easiest example. What if you had a table of plane flights that included a departure city and arrival city. It could also include other details such as flight number, departure and arrival times. Then simply find all the flights that depart from the user's city on the day and approximate time requested. Then work a flight plan for each of them and then eliminate the ones that are too long or don't end up in the users requested city. From there you could also filter by distance (Using a table of city distances) and trip time (using the arrival and departure times in the flights table, along with layover times). It's not simple, but I think it could work.

The same principle could be applied to trains, buses, boats, or any kind of transportation with a planned schedule of point A to point B. Cars and walking will be a lot more complex because there's no point A to point B trips. The driver has control and can go pretty much anywhere. For this situation you would need a digital map that you can use to trace a route, obeying street signs. You can calculate times by using the speed limit and miles driven for each street on the route.

EDIT:
For the first solution, may I suggest a recursive function.
Also, I forgot to mention, nice thread. This is a really interesting problem!

[ineedalotohelp]

Thanks, definitely helps to talk these problems through. I will post back here and let you know the methods i went with in the end...

If you have any more ideas in the mean time, let me know!