Information Technology Reference
In-Depth Information
instance including column generation time, branching or CPLEX solver time is less
than 1000 seconds. The branching rules based on Ryan and Foster [18] are not only
time-consuming for the large-sized instances, but also the solutions are not superior to
those resulting from D_FH branching and the CPLEX solver. For the small-sized
instances the solution quality is similar. Therefore, we just present results produced
by D_FH branching and the CPLEX solver.
We compare the heuristic CG technique with the two-level metaheuristic tabu
search (TS
2
PACK) developed by Crainic et al. [2]. The authors mentioned that the
TS
2
PACK metaheuristic outperforms other techniques for solving the three-
dimensional bin packing problem. Computational results are summarized in Table1.
The class of instance, the vehicle size and the number of items are presented in col-
umns 1, 2 and 3, respectively. Columns CG and TS
2
PACK correspond to the mean
number of vehicles over ten instances resulting from the CG technique and the
TS
2
PACK heuristic. It should be noted that TS
2
PACK is stopped after 1000 seconds
for each instance. Since the properties of classes 2 and 3 are the same as class 1, the
results for these classes are not considered for the TS
2
PACK heuristic in Crainic et al.
[2]. Column LB shows the lower bound for the mean number of vehicles over ten
instances resulted by Boschetti [5]. Since there are ten different instances for each
class and instance size, the last column shows the maximum execution time in
seconds for each instance. Note that the execution time for some instances is much
less than this value. It is seen that the maximum computational time for each instance
is 1000 seconds.
A comparison of results in column 3 with column 4 indicates that the quality of the
solutions obtained by the CG technique is the same or better than those produced by
the TS
2
PACK heuristic with a maximum computational time of 1000 seconds for
each instance in both algorithms. The performance of the CG technique is better than
the TS
2
PACK heuristic for the large-sized instances. The overall results show a total
gap of 3% between CG and TS
2
PACK.
8
Conclusion
In this work, we presented a column generation based heuristic algorithm for the
three-dimensional vehicle loading problem. To reduce the overall execution time of
the algorithm, heuristic pricing and branching are applied. The computational results
show that solutions obtained through this algorithm are better than any solution ob-
tained by meta-heuristics proposed in the literature. This method as a flexible tech-
nique can solve quite large instances better than other methods in a reasonable time. A
second contribution of this work is modifying the definition of extreme points used in
the best existing constructive heuristic for the 3D-BPP.
