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

yielding the best experimental results. In the present work, we apply two sorting rules
Clustered Area-height and Clustered Height-area [1]. In the Clustered Area-height,
for a given 1,100 a set of intervals ,

,

is defined based
on the vehicle area . Items whose base areas are in the same interval are as-
signed into a group. Groups are ordered according to k and items of a group are sorted
by decreasing values of their height. In the Clustered Height-area, for a given
1,100 a set of intervals ,

,

is defined based on the vehicle
height . Items whose height is in the same interval are assigned in a group. Groups
are ordered according to k and items of a group are sorted by decreasing values of
their base area.

6.3 Pseudocode for Generating an Initial Solution

All items are loaded into vehicles by the Loading(SI,(L,W,H)) procedure in
which SI is a list of sorted items resulted by rules Clustered Area-height or Clustered
Height-area and (L,W,H) are the dimensions of the vehicles. As long as SI is not emp-
ty, one vehicle after the other is filled. Let LEPs be the set of EPs initialized by point
(0, 0, 0). For each item , PutItemInVehicle procedure scans list LEPs
from first to end to identify an EP p on where an item i can be placed. It returns true,
if item i can be loaded, otherwise false. In fact, an item can be placed on an EP, if
placement of its left-back-bottom corner on EP does not overlap with the other items
available in the vehicle. If item i can be placed on more than one EP, the EP with the
lowest z, y, x coordinates in order is selected. Update_LEPs procedure generates
and inserts new EPs, generated by placing item i to LEPs. The residual spaces of EPs
are updated by the UpdateResidualSpace procedure. Items are added to a ve-
hicle as long as possible. If no items fit into a vehicle, the vehicle is closed, and a new
vehicle is initialized and so on. This process is repeated until all items are loaded into
vehicles. Note that procedures Update_LEP and UpdateResidualSpace are
Algorithms 1 and 2 in Crainic et al. [2], respectively. After placement of an item into
a vehicle the total set of EPs is updated by the UpdateResidualSpace procedure.

Loading(SI,(L,W,H))
while SI is not empty do
Initialize new vehicle v with dimensions (L,W,H)
LEPs= {(0, 0, 0)}.
for each item i • SI do
if PutItemInVehicle(i, LEPs) then
Update_3DEPL(i,p,LEPs)
UpdateResidualSpace(i,LNVs)
Remove item i from SI
Endif
Endfor
Close vehicle v
Endwhile