to handle complicated constraints (e.g., the three-dimensional bin packing in this
study).
Algorithmic framework to solve the last mile problem
N = set of unassigned customers;
R = set of routes, always contains the empty route, initially contains only the empty
route; while N , ∅ do c ∗ = ∞; for j ∈ N do
for r ∈ R do
for (i − 1, i) ∈ r do
if BinPackingFeasible(r, i, j) and Cost(i, j) < c ∗ then
r ∗ = r; i ∗ =
i;
j ∗ = j;
c ∗ = Cost(i, j);
end if
end for
end for
end for
Insert (i*,j*);
N = N \ j* ;
Update(r ∗ );
end while
*
In the framework above, BinPackingFeasible(r,i, j) is a function to check
whether the insertion of customer j between (i À 1) and i in the route r is feasible
for three-dimensional bin packing such as the non-overlapping of modularized boxes
and the Last-In, First-Out requirement. We proposed two methods to evaluate the
value of the function BinPackingFeasible(r,i, j). The first one is based on the
technique of constraint programming. Compared to traditional mathematical optimization, usually in constraint programming, the optimal solutions are not very
important since the major task is to seek feasible solutions which satisfy all the
constraints. However, in the three-dimensional bin packing problem, since we must
obey the laws of gravity and cannot allow “floating boxes,” we try to minimize the
sum of y i s instead.
44
Sh. Sharif Azadeh et al.