Local search heuristics for multi-index assignment problems with decomposable costs |
| |
Authors: | H-J Bandelt A Maas F C R Spieksma |
| |
Affiliation: | 1.Universit?t Hamburg,Hamburg,Germany;2.Maastricht University,The Netherlands;3.Katholieke Universiteit Leuven,Leuven,Belgium |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|