Solving the Traveling Salesman Problem using Self-Organizing Maps

Last update: Dec 31, 2022

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.

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

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

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

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
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

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.

opened by Rouroul 1
Changes from Y-Shy@Github
A ch34.tsp data file was added: 34 cities from china. Hong Kong, Macao, Taipei, Haikou included

Changes in ./src/main.py

Argv related lines were deleted

File pathes were modified

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."

GitHub https://diego.codes/post/som-tsp/

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

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

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

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(

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

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

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.

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

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

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

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.

1 Dec 26, 2021

Solving the Traveling Salesman Problem using Self-Organizing Maps

Related tags

Overview

Solving the Traveling Salesman Problem using Self-Organizing Maps

Comments

Pypi package

Comparing SOM with other TSP algorithms

Using SOM to find best bath in picking warehouse process

A few comments needed

Fix x/y ratio into io_helper.py:normalize

Changes from Y-Shy@Github

Owner

Diego Vicente

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

Python Data. Leaflet.js Maps.

Google maps for Jupyter notebooks

python toolbox for visualizing geographical data and making maps

Interactive Maps with Geopandas

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.

prettymaps - A minimal Python library to draw customized maps from OpenStreetMap data.

Location field and widget for Django. It supports Google Maps, OpenStreetMap and Mapbox

Deal with Bing Maps Tiles and Pixels / WGS 84 coordinates conversions, and generate grid Shapefiles

Python library to visualize circular plasmid maps

Implemented a Google Maps prototype that provides the shortest route in terms of distance

Spectral decomposition for characterizing long-range interaction profiles in Hi-C maps

Python library to decrypt Airtag reports, as well as a InfluxDB/Grafana self-hosted dashboard example

A package built to support working with spatial data using open source python

Pandas Network Analysis: fast accessibility metrics and shortest paths, using contraction hierarchies :world_map:

Using SQLAlchemy with spatial databases

Read and write rasters in parallel using Rasterio and Dask

Download and process satellite imagery in Python using Sentinel Hub services.

Hapi is a Python library for building Conceptual Distributed Model using HBV96 lumped model & Muskingum routing method