Local search heuristics for the multidimensional assignment problem

Author： Karapetyan Daniel  

Publisher： Springer Publishing Company

ISSN： 1381-1231

Source： Journal of Heuristics, Vol.17, Iss.3, 2011-06, pp. : 201-249

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

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.

Related content

Sequential constraint augmentation with variable neighbourhood search for the multidimensional assignment problem

By Pasiliao Eduardo L.   Pardalos Panos M.  

International Journal of Computational Science and Engineering, Vol. 3, Iss. 3, 2008-04 ,pp. : 184-193 (10)

Inderscience Publishers

Access to resources Recommend Favorite

Applying an Extended Guided Local Search to the Quadratic Assignment Problem

By Mills P.  

Annals of Operations Research, Vol. 118, Iss. 1-4, 2003-02 ,pp. : 121-135 (15)

Springer Publishing Company

Access to resources Recommend Favorite

Improved convergent heuristics for the 0-1 multidimensional knapsack problem

By Hanafi Saïd  

Annals of Operations Research, Vol. 183, Iss. 1, 2011-03 ,pp. : 125-142 (18)

Springer Publishing Company

Access to resources Recommend Favorite

LP based heuristics for the multiple knapsack problem with assignment restrictions

By Dahl Geir  

Annals of Operations Research, Vol. 146, Iss. 1, 2006-09 ,pp. : 91-104 (14)

Springer Publishing Company

Access to resources Recommend Favorite

Local Optimization Method with Global Multidimensional Search

By Bagirov Adil   Rubinov Alexander   Zhang Jiapu  

Journal of Global Optimization, Vol. 32, Iss. 2, 2005-06 ,pp. : 161-179 (19)

Springer Publishing Company

Access to resources Recommend Favorite