Project Summary

Nowadays metaheuristics are widely used to solve important practical combinatorial optimization problems. However, due to the variety of techniques and concepts comprised by metaheuristics, there is still no commonly agreed definition for metaheuristics. The definition used in the Metaheuristics Network is the following.

A metaheuristic is a set of concepts that can be used to define heuristic methods that can be applied to a wide set of different problems. In other words, a metaheuristic can be seen as a general algorithmic framework which can be applied to different optimization problems with relatively few modifications to make them adapted to a specific problem. Examples of metaheuristics include simulated annealing (SA), tabu search (TS), iterated local search (ILS), evolutionary algorithms (EC), and ant colony optimization (ACO).

Although metaheuristics are widely used techniques, the how and why they work effectively for specific problems and for others not, is still not well understood. The overall goal of the Metaheuristics Network is to increase our understanding of metaheuristics, to propose new ways of structuring metaheuristic components, and to evaluate their contribution to metaheuristics behavior as well as to use the extracted information for the development of new hybrid metaheuristics.

Specifically, the network has goals of scientific, engineering, and training nature. These are explained in the following.

• Scientific goals. The main scientific goal of the Metaheuristics Network is to improve the understanding of how metaheuristics work through theoretical and experimental research. Other scientific goals are the definition of new high-performing hybrid metaheuristics, that is, metaheuristics that combine components taken from existing metaheuristics, as well as the definition and use of a strictly controlled, machine independent, experimental methodology which allows a fair and meaningful comparison of experimental results.
• Engineering goals. The first engineering oriented goal consists in the definition of guidelines that can be used to help choosing which metaheuristics, or metaheuristic components, to use when a new problem is attacked. A second engineering oriented goal of the network is the testing and validation of the developed ideas on very challenging problems taken from the industrial world.
• Training goals. The main training goals of the network are: (i) to let young researchers learn about metaheuristic techniques as well as about a number of important optimization problems, (ii) to let them learn how to design experiments in a rigorous way, and (iii) to develop their project management skills by means of participation in a strictly co-ordinated international team activity.

Research Method

The research method is mostly experimental. The experimental activity is structured along two orthogonal lines, metaheuristics and problems, that is reflected in the role played by the network nodes: each node will be the ``expert'' for one metaheuristic (with the exception of EUROBIOS) as well as the co-ordinator (with exception of IRIDIA) for one of the problems. The metaheuristics chosen are among the best-known ones. The choice of the problems comprises academic ones, most of which are closely related to problems arising in practice, and challenging real-world problems from industrial applications.

The research nodes of the network were selected in such a way that (i) for each of the studied metaheuristics there is at least one node that is a recognized expert, and (ii) for each of the considered problems at least one node has extensive research experience. Table~1 shows the role of the network nodes in this respect.

The work that will be performed by the network is structured in three main phases: (1) network setup (months 1--6), (2) benchmark problem (months 7--30), and (3) final analysis, synthesis and guidelines production (months 31--36).

The goal of the first phase is to set up the network so that everything runs smoothly. During this phase two well-known academic combinatorial optimization problems will be used as test problems. At this time the focus is on research methodology and on experimental procedures as well as on learning about the techniques to be used.

The second phase concerns the study of metaheuristics applied to academic versions of real world problems as well as to problems taken directly from industrial applications. The problems studied in the second phase will be vehicle routing problems, scheduling problems, and timetabling problems. Additionally, real industrial instances for two of the studied problems, or similar, are provided by the industrial partner.

The third phase will be concerned with systematization of the acquired knowledge, and with the definition of guidelines on how to match metaheuristics components to problem characteristics.

From a methodological point of view, it is important how the experimental activity is performed. For each of the problem classes considered, the following general criteria will be followed:

• A common input-output protocol is defined during the first phase of the network so that all software produced by the different nodes can be run on the same problems producing results in a same format. To avoid a bias due to the choice of the programming language, all software will be written in a common language (most probably C or C++).
• The node that is the expert of the class of problems under consideration co-ordinates the activities connected with the identification and choice of the problem instances to be considered and helps solving issues related to the implementation of local search algorithms.
• Each network node implements the metaheuristic for which it is an expert, and a second metaheuristic chosen by the co-ordinator (the co-ordinator will choose the second metaheuristic in such a way that each node will implement each metaheuristic for at least one problem).
• Once a node has finished its own local experimentation with the implemented metaheuristics, local search and problem instance characteristics, it delivers to IRIDIA a software package composed of two working metaheuristics.
• The IRIDIA node will run unbiased comparisons on a set of problem instances unknown to the developer nodes but which present similar characteristics to those problem instances attacked in the explorative phase. These experiments will be run on a same machine using the software provided by the nodes as it is.
• The experimental results will be statistically analysed.
• Once experiments have been performed, the problem instances used will be disclosed to the network nodes, which will be allowed to fine tune their algorithms to get the best possible performance on the test set.

Finally, a recurrent algorithm competition (biannual) to be held in correspondence with a major conference in the field will be organized.