Algorithmic approaches to the multiple knapsack assignment problem |
| |
Affiliation: | DEI “Guglielmo Marconi”, Università di Bologna, Viale Risorgimento 2, Bologna I-40136, Italy |
| |
Abstract: | We consider a variant of the multiple knapsack problem in which some assignment-type side constraints have to be satisfied. The problem finds applications in logistics sectors related, e.g., to transportation and maritime shipping. We derive upper bounds from Lagrangian and surrogate relaxations of a mathematical model of the problem. We introduce a constructive heuristic and a metaheuristic refinement. We study the computational complexity of the proposed methods and evaluate their practical performance through extensive computational experiments on benchmarks from the literature and on new sets of randomly generated instances. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|