2-opt algorithm for traveling salesman [closed]

Question

I wrote a 2-opt algorithm to be used in a program and noticed (using profile) that the 2-opt is eating up a lot of time. I have tried a few things to make it run faster, but I am out of ideas. Any tips on making it run faster, or a better way to write a 2-opt algo?

def twoOpt(self):
    '''Peforms 2-opt search to improve route'''
    for index, route in enumerate(self.routes):
        for element in xrange(len(route.fields)):
            i = element + 1
            k = i + 1
            while k <= len(route.fields):
                newRoute = Route(route.scout)
                for field in self.twoOptSwap(route.fields, i, k):
                    newRoute.addField(field)
                newRoute.calcRouteCost()
                if newRoute.cost < route.cost:
                    self.routes[index] = newRoute
                k += 1

def twoOptSwap(self, fields, i, k):
    start = fields[0:i]
    middle = fields[i:k]
    middle = middle[::-1]
    end = fields[k:]
    newFields = start + middle + end
    return newFields

Each route object contains a list of fields (route.fields) and route.calcRouteCost() sets route.cost with a value.

Answer 1

• A slice of a list is a new list, so this code constructs five lists:

  start = fields[0:i]
  middle = fields[i:k]
  middle = middle[::-1]
  end = fields[k:]
  newFields = start + middle + end
  

  This is probably faster:

  newFields = fields[:]
  newFields[i:k] = fields[k-1:i-1:-1]
  

• Instead of adding fields one by one in the code below, you could change Route to accept the list of fields in the constructor.

  newRoute = Route(route.scout)
  for field in self.twoOptSwap(route.fields, i, k):
      newRoute.addField(field)  
  

  Note also that after reversing a segment of the route, a complete recalculation of cost is not necessary. You only need to consider how the cost changes where the segments join, assuming cost does not depend on direction of travel.

• Instead of

  for element in xrange(len(route.fields)):
      i = element + 1
  

  simply

  for i in xrange(1, len(route.fields) + 1):
  

• Instead of a while loop

  k = i + 1
  while k <= len(route.fields):
      ...
      k += 1      
  

  a for loop

  for k in xrange(i + 1, len(route.fields) + 1):