The Cumulative Assignment Problem is an NP-complete problemobtained by substituting the linear objective function of the classicLinear 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.
Solution of the cumulative assignment problem with a well-structured tabu search method / Dell'Amico, Mauro; A., Lodi; F., Maffioli. - In: JOURNAL OF HEURISTICS. - ISSN 1381-1231. - STAMPA. - 5.2:(1999), pp. 123-145.