GLNS – A Generalized Traveling Salesman Problem (GTSP) Solver

alt text 

Stephen L. Smith and Frank Imeson

Department of Electrical and Computer Engineering
University of Waterloo
stephen.smith at uwaterloo.ca
fcimeson at uwaterloo.ca

Solver download and information

Citation

@Article{Smith2016GLNS,
  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,
}

Using the Solver

Running from the command line

$ ./GLNScmd.jl <path_to_instance> -options
$ ./GLNScmd.jl test/39rat195.gtsp
$ ./GLNScmd.jl test/39rat195.gtsp -mode=fast -output=tour.txt
$ ./GLNScmd.jl test/39rat195.gtsp -max_time=30 -trials=10000

Running from the Julia REPL

$ julia
julia> include("GLNS.jl")
julia> GLNS.solver("<path_to_instance>", options)
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)

Problem Libraries

New best solutions

Problem Instance    Previous Best    New Best Solution
baf107att532 3,891 3,880
baf113pa561 442 431*
baf115rat575 1,346 1,330
baf131p654 5,827 5,824
baf132d657 8,160 8,132
baf145u724 7,934 7,354
baf157rat783 1,841 1,700
baf201pr1002 48,807 48,400
baf207si1032 18,936 18,836
baf212u1060 44,488 38,639
150i2000-605 5,942 5,940
200i3000-805 6,913 6,902
144pcb1173-12x12 16,418 16,412

License

Copyright 2017 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.

Feedback

We are thankful for any feedback or potential bugs encountered when using the GLNS solver. Please send feedback to stephen.smith at uwaterloo.ca