5 Replies Latest reply on Jul 25, 2010 11:27 AM by JosAH

# 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 !
• ###### 1. Re: Graph theory - find path from point A to point B in a tram / bus network
Why do you think Dijkstra would be too slow? I have used it on networks of thousands of nodes and tens of thousands of links and in my experience it is pretty fast.

As far as people "walking" from stop to stop is concerned, is that not just another form of public transport. It may not be practical to apply directly because this would add all the streets and junctions as part of your graph with a traversal time that is a function of walking speed but it must be worth investigating.

Most of this problem would seem to be a fairly simple shortest path but the probabilistic nature of the arrival, departure and speed of public transport mean that you would need to involve some simulation (at least that is the way I would approach it).
• ###### 2. Re: Graph theory - find path from point A to point B in a tram / bus network
Hi,

About Dijkstra, I will give it a try, but I'll have to modify it, as i have to take into account the waiting time between two changes, and also limit the number of changes
(because I'm not sure someone would like to change bus 5 times to go from A to B).
What do you mean exactly by pretty fast? For me it is important to do everything within a second (sending the request to server, processing the request, sending the K shortest paths back, and displaying them on the map), with a good internet connexion obviously.

About walking you're right, it might be smarter to differentiate it. I'll investigate it later and let you know the results.

The problem is not as simple as it sounds, as it implies dynamics graphs, multi-criteria searchs and some extra issues proper to public transportation.
• ###### 3. Re: Graph theory - find path from point A to point B in a tram / bus network
jun_pl_56 wrote:

About Dijkstra, I will give it a try, but I'll have to modify it, as i have to take into account the waiting time between two changes, and also limit the number of changes
(because I'm not sure someone would like to change bus 5 times to go from A to B).
What do you mean exactly by pretty fast? For me it is important to do everything within a second (sending the request to server, processing the request, sending the K shortest paths back, and displaying them on the map), with a good internet connexion obviously.
I suspect your 1 second will be swallowed up by the network without leaving anything for the routing.

Since you have now expanded the problem from just a shortest path to the K shortest paths you have a lot more work to do. For one thing, you need to decide whether or not the K shortest paths should be disjoint (containing no common node or link except the starting or ending link).

For this I have only ever used the Suurballe algorithm which finds the pair of disjoint shortest paths. I understand it can be extended to the K shortest disjoint paths but I have never looked at it.

>
About walking you're right, it might be smarter to differentiate it. I'll investigate it later and let you know the results.

The problem is not as simple as it sounds, as it implies dynamics graphs, multi-criteria searchs and some extra issues proper to public transportation.
As I see it, there are at least three parts to the dynamics. First one has the slow moving dynamics caused by the way the timetable changes during the day/week, second one has the statistical dynamics caused by local traffic conditions and finally one has the dynamics associated with person making the journey (how fast he/she walks).

These last two are the real problem areas. Many many years ago (1979) I did some very interesting work on 'covariance analysis' where one estimated the mean and covariance propagation through a non-linear dynamic system. I can see that this work might have an application here but I have not thought it through and it certainly will not be computed from scratch in 1 second. Again, I have not thought it through but I can see that much of the covariance calculation can be done as a background thread that sets up the network for use with a much quicker algorithm such as Djikstra.

This sounds an interest (college?) project.
• ###### 4. Re: Graph theory - find path from point A to point B in a tram / bus network
The K-paths don't necesseraly need to be disjoint here, the more important is to provide the user with the second and third best alternative. I guess I can store intermediate results when the algorithm runs, it will take extra time but at the end I'll have what I want.
Unfortunately it's not a college work, and I have very limited time and resource to set up everything. I'll try what you suggested, ie running a Dijkstra algorithm on the global graph and see the results.

At the same time I've thought of a different approach of the problem :
as i know the coordinates of every stop, i was thinking of scanning the 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 reach the destination from there, I reiterate the same operation and so on. This could also be done bidirectionnaly.
I understood they use a similar thing in mapping companies, but it's a bit easier because they don't take into account mult-modal transports.
• ###### 5. Re: Graph theory - find path from point A to point B in a tram / bus network
I did the same once (travel by car/bus/train or walk from point A to point B or any combination thereof). You can use an ordinary Dijkstra algorithm with a few precautions: at every bus/tram stop you have to add edges from point A (the bus/tram stop) to any point B (another bus/tram stop) and add costs to every waiting time (at that stop). If the bus/tram network is 'reasonable' you can apply a Bell heuristics (add the cost of a straight line (Euclidean distance) from your current position to the destination). This algorithm worked fine on the Dutch railway/buses network joined with the Dutch highway network.

kind regards,

Jos