## Stephen L. Smith and Frank ImesonDepartment of Electrical and Computer Engineering |

The GLNS solver is maintained at the following Git repository

If you would like to directly download the source, you can do so from here

**[direct download of GLNS**].The solver is written in the language Julia:

**[download Julia]**

Please cite the following paper when using GLNS in your research

**[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, }

GLNS has three main 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.

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 few examples

$ ./GLNScmd.jl test/39rat195.gtsp $ ./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=30 -trials=10000

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 30 seconds, but will quit if it finds a tour of cost 13,505 or less (the optimal 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)

Instances are provided in the GTSPLIB format

GTSP-LIB is

**[available here]**LARGE-LIB, 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)

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.

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 |

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.

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