A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem

Avci M., Topaloglu Ş. A.

COMPUTERS & OPERATIONS RESEARCH, vol.83, pp.54-65, 2017 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 83
  • Publication Date: 2017
  • Doi Number: 10.1016/j.cor.2017.02.004
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.54-65
  • Keywords: Generalized quadratic multiple knapsack problem, Variable neighborhood descent, Iterated local search, Perturbation mechanism, VEHICLE-ROUTING PROBLEM, GREEDY ALGORITHM, TABU SEARCH
  • Dokuz Eylül University Affiliated: Yes


The quadratic multiple knapsack problem (QMKP) is a variant of the classical knapsack problem where multiple knapsacks are considered and the objective is to maximize a quadratic objective function subject to capacity constraints. The generalized quadratic multiple knapsack problem (G-QMKP) extends the QMKP by considering the setups, assignment conditions and the knapsack preferences of the items. In this study, a multi-start iterated local search algorithm (MS-ILS) in w the variable neighborhood descent (VND) algorithm is integrated with an adaptive perturbation mechanism is proposed to solve the G-QMKP. The multi-start implementation together with the adaptive perturbation mechanism enables the search process to explore different search regions in the search space while VND is applied to obtain high-quality solutions from the examined regions. Another remarkable feature of MS-ILS is its simplicity and adaptiveness that ease its implementation. The proposed MS-ILS is tested on G-QMKP benchmark instances derived from the literature. The results indicate that the developed MS-ILS can produce high-quality solutions for the G-QMKP. Particularly, it has been observed that the developed MS-ILS has improved the best known solutions for 35 out of 48 large-size G-QMKP instances. (C) 2017 Elsevier Ltd. All rights reserved.