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.