DOI: 10.11583/dtu.28498229.v1
title: Multi-Class Constrained Variable Size Bin Packing Problem (MCCVSBPP) - Benchmark Instances

description: Full reference: Coutton, B., Pacino, D., Holst, K., Guericke, S. and Kidd, M.P. (2023). Heuristic approaches for freight containerization with business rules. Under revision.This repository hosts the files backing up the data and experimental results described in our paper Heuristic approaches for freight containerization with business rules referenced above. The paper is now under revision. A link to it will be provided as soon as possible.If you have any questions, please feel free to reach out to <b>baptiste.coutton@gmail.com</b>DataThe CSV files that describe the instances are found in the <code>instances</code> folder. There is then one folder for each of the three sets described in the paper: <code>set1</code>, <code>set2</code>, and <code>set3</code>. In <code>set2</code> and <code>set3</code>, you will find some sub-folders that further partition the instances. In <code>set2</code> there is one subfolder per number of classes, and in <code>set3</code>there is one subfolder per combination of volume distribution and correlation between the class capacities and the number of class colors. So, for example, <code>set3_t1_corr</code> contains the instances of type T1 where the class capacities are correlated to the number of class colors.The instance folder structureThen, each individual instance has its own folder. It contains three files: <code>items.csv</code>, <code>bin_types.csv</code>, and <code>classes.csv</code>. Let's describe each of them:<code>items.csv</code>: This file contains the information about all the items in the instance. One row corresponds to one item and holds its descriptive attributes. The first column (<code>volume</code>) is the item's volume. There is then one column per class (<code>class_c</code>, with <i>c</i> the class id), and in each column is the item's color for the corresponding class. The ID of an item is the number of its row in this file.<code>bin_types.csv</code>: This file contains the information about the bin types, and is sufficient to then generate the bins individually. One row corresponds to one bin type. The first column (<code>bin_capacity</code>) gives the bin type's volume capacity. The second column (<code>count</code>) tells how many bins of that type are in the instance. The third column (<code>cost</code>) is the bin type's cost. When creating the bins, we give an ID to each of them. Bins are generated by increasing order of bin type. So if there are for example two bin types (named type 1 and type 2), with 30 bins of type 1 and 10 bins of type 2, the bins of type 1 will have IDs going from 0 to 29 and bins of type 2 will have IDs going from 30 to 39.<code>classes.csv</code>: This file contains information about classes. One row corresponds to one class. The first column (<code>class</code>) indicates which class we are considering. The second column (<code>colors</code>) indicates how many colors exist for the class. The third column (<code>capacity</code>) is the class's capacity.How to read an instance IDThe three instance sets were generated independently by different authors and use distinct naming conventions for their instance directories. We decided to preserve these conventions, and now provide a guide on how to read them.<b>Set 1</b>This set was generated by Anand and Guericke (2020). An instance will be named for example <code>ID2_I100_C120_ALPHA1.41_BETA6.6_U0.1_UB5_R1</code><code>ID2</code> means that this is the second instance randomly generated with the parameters that follow<code>I100</code> means that there are 100 items in the instance<code>C120</code> means that there are 120 bins in the instance<code>ALPHA1.41_BETA6.6</code> means that the <i>alpha</i> and <i>beta</i> parameters of the beta-distribution used to generate the volume of items are 1.41 and 6.6, respectively<code>UB5</code> means that the class capacity is 5 for each class<code>R1</code> means that there is 1 class in the instance<b>Set 2</b>This set was generated by Borges et al. (2020). An instance will be named for example <code>Q2C1N3B2W2_1_BPP</code>.<code>Q2</code> gives the number of colors of the first class (as this set was originally designed with one class, only this class has its information in the instance ID). There are three possible values: <code>Q1</code> corresponds to 10 colors, <code>Q2</code> corresponds to 25 colors, and <code>Q3</code> corresponds to 50 colors.<code>C1</code> gives the capacity of the first class. There are again three possible values: <code>C1</code> corresponds to 2, <code>C2</code>corresponds to 3, and <code>C3</code> corresponds to a number that is either 2 or the average number of items per bin in the classical BPP solution (see the paper for more details)<code>B2</code> gives the bin volume capacity. Once again there are again 3 possible values: <code>B1</code> corresponds to 100, <code>B2</code>corresponds to 150, and <code>B3</code> corresponds to 200.<code>W2</code> gives the distribution of the items' volumes were sampled from. In our paper, we have used those distributions to define four instance types. Based on this correspondence, replacing W with T gives the instance's type. So in this case, <code>W2</code> means that the instance is of type T2.<code>_1</code> means that this is the second instance randomly generated with those parameters (indexation starts at 0 for this set).The other elements of the instance ID do not bear useful information.<b>Set 3</b>This set was generated for this paper. Information about the instance type and the correlation between the number of colors and the class capacity is found in the sub-folder names. An instance will then be named for example <code>I500_C4_6</code>.<code>I500</code> means there are 500 items in the instance<code>C4</code> means there are 4 classes in the instance<code>_6</code> means this is the sixth instance randomly generated with those parametersResultsThe results CSV files are found inside the <code>results</code> folder. They are divided between <code>lower_bounds</code> and <code>heuristics</code>.Lower boundsIn <code>lower_bounds</code>, you will find for each set:a file with the results of Column Generation results (files <code>colgen_*</code>)one file with the results of the compact formulation's relaxation solved using Gurobi (files <code>gurobi_lp</code>).A file contains the results of all the instances in the set. For each instance, we report the number of items and classes, as well as the instance's type (column <code>type</code>) for Sets 2 and 3 (this value is always 1 for Set 1, as there is no instance type).Greedy heuristicsIn <code>heuristics/greedy</code>, you will find for each set the results of all the greedy heuristics for each instance of the set.<br>For <code>set2</code>, there are 4 columns for bin types, but only type 1 is used. The other 3 columns can therefore be ignored. The intention was to have the same columns for all files.ALNSIn <code>heuristics/alns</code>, you will find for each set:a file with the results of the 10 ALNS runs for each instance of the set (files <code>alns_*</code>)a file with only the best solution for each instance (files <code>best_alns_*</code>).In both cases, you will find the results of the 5-minute and 1-hour runs.We also provide the detail of the best solution found by the 1-hour ALNS for each instance. The files are found in <code>heuristics/alns/detail</code>. There is one folder per instance (sub)set. A file indicates to which bin an item is assigned, using the item and bin ID systems described above.