The Biobjective Assignment Problem

In this paper we present a synthesis of the two phase method for the biobjective assignment problem. The method, which is a general technique to solve multiobjective combinatorial optimization (MOCO) problems, has been introduced by Ulungu in 1993. However, no complete description of the method to find all efficient solutions of the biobjective assignment problem (that allows an independent implementation) has been published. First, we present a complete description of a two phase method for the biobjective assignment problem, with an improved upper bound. Second, a combination of this method with a population based heuristic using path relinking is proposed to improve computational performance. Third, we propose a new technique for the second phase with a ranking approach. All of the methods have been tested on instances of varying size and range of objective function coefficients. We discuss the obtained results and explain our observations based on the distribution of objective function values