Home > Research > Publications & Outputs > Two-phase algorithms for the bi-objective assig...

Research

Links

Text available via DOI:

Keywords

View graph of relations

Two-phase algorithms for the bi-objective assignment problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Two-phase algorithms for the bi-objective assignment problem. / Przybylski, Anthony; Gandibleux, Xavier; Ehrgott, Matthias.
In: European Journal of Operational Research, Vol. 185, No. 2, 2008, p. 509-533.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Przybylski, A, Gandibleux, X & Ehrgott, M 2008, 'Two-phase algorithms for the bi-objective assignment problem', European Journal of Operational Research, vol. 185, no. 2, pp. 509-533. https://doi.org/10.1016/j.ejor.2006.12.054

APA

Przybylski, A., Gandibleux, X., & Ehrgott, M. (2008). Two-phase algorithms for the bi-objective assignment problem. European Journal of Operational Research, 185(2), 509-533. https://doi.org/10.1016/j.ejor.2006.12.054

Vancouver

Przybylski A, Gandibleux X, Ehrgott M. Two-phase algorithms for the bi-objective assignment problem. European Journal of Operational Research. 2008;185(2):509-533. doi: 10.1016/j.ejor.2006.12.054

Author

Przybylski, Anthony ; Gandibleux, Xavier ; Ehrgott, Matthias. / Two-phase algorithms for the bi-objective assignment problem. In: European Journal of Operational Research. 2008 ; Vol. 185, No. 2. pp. 509-533.

Bibtex

@article{84924d0a6151474eabbc90323acdb0b1,
title = "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.",
keywords = "Multi-objective optimisation, Integer programming, Assignment problem, Two phase method, Heuristic, Path relinking, Efficient solution, Ranking algorithm, Combinatorial optimization, Metaheuristics",
author = "Anthony Przybylski and Xavier Gandibleux and Matthias Ehrgott",
year = "2008",
doi = "10.1016/j.ejor.2006.12.054",
language = "English",
volume = "185",
pages = "509--533",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier Science B.V.",
number = "2",

}

RIS

TY - JOUR

T1 - Two-phase algorithms for the bi-objective assignment problem

AU - Przybylski, Anthony

AU - Gandibleux, Xavier

AU - Ehrgott, Matthias

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Multi-objective optimisation

KW - Integer programming

KW - Assignment problem

KW - Two phase method

KW - Heuristic

KW - Path relinking

KW - Efficient solution

KW - Ranking algorithm

KW - Combinatorial optimization

KW - Metaheuristics

U2 - 10.1016/j.ejor.2006.12.054

DO - 10.1016/j.ejor.2006.12.054

M3 - Journal article

VL - 185

SP - 509

EP - 533

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -