Solving the Traveling Salesman Problem using Self-Organizing Maps

Related tags

Geolocation som traveling-salesman tsp self-organizing-map tsp-problem tsp-approximation
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.

Comments
  • Pypi package

    Pypi package

    Hey @diego-vicente, It would be nice to have a Pypi package for your algorithm.

    We could be able to solve a TSP problem with the following command som-tsp myfile.tsp.

    With some options I could choose whether to output the brut path, print the logs, display the distance, plot a graph or an animation...etc

    opened by LucBerge 4
  • Comparing SOM with other TSP algorithms

    Comparing SOM with other TSP algorithms

    Hey there, thanks for the code @diego-vicente !

    The SOM algorithm looks awesome but have you ever compared it with other algorithms ? Is there a website comparing the TSP algorithms ?

    opened by LucBerge 1
  • Using SOM to find best bath in picking warehouse process

    Using SOM to find best bath in picking warehouse process

    Hi Diego, I've just seen your work regarding self-organized map in salesman problem and I thank you for share your work.. I was looking some salesman problem solution because I'd like to implement something similar applied the process of peaces picking in my firm's warehouse. Let me explain the issue: suppose there's a order of production included all peaces needed to accomplish that order.. naturally each peace is located in a different place of the warehouse... so it'll be usefull to find the best way. I just need to change distance.py class due I'm not going to use euclidean metric... Am I right?

    opened by minels 1
  • A few comments needed

    A few comments needed

    Hello Diego! Can you please add some comments on TSP files. I understand, that these are city coordinates. OK, but why they are in such strange format - 25270.8333 51505.8333 ? Why the generic format, e.g. 56.124122, 25.076389 is not used?

    And why some coordinates are duplicated? E.g. (assets/qa194.tsp file)

    39 25270.8333 51505.8333
40 25270.8333 51523.0556

    What's the point of duplicating 25270.8333 value? (and many others)

    Also I've noticed, that many values has different integer part, but fraction parts of the values are the same:

    3345 61200.0000 23466.6667 3346 61200.0000 23500.0000 3347 61200.0000 23766.6667 3348 61200.0000 24066.6667 3349 61200.0000 24100.0000

    Why so?

    opened by divlv 1
  • Fix x/y ratio into io_helper.py:normalize

    Fix x/y ratio into io_helper.py:normalize

    normalize() functions uniformly scales positions 'x' and 'y' columns to a [0,1] range, this transformation doesn't keep the initial map dx/dy ratio and has negative impact on solution.

    You can keep the ratio while bounding values to [0,1]: dx = max(x)-min(x) dy = max(y)-min(y) ratio = max(dx, dy) return (c-c.min()) / ratio

    Most of your assets are squares and returns similar results but on assets/qa194.tsp, where dx/dy=1.64, it gives a -7% bonus to total route length.

    som-tsp-perf-scalefix

    opened by Rouroul 1
  • Changes from Y-Shy@Github

    Changes from Y-Shy@Github

    1. A ch34.tsp data file was added: 34 cities from china. Hong Kong, Macao, Taipei, Haikou included
    2. Changes in ./src/main.py
      • Argv related lines were deleted
      • File pathes were modified
    3. Changes in ./src/plot.py Linewidth and marksize were enlarged so that you would get a clearer figure if you wanted to print it.
    opened by realysy 0
Owner
Diego Vicente
Computer Science @UC3M, Data Science @ Decide Soluciones -- "Some may call this junk. Me, I call them treasures."
Diego Vicente
GitHub https://diego.codes/post/som-tsp/
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
Python Data. Leaflet.js Maps.

folium Python Data, Leaflet.js Maps folium builds on the data wrangling strengths of the Python ecosystem and the mapping strengths of the Leaflet.js

null 6k Jan 2, 2023
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
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
Interactive Maps with Geopandas

Create Interactive maps ??️ with your geodataframe Geopatra extends geopandas for interactive mapping and attempts to wrap the goodness of amazing map

sangarshanan 46 Aug 16, 2022
Google Maps keeps old satellite imagery around for a while – this tool collects what's available for a user-specified region in the form of a GIF.

google-maps-at-88-mph The folks maintaining Google Maps regularly update the satellite imagery it serves its users, but outdated versions of the image

Noah Doersing 111 Sep 27, 2022
prettymaps - A minimal Python library to draw customized maps from OpenStreetMap data.

A small set of Python functions to draw pretty maps from OpenStreetMap data. Based on osmnx, matplotlib and shapely libraries.

Marcelo de Oliveira Rosa Prates 9k Jan 8, 2023
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
Deal with Bing Maps Tiles and Pixels / WGS 84 coordinates conversions, and generate grid Shapefiles

PyBingTiles This is a small toolkit in order to deal with Bing Tiles, used i.e. by Facebook for their Data for Good datasets. Install Clone this repos

Shoichi 1 Dec 8, 2021
Python library to visualize circular plasmid maps

Plasmidviewer Plasmidviewer is a Python library to visualize plasmid maps from GenBank. This library provides only the function to visualize circular

Mori Hideto 9 Dec 4, 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 source and destination. The algorithms used were DFS, BFS, A*, and Iterative Depth First Search.

null 1 Dec 26, 2021
Spectral decomposition for characterizing long-range interaction profiles in Hi-C maps

Inspectral Spectral decomposition for characterizing long-range interaction prof

Nezar Abdennur 6 Dec 13, 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 3, 2023
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
Pandas Network Analysis: fast accessibility metrics and shortest paths, using contraction hierarchies :world_map:

Pandana Pandana is a Python library for network analysis that uses contraction hierarchies to calculate super-fast travel accessibility metrics and sh

Urban Data Science Toolkit 321 Jan 5, 2023
Using SQLAlchemy with spatial databases

GeoAlchemy GIS Support for SQLAlchemy. Introduction GeoAlchemy is an extension of SQLAlchemy. It provides support for Geospatial data types at the ORM

null 109 Dec 1, 2022
Read and write rasters in parallel using Rasterio and Dask

dask-rasterio dask-rasterio provides some methods for reading and writing rasters in parallel using Rasterio and Dask arrays. Usage Read a multiband r

Dymaxion Labs 85 Aug 30, 2022
Download and process satellite imagery in Python using Sentinel Hub services.

Description The sentinelhub Python package allows users to make OGC (WMS and WCS) web requests to download and process satellite images within your Py

Sentinel Hub 659 Dec 23, 2022
Hapi is a Python library for building Conceptual Distributed Model using HBV96 lumped model & Muskingum routing method

Current build status All platforms: Current release info Name Downloads Version Platforms Hapi - Hydrological library for Python Hapi is an open-sourc

Mostafa Farrag 15 Dec 26, 2022