J. Soc. Korea Ind. Syst. Eng Vol. 9, No. 56-63, September 2016
tải về 0.73 Mb. Chế độ xem pdf
|
| of containers, pallets, and bulks in the aircraft cargo space
while satisfying stability restrictions defined above and fin- ishing 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 com- posed of three different positions. In sent positions, the numbers in parenthesis represent position numbers, and shaded rectangles denote containers. It is as- sumed 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 al- lowed; and repackaging containers, pallets, and bulks is not allowed. 3. Solution Algorithm To solve the air cargo loading problem, this paper devel- ops 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 greedy- type heuristic and improved by a method of generating new solutions and the ordinary SA procedure. Let container, pal- let, 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 po- sition in the cargo space where the selected container is lo- cated; 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 An Algorithm for the Loading Planning of Air Express Cargoes 59 space. The container giving the maximum revenue i * is de- termined using ∈ where r i 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 L j is the load limit of the location including position j and w i is the weight of container i. However, if there is no available position, container i* is never added in the re- cursive 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 re- cursively eliminate containers, each giving the minimum rev- enue among selected containers, until the corresponding sol- ution 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 contain- ers 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 chos- en is better than locating at the best empty positions. If the resulting solution is infeasible, we recursively eliminate con- tainers 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 t 0 is set as follows. First, tải về 0.73 Mb. Chia sẻ với bạn bè của bạn:
|