Two phase algorithms for the bi-objective assignment problem

Abstract

In this paper, we present several algorithms for the bi-objective assignment problem. The algorithms are based on the two phase method, which is a general technique to solve multi-objective combinatorial optimisation (MOCO) problems. We give a description of the original two phase method for the bi-objective assignment problem, including an implementation of the variable fixing strategy of the original method. We propose several enhancements for the second phase, i.e., improved upper bounds and a combination of the two phase method with a population based heuristic using path relinking to improve computational performance. Finally, we describe a new technique for the second phase with a ranking approach, which outperforms all other tested algorithms. All of the algorithms have been tested on instances of varying size and range of objective function coefficients. We discuss the results obtained and explain our observations based on the distribution of objective function values.