LANDING THE 4.0 REVOLUTION… (PART IV)

METAHEURISTIC METHODS

In operations research, analytics, and computer science, it’s common to come across archetypal problems such as the knapsack problem, the traveling salesman problem, or the nearest neighbor problem, which can be confusing when first approaching the subject. What do they refer to?

Let’s imagine we have to plan a route where we need to visit 20 points and don’t want to pass through the same place twice, or we have to carry out 20 actions and don’t know in what order to perform them. Let’s also imagine we wanted to know which combination (based on the parameters we set, such as distance, time, cost, etc.) is the most efficient. We might think that now, with the technology and computing speed available in modern computers, nothing is impossible. However, if we had a computer that analyzes a million possible combinations every second, finding out which is the best one (that is, examining all the possibilities and choosing the best among them) would take… 77,000 years! (although for the Chinese supercomputer Tianhe-2, with 33.86 petaflops per second, this is not an insurmountable challenge)

This may not be a very common example, but it already gives us an idea of just how large combinatorial problems can become. That’s where the field of heuristic methods comes into play.

HEURI… WHAT?

Looking at combinatorial problems, we understand that we need a type of model that allows us to provide a satisfactory answer (even if it might not be the best one) within a reasonable amount of time for it to be useful (there’s no point in having a solution that can’t be applied). This is precisely the goal of heuristic methods. And among these algorithms, those that are procedures used in generic approaches are known as metaheuristic methods. There are numerous metaheuristic methods implemented, ranging from the most intuitive, such as greedy algorithms or nearest neighbor implementations, to more sophisticated methods that attempt to overcome the problem of getting stuck in local minima, such as simulated annealing or genetic algorithms.

HOW CAN I USE HEURISTICS IN MY COMPANY?

As we’ve mentioned throughout several posts, the goal of these entries is to give a general overview of the concepts and to point out in which areas of a business these theories can be applied. In short: landing the 4.0 Revolution. Some practical problems may include:

• Box filling: quickly finding an efficient way to fill boxes (based on price or volume, the associated cost, etc.)
• Route design: both for commercial delivery and for internal factory movements.
• Operational improvement: finding how to carry out a series of tasks quickly and efficiently (the problem could take into account tasks that must necessarily occur before others, for example, sanding before painting).

The key to understanding where to use metaheuristic algorithms is to generally have a combinatorial process (different ways of performing a series of tasks) and know the criterion (cost function) based on which we decide whether one combination is better than another (it could be cost, time, distance, etc.).

METAHEURISTIC METHODS IN DATA MANAGEMENT AND COMBINATORICS

Metaheuristic methods emerged to address the need to find a fast and effective solution to a combinatorial problem, where the options are vast and finding the needle in the haystack seems like a daunting task. Our business processes can benefit from these implementations and guide our companies’ actions based on data.