J. Soc. Korea Ind. Syst. Eng Vol. 9, No. 56-63, September 2016



tải về 0.73 Mb.
Chế độ xem pdf
trang3/5
Chuyển đổi dữ liệu11.05.2022
Kích0.73 Mb.
#51824
1   2   3   4   5
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

= 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
= rt
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 


An Algorithm for the Loading Planning of Air Express Cargoes
61
100.0%
99.8%
99.8%
99.8%
99.7%
99.3%
99.3%
100.0%
100.0%
99.6%
99.2%
99.0%
98.6%
98.6%
98.1%
97.8%
99.7%
99.5%
99.1%
97.9%
97.9%
97.3%
96.0%
95.1%
95.0%
95.5%
96.0%
96.5%
97.0%
97.5%
98.0%
98.5%
99.0%
99.5%
100.0%
Non-urgent container arrival situation
Moderately-urgent container arrival situation
Urgent container arrival situation
Flight 
departure 
time 
Revenue 
change
rate
Effect of Different Flight Departure Times
cases. On the other hand, their computation times dramati-
cally increased along with the number of containers as 
expected. They increased also along with the container arriv-
al percentage although the increase rates were not significant 
unlike the number of containers. This may be because in-
creasing the number of containers increases the problem-size 
while the container arrival percentage does not. The standard 
deviation of CPU seconds of the SA algorithm was around 
10% of its average while that of CPLEX was more than 
50% in many cases, i.e., the variability of the CPU seconds 
of the SA algorithm is less than that of CPLEX. Therefore, 
considering the solution quality and the computation time
one may regard the SA algorithm as a viable tool for making 
a loading planning of air express cargoes.
To draw practical implications, we further conducted sce-
nario analyses to investigate effects on changes in revenue 
when the aircraft departs earlier than the scheduled departure 
time and the time required for lifting a container up to the 
cargo space door is reduced. These analyses were performed 
based on the information obtained from the current activities 
of air express service providers. UPS is letting depart his 
aircrafts to alleviate congestion in UPS air hub, named 
Worldport. However, one may think that this may reduce 
the revenue of UPS because some cargoes may not be 
caught. On the other hand, DHL, UPS, and FedEx are trying 
to reduce the lift-up time in order not to delay flight de-

tải về 0.73 Mb.

Chia sẻ với bạn bè của bạn:
1   2   3   4   5




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý

    Quê hương