yet another source of inspiration…
A common problem in production scheduling involves distributing jobs of varying durations across multiple identical machines to minimize the time when the last job finishes. In other words, the goal is to minimize the makespan. Production Planning Problem Instances The following list presents some instances of the makespan minimization problem. It involves a set number… Read more How to Construct Solutions to the Production Planning Problem
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
The bin packing problem is a combinatorial optimization problem in which items of different sizes must be packed into a number of containers with a fixed capacity in such a way that the number of containers used is minimized. This website of the lamarr-institute provides a nice and clear explanation of the bin-packing problem and… Read more How to construct Solutions to the Bin Packing Problem
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’ll develop a construction heuristic to build reasonable (start) solutions for the knapsack problem. Why use Construction Heuristics? Construction heuristics offer the advantage of quickly leading to acceptable solutions. Unlike more complex optimization algorithms, they are easy to implement and require less computational power. These heuristics are particularly well-suited for handling large… Read more The use of Construction Heuristics
If you happen to have to solve TSPs or some special type of VRPs – i.e. capacitated or with timewindows and other constraints – you might want to have a look at Google OR-Tools. The library contains a wide variety of heuristics for different problems primarly based on google’s excellent constraint programming solver. The library… Read more Solve TSP Instance using Google OR-Tools
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