The multiple objective simulated annealing method: A tool for solving multiobjective combinatorial optimization problems

The success of modern heuristics (Simulated Annealing (SA), Tabu Search, Genetic Algorithms, …) in solving classical combinatorial optimization problems has drawn the attention of the research community in multicriteria methods. In fact, for large-scale problems, the simultaneous difficulties of NP-hard complexity and of multiobjective framework make most Multiobjective Combinatorial Optimization (MOCO) problems intractable for exact methods. This paper develops the so-called MOSA (Multiobjective Simulated Annealing) method to approximate the set of efficient solutions of a MOCO problem. Different options for the implementation are illustrated and extensive experiments prove the efficiency of the approach. Its results are compared to exact methods on bi-objective knapsack problems.