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
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
EOReader is a multi-satellite reader allowing you to open optical and SAR data.

Remote-sensing opensource python library reading optical and SAR sensors, loading and stacking bands, clouds, DEM and index.

ICube-SERTIT 152 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
Specification for storing geospatial vector data (point, line, polygon) in Parquet

GeoParquet About This repository defines how to store geospatial vector data (point, lines, polygons) in Apache Parquet, a popular columnar storage fo

Open Geospatial Consortium 449 Dec 27, 2022
This app displays interesting statistical weather records and trends which can be used in climate related research including study of global warming.

This app displays interesting statistical weather records and trends which can be used in climate related research including study of global warming.

0 Dec 27, 2021
A library to access OpenStreetMap related services

OSMPythonTools The python package OSMPythonTools provides easy access to OpenStreetMap (OSM) related services, among them an Overpass endpoint, Nomina

Franz-Benjamin Mocnik 342 Dec 31, 2022
Pure python WMS

Ogcserver Python WMS implementation using Mapnik. Depends Mapnik = 0.7.0 (and python bindings) Pillow PasteScript WebOb You will need to install Map

Mapnik 130 Dec 28, 2022
Wraps GEOS geometry functions in numpy ufuncs.

PyGEOS PyGEOS is a C/Python library with vectorized geometry functions. The geometry operations are done in the open-source geometry library GEOS. PyG

362 Dec 23, 2022
Geospatial web application developed uisng earthengine, geemap, and streamlit.

geospatial-streamlit Geospatial web applications developed uisng earthengine, geemap, and streamlit. App 1 - Land Surface Temperature A simple, code-f

13 Nov 27, 2022
Fiona reads and writes geographic data files

Fiona Fiona reads and writes geographic data files and thereby helps Python programmers integrate geographic information systems with other computer s

987 Jan 04, 2023
Summary statistics of geospatial raster datasets based on vector geometries.

rasterstats rasterstats is a Python module for summarizing geospatial raster datasets based on vector geometries. It includes functions for zonal stat

Matthew Perry 437 Dec 23, 2022
Python interface to PROJ (cartographic projections and coordinate transformations library)

pyproj Python interface to PROJ (cartographic projections and coordinate transformations library). Documentation Stable: http://pyproj4.github.io/pypr

832 Dec 31, 2022
A Python framework for building geospatial web-applications

Hey there, this is Greppo... A Python framework for building geospatial web-applications. Greppo is an open-source Python framework that makes it easy

Greppo 304 Dec 27, 2022
Digital Earth Australia notebooks and tools repository

Repository for Digital Earth Australia Jupyter Notebooks: tools and workflows for geospatial analysis with Open Data Cube and xarray

Geoscience Australia 335 Dec 24, 2022
🌐 Local tile server for viewing geospatial raster files with ipyleaflet or folium

🌐 Local Tile Server for Geospatial Rasters Need to visualize a rather large (gigabytes) raster you have locally? This is for you. A Flask application

Bane Sullivan 192 Jan 04, 2023
Open GeoJSON data on geojson.io

geojsonio.py Open GeoJSON data on geojson.io from Python. geojsonio.py also contains a command line utility that is a Python port of geojsonio-cli. Us

Jacob Wasserman 114 Dec 21, 2022
iNaturalist observations along hiking trails

This tool reads the route of a hike and generates a table of iNaturalist observations along the trails. It also shows the observations and the route of the hike on a map. Moreover, it saves waypoints

7 Nov 11, 2022
Advanced raster and geometry manipulations

buzzard In a nutshell, the buzzard library provides powerful abstractions to manipulate together images and geometries that come from different kind o

Earthcube Lab 30 Jun 20, 2022
WIP: extracting Geometry utilities from datacube-core

odc.geo This is still work in progress. This repository contains geometry related code extracted from Open Datacube. For details and motivation see OD

Open Data Cube 34 Jan 09, 2023
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