tsp-solver

metaheuristics for traveling salesman problem (TSP)

• tsp_ls_naive.py Local Search (LS)
• tsp_ls_nblist.py Local Search with Neighbor-List (LS-NL)
• tsp_mls.py Random Multi-start Local Search (MLS)
• tsp_ils.py Iterated Local Search (ILS)
• tsp_ils_fls.py Iterated Local Search with Fast Local Search (ILS-FLS)
• tsp_ils_imp.py Improved ILS-FLS (ILS+)
• tsp_gls.py Guided Local Search (GLS)
• tsp_gls_fls.py Guided Local Search with FLS (GLS-FLS)
• tsp_grasp.py Greedy Randomized Adaptive Search Procedure (GRASP)
• tsp_sa.py Simulated Annealing (SA)
• tsp_tabu_rule1.py Tabu Search with Rule1 (TS1)
• tsp_tabu_rule2.py Tabu Search with Rule2 (TS2)
• tsp_ma.py Memetic Alsogithm (MA)
• tsp_ma_fls.py Memetic Alsogithm with FLS (MA-FLS)

Feature

• Simple implementation of metaheuristics in Python.
• Local search with 2-opt, Or-opt, and 3-opt neighborhood search.
• Efficient LS implementation using neighbor-list.
• For Euclidean TSP instances (EUC2D) in TSPLIB.

Usage

common usage for all codes

$ tsp_ils.py [-h] [-t TIME] [-d] filename

• filename TSP instance (mandatory)
• -d visually display obtained tour (optional)
• -t timelimit (optional, default 60 sec) except for tsp_ls_naive.py and tsp_ls_nblist.py

References

slide (Japanese)

Author

Umetani, Shunji

License

This software is released under the MIT License, see LICENSE.