This repository has been archived by the owner on May 31, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathsolve_tsp.py
131 lines (111 loc) · 5.17 KB
/
solve_tsp.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
from time import time
from random import seed, randint
from argparse import ArgumentParser
from pandas import read_csv
from numpy import linalg, array
from math import sin, cos
from visualizer.visualizer import Visualizer
from algo.greedy_rotate import greedy_rotate
from algo.cross_path_dismantling import cross_path_dismantling
from algo.two_opt import two_opt
from algo.simulated_annealing import sim_annealing
ini_time = time() # start the timer here
# ===== List of datasets =====
# wi29 27603 Western Sahara
# dj38 6656 Djibouti
# berlin52 7544 Berlin
# ch150 6528 Churritz
# qa194 9352 Qatar
# pr264
# lin318 Lin/Kernighan
# pr439
# rat575
# rat783
# uy734 79114 Uruguay
# zi929 95345 Zimbabwe
# sw24978 855597 Sweden
# ===========================
# argument parser -----------------------------------------------------------------
parser = ArgumentParser(description='Solving the TSP.')
parser.add_argument('input', metavar='i', nargs='?',
help='the path to input coordinates file')
parser.add_argument('output', metavar='o', nargs='?', default='output-tour.txt',
help='the path to output tour file')
parser.add_argument('--time', metavar='-t', type=int, nargs='?', default=180,
help='the maximum number of seconds that the program should run')
parser.add_argument('--algo', metavar='-a', type=int, nargs='?', default=0,
help='manually select algorithm: 1 - sa; 2 - dcp - 2opt; 3 - 2-opt')
parser.add_argument('--loop', metavar='-l', type=int, nargs='?', default=1,
help='loop the program for a given time')
parser.add_argument('-v', action='store_true',
help='visualize the result at the end')
args = parser.parse_args()
args_value = vars(args)
# end of argument parser ----------------------------------------------------------
# helper functions ----------------------------------------------------------------
def gen_node(num): # random dataset generator
seed()
a = []
for _ in range(num):
a.append([randint(0, num * 2), randint(0, num * 2)])
return array(a)
def rotate(origin, point, angle): # rotates a point about an origin by an angle
ox, oy = origin
px = point[0]
py = point[1]
qx = ox + cos(angle) * (px - ox) - sin(angle) * (py - oy)
qy = oy + sin(angle) * (px - ox) + cos(angle) * (py - oy)
return qx, qy
# end of helper functions ---------------------------------------------------------
# data & arguments parsing --------------------------------------------------------
node = read_csv(args_value['input'], sep=" ", header=None, names=['idx', 'x', 'y']).set_index('idx')[['y', 'x']].values
euclidean_map = [[0 for x in range(len(node))] for y in range(len(node))]
for i in range(len(node)):
for j in range(len(node)):
euclidean_map[i][j] = int(round(linalg.norm(node[i] - node[j])))
for n in node:
n[0], n[1] = rotate([0, 0], [n[0], n[1]], 1)
# end of data & arguments parsing -------------------------------------------------
# main <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><>><><><><><><><><><><><><><>
for loop in range(args_value["loop"]):
deadline = time() + args_value["time"]
final_length = None
final_route = None
g_length, g_route = greedy_rotate(euclidean_map)
print("greedy cost:", g_length, "(time cost:", time() - ini_time, "s)")
if args_value["algo"] == 1 or (args_value["algo"] == 0 and len(node) <= 50):
best_sa_length = None
best_sa_route = None
for _ in range(int(args_value["time"] / 30 - 1)):
# worst case 30 sec per run
sa_length, sa_route = sim_annealing(euclidean_map, g_length, g_route, 2000000)
if best_sa_length is None or sa_length < best_sa_length:
best_sa_length = sa_length
best_sa_route = sa_route
final_length = best_sa_length
final_route = best_sa_route
elif args_value["algo"] == 2 or (args_value["algo"] == 0 and len(node) <= 500):
c_length, c_route = cross_path_dismantling(euclidean_map, node, g_route)
print("cross path cost:", c_length, "time cost:", time() - ini_time, "s)")
t_length, t_route = two_opt(euclidean_map, c_length, c_route, deadline)
print("2-opt cost:", t_length, "(time cost:", time() - ini_time, "s)")
final_length = t_length
final_route = t_route
else:
t_length, t_route = two_opt(euclidean_map, g_length, g_route, deadline)
print("2-opt cost:", t_length, "(time cost:", time() - ini_time, "s)")
final_length = t_length
final_route = t_route
output_string = "tour cost: " + str(final_length) + "\n" + "tour: " + str(final_route) + "\n"
mode = 'w'
if args_value["loop"] > 1:
mode = 'a+'
out = open(args_value['output'], mode)
out.write(output_string)
out.close()
print("final tour cost:", final_length)
print("--- finish (total time cost:", time() - ini_time, "s) ---")
print()
if loop == (args_value["loop"] - 1) and args.v:
Visualizer(node, final_length, final_route)
# end of main <><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><>