1.Introduction
Air express market has rapidly expanded during the past two decades, e.g., the intra-Asia market has grown in excess of 6.5% per annum in recent years [2]. Air express service providers such as FedEx, UPS, and DHL offer various express delivery services such as overnight delivery and nextbusiness day delivery services. Although on-time delivery is a key issue for providing the express delivery services [15], there are many obstacles disturbing them such as late arriving cargoes and late-generated loading plans. Moreover, the service providers receive cargoes until 30 minutes before flight departure to catch as many as cargoes [3]. This implies that a short amount of time is available to complete all operations before flight departure including establishing loading plans.
One of major concerns in the air cargo loading planning is to establish a plan that insures the stability of an aircraft to avoid take-off, flight, and landing accidents. See Park et al. [9] for the aircraft operational risk. Therefore, this paper considers an air cargo loading planning problem, which is the problem of determining locations in the aircraft cargo space where air containers, pallets and bulks to be located while insuring the aircraft stability. As reviewed below, previous research except for Kim et al. [3] did not or simply considered the aircraft stability restriction. Instead, we consider all of stability restrictions considered when planners in an air express carrier establish manually a loading plan in practice. The objective of the problem is to maximize the total revenue gained from loading cargoes.
We confine our review to previous studies after 1985 because Martin-Vega [6] provided a comprehensive review of the literature on the air cargo loading planning. Ng [8] suggested a multi-criteria goal programming model for maximizing the cargo loading and minimizing exceeding the capacity of an aircraft. Amiouny et al. [1] consider a special case of our problem with the objective of making a center of gravity be as close as possible to a specific target point. Their heuristic produced good solutions in terms of solution quality and computation time. Later, Marthur [5] suggested a better heuristic algorithm for Amiouny’s problem. Thomas et al. [11] presented a case study in FedEx using the same aircraft model used in our research. To solve the problem, they suggested a heuristic algorithm consisting of two phases : the first phase generates an initial loading plan using an integer program without specific objective function; and then a feasible loading plan is generated by recursively eliminating non-preferred containers from the initial solution until the solution satisfies all constraints. Mongeau and Bes [7] considered the problem with the objective of maximizing the total weight of cargoes and suggested an integer program while considering three stability restrictions : total weight limit of cargoes, weight limit of locations. Recently, Yan et al. [13, 14] considered a loading planning problem in a hub-and-spoke system by considering different destinations of cargoes. However, the stability restriction was not considered in these studies. Lurkin and Schyns [4] proposed an integer program by considering multiple destinations of containers. Vancroonenburg et al. [12] considered the loading problem with the objective of maximizing the total profit obtained from delivering containers while minimizing deviation of the aircraft’s center-of-gravity. Finally, Kim et al. [3] considered the problem, the same as in the current paper, motivated from DHL and Air Hong Kong. They defined the problem as methods used when planners in Air Hong Kong manually make loading plans and suggested an integer program to solve the problem.
The current paper extends Kim et al. [3] who suggested only an integer program, which itself is not a viable tool especially in the air express industry where cargo loading plans should be quickly established as described above. According to a manager in Air Hong Kong, planners in the company make a cargo loading plan within 20 minutes due to the characteristics of their business. However, the integer program requires more than 20 minutes in many cases in obtaining an optimal solution as reported in Section 4. Therefore, the current paper suggests a quickly-running heuristic that can obtain good solutions. In addition, to draw practical implications for air express service providers, scenario analyses are performed to analyze the effect of their current activities.
The remainder of this paper is organized as follows. The next section describes the problem along with stability restrictions. Section 3 presents a simulated annealing (SA) algorithm with methods for generating an initial solution and improving the solution. Section 4 summarizes the results of computational experiments and scenario analyses. Section 5 concludes the paper by summarizing research results and offering future research directions.
2.Problem Description
The problem considered in this research is to determine the locations of containers, pallets, and bulks while satisfying the stability restrictions of an aircraft, Airbus A300-600 in <Figure 1>. Since a detailed description on the problem is given in Kim et al. [3] and a long description is needed to exactly define the problem, this section shortly describes stability restrictions, which are major concerns in the air cargo loading planning.
There are four types of the stability restrictions for the aircraft : cumulative load limit; location load limit; lateral load imbalance limit; and center-of-gravity restriction. These limits are essential for the sake of safe take-off, in-flight, and landing of the aircraft. First, each zone depicted in <Figure 1(b)> has its own cumulative load limit. The cummulative load limit of a zone implies that the total weight of all cargoes in previous zones located on the left or right side of the zone and itself should not be more than the limit of the zone. For example, the total weight of all cargoes loaded in zones A, B, C, D, E should not be more than the cumulative load limit of zone E. Second, the location load limit implies that the weight of cargoes loaded in a location depicted in <Figure 1(a)> should not be more than the limit of the location. Third, the lateral load imbalance limit implies that the weight difference between left and right lanes of the aircraft denoted in <Figure 1(b)> must not exceed the imbalance limit. Finally, the center-of-gravity restriction is literally related to maintaining the aircraft’s center- of-gravity after loading all cargoes and having crews on board. Since it requires a lengthy explanation, we omit the detailed description to avoid duplication. See Kim et al. [3] having described it in detail along with examples.
Now, the problem considered in this research is defined as follows : the problem is to determine the loading locations of containers, pallets, and bulks in the aircraft cargo space while satisfying stability restrictions defined above and finishing all loading operations before the closing time of the aircraft, with the objective of maximizing the total revenue gained from loading the cargoes. The closing time is the last time that all cargo loading operations should be finished before flight departure. It is assumed that a location is composed of three different positions. In <Figure 2>, dots represent positions, the numbers in parenthesis represent position numbers, and shaded rectangles denote containers. It is assumed that containers, pallets, and bulks arrive at different times according to real practice. It is also assumed that no cargo is loaded on the aircraft before solving the problem. Finally, the other assumptions made in this research are : reshuffling cargo locations in the cargo space is not allowed; and repackaging containers, pallets, and bulks is not allowed.
3.Solution Algorithm
To solve the air cargo loading problem, this paper develops a SA algorithm, which is one of meta-heuristics that avoid falling into a local optimum by sometimes accepting neighborhood solutions with worse objective values. The SA algorithm consists of solution construction and improvement phases, where an initial solution is constructed by a greedytype heuristic and improved by a method of generating new solutions and the ordinary SA procedure. Let container, pallet, and bulk be container for convenience.
An initial solution for our SA algorithm is constructed through a greedy-type heuristic : select a container with the highest revenue among unloaded containers; determine a position in the cargo space where the selected container is located; and check its feasibility in terms of constraints in the model of Kim et al. [3] including stability restrictions defined above.
To explain in more detail, let C be the set of unselected containers, P the set of unoccupied positions in the cargo space. The container giving the maximum revenue i*is determined using
where ri is the revenue of container i. The best position of container j*to be located is determined by considering the load limit of the location including the position as :
where Lj is the load limit of the location including position j and wi is the weight of container i. However, if there is no available position, container i*is never added in the recursive routine of generating the initial solution. This routine continues until all sets of containers and their positions are determined.
A solution with selected containers and their positions in the cargo space could be infeasible in terms of constraints in the model of Kim et al. [3]. To make it feasible, we recursively eliminate containers, each giving the minimum revenue among selected containers, until the corresponding solution satisfies all required constraints.
Next, to improve the current solution (or initial solution), a neighborhood solution is generated by adding m containers into the current solution. That is, value m is randomly chosen and m containers are randomly selected among non-selected containers in the current solution. Then, m selected containers are randomly located at empty positions in the cargo space. Although one may think that those containers may be better being located at the best empty positions as in the solution construction method, a series of preliminary tests has indicated that locating at empty positions randomly chosen is better than locating at the best empty positions. If the resulting solution is infeasible, we recursively eliminate containers randomly chosen from the current solution until all constraints are satisfied.
If the solution is improved, the move to the new solution is accepted. Otherwise, the move can be accepted with a specified probability controlled by a temperature. Our SA begins a high temperature and the temperature is decreased with a certain rule, called the cooling schedule or annealing schedule in the literature. The temperature is kept the same for a certain number of iterations, called the epoch length. The epoch length L is set to β ․[n․(n-1)/2], where β is a parameter to be determined and n is the number of containers. The initial temperature t0 is set as follows. First, n moves are made and the average increase in the objective function value Δ is calculated with uphill moves only, and then t0 is computed as e-Δ/t0= F0 where F0 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 tk = r․tk-1, where r is a parameter, called the cooling ratio, i.e., at each iteration, the temperature is reduced in accordance 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 scenario analyses on air express service providers’ activities to draw practical implications. The SA algorithm and the program 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 F0, β , 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 percentages 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 integer program using CPLEX 12.6.1, a commercial optimization software package. We set a time limit to be 3600 seconds in the CPLEX to avoid unnecessary excessive running 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 summarized in <Table 1>, 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 problems, 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 performance of the SA algorithm is not significantly affected from the parameters.
<Table 2> summarizes the CPU seconds of the SA algorithm 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 cases. On the other hand, their computation times dramatically increased along with the number of containers as expected. They increased also along with the container arrival percentage although the increase rates were not significant unlike the number of containers. This may be because increasing 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 scenario 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 departure. Under this background, their effects are analyzed by variating flight depart times and lift-up times in the data- setting. The flight departure time was varied from noon set by Kim et al. [3] to 11:40 in decrements of 2.5 minutes and the lift-up time was varied from 300 seconds set by Kim et al. [3] to 260 seconds in decrements of 5 seconds. We generated 10 test problems for each combination of the flight departure time and the lift-up time and randomly set to U(20%, 40%), U(40%, 60%), and U(60%, 80%) of containers arriving at 30~60 minutes before flight departure for non-urgent, moderately-urgent and urgent container arrival situations, respectively. Here, U(a, b) is the uniform distribution with a range of [a, b].
<Figure 3> shows the effect of different flight departure times on the rate of revenue change compared to the original departure time. It can be seen from the figure that the revenue decreased as the flight departure time became earlier as expected. For example, if the flight departure time was changed from noon (original schedule) to 11:40, i.e., 20 minutes earlier than the original schedule, the revenue decreased 0.7%p, 2.2%p, and 4.9%p for non-urgent, moderately-urgent and urgent container arrival situations, respectively. This implies that air express service providers should be cautious when letting their aircrafts depart earlier than the original schedule.
<Figure 4> shows the effect of different lift-up times on the rate of revenue change compared to the original lift-up time. It can be seen from the figure that the revenue slightly increased as the lift-up time of containers reduced as expected. For example, if the lift-up time reduced from 300 seconds to 260 seconds, i.e., 13% reduction, the revenue increased 0.9%p, 0.9%p, and 0.8%p for non-urgent, moderately-urgent and urgent container arrival situations, respectively. This implies that air express service providers should make their effort to reduce the lift-up time and more generally writing to improve the productivity of cargo loading operations and warehousing operations as described in Song et al. [10].
5.Conclusion
This paper revisited a previous study having considered the problem of planning the loading of air express cargoes motivated from DHL and Air Hong Kong. The problem is to determine the locations to be loaded in an aircraft while maintaining its stability. The objective of the problem is to maximize the total revenue obtained from loading containers. The current paper suggested an SA algorithm because our previous research suggested an integer program requiring a long computation time. Computational experiments were performed to evaluate the performance of the SA algorithm and derive some managerial implications for air express service providers. The test results showed that our SA algorithm could give good solutions within a short amount of computation time. Therefore, it can be argued that the SA algorithm may be a viable tool for air express carriers including Air Hong Kong needing to quickly establish air cargo loading plans. In addition, scenario analyses showed that air express service providers could experience revenue drop if letting their aircrafts depart earlier than the original schedule and revenue rise if decreasing the container lift-up time.
This research can be extended in several ways. First, relocation of containers already loaded in the aircraft should be considered because more containers may be loaded by relocating the containers. Second, it is worthwhile to consider the uncertainty of the cargo weight and arrival time. Third, the problem of jointly determining cargo loading and packaging plans is a meaningful research direction. Finally, the problem considering different directions of cargoes is worthwhile to be considered.
