Local search heuristics for multi-index assignment problems with decomposable costs

Local search heuristics for multi-index assignment problems with decomposable costs

0.00 Avg rating0 Votes
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: , ,
Keywords: search, programming: assignment
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.

Reviews

Required fields are marked *. Your email address will not be published.