ThinkGeo.com    |     Blog    |     Wiki    |     Support

Optimizations dropping stops, and optimized routes don't make any sense

I am having a couple of issues getting optimizations to work, I am hoping it is just something I’m doing wrong and/or related to the data I’m using. I am extremely interested is getting this product to work as it meets all of my company’s requirements.



Here is what I’ve done so far:


        
  1. Downloaded 2 test .SHP files from OSM. One for Ontario, Canada, and another for the state of Missouri.

  2.     
  3. I used the Routing Explorer tool to create “Routable” .SHP files, and then used the Routable .SHP files to create .RTG files.

  4.     
  5. I modified the TSP samples of the “Routing_Desktop_HowDoI” solution to use my new SHP and RTG files, and added my own waypoints to test the optimizations.


The issues I am having:


        
  1. The optimized results do not have all the original waypoints in it. For example if I optimize a route that has 20 stops via the GetRoute method, the routingResult.OrderedStops collection only has 15 stops in it. 

  2.     
  3. The optimization is all over the place. Even if I bump the iterations up to 100,000 the order they are optimized in makes no sense. This happened for both Ontario and Missouri:



Thanks in advance!



Hi Chad, 
  
 Thanks for you interested in our Routing. 
  
 For your question: 
  
 1. If you assign a list contains many locations, some of them are near the same street segment, we will only leave one location. So I think there are 5 stops ignored because this reason. 
  
 2. I think for the iteration value, when it’s a small value, the result will changed between different setting, but when the algorithm reach a limitation, the result cannot go on enhancement and the result should be the best one. So after that, the result won’t change no matter how you modify the value. 
  
 Wish that’s helpful. 
  
 BTW, thanks for your detail steps about how you test our product, could I double check whether you download data here: wiki.openstreetmap.org/wiki/Canada:Ontario#Downloads, because if you met question, we can reply you better if we get same data. 
  
 Regards, 
  
 Don

Ontario data: download.geofabrik.de/north-america/canada/ontario.html 
 Missouri data (shown above): download.geofabrik.de/north-america/us/missouri.html 
  
 I need software to optimize my waypoints and put them in the best order possible. How does removing them help me optimize them, regardless of their proximity? It makes no sense. 
  
 And my issue wasn’t the fact that the number of iterations didn’t seem to make a difference, the issue is that the order the optimized stops are never put in a reasonable order. I understand there will be variances and that calculating a perfect permutation is not possible, but these aren’t anywhere near to a usable route. 
  
 I am looking for a replacement for MapPoint to help me optimize waypoints. Will your software help me achieve this? 


Hi Chad, 



Yes the result in your screen capture looks not well, the stops order is strange, I guess maybe that’s cause by the lines haven’t been handled enough good to routing.



We want to reproduce that local and see what’s the problem, but the link you given said we don’t have permission to download ontario-latest.shp.zip and missouri-latest.shp.zip, do we need some special security for download it? Or could you please upload the data to our FTP, I think you can get an account from our sales.



I think our Map Suite Routing should be a flexible and professional product for routing, and you know the routing result related with data, so we want to reproduce your issue quickly and solve that, so make our Routing works for your scenario. 



Regards, 



Don

Chad, 
  
   I think what Don is saying regarding the stops that were removed is related to the way we treat segments in the routing engine and we will need to enhance that.  Currently, and I may be wrong, when you have a way point we behind the scenes find out what segment of road the way point is on and we try to route to there.  In our world at the moment each road segment is a whole unit and is not really sub divided.  So if you have two point on one segment, say a long road, then I think our system doesn’t handle that well.  In your case all of the stops are in a small region which isn’t a case we have had experience in.  As I said I’m not 100% sure about this but it seems to be the case. 
  
   I’m downloading the test files you mentioned now and will pass them on to Don.  Can you provide us with the list a set of test way points so we can accurately re-create your issue?  
  
 David

Hi Chad,



I think I recreated your issues with the data from the link and some test coordinates. 

For the missing stops, I figured out the missing stops happened when multi stops are located at a same segment, then it only keeps one stop for this segment. Now, we are working on to figure out a solution for that.

As for the stop order issues, I found making iterations larger would make it better but looks still have some issues and we are digging into it.







Thanks for your patience and we will update the status as soon as possible.

Troy

Hi Chad, 
  
 As mentioned, we have recreated the problem with data you provided, I guess there are 2 possible reasons, just shown it as following: 
  
 1.How did you generate the Routing Index file? Can you show us the code, I just need to have a check if everything is ok there, and otherwise, we need to implement this code by ourselves. 
  
 2.The base algorithm used in TSP is the Genetic Algorithm, it just provides an optimized option for the route, I guess there may be some problem in our implementation as you mentioned, it’s unreasonable sometimes, we will try to do some improvements there soon. 
  
 Thanks, 
  
 Johnny 


I generated the original index file using the "MapSuite Routing Explorer" tool. And I used a subsequent set of data for the state of Missouri supplied to me by Moritz at your office. In both scenarios the results were similar - missing stops and not in any order that made sense.



Here are the coordinate I was using:
   


this.lsbPoints.Items.AddRange( new object[] {
                "-90.64387,38.604334",
                "-90.642189,38.604549",
                "-90.641805,38.603822",
                "-90.641347,38.605933",
                "-90.638705,38.588056",
                "-90.63851,38.599301",
                "-90.637065,38.588615",
                "-90.636971,38.592288",
                "-90.636031,38.588225",
                "-90.635845,38.588183",
                "-90.634972,38.592352",
                "-90.634959,38.588183",
                "-90.634059,38.59294",
                "-90.633799,38.587923",
                "-90.633799,38.591253",
                "-90.633753,38.591875",
                "-90.633286,38.59101",
                "-90.633074,38.587749",
                "-90.633057,38.591067",
                "-90.632461,38.590167"
 } );



Thanks Chad,I have recreated the issue, which may need couple days for a fix, please wait a moment, and any news I will update it here. 
  
 Regards, 
 Johnny

Hi Chad,

The issue has been fixed in the latest Daily Build version 9.0.359.0 or later, please get it and have a try.

Thanks,
Johnny