-
Notifications
You must be signed in to change notification settings - Fork 0
/
READ.txt
40 lines (32 loc) · 2 KB
/
READ.txt
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
TSP Project
Jonas Actor, Tom Klotz, Jeremy Tillay
CAAM 571
TSP Algorithms:
tsp.py is the main file and runs the full solution
bandb.py contains the algorithm for performing branch and bound
outputModel contains the I/O processes for formatting the solution to be read by the user
Data MUST be stored in the data folder as a .txt file. It MUST have no empty lines or the program will have an error. It must be formatted exactly as dsecribed in project description.
The folder runtime logs is automatically updated with each run keeping track of runtime, number of branches searched, optimal solution, and optimal objective.
The solutions are printed to console and written to .sol.out files with name matching the name of the data file storing the traveling salesman edge and vertex set. These files can be read with any .txt reader.
Usage:
$python tsp.py
Will prompt the user for input
write 'filename.txt' or just press enter to default to ulysses22.txt file. File must be stored in the data folder
solution tour is outputted and written to a file in the solutions folder. runtime info is written in runtimelogs folder.
Upper Bound Algorithms: (Greedy) Nearest Neighbor, 2Opt, 3Opt, 2/3Opt
Description of files:
GNN.py : finds nearest neighbor TSP solution from a specified starting node
enhance.py : performs 2Opt and 3Opt on a provided TSP solution
getTSP_UB.py : calls GNN and determines which enhancement scheme should be used
UpperBound.py : user interface; reads in .txt file, makes node-node adjacency matrix, and prints solution
Usage:
$ python UpperBound.py '<file name>' e
<file name> : name of file, in format specified by project
e : an integer, either 0, 2, 3, or 23:
0 : runs GNN; no enhancement algorithm
2 : performs 2Opt on GNN solution
3 : performs 3Opt on GNN solution
23 : perofrms 2Opt on GNN solution, and then 3Opt on 2Opt's solution
Output:
Displays edges and weights in optimal TSP path, as per project description
Also outputs time elapsed, and the number of enhancement moves made for the optimal solution