Added on top of this repo to evaluate our bounds on GTSP.
A Generalized Traveling Salesman Problem (GTSP) Solver.
This solver is implemented in Julia (http://julialang.org/). It is now compatible with Julia v1.0. Update Julia to v1.0 before running GLNS.
More information on the solver is given at https://ece.uwaterloo.ca/~sl2smith/GLNS/
The solver and its settings are described in the following paper [DOI] [PDF]:
@Article{Smith2017GLNS,
author = {S. L. Smith and F. Imeson},
title = {{GLNS}: An Effective Large Neighborhood Search Heuristic
for the Generalized Traveling Salesman Problem},
journal = {Computers \& Operations Research},
volume = 87,
pages = {1-19},
year = 2017,
}
Please cite this paper when using GLNS.
GLNS has three default settings: slow, default, and fast.
It also has several flags that can be used to give to give the solver
timeout, or to have it quit when a solution cost threshold is met.
The solver can be run from the command line or from the Julia REPL.
The input to the solver is a text file in GTSPLIB format, which is an extension of the TSPLIB format.
Julia has a startup time of approximately 0.5 seconds, which gives this
option a delay over option two below. The syntax is as follows:
$ ./GLNScmd.jl <path_to_instance> -options
The following are a few examples
$ ./GLNScmd.jl test/39rat195.gtsp -mode=fast -output=tour.txt```
GLNS can also be set to run "persistently" for a given amount of time.
The following example will run for 60 seconds before terminating.
`$ ./GLNScmd.jl test/39rat195.gtsp -max_time=60 -trials=100000`
### Running from the Julia REPL
For this method you should launch Julia, include the GLNS module, and then
call the solver. This is done as follows:
$ julia julia> include("GLNS.jl") julia> GLNS.solver("<path_to_instance>", options)
The following are a few examples. The first is the default setting. The
last example is a persistent solver that will run for at most 60 seconds,
but will quit if it finds a tour of cost 13,505 or less (the best known solution
for this instance is 13,502):
julia> GLNS.solver("test/39rat195.gtsp") julia> GLNS.solver("test/39rat195.gtsp", mode="slow") julia> GLNS.solver("test/107si535.gtsp", max_time=60, budget=13505, trials=100000)
## Index of files
The GLNS solver contains the following files.
- GLNScmd.jl --- command line solver
- GLNS.jl --- Main Julia solver
- src/ -- contains
- adaptive_powers.jl
- insertion_deletion.jl
- parameter_defaults.jl
- parse_print.jl
- tour_optimizations.jl
- utilities.jl
- test/ -- contains sample GTSP instances for testing and as example inputs
## License
Copyright 2018 Stephen L. Smith and Frank Imeson
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at <http://www.apache.org/licenses/LICENSE-2.0>
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
## Contact information
Prof. Stephen L. Smith
Department of Electrical and Computer Engineering
University of Waterloo
Waterloo, ON Canada
web: <https://ece.uwaterloo.ca/~sl2smith/>
email: <[email protected]>
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent