[{"_1":2,"_161":-5,"_162":-5},"loaderData",{"_3":4,"_17":18,"_25":26,"_140":141},"root",{"_5":-5,"_6":-7,"_7":8,"_9":-7,"_10":11,"_12":-7,"_13":14,"_15":16},"currentUser","primaryEmail","siteVerification","6LeIxAcTAAAAAJcZVRqyHh71UMIEGNQ_MXjiZKhI","toast","enableDev",false,"incidentStatus","theme","system","contrast","normal","routes/_layout",{"_19":-5,"_20":21,"_22":21,"_23":21,"_24":21},"username","isAskGordonEnabled",true,"isUsingNewTemplate","showMinimalLanding","showHoneypotTrap","routes/_layout.r.$namespace.$reponame",{"_27":28,"_29":-5,"_30":11,"_31":11,"_32":33,"_34":35,"_36":-5,"_37":11,"_38":39,"_88":-5,"_89":90,"_129":-5,"_130":11,"_131":21,"_132":11,"_133":-5,"_134":11,"_135":-5,"_136":137,"_138":91,"_139":-7},"canonicalUrl","https://hub.docker.com/r/afourmy/pytsp/tags","mcpServer","canSeeDockerfile","canSeeAutobuilds","namespace","afourmy","reponame","pytsp","cloudBuildSource","isAutobuildsAvailable","repo",{"_40":41,"_42":43,"_45":46,"_47":48,"_49":11,"_50":51,"_52":53,"_54":55,"_57":35,"_32":33,"_58":59,"_60":44,"_61":62,"_63":64,"_65":66,"_67":-5,"_68":62,"_69":70,"_71":11,"_72":33,"_73":74,"_79":21,"_80":81,"_85":33,"_86":87},"categories",[],"content_types",[44],"image","date_registered","2018-03-24T19:23:49.229179Z","description","A 2D/3D visualization of the Traveling Salesman Problem main heuristics","is_private","last_updated","2018-10-10T19:05:12.25089Z","last_modified","2024-10-16T13:48:34.145251Z","media_types",[56],"application/vnd.docker.container.image.v1+json","name","pull_count",2509,"repository_type","star_count",0,"status",1,"status_description","active","source","collaborator_count","full_description","# Introduction\n\nThe travelling salesman problem (TSP) asks the following question: \"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city ?\n\npyTSP uses various approaches to solve the TSP (linear programming, construction heuristics, optimization heuristics, genetic algorithm).\nIt provides a geographical step-by-step visualization of each of these algorithms.\n\n![pyTSP](readme/intro.gif)\n\n**You can find a demo of pyTSP here ! (U.S cities with a population larger than 900 000 inhabitants)**\n\n# Algorithms\n\nThe following algorithms are implemented in pyTSP:\n\n- Construction heuristics\n - Nearest neighbor\n - Nearest insertion\n - Farthest insertion\n - Cheapest insertion\n- Linear programming\n- Optimization heuristics\n - Pairwise exchange (2-opt)\n - Node insertion\n - Edge insertion\n- Genetic algorithm\n\n# Construction heuristics\n\n## Nearest neighbor\n\n```\n- Start from a random city.\n- Travel to the nearest unvisited city.\n- Repeat until every city has been visited.\n```\n\n![Nearest neighbor](readme/nearest_neighbor.gif)\n\n## Nearest insertion\n\n

\n- Start from a random city.\n- Find the city closest to the partial tour, i.e the city i which minimizes d(i, j)\nwith j a city already in the tour.\n- Insert i before or after j, depending on which option is shorter.\n- Repeat until every city has been visited.\n

\n\n![Nearest insertion](readme/nearest_insertion.gif)\n\n## Cheapest insertion\n\n

\n- Start from a random city.\n- Find the city which insertion in the tour causes the smallest increase in length,  \ni.e the city k which minimizes d(i, k)  + d(k, j) - d(i, j) with (i, j) an edge in the partial tour.\n- Insert k between i and j.\n- Repeat until every city has been visited.\n

\n\n![Cheapest insertion](readme/cheapest_insertion.gif)\n\n## Farthest insertion\n\n

\n- Start from a random city.\n- Find the city k farthest from any node in the tour (i.e the city k which maximizes d(c, k) with c\na city in the partial tour), and insert k where it causes the smallest increase in length \n(by minimizing d(i, k)  + d(k, j) - d(i, j), with (i, j) an edge in the partial tour).  \n- Repeat until every city has been visited.\n

\n\n![Farthest insertion](readme/farthest_insertion.gif)\n\n# Linear programming\n\n![First constraints](readme/linear_programming.png)\n\n![Example of disjoint subtours](readme/subtours.png)\n\n![Subtour constraint](readme/linear_programming_subtour_constraint.png)\n\n![Final solution](readme/lp_solution.png)\n\n**Note**: there is an exponentially growing number of subtour constraints, which makes this algorithm inefficient for larger instances of the TSP. One way to improve it is to use lazy constraints, i.e ignore the subtour constraints and eliminate them one by one when looking for a feasible solution.\n\n# Optimization heuristics\n\n## Pairwise exchange (2-opt)\n\n![Pairwise exchange](readme/pairwise_exchange.png)\n\n```\n- Given a pair of edges, there is only one way of deleting and reconnecting the edges to obtain\na valid tour. If this new tour is shorter, make the change.\n- Repeat for any pair of edges until no further improvement can be made.\n```\n\n![Pairwise exchange](readme/pairwise_exchange.gif)\n\n## Node insertion\n\n![Node insertion](readme/node_insertion.png)\n\n```\n- Given a node, remove it from the tour and insert it at the best possible position.\n- Repeat for any node until no further improvement can be made.\n```\n\n![Node insertion](readme/node_insertion.gif)\n\n## Edge insertion\n\n![Edge insertion](readme/edge_insertion.png)\n\n```\n- Given an edge, remove it from the tour and insert it at the best possible position.\n- Repeat for any edge until no further improvement can be made.\n```\n\n![Edge insertion](readme/edge_insertion.gif)\n\n# Genetic algorithm\n\npyTSP implements a genetic algorithm with the following properties:\n- 3 mutation methods: random swap, insertion or displacement.\n- 3 crossover methods: order, maximally preservative, or partially mapped.\n- Selection: at each generation, 30 individuals are chosen randomly, and the 10 best are kept for the next generation.\n- Mutation and crossover rates default to 50%. They can be modified with sliders.\n\n![Genetic algorithm](readme/genetic_algorithm.gif)\n\n**Note**: the genetic algorithm is processed by the server, and websockets (or long-polling if the server does not support websockets) are used to update the display client-side every new generation.\n\n# Getting started\n\nThe following modules are used in pyTSP:\n```\nflask\nflask_socketio (sockets)\nflask_sqlalchemy (database)\nnumpy (linear programming)\ncvxopt (linear programming)\nxlrd (graph import)\n```\n\nIn order to use pyTSP, you need to:\n \n- (optional) set up a [virtual environment](https://docs.python.org/3/library/venv.html) .\n\n- clone pyTSP (or download as a zip archive from github)\n```\ngit clone https://github.com/afourmy/pyTSP.git\n```\n \n- install the requirements\n```\ncd pyTSP\npip install -r requirements.txt\n```\n\n- run **/flask_app.py**.\n```\npython flask_app.py\n```\n\n- go the http://127.0.0.1:5000/.\n\n# Credits \n\n[Bootstrap](https://getbootstrap.com/ \"Bootstrap\"): Front-end HTML/CSS framework.\n\n[Bootstrap slider](http://seiyria.com/bootstrap-slider/): A slider component for Bootstrap.\n\n[CVXOPT](https://github.com/cvxopt/cvxopt): A library for convex optimization.\n\n[Flask](http://flask.pocoo.org/ \"Flask\"): A microframework based on the Werkzeug toolkit and Jinja2 template engine.\n\n[Flask SQLAlchemy](http://flask-sqlalchemy.pocoo.org/ \"Flask SQLAlchemy\"): Adds support for SQLAlchemy to Flask.\n\n[Jquery](https://jquery.com/ \"Jquery\"): JavaScript library designed to simplify the client-side scripting of HTML.\n\n[Leaflet](http://leafletjs.com/ \"Leaflet\"): JavaScript library for mobile-friendly interactive maps.\n\n[OpenStreetMap](https://www.openstreetmap.org/ \"OpenStreetMap\"): Collaborative project to create a free editable map of the world.\n\n[WebGL Earth](http://www.webglearth.org \"WebGL Earth\"): 3D digital globe for web and mobile devices.\n\n[xlrd](https://github.com/python-excel/xlrd): Library to extract data from Microsoft Excel (tm) spreadsheet files.","has_starred","hub_user","immutable_tags_settings",{"_75":11,"_76":77},"enabled","rules",[78],".*","is_automated","permissions",{"_82":21,"_83":11,"_84":11},"read","write","admin","user","storage_size",1478869438,"orgData","recentTags",[91],{"_92":44,"_93":94,"_95":96,"_97":98,"_99":100,"_50":118,"_119":94,"_120":33,"_121":56,"_57":122,"_123":124,"_125":109,"_126":118,"_127":66,"_128":21},"content_type","creator",2751413,"full_size",419939224,"id",24460273,"images",[101],{"_102":103,"_104":105,"_106":107,"_108":109,"_110":111,"_112":113,"_114":107,"_115":-5,"_116":96,"_63":66,"_117":-5},"architecture","amd64","digest","sha256:2c6e57e49928658153662e8f38f61b1bc1339330393a96cb29a2f50b34e1a31b","features","","last_pulled","2026-10-04T16:48:54.6054694Z","last_pushed","2018-10-10T19:05:09Z","os","linux","os_features","os_version","size","variant","2018-10-10T19:05:08.511105Z","last_updater","last_updater_username","media_type","latest","repository",5013761,"tag_last_pulled","tag_last_pushed","tag_status","v2","sbxKitMetadata","isPotentialSpam","isHubSbxKitsEnabled","showSbxLogoOverride","sbxTrademarkText","displaySecurityMetadata","tagAttestations","tagsHaveAttestations",[],"selectedTag","attestationsUrl","routes/_layout.r.$namespace.$reponame.tags",{"_38":142,"_149":150,"_136":159,"_160":11},{"_40":143,"_42":144,"_45":46,"_47":48,"_49":11,"_50":51,"_52":53,"_54":145,"_57":35,"_32":33,"_58":59,"_60":44,"_61":62,"_63":64,"_65":66,"_67":-5,"_68":62,"_69":70,"_71":11,"_72":33,"_73":146,"_79":21,"_80":148,"_85":33,"_86":87},[],[44],[56],{"_75":11,"_76":147},[78],{"_82":21,"_83":11,"_84":11},"tags",{"_151":64,"_152":-5,"_153":-5,"_154":155},"count","next","previous","results",[156],{"_92":44,"_93":94,"_95":96,"_97":98,"_99":157,"_50":118,"_119":94,"_120":33,"_121":56,"_57":122,"_123":124,"_125":109,"_126":118,"_127":66,"_128":21},[158],{"_102":103,"_104":105,"_106":107,"_108":109,"_110":111,"_112":113,"_114":107,"_115":-5,"_116":96,"_63":66,"_117":-5},[],"canDeleteTags","actionData","errors"]

afourmy/pytsp

Tags for afourmy/pytsp