Article ID: | iaor20051511 |
Country: | United Kingdom |
Volume: | 55 |
Issue: | 7 |
Start Page Number: | 694 |
End Page Number: | 704 |
Publication Date: | Jul 2004 |
Journal: | Journal of the Operational Research Society |
Authors: | Spieksma F.C.R., Bandelt H.-J., Maas A. |
Keywords: | search, programming: assignment |
The multi-index assignment problem (MIAP) with decomposable costs is a natural generalization of the well-known assignment problem. Applications of the MIAP arise, for instance, in the field of multi-target multi-sensor tracking. We describe an (exponentially sized) neighbourhood for a solution of the MIAP with decomposable costs, and show that one can find a best solution in this neighbourhood in polynomial time. Based on this neighbourhood, we propose a local search algorithm. We empirically test the performance of published constructive heuristics and the local search algorithm on random instances; a straightforward iterated local search algorithm is also tested. Finally, we compute lower bounds to our problem, which enable us to assess the quality of the solutions found.