Metaheuristics for Logistics

4A First Implementation of Metaheuristics

After giving an outline of metaheuristics, we intend to show more definitively how these procedures can quite easily be set up. This first implementation allows us, with relatively little effort, to obtain results that are already comparatively satisfactory for many of the logistic problems we have introduced. The only condition that needs to be satisfied is that we should be able to represent the solution as a list of objects. This inventory of objects may characterize a solution to our problem (list of cities to be visited, list of products to be manufactured, etc.), in which case we will talk about “direct solution representation”. It may also represent an order that allows us to create a solution to our problem (the first stage of a construction heuristic, for example – we will find more of them in the following chapters). The representation of the solution will then be called indirect. After describing how a list of objects can be represented, we will define the components necessary for the conception of a first metaheuristic, namely the initialization phase (generation of one or many initial solution(s)) and the optimization phase (techniques employed to build new solutions from existing ones). Some metaheuristics will then be described in more detail.

4.1. Representing a list of objects

Let us consider an optimization problem in which a solution corresponds to the creation of a set of objects {o₁,o₂,…,o_n} in a specific order. ...