Traveling Salesman Problem

Traveling salesman problem, also known as TSP, approached with genetic algorithms and others. Based on CS454, KAIST, 2019 Fall.

About the Course and the Problem

Please refer to the course homepage. More information about traveling salesman problem can be found here.

About the Code

Classical optimization algorithms such as greedy search are not effective due to high computational cost in large problem instances of traveling salesman problem. There's currently no known single best algorithm, and instead, various stochastic optimizations are proposed. These solutions does not aim for the 'answer', but shows sufficient level of optimization with great efficiency.

The classic and meta-heuristic approaches are as follows:

Greedy Search, 2-Opt, Genetic Algorithms, Ant-Colony Optimization (ACO), Particle Swarm Optimization (PSO)
And more: Lin-Kernigan Heuristic, Concorde

Getting Started

$ python3 main.py                   # default: genetic-algorithm with rl11849
$ python3 main.py 2opt a280         # receives two positional arguments of method and data

Folder Structure

traveling-salesman-problem
├── README.md
├── .gitignore
├── data/
│   ├── a280.tsp
│   ├── rl11849.tsp
│   └── ...
├── heuristics/
│   ├── genetic_programming.py
│   ├── greedy_search.py
│   ├── two_opt.py
│   └── ...
├── tsp.py
└── main.py

Data and testings

Raw dataset

The basic dataset used for testings in this problem is MP-TESTDATA. The numbers in file name denotes the number of cities.

To add new test data, refer to test.tsp for required format.