A population-based algorithm for solving linear assignment problems with two objectives. (March 2017)

• Record Type: Journal Article
• Authors: Gandibleux, Xavier; Morita, Hiroyuki; Katoh, Naoki
• Is Part Of: Computers & operations research. Volume 79(2017)
• Page Start: 291
• Page End: 303
• Publication Date: 2017-03
• Subjects: Multiobjective optimization -- Linear assignment problem -- Metaheuristic -- Heterogeneous functions; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.07.006
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: The paper presents a population-based algorithm for computing approximations of the efficient solution set for the linear assignment problem with two objectives. This is a multiobjective metaheuristic based on the intensive use of three operators – a local search, a crossover and a path-relinking – performed on a population composed only of elite solutions. The initial population is a set of feasible solutions, where each solution is one optimal assignment for an appropriate weighted sum of two objectives. Genetic information is derived from the elite solutions, providing a useful genetic heritage to be exploited by crossover operators. An upper bound set, defined in the objective space, provides one acceptable limit for performing a local search. Results reported using referenced data sets have shown that the heuristic is able to quickly find a very good approximation of the efficient frontier, even in situation of heterogeneity of objective functions. In addition, this heuristic has two main advantages. It is based on simple easy-to-implement principles, and it does not need a parameter tuning phase. Abstract : Highlights: A population-based algorithm for bi-objective linear assignment problems is proposed. It is based on the intensive use of a local search, a crossover and a path-relinking. The population is composed only of elite solutions. The situation of heterogeneity of objective functions is discussed.