yet another source of inspiration…
In this post we will learn how to optimally solve the TSP problem using integer linear programming using Google OR-Tools for mathmatical modelling in Python. In previous posts I have already presented two ways of solving the TSP using heuristic approaches: Construct solutions using the Nearest Neighbor construction heuristic and improve solutions using the 2-opt… Read more Solving TSPs to Optimality with Integer Linear Programming in Python
In this post, we’ll learn how to improve TSP tours using a well known and approved local search improvement heuristic approach. These improvement heuristics start with an initial solution and iteratively improve it until no further improvement is possible, then return the best solution found. Previously, we discussed how to generate initial solutions for TSP… Read more How to Improve TSP-Tours Applying the 2-opt Neighborhood
In this post, we develop a construction heuristic to generate a first solution to the Traveling Salesman Problem (TSP). This is a simple heuristic which starts from an arbitrarily chosen location and then visits the nearest neighbor until all nodes have been visited. Finally, the tour is completed by returning to the starting node. Problem… Read more Construct TSP Solutions with the Nearest Neighbor Heuristic
In this post we want to try to provide a solution to solve the Traveling Salesman Problem (TSP) using linear programming. The post is based on this excellent video from Mr. Michel Bierlaire at the EPFL. A good written documentation of the Miller Tucker Zemlin Constraint can be found here. What is a TSP? The… Read more TSP Miller-Tucker-Zemlin Subtour Elimination Constraint
Ant Colony Optimization is an old but still often applied construction heuristic to develop solutions using nature inspired behavior. The heuristic mimics the behavior of ants when finding shortest paths to between their nests and some kind of attraction, i.e. a food-source. The main idea are the pheromone trails, which ants leave behind, when travelling… Read more Calculate an MST with Ant Colony Optimization in Python
This post shows a simple implementation using R to solve a given TSP (Traveling Salesperson Problem) instance using the Pilot Method. The whole R script can be accessed here on my gist. How does the Pilot Method work? The Pilot Method is a construction heuristic to build (i.e. initial) solutions. The method tries to avoid… Read more Solve TSP using Pilot Method