New metaheuristics for solving MOCO problems: application to the knapsack
problem, the traveling salesman problem and IMRT optimization

The motivation of this thesis is to develop new heuristic methods, based on metaheuristics, to solve multiobjective combinatorial optimization problems (MOCO problems). In MOCO problems, an optimal solution does not exist since conflicting ob jectives are considered to evaluate the solutions. On the other hand, a set of good compromise solutions (called efficient solutions) can be determined. An efficient solution is such that it is impossible to find another solution better on all objectives. The goal of multiobjective optimization is to provide to the decision maker the set of efficient solutions. However, difficulties related to MOCO problems have been identified: NP -Hardness even when the single-objective counterpart is in P, an exponential number of efficient solutions, and the presence of non-supported efficient solutions, harder  to compute than supported ones. Accordingly, only heuristics methods based on metaheuristics have been developed in this thesis. Metaheuristics are general concepts including intensification and diversification techniques to explore the search space and allowing to design a heuristic for a specific optimization problem, in order to obtain approximations of good quality in a reasonable computation time.
Three new solving methods based on metaheuristics have been developed. The first one is a simple and classic adaptation to multiobjective optimization of tabu search, called PRTS, with a selection of the neighbors based on Pareto dominance relations. The second one is a memetic algorithm, called MEMOTS, making use of PRTS. The particularity of this algorithm is the selection of the parents based on the density information given by a hypergrid built in the ob jective space. The last method, the two-phase Pareto local search (2PPLS), is an extension of the Pareto local search method, where in the place of one single initial solution, a population of solutions of good quality is used as starting point.
We have first applied the three methods to the multiobjective multidimensional knapsack problem. For this problem, we show that the hybridization between MEMOTS and 2PPLS gives better results than state-of-the-art results.
We have then considered the resolution of the biob jective traveling salesman problem. We have obtained with 2PPLS better results than state-of-the-art results for many different types of instances. Different speed-up techniques based on dominance relations performed in the data or based on the solutions previously generated have been developed. The last part of this work concerns a very specific multiob jective problem that occurs in the treatment of cancer with intensity-modulated radiation therapy.