Results 1 to 10 of 10

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

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    5

    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 !
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    5
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    I'm not sure I understand: Dijkstra's Algorithm runs in polynomial time. Do you need something faster than O(n^{3})? All those constraints you have there could be modeled, I think, by cleverly choosing weights for the edges in your graph.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2010
    Posts
    5
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jul 2010
    Posts
    5
    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!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    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!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jul 2010
    Posts
    5
    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!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    You're very welcome. Have a good one!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Find maximum point of curve graph
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: September 29th 2011, 10:49 AM
  2. Replies: 1
    Last Post: April 6th 2011, 07:44 AM
  3. How to find the maximum point of a graph
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: May 2nd 2010, 04:49 PM
  4. Replies: 1
    Last Post: April 27th 2009, 03:30 PM
  5. Replies: 2
    Last Post: December 9th 2008, 02:41 AM

Search Tags


/mathhelpforum @mathhelpforum