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. (C) 2018 Elsevier Ltd. All rights reserved.

Algorithmic approaches to the multiple knapsack assignment problem / Martello S.; Monaci M.. - In: OMEGA. - ISSN 0305-0483. - STAMPA. - 90:(2020), pp. 102004.1-102004.11. [10.1016/j.omega.2018.11.013]

Algorithmic approaches to the multiple knapsack assignment problem

Martello S.;Monaci M.
2020

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. (C) 2018 Elsevier Ltd. All rights reserved.
2020
Algorithmic approaches to the multiple knapsack assignment problem / Martello S.; Monaci M.. - In: OMEGA. - ISSN 0305-0483. - STAMPA. - 90:(2020), pp. 102004.1-102004.11. [10.1016/j.omega.2018.11.013]
Martello S.; Monaci M.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/899477
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 18
social impact