An Algorithm for the Loading Planning of Air Express Cargoes
n moves are made and the average increase in the objective
function value ∆ is calculated with uphill moves only, and
then t 0
is computed as e −∆/t 0 = F 0
where F 0
is a parameter
to be determined. The temperature is decreased in such a
way that the temperature at the k-th epoch is given by t k = r․t k −1
, where r is a parameter, called the cooling ratio,
i.e., at each iteration, the temperature is reduced in accord-
ance with a geometric cooling schedule.
4. Computational Experiments
This section presents the performance of the suggested SA
algorithm over the direct application of the model suggested
in Kim et al. [3]. In addition, it presents the results of scenar-
io analyses on air express service providers’ activities to
draw practical implications. The SA algorithm and the pro-
gram to generate the integer program were coded using the
C computer programming language and the experiments
were performed on a personal computer with Intel (R) Core
(TM) i7-2600 operating at 3.40 GHz clock speed. After a
series of preliminary tests of the SA algorithm, parameters
F 0
,
β, and r were set to 0.79, 100, and 0.99, respectively,
and value m was randomly selected from the discrete uniform
distribution with a range of [1, 2].
To show the performance of the suggested SA algorithm,
computational experiments were performed on randomly
generated test problems with the data specific to Airbus
A300-600. Based on the information obtained from Air Hong
Kong, we randomly generated 250 test problems, 10 test
problems for each of all combinations of five different per-
centages of containers arriving at 30~60 minutes before the
scheduled flight departure time (20%, 30%, 40%, 50%, 60%)
and five levels for the number of arrived containers (10, 15,
20, 25, and 30). A high percentage of containers arriving
at 30~60 minutes before flight departure implies that container
loading operations should urgently completed in order not
to delay flight departure and vice versa. Note that about 40%
of containers arrive during this time period and the others
between 4 and 1 hour before flight departure in practice.
We used the aircraft-specific data such as the load lime of
each zone and the cargo-related data such as the arrival time
of containers summarized in Kim et al. [3]. For the test,
optimal solutions were obtained by directly solving the in-
Dong-Hoon Son․Hwa-Joong Kim
60
Performance of the SA Algorithm
Number of
containers
Percentage of containers arriving at 30~60 minutes before flight departure
Overall
20%
30%
40%
50%
60%
10
4.3%(2.0%)
a
0
b
2.5%(1.8%)
0
4.8%(3.1%)
0
5.4%(3.5%)
0
4.6%(2.2%)
0
4.3%(2.5%)
0
15
3.9%(2.3%)
0
3.3%(2.2%)
0
5.2%(4.3%)
0
3.1%(2.7%)
0
2.3%(2.0%)
0
3.6%(2.7%)
0
20
3.7%(2.7%)
0
3.5%(2.5%)
0
4.4%(3.4%)
0
6.2%(2.9%)
0
2.6%(2.3%)
0
2.7%(2.8%)
0
25
4.3%(2.4%)
1
5.0%(2.5%)
1
4.6%(2.9%)
1
4.5%(2.4%)
1
2.8%(1.9%)
2
4.2%(2.4%)
1.2
30
3.9%(1.8%)
2
3.7%(2.0%)
2
2.0%(3.3%)
2
3.0%(1.6%)
2
2.2%(2.3%)
3
2.9%(2.2%)
2.2
Overall
4.0%(2.3%)
0.6
3.6%(2.2%)
0.6
4.2%(3.4%)
0.6
4.4%(2.6%)
0.6
2.9%(1.7%)
1.0
3.8%(2.5%)
0.7
a
average and standard deviation (in parenthesis) of the percentage deviations from the optimal solutions (or lower bounds).
b
number of test problems (out of 10) that the SA algorithm obtained better solutions than CPLEX.
CPU Seconds of the SA Algorithm and CPLEX
Number of
containers
Percentage of containers arriving at 30~60 minutes before flight departure
Overall
20%
30%
40%
50%
60%
10
1.6(0.4)
a
0.0(0.0)
b
1.1(0.3)
0.2(0.1)
1.0(0.3)
0.0(0.0)
2.2(0.5)
0.0(0.0)
1.1(0.2)
0.0(0.0)
1.4(0.3)
0.1(0.0)
15
2.3(2.4)
1.7(0.1)
3.7(2.2)
0.2(0.0)
5.2(3.1)
0.2(0.0)
9.8(5.8)
0.4(0.1)
4.1(2.4)
2.6(0.1)
5.0(3.2)
1.0(0.1)
20
79.0(8.3)
765.0(102.5)
80.5(9.4)
749.3(111.0)
49.7(16.0)
756.6(97.5)
83.1(7.5)
988.8(152.4)
92.8(8.8)
849.3(146.7)
77.0(10.0)
821.8(122.0)
25
139.9(10.2)
2809.2(807.4)
133.5(9.6)
2840.2(889.2)
148.3(11.5)
2927.0(803.3)
142.8(10.7)
3215.4(815.8)
145.1(9.0)
3166.5(908.5)
141.9(10.2)
2991.7(844.6)
30
172.3(13.8)
2347.3(798.7)
177.0(12.3)
2029.6(928.5)
197.2(19.5)
2640.1(773.8)
185.6(21.4)
2529.4(760.0)
206.4(27.5)
2641.4(758.7)
187.7(18.9)
2437.5(804.1)
Overall
79.0(7.0)
1184.6(341.7)
79.2(6.7)
1123.9(385.8)
80.3(10.1)
1264.8(334.9)
84.7(9.2)
1346.8(345.7)
89.9(9.6)
1180.7(362.8)
82.6(8.5)
1250.4(354.2)
a
average and standard deviation (in parenthesis) of CPU seconds of the SA algorithm.
b
average and standard deviation (in parenthesis) of CPU seconds of CPLEX.
teger program using CPLEX 12.6.1, a commercial opti-
mization software package. We set a time limit to be 3600
seconds in the CPLEX to avoid unnecessary excessive run-
ning and compare with lower bound solutions (obtained by
CPLEX) if no optimal solution could be obtained within the
time limit.
The test results for the performance evaluation are sum-
marized in
, which shows the percentage deviation
from CPLEX solutions and the number of test problems (out
of 10) that the SA algorithm gave better solutions than
CPLEX. It can be seen from the table that the SA algorithm
gave good solutions, e.g., the overall percentage deviation
from optimal solutions (or lower bounds) was 4%, 3.6% ,
4.2%, 4.4%, and 2.9% for the cases of 20%, 30%, 40%,
50%, and 60% of containers arriving at 30~60 minutes before
flight departure, respectively. In particular, the SA algorithm
obtained better solutions than CPLEX for some test prob-
lems, e.g., three test problems in case of 60% arrival and
30 containers. On the other hand, the performance of the
SA algorithm is robust to the change of the container arrival
percentage and the number of containers. That is, the per-
formance of the SA algorithm is not significantly affected
from the parameters.
summarizes the CPU seconds of the SA algo-
rithm and CPLEX tested. The overall computation times of
the SA algorithm were significantly shorter than CPLEX
with the time limit of 3,600 seconds, i.e., the SA algorithm
was nearly ten times faster than CPLEX. It is notable that
the SA algorithm required significantly less than 20 CPU
minutes, which is the time that planners in Air Hong Kong
are allowed to take when making a plan. However, CPLEX
has taken almost 20 minutes and more than one hour in many