AnsweredAssumed Answered

Find best order route is slow

Question asked by modybsystematics-co-il-esridist

on Jan 14, 2016
Latest reply on Jan 16, 2016 by modybsystematics-co-il-esridist

Like • Show 0 Likes0
Comment • 7

We have a network dataset with around 300k lines.

We have a car that has to do inspections on some elements along a route. It needs to visit 500-700 elements (most of them are close to each other).

The points create one simple route but are not ordered.

The way we solve the problem is to load the points as steps and to ask for best order route (usually the first point is really the start).

It creates a good route that visits every element.

The only problem is the time it takes. About 7 minutes to 700 points.

When the points is ordered it takes a few seconds.

Is there any way to speed the best route algorithm?

Thanks

No one else has this question

Outcomes

7 Replies

Dan_Patterson Jan 14, 2016 2:50 AM
Mark Correct
Correct Answer
That is a lot of combination to figure out. Have you tried a
lexicographic sort on the coordinates? Or is that what you mean by sorted? You really need to limit you search radius for the next possible candidate.
Like • Show 0 Likes0
Actions
- modybsystematics-co-il-esridist @ Dan_Patterson on Jan 14, 2016 10:23 PM
  Mark Correct
  Correct Answer
  Hi Dan
  
  The route is not going in one direction only but it might be a good idea to order the points by ariel distance first and then run the route in this order.
  Do you know any ready to use tool that will order the point (starting from a known point) or do I have to write it?
  
  Thanks
  Like • Show 0 Likes0
  Actions
  - Dan_Patterson @ modybsystematics-co-il-esridist on Jan 14, 2016 10:57 PM
    Mark Correct
    Correct Answer
    short of a simple sort on the XY coordinates of the points, which may speed things up, a spanning tree from an origin point may help since it provides the shortest connections between points. I haven't experimented in a long time, but you could give this a try http://www.arcgis.com/home/item.html?id=6ce9db93533345e49350d30a07fc913a (spanning tree tools) it may give you some ideas.
    Like • Show 0 Likes0
    Actions
ciava.at Jan 14, 2016 2:50 AM
Mark Correct
Correct Answer
Mody, NA based on the well-known Dijkstra's algorithm so if you need speed you need more rules/restriction so algorithm discards useless path evaluate
Like • Show 0 Likes0
Actions

ciava.at Jan 14, 2016 11:32 PM

Mody you can also approximate solution collapse your points of same edge in a single point ('most of them are close to each other') and then order all points after solve.

Actions

Dan_Patterson

@ ciava.at on Jan 14, 2016 11:44 PM

I think Domenico is on to something...your problem could be greatly simplified if you could group points or cluster them and use a representative location. If you have 5 origin points all on the same block, it really doesn't matter their individual route solutions, since they will effectively be identical...if you throw a coffee break into the mix, your grouping distance could expand to a couple of blocks. So I would follow his suggestion and have a good look at your point pattern(s) and see if there is any inherent clustering as origins and/or destinations

Actions

modybsystematics-co-il-esridist

@ Dan_Patterson on Jan 16, 2016 10:01 PM

I think I found a great solution (Dan post gave me the idea).

We work so much with complex software that we forget how quick a computer is when it just do in memory calculation.

The code below sort the point by distance (direct distance). It is running in memory and takes less the 3 seconds for 2000 points (including reading and writing to layer).

import arcpy
import sys
import traceback
import math
points = arcpy.GetParameterAsText(0)
# globals
coords = []
order = []
# find the closest point that is not connected
def FindClosest(x,y):
    global coords
    global order
    max1 = 1000000000000
    closest = -1
    for i in range(0, len(order)):
        if (order[i] != 0): continue
        # noo need for sqrt - just looking for the smallest
        dist = math.pow((coords[i][0] - x),2) + math.pow((coords[i][1] - y),2)
        if (dist < max1):
            max1 = dist
            closest = i
    return closest
try:
    #read into memory
    with arcpy.da.SearchCursor(points, ["SHAPE@X", "SHAPE@Y"]) as cursor:
        for row in cursor:
            p = [row[0],row[1]]
            coords.append(p)
            order.append(0)
    arcpy.AddMessage("read %s records" % len(coords))
    # first record
    next1 = 2
    order[0] = 1
    x1 = coords[0][0]
    y1 = coords[0][1]
    # endless loop until we have no free points
    while(True):
        x = FindClosest(x1,y1)
        if(x == -1): break # done
        order[x] = next1
        x1 = coords[x][0]
        y1 = coords[x][1]
        next1 = next1 + 1
    # update results
    i = 0
    with arcpy.da.UpdateCursor(points, ["order1"]) as cursor:
        for row in cursor:
            row[0] = order[i]
            cursor.updateRow(row)
            i = i + 1
    #for i in range(0,len(order)):
    #    arcpy.AddMessage("point %s order = %s" % (order[i],i))
except:

1 person found this helpful

Actions

GeoNet

The Esri Community

Find best order route is slow

Outcomes

Related Content

Recommended Content