Determine problem characteristics relevant for choosing the appropriate solution technique for a real-life problem.

[Pieter Vansteenwegen]

At this moment, almost randomly all kinds of algorithms are applied to efficiently solve a problem. No or little scientific insight is present in the strong and weak points of different algorithms. The aim of this project is to develop insight in which algorithm is the most promising when a new problem comes up. More specifically, connections should be discovered between certain problem characteristics and the (high-quality) performance of a certain algorithm.

Three types of solution strategies can be distinguished in the operations research field: exact methods, heuristics and metaheuristics. With exact methods (for instance, for vehicle routing problems: Toth & Vigo, 1998) an optimal solution is guaranteed. However, of all “difficult” (NP-Hard) problems in operations research, only the small ones can be solved with exact methods. For bigger or more complex problems not enough calculation time or memory is available to reach a solution. Heuristics are more straightforward and much faster methods capable of solving big and complex problems. However, the solution quality is significantly reduced, an optimal solution is not guaranteed and the gap with the optimal solution is regularly very large. Metaheuristics are the most recent solution strategy. Metaheuristics apply a meta-strategy to considerably improve the quality of the results of one or more simple heuristics. The most important metaheuristics are (Glover & Kochenberger, 2003) tabu search, iterated local search, guided local search, genetic and evolutionary algorithms, ant colony optimisation and variable neighbourhood search. Metaheuristics are capable of reaching a high quality solution within reasonable calculation time. Metaheuristics are generally accepted as the most appropriate methods to solve large and complex optimisation problems, for instance for the vehicle routing problem (Gendreau et al., 1998). A large number of possibly promising methods is available to skilfully solve a new kind of problem.

When a new type of problem comes up, a researcher will often try to solve this problem with the solution strategy he is familiar with. This method of trial and error, without real insight, will sometimes result in a high-quality solution (and a scientific publication), but frequently this effort is just a waist of time. At this moment, not enough scientific insight is developed about strong and weak points of algorithms to make a wellconsidered choice for a certain procedure. Sometimes the quality of (specific implementations of) algorithms is compared for a given problem, but this comparison is almost always based on the obtained results and not on the question why one method obtained better results than the other method.

The goal of this project is to determine problem characteristics relevant in the choice of a well performing solution strategy. When a new problem arises, in logistics or production, it will be possible to select the most promising technique for this new problem, based on its characteristics. More specifically, this means that when a new problem has characteristic A (or B), algorithm X (or Y) will be a proper framework to start with. It is not the idea to determine which algorithm is “somewhat better”, but to determine which algorithm is the most promising one for a class of problems with a specific characteristic.

(Copy paste from a part of my post-doc research proposal)