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). 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
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 > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 24 May 2018 12:09
Last Modified: 24 May 2018 13:15

Actions (login required)

View Item View Item