/
tsp_rnnopt2.py
252 lines (195 loc) · 7.86 KB
/
tsp_rnnopt2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
import math
import sys
import os
import copy
import time
def main(argv):
#start counting time
start_time = time.time()
#time limit is current time + 100 minutes
time_limit = time.time() + 6000
# Get the file name from the command line argument
filename = os.path.splitext(sys.argv[-1])[0]
# List to hold all the data from the file
data = readInput(filename)
graph = createGraph(data)
walk,distance = repetativeNearestNeighbor(graph)
print("Before 2 opt")
print(walk)
print(distance)
##print (time.time())
##print(time_limit)
if time.time() < time_limit:
improvedTour = twoOptTour(walk, graph, filename,time_limit)
walk = improvedTour
distance = totalLength(improvedTour, graph)
print("After 2 opt")
print(walk)
print(distance)
time_taken = time.time() - start_time
print("Time taken: %d" %time_taken)
writeOutput(distance, walk, filename)
# This function takes a filename and returns a list of tuples containing (city number, x-coordinate, y-coordinate)
def readInput(filename):
data = []
with open(filename + ".txt", "r") as inputFile:
for line in inputFile:
source, sourceXCoordinate, sourceYCoordinate = (int(i) for i in line.split())
data.append(tuple([source, sourceXCoordinate, sourceYCoordinate]))
#https://stackoverflow.com/questions/11354544/read-lines-containing-integers-from-a-file-in-python
inputFile.close()
return data
# This function will write the tour length and each city in tour list
def writeOutput(tourLength, tourList, filename):
filename = filename + ".txt.tour"
with open(filename, "w") as outputFile:
outputFile.write("%d\n" %tourLength)
# Write each city in tour. Exclude writing the last city
# since each city should only appear once. Last city is a repeated vertex
lastElement = len(tourList) - 1
for city in tourList[0:lastElement]:
outputFile.write("%d\n" %city)
outputFile.close()
# Will take a list of tuples representing city name, xCoordinate, y-Coordinate and create an adjacency list
def createGraph(data):
# Graph will be represented by an adjacency list
graph = {}
distanceTable = [[0 for i in range(len(data))]for j in range(len(data))]
# Create an adjacency list
# {City1: {neighbor1: distance, neighbor2: distance...}...}
# Iterate over each location
for source, xCoordinate, yCoordinate in data:
currentSource = source
currentX = xCoordinate
currentY = yCoordinate
# Create a dictionary consisting of all neighbors of currentSource and the distance to currentSource
neighbors = {}
for dest, destX, destY in data:
# Don't calculate the distance from one location to the same location
if dest != currentSource:
if distanceTable[source][dest] > 0:
distance = distanceTable[source][dest]
else:
distance = calculateDistance(currentX, destX, currentY, destY)
distanceTable[source][dest] = distance
distanceTable[dest][source] = distance
neighbors.update({dest: distance})
graph[currentSource] = neighbors
return graph
# This function returns the euclidean distance between two points given x and y coordinates
def calculateDistance(x1, x2, y1, y2):
x_diff = x1 - x2
y_diff = y1 - y2
distance = math.sqrt(x_diff * x_diff + y_diff * y_diff)
# Return the distance rounded to the nearest integer
return int(round(distance))
def nearestNeighbor(graph):
cities = graph.keys()
citiesVisited = 0
currentCity = 0
order = [0]
while(citiesVisited < len(cities)):
minDistance = sorted(graph[currentCity], key=graph[currentCity].get)
for city in minDistance:
if city in order:
continue
else:
nearest = city
order.append(nearest)
break
citiesVisited += 1
currentCity = nearest
order.append(order[0])
return order
def repetativeNearestNeighbor(graph):
cities = graph.keys()
citiesVisited = 0
bestDistance = float('inf')
bestOrder = []
# tour each city
for i in range(len(cities)):
citiesVisited = 0
order = [i]
currentCity = i
while(citiesVisited < len(cities)):
# sort neighbors of currentCity by shortest distance
minDistance = sorted(graph[currentCity], key=graph[currentCity].get)
for city in minDistance:
# if city has been visited, exclude it, else add it to the tour
if city in order:
continue
else:
nearest = city
order.append(nearest)
break
citiesVisited += 1
currentCity = nearest
order.append(order[0])
tourLength = totalLength(order, graph)
# if this tour is shorter than the best tour so far, it is the new best tour
if tourLength < bestDistance:
bestDistance = tourLength
bestOrder = order
return bestOrder, bestDistance
# calculate tour length
def totalLength(walk, graph):
totalDistance = 0
walkLength = (len(walk)-1)
# iterate through all walk items
for i in range(walkLength):
sourceCity = walk[i]
if (i+1) > (walkLength): # fixes out of range
destCity = walk[0]
else:
destCity = walk[i+1]
# look up distance between source city and destination city in graph
distance = graph[sourceCity][destCity]
totalDistance += distance
return totalDistance
# This function will use the two opt local search algorithm to improve TSP solution
# https://en.wikipedia.org/wiki/2-opt
def twoOptTour(tour, graph, filename,time_limit):
bestDistance = totalLength(tour, graph)
madeChange = True
# Keep creating a new tour if a previous call to create new tour created a better solution
# Otherwise return the tour
while(madeChange == True):
#print("while")
if time.time() > time_limit:
break
madeChange, tour = createNewTour(tour, graph, filename,time_limit)
return tour
def createNewTour(tour, graph,filename,time_limit):
bestDistance = totalLength(tour, graph)
# Start at city m that is not the start and perform swaps from m+1 to length of the tour - 1
# since last city cannot be swapped either
for m in xrange(1, len(tour) - 1):
for n in xrange(m + 1, len(tour) - 1):
#if time limit has been reached end loop
if time.time() > time_limit:
break
#create a new tour and get its distance
newTour = twoOptSwap(tour, m, n)
newDistance = totalLength(newTour, graph)
# If the new distance is better than best distance, assign tour to the new improved tour
if(newDistance < bestDistance):
tour = newTour
writeOutput(newDistance, tour, filename)
return True, tour
return False, tour #Indicate no changes was made
# Perform a 2-opt swap when given a tour and cities m and n
# https://en.wikipedia.org/wiki/2-opt
def twoOptSwap(tour, m, n):
newTour = []
# take tour from start to city m - 1 and add it to new tour
newTour.extend(tour[:m])
# take tour m to n and add them in reverse order
index = n
while(index >= m):
newTour.append(tour[index])
index -= 1
# take the rest of the tour after m and add it to the new tour
newTour.extend(tour[n+1:])
return newTour
if __name__ == "__main__":
main(sys.argv)