OR Spectrum (2022) 44:375–417
https://doi.org/10.1007/s00291-021-00628-x
ORIG INAL ART ICLE
Bin packing with lexicographic objectives for loading
weight- and volume-constrained trucks in a direct-shipping
system
Katrin Heßler1 · Stefan Irnich1 · Tobias Kreiter2,3 · Ulrich Pferschy3
Received: 14 April 2020 / Accepted: 24 March 2021 / Published online: 17 July 2021
© The Author(s) 2021
Abstract
We consider a packing problem that arises in a direct-shipping system in the food and
beverage industry: Trucks are the containers, and products to be distributed are the
items. The packing is constrained by two independent quantities, weight (e.g., mea-
sured in kg) and volume (number of pallets). Additionally, the products are grouped
into the three categories: standard, cooled, and frozen (the latter two require refrig-
erated trucks). Products of different categories can be transported in one truck using
separated zones, but the cost of a truck depends on the transported product categories.
Moreover, splitting orders of a product should be avoided so that (un-)loading is sim-
plified. As a result, we seek for a feasible packing optimizing the following objective
functions in a strictly lexicographic sense: minimize the (1) total number of trucks;
(2) number of refrigerated trucks; (3) number of refrigerated trucks which contain
frozen products; (4) number of refrigerated trucks which also transport standard prod-
ucts; (5) and minimize splitting. This is a real-world application of a bin-packing
problem with cardinality constraints a.k.a. the two-dimensional vector packing prob-
lemwith additional constraints.We provide a heuristic and an exact solution approach.
The heuristic meta-scheme considers the multi-compartment and item fragmentation
B Katrin Heßler
khessler@uni-mainz.de
Stefan Irnich
irnich@uni-mainz.de
Tobias Kreiter
tobias.kreiter@scc.at
Ulrich Pferschy
pferschy@uni-graz.at
1 Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes
Gutenberg University Mainz, Jakob-Welder-Weg 9, D-55128 Mainz, Germany
2 scc EDV-Beratung AG, Wambachergasse 10, 1130 Wien, Austria
3 Department of Statistics and Operations Research, University of Graz, Universitaetsstrasse 15/E3,
8010 Graz, Austria
123
376 K. Heßler et al.
features of the problemand applies various problem-specific heuristics. The exact solu-
tion algorithm covering all five stages is based on branch-and-price using stabilization
techniques exploiting dual-optimal inequalities. Computational results on real-world
and difficult self-generated instances prove the applicability of our approach.
Keywords Bin packing · Lexicographic objective · Heuristics · Column generation ·
Dual-optimal inequalities
1 Introduction
In this paper, we present a system of bin-packing problems that arise in a direct-
shipping system in the food and beverage industry. More than 1.2 million units of
different products leave the factory of our industry partner every day. By far, the
largest share of the products is transported by trucks from the factory to the distribution
centers of supermarket chains (in the following denoted as warehouses). As shipping
is done directly from the factory to individual warehouses with full-truck volumes, the
routing of trucks plays no role. For each warehouse, the use of the utilized trucks has
to be optimized by assigning shipments to trucks. Hence, the overall problem naturally
decomposes by warehouse.
The transportation of products is standardized and uses euro-pallets (which are
typically packedwith a set of uniformboxes of a product). In our application, quantities
are large so that pallets are not mixed, i.e., each pallet contains only one product.
Moreover, it is legitimate to assume that products are equally distributed on pallets
such that each pallet loaded with a certain product has the same weight. Let K =
{1, 2, . . . ,m} denote the set of products (to be shipped to a particular warehouse on a
specific day). As the range of food products includes a huge variety of commodities,
e.g., fruit juices, spirits, baked goods, jams, wafers, and ketchup, the weight and space
requirements for the transport differ substantially by product. For each product k ∈ K ,
these requirements are therefore described by two attributes:
• the unit weight ρk (in kg/pallet) of a pallet loaded with product k and
• the number nk of pallets that need to be shipped.
In addition, all products can be uniquely grouped into three categories:
• Standard products I S require no cooling;
• Cooled products IC require cooling;
• Shipping of frozen products I F requires deep cooling and is themost costly transport.
As a result, the set of products is partitioned into I = I S ∪ IC ∪ I F.
The fleet consists of standard trucks and refrigerated trucks, i.e., trucks without and
with a cooling system. Frozen and cooled products must be transported in refrigerated
trucks, which are more costly than standard trucks. Frozen and cooled products can be
mixed (using different zones), but costs are higher if frozen products are transported.
Also, standard products can be transported by refrigerated trucks (again using sepa-
rated zones). There are no conflicts between products, i.e., any subset of products can
be packed together into a truck. All trucks are homogeneous regarding capacity. Let
123
Bin packing with lexicographic objectives for loading… 377
W be the capacity (in kg) for the physical weight and B be the capacity for the number
of pallets that fit into one truck (usually B = 33 pallets).
Moreover, dependingon the customer orwarehouse, twopolicies are applied regard-
ing the splitting of orders of the same product:
forbidden: Splitting is forbidden so that all nk pallets loaded with product k ∈ K
must be transported by the same truck. This is the standard case because
it simplifies the handling and processing in the loading and unloading
phases.
allowed: Splitting is allowed so that the nk pallets of a product k ∈ K may be
distributed arbitrarily over the trucks.Note that neither pallets nor packages
on the pallets are split. Orders are split so that pallets of one product are
transported with more than one truck. This splitting-allowed policy can
help to reduce the total number of used trucks but causes inconveniences.
It should not occur more often than necessary (see objective 5. below).
For a given solution, we denote a product assigned to two or more trucks as split
product.
We want to present both policies, splitting-forbidden and splitting-allowed, as vari-
ants of the same packing problem. For this purpose, we introduce items which are the
atomic, not-divisible objects in the bin-packing model. The set K of products and the
set I of items are identical, i.e., K = I . However, we write k ∈ K to refer to products
and i ∈ I to refer to items. Depending on the policy, we define two weights for each
item: wi refers to the physical weight and bi to the volume expressed as number of
pallets. Table 1 and Example 1 clarify the correspondence.
Example 1 Consider a set of products consisting of three standard products (n1 =
5, n2 = 5, n3 = 3, ρ1 = ρ2 = ρ3 = 1), (gray in Fig. 1), one cooled product
(n4 = 2, ρ4 = 2) (green in Fig. 1), and one frozen product (n5 = 3, ρ5 = 3)
(blue in Fig. 1), i.e., K = I = {1, . . . , 5} with I S = {1, 2, 3}, IC = {4}, I F = {5}.
Then, the corresponding instance of the splitting-forbidden policy has parametersw =
(5, 5, 3, 4, 9), b = (5, 5, 3, 2, 3), q = 1, whereas the corresponding instance of the
splitting-allowed policy has parametersw = (1, 1, 1, 2, 3), b = 1, q = (5, 5, 3, 2, 3).
With these definitions of items i ∈ I with two weights (wi , bi )i∈I and two capaci-
ties (W , B), the problem of assigning products to trucks becomes a two-dimensional
bin/vector-packing problem (see Sect. 2 for references to the pertinent literature). Triv-
ially, a feasible packing exists only if wi ≤ W and bi ≤ B holds for all items i ∈ I .
Table 1 Relationship between products and items for the splitting-forbidden and splitting-allowed policies
Product k ∈ K Corresponding item i ∈ I
Policy Splitting-forbidden Splitting-allowed
Unit weight ρk Weight 1 wi = ρk · nk wi = ρk
Number of pallets nk Weight 2 bi = nk bi = 1
Demand qi = 1 qi = nk
123
378 K. Heßler et al.
splitting forbidden splitting allowed
minimize number of splits (5a.) min. number of split products (5b.)
Fig. 1 Optimal solutions of three objectives for Example 1 with capacity B = 6 pallets
What also makes our real-world problem interesting is the non-standard objective.
We are seeking for a feasible product-truck assignment optimizing the following five
objectives in a strictly lexicographic sense:
1. Minimize the total number of trucks;
2. Minimize the number of refrigerated trucks;
3. Minimize the number of refrigerated trucks transporting frozen products;
4. Minimize the number of refrigerated truckswhich also transport standard products;
and
5. Minimize order splittings, which is either
5a. Minimize the overall number of splits; or
5b. Minimize the number of products which are split (over any number of trucks).
The fifth objective is only relevant for the splitting-allowed policy. Altogether, we
show that this lexicographic objective can be optimized by solving a sequence of
extended bin-packing problems. Note that it is not a-priori given how to measure
the impact of order splitting. The corresponding objective will depend on the actual
handling of split orders after their delivery at the destination warehouse. According to
our industry partner, there are two different strategies observedwith its customers: One
customer handles products separately for every truck. This means that for every truck
the processing effort depends on the number of different products (but also on other
factors, such as the number of pallets). Therefore, it is cost-efficient to minimize the
overall number of splits, i.e., packing one product separated into two trucks is preferred
over packing it separated into three trucks, as stated in objective 5a. A second customer
collects all pallets carrying the same product, but arriving on different trucks, in the
unloading zone and then inserts them into the warehouse in one batch. Thus, the main
effort of splitting is due to the necessity of reserving a collection area, which happens
123
Bin packing with lexicographic objectives for loading… 379
whenever a product order is split. Whether pallets are collected from two or more
trucks hardly plays a role, as stated in objective 5b.
Note that for both splitting policies, objectives 1.–4. have to be observed in a lexico-
graphic sense. This means that, e.g., a solution with 20 trucks and many refrigerated
trucks is preferred over a solution with 21 trucks and less refrigerated trucks. An
example of three different optimal solutions (splitting-forbidden, splitting-allowed
and minimize either the number of splits or the number of split products) is given in
Fig. 1.
The methodological contribution of our paper is the development of an exact and
heuristic solution approach. The exact approach is based on branch-and-price (BaP)
(Desaulniers et al. 2005; Lübbecke and Desrosiers 2005). For different objectives and
corresponding extended bin-packing problems, we develop a unified description of the
respective column-generation subproblems. We show that, in turn, each subproblem
can be solved by one or several modified 2-dimensional knapsack problems (Martello
and Toth 2003; Kellerer et al. 2004, ch. 9.6). These are especially involved in the case
of the splitting-allowed policy. Moreover, an important and here non-trivial algorith-
mic component is the branching scheme. We adopt the branching scheme originally
developed and successfully applied by Heßler et al. (2018) to the vector-packing prob-
lem. Stabilization with dual-optimal inequalities (Ben Amor et al. 2006; Gschwind
and Irnich 2016) helps to increase the performance of the BaP approach.
The heuristic approach works in two levels: In the first level, several constructive
heuristics are employed to reach a packing of items from the same category. They
strive for a balanced utilization of weight and volume constraints based on weight-
per-pallet, i.e., density considerations, and on the surrogate weights as introduced
by Caprara and Toth (2001). In the second level, a more complicated meta-scheme
considers the multi-compartment and product-fragmentation features of the problem
at hand and applies various problem-specific heuristics to search for good solutions.
They are based on decomposing and regrouping the best solution obtained from thefirst
level to improve the lexicographic objectives for different product categories. At first,
only the splitting-forbidden policy is considered. Then, for the splitting-allowed policy
we try to improve the given solution by separating certain pallets of the same product
and possibly reduce the number of trucks by reassigning these items. Throughout the
heuristic process, we compare the current solutions to lower bounds as a stopping
criterion. It should be noted that the heuristics were also incorporated in the SAP
ERP software system of our industrial partner, a European producer of foodstuffs and
beverages, and are used in the daily planning process.
We conducted a series of computational experiments with the exact and heuristic
algorithms based on real-world data sets with up to 430 items and on more difficult
test instances derived from these. We compare the performance of our heuristic to the
previously employed strategy of the company and to the proven optimal solutions.
It turns out that the heuristic saves on average one truck per day compared to the
previously used approach for real-world instances, with an even higher advantage for
more difficult instances. At the same time, running times are moderate, often less than
one second. The gap to the optimal solution is fairly moderate for real-world instances
but increases for the self-generated hard test cases. Regarding the performance of the
exact branch-and-price algorithm,most of the test instances can be solved to optimality
123
380 K. Heßler et al.
within the time limit of 10min for every subproblem. Notably exceptions arise for
some of the generated, difficult instances in case of the splitting-allowed policy. We
can also illustrate the highly positive effect of strengthening the ILP-models by lower
bounds and of solving pricing problems on a reduced graph. Finally, combining the two
approaches it turns out that adding the best heuristic solution to the set of columns of
the branch-and-price approach has hardly any effect for the splitting-forbidden policy,
but it gives a major improvement for the splitting-allowed policy.
The remainder of the paper is organized as follows: In Sect. 2, a brief overview
of the literature on two-dimensional bin-packing problems with and without item
fragmentation andmulti-compartment vehicle-routing problems is given. Analytically
computed lower bounds are presented in Sect. 3. Details on the exact BaP algorithm are
provided in Sect. 4, including the sequence of extensive formulations used for different
objectives, the unified column-generation algorithm, and stabilization techniques. The
heuristic approach is presented in Sect. 5. In Sect. 6, the results of our computational
experiments are presented and discussed. Final conclusions are drawn in Sect. 7.
2 Literature review
The classical one-dimensional bin-packing problem (BP) is one of the most funda-
mental problems in combinatorial optimization: A given set of items has to be packed
into a minimum number of bins such that the total weight of the items in each bin does
not exceed the bin capacity. Classical heuristics for BP, such as first-fit (FF), best-fit
(BF) and worst-fit (WF), and their variants based on a decreasing ordering of item
weights, i.e., FFD, BFD, and WFD (see, e.g., Coffman et al. 2013), will be assumed
common knowledge throughout this paper.
For the exact solution of BP, two alternative and competing solution principles
can be observed in the recent literature (see Delorme et al. 2016, for an overview of
BP formulations). The first type of solution approach relies on pseudo-polynomial
arc-flow formulations (Valério de Carvalho 1999) solved with general-purposemixed-
integer linear programming (MIP) solvers. Important refinements are network/graph
compression techniques (Brandão and Pedroso 2016) and the use of reflect networks
modeling packings with only half of the bin capacity (Côté and Iori 2018). The first
half and the second half of a packed bin are represented and feasibly combined in the
reflect network. The second type of solution approach uses a pattern-based formulation
a.k.a. the Gilmore–Gomory model (Gilmore and Gomory 1961), which is solved by
column generation techniques. While early works focused on the solution of the linear
relaxation in order to quickly compute a strong lower bound, the necessary theory
providing a complete branching scheme leading to a fully fledged BaP algorithm
has been provided with the work of Vanderbeck (1999). A state-of-the-art branch-
price-and-cut approach for BP is presented by Wei et al. (2020b). A hybrid of both
approaches, denoted as reflect+, has been recently coined by Delorme and Iori (2020)
and seems to be a very competitive approach making use of the excellent dual bounds
provided by column generation, heuristically and exactly truncated reflect networks,
and the power of modern MIP solvers.
123
Bin packing with lexicographic objectives for loading… 381
Due to the high practical relevance of packing problems, many variations in the
classical one-dimensional BP have been investigated. For a comprehensive overview,
we refer to the surveys by Christensen et al. (2017) and Coffman et al. (2013). In
the context of our real-world bin-packing variant, especially publications dealing with
two-dimensional, multi-compartment, and item fragmentation aspects are of particular
relevance.
Two-dimensional BPs represent a well-studied generalization and, hence, a large
number of publications in this field appeared over the last decades. We do not consider
packing problems in which geometric items have to be placed into bins, known as
rectangle packing (Lodi et al. 2002). Relevant for our application are p-dimensional
BPs with p = 2 independent dimensions (such as physical weight and volume, or
value and weight). In the literature, these problems are given different names, e.g.,
(2-dimensional) vector (bin) packing problem (VPP, 2D-VPP) and two-constraint bin-
packing problem. Our problem is a variant of the 2D-VPP for which an early exact
approach is given by Spieksma (1994). Recent exact approaches are based on BaP and
are described in Heßler et al. (2018) and Wei et al. (2020a). General approximation
results are given in Bansal et al. (2016). The case, where weights and volume are
strictly ordered, is considered in Caprara et al. (2003). Simple greedy-type heuristics
are presented in Aringhieri et al. (2018). A comprehensive survey of vector packing
problems can be found in Christensen et al. (2017).
Multi-compartment problems arise when different item types can be packed into
the same bin but have to be separated from each other (incompatibility constraints).
Those settings aremainly studied in vehicle-routing problems, see the surveys (Pollaris
et al. 2014; Henke 2018). In our application, there are no incompatibilities between
products/items. However, the use of compartments for cooled and frozen products
imposes additional costs.
The introduction of item fragmentation generalizes the classical BP by allowing
items to be split among several bins at a cost. Item fragmentation for BPs is introduced
and proved NP-hard by Mandal et al. (1998). More recent publications provide exact
solution algorithms based on column generation and dual cuts techniques as well as
employing heuristics and implicit enumeration (Casazza and Ceselli 2016). LeCun
et al. (2015) presents models for practical applications of item fragmentation like
minimizing the number of money transfers after a group trip and presents approxima-
tion algorithms for identical as well as for the more generic case of non-equal-sized
bins. The generalization to bins that differ in both cost and capacity is tackled in the
contribution Casazza (2019) by proposing new mathematical programming models
that even avoid the use of fractional variables. A worst-case analysis for BP with item
fragmentation is performed by Bertazzi et al. (2019). General models of valuations
for fragmented items are considered for the closely related knapsack problem in the
recent workMalaguti et al. (2019). Recall from Sect. 1 that in our application, products
might be divisible (depending on the splitting policy) but that by definition our items
are never split. Our definition of an item has implicitly solved issues related to product
fragmentation by discretely splitting demand along the volume (=pallets) dimension.
123
382 K. Heßler et al.
3 Lower bounds
Various lower bounds for subsets of items or all items are used in different parts of the
algorithms. For convenience, we introduce these lower bounds in this brief section.
A straightforward lower bound on the number of bins needed to pack a subset
I ⊆ I can be obtained by dividing the problem along the two dimensions. For each
dimension, one can compute a bound on the respective one-dimensional bin-packing
problems and then use the better bound of the two:
{⌈∑ ⌉ ⌈∑ ⌉}
I = i∈I wi biLB1( ) max , i∈I .
W B
Caprara (1998) proved that this lower bound equals the rounded up value of the linear
relaxation to the standard assigment-type ILP model for the two-dimensional bin-
packing problem, see e.g. (1)–(6) in Caprara and Toth (2001).
Another lower bound is inspired by the lower bounding procedure of Martello and
Toth (1990) for bin-packing problems. We use two distinct subsets of I, namely the
subset
I1 = {i ∈ I : wi > W/2 and bi > B/2}
of items consuming more than half of a bin’s capacity, and the disjoint subset
I2 = {i ∈ I\I1 : wi ≥ W/2 or bi ≥ B/2}
of items that do not fit together into a bin with any item of the subset I1. We obtain
the lower bound
LB2(I) = |I1| + LB1(I2).
In the following, the lower bound LB(I) = max{LB1(I), LB2(I)} is used for
various subsets I. For the sake of brevity, we define the following shorthand notation
for the lower bounds
= S = ( )LB LB(I ), LB LB I S , LBF = ( F) ( )LB I , and LBC,F = LB IC ∪ I F .
4 Branch-and-price algorithm
We propose the exact solution of the overall lexicographic minimization problem
using a stage-wise modified BaP algorithm (Desaulniers et al. 2005; Lübbecke and
Desrosiers 2005).While the first objective isminimized by solving a standard 2D-VPP,
the following four stagesfirst restrict the solution space to previously computedoptimal
value(s) and then apply BaP to the restricted formulation. Since the initial formulation
is of the Gilmore–Gomory type (Gilmore and Gomory 1961; Heßler et al. 2018),
the linear programs can be characterized as extensive, meaning that they typically
123
Bin packing with lexicographic objectives for loading… 383
exhibit an enormous number of variables. BaP is tailored to solving such extensive
optimization problems. Technically, BaP is a branch-and-bound algorithm in which
the linear relaxation at each node of the search tree is solved by column generation
(CG). CG is an iterative method that solves a linear program by decomposing it into
a restricted master problem (RMP) and a pricing subproblem (SP).
In Sect. 4.1, we start by describing the set of all feasible packing patterns and
define some subsets of patterns which are later used for presenting the restricted
formulations that address the objectives 2.–4., 5a., and 5b. at subsequent stages. The
unifying approach for the pricing subproblems presented in Sect. 4.2 is followed by
the discussion of stabilization, branching schemes, and acceleration techniques in
Sects. 4.3–4.5.
4.1 Pattern-based formulations
The models of all stages are variations in the covering formulation of Gilmore and
Gomory (1961) that are based on patterns. A pattern describes a feasible packing of
a bin with items. For each item i ∈ I , the value
{ ⌊ ⌋ ⌊ ⌋}
W B
ui = min qi , ,
wi bi
is an upper bound on the number of times that item i may occur in a pattern. The set
of all feasible patterns is therefore
{ ∑ ∑ }m m
P = (a1, . . . , a )m ∈ Z+m : aiwi ≤ W , aibi ≤ B and ai ≤ ui for all i ∈ I .
i=1 i=1
Recall that for the standard case of the splitting-forbidden policy, we have qi = 1
and thus ui = 1 so that all feasible patterns are binary, i.e., (a1, . . . , am) ∈ {0, 1}m .
Thus, the resulting VPP is a binary VPP (01-VPP). For the splitting-allowed policy,
the coefficients ai are upper bounded by integers ui so that the resulting VPP is a
bounded VPP (B-VPP).
For Stages 2.–5., pattern subsets taking different product types into account have
to be considered. We use the superscripts S, C, and F to refer to standard, cooled, and
frozen products/items, respectively. A combination of superscripts refers to patterns
that only include items of the respective categories. If a superscript is supplemented
with > 0, at least one item of the category must be included. Table 2 exactly defines
the relevant pattern subsets.
Stage 1.: Minimize the total number of trucks
At Stage 1., the minimization of the number of trucks is equivalent to the minimization
of the total number of bins that are used. Therefore, the problem is a standard 2D-VPP.
The Gilmore–Gomory formulation comprises non-negative integer variables xp for all
patterns p ∈ P and is given by
123
384 K. Heßler et al.
Table 2 Overview of pattern subsets
Pattern subset Specificat∑ion regarding categories of items∑ ∑
Standard i∈IS ai Cooled i∈IC ai Frozen i∈IF ai
PS = 0 and = 0
PC = 0 = 0
PF = 0 and = 0
PC,F = 0
PS,C>0 ≥ 1 and = 0
PC,F>0 = 0 and ≥ 1
PS>0,C>0 ≥ 1 and ≥ 1 and = 0
PS,C,F>0 ≥ 1
PS>0,C,F>0 ≥ 1 and ≥ 1
PS,C∪F>0 ∑ ∑i∈IC ai + i∈IF ai ≥ 1
PS>0,C∪F>0 ≥ ∑ ∑1 and i∈IC ai + i∈IF ai ≥ 1
∑
z1. = min xp duals: (1a)
p∑∈P
(Stage 1.) subject to a pi x p ≥ qi , i ∈ I [πi ] (1b)
p∈P
xp ≥ 0 integer, p ∈ P. (1c)
The objective (1a) minimizes the number of bins, i.e., patterns used. Constraints (1b)
ensure that the demand of all items is covered. Note that for an RMP, i.e., the linear
relaxation of a model with a restricted variable/pattern set P ′ ⊂ P , we also show the
associated dual variables (πi )i∈I of constraints (1b) that we later use in Sect. 4.2 to
describe the CG process. The domain of the pattern variables is defined by (1c). The
first stage can be exactly solved with the BaP algorithm presented by Heßler et al.
(2018) without any adaptation.
Stage 2.: Minimize the number of refrigerated trucks
The secondary objective of minimizing the number of refrigerated trucks is equivalent
to minimizing the number of patterns of the subset PS,C∪F>0 (see Table 2). The first
objective imposes the additional condition that the total number of all trucks/bins is
restricted to z1.. It can be incorporated intomodel (1)with a single additional constraint,
leading to:
∑
z2. = min xp duals: (2a)
p∈PS,C∪F>0
123
Bin packing with lexicographic objectives for loading… 385
(Stage 2.) subject to (∑1b)−(1c)
x 1.p ≤ z [δ2b] (2b)
∑p∈P
x ≥ LBC,Fp . [δ2c] (2c)
p∈PS,C∪F>0
The objective (2a) minimizes the number of refrigerated trucks. Constraint (2b)
restricts the total number of trucks to the minimum number resulting from the solution
of formulation (1). A lower bound on the number of refrigerated trucks is imposed by
constraint (2c). Note that constraint (2c) is not mandatory for the correctness of the
model, but its addition often yields a better lower bound of the linear relaxation.
Stage 3.: Minimize the number of refrigerated trucks which contain frozen products
The tertiary objective of minimizing the number of refrigerated trucks that contain
frozen products is equivalent to minimizing the number of patterns of the sub-
set PS,C,F>0 (see Table 2). At Stage 3., we additionally have to bound the number of
refrigerated trucks by z2., which yields to the model
∑
z3. = min xp duals: (3a)
p∈PS,C,F>0
(Stage 3.) subject to∑(1b)−(1c), (2b)
x ≤ z2.p [δ3b] (3b)
p∈P∑S,C∪F>0
xp ≥ LBF. [δ3c] (3c)
p∈PS,C,F>0
The objective (3a) is the minimization of the number of trucks transporting frozen
products. Constraint (3b) fixes the total number of refrigerated trucks. Since this fixa-
tionmakes constraint (2c) redundant, it is omitted.We add the constraint (3c) imposing
a lower bound on the number of frozen trucks to strengthen the linear relaxation.
Stage 4.: Minimize the number of refrigerated trucks which also contain standard
products
The fourth rate objective of minimizing the number of refrigerated trucks which
also contain standard products is equivalent to the minimization of patterns of the
subset PS>0,C∪F>0. Optimal values from the Stages 1.–3. are again incorporated as
additional constraints:
123
386 K. Heßler et al.
∑
z4. = min xp duals: (4a)
p∈PS>0,C∪F>0
(Stage 4.) subject to (1b∑)−(1c), (2b), (3b)
xp ≤ z3. [δ4b] (4b)
p∈∑PS,C,F>0
x ≥ LBS + z2. − z1.p . [δ4c] (4c)
p∈PS>0,C∪F>0
The objective (4a) minimizes the number of refrigerated trucks which also transport
at least one standard product. In the following, such a truck is denoted as mixed truck.
A lower bound on the total number of mixed trucks is LBS− (z1.− z2.). The difference
z1.− z2. gives the number of trucks containing only standard products. Subtracting this
number from the lower bound for the number of trucks required to pack all standard
products gives a lower bound on the number of mixed trucks. Constraint (4b) restricts
the number of frozen trucks. As constraint (3c), constraint (4c) is not mandatory but
helps to strengthen the linear relaxation.
Stage 5.: Minimize splitting
Recall from Sect. 1 that the last objective of minimizing splitting applies only to
the splitting-allowed policy and can be put into effect in two different ways using
objective 5a. or 5b.
In the case of objective 5a., minimizing the overall number of splits is equivalent to
m∣∣ inimizing the nu∣∣mber of different products packed into all bins. To this end, let sp ={a pi > 0 : i ∈ I } denote this number of different products/items in a pattern a pi ∈ P .
Then, the actual number of splits is given by the difference of the total number of
different products in all used bins and the total number m of products. Therefore,
minimizing the number of splits can be formulated as
∑
z5a. = min spxp duals: (5a)
p∈P
(Stage 5a.) subject to (1b)−(1∑c), (2b), (3b), (4b)
x ≤ z4.p . [δ5b] (5b)
p∈PS>0,C∪F>0
Constraint (5b) restricts the number of mixed trucks as determined at Stage 4.
In the case of objective 5b., it only counts whether a product is split or not, but
the number of trucks a split product occupies is irrelevant. Minimizing the number of
split products is equivalent to maximizing the number of integrally packed products. A
product is integrally packed if all its pallets are packed on the same truck. Accordingly,
for a pattern p ∈ P , we define for our m{inimization pro}blem the negative number
of integrally packed products as dp = −| i ∈ I : a pi = qi |. Hence, our objective is
expressed by the minimization of the total value of dp over all patterns used:
123
Bin packing with lexicographic objectives for loading… 387
∑
z5b. = min dpxp duals: (5c)
p∈P
(Stage 5b.) subject to (1b()−(1c),)(2b), (3b), (4b), (5b)∑ ∑ ∑
a pi x p ≤ qi . [γ ] (5d)
p∈P i∈I i∈I
Constraint (5d) ensures that each item i ∈ I is packed at most qi times. Note that the
latter constraint is indeed necessary because otherwise one might artificially improve
the objective function by adding additional integrally packed products more often
than demanded. In combination with the covering constraint (1b), both constraints
(5d) a∑nd (1b) are always binding. Therefore, adding disaggregated constraints of the
form a pp∈P i x p = qi for all i ∈ I does not yield a tighter formulation.
4.2 Column generation
With themodels (1), (2), (3), (4), (5a)–(5b), and (5c)–(5d),we have presented six differ-
ent extensive formulations that all require a CG-based solution approach. In principle,
pattern generation is algorithmically simple to manage, since we will show that the
subproblem solution finally boils down to solving binary or bounded 2-dimensional
knapsack problems, see (Martello and Toth 2003), (Kellerer et al. 2004, ch. 9.6). In the
following, we assume that a linear relaxation of the RMP is solved and has produced
dual prices (πi )i∈I and (δcon) for the respective constraint(s) con. The task of the SP
is to determine at least one negative reduced-cost pattern or to prove that no negative
reduced-cost pattern exists.
A first difficulty for precisely describing the associated SPs lies in the fact that
each of the six SPs associates different dual prices to groups of patterns depending
on whether they include standard, cooled, or frozen products/items. Handling these
multiple cases is indeed confusing. A fundamental step toward a concise and unified
handling is the idea to further divide each SP into 2D-KPs for subsets of patterns.
Solving the SP then amounts to solving the associated 2D-KPs. The decisive point is
that the reduced cost of a pattern p = (ai ) can be described as (at least for the first
four stages, see below)
∑
c̃p = δ − σi ai ,
i∈I
where the coefficients δ = δX and σ Xi = σi for i ∈ I depend of the particular
subcase X . Table 3 formalizes different (sub)cases: Depending on the stage/objective,
there are between one and five different pattern subsets (see Table 2 for their formal
definition) for which independent 2D-KPs need to be solved. For each pattern subset,
the columns σi and δ describe how these coefficients can be computed from the given
dual solution (πi )i∈I and (δcon) (using only dual prices of constraints con that exist
at the actual stage). Moreover, the 2D-KP can be restricted to an item subset I ⊂ I .
Finally, some pattern subsets require the presence of one or two subsets of items. For
123
388 K. Heßler et al.
example, PS>0,C,F>0 requires that at least one item of a standard product and one
item of a frozen product are present in the pattern. For this purpose, let R be the set
of required subsets of items, i.e., for PS>0,C,F>0 there isR = {I S, I F}. The elements
of the respective sets R are displayed in the last column of Table 3.
A second difficulty stems from the fact that, for the objectives 5a. and 5b., the
reduced cost of a pattern is no longer completely linear in the coefficients of the
pattern. However, all 2D-KPs can be formalized as follows. Nonnegative bounded
integer (binary for ui = 1) variables yi for i ∈ I describe the unknown pattern
coefficients ai . Moreover, for these variables y = (yi )i∈I , the function f (y) captures
the non-linear part of the reduced cost (described in detail in the next paragraphs).
For a given subset of admissible items I (in the sense of the second last column of
Table 3), the extended 2D-KP can now be described as
( )
zKP(I
∑
,σi ,δ,R) = δ −max σi yi − f (y) (6a)
i∑∈I
(KP(I, σi , δ,R)) subject to wi yi ≤ W (6b)
∑i∈I
bi yi ≤ B (6c)
∑i∈I
yi ≥ 1 J ∈ R (6d)
i∈J
yi ∈ {0, 1, . . . , ui }, i ∈ I. (6e)
The objective (6a) is the minimization of the reduced cost of the pattern. The con-
straints (6b) and (6c) are the capacity constraints. The defining property of somepattern
subsets to contain at least one item of one or two particular categories is enforced by
condition(s) (6d). The domain of the decision variables is defined by (6e).
At Stages 1.–4., the function f vanishes, i.e., f ≡ 0, so that KP(I, σi , δ,R)
reduces to a standard binary or bounded 2D-KP with the additional constraints (6d).
A straightforward solution approach could be to solve several standard binary 2D-
KP that previously pack one item of each set J ∈ R. Instead of enumerating all
combinations, the selection of previously packed items could also be embedded into
a branch-and-bound algorithm. However, we formulate and solve this subproblem as
a variant of the shortest-path problem with resource constraints (see next paragraph).
For the first splitting variant that minimizes the total number of splits, i.e., objec-
tive 5a., the function f must count the number of products the constructed pattern
contains. This is done with
f ( y) = |{i ∈ I : yi > 0}|.
For the second splitting variant that minimizes the number of split products, i.e.,
objective 5b., the function f must count the (negative) number of integrally packed
123
Bin packing with lexicographic objectives for loading… 389
123
Table 3 Overview of pricing subproblems
Stage Pattern subsets Dual prices Item subset I Elements of subsets R of
required items
σi δ
1. P πi 1 I
2. PS πi 1− δ2b IS IS
PS,C∪F>0 πi 1− δ2b − δ2c I IC ∪ IF
3. PS πi 1− δ S2b I IS
PS,C>0 πi 1− δ2b − δ − δ S C C2c 3b I ∪ I I
PS,C,F>0 πi 1− δ F2b − δ2c − δ3b − δ3c I I
4. PS πi 1− δ S2b I
PC πi 1− δ C2b − δ2c − δ3b I
PC,F>0 πi 1− δ2b − δ2c − δ − δ C F F3b 3c − δ4b I ∪ I I
PS>0,C>0 π Si 1− δ2b − δ2c − δ3b − δ4c I ∪ IC IS, IC
PS>0,C,F>0 πi 1− δ2b − δ2c − δ3b − δ3c − δ4b − δ4c I IS, IF
5a. PS πi 1− δ2b IS
PC πi 1− δ2b − δ2c − δ C3b I
PC,F>0 πi 1− δ C F F2b − δ2c − δ3b − δ3c − δ4b I ∪ I I
PS>0,C>0 πi 1− δ2b − δ2c − δ3b − δ S C S C4c − δ5b I ∪ I I , I
PS>0,C,F>0 πi 1− δ2b − δ2c − δ3b − δ3c − δ4b − δ4c − δ5b I IS, IF
5b. PS πi + γ 1− δ S2b I
PC πi + γ 1− δ2b − δ C2c − δ3b I
PC,F>0 πi + γ 1− δ2b − δ2c − δ3b − δ − δ IC ∪ IF F3c 4b I
PS>0,C>0 πi + γ 1− δ2b − δ2c − δ3b − δ4c − δ IS ∪ IC5b IS, IC
PS>0,C,F>0 πi + γ 1− δ2b − δ2c − δ3b − δ3c − δ4b − δ4c − δ5b I IS, IF
390 K. Heßler et al.
products the constructed pattern contains. The definition
f ( y) = −|{i ∈ I : yi = qi }|
gives the correct contribution. As an example, the two 2D-KPs arising at Stage 2. are
specified in the following example.
Example 2 At Stage 2., we consider two 2D-KPs that generate patterns of the subsets
PS and PS,C∪F>0. Recall that δ2b and δ2c are the dual prices of constraints (2b)
and (2c), respectively. Both 2D-KPs have σi = πi for all i ∈ I and f ≡ 0. The first
2D-KP generates patterns of set PS and is defined by δ = 1 − δ S
= { } 2b
, I = I , and
R I S , while the second generates patterns of the set PS,C∪F>0 and is defined by
δ = 1− δ − δ , I = I , and R = {IC ∪ I F2b 2c }.
SPPRC-based solution Different problems KP(I, σi , δ,R) can be formulated as
shortest path problems with resource constraints (SPPRCs, Irnich and Desaulniers
2005). SPPRCs canmodel intricate relationships between attributes andmany variants
of the SPPRC can be effectively solved by dynamic-programming labeling algorithms.
Such an approach has been successfully chosen for the one-dimensional BP by Wei
et al. (2020b) and for the VPP by Heßler et al. (2018). The advantage of a labeling-
based approach is that also subsets R of required items and the objectives 5a. and
5b. defining the function f can be considered as well as involved branching decisions
(discussed later in Sect. 4.4).
For the sake of simplicity, we start with the case that any item can be contained
in a pattern, i.e., I = I = {1, 2, . . . ,m}. The underlying digraph G = (V∑, E) then
∑consists of m + 1 vertices V = {0, . . . ,m}. The arc set E consists of m ++ i∈I ui =i∈I (ui 1) arcs partitioned into m subsets E(i) associated with item i ∈ I . The
set E(i) contains ui + 1 parallel arcs connecting vertex i − 1 with vertex i . Thus, we
have an arc set E(i) consisting of arcs e j (i) with j ∈ {0, 1, . . . , ui + 1}.
Each arc e j (i) has three attributes, two for the weights and one for the profit. For
the j-th arc e j (i) of E(i), these are defined as w(e j (i)) = j · wi , b(e j (i)) = j · bi ,
and σ(e j (i)) = j · σi , respectively.
An example of the digraph is sketched in Fig. 2. Each 0-m-path (0, e j1(1), 1, e j2(2),
2, . . . ,m − 1, e jm (m),m) uniquely d∑efines a pattern (ai ) with∑ai = ji . Necessary
conditions for its feasibility are that m mi=1w(e ji (i)) ≤ W and i=1 b(e ji (i)) ≤ B
holds. Partial paths that do not fulfill these conditions can be directly discarded.
(0, 0, 0)
(0, 0, 0) (0, 0, 0)
(w1, b1, σ1)
0 1 2 · · · m− 1 m
(2w1, 2b1, 2σ1)
(w , b (w , b , σ )2 2, σ2) m m m
(3w1, 3b1, 3σ1)
Fig. 2 SPPRC digraph with items having u1 = 3, u2 = 1, and um = 1. The arcs e ∈ E are shown with
their weights and profit (w(e), b(e), σ (e))
123
Bin packing with lexicographic objectives for loading… 391
If I  I , i.e., some categories of items are not in I, the corresponding digraph can
be obtained by reducing the arc set so that for each i ∈ I\I only the null-arc (0, 0, 0)
is in E(i). Subsequently, the digraph can be shrunk by merging vertices i − 1 and i
for all i ∈ I\I.
At Stages 2.–5., three additional boolean attributes v = (vS, vC , vF ) for the three
categories standard, cooled, and frozen are added to indicatewhether a specific product
category has been packed. For an item i ∈ I , we define v(e j (i)) = (1, 0, 0), (0, 1, 0),
or (0, 0, 1) for all j according to the category product/item i belongs to.
The SPPRC is solved by a forward dynamic-programming labeling algorithm
that works as follows: The starting point is the trivial partial path (0) with the
initial label (0, 0, 0). All labels at a vertex i − 1 are extended to vertex i itera-
tively for i = 1, 2, . . . ,m. A forward extension along an arc e(i) ∈ E(i) of label
L(F) = (w, b, v, σ ) (omitting the index j) produces the label (w + w(e(i)), b +
b(e(i)),max{v, v(e(i))}, σ + σ(e(i))), where the maximum operator is applied
component-wise. The labels at m and the associated 0-m-paths have to be filtered
at the end: Only labels (w, b, v, σ ) with correct v-values provide feasible patterns,
e.g., vC + v ≥ 1 for the pattern set PS,C∪F>0F used at Stage 2. in the second subcase.
Moreover, the reduced cost of the associated pattern is δ − σ .
The work of Heßler et al. (2018) has pointed out that different dominance principles
between labels are possible andworth to be investigated. There clearly exists a tradeoff
between the strength of a dominance rule and its computational burden resulting from
the pairwise comparison of labels. A strong dominance rule can help to drastically
reduce the overall number of labels that remain at termination of the labeling algorithm.
The result is also fewer labels at intermediate vertices,which reduces the computational
effort associated with the label extension step and later dominance comparisons. On
the downside, the application of the following strong dominance rule may require the
pairwise comparison of a possibly huge number of labels.
Rule 1 (Strong dominance) A forward label L(F) = (w, b, v, σ ) of a forward partial
path F dominates another forward label L(F ′) = (w′, b′, v′, σ ′) of a forward partial
path F ′ ending at the same vertex if w ≤ w′, b ≤ b′, v ≥ v′, and σ ≥ σ ′.
The following weaker dominance rule allows a direct O(1) comparison of labels,
immediately at the time when a label is created, if labels are stored in a lookup table.
Rule 2 (Weak dominance) A forward label L(F) = (w, b, v, σ ) of a forward partial
path F dominates another forward label L(F ′) = (w′, b′, v′, σ ′) of a forward partial
path F ′ ending at the same vertex if w = w′, b = b′, v = v′, and σ ≥ σ ′.
As inHeßler et al. (2018), also our pretests have confirmed that theweak dominance
Rule 2 performs better than the strong Rule 1 for most benchmark instance used in the
computational experiments. Therefore, we do not use Rule 1 and also omit its proof.
The validity of the weak dominance Rule 2 is obvious.
Finally, we discuss the incorporation of the functions f at Stage 5. into the SPPRC
modeling and solution approach. For the first objective 5a., the function f counts the
number of products the pattern contains, i.e., f ( y) = |{i ∈ I : yi > 0}|. Consequently,
the profit attribute on the arcs of the SPPRC digraph must consider the number of
123
392 K. Heßler et al.
different products in the resulting pattern. Thus, a cost of 1 is subtracted for every item
that is packed, i.e., every non-zero arc. An example is given in Fig. 3.
For the second objective 5b., the function f counts the (negative) number of inte-
grally packed products the pattern contains, i.e., f ( y) = −|{i ∈ I : yi = qi }|. Hence,
arc profits are modified if an item i is packed completely, i.e., the additional profit of
1 is added to the qi th arc of item i (present only if qi ≤ ui ). An example is given in
Fig. 4. Note that the dual price γ of constraint (5d) is already included in the definition
of σi for all i ∈ I .
4.3 Stabilization
TheCGprocess can be stabilized by using dual inequalities (Valério de Carvalho 2005;
Ben Amor et al. 2006; Gschwind and Irnich 2016). In the following, we restrict our-
selves to inequalities that are formulated only in the dual variables πi that correspond
to the demand fulfillment constraints (1b) of the model solved at Stage 1. (for the
subsequent stages we consider the projection onto the m-dimensional space defined
by the π -variables). Let D∗ be the set of dual optimal solutions to the linear relaxation.
For t ∈ mZ and t ∈ Z, the dual inequality (DI) tπ ≤ t is a dual-optimal inequality
(DOI) if D∗ ⊆ {π : tπ ≤ t}. A set of DIs is a set of deep dual-optimal inequalities
(DDOIs) if at least one optimal dual solution π∗ ∈ D∗ fulfills all inequalities of this
set.
We first focus on Stage 1. and the B-VPP and 01-VPP. According to Heßler et al.
(2018), pair inequalities (PIs) πh ≥ πi are DDOIs for all h, i ∈ I with wh ≥ wi
and bh ≥ bi . In the primal formulation (1), these additional columns stand for the
exchange of the larger item h by the smaller item i , i.e., a zero-cost column in the
RMP with entries −1 and 1 for h and i , respectively. Moreover, subset inequalities
(0, 0, 0)
(0, 0, 0) (0, 0, 0)
(w1, b1, σ1 − 1)
0 1 2 · · · m− 1 m
(2w1, 2b1, 2σ1 − 1)
(w , b (w , b , σ − 1)2 2, σ2 − 1) m m m
(3w1, 3b1, 3σ1 − 1)
Fig. 3 SPPRC digraph for objective 5a. with otherwise identical attributes as depicted in Fig. 2. The arcs
e ∈ E are shown with their weights and profit (w(e), b(e), σ (e))
(0, 0, 0)
(0, 0, 0) (0, 0, 0)
(w1, b1, σ1)
0 1 2 · · · m− 1 m
(2w1, 2b1, 2σ1)
(w2, b2, σ2 + 1) (wm, bm, σm + 1)
(3w1, 3b1, 3σ1 + 1)
Fig. 4 SPPRC digraph for objective 5b. with otherwise identical attributes as depicted in Figure 2. The arcs
e ∈ E are shown with their weights and profit (w(e), b(e), σ (e))
123
Bin packing with lexicographic objectives for loading… 393
Table 4 Overview of DIs
Stage/objective Subsets of exchangeable items RHS of a SI defined by (S, h), i.e., cost c of the
associated primal column
1. I 0
2. IS, IC ∪ IF 0
3. and 4. IS, IC, IF 0
5a. IS, IC, IF |{i ∈ I : ti > 0}| − one(uh)
5b. IS, IC, IF 1
∑
(SIs)∑−πh + i∈S πi ≤∑0 are defined for any item h ∈ I and subset S ⊆ I\{h}
with i∈S wi ≤ wh and i∈S bi ≤ bh . We refer to a SI as (S, h). In general, SIs are
not necessarily DOIs or DDOIs for the B-VPP and the 01-VPP. Nevertheless, their
associated primal columns can be added to stabilize the RMP at the risk of a possible
over-stabilization. Over-stabilization can be restored with a recovery procedure of low
computational effort as described in detail in (Gschwind and Irnich 2016).
At Stages 2.–4., the use of DIs is still possible when categories of items are kept
separate, i.e., a SI for (S, h) can only be used if all items i ∈ S and also item h all
belong to the same, stage-dependent subset of exchangeable items. An overview of the
applicable DIs at different stages is provided in Table 4. For example, at Stage 2., the
PIs and SIs exclusively exchange either items of standard products I S or of refrigerated
products I C ∪ I F. At Stages 3. and 4., exchanges are only allowed among items of the
same category.
At Stage 5., we have to take into account the following speciality. The transforma-
tion of a solution with packing and DI columns into a pure packing column solution
may change the number of packed products in a pattern (to be taken into account at
Stage 5a.). Likewise, an integrally packed product may be transformed into a split
product and vice versa (to be taken into account at Stage 5b.). In order to ensure a
valid objective value after the replacement, we have to modify the right-hand side
of a DI from 0 to some integer value c, i.e., add a cost c to the corresponding pri-
mal DI column. T∑able 4 summarizes different cases. For example, let p ∈ P be
a pattern and let i∈I tiπi ≤ c be a DI. If at Stage 5a. in the primal model both
corresponding variables are positive, the following replacement can be performed:
Exchange item h by items {i ∈ I : ti > 0} in pattern p with original associated cost
sp (i.e., the number of packed products) yields a new pattern p′ with associated cost
sp′ ≤ sp +|{i ∈ I : ti > 0}|− one(uh), where one(u) is 1 for u = 1, and 0 otherwise.
The new pattern p′ might consist of added items {i ∈ I : ti > 0} compared to pattern
p, and if uh = 1, then item h vanishes in pattern p′.
Similarly, at Stage 5b., the (negative) number of integrally packed items for the new
pattern p′ can be estimated by dp′ ≤ dp + 1 because item h might change from an
integrally packed item to a split item.
As discussed in Gschwind and Irnich (2016) in more detail, one may experiment
with different strategies which DIs and at what point in time the DI columns are added
to the RMP. On the one hand, DI columns can be added at the very beginning to the
123
394 K. Heßler et al.
initial RMP and stay there during the entire CG process (static). On the other hand,
only violated DIs can be added during the CG process (dynamic). We combine these
two strategies which yields a mixed approach that adds some DI columns at the start
and adds violated DIs later on.
We employ this mixed strategy in the following form: For the initialization of the
first RMP, for each item i , the PIπi ≥ π j with j = argmink∈I\{i}{|wi−wk |+|bi−bk | :
wi ≥ wk, bi ≥ bk} is added and all SIs with |S| = 2 are added. While solving the root
node, violated PIs are added dynamically. At Stages 2.–5., we only keepDIs belonging
to the subset of exchangeable items according to Table 4 (and remove the others). In
the same spirit, we only dynamically add violated PIs belonging to these subsets.
4.4 Branching
We apply a single or a two-level branching scheme depending on the stage. At Stage 1.,
there is only one level where we apply the branching scheme suggested byVanderbeck
(1999). The idea is to formulate the 2D-VPP as a pure binary problem so that all pattern
coefficients are also binary. Branching is then performed choosing two disjoint subsets
I 0, I 1 of items. In any fractional solution there exists a pair (I 0, I 1) for which the
number of patterns having coefficients ai equal to 0 (1) for all i ∈ I 0 (∈ I 1) is
fractional. For a detailed explanation and examples, we refer to Heßler et al. (2018).
At Stages 2.–4., there are two branching levels. First, we branch on the number of
refrigerated trucks (2c), the number of frozen trucks (3c), and the number of mixed
trucks (4c), respectively. Second, we apply the above described branching rules of
Vanderbeck (1999).
At Stage 5., there are also two branching levels. First, we branch on the number of
integrally packed products, i.e., when the value
∑
a pi x p (7)
p=(ai )∈P:a pi =qi
is fractional for an item i ∈ I . Note that this is a special case of Vanderbeck branching,
which we apply subsequently at the second level.
At all levels, the branching variable/term is selected as one with fractional part
closest to 0.5. Ties are resolved randomly.
Note that all first-level and second-level branching decisions can be implemented
by either adding some linear constraint(s) to the RMP or by removing certain pattern
subsets. Since the branching rule of Vanderbeck (1999) ensures integrality, the overall
branching scheme is complete for all stages.
Finally, we use a depth-first tree exploration strategy. The intention is to find an
integer solution as soon as possible. Since the lower bounds of the linear relaxations of
formulations (1a)–(5) are often tight, we quickly obtain good and sometimes optimal
solutions.
123
Bin packing with lexicographic objectives for loading… 395
(0, 0, 0) (0, 0, 0) (0, 0, 0)
0 1 2 · · · m− 1 m
(u w (u w , u b , u π )1 1, u1b1, u1π1) (u2w2, u2b2, u2π2) m m m m m m
Fig. 5 Reduced SPPRC digraph for objective 1. with otherwise identical attributes as depicted in Figure 2.
The arcs e ∈ E are shown with their weights and profit (w(e), b(e), σ (e))
4.5 Acceleration techniques
When applying the splitting-allowed policy, patterns with fewer split products are
preferred over patterns with more split products. Therefore, it is beneficial to already
generate patterns with very few split products (if any) at the Stages 1.–4. so that
the initial RMP at Stage 5. mainly consists of variables representing patterns with
many integrally packed products. To foster that predominantly patterns with only
integrally packed products are generated, the SP is always first solved heuristically
over a reduced SPPRC digraph. In this reduced digraph, each item i ∈ I has only two
associated parallel arcs (0, 0, 0) and (uiwi , uibi , uiπi ) so that for ui = qi the item is
either integrally packed or not packed at all. An example of a reduced graph is given in
Fig. 5. Only if no pattern with negative reduced cost is found in the reduced digraph,
SPPRC SPs are solved again using the complete digraph.
This approach has two advantages: First, the 2D-KPs at the Stages 1.–4. are solved
faster because in most iterations the reduced network provides negative reduced cost
patterns. Secondly, Stage 5. is solved faster because the RMP already consists of bene-
ficial columns. Computational results show that this approach significantly accelerates
the CG process. For a computational analysis, we refer to Sect. 6.4.
5 Heuristics
For real-world applications, user acceptance is a crucial success factor, especially
for constructive heuristics, where the key users want to get some insights into the
decision mechanism. Therefore, we developed various heuristic ideas and presented
their underlying rationals as well as their strengths and weaknesses to the decision
makers of the affected company. For comparison, we also re-implemented the strategy
previously employed by the dispatchers, the so-called Business Today logic.
For our own development, we started with the well-known BFD, FFD, and WFD
heuristics, all of them employing the concept of surrogate weight (Sect. 5.1). Then
five additional heuristic approaches were developed in accordance to the real-world
situation of our industrial partner (Sect. 5.2). Comparisons to results of the Business
Today logic are found in Sect. 6.
5.1 Basic single-class heuristics
At the beginning, wewill introduce a number of heuristicswhich consider only a single
class of items and do not distinguish between products of different categories. Also
123
396 K. Heßler et al.
splitting products is not taken into account. At the end of this section, we will have
obtained one combined heuristic which consists of running all heuristics described so
far and taking the best solution. This combined heuristic will serve as building block
for a more complicated heuristic framework described in Sect. 5.4.
As pointed out in the introduction, we are facing a highly heterogeneous product
range where the unit weight ρk of product k ∈ K varies considerably. It is obvious
that truck loads containing mainly heavy goods (ρk  W/B) will leave excess pallet
spaces even if the weight capacity is exhausted. On the other hand, truck loads con-
taining mainly lightweight goods (ρk 
 W/B) still provide excess weight capacity
even if all pallet spaces are used. Thus, a “good” loading pattern should utilize both
capacity dimensions by mixing heavy and lightweight products in a suitable way.
Based on this simple observation, the transport planners previously created loading
patterns filling one truck after the other in a FF manner. Each truck is manually
assigned its load following a strict rule that alternately packs the heaviest and the
lightest unpacked item as described in Business Today Algorithm 1.
Algorithm 1 Business Today
Sort item set I by increasing ρi .
Open truck 1 and set t ← 1.
while I = ∅ do
Take the last (first) item i from I in an odd (even) iteration.
if i fits into truck t then
Insert i into truck t .
else
Open a new truck t + 1 and insert i .
t ← t + 1.
end if
Remove i from I .
end while
Practical experience showed: If each product fills only one pallet, i.e., bi = 1 for
all i ∈ I , then this procedure amounts to a pairwise combination of items with large
and small unit weight ρi and shows reasonably good results. However, this is a rare
case, and for all other, more general instances, inefficient solutions may occur. In the
worst case, many large items (high wi and bi ) with medium density ρi remain until
the end, which leads to unnecessary additional trucks.
Naturally, Algorithm 1 suffers from neglecting the absolute weights of items and
from the FF strategy of handling trucks. However, sorting items by decreasing weight
wi or decreasing number of pallets bi would only be useful for instances with a clear
dominance in one dimension. Our real-world test instances showed that both con-
straints, weight and pallet capacity, can become active, i.e., there is no clear dominance
of one of the two dimensions.
To overcome this dilemma, we suggest to apply the concept of a surrogate weight
proposed byCaprara andToth (2001). The surrogateweight of an item i ∈ I constitutes
a convex combination of relative weight and relative pallet number. For each i ∈ I , it
123
Bin packing with lexicographic objectives for loading… 397
is defined as
∑
b ww i= i + 1− is λ ( λ) , where = ∑ (i∈Iλ Wi ) .W B wi + b∈ ii I W B
Based on these surrogate weights, we can (almost) transform our packing problem
into a classical one-dimensional bin-packing problem and apply well-known standard
heuristics. In particular, we take FFD, BFD, andWFD, and adapt them for the solution
of our truck loading problem by using the surrogate weight si . In the following, we
present further heuristic approaches based on the concept of a surrogate weight.
5.2 Block-based single-class heuristics
In this section, we introduce three heuristics called A, B, and C, which are all based
on a fixed pattern of assigning blocks of items to trucks. Therefore, the lower bound
of the number of trucks LB (see Sect. 3) is computed and LB trucks are opened. Then,
the item set is partitioned into blocks of equal size LB. In each iteration, one block
is selected and matched to the set of trucks, i.e., every item of the block is assigned
to one of the trucks. The selection of blocks and the matching patterns differ between
the three heuristics. If an item does not fit into the preferred truck, the item is moved
to the next truck in the sequence (following a FF logic) or, if necessary, a new truck
is opened, see Algorithm 2. Note that any new trucks opened during the execution of
the heuristic only serve as a backup for loading items exceeding the capacity, while
the matching of subsets remains restricted to the originally opened LB trucks.
All three heuristics are based on sorting the items by increasing surrogateweights si .
Their details are informally described below followed by pseudocode. An illustrative
example is given in Table 5 further below.
Heuristic A assigns the LB items with largest surrogate weights to the LB trucks
and then adds the LB items with smallest surrogate weights in a reversed order, such
that the items with smax and smin end up in the same truck number 1. These two steps
are repeated iteratively for the remaining items as described in Algorithm 3.
Heuristic B also starts by assigning the LB items with largest surrogate weights to
the LB trucks, but then proceeds by assigning the next largest (w.r.t. si ) LB items to the
trucks in a mirrored order such that items with LBth and (LB + 1)-largest surrogate
weight end up being assigned to the same truck number LB, see Algorithm 4.
Finally, Heuristic C repeats the first step of Heuristic A and iteratively assigns the
items with largest surrogate weights to the LB trucks, always maintaining the same
order of trucks, see Algorithm 5.
Algorithm 2 Subprocedure Assign item i to truck t
Try to insert i into an open truck by a FF strategy,
i.e., try all trucks t, t + 1, . . . ,LB and then trucks 1, 2, . . . , t − 1 until item i fits.
If no such truck is found, insert i into a truck LB+ 1,LB+ 2, . . . by a FF strategy, opening a new truck
if necessary.
123
398 K. Heßler et al.
Algorithm 3 Heuristic A
Calculate lower bound LB and open LB trucks.
Sort item set I by increasing si .
Partition set I into H := m/LB subsets I j of cardinality LB according to the sorting. {For simplicity
of notation we assume that H is even.}
j ← 1, h ← H
while j < h do
for i ← LB downto 1 do
Assign item i in set Ih to truck LB− i + 1.
end for
h ← h − 1
for i ← 1 to LB do
Assign item i in set I j to truck i .
end for
j ← j + 1
end while
Algorithm 4 Heuristic B
Calculate lower bound LB and open LB trucks.
Sort item set I by increasing si .
Partition set I into H := m/LB subsets I j of cardinality LB according to the sorting. {For simplicity
of notation we assume that H is even.}
j ← H
while j ≥ 1 do
for i ← LB downto 1 do
Assign item i in set I j to truck LB− i + 1.
end for
j ← j − 1
for i ← 1 to LB do
Assign item i in set I j to truck i .
end for
j ← j − 1
end while
To illustrate the different heuristics, an example with 20 items is given in Table 5.
Obviously, Heuristic A exhibits more similarities to the Business Today logic, includ-
ing the feature of not keeping the items with lowest si until the end. Heuristics B and
C overcome that issue. Besides that, Heuristic B aims at uniformly filling all trucks.
According to the basic intuition of how good solutions might look like, this should
reduce the probability that any smaller item does not fit into its preferred truck. On
the other hand, Heuristic C provides gaps of different sizes in the LB different trucks,
which may offer more room to maneuver if an item does not fit into its assigned truck.
5.3 Density-based single-class heuristics
The third group of heuristics for items of the same class is based on the unit weight
ρ considerations discussed at the beginning of Sect. 5.1. Recall that “good” loading
patterns, in general, utilize both capacity dimensions and do not leave large excess
123
Bin packing with lexicographic objectives for loading… 399
123
Table 5 Comparison of solutions produced by the Business Today algorithm and Heuristics A, B, and C. The example has 20 items I = {1, 2, . . . , 19, 20} and LB = 5. Items
are numbered according to their surrogate weight in ascending order, i.e., item 1 is the smallest item and item 20 is the largest item
Business Today Heuristic A Heuristic B Heuristic C
truck\iter. 1 2 3 4 1 2 3 4 1 2 3 4
t = 1 20 1 19 2 18 20 1 15 6 20 11 10 1 20 15 10 5
t = 2 3 17 4 16 19 2 14 7 19 12 9 2 19 14 9 4
t = 3 5 15 6 14 18 3 13 8 18 13 8 3 18 13 8 3
t = 4 7 13 8 12 9 17 4 12 9 17 14 7 4 17 12 7 2
t = 5 11 10 16 5 11 10 16 15 6 5 16 11 6 1
400 K. Heßler et al.
Algorithm 5 Heuristic C
Calculate lower bound LB and open LB trucks.
Sort item set I by increasing si .
Partition set I into H := m/LB subsets I j of cardinality LB according to the sorting.
for j ← H downto 1 do
for i ← LB downto 1 do
Assign item i in set I j to truck LB− i + 1.
end for
end for
capacity of pallet space ifweight capacity is used to the limit, and vice versa. Therefore,
we can define a desired average density for an ideal load of a truck, namely the ratio
optavgρ =∑W/B. Cl∑early, a loading pattern Pt of a truck t with an average density
avgrt := j∈P w j/ j∈P b j close to optavgρ and total weight close to the capacityt t
W also fills the available pallet space close to the limit B, and vice versa.
Based on this simple observation, we introduce two heuristics D and E. In contrast
to heuristics A, B, and C, they both consider trucks one after the other and for each
considered truck t they add the item yielding a new average density avgrt as close as
possible to the target value optavgρ . Of course, the item also has to fit into the truck at
hand. Ties are broken by choosing the item with the largest weight, because smaller
items can be expected to fit more easily in later iterations.
Heuristics D and E differ from each other only by the weight measure for the initial
sorting step. Note that the sorting only determines the first item put into every truck.
Heuristic D sorts by the surrogate weight si ensuring that “large” items are assigned
first and will not give rise to trucks with low utilization toward the end of the packing
procedure. On the contrary, heuristic E focuses on outliers with an unusual density
that are potentially hard to assign. Therefore, items are sorted in decreasing order of
unit weight ρi . By the same rationale also the reverse ordering could be a reasonable
choice, but for our test data, pretests showed that this ordering is less effective.
Algorithm 6 Heuristic D (E)
Sort items I by decreasing si (ρi ).
Let Pt ← ∅ be the loading of all trucks t .
t ← 0
while I = ∅ do
t ← t + 1
Take the first i from I and insert i into Pt .
Set avgrt = ρi and remove i from I .
while items exist tha{t ∣∣fit int∑o Pt do ∣ }′ ← ∣∣w +i argmin ∈ i j∈P w j
∣
i I bi+
∑ t − optavg ∣
∈ ρ
: i fits into Pt
j P ∣t b j
Insert i ′ into Pt and remove i ′ from I .
end while
end while
Heuristics D and E could be immediately extended to consider all trucks instead of
only the current truck t for inserting items. In that case, the computation of i ′ would
have to be extended to taking the argmin over all currently open trucks, which means
123
Bin packing with lexicographic objectives for loading… 401
that an item is inserted into a truck where the minimal deviation from optavgρ can be
realized. Indeed,we also implemented this extensionwith the initialization that the first
LB items (according to the given ordering) are packed on LB trucks. However, since
improvements were only marginal and occurred only for a small subset of instances,
we decided to stick to the simpler standard version described above.
5.4 Multi-class heuristic scheme of splitting-forbidden policy
All heuristics described in the previous sections focus on creating good patterns utiliz-
ing both capacity dimensions, but they take neither itemsof different product categories
packed into different compartments of a truck nor item fragmentation into account,
while the latter is considered in the following Sect. 5.5. Accordingly, we now present
a heuristic scheme which is based on the single-class heuristics presented before.
These are embedded into a more complicated algorithmic framework consisting of
various decomposition and re-merging steps. Since the running times of the single-
class heuristics are rather low, we perform the task of solving a single-class problem
for a certain subset of item I ⊆ I as a subroutine by running all nine heuristics from
Sects. 5.1, 5.2, and 5.3 and taking the best solution found. More precisely, we run
the Business Today algorithm, FFD, BFD, WFD, and Heuristics A to E. The result
(= number of trucks) derived by this combined single-class heuristic is denoted by
zheu(I). Additionally, this combined heuristic is executed with a given starting solu-
tion of prepacked trucks, i.e., some trucks have reduced residual capacities. We refrain
from listing all the details of adapting the single-class heuristics to this situation.
In Sect. 3, the lower boundsLB,LBS,LBC,F, andLBF for the corresponding subsets
of items are introduced. Applying a single-class heuristic only for standard items and
then separately only for refrigerated items yielding heuristic solution values zSheu and
zC,Fheu , respectively, we can conclude the following: If z
1.
sep := zS C,Fheu + zheu = LB, then
we have reached an optimal solution w.r.t. the objectives of Stages 1. and 2. with
z1. = z1. and z4.sep = 0.
Otherwise, if zS + zC,Fheu heu > LB, we cannot guarantee optimality of the merged
solution without mixed trucks. In this case, it makes sense to gradually introduce
mixed trucks while trying to reduce the total number of trucks. As already used in
Sect. 4, constraint (4c), the lower bound for mixed trucks (z4.) is given by LBmixed =
LBS + LBC,F − LB for solutions that are optimal w.r.t. Stages 1. to 3. Therefore,
LBmixed = 0, if LBS + LBC,F = LB and LBmixed > 0, otherwise.
The heuristic scheme striving for a good solution of the lexicographic optimization
problem defined by Stages 1.–4. with splitting forbidden works in three phases which
are described in Algorithm 7. Phase 1 builds up a solution starting with frozen prod-
ucts. After packing I F by the combined single-class heuristic (following the Stage 4.
objective), the cooled items are added which might require additional trucks (Stage 3.
objective). Then a separate solution for the standard item set I S is determined. Taking
the union of the two sets of trucks gives a first solution, where standard and refriger-
ated items are packed in separate trucks (Stage 2. objective). If the resulting number
of trucks zbest equals the overall lower bound LB we stop (STOP 1), since we have
found a solution which is optimal w.r.t. Stages 1. and 2.
123
402 K. Heßler et al.
Otherwise, we try to improve the currently best solution in Phase 2: Therefore,
we allow mixed trucks and pack standard products also into refrigerated trucks. To
reach a better starting position for adding also large standard items to the refrigerated
trucks given from Phase 1, but keeping the number of mixed trucks small, the load
of the refrigerated trucks is regrouped at the beginning of Phase 2 with the goal of
obtaining some refrigerated trucks with a low load and others which are almost fully
packed with cooled products. This is done by subprocedure Regroup, which tries to
empty the least loaded refrigerated truck by moving its items (in decreasing order of
surrogate weight) to other refrigerated trucks selected by a BF strategy. If the number
of frozen products is small, we try to keep them together in the regrouping in the
spirit of the Stage 3. objective. Therefore, all frozen products contained in the current
truck are considered as a single product and moved to a new truck together. Only
if this artificial product does not fit, the frozen products are reassigned individually.
This regrouping is applied to all trucks in an increasing order of surrogate load. Then
the standard items I S are added to the regrouped refrigerated trucks by the combined
single-class heuristic. In this way, we aim to find a packing with a lower number of
trucks (Stage 1.), but without increasing the number of refrigerated trucks (Stage 2.).
Again, we stop if the new solution matches the lower bound LBI (STOP 1).
A further reduction in the total number of trucks is sought in Phase 3 at the cost of
increasing the number of refrigerated trucks. Again we try to improve the possibility
of adding standard products to refrigerated trucks. Therefore, we take the refriger-
ated truck with lowest load w.r.t. the surrogate weight and split its content on two
empty trucks, thereby incrementing the number of refrigerated trucks by one. The
splitting is performed in a balanced way by assigning the items by a WFD strategy
(w.r.t. surrogate weights). Again, all frozen items are treated as one product, if the
truck contains both frozen and cooled products. Then the standard items are again
added by the single-class heuristic. If the total number of trucks reaches the lower
bound LB we stop the procedure. Otherwise, we unpack all standard items again and
iterate, taking the refrigerated truck with lowest load that was not split before. If all
refrigerated trucks given at the beginning of Phase 3 were split, another iteration is
started permitting a second split operation for each refrigerated truck given at the end
of the first iteration. Further iterations along this rule are possible, until at some point
the number of refrigerated trucks exceeds the lower bound for all items (STOP 2).
In this case, we also run the single-class heuristic for all items I to reach a possible
improvement in the Stage 1. objective.
5.5 Multi-class heuristic scheme of splitting-allowed policy
If the multi-class heuristic of Sect. 5.4 reaches a solution where all lower bounds for
the objectives of Stages 1.–4. are reached, obviously the result cannot be improved by
splitting products. However, if this is not the case, item fragmentation offers potential
for improvements.
In the following, we consider the two different splitting objectives introduced in
the Introduction.
123
Bin packing with lexicographic objectives for loading… 403
Algorithm 7Multi-class heuristic
Compute LB.
Phase 1: {pack refrigerated and standard items separately}
Compute zFheu
Compute z Crefrig ← zheu starting from the packing implied by zFheu
Compute zSheu {for empty trucks}
z Sbest ← zrefrig + zheu {current best solution}
if zbest = LB then
STOP 1.
end if
Phase 2: {reshuffle the refrigerated items and then add standard items}
Regroup(all zrefrig refrigerated trucks)
Compute zSheu starting from the packing of the zrefrig refrigerated trucks returned by Regroup.
zbest ← min{zbest, zS
= heu
}
if zbest LB then
STOP 1.
end if
Phase 3: {Iteration: expand the number of refrigerated trucks by distributing the load of one truck on
two trucks and add standard items}
Remove all standard items IS from the zrefrig refrigerated trucks returned by Regroup.
repeat
zcurrent ← zrefrig
for all zcurrent refrigerated trucks t opened so far in increasing order of load w.r.t. surrogate weights
do
Open a new (empty) truck zrefrig + 1
zrefrig ← zrefrig + 1
Take all (refrigerated) items currently loaded on truck t and pack them on the two trucks t and
zrefrig by a WFD strategy. {gives a balanced bipartition}
Compute zSheu starting from the current packing of the zrefrig refrigerated trucks.
zbest ← min{z Sbest, z
= heu
}
if zbest LB then
STOP 1.
end if
if zrefrig ≥ LB then
Compute zheu {for empty trucks}
zbest ← min{zbest, zheu}
STOP 2.
end if
Remove all standard items IS from the trucks
end for
until false
Subprocedure Regroup(P1, . . . , PT )
Sort the T trucks in increasing order of load w.r.t. surrogate weights
for t = 1 to T do
for all items i in Pt in decreasing order of surrogate weights do
Try to pack item i in trucks {Pt+1, . . . , PT } by a BF strategy (w.r.t. surrogate weights)
end for
end for
123
404 K. Heßler et al.
Algorithm 8Multi-class heuristic: Stage 5a., minimizing the number of splits
Compute LB1
Execute Algorithm Multi-class heuristic returning T := zbest trucks with loads P1, . . . , PT
Sort the T trucks in increasing order of load w.r.t. surrogate weights
t ← 1
repeat
for all items i in Pt in decreasing order of surrogate weights do
Try to pack item i into another truck by a BF strategy (w.r.t. surrogate weights)
end for
while Pt = ∅ do
Let i ′ be the item in Pt with largest surrogate weight
{find the truck t ′ where the largest number of pallets of i ′ can be added}
h′ ← maxτ { : · +∑ ∑h h wi ′/bi ′ j∈P w j ≤ W , h+ j∈P b j ≤ B, τ ∈ {1, . . . , T }\{t}} attainedτ τ
for t ′
if h′ = 0 then
{Truck t cannot be emptied}
Return the solution with zbest trucks (as given at the start of the current iteration of repeat)
STOP.
end if
Move h′ pallets of product i ′ from Pt to Pt ′
end while
Remove Pt
zbest ← zbest − 1
if zbest = LBI1 then
Return current solution with zbest trucks
STOP.
end if
t ← t + 1
until false
Algorithm 9Multi-class heuristic: Stage 5b., minimizing the number of split products
Compute LB , LBS , LBC,F and LBmixed1 1 1 1
Sort all items i ∈ I in decreasing order of bi
i ← 0
repeat
i ← i + 1
Split item i into bi separate items
Execute Algorithm Multi-class heuristic returning zbest
until all lower bounds LB , LBS , LBC,F1 1 1 and LB
mixed
1 are reached or bi+1 = 1 or i = m
Return zbest
5.5.1 Stage 5a.: Minimizing the number of splits
In this setting, it is not a-priori clear which items should be split and in which way
to gain the largest improvement in the solution. We have chosen to incorporate item
splitting as a post-processing step applied to a solution derived from the multi-class
heuristic of Sect. 5.4. In every iteration of the main loop of our Algorithm 8, we try
to empty the truck with lowest surrogate load and thus reduce the total number of
trucks by one. If this turns out to be impossible, the procedure is stopped. Otherwise
we proceed to the next iteration, unless we have reached a solution with LB1 trucks,
which proves optimality of objective 1. and also lets us stop the procedure.
123
Bin packing with lexicographic objectives for loading… 405
Every iteration for the truck t with minimal surrogate weight consists of two parts:
At first (for-loop) we try to further reduce the load of truck t by moving items (without
splitting them) to other trucks by a BF strategy. Then (in the while-loop) we iteratively
take the largest (w.r.t. surrogate weight) remaining item i ′ in truck t and split it, i.e.,
we pack the largest possible fractional part of it, expressed as number of pallets, to
one of the other trucks. Formally, the largest pallet number h′ is calculated, such that
h′ pallets out of the bi ′ pallets constituting i ′ can be loaded on some truck t ′. Ties
among trucks are broken by a BF rule. The remaining part of item i ′ consisting of
bi ′ − h′ pallets is treated like an individual item in t . By moving the largest possible
number of pallets, it can be expected that the total number of splits remains small.
If no single pallet can be moved from truck t (i.e., h′ = 0), the whole procedure is
stopped. Otherwise, truck t is completely empty and can be removed.
5.5.2 Stage 5b.: Minimizing the number of split products
In this case, it does not matter whether a large or small item i is split and whether i
is split into two fragments or the maximum number of bi fragments. It is intuitively
clear that the largest potential for improvement is given by splitting large products
completely into separate pallets. Therefore, in our Algorithm 9 we iterate over all
items in decreasing order of bi . Every considered item is split into separate pallets
and then the multi-class heuristic from Sect. 5.4 is executed. The iterative process is
stopped in any of the following three cases: (1) the multi-class heuristic stops with a
solutionmatching all lower bounds for the objectives of Stages 1.–4. Sincewe consider
split products, we can only utilize the volume based lower bound LB1; (2) all products
consisting of more than one pallet were split; (3) all products were considered and
split.
6 Computational results
In this section we will report computational results for all algorithms described before.
The experiments are based on real-world instances and on more difficult instances
generated from these by reducing their data to more difficult item sets (see Sect. 6.2).
We first report in Sect. 6.3 results for the heuristic approaches described above in
Sect. 5. To analyze the performance of the algorithm we compare the heuristic with
the exact solutions in detail. Then we will illustrate the performance of the exact
BaP algorithm in Sect. 6.4. Furthermore, we also analyze in that section the impact of
adding the heuristic solutions as columns to the initial RMP.
6.1 Details of the implementation
All heuristic algorithms presented in Sect. 5 are implemented and tested in Python
3.3.7 on a standard PC equipped with an Intel® Core™ i5-3210M processor with 2.5
GHz and 4GB of RAM.Note that the heuristics are also used in the daily planning task
of our industrial partner. For this application they were originally implemented within
123
406 K. Heßler et al.
the SAP ERP system of the company in the SAP-internal programming language
ABAP. However, for test purposes we re-implemented the heuristics in Python.
The BaP algorithm described in Sect. 4 is implemented in C++ and compiled in
release mode into a single-thread code underMSVisual Studio 2015. The experiments
are conducted on a standard PC with an Intel® Core™ i7-5930k processor clocked at
3.5GHzand64GBofRAM.TheRMP is solved at each column-generation iteration by
means of CPLEX 12.9. Moreover, CPLEX is called after the solution of each branch-
and-bound node as a primal MIP-based heuristic solver using the so far generated
columns. CPLEX’s default values are kept for all parameters. The time limit to solve
each stage is set to 10min (600s). In case a stage cannot be solved within the time
limit, the computation is stopped and following stages are not considered.
6.2 Benchmark instances
We consider 80 real-world instances with 35 to 430 items provided by our partner
from the European food and beverage industry. The cardinality bound of each truck is
33 pallets (a common industry standard), and the weight capacity is 22.8 or 24.5 tons.
The weight of each item is rounded up with an accuracy of 10kg. Preliminary tests
show that both constraints, weight and cardinality, can become active, i.e., there is no
clear dominance of one of the two dimensions. Not all instances contain all types of
products; especially, frozen products often appear in rather small quantities or they
may even be completely absent. A detailed summary of our test instances is found in
Table 6.
During the computational study it turned out that for most of the instances the
optimal solutions for Stages 1.–4. do not require any splitting, and thus, the objective
of Stage 5. would be optimized by default. The reason for this behavior is that the
instances also contain rather small items which fill up trucks without being split.
Therefore,wedistilledmore difficult new instances from the given real-world instances
avoiding this effect in the following way. The 80 real-world instances are divided into
10 groups each with 8 instances. For each group, we selected 5, 10 or 15 items with the
highest weight and/or the highest number of used pallets of each instance forming a
new instance, respectively. In total, we generated 30 new instances with up to 80, 160
Table 6 Overview of benchmark instances
Instance type Real-world Generated
Number of instances 80 30
Average number of items 144 153.9
Average weight of items (in 10kg) 93.7 114.6
Average pallet number of items 3.8 6.7
Number of instances with standard products 80 30
Number of instances with cooled products 73 30
Number of instances with frozen products 31 16
123
Bin packing with lexicographic objectives for loading… 407
Table 7 Results of the heuristic approach
Instance type Real-world Generated
Number of instances 80 30
Business today logic achieved LB 21 0
Heuristics outperform business today logic 59 30
Heuristics achieve LB without split 56 3
Splitting improved heuristic solution 18 25
Improvements led to reaching LB 13 21
No improvement by splitting 6 2
Heuristic runtime < 1s 46 3
Heuristic runtime 1–10s 27 8
Heuristic runtime 10–30s 4 7
Heuristic runtime >30s 3 12
Average number of trucks business today 23.1 45.8
Average number of trucks heuristic unsplit 22.2 42.2
Average number of trucks heuristic split 22.1 40.6
or 240 items, respectively. All instances are available on the website http://logistik.
bwl.uni-mainz.de/benchmarks.php.
6.3 Results of the heuristic approach
In this section, we report results of the heuristic approach. Table 7 shows the key results
for the pure heuristic approach. For 56 out of the 80 real-world instances, all lower
bounds for objectives 1.–4. are already achieved without splitting. The 24 remaining
instances provide at least a theoretical improvement potential, which is exploited in
18 cases. For 13 of them, even the lower bounds for objectives 1.–4. are achieved if
items are allowed to be split. While for the real-world instances exactly 70% could
be solved to the lower bounds for objectives 1.–4., this was possible only for 10% (3
out of 30) of the generated instances, all without splitting.
However, the share of solutions that could be improved by applying splitting is far
higher (25 out of 27) and the same is valid for the number of instances where that
improvements even led to the lower bounds for objectives 1.–4. This higher improve-
ment is not surprising, as the average pallet size of items is more than 75% larger for
generated instances, and thus, the effect of splitting items into separate pallets is much
stronger. The higher difficulty of generated instances is also reflected in the running
times of the heuristics.
For none of the 110 instances, the original Business Today logic outperformed the
heuristic approach, but for 89 instances, the heuristics performed better. For the other
21 (all real-world) instances, both the heuristics and the Business Today logic reached
the lower bounds.
123
408 K. Heßler et al.
For a further performance analysis, we compare the objective values of the heuristic
approach with the optimal objective values computed by the BaP approach. Detailed
results are found in Table 8. The table entries have the following meaning:
#opt: number of instances solved to proven optimality at the specific stage;
z = z∗H : number of instances in which the heuristic approach finds the optimal
solution; instances with non-optimal heuristic solutions in former stages
are not considered;
zH > z∗: number of instances in which the heuristic approach does not find the
optimal solution; instanceswith non-optimal heuristic solutions in former
stages are not considered;
gapH : average gap between heuristic and exact solution, we use the gap z
∗
H − z
instead of the relative gap because the optimal solution can be z∗ = 0 in
Stages 4.–5.; recall that solution values for Stages 1.–4. represent number
of trucks, but split parameters for Stage 5.;
#implicitH : number of instances for which the heuristic and optimal solution implic-
itly coincide, or where the current stage is not active (e.g., no Stage 3. for
instances without any frozen items);
	-z = z∗H : total number of instances in which the heuristic approach finds the
optimal solution up to the specific stage: (	-zH = z∗) := (z∗ H =z )+ (#implicitH );
	-#opt: number of instances solved to proven optimality at the current stage; in
contrast to #opt, implicitly optimally solved instances are also included.
For a better understanding, we describe the entries in the second row of Table 8
in detail. At Stage 2., the branch-and-price algorithm solves 64 instances to prove
optimality. For 60 (3) instances, the heuristic approach could (not) find the optimal
solution. For one instance, we cannot compare the heuristic and exact approach at
Stage 2. because the solution at Stage 1. differs for this instance. For 6 instances
without any refrigerated items, the heuristic approach finds the optimal solution at
Stage 1. so that Stage 2. is solved implicitly. Including instances without refrigerated
products, the heuristic and exact solution coincides for 66 instances in total.
For the splitting-forbidden policy, the heuristic solution is optimal for 58+6 of
68+18 instances. Interestingly, in most of the cases, the heuristic approach fails to
find the optimal solution at the first stage. Especially for the generated instances, only
15 of 30 instances are solved to optimality. For the remaining 12+12 instances, where
no optimal solutions are achieved by the BaP algorithm either, the heuristic approach
fails to reach the lower bounds in 7+9 cases at the first stage. However, the gaps are
rather small. Only for 0+2 instances, absolute gaps larger than 1 truck occur. For the
splitting-allowed policy, the heuristic approach performs well with 67+24 of 67+25
instances solved optimally up to Stage 4. The absolute deviance gapH is low up to
Stage 4. with a maximum of 0.2, but the values are big for Stage 5. With 6/6+4/5
of 62/63+7/8 non-optimal instances, the heuristics fail for most of the instances at
Stage 5.
123
Bin packing with lexicographic objectives for loading… 409
Table 8 Comparison between the heuristic and the exact solution
Splitting Class Stage #opt z ∗ ∗ ∗H = z zH > z gapH #implicitH 	-zH = z 	-#opt
Forbidden Real-world 1 76 71 5 0.1 0 71 76
2 64 60 3 0.0 6 66 71
3 26 24 1 0.0 41 65 71
4 61 52 4 0.3 6 58 68
Generated 1 30 15 15 0.6 0 15 30
2 22 9 5 0.9 0 9 22
3 11 4 0 0.0 5 9 22
4 18 6 2 1.3 0 6 18
Allowed Real-world 1 73 73 0 0.0 0 73 73
2 64 64 0 0.0 7 71 71
3 27 27 0 0.0 44 71 71
4 60 60 0 0.0 7 67 67
5a. 5 62 50 6 98.3 0 50 62
5b. 5 63 48 6 3.9 0 48 63
Generated 1 28 28 0 0.0 0 28 28
2 27 25 2 0.2 0 25 27
3 15 15 0 0.0 10 25 27
4 25 24 0 0.0 0 24 25
5a. 5 7 3 4 80.8 0 3 7
5b. 5 8 3 5 32.2 0 3 8
Total 767 661 58 9.5 126 787 907
6.4 Results of the branch-and-price algorithm
In this section, we report the results of our BaP algorithm. In general, reaching a stage
of the lexicographic optimization task triggers the execution of a BaP algorithm solv-
ing the respective model (1)–(4), and possibly (5a)–(5b) or (5c)–(5d). However, for
some instances, not all stages become active, e.g., if there are no frozen products in
the instance or if a stage is solved implicitly during the preceding stage. Therefore,
the total number of instances per stage to be reported in the computational experi-
ments may be different for every stage. Moreover, the different BaP algorithms of the
stages may have different success rates and thus will lead to a different number of
instances remaining for the successive stages. This makes the comparison of different
algorithmic approaches a delicate task. The following analyses may, therefore, seem
somewhat less transparent, but our focus is on the correct interpretation of the results
we obtained.
The construction of the initial RMP works as follows. As the first stage is a vector
packing problem without additional constraints, we start with the same initial RMP
as described in (Heßler et al. 2018) by adding unit vectors, columns with only one
non-negative coefficient a pi = ui , and 200 additional columns resulting from variants
of the FF and BF heuristics. At Stage 2., we add other 200 columns resulting from
123
410 K. Heßler et al.
the FF and BF heuristics that first assign items to bins that already contain the same
product type. Moreover, the same FF and BF variants used in Stage 1. are performed
on restricted item sets by considering standard or refrigerated products separately.
Analogously, Stage 3. applies the FF and BF variants for cooled or frozen products
separately. At Stage 4.–5., no additional columns are added initially to the RMPs.
At all stages, after solving the linear relaxation of a branch-and-boundnode,CPLEX
is invoked as a primal heuristic using the integer model and all patterns that have been
generated up to this point. If the integrality gap is closed with the CPLEX solution, the
branch-and-price is immediately terminated (providing a provably optimal solution).
To allow for a fair comparison of computation times, CPLEX is run in single-thread
mode and its computation times are counted for the overall computation time and time
limit.
For each stage, the computation time is restricted to a maximum of 10min (600s).
If a stage cannot be solved within the time limit, we cannot solve the instance exactly.
Therefore, the computation is stopped at this stage and the following stages are not
considered. If an instance has no frozen or no refrigerated products at all, Stage 3. or
Stages 2.–4. are skipped, respectively.
At first, the BaP algorithm is tested employing the results of the heuristic approach,
i.e., the corresponding columns are added to the initial RMP. We refer to this variant
as base. To analyze the impact of the heuristic solution, we compare the base
variant to a variant without using the heuristic solution. Moreover, the impact of
the lower bounds enforced by constraints (2c), (3c), and (4c), and the graph reduction
presented in Sect. 4.5 are tested.We refer to these variants aswithout heuristic
solution, without lb, and without reduced graph, respectively. For
the base(long) variant, the computation time is extended to a maximum of 20min
(1200s). The results are summarized in Table 9. The table entries have the following
meaning:
Class: class of instances; real-world or self-generated; for details see Sect. 6.2;
Splitting: allowed or forbidden; in case of splitting-allowed, either the number of
splits (objective 5a.) or the number of split products (objective 5b.) is
minimized, see Sect. 4.1;
#inst: number of active instances;
#inst_cons: number of active instances considered at the current stage; instances that
are not solved to proven optimality in a previous stage are not considered;
#opt: number of instances (out of #inst_cons) solved to proven optimality at the
specific stage within 10min (600s);
#implicit: number of instances forwhich the current stage is already implicitly solved
by the result of a previous stage, or where the current stage is not active
(e.g., at Stage 3. for instances without any frozen items);
	-#opt: number of instances solved to proven optimality at the current stage: 	-
#opt:= #opt+#implicit
T̄ : average computation time in seconds over #inst_cons instances; unsolved
instances are taken into account with the time limit of 10min (600s);
123
Bin packing with lexicographic objectives for loading… 411
123
∑
Table 9 Results of the exact BaP-based approach The largest #opt and -#opt entries are bold, respectively (not considering base(long))
Splitting Class Stage #inst Base Without heuristic solution
#inst_cons #opt #implicit 	-#opt T̄ T̄L P Gap #inst_cons #opt #implicit 	-#opt T̄ T̄L P Gap
Forbidden Real-world 1 80 80 76 0 76 65.7 30.1 0.1 80 77 0 77 59.1 32.6 0.0
2 73 69 64 7 71 79.8 21.3 0.9 70 62 7 69 99.9 21.3 1.6
3 31 26 26 45 71 61.4 40.0 0.0 25 25 44 69 58.3 38.0 0.0
4 73 64 61 7 68 65.3 32.6 0.1 62 59 7 66 69.6 23.4 0.0
Generated 1 30 30 30 0 30 47.2 40.2 0.0 30 30 0 30 49.5 39.9 0.0
2 30 30 22 0 22 192.4 33.7 3.3 30 23 0 23 186.4 33.1 2.5
3 16 11 11 11 22 22.3 13.1 0.0 12 12 11 23 45.6 16.6 0.0
4 30 22 18 0 18 132.6 18.0 0.2 23 19 0 19 130.9 18.8 0.2
Allowed Real-world 1 80 80 73 0 73 131.4 107.9 1.4 80 71 0 71 139.7 106.5 1.4
2 73 66 64 7 71 114.8 75.8 0.5 64 61 7 68 117.8 75.7 1.2
3 31 27 27 44 71 170.5 139.5 0.0 25 21 43 64 227.2 137.9 0.4
4 73 64 60 7 67 140.3 95.5 0.2 57 52 7 59 144.6 81.8 0.1
5a. 5 80 67 62 0 62 157.3 91.2 5.8 59 56 0 56 140.4 79.1 8.4
5b. 5 80 67 63 0 63 148.3 88.2 1.4 59 56 0 56 139.1 87.1 4.0
Generated 1 30 30 28 0 28 181.6 159.2 5.4 30 22 0 22 226.9 175.9 9.0
2 30 28 27 0 27 192.5 143.1 0.8 22 11 0 11 355.2 139.2 10.2
3 16 15 15 12 27 240.3 201.6 0.0 6 5 5 10 231.1 121.0 0.2
4 30 27 25 0 25 229.4 175.9 0.4 10 10 0 10 124.2 112.8 0.0
5a. 5 80 25 7 0 7 465.8 317.3 347.3 10 5 0 5 360.3 249.2 177.6
5b. 5 80 25 8 0 8 459.2 320.5 32.0 10 5 0 5 399.1 251.9 39.1
Total 1046 853 767 140 907 144.0 91.2 12.3 764 682 131 813 133.6 73.0 5.0
412 K. Heßler et al.
123
Table 9 continued
Splitting Class Stage #inst Without lb Without reduced graph Base(long)
#inst_cons #opt #implicit 	-#opt T̄ T̄L P Gap #inst_cons #opt #implicit 	-#opt T̄ T̄L P Gap 	-#opt T̄
Forbidden Real-world 1 80 80 75 0 75 91.4 58.9 0.1 77 110.6
2 73 68 63 7 70 136.2 88.8 0.6 71 147.9
3 31 26 25 44 69 101.9 68.4 0.3 71 76.9
4 73 62 38 7 45 261.3 34.5 0.4 68 102.5
Generated 1 30 30 30 0 30 80.2 73.6 0.0 30 77.1
2 30 30 23 0 23 187.2 79.9 4.5 24 318.4
3 16 11 11 12 23 28.0 20.0 0.0 24 54.9
4 30 23 13 0 13 283.4 29.3 0.5 20 266.9
Allowed Real-world 1 80 80 73 0 73 131.3 107.9 1.4 80 63 0 63 235.8 225.0 6.5 75 172.9
2 73 66 61 7 68 179.8 147.0 0.9 56 55 7 62 94.3 57.3 0.1 74 129.9
3 31 24 19 44 63 230.6 213.5 0.5 23 22 39 61 141.3 119.6 0.2 74 205.5
4 73 56 34 7 41 285.0 61.1 0.4 54 51 7 58 107.9 69.5 0.2 70 196.1
5a. 5 80 41 38 0 38 140.9 68.7 7.3 58 54 0 54 137.2 74.2 12.6 63 240.9
5b. 5 80 41 39 0 39 122.4 64.3 1.7 58 54 0 54 121.8 58.9 1.6 63 226.6
Generated 1 30 30 29 0 29 169.8 146.0 3.0 30 19 0 19 289.4 282.3 19.8 29 193.7
2 30 29 24 0 24 312.1 276.1 2.2 19 17 0 17 197.6 162.3 1.9 28 206.3
3 16 13 11 11 22 280.2 245.7 0.4 9 9 8 17 201.0 172.4 0.0 28 237.8
4 30 22 13 0 13 339.3 153.2 0.6 17 16 0 16 190.2 157.6 0.2 25 303.6
5a. 5 80 13 3 0 3 497.6 366.9 275.7 16 6 0 6 413.2 382.4 336.9 8 875.5
5b. 5 80 13 3 0 3 498.0 366.9 23.5 16 6 0 6 441.8 384.9 19.1 8 865.5
Total 1046 758 625 139 764 188.8 106.9 6.4 436 372 61 433 182.1 145.6 17.6 930 216.1
Bin packing with lexicographic objectives for loading… 413
T̄L P : average computation time of the linear relaxation in seconds; unsolved
linear relaxations are taken into account with the time limit of 10min
(600s);
Gap: average gap between the upper and lower bounds; we use the gap UB −
LB instead of the relative gap because the objective value can be zero at
Stages 4.–5.
We summarize and interpret the results as follows: For the splitting-forbidden pol-
icy, 68 of 80 real-world and 18 of 30 self-generated instances are solved to optimality.
In particular, the algorithm performs well at Stage 3. with an average computation
time of around 1min. In comparison, the splitting-allowed policy is more difficult
than splitting-forbidden. The performance at Stage 1. is similar for both policies with
101 solved instances (splitting-allowed) instead of 106 (splitting-forbidden). Up to
Stage 4., 67 of the 80 real-world and 25 of the 30 generated instances are solved
which is (−1) + 3 instances more compared to the splitting-forbidden policy. The
performance of the algorithm at Stage 5., where 62/63+7/8 instances are solved, is
almost the same for both objectives 5a. and 5b. with similar average solution time. As
can be expected, Stage 5. is particularly difficult for the generated instances. Espe-
cially, the average deviation (Gap) at Stage 5a. is very high because in many cases the
root node cannot be solved or the solution of the preceding stage is poor.
When thebase algorithm is stopped after solving the root node, only four instances
less are solved to optimality. This results from the strong linear relaxation of the model
in all stages, the tight upper bounds computed by the heuristic approach, and the
effectiveness of the MIP solver.
We also analyze the solution quality for instances not solved within the time limit:
For the splitting-forbidden policy, the base algorithm cannot solve the root node of
the branch-and-bound tree in 2 cases. Moreover, the absolute gap UB − LB is 1 for
all non-solved instances at Stages 1. and 4., while the average gap is 12.9 for all non-
solved instances at Stage 2. Similar observations can be made for the splitting-allowed
policy: At Stages 1. and 4., the absolute gap UB − LB is almost always 1, while at
Stages 2. and 5., the average gap is 8 and> 50, respectively. For the splitting-allowed
policy, approximately half of the non-solved instances (18 instances) are so difficult
for our approach that the root node remained unsolved in one of the stages.
To analyze the impact of the heuristic solution, we compare the variants base and
without heuristic solution. For the splitting-forbidden policy, the results
hardly change when the initial columns from the heuristic are omitted. In total, only
one instance less can be solved and the average running times differ by less than 5s.
Therefore, the use of the heuristic solution provides only a small advantage for the
splitting-forbidden policy. In contrast, for the splitting-allowed policy, the effect of
adding the heuristic solution is more significant, as it helps to solve 6/7+2/3 additional
instances, respectively.
Adding the additional constraints (2c), (3c), and (4c) to ensure lower bounds on the
number of refrigerated, frozen, and mixed trucks, respectively, has a strong impact on
the performance of theBaP algorithm.Without adding these lower bounds, only 45+13
instances of the splitting-forbidden policy and 38/39+3 instances of the splitting-
allowed policy can be solved. In total, around one-third of the instances cannot be
123
414 K. Heßler et al.
solved without these bounds. Moreover, the running time increases significantly for
all stages and problem variants.
For the splitting-allowed policy, using a reduced graph as described in Sect. 4.5
has a positive impact for the Stages 1.–4. Already at Stage 1., 10+9 instances less are
solved if the graph reduction is omitted. Overall, 8/9+1/2 instances less are solved.
When the maximal computation time is extended to 20min (instead of 10min),
the number of solved instances slightly increases. In total, 68+20 instances of the
splitting-forbidden policy and 63+8 instances of the splitting-allowed policy are solved
to optimality which is four instances more compared to the time limit of 10min.
7 Conclusion
Packing pallets of products from industrial producers into trucks for shipment to
wholesalers is an important daily task in supply chain management. Reducing the
number of trucks, even if only by one, or rearranging the package layout to diminish the
number of the more costly trucks carrying cooled or frozen products, has a significant
impact on costs. It also helps to reduce exhaust emissions of trucks, since the supply
operation is usually performed daily or several times a week. Thus, the effort spent
on optimizing the packing operation yields savings that will add up over a year to
numbers of considerable economic relevance.
In this contribution, we consider a real-word packing problem where products
should be packed into trucks such that a five-level lexicographic objective function is
minimized. Feasibility is defined by a weight and a volume (=number of pallets) con-
straint for every truck. This special variant of a multi-objective optimization problem
considers the total number of required trucks as main objective dominating all other
goals due to the high cost of labor. However, after fixing the overall number of trucks
(and thus the number of required personal) secondary objectives come into play, which
concern the costly operations of cooling and freezing devices of a truck. Finally, for
practical handling it is clearly convenient for the customer to receive all pallets carrying
the same product in the same truck. But if the total number of trucks could be reduced,
the customer will agree to a splitting of products onto several trucks. Nevertheless,
such a splitting should happen as rarely as possible, which opens the question how to
measure the inconvenience of splitting. We believe that such a lexicographic setting
has not be considered for one- or two-dimensional bin-packing problems before.
The first part of this paper gives a branch-and-price framework for computing
exact solutions of our problem. While the upper-level problem of minimizing the
number of trucks can be modeled as a two-dimensional vector packing problem, with
a special structure in one dimension, the lexicographic objective requires five iterative
steps of successive optimization problems, in each of which columns are generated
by solving appropriate instances of a shortest path problem with resource constraints
(SPPRC). It is amajor contributionof the paper to put thefivedifferent problems arising
for different levels into a uniform framework of column generation. Furthermore,
advanced concepts of stabilization and some acceleration techniques are employed.
In the secondpart,we describe the heuristic solutionmethod previously employed in
practice and then develop a number of new constructive heuristics for solving a single
123
Bin packing with lexicographic objectives for loading… 415
level of the packing problem. These try to balance the two constraints and generate
solutions with a favorable mix of weight and volume. Then, the single-level heuristics
are integrated into a more complex heuristic framework for building solutions of high
quality with respect to the multi-level lexicographic objective function.
Computational experiments for real-world benchmark instances as well as struc-
turally more difficult instances extracted from these show that the branch-and-price
algorithm is highly effective in computing optimal solutions.Within 10min of compu-
tation time it reaches proven optimality for 68 out of 80 real-world scenarios without
splitting. Allowing splitting leads to more difficult problems, but still 62 of 80 are
solved to optimality.
It also turns out that the heuristic framework performsmuch better than the approach
previously applied in practice andmatches the optimal solutions in 86%of all subprob-
lems. Note that it is also very helpful to use the heuristic solution as a starting column
for the branch-and-price algorithm. Based on this evaluation, our heuristic framework
has been successfully incorporated into the SAP ERP system of our industrial partner
and is currently used for the daily planning of direct shipments.
In the future, it would be interesting to extend our single-source single-sink shipping
problem to a more complex supply network serving multiple customers. This would
open up the possibility of delivering less-than-truckload amounts to one customer and
using the residual capacity of a truck for serving a second (or third) customer, if the
routing costs support such a decision.
Acknowledgements We would like to thank scc EDV-Beratung AG, Vienna, and its industrial partner for
the fruitful collaboration and for providing all the practical insights. We further want to thank the editors
and reviewers for their valuable advice on improving this work. Ulrich Pferschy was supported by the Field
of Excellence “COLIBRI” at the University of Graz.
Funding Open Access funding enabled and organized by Projekt DEAL.
OpenAccess This article is licensedunder aCreativeCommonsAttribution 4.0 InternationalLicense,which
permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give
appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence,
and indicate if changes were made. The images or other third party material in this article are included
in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If
material is not included in the article’s Creative Commons licence and your intended use is not permitted
by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the
copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
References
Aringhieri R, Duma D, Grosso A, Hosteins P (2018) Simple but effective heuristics for the 2-constraint bin
packing problem. J Heuristics 24(3):345–357
Bansal N, Eliíš M, Khan A (2016) Improved approximation for vector bin packing. In: Proceedings of the
twenty-seventh annual ACM-SIAM symposium on discrete algorithms, vol 3. SIAM, pp 1561–1579
Ben Amor H, Desrosiers J, Valério de Carvalho JM (2006) Dual-optimal inequalities for stabilized column
generation. Oper Res 54(3):454–463
Bertazzi L, Golden B, Wang X (2019) The bin packing problem with item fragmentation: a worst-case
analysis. Discrete Appl Math 261:63–77
Brandão F, Pedroso JP (2016) Bin packing and related problems: general arc-flow formulation with graph
compression. Comput Oper Res 69:56–67
123
416 K. Heßler et al.
Caprara A (1998) Properties of some ILP formulations of a class of partitioning problems. Discrete Appl
Math 87(1–3):11–23
Caprara A, Toth P (2001) Lower bounds and algorithms for the 2-dimensional vector packing problem.
Discrete Appl Math 111(3):231–262
Caprara A, Kellerer H, Pferschy U (2003) Approximation schemes for ordered vector packing problems.
Naval Res Logist 50(1):58–69
Casazza M (2019) New formulations for variable cost and size bin packing problems with item fragmenta-
tion. Optim Lett 13(2):379–398
Casazza M, Ceselli A (2016) Exactly solving packing problems with fragmentation. Comput Oper Res
75:202–213
Christensen HI, Khan A, Pokutta S, Tetali P (2017) Approximation and online algorithms for multidimen-
sional bin packing: a survey. Comput Sci Rev 24:63–79
Coffman EG Jr, Csirik J, Galambos G, Martello S, Vigo D (2013) Bin packing approximation algorithms:
survey and classification. In: Pardalos P, Du DZ, Graham R (eds) Handbook of combinatorial opti-
mization. Springer, New York, pp 455–531
Côté J-F, Iori M (2018) The meet-in-the-middle principle for cutting and packing problems. INFORMS J
Comput 30(4):646–661
Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock
problems. INFORMS J Comput 32(1):101–119
Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: mathematical models and
exact algorithms. Eur J Oper Res 255(1):1–20
Desaulniers G, Desrosiers J, Solomon M (eds) (2005) Column generation. Springer, New York, NY
Gilmore P, Gomory R (1961) A linear programming approach to the cutting-stock problem. Oper Res
9:849–859
Gschwind T, Irnich S (2016) Dual inequalities for stabilized column generation revisited. INFORMS J
Comput 28(1):175–194
Henke T (2018)Multi-compartment vehicle routing problems in the context of glass waste collection. Ph.D.
thesis, Otto-von-Guericke University Magdeburg, Magdeburg, Germany
Heßler K, Gschwind T, Irnich S (2018) Stabilized branch-and-price algorithms for vector packing problems.
Eur J Oper Res 271(2):401–419
Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G,
Desrosiers J, Solomon M (eds) Column generation, chapter 2. Springer, Berlin, pp 33–65
Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin
LeCun B, Mautor T, Quessette F, Weisser M-A (2015) Bin packing with fragmentable items: presentation
and approximations. Theor Comput Sci 602:50–59
Lodi A, Martello S, Vigo D (2002) Recent advances on two-dimensional bin packing problems. Discrete
Appl Math 123(1–3):379–396
Lübbecke M, Desrosiers J (2005) Selected topics in column generation. Oper Res 53(6):1007–1023
Malaguti E, Monaci M, Paronuzzi P, Pferschy U (2019) Integer optimization with penalized fractional
values: the Knapsack case. Eur J Oper Res 273(3):874–888
Mandal CA, Chakrabarti PP, Ghose S (1998) Complexity of fragmentable object bin packing and an appli-
cation. Comput Math Appl 35(11):91–97
Martello S, Toth P (1990) Bin-packing problem. In: Knapsack problems: algorithms and computer imple-
mentations, Wiley series in discrete mathematics and optimization. Wiley, pp 221–245
Martello S, Toth P (2003) An exact algorithm for the two-constraint 0–1 knapsack problem. Oper Res
51(5):826–835
Pollaris H, Braekers K, Caris A, Janssens GK, Limbourg S (2014) Vehicle routing problems with loading
constraints: state-of-the-art and future directions. OR Spectrum 37(2):297–330
Spieksma FC (1994) A branch-and-bound algorithm for the two-dimensional vector packing problem.
Comput Oper Res 21(1):19–25
Valério de Carvalho JM (1999) Exact solution of bin-packing problems using column generation and
branch-and-bound. Ann Oper Res 86:629–659
Valério de Carvalho JM (2005) Using extra dual cuts to accelerate column generation. INFORMS J Comput
17(2):175–182
Vanderbeck F (1999) Computational study of a column generation algorithm for bin packing and cutting
stock problems. Math Program 86(3):565–594
123
Bin packing with lexicographic objectives for loading… 417
Wei L, Lai M, Lim A, Hu Q (2020a) A branch-and-price algorithm for the two-dimensional vector packing
problem. Eur J Oper Res 281(1):25–35
Wei L, Luo Z, Baldacci R, Lim A (2020b) A new branch-and-price-and-cut algorithm for one-dimensional
bin-packing problems. INFORMS J Comput 32(2):428–443
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps
and institutional affiliations.
123