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.
Solution of the cumulative assignment problem with a well-structured tabu search method
DELL'AMICO, Mauro;
1999
Abstract
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.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
