ThinkGeo.com    |     Documentation    |     Premium Support

OrderedStops.Count < StopPoints.Count?

#1

I think I have problem with routing algorithm. I am using code snippet from your example for traveling salesman’s problem : 





Dim routingResult As RoutingResult = routingEngine.GetRoute(routingLayer.StartPoint, routingLayer.StopPoints, ITERATIONS_COUNT)




After this method call, I can often see in debugger that routingResult.OrderedStops collection is shorter than routingLayer.StopPoints (specially for longer points-lists), though I expect them to be same length. Am I missing something here ? Is there a reason for routing algorithm to ignore some points ? 
Maybe some points are too close to each other ? (I can not see this by hand, because it usually happens in bigger point-sets.)




#2

Hi Dragan, 
  
 Thanks for let us know your question. 
  
 Here routingResult.OrderedStops contains the routing result, you can think it’s a data source. The routingLayer.StopPoints is data render level, if you view the class TravelingSalesmanProblemAnalysis.cs in our sample, you can see this code: 
  
  routingLayer.StopPoints.Clear();
            foreach (PointShape stop in routingResult.OrderedStops)
            {
                routingLayer.StopPoints.Add(stop);
            } 
  
 That means the value in routingLayer.StopPoints is comes from routingResult.OrderedStops by your code, if you don’t handle that, the routingLayer.StopPoints will get it’s original values. 
  
 Wish that’s helpful. 
  
 Regards, 
  
 Don

#3

Don, I have a snippet like yours in my method, and I understand it. 
 My question remains the same : Shouldn’t OrderedStops variable contain all elements (all stops) from routingLayer.StopPoints ? As far as I understand, routing algorithm should only reorder stops from routingLayer.StopPoints variable. That means, the result (routingResult.OrderedStops) should contain all points from routingLayer.StopPoints list. Am I right ?

#4

Hi Dragan, 



That’s should related with our calculate logic, if you pass many StopPoints, it will calculate the nearest route feature first, so maybe in this step some points is found corresponding the same route feature and if in routing index there isn’t valid routing feature for this point maybe cause the result points less than the stop points.



Wish that’s helpful.



Regards, 



Don

#5

I have made some more tests, and they confirm your thesis - when two points are very close to each other (for example -97.7056, 30.2645 and -97.7056, 30.2647), one of them is just removed from resulting array. That means I must somehow assign its address to the neighboring point. 

Can you maybe give me exact specification, on which distances I should expect this happening ?

#6

Hi Dragan, 
  
 I am sorry, it looks we have many optimize about this, and some logic is a little more deep. If your multiply points is near the same routing feature, they should be cluster, so it’s not exist a minimum distance here. 
  
 I hadn’t found a solution for that today, have you tried to add the lost points from your original collection? If that’s important to you please let me know, I will get some hours look into the deeper logic and see why it happen and whether we can find a workaround. 
  
 Regards, 
  
 Don

#7

Hi Dragan, 
  
 Would you please share your demo data and test coordinates here? I was wondering if there is anything missed on our end. We may create a demo for you then. 
  
 Thanks, 
 Johnny

#8

Here is my code. Points data is inlined in code. You can play with values of those two test points, in order to see how it behaves for various distances.

(If you want to test my code : routing is triggered on map click; after click you can see one of points disappear.)




Imports Microsoft.VisualBasic
Imports System
Imports ThinkGeo.MapSuite.Core
Imports ThinkGeo.MapSuite.WebEdition
Imports ThinkGeo.MapSuite.Routing
 
Partial Public Class TravelingSalesmansProblem : Inherits System.Web.UI.Page
    Private Shared routingEngine As RoutingEngine
    Private Shared routingSource As RoutingSource
    Private pointsView As DataView
 
    Private ITERATIONS_COUNT As Integer = 5
 
    Private DATA_FILE_NAME As String
    Private DATA_PATH As String
    Public Shared LEFT, TOP, RIGHT, BOTTOM As Double
 
    Protected Sub Page_Load(ByVal sender As Object, ByVal e As EventArgs) Handles Me.Load
        If (Not Page.IsPostBack) Then
            PrepareRoutingData()
            RenderMap()
        End If
    End Sub
 
    Private Sub PrepareDataForAustin()
        DATA_FILE_NAME = “Austinstreets”
        DATA_PATH = “…\App_Data&#34;
        LEFT = -97.7319606824951
        TOP = 30.2922109418945
        RIGHT = -97.7002033277588
        BOTTOM = 30.269551640136
    End Sub
    Private Sub PrepareRoutingData()
        PrepareDataForAustin()
        Dim path As String = Server.MapPath(DATA_PATH & DATA_FILE_NAME & “.shp”)
        Dim featureSource As ShapeFileFeatureSource = New ShapeFileFeatureSource(path)
        Dim rtgPath = Server.MapPath(DATA_PATH & DATA_FILE_NAME & “.rtg”)
        routingSource = New RtgRoutingSource(rtgPath)
        routingEngine = New RoutingEngine(routingSource, New AStarRoutingAlgorithm(), featureSource)
    End Sub
 
    Private Sub RenderMap()
        Map1.MapUnit = GeographyUnit.DecimalDegree
        Map1.MapBackground.BackgroundBrush = New GeoSolidBrush(GeoColor.FromHtml(”#E5E3DF"))
        Map1.CurrentExtent = New RectangleShape(LEFT, TOP, RIGHT, BOTTOM)
 
        Dim worldMapKitOverlay As WorldMapKitWmsWebOverlay = New WorldMapKitWmsWebOverlay()
        Map1.BackgroundOverlay = worldMapKitOverlay
 
        Dim routingLayer As RoutingLayer = New RoutingLayer()
        Map1.DynamicOverlay.Layers.Add(“RoutingLayer”, routingLayer)
        AddFixedStopPointsTo(routingLayer)
        routingLayer.ShowStopOrder = False
 
        Dim routingExtentLayer As InMemoryFeatureLayer = New InMemoryFeatureLayer()
        routingExtentLayer.ZoomLevelSet.ZoomLevel01.DefaultAreaStyle = New AreaStyle(New GeoPen(GeoColor.SimpleColors.Green))
        routingExtentLayer.ZoomLevelSet.ZoomLevel01.ApplyUntilZoomLevel = ApplyUntilZoomLevel.Level20
        routingExtentLayer.InternalFeatures.Add(New Feature(New RectangleShape(LEFT, TOP, RIGHT, BOTTOM)))
 
        Map1.DynamicOverlay.Layers.Add(“RoutingExtentLayer”, routingExtentLayer)
    End Sub
 
    Private Sub AddFixedStopPointsTo(ByRef pRoutingLayer As RoutingLayer)
        pRoutingLayer.StartPoint = GetNearistRoadPointFrom(New PointShape(-97.7186, 30.2899))
 
        pRoutingLayer.StopPoints.Add(GetNearistRoadPointFrom(New PointShape(-97.7556, 30.3225)))
        pRoutingLayer.StopPoints.Add(GetNearistRoadPointFrom(New PointShape(-97.6756, 30.2425)))
 
        ’ ************************  here they are ***********************
        pRoutingLayer.StopPoints.Add(GetNearistRoadPointFrom(New PointShape(-97.7056, 30.2735)))
        pRoutingLayer.StopPoints.Add(GetNearistRoadPointFrom(New PointShape(-97.7057, 30.2746))) ’ change 30.2746 to 30.2756, and it will work
 
    End Sub
    Private Function GetNearistRoadPointFrom(ByVal pRawPoint As PointShape) As PointShape
        routingEngine.FeatureSource.Open()
        Dim nearestFeatures = routingEngine.FeatureSource.GetFeaturesNearestTo(pRawPoint, Map1.MapUnit, 1, New List(Of String)().AsEnumerable())
        routingEngine.FeatureSource.Close()
        Dim pointOnRoad As PointShape = nearestFeatures(0).GetShape().GetClosestPointTo(pRawPoint, Map1.MapUnit)
        Return pointOnRoad
    End Function
 
    Protected Sub Map1_Click(ByVal sender As Object, ByVal e As MapClickedEventArgs)
        Dim routingLayer As RoutingLayer = Map1.DynamicOverlay.Layers(“RoutingLayer”) 'As RoutingLayer
 
        Dim watch As Stopwatch = New Stopwatch()
        watch.Start()
        Dim routingResult As RoutingResult = routingEngine.GetRoute(routingLayer.StartPoint, routingLayer.StopPoints, ITERATIONS_COUNT)
        watch.Stop()
 
        ’ Render the route  
        routingLayer.Routes.Clear()
        routingLayer.Routes.Add(routingResult.Route)
 
        routingLayer.StopPoints.Clear()
        ’ Show the visit sequence  
        For Each stopp As PointShape In routingResult.OrderedStops
            routingLayer.StopPoints.Add(stopp)
        Next
        routingLayer.ShowStopOrder = True
        Map1.DynamicOverlay.Redraw()
    End Sub
End Class


#9

have you tried to add the lost points from your original collection?  
 That’s what I am working on right now. 
  
 If that’s important to you please let me know  
 Yes, it is. But I guess I can fix this myself.

#10

Hi Dragan, 
  
 Thanks for your code and update. 
  
 I view deeper logic for it today, just like my previous mentioned, when you pass in multiply stop points, we will find their nearest routing feature, then if they are too closest so the nearest routing feature is the same one, only one of them will be left after routing.  
  
 I talked with our development team about it today, we think the logic here shouldn’t been the best one. We cannot enhancement it immediately, but we will add it to our list and assign source for it future.  
  
 So the solution what you are doing should be the workaround.  
  
 Any question please feel free to let us know. 
  
 Regards, 
  
 Don