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

• 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

## 1 Answer

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