Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
This is the question that asks the Travelling Salesman Problem. In this repository you can find some exact methods and heuristics to solve it.
| Name | Type | Solution | Resources |
|---|---|---|---|
| Gavish-Graves | Mixed Integer Linear Programming | Exact | [1] |
| Ant System | Metaheuristic | Approximation | [2] |
| Ant Colony System | Metaheuristic | Approximation | [3] |
| [1] | Gavish, Bezalel & Graves, Stephen. (2004). The Traveling Salesman Problem and Related Problems. |
| [2] | M. Dorigo, M. Birattari and T. Stutzle, "Ant colony optimization". |
| [3] | M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative learning approach to the traveling salesman problem" |