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
Google maps for Jupyter notebooks

gmaps gmaps is a plugin for including interactive Google maps in the IPython Notebook. Let's plot a heatmap of taxi pickups in San Francisco: import g

Pascal Bugnion 747 Dec 19, 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
Daily social mapping project in November 2021. Maps made using PyGMT whenever possible.

Daily social mapping project in November 2021. Maps made using PyGMT whenever possible.

Wei Ji 20 Nov 24, 2022
Code and coordinates for Matt's 2021 xmas tree

xmastree2021 Code and coordinates for Matt's 2021 xmas tree This repository contains the code and coordinates used for Matt's 2021 Christmas tree, as

Stand-up Maths 117 Jan 01, 2023
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
Enable geospatial data mining through Google Earth Engine in Grasshopper 3D, via its most recent Hops component.

AALU_Geo Mining This repository is produced for a masterclass at the Architectural Association Landscape Urbanism programme. Requirements Rhinoceros (

4 Nov 16, 2022
:earth_asia: Python Geocoder

Python Geocoder Simple and consistent geocoding library written in Python. Table of content Overview A glimpse at the API Forward Multiple results Rev

Denis 1.5k Jan 02, 2023
Rasterio reads and writes geospatial raster datasets

Rasterio Rasterio reads and writes geospatial raster data. Geographic information systems use GeoTIFF and other formats to organize and store gridded,

Mapbox 1.9k Jan 07, 2023
3D extension built off of shapely to make working with geospatial/trajectory data easier in python.

PyGeoShape 3D extension to shapely and pyproj to make working with geospatial/trajectory data easier in python. Getting Started Installation pip The e

Marc Brittain 5 Dec 27, 2022
LEOGPS - Satellite Navigation with GPS on Python!

LEOGPS is an open-source Python software which performs relative satellite navigation between two formation flying satellites, with the objective of high accuracy relative positioning. Specifically,

Samuel Low 50 Dec 13, 2022
PyTorch implementation of ''Background Activation Suppression for Weakly Supervised Object Localization''.

Background Activation Suppression for Weakly Supervised Object Localization PyTorch implementation of ''Background Activation Suppression for Weakly S

34 Dec 27, 2022
A package built to support working with spatial data using open source python

EarthPy EarthPy makes it easier to plot and manipulate spatial data in Python. Why EarthPy? Python is a generic programming language designed to suppo

Earth Lab 414 Dec 23, 2022
A set of utility functions for working with GeoJSON annotations in Kaibu

kaibu-utils A set of utility functions for working with Kaibu. Create a new repository Create a new repository and select imjoy-team/imjoy-python-temp

ImJoy Team 0 Dec 12, 2021
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 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
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
Solving the Traveling Salesman Problem using Self-Organizing Maps

Solving the Traveling Salesman Problem using Self-Organizing Maps This repository contains an implementation of a Self Organizing Map that can be used

Diego Vicente 3.1k Dec 31, 2022
Implemented a Google Maps prototype that provides the shortest route in terms of distance

Implemented a Google Maps prototype that provides the shortest route in terms of distance, the fastest route, the route with the fewest turns, and a scenic route that avoids roads when provided a sou

1 Dec 26, 2021
glTF to 3d Tiles Converter. Convert glTF model to Glb, b3dm or 3d tiles format.

gltf-to-3d-tiles glTF to 3d Tiles Converter. Convert glTF model to Glb, b3dm or 3d tiles format. Usage λ python main.py --help Usage: main.py [OPTION

58 Dec 27, 2022
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