An Improved Multi-Objective Hybrid Genetic-Simulated Annealing Algorithm for AGV Scheduling under Composite Operation Mode

Jiamin Xiang ,Ying Zhang ,Xiaohua Cao,? and Zhigang Zhou

1School of Transportation and Logistics Engineering,Wuhan University of Technology,Wuhan,430063,China

2Hubei Plog Technology Co.,Ltd.,Wuhan,430000,China

ABSTRACT This paper presents an improved hybrid algorithm and a multi-objective model to tackle the scheduling problem of multiple Automated Guided Vehicles(AGVs)under the composite operation mode.The multi-objective model aims to minimize the maximum completion time,the total distance covered by AGVs,and the distance traveled while empty-loaded.The improved hybrid algorithm combines the improved genetic algorithm (GA) and the simulated annealing algorithm(SA)to strengthen the local search ability of the algorithm and improve the stability of the calculation results.Based on the characteristics of the composite operation mode,the authors introduce the combined coding and parallel decoding mode and calculate the fitness function with the grey entropy parallel analysis method to solve the multi-objective problem.The grey entropy parallel analysis method is a combination of the grey correlation analysis method and the entropy weighting method to solve multi-objective solving problems.A task advance evaluation strategy is proposed in the process of crossover and mutation operator to guide the direction of crossover and mutation.The computational experiments results show that the improved hybrid algorithm is better than the GA and the genetic algorithm with task advance evaluation strategy(AEGA)in terms of convergence speed and solution results,and the effectiveness of the multi-objective solution is proved.All three objectives are optimized and the proposed algorithm has an optimization of 7.6%respectively compared with the GA and 3.4%compared with the AEGA in terms of the objective of maximum completion time.

KEYWORDS AGV scheduling;composite operation mode;genetic algorithm;simulated annealing algorithm;task advance evaluation strategy

1 Introduction

The scheduling of AGVs is to dispatch a set of AGVs to complete a batch of pickup/drop-off jobs to achieve certain goals (e.g.,shortest completion time,minimum AGV idle time,etc.) under given constraints[1].The AGV scheduling problem has been proven to be an NP-hard problem,with its complexity growing exponentially with the size of the problem[2].The AGV scheduling problem has been extensively studied.On the one hand,different optimization objectives were proposed for different scenarios including flexible manufacturing systems[3–5],intelligent job shops[6],automated warehouses [7] and container terminals [8–10].On the other hand,a variety of new and improved algorithms have been proposed to optimize the solution process.The main optimization objectives are minimizing the total handling completion time [11],the shortest path cost [12],the maximum completion time [13–14],the number of AGVs [6],the total time for inbound and outbound order operations[15],the energy consumption of machines[5],carbon emission[16–18],etc.

In real manufacturing and logistics systems,there are many combinatorial optimization problems(COP) imposing on more complex issues,such as complex structure,nonlinear constraints,and multiple objectives to be handled simultaneously[19].Karimi et al.[20]established a multi-objective scheduling optimization model with the objectives of reliability and minimizing the maximum completion time of AGVs,and calculated the optimal solution of the trolley dynamic scheduling scheme based on the non-dominated sorting cuckoo algorithm and the meta-heuristic algorithm of multiobjective teaching optimization through optimal sorting of several complexity results.A multiobjective adaptive clustering genetic algorithm based on time windows and Dijkstra was proposed with the three optimization objectives of minimizing maximum completion time,AGV travel time,and total machine load,and a cross-reorganization strategy including adaptive individual cross probabilities was used to enhance the superiority of the algorithm [21].In addition to minimizing the maximum completion time and AGV travel time,Umar et al.[4]also considered the penalty cost caused by delays or conflicts,and the multi-objective fitness function was calculated using the adaptive weight method,and the genetic operator was controlled by the fuzzy expert method to adaptively control the crossover rate and mutation rate,which greatly improved the performance of the algorithm,but could only be applied with small data volumes.Yang et al.[22]also took the AGV task time penalty cost and total distance traveled as the optimization objectives and proposed the concept of a variable domain search based on the addition of an elite individual protection mechanism,which increased the volume of data in the late iteration of the algorithm and reduced the probability of prematureness of the algorithm,but the search method still had certain limitations.Devapriya et al.[23] constructed a scheduling model for product production and distribution with time constraints,with both fixed cost of vehicles and minimizing distribution time as the objectives,and considered the case of reciprocal vehicle distribution,which is solved using a heuristic algorithm combined with an evolutionary algorithm.

The genetic algorithm is one of the most popular evolutionary algorithms for finding a satisfactory solution in an acceptable time for NP-hard scheduling problems [24].An improved genetic algorithm was proposed to promote productivity efficiency in collaborative manufacturing systems[25].Morandin et al.[26]optimized the scheduling of machines and AGVs in flexible manufacturing systems.The proposed algorithm was tested in two scenarios of FMS(Flexible Manufacturing System)and validated by comparing its results with two other algorithms.A non-dominated sorting genetic algorithm(NSGA-II)was adopted to solve multi-objective scheduling problems[27].Due to the higher probability of the genetic algorithm falling into a local optimum as the population iterates,lots of hybrid algorithms have emerged for solving AGV scheduling problems.Zhong et al.[28]proposed the hybrid genetic algorithm-particle swarm optimization(HGA-PSO)with the fuzzy logic controller to realize the integrated scheduling of multi-AGV with conflict-free path planning.The multi-objective and multi-dimensional optimal scheduling process was defined while considering energy consumption and multi-function of machines and the hybrid sectional encoding genetic algorithm and the discrete particle swarm optimization(HSE-GA-DPSO)was proposed to solve it[5].Zade et al.[29]proposed a multi-objective hybrid meta-heuristic algorithm called hybrid fuzzy hitch cock bird(MOHFHB)to solve task scheduling problems.A fuzzy hybrid genetic algorithm-particle swarm optimization(GAPSO) algorithm was proposed to optimize the AGV scheduling model [30].Rao et al.introduced a developed hybrid whale and the grey wolf optimization algorithm(WGWOA)with a random forest classifier to determine the optimal subset of gait features[31].

This paper studies the AGVs scheduling problem under the composite operation mode which is more efficient than the single operation mode but lacks relevant research.Due to different operation modes,different mathematical models need to be built and effective algorithms should be applied to solve the problem efficiently.In this paper,the improved hybrid algorithm is the simulated annealing algorithm intervening in the genetic algorithm effectively,which was proposed to realize the multiobjective optimization of minimizing the maximum completion time,the total distance traveled by the AGV,and the empty-loaded travel distance.Similar hybrid algorithms have been studied and applied,but mostly in the fields of route planning and the structure of the algorithm fusion is relatively simple and usually treats the two algorithms as an inherited population,neglecting the combination of features between the two algorithms[32–33].In addition,a grey entropy parallel analysis method combining the grey system theory and the information entropy method is applied to calculate the multi-objective fitness function[34].

The main contributions of this paper are as follows:

? Firstly,a multi-objective scheduling model under composite operation mode was constructed,and a task vector was added to the model to represent the task mode.

? Secondly,an improved hybrid genetic algorithm-simulated annealing algorithm based on task advance evaluation strategy(AEGA-SA)was proposed to realize the multi-objective model.

? Thirdly,a combined coding,parallel decoding mode aiming at composite operation scheduling mode was designed and a grey entropy parallel analysis method was applied to calculate the multi-objective fitness function.

? Finally,a task advance evaluation strategy was proposed for the crossover and mutation operators of the algorithm,which can effectively improve the convergence speed of the algorithm in the early stage.

The remainder of this paper is organized as follows.Section 2 describes the problem to be solved in this paper and establishes the mathematical model.Section 3 concretely illustrates each step of the improved hybrid algorithm.In Section 4,experiments are performed to investigate the effectiveness of the proposed algorithm.Finally,Section 5 summarizes the main conclusions of this study and puts forward the potential direction of further research in the future.

2 Problem Formulation

2.1 Application Scenarios

The AGVs studied in this paper are directly oriented to shelf operations and are mainly used for loading and unloading palletized goods,aiming too low and medium-level shelves for storage of goods or oriented to loading and unloading operations in storage entrances/exits.Such a scenario can be specifically applied in the low and medium-shelf storage area of automated storage systems and storage logistics centers,product storage area of flexible manufacturing systems,etc.

AGV operation mode can be divided into the single operation mode,which refers to a single task of outbound or inbound storage,and the composite operation mode,which combines outbound and inbound storage as a single task.Due to the lack of reasonable scheduling technology,when the inbound and outbound tasks arrive at the same time,the single operation mode is generally used to partially complete the inbound task and partially complete the outbound task or to complete the two tasks one after another,which is inefficient and causes waste of resources.The composite operation mode can effectively avoid shortcomings of the single operation mode in the coordination of inbound and outbound tasks.There are two kinds of processes of composite operation:First in,last out and first out,last in.The former process is illustrated in Fig.1a:AGVs go to the inbound area to load the inbound task,run to the shelf,and put the goods into the shelf,then run to the shelf location of the outbound task and pick up the goods,and finally run to the outbound area to complete the outbound task.The latter process is illustrated in Fig.1b:AGVs first go to the shelf location of the outbound task,pick up the goods,move to the outbound area to unload goods,and then move to the inbound area to load goods to the corresponding shelf.

Figure 1:Two processes for composite operations

Raster is used to construct the map model,the specific information of each location of the raster map can be represented by a specific number and matrix,but the map information matrix can only indicate whether each raster is passable or not,so replace the original number with a particle that can store and modify information,as shown in Eq.(1):EachPin the matrix represents a particle andPxyrepresents a particle located at the horizontalxand vertical in the map,which can record information such as the coordinates of the current location,whether it is passable or not,whether it is a shelf or an entrance/exit area.

In this paper,the storage map space area is divided into four major parts: the shelf area,the out/inbound area,the aisle area and the AGV parking area,which has a certain universality,as shown in Fig.2.The blue area indicates the shelf area,where the goods are stored.The green area indicates the in/outbound area,where the operation of the goods out/in is realized.The orange area is the AGV parking area,where the idle AGV stays after completing its task.The grey area indicates the aisles where the AGVs can run,with a single lane between the rows of shelves,allowing the storage/pickup of goods from both ends of the shelves,and a double lane between the columns,allowing two AGVs to run at the same time.

Figure 2:Raster map

2.2 Problem Description

The composite operation refers to an operation mode in which the sequences of AGV inbound and outbound tasks are matched according to certain rules and are completed as a task group.In the case of inbound and outbound orders arriving at the same time,the scheduling study of the composite operation mode can improve system operation efficiency and save system resources.It is important for companies to shorten the delivery time of their products or to respond quickly to customer needs.The distance traveled by the AGVs in the warehouse operation process is closely related to the power consumption of the system.The unloaded travel distance of the composite operation mode often reflects the actual efficiency of the AGVs.The three objectives of the scheduling model optimization in this paper are:1)the time to complete all tasks should be as short as possible;2)the distance traveled by all AGVs operations should be as short as possible;3)the empty travel distance of the AGVs should be as short as possible.

2.3 Mathematical Formulation

2.3.1 Assumptions

The speed of the AGV during travel is directly related to the load status of the vehicle,the working time for pickup/drop-off is related to the lifting speed of the forks,the level and the height of the shelf on which the target goods are located,and the turning time loss is directly related to its turning radius.In addition to these factors,which are related to the performance parameters of the vehicle itself,the operational efficiency of the whole system is related to the solution of the AGV scheduling system.The following assumptions are therefore made for the calculation of the AGV scheduling process:

1) Only one pallet of goods can be handled by one vehicle at the same moment,and the AGV has sufficient power to ensure sufficient completion of the assigned tasks.2)The input capacity and output capacity of the in/outbound area are large enough.3)AGV travels at a uniform speed during its work.4)The acceleration process of the AGV is fast to neglect the loss time of the AGV from motion to rest and from rest to motion.5)AGV’s loading and unloading time in the in/outbound area is fixed.6)The lifting and lowering speed of the AGV forks is constant.7)Conflicts such as traffic collisions and deadlocks are not considered in the calculation process.8)There are five levels of shelf and the AGV can complete operations at this height.9)Each pallet task has been planned through the system with a starting and ending location.

2.3.2 Notations

Based on the above problem description in Section 2.2 and analytical assumptions in Section 2.3.1,some of the parameters and the variables involved in the scheduling problem under composite AGV operations studied in this paper are defined as shown in Tables 1 and 2.

Table 1:Definition of parameters

Table 2:Definition of variables

2.3.3 Mathematical Model

Three optimization objectives are proposed above in Section 2.2,and corresponding mathematical models are constructed regarding the paper[3]and[14]as follows:

(1)Minimizing the maximum completion time

In the composite operation mode,the completion of a task by AGV can be regarded as a cycle of three steps:inbound,empty-loaded and outbound task.A task vector is constructed to represent task mode in Eq.(5),and(1,1,1)Tindicates a complete task,including all three steps,while(0,1,1)Tand(1,0,1)Trespectively means no outbound task and no inbound task.

(2)Minimizing the total distance traveled for AGV operations

(3)Minimizing empty-loaded travel distance

In this mode the start and end positions of the AGV’s empty-loaded travel are generated in two main areas,one in the out/inbound area and the other in the shelf area.If the start and end positions are in the shelf area,the empty-loaded travel distance needs to be compensated numerically with the Manhattan distance.The compensation formulag(x) is related to the current position of the AGV and the shelf position where the dispatched task is located,as shown in Fig.3.

Figure 3:Distance compensation

As shown in Fig.3a,if the nearest shelf to the location of the AGV is not in the same row of shelves as the shelf location of the task,no distance compensation is required and the AGV travel distance is Manhattan distance.Otherwise,as shown in Fig.3b,the Manhattan distance is not the exact distance that AGV has traveled,thus a compensation distance is calculated to amend the distance and the distance compensation formula is Eq.(15).

whereμis the compensation factor,which is 0 in the case of non-essential compensation and 2 in the case of essential compensation.xijleftandxijrightare the leftmost horizontal coordinates of the shelf where taskjof AGViis located and the rightmost horizontal coordinate of the shelf,respectively.

(4)Constraints

Subject to

Constraint (16) indicates the start and the end point of the AGVs.Constraints (17) and (18)indicate that the task assignment is under the AGV capability,and Constraint (17) indicates that each AGV is performing at most one task while Constraint(18)indicates that the number of AGVs performing a task is no more than the total number of AGVs.Constraint (19) indicates the earliest time when an AGV completes the next taskshould be later than the time when the previous task is completed.Constraint(20)indicates that only one AGV is allowed to move and stop at each raster node,and the node can only be released after the AGV leaves,if there is a shelf on the node,it will always be occupied.Constraint(21)indicates that each cargo compartment of the shelf can only be placed in one kind of goods and no other goods can be placed until the goods have been picked up by the AGV.

3 Multi-Objective AEGA-SA for Composite Operation Scheduling

3.1 Improved Hybrid Algorithm Framework

The probability of the genetic algorithm falling into a local optimum would increase as the population iterates,while the simulated annealing algorithm keeps the solution in a wide interval during the computation,but lacks a mature evolutionary mechanism.This paper combines the genetic algorithm and the simulated annealing algorithm to effectively improve the solution quality of the algorithm.The framework of the hybrid algorithm is as follows: after receiving external data,the genetic algorithm is used to seek the global solution of the problem,which plays a role in exploration.In the evolutionary process,the population richness is judged by the variance of the population fitness,and when it remains low for a long time,the simulated annealing algorithm is intervened to improve the population richness,which plays a role in exploitation.The hybrid algorithm therefore makes full use of the advantages of both algorithms,so that the genetic algorithm can continue to have a rich population during the iterative process and can re-optimize the populations locally through the simulated annealing algorithm,maintaining an adequate balance between the local and global search abilities.The overall framework of the hybrid algorithm is illustrated in Fig.4.

Figure 4:Framework of hybrid algorithm

In the design of both algorithms,the framework of the genetic algorithm is dominant and the simulated annealing algorithm is supplementary.In this paper,the hybrid algorithm is improved for the case of composite operation scheduling.Firstly,this paper adapts the coding and decoding rules of the composite operation model;secondly,the paper converts the original algorithm into a multi-objective solution algorithm through the method of the grey entropy parallel analysis;thirdly,the paper adds a task advance evaluation strategy in the crossover and mutation process to speed up global exploration and local exploitation,improving the efficiency of the algorithm and the accuracy of the calculation results.The specific framework of the designed algorithm is illustrated in Fig.5.

Figure 5:Improved hybrid algorithm flow in composite operation mode

Step1:Calculate the reference sequence.Run the algorithm to obtain the optimal solution for each objective as the reference sequence for the multi-objective solution.

Step2: Task advance evaluation.The task sequence of each AGV is evaluated and ranked to facilitate the improvement of the operator crossover and mutation.

Step3: Adaptation encoding.The AGV sequences,outbound task sequences and inbound task sequences are encoded.

Step4:Initialization of populations.A certain number of initial populations are generated in the global space as initial solutions.

Step5:Initial route planning.The A?algorithm is used to carry out initial route planning for the initial population in advance,targeting the load travel of the task and improving the accuracy of the algorithm’s calculation results.

Step6:Calculate the multi-objective fitness.The grey entropy parallel analysis method is applied to calculate the multi-objective fitness function.

Step7: Improve crossover and mutation.Based on the task advance evaluation ranking results of Step2,this step combines with roulette ideas to adopt a point-to-point crossover and mutation approach.

Step8:Select the operator.Use a ranked selection strategy and the optimal preservation strategy.

Step9:Calculate the variance of the population fitness for the current generation.If the variance of 15 consecutive generations of the population is less than one-half of the mean of the variance of the previous 40 generations,enter the simulated annealing algorithm,otherwise go back to Step6.

Step10: Generate new solutions.New solutions are generated for one-fifth of the population’s chromosomes by perturbing them in three ways.

Step11: Determine if the new solution is optimized.If yes,update the chromosome directly,otherwise use the Metropolis criterion to determine whether to accept the solution.

Step12: Determine if the loop condition is met,i.e.,If the maximum number of iterations is reached,output the final solution.If not,go back to Step6.

3.2 Encoding and Decoding Design under Composite Operation

3.2.1 Combined Coding Design

To adapt to the composite operation model,the AGV sequence,the outbound task sequence and the inbound task sequence are each created with a corresponding chromosome,forming a threechromosome combination encoding model.

The number of outbound tasks may not be equal to the number of inbound tasks in the composite operation mode,so further processing of the chromosomes is required.The steps are: 1) determine whether the lengths of the two task sequences are equal,and if so,encode them directly;2)calculate the absolute value of the sequence length difference;3)create empty particles that do not contain any information,and fill the chromosomes with the number of particle genes with the absolute value for the shorter sequence length.The final encoding is shown in Fig.6.

Figure 6:Chromosome coding for the composite mode of operation

3.2.2 Parallel Decoding Design

Treating the two task chromosomes as independent individuals.The number of tasks iskand the number of AGVs ism,Eq.(22)indicates the task sequenceUifor theiAGV.

After chromosomes are decoded,the outbound task sequenceAOiand the inbound task sequenceAIifor each AGV respectively are obtained.AOi(x),AIi(x),x=1,2,...,nindicates specific tasks in the outbound and inbound task sequences andnindicates the number of tasks contained in the task sequence.

The sequencesAOiandAIiare regarded as row vectors to form a matrix of 2 rows andncolumns respectively,which are transformed into column vectors to obtain the final task sequence as shown in Eq.(23).EachUirepresents one cycle of an AGV job,and the AGV completes each operation cycle in the order of the final task sequence.

3.3 Multi-Objective Problem Approach

The grey entropy parallel analysis method combines the characteristics of the grey correlation analysis and the information entropy [34],calculates the grey correlation coefficient for the data sequence,and calculates the information entropy and the entropy weight for the data sequence in the meantime.The grey-entropy parallel correlation is obtained by combining the grey correlation coefficient and the entropy weight.The hybrid application of two methods makes up for the deficiencies of grey correlation analysis in terms of data information loss and coefficient skewing,and also provides a computational basis for the information entropy theory,which has been applied to the field of shop floor scheduling by some scholars with good results[34,35].Three parts of the greyentropy parallel analysis method are specifically illustrated as follows: the grey correlation theory,the entropy weight theory,and the hybrid of two methods.This method is particularly suitable for discrete data problems because of its low requirements for data sequence distribution.In this section,it is applied to the calculation of multi-objective solution fitness functions for AGV scheduling.The specific steps are shown below.

3.3.1 Reference Sequence Calculation

3.3.2 Grey Correlation Coefficients Calculation

The fitness sequences for each population are dimensioned to eliminate the effects of order of magnitude and dimensionality between the indicators in Eq.(24).The absolute difference between the comparison sequence and the corresponding element of the reference sequence is calculated by taking the maximum and minimum difference between the two data as in Eqs.(25)and(26).The grey correlation coefficient is calculated as in Eq.(27)whereρtakes the value of 0.5.

3.3.3 Entropy Weights Calculation

The dimensioned data is normalized in Eq.(28)and the data weight matrix of theYis obtained.Entropy values between chromosomes are calculated in Eq.(29).Entropy weights are calculated in Eq.(30).Eq.(31) indicates thatKis the Boltzmann constant and Eq.(32) indicates that the sum of the weights is 1.

3.3.4 Multi-Objective Fitness Value Calculation

The grey correlation indicates the degree of similarity between the comparison sequence of a chromosome and the reference sequence,the entropy weights indicate the influence of each objective between chromosomes,and the two are multiplied and summed to calculate the fitness value of each chromosome in Eq.(33).

wherek=1,2,...,p,i=1,2,3...,pop size,andpop sizeindicates population size.

3.4 Crossover and Mutation Based on Task Advance Evaluation

The task scheduling problem under the composite operation mode is essentially a task allocation and sequencing problem,with an additional step of inbound and outbound task matching compared to the single operation mode.The results of matching inbound and outbound tasks have different degrees of influence on the three optimization objectives and the key influence is the distance of empty-loaded travel for AGVs.For example,if an inbound task and an outbound task at the same coordinates but different levels were matched into a set of composite tasks,the distance of emptyloaded traveling can be significantly reduced compared to a single task at a time.Therefore,a strategy for the advanced evaluation of composite tasks is proposed to improve the crossover and mutation process of the algorithm.

The strategy is divided into three main steps.Firstly,the advanced evaluation of tasks.Secondly,the roulette of the evaluation results.Thirdly,the specific process of crossover and mutation.

3.4.1 Advance Evaluation of Tasks

The evaluation steps devised in this paper are shown in Fig.7.

Figure 7:Flow of evaluation process

The sequences of inbound and outbound tasks for each AGV are denoted asAOi={b1,b2,...,bk}andAIi={c1,c2,...,cn},respectively,and the distances and the numbers of turns between all tasks ofbkandAIiare calculated in advance based on the A?route planning algorithm to form the cost matrixQk×nofk×nin Eq.(34).

Eq.(35) indicates the calculation of the cost,wherelknandzknindicate the distance of the route and the number of turns,respectively,andεindicates the turning penalty cost factor,which is 3 in this case.

Sorting each column ofQk×nin descending order gives the evaluation ranking of taskbifor all tasks in the inbound task sequenceAIi.

3.4.2 Roulette of Evaluation Results

The advance evaluation of tasks provides direction for the algorithm to evolve in the process of producing new chromosomes.After the evaluation of tasks,each task is given a sequence of all task ordering levels on another chromosome,which is assumed to bebci=An example of the results is illustrated in Fig.8.

Figure 8:Example of task evaluation results

The idea of roulette is applied to select particles and particles with a higher rating are more likely to be selected.The calculated cost of each element in thebcisequence is assumed asqbi=Eq.(36)indicates that each element is negatively indexed.Eq.(37)indicates thatyjis normalized to obtain the probability of each elementEq.(38)indicates that the cumulative probability of each elementis calculated:

where j=1,2,...,n.

3.4.3 The Specific Process of Crossover and Mutation

Since particles with null information may be present in the chromosome,a mixture of point-topoint and task-advanced evaluation crossover strategies is applied.A select factor?is set in Eq.(39),which is used to select the crossover strategy.In this equation,numdenotes the current evolutionary generations andGedenotes the maximum number of iterations.

The crossover strategy based on evaluation results in Section 3.4.2 is mainly adopted in the early stage of algorithm convergence,while the point-to-point crossover strategy is mainly adopted in the middle and late stages of the algorithm to avoid forced perturbation leading to the destruction of the algorithm evolutionary law and premature convergence into local optimum.The random numberRis generated using the Rand class,and the point-to-point crossover strategy will be adopted ifR>?while task advance evaluation crossover strategy will be adopted ifR

Mutation operation based on the evaluation results is implemented in such a process.Firstly,two random numbersr1andr2are generated for the chromosome group without null information particle gene chromosome,and the two genes at that position are exchanged for the position.Secondly,random numbersr3andr4are generated,wherer3∈(0,1),r4∈(0,1),and the roulette idea is used to select the tasks in the evaluation sequence and find their respective positionsr5andr6,which are exchanged point to point again,which is illustrated in Fig.9.

Figure 9:Improved mutation under composite operation

4 Computational Experiments

The optimization effect of the improved algorithm and the validity of the multi-objective solution approach are verified and analyzed respectively in Sections 4.1 and 4.2.The multi-objective advance evaluation strategy genetic algorithm-simulated annealing(AEGA-SA)solution for composite operation scheduling algorithms described in Section 3 is implemented in the visual studio 2022 software platform in C#programming language.

4.1 Algorithm Improvement Validation

This section selects three kinds of algorithms to compare the convergence speed and solution results.They are the genetic algorithm (GA),the AEGA (advance evaluation strategy genetic algorithm)and the AEGA-SA(advance evaluation strategy genetic algorithm-simulated annealing).Computational simulation experiments are conducted to verify the effectiveness of the improved hybrid algorithm.The number of AGV is 10,and the settings of all parameter values are shown in Table 3.

Table 3:Parameters

The comparisons of the convergence curves of GA,AEGA and AEGA-SA are shown below.The maximum completion time is shown in Fig.10,the total distance traveled for AGV operations is shown in Fig.11 and the empty-loaded travel distance is shown in Fig.12.

Figure 10:Comparison of maximum completion time

Figure 11:Comparison of total distance traveled for AGV operations

Figure 12:Comparison of empty-loaded travel distance

The comparisons of the above three computational experimental results can draw the following conclusions:

Comparing GA and AEGA,GA converges incompletely and more slowly,while AEGA converges faster in the early stage.Therefore,the task advance evaluation strategy can help the genetic algorithm to calculate the optimal solution faster in the composite operation mode and ensure that the algorithm reaches the convergence state within a specified number of iterations.However,AEGA still suffers from a tendency to fall into a local optimum.

Comparing AEGA and AEGA-SA,the convergence speed gap between them is very small in the early stage,and AEGA is even better than AEGA-SA in the total travel distance.However,AEGA-SA outperforms SA and AEGA in solving the optimal solution for all three objectives,and can optimize the original solution again in the middle and late stage of evolution,especially for the solution with the maximum completion time as the objective.Thus,the improved hybrid algorithm remains the advantage of fast convergence in the early stage of the AEGA with the addition of the task advance evaluation strategy and remains the ability of the hybrid algorithm(GA-SA)to locally optimize the solution again in the late stage of evolution.

As the improved hybrid algorithm is not designed to simply fuse the two algorithms in the form of inherited solutions,it uses the richness of the populations as the criterion for judgment,and the simulated annealing algorithm is organically intervened in the evolutionary process of the genetic algorithm.This step not only preserves the global solving capability of the genetic algorithm,but also gives full play to the local solving capability of the simulated annealing algorithm.The task advance evaluation strategy is proposed for the crossover and mutation operators of the algorithm,which can effectively improve the convergence speed of the algorithm in the early stage,and then cooperate with the local optimization-seeking ability of the hybrid algorithm to complete the local solution of the algorithm in the late stage,improving convergence speed more obviously.The experimental results show that both the speed and the capability of solving all three objectives of the AEGA-SA have been improved.

4.2 Multi-Objective Algorithm Validation

The grey entropy parallel correlation is regarded as the fitness,the three algorithms are compared and analyzed,where the data volume type is expressed in the form of number of outbound tasks,number of inbound tasks × number of AGVs shown in Table 4,and the reference sequences are constituted by solving each objective 20 times to obtain its optimal solution,respectively,and the optimal solution is obtained from the multi-objective algorithm solving 10 times.

Table 4:Comparison of results of multi-objective composite operation algorithms

There are two indicators to evaluate the effectiveness of the multi-objective algorithm under the grey entropy parallel analysis method,which are the generation distance (GD) and the progress measure (PM) [34].The former evaluates the distance between the non-inferior sequences and the reference sequences and can be used as an indicator of the convergence efficiency of multi-objective algorithms,as shown in Eq.(40).The latter evaluates the relative convergence of algorithms,in general,the smaller the PM,the better the convergence of the algorithm,as shown in Eq.(41).

whereWmaxis the number of non-inferior sequences in the set,taken as 50,anddiis the Euclidean measure of the non-inferior sequencesiagainst the reference sequences.

whereψ1,ψgenrepresent the value of the maximum grey entropy parallel correlation achieved in the first and the last iteration of algorithms.

As shown in Table 4,for the multi-objective composite operation scheduling problem,the grey parallel correlations obtained by the three algorithms remain above 0.8,and all of them can achieve good results.On the one hand,this is because the three objectives have a linear pattern,and on the other hand,it also shows that the grey entropy parallel analysis method has an exchange promotion effect on the whole population.When the task size is small,the grey entropy parallel correlations of the three algorithms can reach above 0.9,which is very close to the solution of the reference sequences.When the maximum number of iterations is 500,the grey entropy parallel correlations decrease as the task size increases.

Taking AEGA-SA as an example,when the data volume increases from (20,20) × 5 to(350,350)×8,the grey entropy parallel correlations decrease from 0.9748 to 0.9058.This is because the algorithm takes a longer time to evolve as the amounts of computation increase,and the number of iterations is insufficient,resulting in low results.After adjusting the maximum number of iterations to 1000 and increasing the data type volume to(450,450)×10,the grey entropy parallel correlation increased again to 0.9316 and the algorithm regained good results.

As shown in Table 5,comparing the results of the three algorithms with data volume,the results of the AEGA are better than the GA.According to the GD,the sets of non-inferior sequences obtained by the AEGA are smaller than those of the GA,which means that the AEGA can obtain better sets of non-inferior sequence solutions.According to the PM,the results of the AEGA are smaller than the GA,which indicates that the convergence effect of the AEGA is better,indicating that the intervention of the task advance evaluation strategy enables the algorithm to iterate faster and ensures the algorithm enough time for local optimization at the late stage.AEGA-SA,on the other hand,is further improved compared to the AEGA because it inherits the advantages of AEGA’s fast convergence and integrates the local optimization capability of the SA.According to the GD,AEGASA has a higher probability of being the smallest among the three algorithms,which is because the algorithm not only has sufficient local optimization time but also better local optimization capability,providing high-quality non-inferior solutions for the non-inferior solution sets.Moreover,the PM is further improved based on the AEGA,which is due to the advantages of local optimization in the middle and late iteration of the hybrid algorithm.

Table 5:Comparison of evaluation indicators

Zhu et al.[35]have demonstrated the ability of the genetic algorithm to solve multiple objectives under the grey entropy parallel analysis method and this paper provides a further enhancement to the algorithm’s solving ability after an improvement of the genetic algorithm and the fusion with simulated annealing.

5 Conclusion

This paper deals with the multi-objective scheduling problem of AGVs under the composite operation mode.The AEGA-SA has been proposed to realize the multi-objective model.Specifically,a grey entropy parallel analysis method was applied to calculate the multi-objective fitness function.

Additionally,this paper proposed a task-advance evaluation strategy to guide the crossover and mutation of operators,aiming to improve the convergence rates and solution accuracy of the algorithm.The computational experiments have shown that the convergence rate of the AEGA-SA was faster than the other two algorithms in most cases and the convergence results of the AEGA-SA for all three objectives were better than the other two algorithms.Particularly,AEGA-SA achieved a 7.6%improvement over GA and a 3.4%improvement over AEGA in terms of the objective of the maximum completion time.Moreover,the analyses of GD and PM also demonstrate that the ability of multi-objective solution algorithms has been comprehensively enhanced.

However,the proposed algorithm has some shortcomings.The convergence speed did not show significant improvement when compared to AEGA.Meanwhile,since the emphasis of this paper is on the elaboration of the multi-objective improved algorithm and the comparisons of three algorithms,the time complexity has not been analyzed in detail.The integration of other algorithms and the analysis of time complexity can be considered in future research.

Acknowledgement:The authors would like to thank the editor and the anonymous reviewers whose comments helped considerably in improving this paper.

Funding Statement:This work is funded by the Shandong Province Key Research and Development Program under Grant No.2021SFGC0601.

Author Contributions:The authors confirm contribution to the paper as follows:study conception and design:J.M.Xiang,X.H.Cao;computational experiments:J.M.Xiang;analysis and interpretation of results: Y.Zhang,Z.G.Zhou;draft manuscript preparation: Y.Zhang,J.M.Xiang.All authors reviewed the results and approved the final version of the manuscript.

Availability of Data and Materials:The source code for this article is currently not available on the website.This work is funded by the Shandong Province Key Research and Development Program and we need to ask for permission to release it online.

Conflicts of Interest:The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.