A hybrid evolutionary search for the generalized quadratic multiple knapsack problem

Qing Zhou, Jin-Kao Hao and Qinghua Wu

European Journal of Operational Research, 2022, vol. 296, issue 3, 788-803

Abstract: Knapsack problems are useful models that can formulate many real-life applications. The generalized quadratic multiple knapsack problem (GQMKP) extends the well-known quadratic multiple knapsack problem by taking into account setups and knapsack preference of the items. In this study, an efficient hybrid evolutionary search algorithm (HESA) is proposed to tackle GQMKP, which relies on a knapsack-based crossover operator to generate new offspring solutions, and an adaptive feasible and infeasible tabu search to improve new offspring solutions. Other new features of HESA include a dedicated strategy to ensure a diversified and high-quality initial population, and a streamlining technique to speed up the evaluations of candidate solutions. The experiments on two sets of 96 benchmark instances as well as one large-scale real-life instance show that the proposed algorithm outperforms the state-of-the-art algorithms from the literature. In particular, HESA finds 44 improved best-known solutions (new lower bounds) (for more than 45% cases). The key components of the algorithm are studied to assess their effects on the algorithm’s performance.

Keywords: Metaheuristics; Generalized knapsack problem; Evolutionary search; Feasible and infeasible search (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721003131
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:296:y:2022:i:3:p:788-803

DOI: 10.1016/j.ejor.2021.04.001

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().