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

## closed as off-topic by t3chb0t, Toby Speight, Mast, IEatBagels, Gareth ReesOct 16 '18 at 21:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Lacks concrete context: Code Review requires concrete code from a project, with sufficient context for reviewers to understand how that code is used. Pseudocode, stub code, hypothetical code, obfuscated code, and generic best practices are outside the scope of this site." – t3chb0t, Toby Speight, Mast, IEatBagels, Gareth Rees
If this question can be reworded to fit the rules in the help center, please edit the question.

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