Article ID: | iaor20002379 |
Country: | Netherlands |
Volume: | 5 |
Issue: | 2 |
Start Page Number: | 123 |
End Page Number: | 143 |
Publication Date: | Jun 1999 |
Journal: | Journal of Heuristics |
Authors: | Maffioli F., DellAmico M., Lodi A. |
Keywords: | heuristics |
The Cumulative Assignment Problem is an NP-complete problem obtained by substituting the linear objective function of the classic Linear Assignment Problem, with a non-linear cumulative function. In this paper we present a first attempt to solve the Cumulative Assignment Problem with metaheuristic techniques. In particular we consider two standard techniques, namely the Simulated Annealing and the Multi-Start methods, and we describe the eXploring Tabu Search: a new structured Tabu Search algorithm which uses an iterative multi-level approach to improve the search. The new method is analyzed through extensive computational experiments and proves to be more effective than the standard methods.