Information Technology Reference
In-Depth Information
initializing the algorithm with a good feasible solution. In this work an initial solution
is obtained by a modification of the algorithm of Crainic et al. [1]. Given a list of
sorted items specified by a sorting rule, items are loaded into the vehicle one after the
other based on the concept of Extreme Points (EPs) [1]. When an item cannot be
loaded into the current vehicle, a new vehicle is created. Placing an item into a vehicle
splits vehicle's space into new volumes. EPs provide information about all possible
empty positions where new items may be loaded.
The basic process of generating EPs is as follows. Suppose that an item
i
with di-
mensions
,
,
) is added to a given loading in position
,
,
. This placement
produces a set of
EPs that are projections of point
,
,
along the
y
and
z
axes, point
,
,
along the
x
and
z
axes, and point
,
,
along the
x
and
y
axes (see Figure 1). In each direction, if there are some items between item
i
and the wall of the vehicle, a point is projected on the nearest item.
Fig. 1.
EPs (black circles) generated by placing an item into a vehicle
If the vehicle is empty, placing an item in position (0,0,0) generates three EPs in
points
,0,0
,
0,
,0
and
0,0,
.
6.1
Introducing New EPs
Suppose that there is a loading of two items as shown in Figure 2. All EPs related to
this loading are illustrated by black circles. To add a new item
k
with dimensions
,,
into the current loading, all EPs are considered, but no one is appropriate.
The only place where item
k
can be accommodated is the point specified by the white
circle, but this point is not in the set of extreme points.
