# afourmy/pyTSP

A 2D/3D visualization of the Traveling Salesman Problem main heuristics
Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
 Failed to load latest commit information. data Feb 24, 2018 readme Feb 23, 2018 source Sep 3, 2018 tests Mar 24, 2018 .dockerignore Mar 24, 2018 .gitignore Feb 12, 2018 .travis.yml Oct 10, 2018 Dockerfile Sep 3, 2018 README.md gunicorn.py Sep 3, 2018 requirements.txt Feb 24, 2018 requirements_dev.txt Mar 24, 2018 setup.cfg Mar 24, 2018

# Introduction

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city ?

pyTSP uses various approaches to solve the TSP (linear programming, construction heuristics, optimization heuristics, genetic algorithm). It provides a geographical step-by-step visualization of each of these algorithms.

You can find a demo of pyTSP here ! (U.S cities with a population larger than 900 000 inhabitants)

# Algorithms

The following algorithms are implemented in pyTSP:

• Construction heuristics
• Nearest neighbor
• Nearest insertion
• Farthest insertion
• Cheapest insertion
• Linear programming
• Optimization heuristics
• Pairwise exchange (2-opt)
• Node insertion
• Edge insertion
• Genetic algorithm

# Construction heuristics

## Nearest neighbor

``````- Start from a random city.
- Travel to the nearest unvisited city.
- Repeat until every city has been visited.
``````

## Nearest insertion

```- Start from a random city.
- Find the city closest to the partial tour, i.e the city i which minimizes d(i, j)
with j a city already in the tour.
- Insert i before or after j, depending on which option is shorter.
- Repeat until every city has been visited.
```

## Cheapest insertion

```- Start from a random city.
- Find the city which insertion in the tour causes the smallest increase in length,
i.e the city k which minimizes d(i, k)  + d(k, j) - d(i, j) with (i, j) an edge in the partial tour.
- Insert k between i and j.
- Repeat until every city has been visited.
```

## Farthest insertion

```- Start from a random city.
- Find the city k farthest from any node in the tour (i.e the city k which maximizes d(c, k) with c
a city in the partial tour), and insert k where it causes the smallest increase in length
(by minimizing d(i, k)  + d(k, j) - d(i, j), with (i, j) an edge in the partial tour).
- Repeat until every city has been visited.
```

# Linear programming

Note: there is an exponentially growing number of subtour constraints, which makes this algorithm inefficient for larger instances of the TSP. One way to improve it is to use lazy constraints, i.e ignore the subtour constraints and eliminate them one by one when looking for a feasible solution.

# Optimization heuristics

## Pairwise exchange (2-opt)

``````- Given a pair of edges, there is only one way of deleting and reconnecting the edges to obtain
a valid tour. If this new tour is shorter, make the change.
- Repeat for any pair of edges until no further improvement can be made.
``````

## Node insertion

``````- Given a node, remove it from the tour and insert it at the best possible position.
- Repeat for any node until no further improvement can be made.
``````

## Edge insertion

``````- Given an edge, remove it from the tour and insert it at the best possible position.
- Repeat for any edge until no further improvement can be made.
``````

# Genetic algorithm

pyTSP implements a genetic algorithm with the following properties:

• 3 mutation methods: random swap, insertion or displacement.
• 3 crossover methods: order, maximally preservative, or partially mapped.
• Selection: at each generation, 30 individuals are chosen randomly, and the 10 best are kept for the next generation.
• Mutation and crossover rates default to 50%. They can be modified with sliders.

Note: the genetic algorithm is processed by the server, and websockets (or long-polling if the server does not support websockets) are used to update the display client-side every new generation.

# Getting started

The following modules are used in pyTSP:

``````flask
numpy (linear programming)
cvxopt (linear programming)
xlrd (graph import)
``````

In order to use pyTSP, you need to:

• (optional) set up a virtual environment .

``````git clone https://github.com/afourmy/pyTSP.git
``````
• install the requirements
``````cd pyTSP
pip install -r requirements.txt
``````
``````python flask_app.py
``````

# Credits

Bootstrap: Front-end HTML/CSS framework.

Bootstrap slider: A slider component for Bootstrap.

CVXOPT: A library for convex optimization.

Flask: A microframework based on the Werkzeug toolkit and Jinja2 template engine.