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


Avci M., Topaloglu Ş. A.

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

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 83
  • Basım Tarihi: 2017
  • Doi Numarası: 10.1016/j.cor.2017.02.004
  • Dergi Adı: COMPUTERS & OPERATIONS RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.54-65
  • Anahtar Kelimeler: Generalized quadratic multiple knapsack problem, Variable neighborhood descent, Iterated local search, Perturbation mechanism, VEHICLE-ROUTING PROBLEM, GREEDY ALGORITHM, TABU SEARCH
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

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.