Need help with trip planner!!

solodesignz

Hi,

Well, I've been trying to build a trip planner for some time now for a client of ours. Heres some background:

The tripplanner is for a southern california train company... The system needs to
generate routes and display the routes (station, train #, time and traveling train line) for the user.

The user inputs a start station, end station and starting time.

It needs to work off these tables:


"Station"
Id
Name
Line

"Train"
Id
Name

"TimeTable"
Id
Name

"TimeTableStation"
Id
TimeTableId
StationId

"TimeTableTrain"
Id
TimeTableId
TrainId

"Time"
Id
TimeTableId
StationId
TrainId

I originally had a recursive loop generating routes, storing them in the database then when a user submits the page, the system gets the routes and finds the fastest time.... The problem here is that the recursive loop takes way too long to generate all possible routes. So basically the whole thing fails because it doesnt have enough time to find all possible routes, so it defaults on some really long route or something.

There are 55 five stations on the map, so 55x55=3025 possible route combinations . Now I would guess each route combination would require 5-10min to generate all possible routes... do the math.. its just not practical. =/

Now... this recursive loop basically spiders through the stations to find routes... ends up being looped millions of times.

If anyone is up for helping me on this, it might take some time, I can provide all my source code.

Thanks so much!

etully

Since I don't know a lot about the problem, this advice may or may not be useful:

Can you pre-process the entire database and store the fastest results? For example, let's say that there are 5 ways to get from A -> Z and they are:

a,b,c,d,z
a,m,z
a,b,y,z
a,b,g,z
a,b,t,u,v,w,x,z

So you run the numbers once (maybe you have to let your machine run for 2-3 days) and it builds and index where it stores the fastest time:

So your table has two fields: path and best route. Path would be "az" and best route could be "a,b,y,z". When you want to find the best route from A-Z, you just lookup the best_route where path='AZ'.

If there are some conditions where a,b,y,z is the fastest way and there are other times when a,b,g,z is faster, then you could store maybe the three fastest routes. When the user wants to know the best route, you only have to calculate the times on three routes instead of 55 million.

solodesignz

Thanks for the input... this is pretty much exactly what I did on my second pass at trying to accomplish this.

Generating all the routes took about 3 days straight, and that was at 3 minutes allowed for each calculation... problem was that it didnt find all the routes in the given time... so, even if I bumped the time allowed to 6, that would take 6 days to generate the routes....

I was trying to find some way around this, but maybe it is the best way...

WDPEjoe

Are the train schedules static? If they change, how regularly? You must consider this when you're talking about pre-generating the fastest routes as a changing schedule implies that the fastest routes must be re-analyzed.