期刊
APPLIED SOFT COMPUTING
卷 131, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.asoc.2022.109821
关键词
Discounted knapsack problem; Greedy heuristic; Metaheuristic; Variable neighborhood search
The discounted {0,1} knapsack problem (D{0-1}KP) is a variant of the well-known knapsack problem where items are partitioned into groups and a discount relationship is introduced among items in each group. In this work, a new variable neighborhood search (VNS) algorithm is proposed to solve the D{0-1}KP, and several greedy heuristics are used to build initial feasible solutions. The performance of VNS is evaluated and compared with state-of-the-art metaheuristics, demonstrating its robustness and competitiveness.
The discounted {0,1} knapsack problem (D{0-1}KP) is a relatively recent variant of the well-known knapsack problem. In the D{0-1}KP a set of items is partitioned into groups of three items and at most one item can be chosen from each group. In addition, a discount relationship is introduced among items in each group. As for the knapsack problem the aim is to maximize the total profit of the selected items while respecting the knapsack capacity constraint. The D{0-1}KP has been considered in recent years by various authors who proposed different (meta-)heuristics to solve it. In this work we propose a new variable neighborhood search (VNS) to solve the D{0-1}KP. We also consider several greedy heuristics to build an initial feasible solution that can be used by VNS as a starting solution. To evaluate proposed approaches the benchmark instances from the literature are considered. We first assess the quality of initial solutions returned by the greedy algorithms. Then, we analyze the capability of VNS to improve these initial solutions. Finally, we evaluate the performance of VNS compared to the state-of-the-art metaheuristics for solving the D{0-1}KP. The results demonstrate the robustness of VNS which converges to near optimal solutions in a reasonable time. This is especially true when VNS is initialized by solutions returned by greedy algorithms based on linear programming. Moreover, the obtained results show that our VNS based approaches are competitive with the best metaheuristics from the literature for the D{0-1}KP.(c) 2022 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据