# 2-opt algorithm for traveling salesman [closed]

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.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.

• These appear to be two methods of a class. Could you include the whole class? Also show an example what the input data structure and the output look like. – 200_success Dec 10 '14 at 19:31

• 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):


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.

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):