Thread: Graph theory - find path from point A to point B in a tram / bus network

Hi,

I am currently working on a project to find the most optimal path from one address to another using public transports in a town. Different options will be available
to the user : find the fatest way and also the one with the least number of bus / tramway changes.
There are in the town approximately 1500 stops and 60 different lines, and i am looking for a fast algorithm to compute the path from address A to address B.
There are some constraints, like the respect of schedules (it is a dynamic graph) and also the fact that people will sometimes to walk from one stop to another to change bus / tramway.

I am looking for an algorithm to do that. I have several ideas in mind, like :
- using A* algorithm with some heuristics (i don't know if it fits well to the problem, since we can't really use heuristics like Manhattan distance here, as public transports not always go straight from one point to another).
- computing a dijkstra algorithm to blindy find the address A (but i think it would be too long).

Would you have any idea or opinion on how to do it?
Any remarks, links, suggestions are welcome

Thank you !

Maybe you should start from here...

some links...:

https://wiki.cc.gatech.edu/theory/in...in-max_theorem


Minimax - Wikipedia, the free encyclopedia

Hi,

thank you for the links, but sorry I don't really understand how they are related to my problem. Could you give me some more information?
Thank you

I'm not sure I understand: Dijkstra's Algorithm runs in polynomial time. Do you need something faster than ? All those constraints you have there could be modeled, I think, by cleverly choosing weights for the edges in your graph.

It needs to be really fast as it will be used as a webservice. The user enters a start and end point, some extra options (departure time, max. number of changes, shortest time..). The request has to be sent, processed, then results sent back and displayed really fast, let's say within 2 secondes, with a good internet connexion.

I know this is possible as I already saw a website offering the same kind of service really efficiently.

Moreover, it's a time-varying graph with multi-criteria search, that's why I'm not certain Dijkstra will fit here. But I might be completely wrong. Do you think some other algorithm would be more appropriate?

Thank you

Well, Dijkstra is pretty fast. And it will certainly solve a "snapshot in time" problem. However, you might be better off using evolutionary methods. These sorts of algorithms can adapt faster to changes in the search space, especially over time. One book I found very helpful was How to Solve It: Modern Hueristics, by Michalewicz and Fogel. I'm not an expert in these algorithms, but those two authors are. And they show you which kind of algorithm to use in which kind of problem.

Ackbeet, thank you for the book recommendation, I read a few reviews and it looks really interesting! I'll try to find it ASAP, see if I can find a solution to my problem. Also
i'll give Dijkstra a try, to see in practice if it fits to my time constraints.

Last thing, i had also one other approach in mind. I know the gps coordinates of the bus stops, so i was thinking of scanning a number of stops nearby the start point, and establish a list of lines that would bring me closer to the destination point. If i can't reach the destination from there, I reiterate the same operation and so on.
This could also be done bidirectionnaly, starting from the destination point also.

I think this is used by mapping application to find some car itineraries, here the problem is different as we have several modes of transport and changes, but still it might work.
What do you think of it?

Thanks again!

Your algorithm sounds a bit like Dijkstra's to me. By all means pursue it. I'm not sure I could be of a whole lot of help there, though.

Good luck!

Ok, thank you for the help and the book, i'll let you know if ever I find a good enough solution to the problem .

Bye!

You're very welcome. Have a good one!