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
flask_socketio (sockets)
flask_sqlalchemy (database)
numpy (linear programming)
cvxopt (linear programming)
xlrd (graph import)

In order to use pyTSP, you need to:

(optional) set up a virtual environment .
clone pyTSP (or download as a zip archive from github)

git clone https://github.com/afourmy/pyTSP.git

install the requirements

cd pyTSP
pip install -r requirements.txt

run /flask_app.py.

python flask_app.py

go the http://127.0.0.1:5000/.

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.

Flask SQLAlchemy: Adds support for SQLAlchemy to Flask.

Jquery: JavaScript library designed to simplify the client-side scripting of HTML.

Leaflet: JavaScript library for mobile-friendly interactive maps.

OpenStreetMap: Collaborative project to create a free editable map of the world.

WebGL Earth: 3D digital globe for web and mobile devices.

xlrd: Library to extract data from Microsoft Excel (tm) spreadsheet files.

afourmy/pyTSP

afourmy

Reviews

Repository Details