Variable Neighborhood Search for the Bin Packing Problem with Compatible Categories
Bin Packing with Conflicts (BPC) are problems in which items with compatibility constraints must be packed in the least number of bins, not exceeding the capacity of the bins and ensuring that non-conflicting items are packed in each bin. In this work, we introduce the Bin Packing Problem with Compatible Categories (BPCC), a variant of the BPC in which items belong to conflicting or compatible categories, in opposition to the item-by-item incompatibility found in previous literature. It is a common problem in the context of last mile distribution to nanostores located in densely populated areas. To efficiently solve real-life sized instances of the problem, we propose a Variable Neighborhood Search (VNS) metaheuristic algorithm. Computational experiments suggest that the algorithm yields good solutions in very short times while compared to linear integer programming running on a high-performance computing environment.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fast Neighborhood Search Heuristics for the Colored Bin Packing Problem
The Colored Bin Packing Problem (CBPP) is a generalization of the Bin Packing Problem (BPP). The CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity, minimizing the number…
Adaptive Large Neighborhood Search for Circle Bin Packing Problem
We address a new variant of packing problem called the circle bin packing problem (CBPP), which is to find a dense packing of circle items to multiple square bins so as to minimize the number of used bins. To this end, w…
Iterated Tabu Search Algorithm for Packing Unequal Circles in a Circle
This paper presents an Iterated Tabu Search algorithm (denoted by ITS-PUCC) for solving the problem of Packing Unequal Circles in a Circle. The algorithm exploits the continuous and combinatorial nature of the unequal ci…
Combinatorial OptimizationFormulating and solving integrated order batching and routing in multi-depot AGV-assisted mixed-shelves warehouses
Different retail and e-commerce companies are facing the challenge of assembling large numbers of time-critical picking orders that include both small-line and multi-line orders. To reduce unproductive picker working tim…
Iterated two-phase local search for the Set-Union Knapsack Problem
The Set-union Knapsack Problem (SUKP) is a generalization of the popular 0-1 knapsack problem. Given a set of weighted elements and a set of items with profits where each item is composed of a subset of elements, the SUK…
Combinatorial OptimizationVocal Bursts Valence Prediction