An implicit fully discrete compact finite difference scheme for time fractional diffusion-wave equation

1.   Introduction

The economy of China is expanding rapidly with the increasing demand for air freight services. Since 2008, China's air cargo and postal transport volume maintains sustained growth, from 4.076 million tons in 2008 to 8.632 million tons in 2020 ^[1], meanwhile the products needed to be transported become more diversified, a large amount of high value-added goods including fresh goods, seasonal or precious commodities appear. In other words, the situations of multi batch, small batch, fast transportation are more prominent, and higher real-time requirement is presented compared with other logistics industries.

In order to improve the efficiency of air freight transport system, an efficient automated multi-dimensional warehouse with ETVs needs to be established, and as the basis of the system, a proper scheduling strategy considering the assignment of cargo locations as well as the sequence of inbound/outbound tasks should be designed.

From limited references in the past few years, the relevant research mainly focus on deciding the cargoes' transportation sequence. Guo ^[2] and Qiu et al. ^[3] studied the inbound and outbound cargoes scheduling problem with single ETV and solved it with particle swarm optimization (PSO) algorithm. Different from the above single ETV scheduling problem, Lei ^[4] discussed the task scheduling problem with dual ETVs considering collision avoidance and introduced expert system to improve the operation efficiency. Ding ^[5] proposed task chain generation algorithm with improved shared fitness strategy and applied it to assign two ETVs to different cargo areas.

The works mentioned above developed different scheduling models with considering picking sequence and ETV routing, but they neglected to discuss the problem of assignment of input and output ports (I/O ports) if the air freight station has several entrances and exits. On the other hand, previous scheduling problems have been solved with different intelligent algorithms, but a more efficient algorithm needs to be designed for improving the efficiency and accuracy as the problems become more complex. In our research, ABC algorithm which possesses strong global optimization ability and few parameters ^[6,7,8,9] is first introduced to solve the scheduling problem in air freight transport system.

Actually, as one of the most recently defined bio-inspired algorithms, ABC is motivated by the swarm intelligence behaviors of gregarious colony, and it has been proved to be useful in solving various engineering problems, such as civil engineering design ^[10], aerospace industry ^[11], software testing ^[12], logistics warehouse management ^[13], manufacturing production ^[14], communication problem ^[15] and so on. However, it often suffers from the problems of poor exploitation and slow convergence, so developing new search mechanisms is crucial for complex optimization problems. Recently, other metaheuristic algorithms were introduced and combined with traditional ABC to improve its performance. Ghanem et al. ^[16] incorporated monarch butterfly optimization into ABC. The firework explosion search mechanism was introduced to explore the potential food sources of ABC in ^[17]. Gaidhane et al. ^[18] mixed ABC with grey wolf optimizer to balance the exploration and exploitation capabilities. Liang et al. ^[19] introduced differential operator in employed bee phase and revised the selection probability to be a step function. Moreover, another improving idea was to replace the single search strategy in original ABC with two or more search strategies. Xu et al. ^[20] introduced differential evolution strategy in employed bee phase to accelerate its convergence and adopted the global best position to guide the following updating processes in onlooker bee phase which could enhance the local search ability. Literature ^[21] proposed two search strategies with the help of the information of the best-so-far solution and the mean of two random solutions. In ^[22], three search strategies with different characteristics were employed to construct a strategy candidate pool, and the Parzen window method was applied to select the best candidate individuals. Two new search strategies were adopted based on the k-neighborhood of best solution in ^[23] which didn't need to calculate the selection probability. Different from the above literatures, from the perspective of improving the search mechanism, Zhang et al. ^[24] proposed a new search mechanism named full-dimensional ABC algorithm (fdABC), it was executed with all dimensions of each solution thus the search area could be expanded and the probability of obtaining the optimal solution could be improved. Although the proposed algorithm possessed better optimization performance especially for high-dimensional optimization problems, the time cost increased substantially because more dimensions needed to be updated compared with traditional ABC. In this paper, improvement on the search mechanisms is introduced and applied to solve the scheduling problem in air freight station.

The main features that distinguish this study from previous studies are presented below. a) For solving the tasks scheduling problem in airport container storage area with several I/O ports, the model considering the assignment of I/O ports, as well as the optimization of picking sequence and ETVs' travelling route is first established. The proposed modeling method could be applied to all scheduling problems of storage systems in fast moving consumer goods industry, e-commerce industry and logistics industry; b) In order to balance the abilities of exploration and exploitation of ABC algorithm, two improvements on search mechanisms are proposed. Different from original ABC that only one dimension is randomly updated, improvement is realized by saving the most valuable dimension of current solution and guiding the direction of subsequent exploration. Related improvement could be adopted to solve all optimization and scheduling problems in engineering fields.

The rest of this paper is organized as follows: Section 2 introduces the scheduling model with dual ETVs in the freight station of Luoyang Beijiao Airport. Then ABC and IMABC algorithms are proposed in Section 3, and their optimization performance is verified on benchmark functions. In Section 4, the improved algorithms are applied to the dual ETVs scheduling problem and their effectiveness is proved. Finally, the above work is summarized.

2.   Modeling of the scheduling problem

2.1.   System description

The air freight station in Luoyang Beijiao Airport consists of three parts, which are container storage area, bulk cargo storage area, and unhandled cargo area respectively as shown in Figure 1.

As the core of the whole system, the container storage area is used for handling the containerized cargoes, which are unloaded from aircraft in the airside or inbounded from the bulk cargo storage area in the landside. It is a three-dimensional warehouse with two rows of shelves and 16 I/O ports, each row has eight layers and 60 columns, the total slots are $60\times 8\times 2 = 960$. Two ETVs are employed for handling cargoes between the 14 I/O ports in airside and the two I/O ports in landside, and each ETV is responsible for half of the shelf and I/O ports.

The operational process of the two ETVs is depicted as Figure 2 (some columns and I/O ports are omitted). ETVs start from R₁ and R₃ respectively, the 1# ETV picks up cargo at entrance R₂, and stores it at I₁. And then, it retrieves outbound cargo from O₂ and delivers it to the exit C₁. The same actions are executed with 2# ETV from R₃ to C₂.

Obviously, in order to improve the efficiency of cargo transportation in the container storage area, the sequence of inbound/outbound tasks as well as the corresponding I/O ports need to be scheduled, meanwhile the actions of ETVs should be optimized to obtain the minimum running time.

2.2.   Model formulations

For solving the scheduling problem, the objective function should be established firstly based on the notations defined in Table 1.

If there are several inbound and outbound tasks in the storage area, the objective of optimized problem which is named as fitness function is to minimize the total execution time H_max between two ETVs under the constraints in Eq (2).

The first constraint in Eq (2) ensures that the columns between two ETVs at any time are no less than four, which could avoid collision with each other. As the task set is divided into two equal parts and assigned to two ETVs, the second constraint avoids repeated allocation. The time ${fit}_{j}$ in Eq (3) is defined as the summation of execution time ${H}_{io}$ and ${H}_{{i}_{1}}$ of $n$ tasks assigned to the specific ETV, it is the total time cost for picking up, releasing as well as transporting all assigned cargoes. Here the execution time ${H}_{io}$ and ${H}_{{i}_{1}}$ corresponding to different tasks can be obtained from Table 2 (Only the values corresponding to the first five layers and six columns are listed), which are calculated from Eqs (4) and (5). The first row and first column of Table 2 respectively represent the number of difference of rows and columns between the start position and destination in the shelf.

For solving the above nonlinear scheduling problem, an effective optimization algorithm should be introduced.

3.   ABC algorithm and its improvements

3.1.   ABC algorithm

ABC is an optimization algorithm based on the intelligent foraging behavior of honeybee swarm, where the bee colony consists of three groups: employed bees, onlooker bees and scout bees. The position of a food source represents an optimal solution of the specific problem, and its quality could be evaluated through the fitness value of the corresponding solution ^[9,25].

The algorithm starts iterative optimization from employed bee phase, it executes a crossover and mutation process with one randomly chosen companion, and the new solution ${x}_{mk}^{\text{'}}$ is updated based on ${x}_{mk}$ as shown in Eq (6). Then the fitness value of each solution fitness_m could be calculated, and the onlooker bee randomly chooses to exploit or not around corresponding employed bee with the probability Pm defined as Eq (7). If the current mth solution to be exploited cannot improve for several iterations, it will be abandoned, and a scout bee corresponding to a new randomly produced solution will replace it.

where m, $n$ represent the indices of specific solution in the population, $m, n\in \left\{\mathrm{1, 2}, \dots , N\right\}m\ne n$. $k$ is the dimension of the population, $k\in \{\mathrm{1, 2}, \dots , D\}$.$rand\left(-1, 1\right)$ is a random number between [-1, 1]. $SN$ is the number of food sources as well as the number of employed bees.

3.2.   The improved ABC algorithm

In ABC algorithm, for each solution, only one dimension is randomly selected and updated according to Eq (6) in employed bee phase and onlooker bee phase. In this case, the updated dimension may be different in each iteration and the optimal dimension obtained in the previous iteration is likely to be omitted in the following iterations. Thus, the search toward the possible optimal solutions is unable to be continued, the optimization accuracy and the convergence speed will be affected.

In ^[23], full dimensional search strategy (fdABC) is introduced to traverse all dimensions of the solution and select the optimal dimension for further exploration, therefore the search could be extended and the possibility of obtaining optimal solution will be improved, but the optimization time increases inevitably. Another improvement called random multi-dimensional artificial bee colony algorithm (RmdABC) is mentioned in ^[26], the key improvement of the strategy is to randomly select several different dimensions from $\{\mathrm{1, 2}, \dots , D\}$ for one solution, and execute the updated process with Eq (6) in the employed bee and onlooker bee phases. Obviously, it randomly traverses any several dimensions of the solution in each iteration, and fewer dimensions are updated compared with fdABC, as the result, its time complexity could be greatly improved.

In order to further balance the abilities of exploration and exploitation, IMABC strategy is proposed where more valuable dimensions of solution will be picked out and saved in the external set which is used to guide the subsequent exploration. The operations of IMABC are shown as Figure 3 and outlined as follows:

1) In the first iteration, all dimensions of the solution are searched, and new solutions are generated with Eq (6) in employed bee and onlooker bee phases.

2) The fitness values of the generated solutions need to be compared with the optimal one, and if the new solution is superior to the old one, the solution in that dimension could be recognized as having the potential to be optimized, thus the optimal solution should be substituted with the generated one, the valuable dimension will be recorded in the external set and the flag is set to be one.

3) In employed bee and onlooker bee phases, after updating all dimensions of the solution, the value of flag will be checked. If the flag sign is equal to one, it means there is at least one dimension has been updated. If flag sign is zero, it demonstrates that the exploration is failed, and the number of iteration trial should increase by 1.

When the whole cycle is greater than or equal to the value of MaxCycle, if trial < Limit, the above updating operations based on the stored optimal dimensions should be performed iteratively. If trial > Limit, the value of trial resets back to zero and a new random solution will be generated to replace the old one.

Obviously, more dimensions will be explored in IMABC, it could cover more solution space and the ability of exploration could be improved compared with ABC algorithm. Meanwhile, with the help of the stored optimal dimension searched so far, the speed towards the global optimal solution could be accelerated and the ability of exploitation will be enhanced compared with fdABC and RmdABC. Therefore, the performance of the exploration and exploitation could be balanced.

The pseudo-code of IMABC is given below.

3.3.   Performance evaluation

In order to evaluate the performance of the proposed IMABC algorithm, nine CEC 2017 benchmark functions as listed in Table 3 are employed, where f₁(x), f₂(x) and f₆(x) are unimodal functions, and the others are multi-modal functions. All simulations are executed on an Intel Core i7-8750H CPU with 8G RAM, the population size is 200, the dimension of solution is set to 60, 80 and 100 respectively, the number of maximum iterations is set as being 1000, and the limit used in scout bee phase is taken 100. Independent experiments are run 20 trials, the indices including the mean and standard deviation (Mean ± std dev) which reflect the quality of solution and the stability of algorithm, the average running time (Aver-R), the shortest running time (Best-R) and fitness value of the optimal solution (Best-F) are selected to evaluate the optimization performance of different algorithms.

Tables 4–6 illustrate the optimization results with four different algorithms in different dimensions, where the best results among the four indices are highlighted in bold font. As can be seen from the tables, all algorithms could solve the nonlinear problems within limited time, the average running time Aver-R and the shortest running time Best-R increase from 60 dimensions to 100 dimensions because more dimensions need to be updated for all algorithms.

For functions f₃(x), f₅(x), f₆(x), f₇(x) and f₈(x), the values of all four indices in each dimension corresponding to IMABC are smallest, which means IMABC possesses the highest optimization accuracy, the fastest convergence speed as well as the best stability when solves the above functions. Another improved algorithm RmdABC gets smaller fitness values and Mean ± std dev values, but it takes longer time compared with the one of ABC. On the other hand, it improves the optimization efficiency of fdABC at the expense of a worse solution. In other words, RmdABC balances the exploration and exploitation abilities of fdABC and ABC.

In addition, IMABC obtains the lowest values of Mean ± std dev and Best-F, but it takes longer running time to obtain optimal solution than ABC algorithm for f₂(x), which means that the stability and global search ability of IMABC are the best, while its convergence performance is better than fdABC and RmdABC because it updates less dimensions. Besides that, as the results of optimizing functions f₁(x), f₄(x) and f₉(x), fdABC obtains the best fitness value as well as best stability among all algorithms as it executes full-dimensional search and IMABC takes much less time to get the optimal solution.

The curves of fitness values for functions f₃(x) under different dimensions are depicted as Figures 4–6, and the same conclusions as mentioned above could be obtained.

From the analysis above, it can be seen that the proposed IMABC algorithm is able to produce better solutions with higher stability compared with ABC, and costs shorter computational time than other improved algorithms. RmdABC which is deduced from fdABC could reduce its time cost, but the quality of solution becomes poor because it updates less dimensions. Therefore, the proposed IMABC and RmdABC algorithms can balance exploration and exploitation abilities of ABC and fdABC.

4.   Task set schedule with improved ABC algorithms

The performance of proposed algorithms has been evaluated by solving complex mathematical problems above, and they will be applied to solve the scheduling problem in the container storage area of Luoyang Beijiao Airport in this section.

There are 16 entrances and exits in the container storage area of the airport station, the entrance coordinates are R₁ (1-1-5), R₂ (1-1-15), R₃ (2-1-20), R₄ (1-1-25), R₅ (1-1-30), R₆ (1-1-35), R₇ (1-1-40), R₈ (1-1-50) and R₉ (1-1-60), and the exit coordinates are C₁ (1-1-8), C₂ (1-1-18), C₃ (1-1-28), C₄ (1-1-38), C₅ (2-1-48), C₆ (1-1-53) and C₇ (1-1-58), where R₃, C₅ are I/O ports at the landside, and the rest are I/O ports at the airside. The first value in the bracket represents the row number of the shelf, the second value indicates the number of layer and the third value is the number of column. Table 7 depicts the assigned positions and current positions of 60 tasks needed to be scheduled, where the first 30 ones are input tasks, and the last 30 ones are output tasks.

For this constrained optimization problem as shown in Eqs (1) and (2), the solution is the sequence of inbound and outbound tasks with dual ETVs, which corresponds to the minimum total time cost as Eq (1). In other words, it is a discrete optimization problem, integer encoding scheme mentioned in ^[27] is introduced and random numbers between -10 and 10 are assigned to each dimension of the optimized solutions, after sorting them in ascending order based on their values, the corresponding scheduling scheme as well as the optimal solution could be obtained. Furthermore, the constraint conditions as Eq (2) should be checked for each obtained scheduling scheme in the iterative optimization procedure. If the constraints corresponding to the generated solution are satisfied, the solution will be saved and used for further exploration, otherwise a new solution needs to be introduced.

Comparative studies among four algorithms, including ABC, fdABC, RmdABC and IMABC, are executed for the above scheduling problem. The swarm size of all algorithms is set to 200 with 60 dimensions, the maximum local search time is 50, the stopping criterion is set to 1000 generations. Initial populations are generated through uniformly random sampling from the search space. Each algorithm is independently tested 20 times. The experiments are performed with an Intel Core i7-8750H CPU and 8GB of RAM.

Table 8 presents the optimization results (fitness value which is the scheduling time corresponding to the optimal solution) in the first ten trials. It can be seen that all proposed algorithms are able to produce high-quality solutions for scheduling problem, the performance of IMABC is better than RmdABC and ABC.

Table 9 lists four important indices, they are the average time needed to execute the sequence corresponding to optimal solution in 20 trials (Avg), the fitness value of the best solution (Min), the fitness value of the worst solution (Max) and the corresponding running time (CPU time). It is clear that the last two proposed algorithms possess better performance as the first three indices decrease by 6% at most compared with ABC, but the time needed to obtain the optimal solution is longer. It means RmdABC and IMABC can keep the balance between the optimization accuracy and convergence speed compared with ABC. Moreover, because fdABC covers more dimensions than other mentioned algorithms, the fitness values are better than RmdABC, but the running time is 1.97 and 2.35 times of RmdABC and IMABC.

For the two proposed algorithms, the fitness value obtained by IMABC was a 1% reduction with respect to RmdABC and the searching time with IMABC is 83% of RmABC, obviously the optimization ability of IMABC is better than RmABC.

The conclusion also can be obtained from Figure 7 which depicts the average fitness values of the optimization problem, the curve slope of fitness values corresponding to the three improved algorithms is relatively steeper as compared with ABC, which proves their convergence. And the fitness values corresponding to IMABC converges at about 100 iterations, thus its ability of convergence could be proved.

Figure 8 and Table 10 show the corresponding trajectories of two ETVs and the sequence of task set optimized with IMABC algorithm respectively. It is clear that the dual ETVs could execute the scheduling tasks successfully without conflicting with each other.

From the above results, the following conclusions could be obtained:

1) IMABC are valid for solving the complex scheduling problem and they can improve the searching ability of traditional ABC algorithm.

2) fdABC possesses the excellent exploration ability, IMABC could keep the balance between the optimization accuracy and convergence speed compared with ABC and fdABC under this scheduling background.

3) For IMABC, with the help of the current optimal dimensions, the convergence speed could be improved compared with fdABC and RmdABC.

5.   Conclusions

In this paper, in order to improve the efficiency in the container storage area of airport cargo terminal, a study on scheduling of cargoes sequence and the action of ETV with ABC algorithms was performed. The dual ETVs scheduling model was established which considered the assignment of I/O ports as well as the trajectory of two ETVs with the constraint of avoiding collisions, and improved IMABC algorithm was proposed to solve this scheduling problem more effective. The computational experiments were carried out and the results proved the proposed algorithm could effectively avoid conflicts and generate optimal scheduling sequences.

ABC and corresponding improved algorithms have been proved to be effective in solving the scheduling problem, but the time cost for obtaining the optimal solution is high because of the iterative calculations. Improving its efficiency with appropriate methods, such as parallelization, can make the algorithm more useful especially in the scheduling problems. In addition, how to choose appropriate control parameters for different optimization issues is a problem in ABC and improved algorithms as with other metaheuristic algorithms. This problem has not been investigated sufficiently in the literature. Therefore, designing a general principle for tuning the control parameters of ABC can be addressed as a searching subject in future studies.

Acknowledgments

This work was supported by International joint research center for logistics management and engineering in Zhongyuan University of Technology, as well as the High-end foreign expert program of Ministry of Science and Technology, grant number G2021026006L; the Training Program for Young Teachers in Universities of Henan Province, grant number 2020GGJS137; the NSFC-Zhejiang Joint Fund for the Integration of Industrialization and Informatization, grant number U1709215; the Zhejiang Province Key R & D projects, grant number No. 2019C03104; the Key Scientific Research Projects of Henan Province, grant number 22A413011; Henan Province Science and Technology R & D projects, grant number 202102210135, 212102310547 and 212102210080; National Nature Science Foundation of China, grant number U1813201, 72101033 and 71831001; Beijing Natural Science Foundation Project grant number KZ202210037046; Canal Plan-Youth Top-notch Talent Project of Beijing Tongzhou District, grant number YHQN2017014.

Conflict of interest

The authors declare there are no conflicts of interest.