Variable neighborhood search for quadratic multiple constraint variable sized bin-packing problem

doi:10.1016/j.cor.2022.105803

Variable neighborhood search for quadratic multiple constraint variable sized bin-packing problem

2022-07-01

3

PRE

AI

DOI：10.1016/j.cor.2022.105803

Original

Original request for help

Save

Abstract

En 中文

The bin-packing problem is well known in the field of combinatorial optimization. In this paper, we propose a quadratic multiple constraint variable sized bin-packing problem (QMC-VSBPP), which is a generalization of the variable sized bin-packing problem (VSBPP). In QMC-VSBPP, each bin type has multiple capacities, each item has multiple weights, and the items in different bins have joint costs. The objective of QMC-VSBPP is to minimize the sum of costs of used bins and the joint costs of items in different bins. QMC-VSBPP is a new combinatorial optimization problem. Herein, a variable neighborhood search (VNS) heuristic is proposed to solve QMC-VSBPP. The proposed VNS uses a special hierarchical clustering algorithm to generate the initial solution, in which three neighborhood operators are presented to expand solution space, and a local search algorithm based on a combination of two local operators is presented to find a local optimal solution. To evaluate the performance of the proposed VNS for QMC-VSBPP, a genetic algorithm and a variable neighborhood search for VSBPP were adapted for the state-of-the-art QMC-VSBPP, and the commercial solver CPLEX was also applied to QMC-VSBPP. Results of computational experiments on 96 test instances show that the proposed VNS could yield better solutions than those of the adapted genetic algorithm (GA), the adapted VNS, and CPLEX.

Keywords:

Combinatorial optimization

Quadratic multiple constraint variable sized bin-packing problem

Variable neighborhood search

Hierarchical clustering

Variable neighborhood search for quadratic multiple constraint variable sized bin-packing problem

Abstract

Journal

Organization