Chris, Thanks for responding to Doug's query and correcting my incorrect response. It is continually amazing to me how well this software works (on a Garmin GPS system and Microsoft Streets) both in routing between two points and Streets in optimizing multipoint routes.
Gordon Uber At 03:20 AM 7/21/2008, Chris Lusby Taylor wrote: >Hi Doug, >The task of finding the shortest/quickest route from A to Z along a network >of roads is not the same as the Travelling Salesman Problem, nor its >generalisation the Vehicle Routing Problem, unless you also say you want to >go via C, D, E etc in no particular order but without visiting any of them >twice. >Your GPS is usually solving the very much simpler problem of merely finding >the shortest/quickest route from A to Z. >To do this, all it needs to do is to find the distance to all the crossroads >you can reach directly from A, then the minimum distance to all the >crossroads you can reach from them, and so on until you find yourself at Z >by one route and all other routes that haven't yet reached Z are already >longer. >By the way I'm sure it does use vectors, not bitmaps, to draw the route, and >a table of the properties of all road segments. >This may still be a substantial task, and there are ways to direct the >search to improve the chances that the first route you try will be the best. >For instance, you can use a 'meet in the middle' approach - fan out from >both A and Z until you find paths that meet. >Either way, it can then use a critical-path type analysis to see which >is/are the shortest route(s). For instance, if C is 20 miles from A, D is 25 >miles from A but the road CD is 6 miles long, it cannot be on the shortest >route. > >However, I do have a GPS that can tell me how to get from A to Z via B and >C, where B and C are visited in any order to minimise the total journey. >That is the Travelling Salesman Problem, near enough. > >Best wishes >Chris --------------------------------------------------- https://lists.uni-koeln.de/mailman/listinfo/sundial
