Skip to content

a set of implementations of TSP heuristics with a focus on readability

License

Notifications You must be signed in to change notification settings

panfeng5/tsphurt

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

28 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

================================================================================
tsphurt focuses on robust and readable implementations of TSP heuristics:
  1. 2-Opt (2-exchange local search)
  2. GA-EAX (GA with Edge Assembly Crossover)
  3. CLK (Chained Lin-Kernighan)
================================================================================

Contents of the directory tree are below.

src/ is source codes. Some codes are adapted from:
    GA-EAX by Yuichi Nagata (https://github.com/nagata-yuichi/GA-EAX),
    Concorde by Applegate, Bixby, Chvatal, and Cook (www.math.uwaterloo.ca/tsp/concorde/downloads).

doc/ is papers, which are referenced to implement these TSP heuristics.

instances/ is instances of TSP problems, ".tsp" files, which is a widespread format.

tsphurt is available on Linux and Windows.

On Linux, GCC 10.2 and CMake 3.15, or later version are required.
Open the shell and then run the following commands:
    git clone https://github.com/panfeng5/tsphurt.git
    cd tsphurt && mkdir build && cd build
    cmake ..
    make

On Windows, Visual Studio 2019 or later version and its C++ components
are required. Open the "x64 Native Tools Command Prompt" and
then run the following commands:
    git clone https://github.com/panfeng5/tsphurt.git
    cd tsphurt && md build && cd build
    cmake .. -G"Ninja"
    ninja

After compiling, a binary named tsp or tsp.exe will be in build/.
Run it directly to known usage of this command line utility.

On Linux, run any of the following commands:
    make test-2opt
    make test-eax
    make test-clk

On Windows, run any of the following commands:
    ninja test-2opt
    ninja test-eax
    ninja test-clk

After running, statistics will be printed in terminal.

Thanks.

== END OF FILE ==

Releases

No releases published

Packages

No packages published