  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 a combination of two neighborhoods may yield a heuristics
which is superior to both of its components.
