Solving the Traveling Salesman Problem using Self-Organizing Maps
Switch branches/tags
Nothing to show
Clone or download
Latest commit 0d8f9c5 Jun 10, 2018
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
assets Big instances added to the repository Jan 14, 2018
diagrams Added a demo Uruguay gif Jan 21, 2018
report Report and slides pdfs added to the repository Jan 21, 2018
src Fixed #2 for normalziation, removed unused imports Feb 4, 2018
.gitignore Updated gitignore for Python Nov 16, 2017
LICENSE License added Jan 21, 2018
README.org Update README.org Jun 10, 2018
requirements.txt Add requirements.txt Feb 7, 2018

README.org

Solving the Traveling Salesman Problem using Self-Organizing Maps

This repository contains an implementation of a Self Organizing Map that can be used to find sub-optimal solutions for the Traveling Salesman Problem. The instances of the problems that the program supports are .tsp files, which is a widespread format in this problem. All the source code can be found in the src directory, while a report and brief presentation slides (in Spanish) can be found in the report folder. However, for a complete read on the topic, you can read my blog post explaining this implementation and its evaluation.

diagrams/uruguay.gif

To run the code, only Python 3 and the dependencies (matplotlib, numpy and pandas, which are included in the Anaconda distribution by default) are needed. In case you are not using Anaconda, you can install all the dependencies with:

pip install -r requirements.txt

To run the code, simply execute:

cd som-tsp
python src/main.py assets/<instance>.tsp

The images generated will be stored in the diagrams folder. Using a tool like convert, you can easily generate an animation like the one in this file by running:

convert -delay 10 -loop 0 *.png animation.gif

This code is licensed under MIT License, so feel free to modify and/or use it in your projects. If you have any doubts, feel free to contact me or contribute to this repository by creating an issue.


This code was presented for the Bio-Inspired Artificial Intelligence course in the Computer Science & Technology master’s degree @ UC3M. A previous version of this code can be found in this repository. Special thanks to Leonard Kleinans, who worked with me in that previous version.