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
Python bindings to libpostal for fast international address parsing/normalization

pypostal These are the official Python bindings to https://github.com/openvenues/libpostal, a fast statistical parser/normalizer for street addresses

openvenues 651 Dec 16, 2022
Cloud Optimized GeoTIFF creation and validation plugin for rasterio

rio-cogeo Cloud Optimized GeoTIFF (COG) creation and validation plugin for Rasterio. Documentation: https://cogeotiff.github.io/rio-cogeo/ Source Code

216 Dec 31, 2022
Geospatial Image Processing for Python

GIPPY Gippy is a Python library for image processing of geospatial raster data. The core of the library is implemented as a C++ library, libgip, with

GIPIT 83 Aug 19, 2022
geemap - A Python package for interactive mapping with Google Earth Engine, ipyleaflet, and ipywidgets.

A Python package for interactive mapping with Google Earth Engine, ipyleaflet, and folium

Qiusheng Wu 2.4k Dec 30, 2022
Location field and widget for Django. It supports Google Maps, OpenStreetMap and Mapbox

django-location-field Let users pick locations using a map widget and store its latitude and longitude. Stable version: django-location-field==2.1.0 D

Caio Ariede 481 Dec 29, 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
Evaluation of file formats in the context of geo-referenced 3D geometries.

Geo-referenced Geometry File Formats Classic geometry file formats as .obj, .off, .ply, .stl or .dae do not support the utilization of coordinate syst

Advanced Information Systems and Technology 11 Mar 02, 2022
How to use COG's (Cloud optimized GeoTIFFs) with Rasterio

How to use COG's (Cloud optimized GeoTIFFs) with Rasterio According to Cogeo.org: A Cloud Opdtimized GeoTIFF (COG) is a regular GeoTIFF file, aimed at

Marvin Gabler 8 Jul 29, 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
Python package for earth-observing satellite data processing

Satpy The Satpy package is a python library for reading and manipulating meteorological remote sensing data and writing it to various image and data f

PyTroll 882 Dec 27, 2022
A Python tool to display geolocation information in the traceroute.

IP2Trace Python IP2Trace Python is a Python tool allowing user to get IP address information such as country, region, city, latitude, longitude, zip c

IP2Location 22 Jan 08, 2023
ColoringMapAlgorithm-CSP- - Graphical Coloring of Countries with Condition Satisfaction Algorithm

ColoringMapAlgorithm-CSP- Condition Satisfaction Algorithm Output Condition

Kerem TAN 2 Jan 10, 2022
A python package that extends Google Earth Engine.

A python package that extends Google Earth Engine GitHub: https://github.com/davemlz/eemont Documentation: https://eemont.readthedocs.io/ PyPI: https:

David Montero Loaiza 307 Jan 01, 2023
User friendly Rasterio plugin to read raster datasets.

rio-tiler User friendly Rasterio plugin to read raster datasets. Documentation: https://cogeotiff.github.io/rio-tiler/ Source Code: https://github.com

372 Dec 23, 2022
python toolbox for visualizing geographical data and making maps

geoplotlib is a python toolbox for visualizing geographical data and making maps data = read_csv('data/bus.csv') geoplotlib.dot(data) geoplotlib.show(

Andrea Cuttone 976 Dec 11, 2022
This program analizes films database with adresses, and creates a folium map with closest films to the coordinates

Films-map-project UCU CS lab 1.2, 1st year This program analizes films database with adresses, and creates a folium map with closest films to the coor

Artem Moskovets 1 Feb 09, 2022
A bot that tweets info and location map for new bicycle parking added to OpenStreetMap within a GeoJSON boundary.

Bike parking tweepy bot app A twitter bot app that searches for bicycle parking added to OpenStreetMap. Relies on AWS Lambda/S3, Python3, Tweepy, Flas

Angelo Trivisonno 1 Dec 19, 2021
pure-Python (Numpy optional) 3D coordinate conversions for geospace ecef enu eci

Python 3-D coordinate conversions Pure Python (no prerequistes beyond Python itself) 3-D geographic coordinate conversions and geodesy. API similar to

Geospace code 292 Dec 29, 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
LicenseLocation - License Location With Python

LicenseLocation Hi,everyone! ❀ 🧑 πŸ’› πŸ’š πŸ’™ πŸ’œ This is my first project! βœ” Actual

The Bin 1 Jan 25, 2022