Research Repository

Local search heuristics for the multidimensional assignment problem

Karapetyan, Daniel and Gutin, Gregory (2011) 'Local search heuristics for the multidimensional assignment problem.' Journal of Heuristics, 17 (3). pp. 201-249. ISSN 1381-1231

0806.3258v6.pdf - Accepted Version

Download (354kB) | Preview


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: Elements
Depositing User: Elements
Date Deposited: 24 May 2018 12:09
Last Modified: 18 Aug 2022 11:36

Actions (login required)

View Item View Item