Solution of the Cumulative Assignment Problem With a Well-Structured Tabu Search Method |
| |
Authors: | Mauro Dell'amico Andrea Lodi Francesco Maffioli |
| |
Affiliation: | (1) Dipartimento di Scienze e Metodi dell'Ingegneria, Università di Modena e Reggio Emilia, Viale Allegri 15, 42100 Reggio Emilia;(2) Dipartimento di Elettronica, Informatica e Sistemistica, Università di Bologna, viale Risorgimento 2, 40136 Bologna, Italy;(3) Dipartimento di Elettronica e Informazione, Politecnico di Milano, P.zza L. da Vinci 32, 20133 Milano, Italy |
| |
Abstract: | 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. |
| |
Keywords: | metaheuristics linear assignment cumulative functions tabu search |
本文献已被 SpringerLink 等数据库收录! |
|