[MAPSERVER-USERS] Routing Algorithm Confusion !
Dear Readers, I use Dijkstra's shortest path algorithm for route computation. I am satisfied with the accurate result it gives. Still, I feel for road segments ~ 200Million, the route computation will take a lot of time. So, is there another algorithms exist as best practices for route computation(like A*,TSP,etc)? Or, geeks write their own algorithm for route computation? Thanks and Regards, Ritesh Ambastha -- View this message in context: http://www.nabble.com/Routing-Algorithm-Confusion-%21-tp17264809p17264809.html Sent from the Mapserver - User mailing list archive at Nabble.com. ___ mapserver-users mailing list mapserver-users@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/mapserver-users
Re: [MAPSERVER-USERS] Routing Algorithm Confusion !
I guess there are several research papers on fast/quick routing on road networks ... most of them modify dijkstra's ... there are citations on *parallel* dijkstra's if you want to scale ..to large number of nodes ... Thanks Sandeep On Fri, May 16, 2008 at 5:08 AM, Ritesh Ambastha <[EMAIL PROTECTED]> wrote: > > Dear Readers, > > I use Dijkstra's shortest path algorithm for route computation. I am > satisfied with the accurate result it gives. Still, I feel for road > segments > ~ 200Million, the route computation will take a lot of time. So, is there > another algorithms exist as best practices for route computation(like > A*,TSP,etc)? Or, geeks write their own algorithm for route computation? > > Thanks and Regards, > Ritesh Ambastha > -- > View this message in context: > http://www.nabble.com/Routing-Algorithm-Confusion-%21-tp17264809p17264809.html > Sent from the Mapserver - User mailing list archive at Nabble.com. > > ___ > mapserver-users mailing list > mapserver-users@lists.osgeo.org > http://lists.osgeo.org/mailman/listinfo/mapserver-users > -- Thanks Regards Sandeep Kumar Jakkaraju ___ mapserver-users mailing list mapserver-users@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/mapserver-users
Re: [MAPSERVER-USERS] Routing Algorithm Confusion !
Thanks Sandeep, Yeah I know that there are few algorithms exist to solve this case. Please let me know few names(links) of good algorithms which are followed to solve this problem Regards, Ritesh jssandeep wrote: > > I guess there are several research papers on fast/quick routing on road > networks ... most of them modify dijkstra's ... > there are citations on *parallel* dijkstra's if you want to scale ..to > large > number of nodes ... > > Thanks > Sandeep > > > On Fri, May 16, 2008 at 5:08 AM, Ritesh Ambastha <[EMAIL PROTECTED]> > wrote: > >> >> Dear Readers, >> >> I use Dijkstra's shortest path algorithm for route computation. I am >> satisfied with the accurate result it gives. Still, I feel for road >> segments >> ~ 200Million, the route computation will take a lot of time. So, is there >> another algorithms exist as best practices for route computation(like >> A*,TSP,etc)? Or, geeks write their own algorithm for route computation? >> >> Thanks and Regards, >> Ritesh Ambastha >> -- >> View this message in context: >> http://www.nabble.com/Routing-Algorithm-Confusion-%21-tp17264809p17264809.html >> Sent from the Mapserver - User mailing list archive at Nabble.com. >> >> ___ >> mapserver-users mailing list >> mapserver-users@lists.osgeo.org >> http://lists.osgeo.org/mailman/listinfo/mapserver-users >> > > > > -- > Thanks > Regards > > Sandeep Kumar Jakkaraju > > ___ > mapserver-users mailing list > mapserver-users@lists.osgeo.org > http://lists.osgeo.org/mailman/listinfo/mapserver-users > > -- View this message in context: http://www.nabble.com/Routing-Algorithm-Confusion-%21-tp17264809p17270028.html Sent from the Mapserver - User mailing list archive at Nabble.com. ___ mapserver-users mailing list mapserver-users@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/mapserver-users
Re: [MAPSERVER-USERS] Routing Algorithm Confusion !
Ritesh, FWIW a long time ago I wrote a route finding algorithm for a commercial desktop mapping product (Personal Navigator I think it was called) At the time I decided on the A* algorithm - which seemed to work quite well on the UK road data 1:5 I believe this is one of the algorithms available in the PgRouting package, although I haven't tested this implementation myself regards Tim On May 16, 2008, at 1:38 AM, Ritesh Ambastha wrote: Dear Readers, I use Dijkstra's shortest path algorithm for route computation. I am satisfied with the accurate result it gives. Still, I feel for road segments ~ 200Million, the route computation will take a lot of time. So, is there another algorithms exist as best practices for route computation(like A*,TSP,etc)? Or, geeks write their own algorithm for route computation? Thanks and Regards, Ritesh Ambastha -- View this message in context: http://www.nabble.com/Routing-Algorithm-Confusion-%21-tp17264809p17264809.html Sent from the Mapserver - User mailing list archive at Nabble.com. ___ mapserver-users mailing list mapserver-users@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/mapserver-users ___ mapserver-users mailing list mapserver-users@lists.osgeo.org http://lists.osgeo.org/mailman/listinfo/mapserver-users