Karapetyan, Daniel and Gutin, Gregory (2011) Local search heuristics for the multidimensional assignment problem. Journal of Heuristics, 17 (3). pp. 201-249. DOI https://doi.org/10.1007/s10732-010-9133-3
Karapetyan, Daniel and Gutin, Gregory (2011) Local search heuristics for the multidimensional assignment problem. Journal of Heuristics, 17 (3). pp. 201-249. DOI https://doi.org/10.1007/s10732-010-9133-3
Karapetyan, Daniel and Gutin, Gregory (2011) Local search heuristics for the multidimensional assignment problem. Journal of Heuristics, 17 (3). pp. 201-249. DOI https://doi.org/10.1007/s10732-010-9133-3
Abstract
The Multidimensional Assignment Problem (MAP) (abbreviated s-AP in the case of s dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, though the problems with larger values of s also have a large number of applications. We consider several known neighborhoods, generalize them and propose some new ones. The heuristics are evaluated both theoretically and experimentally and dominating algorithms are selected. We also demonstrate that a combination of two neighborhoods may yield a heuristics which is superior to both of its components.
Item Type: | Article |
---|---|
Additional Information: | 30 pages. A preliminary version is published in volume 5420 of Lecture Notes Comp. Sci., pages 100-115, 2009 |
Uncontrolled Keywords: | Multidimensional assignment problem; Local search; Neighborhood; Metaheuristics |
Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 24 May 2018 12:09 |
Last Modified: | 07 Aug 2024 20:09 |
URI: | http://repository.essex.ac.uk/id/eprint/22073 |
Available files
Filename: 0806.3258v6.pdf