-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathREADME.txt
executable file
·175 lines (120 loc) · 4.02 KB
/
README.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
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
LKH is an implementation of the Lin-Kernighan traveling salesman heuristic.
The code is distributed for research use. The author reserves all rights to
the code.
INSTRUCTIONS FOR INSTALLATION: (Version 3.0.6 - May 2019)
-----------------------------
The software is available in gzipped tar format:
LKH-3.0.6.tgz (approximately 2.3 MB)
Download the software and execute the following UNIX commands:
tar xvfz LKH-3.0.6.tgz
cd LKH-3.0.5
make
An executable file called LKH will now be available in the directory LKH-3.0.6.
To test the installation run the program by typing ./LKH pr2392.par.
Then press return. The program should now solve a TSP instance with 2392 nodes.
For testing the installation on an mTSP problem, type ./LKH whizzkids96.par.
Then press return.
A two-level tree is used as the default tour representation.
A three-level tree representation may be used instead by compiling the
source code with the compiler option
-DTHREE_LEVEL_TREE
Just edit the first line in SRC/Makefile and execute the commands
make clean
make
CHANGES IN LKH-3.0.6:
---------------------
Added code for solving the Steiner traveling salesman problem (STTSP).
New keyword
REQUIRED_NODES_SECTION
CHANGES IN LKH-3.0.5:
---------------------
Added code for solving the open close multiple traveling salesman problem (OCMTSP).
New keyword
EXTERNAL_SALESMEN
CHANGES IN LKH-3.0.4:
---------------------
Added code for solving the colored traveling saleman problem (CTSP).
The node coloring is described in a
CTSP_SET_SECTION
New initial tour algorithm: CTSP
Added code solving the minimum latency problem (MLP).
CHANGES IN VERSION 3.0.3:
-------------------------
Candidate sets may now be created by means of POPMUSIC by giving the following
specification in the parameter file for LKH:
CANDIDATE_SET_TYPE = POPMUSIC
The value of the parameter MAX_CANDIDATES is used to trim the candidate set.
There are, however, some other POPMUSIC related parameters. If not specified,
they will take their default values. These parameters are:
POPMUSIC_SAMPLE_SIZE = <int>
Sample size.
Default: 10.
POPMUSIC_SOLUTIONS = <int>
Number of solutions to generate.
Default: 50.
POPMUSIC_MAX_NEIGHBORS = <int>
Maximum number of nearest neighbors used as candidates in iterated 3-opt for
POPMUSIC.
Default: 5.
POPMUSIC_TRIALS = <int>
Number of trials used in iterated 3-opt for POPMUSIC.
If the value is zero, the number of trials is the size of the subpath
to be optimized.
Default: 1.
POPMUSIC_INITIAL_TOUR = { YES | NO }
Specifies whether the first generated POPMUSIC tour is used as
initial tour for Lin-Kernighan.
Default: NO.
CHANGES IN VERSION 3.0.2:
-------------------------
Tours may now be recombined by GPX2 (Generalized Partition Crossover 2)
instead of IPT (Iterative Partial Transcription).
GPX2 is used by giving the following specification in the parameter file:
RECOMBINATION = GPX2
The possible settings are:
RECOMBINATION = { IPT | GPX2 }
IPT is default.
CHANGES IN VERSION 3.0.1:
-------------------------
New problem type: TSPDL (traveling salesman with draft limits)
NEW IN VERSION 3.0:
-------------------
New parameter keywords:
BWTSP = <integer> <integer> [ <integer> ]
DEPOT = <integer>
MAKESPAN = { YES | NO } MTSP_MIN_SIZE = <integer>
MTSP_MAX_SIZE = <integer>
MTSP_OBJECTIVE = [ MINMAX | MINMAX_SIZE | MINSUM ]
MTSP_RESULT_FILE = <string>
SINTEF_RESULT_FILE = <string>
SALESMEN = <integer>
SCALE = <integer>
VEHICLES : <integer>
New initial tour algorithms:
CVRPR
MTSP
SOP
New TSPLIB format keywords:
The specification part:
CAPACITY : <integer>
DEMAND_DIMENSION : <integer>
DISTANCE : <real>
GRID_SIZE : <real>
RISK_THRESHOLD : <integer>
SALESMEN : <integer>
SCALE : <integer>
SERVICE_TIME_SECTION
VEHICLES : <integer>
New edge weight types:
EXACT_2D
EXACT_3D
FLOOR_2D
FLOOR_3D
TOR_2D
TOR_3D
The data part:
BACKHAUL_SECTION
DEMAND_SECTION
DEPOT_SECTION
PICKUP_AND_DELIVERY_SECTION
TIME_WINDOW_SECTION