This content has been marked as final.
Show 5 replies

1. Re: Graph theory  find path from point A to point B in a tram / bus network
843853 Jul 20, 2010 11:04 AM (in response to 843853)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
843853 Jul 20, 2010 11:27 AM (in response to 843853)Hi,
thank you for your answer.
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, multicriteria 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
843853 Jul 20, 2010 12:14 PM (in response to 843853)jun_pl_56 wrote:
I suspect your 1 second will be swallowed up by the network without leaving anything for the routing.
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.
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.
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).
The problem is not as simple as it sounds, as it implies dynamics graphs, multicriteria searchs and some extra issues proper to public transportation.
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 nonlinear 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
843853 Jul 20, 2010 2:07 PM (in response to 843853)The Kpaths 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 multmodal transports. 
5. Re: Graph theory  find path from point A to point B in a tram / bus network
JosAH Jul 25, 2010 11:27 AM (in response to 843853)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