Algorithmic approaches to the multiple knapsack assignment problem

•Multiple knapsack problems with assignment-type side constraints.•Managerial applications in transportation logistics and emergency relocations.•Mathematical model and relaxations.•Constructive and meta-heuristic algorithms.•Computational experiments on benchmarks from the literature and on new tes...

Full description

Saved in:
Bibliographic Details
Published in:Omega (Oxford) 2020-01, Vol.90, p.102004, Article 102004
Main Authors: Martello, Silvano, Monaci, Michele
Format: Article
Language:English
Subjects:
Assignment problem
Computational experiments
Heuristic algorithms
Multiple knapsack problem
Relaxations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•Multiple knapsack problems with assignment-type side constraints.•Managerial applications in transportation logistics and emergency relocations.•Mathematical model and relaxations.•Constructive and meta-heuristic algorithms.•Computational experiments on benchmarks from the literature and on new test instances. 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.
ISSN:0305-0483
1873-5274
DOI:10.1016/j.omega.2018.11.013