GLNS – A Generalized Traveling Salesman Problem (GTSP) Solver

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 installation and usage

• The GLNS solver is maintained at the following GitHub repository

• The solver is written in the language Julia: [download Julia]

• GLNS can be installed through the Julia package manager:

$ julia
julia> Pkg.add("GLNS")
julia> import GLNS
julia> GLNS.solver("<path_to_instance>", options)

• After downloading the file [GLNScmd.jl], the solver can also be used via the command line as

$ ./GLNScmd.jl <path_to_instance> -options

Details on solver and citation

• The GLNS solver is a novel large neighborhood search algorithm that operates by iteratively constructing and destroying tours.

• This is combined with simulated annealing to accept/reject new tours found through the iterative process.

• The algorithm and its details are presented in the following paper [PDF]:

@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,
}

• Please cite this paper when using GLNS in your research

Problem Libraries

• Instances are provided in the GTSPLIB format

• GTSP-LIB is [available here]

• [LARGE-LIB] (1MB compressed file), originally from [here], but appears to no longer be available.

• BAF-LIB, and MOM-LIB instances and best known solutions are [available here]

• SAT-LIB instances and best known solutions: [SAT-LIB Library] (27 MB compressed file)

• GTSPplus-LIB instances and best known solutions: [GTSPplus-LIB Library] (16 MB compressed file)

New best solutions

• We have found several new best solutions for BAF-LIB and MOM-LIB.

• New best tours: [download new best tours]

• Note: the solution for baf113pa561 of cost 431 was found using the Memetic Solver by Gutin and Karapetyan. GLNS found a solution of cost 434.

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