Column Generation Based Heuristic for the Three Dimensional Vehicle Loading Problem - Computational Logistics - page 258

master problem that is a linear relaxation of the model and a sub-problem. The master
problem deals with assignments of items to vehicles, while the sub-problem deals
with the accommodation of items within those vehicles. The master problem deals
with a large number of variables and to handle this complexity a CG technique is
used, which considers just a subset of variables. A set of heuristic pricing problems
are solved to identify the new variables (feasible columns) with negative reduced cost.
To check the feasibility of a column, a modification of the extreme point-based heu-
ristic method [1] is used. At the termination of the column generation step (when no
new entering column/variable can be identified) if the solution to the master problem
is non-integer, a set of branching rules in a heuristic framework is applied.
Extensive computational results on test instances indicate that solutions obtained
by the CG technique are comparable to those produced by a two-level tabu search
meta-heuristic (TS 2 PACK) developed by Crainic et al . [2]. The performance of the
CG technique is only compared with TS 2 PACK, since this method outperforms other
techniques for solving the 3DVLP.
We assume that I is the set of all cubic items. Each item is characterized by
length , width and height . There is an unlimited number of vehicles of fixed
sizes, specified with length L , width W , and height H , with rectangular loading surface
accessed only from one side. Without loss of generality, it is assumed that the length
and width of vehicles are along the x axis and y axis, respectively. The coordinates of
back-left-bottom (BLB) corner of the vehicle is fixed at origin.

2 Literature Review

In the literature, vehicle loading or container loading problems are referred to as bin-
packing problems. Pisinger [3] pointed out that there are different variants of packing
problems depending on the objective function and restrictions available in the
problem. There is a huge literature on multi-dimensional packing problems. Iori and
Martello [4] have broken down the multiple-dimensional packing problem into the
two-dimensional bin packing problem (2BPP), two-dimensional strip packing prob-
lem (2SPP), three-dimensional bin packing problem (3BPP) and three-dimensional
strip packing problem (3SPP). They argued that genetic algorithms and tabu search
are often used as heuristics to solve multi-dimensional bin packing problems.
3BPP deals with packing a given set of rectangular boxes into a minimum number
of large identical three-dimensional bins. Most researches focus on the 3BPP with
identical bins and boxes with fixed orientation. Martello et al . [5] were the first to
develop a two-level branch & bound exact algorithm to the 3BPP based on the
concept of corner points (CPs). The CPs are points within the residual space of the
vehicle where a new item can be accommodated. They tested their exact method on
instances with up to 200 items.
Den Boef et al . [6], Fekete and Schepers [7], Martello et al. [5] and Boschetti [8]
discussed and proposed the lower bounds for the 3BPP. The lower bounds proposed
by Boschetti dominate all bounds by the other authors.