So far, we have worked with so-called permutation problems; that is to say, problems that can be naturally represented in the form of a permutation σ. The two problems that we have used as case studies are the traveling salesman problem and the permutation flow-shop problem.
In Chapter 4, we learned base techniques that allow implementing metaheuristics for permutation problems in a general way. Chapters 5 and 6 helped to describe advanced techniques that improve the performance of these methods.
We are going to see now how this knowledge can be enlarged to deal with other problems: that is to say, combinatorial optimization problems that do not belong to the permutation problem class.
We shall begin with an introductory section having two approaches that will be applied in many cases. Other sections will deal with applications for particular logistic problems.
7.1. Direct representation versus indirect representation
For many combined optimization problems, permutation does not constitute a natural representation of a solution. There are then two possibilities:
- – either one works on a direct representation of the solution;
- – or, it is possible to create a complete solution of the problem thanks to the permutation. We can say then that permutation is an indirect representation of this solution.
Let us come back one instant to the direct presentation, which is probably the most classical and natural approach. Metaheuristics work directly ...