{"repo":"afourmy/pyTSP","free":true,"listed":false,"github":"https://github.com/afourmy/pyTSP","clone":"git clone https://github.com/afourmy/pyTSP.git","description":"A 2D/3D visualization of the Traveling Salesman Problem main heuristics","language":"Python","stars":170,"topics":["travelling-salesman-problem","genetic-algorithm","heuristics","flask","flask-socketio","linear-programming","genetic-algorithms","gis","webgl","algorithm-visualisation"],"license":null,"category":"api-integrations-sdks","readme_excerpt":"Introduction The 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 ? pyTSP uses various approaches to solve the TSP (linear programming, construction heuristics, optimization heuristics, genetic algorithm). It provides a geographical step-by-step visualization of each of these algorithms. You can find a demo of pyTSP here ! Algorithms The following algorithms are implemented in pyTSP: - Construction heuristics - Nearest neighbor - Nearest insertion - Farthest insertion - Cheapest insertion - Linear programming - Optimization heuristics - Pairwise exchange (2-opt) - Node insertion - Edge insertion - Genetic algorithm Construction heuristics Nearest neighbor Nearest insertion - Start from a random city. - Find the city closest to the partial tour, i.e the city i which minimizes d(i, j) with j a city already in the tour. - Insert i before or after j , depending on which option is shorter. - Repeat until every city has been visited. Cheapest insertion - Start from a random city. - Find the city which insertion in the tour causes the smallest increase in length, i.e the city k which minimizes d(i, k) + d(k, j) - d(i, j) with (i, j) an edge in the partial tour. - Insert k between i and j . - Repeat until every city has been visited. Farthest insertion - Start from a random city. - Find the city k farthest from a","default_branch":null,"files":null,"tree":[],"storefront":"/r/afourmy","claimed":false,"request_supported":{"post":"https://gitbuyer.com/r/afourmy/pyTSP/request-supported","requests":0},"note":"indexed from public GitHub; nothing is for sale on this page. Clone it from GitHub. Paid listings live at /search."}