A variable neighborhood search algorithm for the bin packing problem with compatible categories

摘要

In this paper, we address the Bin Packing Problem with Compatible Categories (BPCC), a challenging optimization problem that arises in the context of last mile distribution to nanostores in large cities, particularly in developing countries. By introducing the concept of incompatible categories of items to be delivered (i.e., types of items that cannot be transported together, such as food and cleaning products), as opposed to the item-by-item incompatibility found in previous literature, we aim to determine the best assignment of deliveries of distinct products to a homogeneous fleet of capacitated vehicles in order to minimize the number of required vehicles (bins). To solve large instances of the BPCC that are commonly found in practice, we propose an efficient variable neighborhood search (VNS) metaheuristic that relies on a simple greedy heuristic to generate initial solutions and on simple and efficient neighborhoods as well as problem-tailored shaking procedures. We perform extensive computational experiments on a very large set of 8000 instances derived from benchmark datasets. The tested instances differ in terms of number of items (ranging from 201 to 1002), bin capacities, compatibility matrices and proportion of items that belong to the different categories. We also present two new mathematical formulations for the BPCC and compare them to the item-by-item bin packing formulation (Gendreau et al., 2004) using a high performance computer (HPC). The computational experiments indicate that our VNS algorithm can effectively solve the BPCC in very short CPU times. (C) 2019 Elsevier Ltd. All rights reserved.