Solving the Traveling Salesman Problem using Self-Organizing Maps

Overview

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.

Owner
Diego Vicente
Computer Science @UC3M, Data Science @ Decide Soluciones -- "Some may call this junk. Me, I call them treasures."
Diego Vicente
A public data repository for datasets created from TransLink GTFS data.

TransLink Spatial Data What: TransLink is the statutory public transit authority for the Metro Vancouver region. This GitHub repository is a collectio

Henry Tang 3 Jan 14, 2022
Processing and interpolating spatial data with a twist of machine learning

Documentation | Documentation (dev version) | Contact | Part of the Fatiando a Terra project About Verde is a Python library for processing spatial da

Fatiando a Terra 468 Dec 20, 2022
Automated download of LANDSAT data from USGS website

LANDSAT-Download It seems USGS has changed the structure of its data, and so far, I have not been able to find the direct links to the products? Help

Olivier Hagolle 197 Dec 30, 2022
Open Data Cube analyses continental scale Earth Observation data through time

Open Data Cube Core Overview The Open Data Cube Core provides an integrated gridded data analysis environment for decades of analysis ready earth obse

Open Data Cube 410 Dec 13, 2022
A compilation of several single-beam bathymetry surveys of the Caribbean

Caribbean - Single-beam bathymetry This dataset is a compilation of several single-beam bathymetry surveys of the Caribbean ocean displaying a wide ra

Fatiando a Terra Datasets 0 Jan 20, 2022
This GUI app was created to show the detailed information about the weather in any city selected by user

WeatherApp Content Brief description Tools Features Hotkeys How it works Screenshots Ways to improve the project Installation Brief description This G

TheBugYouCantFix 5 Dec 30, 2022
A toolbox for processing earth observation data with Python.

eo-box eobox is a Python package with a small collection of tools for working with Remote Sensing / Earth Observation data. Package Overview So far, t

13 Jan 06, 2022
Track International space station with python

NASA-ISS-tracker Track International space station with python Modules import json import turtle import urllib.request import time import webbrowser i

Nikhil Yadav 8 Aug 12, 2021
Mmdb-server - An open source fast API server to lookup IP addresses for their geographic location

mmdb-server mmdb-server is an open source fast API server to lookup IP addresses

Alexandre Dulaunoy 67 Nov 25, 2022
Centroids as a Service

Centroids! This application reads a valid geojson FeatureCollection and returns a valid geojson FeatureColleciton of centroids. In the output: All pro

Lyzi Diamond 20 Aug 29, 2021
Obtain a GNSS position fix from an 11-millisecond raw GNSS signal snapshot

Obtain a GNSS position fix from an 11-millisecond raw GNSS signal snapshot without any prior knowledge about the position of the receiver and only coarse knowledge about the time.

Jonas Beuchert 2 Nov 17, 2022
Geocoding library for Python.

geopy geopy is a Python client for several popular geocoding web services. geopy makes it easy for Python developers to locate the coordinates of addr

geopy 3.8k Dec 30, 2022
Python library to decrypt Airtag reports, as well as a InfluxDB/Grafana self-hosted dashboard example

Openhaystack-python This python daemon will allow you to gather your Openhaystack-based airtag reports and display them on a Grafana dashboard. You ca

Bezmenov Denys 19 Jan 03, 2023
Satellite imagery for dummies.

felicette Satellite imagery for dummies. What can you do with this tool? TL;DR: Generate JPEG earth imagery from coordinates/location name with public

Shivashis Padhi 1.8k Jan 03, 2023
Tools for the extraction of OpenStreetMap street network data

OSMnet Tools for the extraction of OpenStreetMap (OSM) street network data. Intended to be used in tandem with Pandana and UrbanAccess libraries to ex

Urban Data Science Toolkit 47 Sep 21, 2022
Focal Statistics

Focal-Statistics The Focal statistics tool in many GIS applications like ArcGIS, QGIS and GRASS GIS is a standard method to gain a local overview of r

Ifeanyi Nwasolu 1 Oct 21, 2021
A trivia questions about Europe

EUROPE TRIVIA QUIZ IN PYTHON Project Outline Ask user if he / she knows more about Europe. If yes show the Trivia main screen, else show the end Trivi

David Danso 1 Nov 17, 2021
GebPy is a Python-based, open source tool for the generation of geological data of minerals, rocks and complete lithological sequences.

GebPy is a Python-based, open source tool for the generation of geological data of minerals, rocks and complete lithological sequences. The data can be generated randomly or with respect to user-defi

Maximilian Beeskow 16 Nov 29, 2022
Creates 3D geometries from 2D vector graphics, for use in geodynamic models

geomIO - creating 3D geometries from 2D input This is the Julia and Python version of geomIO, a free open source software to generate 3D volumes and s

3 Feb 01, 2022
ESMAC diags - Earth System Model Aerosol-Cloud Diagnostics Package

Earth System Model Aerosol-Cloud Diagnostics Package This Earth System Model (ES

Pacific Northwest National Laboratory 1 Jan 04, 2022