A Biased Random-Key Genetic Algorithm for the Multiple Knapsack Assignment Problem

Eduardo Lalla-Ruiz, Stefan Voß

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

The Multiple Knapsack Assignment Problem (MKAP) is an extension of the Multiple Knapsack Problem, a well-known NP-hard combinatorial optimization problem. The MKAP is a hard problem even for small-sized instances. In this paper, we propose an approximate approach for the MKAP based on a biased random key genetic algorithm. Our solution approach exhibits competitive performance when compared to the best approximate approach reported in the literature.
Original languageEnglish
Title of host publicationLearning and Intelligent Optimization
Subtitle of host publication9th International Conference, LION 9, Lille, France, January 12-15, 2015. Revised Selected Papers
EditorsClarisse Dhaenens, Laetitia Jourdan, Marie-Eléonore Marmion
Place of PublicationCham
PublisherSpringer
Pages218-222
Number of pages5
ISBN (Electronic)978-3-319-19084-6
ISBN (Print)978-3-319-19083-9
DOIs
Publication statusPublished - 29 May 2015
Externally publishedYes
Event9th International Conference on Learning and Intelligent Optimization, LION 2015 - Lille, France
Duration: 12 Jan 201515 Jan 2015
Conference number: 9

Publication series

NameLearning and Intelligent Optimization
Volume8994
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Learning and Intelligent Optimization, LION 2015
Abbreviated titleLION
CountryFrance
CityLille
Period12/01/1515/01/15

Fingerprint

Combinatorial optimization
Genetic algorithms
Assignment problem
Genetic algorithm

Cite this

Lalla-Ruiz, E., & Voß, S. (2015). A Biased Random-Key Genetic Algorithm for the Multiple Knapsack Assignment Problem. In C. Dhaenens, L. Jourdan, & M-E. Marmion (Eds.), Learning and Intelligent Optimization : 9th International Conference, LION 9, Lille, France, January 12-15, 2015. Revised Selected Papers (pp. 218-222). (Learning and Intelligent Optimization; Vol. 8994). Cham: Springer. https://doi.org/10.1007/978-3-319-19084-6_19
Lalla-Ruiz, Eduardo ; Voß, Stefan. / A Biased Random-Key Genetic Algorithm for the Multiple Knapsack Assignment Problem. Learning and Intelligent Optimization : 9th International Conference, LION 9, Lille, France, January 12-15, 2015. Revised Selected Papers. editor / Clarisse Dhaenens ; Laetitia Jourdan ; Marie-Eléonore Marmion. Cham : Springer, 2015. pp. 218-222 (Learning and Intelligent Optimization).
@inproceedings{2228c9fd6cac4766bd0f1bdbc3a29b98,
title = "A Biased Random-Key Genetic Algorithm for the Multiple Knapsack Assignment Problem",
abstract = "The Multiple Knapsack Assignment Problem (MKAP) is an extension of the Multiple Knapsack Problem, a well-known NP-hard combinatorial optimization problem. The MKAP is a hard problem even for small-sized instances. In this paper, we propose an approximate approach for the MKAP based on a biased random key genetic algorithm. Our solution approach exhibits competitive performance when compared to the best approximate approach reported in the literature.",
author = "Eduardo Lalla-Ruiz and Stefan Vo{\ss}",
year = "2015",
month = "5",
day = "29",
doi = "10.1007/978-3-319-19084-6_19",
language = "English",
isbn = "978-3-319-19083-9",
series = "Learning and Intelligent Optimization",
publisher = "Springer",
pages = "218--222",
editor = "Clarisse Dhaenens and Laetitia Jourdan and Marie-El{\'e}onore Marmion",
booktitle = "Learning and Intelligent Optimization",

}

Lalla-Ruiz, E & Voß, S 2015, A Biased Random-Key Genetic Algorithm for the Multiple Knapsack Assignment Problem. in C Dhaenens, L Jourdan & M-E Marmion (eds), Learning and Intelligent Optimization : 9th International Conference, LION 9, Lille, France, January 12-15, 2015. Revised Selected Papers. Learning and Intelligent Optimization, vol. 8994, Springer, Cham, pp. 218-222, 9th International Conference on Learning and Intelligent Optimization, LION 2015, Lille, France, 12/01/15. https://doi.org/10.1007/978-3-319-19084-6_19

A Biased Random-Key Genetic Algorithm for the Multiple Knapsack Assignment Problem. / Lalla-Ruiz, Eduardo; Voß, Stefan.

Learning and Intelligent Optimization : 9th International Conference, LION 9, Lille, France, January 12-15, 2015. Revised Selected Papers. ed. / Clarisse Dhaenens; Laetitia Jourdan; Marie-Eléonore Marmion. Cham : Springer, 2015. p. 218-222 (Learning and Intelligent Optimization; Vol. 8994).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - A Biased Random-Key Genetic Algorithm for the Multiple Knapsack Assignment Problem

AU - Lalla-Ruiz, Eduardo

AU - Voß, Stefan

PY - 2015/5/29

Y1 - 2015/5/29

N2 - The Multiple Knapsack Assignment Problem (MKAP) is an extension of the Multiple Knapsack Problem, a well-known NP-hard combinatorial optimization problem. The MKAP is a hard problem even for small-sized instances. In this paper, we propose an approximate approach for the MKAP based on a biased random key genetic algorithm. Our solution approach exhibits competitive performance when compared to the best approximate approach reported in the literature.

AB - The Multiple Knapsack Assignment Problem (MKAP) is an extension of the Multiple Knapsack Problem, a well-known NP-hard combinatorial optimization problem. The MKAP is a hard problem even for small-sized instances. In this paper, we propose an approximate approach for the MKAP based on a biased random key genetic algorithm. Our solution approach exhibits competitive performance when compared to the best approximate approach reported in the literature.

U2 - 10.1007/978-3-319-19084-6_19

DO - 10.1007/978-3-319-19084-6_19

M3 - Conference contribution

SN - 978-3-319-19083-9

T3 - Learning and Intelligent Optimization

SP - 218

EP - 222

BT - Learning and Intelligent Optimization

A2 - Dhaenens, Clarisse

A2 - Jourdan, Laetitia

A2 - Marmion, Marie-Eléonore

PB - Springer

CY - Cham

ER -

Lalla-Ruiz E, Voß S. A Biased Random-Key Genetic Algorithm for the Multiple Knapsack Assignment Problem. In Dhaenens C, Jourdan L, Marmion M-E, editors, Learning and Intelligent Optimization : 9th International Conference, LION 9, Lille, France, January 12-15, 2015. Revised Selected Papers. Cham: Springer. 2015. p. 218-222. (Learning and Intelligent Optimization). https://doi.org/10.1007/978-3-319-19084-6_19