To meet the production demand of workshop, this paper proposes an efficient discrete artificial bee colony (DABC) algorithm to solve a new automatic guided vehicle (AGV) scheduling problem with delivery and pickup in a matrix manufacturing workshop. The goal is to produce a AGV transportation solution that minimizes the total cost, including travel cost, time cost, and AGV cost. Therefore, a mixed integer linear programming model is established. To improve the transportation efficiency, a dynamic calculation method is developed. In the DABC algorithm, a heuristic algorithm and a median based probability selection method are used. For improving the quality of the solutions, four effective neighborhood operators are introduced. In the local search, a rule is given to save the operation time and a problem-based search operator is proposed to improve the quality of the best individual. Finally, a series of comparison experiments were implemented with the iterative greedy algorithm, artificial bee colony algorithm, hybrid fruit fly optimization algorithm, discrete artificial bee colony algorithm, improved harmony search, and hybrid genetic-sweep algorithm. The results show that the proposed DABC algorithm has high performance on solving the delivery and pickup problem.
Notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Introduction
With the continuous development of intelligent manufacturing industry, it is important to complete matrix intelligent workshop transportation with the help of automation equipment. As a new type of transport tool, AGV is considered ideal for material transportation in workshops because of its high flexibility, safety, and utilization [1‐3], and can transport different materials and finished products. With the expansion of the matrix workshop and the diversification of customer needs, the transportation of many kinds of materials and products has become more complex [4]. Multi-AGV scheduling for transporting mixed materials can better solve the complex transportation problems in the workshop [5], which is conducive to improving the transportation efficiency of AGVs and reducing transportation costs [6]. The AGV scheduling problem of delivery and pickup (AGVSPDP) involves assigning the material required by different machines to the appropriate AGVs, and determining the corresponding scheduling sequence on each AGV, the specific process is as shown in Fig. 1. How to effectively schedule AGVs and achieve a more flexible and efficient scheduling solution has become an important issue that needs to be addressed in this paper.
Fig. 1
The AGV scheduling problem of delivery and pickup
×
With the trend of diversification of customer needs, the matrix manufacturing workshop with sub-regional production has become an important solution to meet production needs. the workshop is divided into M areas, each area needs different materials for the production. When the workstations in each area sends a signal for delivery or pickup, the AGVs start from the warehouse and arrive at each workstation to service according to the route. Finally, they return to the warehouse. The vehicle routing problem (VRP) is to organize appropriate traffic routes for a series of loading and unloading points so that vehicles pass through them in an orderly manner [7‐9]. The route should have the same starting point. AGVSPDP is a variant of VRP. The main goal of VRP is to reduce travel cost [10]. Considering the actual matrix workshop, in addition to the travel cost, the price of AGV is very expensive, so we need to consider the cost of AGV. To ensure the production efficiency, time cost is also a very important factor. Therefore, this paper takes minimizing the total cost as the optimization goal, including the following three indicators: travel cost, time cost and AGV cost.
Advertisement
Based on the above description, it is necessary to use meta-heuristic or heuristic algorithm to solve the AGVSPDP. Among the existing algorithms, Due to the performance characteristics of discrete artificial bee colony algorithm (DABC) with few parameters and easy implementation [11‐13]. This paper uses DABC algorithm to solve AGVSPDP. To make DABC algorithm more suitable, some effective methods have been adopted. To improve the transportation efficiency, a dynamic calculation method is developed. A heuristic algorithm and a median based probabilistic selection method are used. A new variable \(\theta\) is used to record the number of iterations of unimproved individuals. In addition, four effective neighborhood operators are introduced, and a problem-based search operator is proposed to improve the quality of the best individual.
The rest of the paper is organized as follows: In Sect. "Literature review", the relevant literature is reviewed. In the Sect. "Problem description and formulation", the AGVSPDP is described, and a mixed integer linear programming model is established. The optimization strategies and algorithm are introduced in Sect. "The proposed discrete artificial bee colony algorithm". The calculation results and comparison are shown in Sect. "Statistical experiments". The last section summarizes the paper and makes a vision.
Literature review
In recent years, workshop automation has continuously attracted more and more interest of scholars. The AGV scheduling problem in the intelligent automatic workshop has also become a hot research topic. We analyzed the AGV scheduling problem (AGVSP) and vehicle routing problem (VRP) which are closely related to AGVSPDP.
For AGV scheduling problems, the traditional first-come-first-served (FCFS) heuristic cannot be ignored, but the scheduling results cannot meet the needs of intelligent workshop. Scholars use heuristic algorithms and meta-heuristic algorithms to solve such complex problems. Farooq et al. [14] proposed a heuristic algorithm based on multiple AGVs assignments to prevent collisions and deadlocks. Chawla et al. [15] applied natural heuristic algorithm and priority scheduling rules solving AGV scheduling problems. Fazlollahtabar and Hassanli [16] aken time and cost attributes into consideration, configured a path according to the earliest delivery time rule. Li et al. [17] used the harmony search algorithm to optimize the tasks waiting time and total distance. Xu et al. [18] proposed a two-layer algorithm to minimize the completion time of AGVs. Zou et al. [19] developed a DABC algorithm with the goal of minimizing transportation costs. Later, Zou et al. [20] proposed an efficient iterative greedy algorithm to solve the scheduling problem of multi-compartment AGVs. In addition, hybrid fruit fly algorithm [9], genetic algorithm based on time window [21], two-stage taboo search algorithm [22], simulated annealing algorithm [23], particle swarm optimization algorithm [24], etc., have also been applied to AGVSP.
Advertisement
The AGVs delivery and pickup problems mentioned in the previous section are the variants of the VRP. For the VRP, to solve larger and more complex instance problems, Wang et al. [25] used a two-stage heuristic method to optimize the average loading rate of the delivery process. Montero et al. [26] considered the priority customers and proposed an integer linear programming to solve the VRP with pickup and delivery. Dechampai et al. [27] proposed a differential evolution algorithm to solve the mixed pickup and delivery services. Silvestrin et al. [28] proposed a taboo search algorithm to optimize the total distance for the delivery of materials. Exposito et al. [29] developed a hybrid meta-heuristic method to reduce the service time of vehicle delivery and pickup. Wu et al. [30] proposed a VRP with time Windows, used ant colony algorithm to reduce the vehicle number.
The DABC algorithm was first proposed by Pan et al. [31] to solve the flow shop scheduling problem. Later, Gong et al. [32] used DABC to solve the multi-objective blocking batch flow shop scheduling problem. Pan et al. [33] solved the distributed permutation flow shop scheduling problem with minimum total flow time. Meng et al. [34] proposed a hybrid ABC algorithm to solve the flexible job shop scheduling problem. Tasgetiren et al. [35] used DABC to solve the no-idle flow shop scheduling problem. Guo et al. [36] proposed a DABC to solve the problem of path planning. DABC algorithm performs well in flow shop scheduling and job shop scheduling. Given the remarkable achievements of these papers, it provides us with a promising opportunity to exploit a variant of the DABC algorithm.
A review of the relevant literature shows that there are fewer studies on solving both the delivery and pickup of AGVs. However, this problem is an inevitable problem in real matrix workshops and has practical significance. Therefore, we use a heuristic algorithm based on relaxation time and a DABC algorithm to solve the AGVSPDP.
Problem description and formulation
Problem description
As shown in Fig. 2, a matrix manufacturing workshop is divided into several areas, each of which needs different materials for production. Each area has several workstations arranged in a matrix pattern. Each workstation consists of several CNC machines and a material buffer. CNC machines are used to produce products by consuming materials stored in a buffer. When the consumed material or stock of products reaches a predetermined value in the buffer, the workstation will send a signal to the AGV system to request a delivery or pickup service. This workstation is called customer or call-workstation. The time of the signal sent by the customer is denoted by call-time. After the AGV system receives the signal, the system calculates the solution according to the demand of customers and the number of AGVs, then the AGVs start to serve the customers. Travel costs are calculated for each AGV. The AGV cannot arrive later than the time required by the customer, otherwise the CNC machines will be shut down. However, there will be a time cost if the service is advanced, and the time cost will vary according to the degree of advance service. The AGV returns to the warehouse after the service is completed. So how to allocate AGVs and distribution sequences to minimize travel cost, time cost and AGV cost is an important criterion for evaluating service solution.
Fig. 2
The arrangement of workstations in a matrix manufacturing workshop
×
In the production process, it would be a waste of resources for the AGV system to send an AGV to serve the customer as soon as it receives the signal. Therefore, the entire production time can be divided into consecutive production cycles as shown in Fig. 3. Each production cycle, e.g. s and s + 1, consists of a computation stage and a transportation stage, respectively. Where the customers collected in cycle s will be calculated and transported in cycle s + 1. In calculation stage, the AGV system generates a solution. In transportation stage T0, AGVs deliver material or pick up production based on the solution. According to the divided cycle, one AGV can serve multiple customers, which greatly reduces the number of AGVs.
Fig. 3
Division of production cycle
×
To ensure the generality of the problem, we make the following assumptions:
All equipment in the matrix manufacturing workshop can operate normally.
The AGVs do not have collision, breakdown, and other accidents.
The AGVs have the same specifications.
The speed of the AGV remains constant.
Same loading and unloading times for AGVs.
The same route can only be passed by one AGV.
One AGV can serve one customer at a time.
Mathematical formula
To solve the problem of AGVSPDP, we have established a mathematical model, and the symbols used are described in Table 1.
Table 1
Variables and implication
Variables
Implication
\(v\)
The speed of the AGV
\(C\)
A production cycle
\(Q\)
Load capacity of AGV
\({t}_{u}\)
Loading and unloading times per customer
\({c}_{\mathrm{ser}}\)
The unit cost of AGV travel distance
\({c}_{\varepsilon }\)
The cost of an AGV
\({c}_{\epsilon }\)
The time penalty coefficient for early service less than 100 s
\({c}_{\eta }\)
The time penalty coefficient for early service greater than 100 s
\(i,j\)
The identity of customer
\({p}_{i}\)
The location of customer \(i\)
\({x}_{i}\)
The x-axis of \({p}_{i}\)
\({y}_{i}\)
The y-axis of \({p}_{i}\)
\(n\)
The number of customers
\(k\)
The current AGV (or AGV route)
\(\Upsilon \)
The material types
\({t}_{m}^{\Upsilon }\)
The consumption time per slice material
\({S}^{\Upsilon }\)
The buffer can accommodate the weight of material ϒ
\({S}_{i}^{c}\)
The buffer inventory of material
\({T}_{i}^{c}\)
The call-time of the customer \(i\)
\({T}_{i}^{l}\)
The time of the AGV arrival to customer \(i\)
\({n}_{i}^{p}\)
Number of produced by customer \(i\)
\({\mathrm{g}}^{\upgamma }\)
The weight of each piece of material ϒ
\({x}_{ijk}\)
1 if route exists between customer i and customer j, 0 otherwise
\({e}_{ijk}\)
1 if the advance service time is less than 100 and 0 otherwise
To solve the AGVSPDP problem, we define an undirected graph \(G = \{ V,E\}\). In \(V = \{ 0,1, \ldots ,n\}\), 0 means warehouse, 1… n mean customers. \(E = \{ (i,j)|i,j \in V,i \ne j\}\) represents the route between customers i and j. n customers \((N = \{ 1, \ldots ,n\} )\) are assigned to k\((K = \{ 1, \ldots ,k\} )\) AGVs.
The travel distance between customer i and customer j is calculated using the following formula:
AGV starts from customer i and arrives at customer j. The arrival time can be expressed by the following formula:
$$ T_{j}^{{{\text{arr}}}} = T_{i}^{{{\text{arr}}}} + t_{u} + t_{ij} ,\quad \forall i \in V,\;j \in V\backslash \{ 0\} ,\quad i \ne j. $$
(3)
When the customer j sends the signal, the CNC machines still consume the material. To ensure that the buffer is full of material when the AGV completes its service, the loading capacity can be calculated according to the following formula:
The optimization goal consists of travel cost, time cost and AGV cost, which are calculated as follows, where the time cost is divided into two calculations according to the advance service:
In this model, constraint (10) indicates the existent route between customer j and customer i that is served by only one AGV. Constraint (11) indicates the existent route between customer i and customer j that is served by only one AGV. Constraint (12) means that the service route and the return route of the AGV are the same. Constraint (13) specifies that the starting and ending point of the AGV is the warehouse. Constraint (14) indicates the time for the AGV to arrive at customer i, the time to unload the material, and the travel time between customers i and j. The sum of these three parts is the time for the AGV to arrive at customer j. Constraint (15) is a capacity constraint, which means that the loading capacity of the AGV cannot be overweight. Constraint (16) is a time constraint, which means that the AGV must arrive at the customer no later than the time requested by the customer and no earlier than the call-time by the customer, and constraint (17–19) add constraints to the decision variables.
The proposed discrete artificial bee colony algorithm
To address the problem in this paper, we propose a new DABC algorithm. In this section, the representation of the solution is first described. Then, a dynamic calculation method, four neighborhood operators, and the detailed procedures of the DABC are introduced. Finally, we give the process of solving AGVSPDP.
Representation of the solution
We use a simple one-dimensional sequence representation. Suppose there are n customers sending signals for service that needs to be allocated to k AGVs. Customers are added to the AGVs in order of service, with 0 spacing between each AGV sequence. For example, in Fig. 4, there are 11 customers \((s_{1} ,...s_{11} )\) and 3 AGVs \({\text{(AGV}}_{1} ,{\text{AGV}}_{2} ,{\text{AGV}}_{3} )\) are needed. \(AGV_{1}\) service order \((s_{11} ,s_{6} ,s_{5} )\), \({\text{AGV}}_{2}\) service order \((s_{1} ,s_{8} ,s_{10} ,s_{9} ,s_{7} ,s_{4} )\),\({\text{AGV}}_{3}\) service order \((s_{2} ,s_{3} )\). Then the solution can be expressed as \((s_{11} ,s_{6} ,s_{5} ,0,s_{1} ,s_{8} ,s_{10} ,s_{9} ,s_{7} ,s_{4} ,0,s_{2} ,s_{3} )\).
Fig. 4
The route partitioning for AGVs
×
A dynamic calculation method
In the matrix manufacturing workshop, if a customer sends a delivery signal, the materials will be loaded into the AGV. If it is a pickup signal, the space for product will be reserved in the AGV. This method is a static assignment. To effectively reduce the cost of AGV, each AGV can serve as many customers as possible. And for AGVSPDP, it is very difficult for one AGV to serve all the customers on time. Based on the above and the actual situation of the workshop, if a strategy is used to insert more customers into the static allocation, then the time cost and AGV cost can be effectively reduced by serving more customers within the limited transportation time. Therefore, a dynamic calculation method is proposed.
Assuming that an AGV passes the customer i with a full load. Customer i requires \(q_{i}^{\Upsilon }\) weight material. Consider the dynamic process, after serving customer i, if the product weight of customer j less than \(q_{i}^{\Upsilon }\). The AGV will pick up the product under the premise of meeting the time constraint. In other words, customer j can be added to the AGV route. So dynamic collection enables AGVs to serve more customers. The calculation formula as follows.
The weight of products of customer j can be expressed as:
$$ w_{p} = n_{j}^{p} g^{\Upsilon } . $$
(20)
Before serving customer i, the loading capacity of AGV:
If customer i meets the conditions of formula (22) or (23), it will be served by AGV.
$$ q_{i}^{\Upsilon } { + }Q_{i} \le Q, $$
(22)
$$ w_{p} + Q_{i} \le Q. $$
(23)
A heuristic algorithm based on relaxation time
The premise of AGV delivery and pickup in matrix manufacturing workshop is the selection of AGVs to the customer. The commonly method is to select based on the time order in which the signal was sent, the other one is based on the nearest distance. However, in this paper we need to consider both travel costs and time costs, so a heuristic algorithm based on relaxation time (RT) is constructed. The calculation method of relaxation time is shown in the following formula (24):
where \(C_{{{\text{last}}}}\) represents the latest service time, \(C_{{{\text{send}}}}\) represents the call-time.
To a large extent, the relaxation time reflects the urgency of the customer. The shorter the relaxation time, the higher the priority and the greater the possibility of being selected. In addition, we should also follow the principle of the centralized selection of customers. The centralized selection can effectively reduce travel costs. According to the above description, the concrete method of construction is as follows:
The relaxation time for each customer is calculated and stored. Select an AGV as the current AGV route. Select the customer which is with the shortest relaxation time as the current customer and add it to the AGV route. If the constraint condition (15) and (16) are met, select the customer closest to the current customer from remaining customers, add it to the AGV route and make it as the current customer. Otherwise, add a new AGV route, repeat the above process until all the customers are assigned. The process is shown in Algorithm 1.
×
Initial population
The DABC belongs to the meta-heuristic algorithm of the population, so the high quality and diversity of the population can often faster make the algorithm closer to good results. The algorithm starts from PS initial solutions. To improve the quality of the population, the RT heuristic algorithm is used to generate an individual. Other individuals are randomly created to ensure the diversity of the population. The algorithm of random generation is shown in Algorithm 2.
×
Neighborhood operator
The insert and swap are two commonly used operators in the scheduling literature [37, 38]. For adapting characteristics of the problem considered in this paper, four new operators are designed. The first two operators are based on insert, and the others are based on swap. Details of the operation are as follows:
(1) The Inner_AGV_Insert
In an AGV route, randomly select two positions, pos1 and pos2, and insert the customer on pos2 into pos1 (as in Fig. 5). A new solution is obtained.
Fig. 5
The Inner_AGV_Insert
×
(2) The Outside_AGV_Insert.
Select two different AGV routes at random. In each AGV route, a position pos1 (pos2) is randomly selected. The customer on pos2 is extracted and re-inserted into position pos1 to obtain a new solution (as in Fig. 6).
Fig. 6
The Outside_AGV_Insert
×
(3) The Inner_AGV_Swap.
Two positions pos1 and pos2 on the same AGV route are randomly selected. Customers at these two positions are swapped to get a new solution (as in Fig. 7).
Fig. 7
The Inner_AGV_Swap
×
(4) The Outside_AGV_Swap.
Select two different routes at random. A position pos1 (pos2) is selected for each AGV route. Swap the customers in these two positions and get a new solution (as in Fig. 8).
Fig. 8
The Outside_AGV_Swap
×
To effectively reduce the number of infeasible solutions, we propose the following rule to ensure the AGV can be applied to each production cycle:
Rule: If \(T_{i}^{l} + d_{j} /v < C\) is satisfied, it is a feasible solution.
Explain: The AGV completes the service of all customers and returns to the warehouse within the cycle \(C\), which proves to be a feasible solution. The return time is \(d_{j} /v\), the transportation time of AGV is \(T_{i}^{l} + d_{j} /v\).
Employed bee phase
Two variables \(\theta\) and \({\text{count}}\) are defined. \(\theta\) is used to record the number of iterations of unimproved individuals and \({\text{count}}\) is the number of times a neighborhood operator is executed. The role of the employed bee is to exploit locally within the neighborhood of the individuals [15]. We assign all the individuals from the initial population to employed bees, then select a random neighborhood operator (see Sect. "Neighborhood operator") for exploitation. Record the cost of the changed AGV routes and replace them if they are less than the original cost: otherwise \(\theta = \theta + 1\). Until the number of iterations satisfies \({\text{count}}\).The process is shown in Algorithm 3.
×
Onlooker bee phase
The onlooker bee should select individuals with potential [39]. To avoid the problem of local optimum caused by too fast convergence, a median-based probabilistic selection method is used, as shown in formula (25). Then one of the neighborhood operators in Sect. "Neighborhood operator" is randomly selected to optimize the selected individuals. At this phase, we use the parameter onlook as the termination condition as follows:
where \(F_{i}\) is the total cost of the current individual, and \({\text{mid}}\) is median total cost of population.
In addition, a problem-based search method is designed to search the best individual. Select a customer to insert it into all the locations and find the best improvement until all the customers are considered. The process is shown in Algorithm 4. There is a great opportunity to improve the quality of the population by operating with the good individual.
Scout bee phase
After going through the employed bee phase and the onlooker bee phase, we get \(\theta\) of individual. At this phase, the role of the scout bee is to discard those individuals whose \(\theta\) is greater than expect value scout and produce a new solution to replace it. The traditional DABC algorithm adopts the method of discarding directly and generating new individuals randomly. However, this process will lead to the loss of some useful information from the discarded individuals. The quality cannot be guaranteed in the randomly generated new individuals. A bad individual will waste time in the search. So, a new acceptance method is proposed. For bad individuals, we do not discard them directly, but use a local search as shown in Algorithm 4. If the local search cannot help it escape from local optimality, we will regenerate it using the RT heuristic algorithm. In this way the scout bees are directed to more promising search areas.
×
The produce of the discrete artificial bee colony algorithm
Based on the canonical DABC algorithm, an improved version of the DABC algorithm is developed for the problem. The DABC is different from the canonical DABC in that the core phase adopts different neighborhood search operators, a new acceptance method and a dynamic calculation method is embedded in the algorithm. The main process overview of DABC algorithm proposed is shown in Algorithm 5.
×
Statistical experiments
Experimental calibration
We use 110 real instances from an electronics manufacturing company. The size of each instance represents the number of customers that are signaled in a cycle. The sizes are 10, 20, 30, 40, and 50. There are 22 instances of the same size. Among them, 2 are used as calibration instances and 20 are used as test instances. For example, an instance is labeled T2008, meaning that the instance is test instance, the size is 20 and the identity number 8. If this instance were a delivery instance, it would have the customer attributes {63, 7, 3, 64.9, 307, 937, 2}. 63 means the identity of the customer. (7, 3) means the location of customer. 64.9 means the shortest distance from the warehouse. 307 means call-time. 937 means the latest delivery time. 2 means the type of material requirements. If it is a pickup instance, the customer attribute is {42, 5, 2, 45.1, 21, 621}. 42 means the identity of the customer. (5, 2) means the customer's location. 45.1 means the shortest distance from the warehouse, 21 means call-time, and 621 means the latest pickup time. For the sake of space, the remaining parameters and instances can be obtained from the authors.
We choose the 6 algorithms which are currently popular and applicable to our problem for comparison. The comparison algorithms are iterative greedy algorithm (IG) [40], artificial bee colony algorithm (ABC) [41], hybrid fruit fly optimization algorithm (HFOA) [9], discrete artificial bee colony algorithm (call DABC* in this paper) [31], improved harmony search (IHS) [42], and hybrid genetic-sweep algorithm (HGA) [43].
All the algorithms used in this paper are written in C++ and compiled and run using visual studio 2019. All the experiments are carried out on a Windows 10 laptop with an I5-6200U CPU at 2.30 GHz and 8 GB of RAM. We used the response variable based on the relative percentage increase (RPI). RPI is a commonly used method, and the smaller the RPI, the better the algorithm performance [44]. The formula as follows:
where \(C_{i}\) is the best total cost of the ith algorithm for each test instance, and \(C_{{{\text{best}}}}\) is the minimum total cost obtained by all the compared algorithms for each test instance.
It is worth noting that most of the algorithms in the literature use the number of iterations as a stopping criterion. But for AGVSPDP, we need to quickly get an excellent solution in an accurate time to improve the production efficiency. So, setting the standard stop time is \(\Delta T = 5s\). We designed each instance to be repeated 20 times independently in all experiments. The experimental results are calculated using the design of experiments (DOE) and analysis of variance (ANOVA) techniques, which are widely used in the study of scheduling problems. The experiment satisfies the normality, independence of residuals, and homoscedasticity required by the ANOVA.
The experimental calibration
In the DABC algorithm, we set four parameters, which are PS, count, onlook, and scout. PS is the size of the population. Count is the number of operator executions. Onlook is the number of cycles in the onlooker bee phase. Scout is the expected value in the scout bee phase. First, the range of parameters is determined according to the experimental experience and relevant literature. The interval of PS = 10, 50, 100, 150, count = 10, 30, 50, 70, 90, onlook = 10, 50, 100, 150 and scout = 100, 200, 300, 400, 500. So, we can get 4 × 5 × 4 × 5 = 400 combinations. Each combination needs to be run 20 times independently in 10 instances. This process will produce 4 × 5 × 4 × 5 × 20 × 10 = 80,000 results.
To set the optimal level of the parameters, a 95% LSD interval for the means plot obtained by the ANOVA is used for analysis. It should be noted that statistical significance is based on the fact that there is no obvious overlap in the plots. The results are shown in Fig. 8. In Fig. 9a, the algorithm achieves the best performance when PS = 50. From Fig. 8b–d, it can be seen that when the algorithm achieves the best performance, count = 30, onlook = 50, and scout = 300.
Fig. 9
Calibration of all parameters in DABC algorithm
×
For the above comparison algorithm, we use the same method to calibrate the parameters. Due to the length of the paper, we only present the results of the calibrated parameters, as shown in Table 2.
Table 2
The control parameters of the respective metaheuristics
Algorithms
Parameters
IG
\(d\) = 5, \({\text{s}}\) = 20
ABC
PS = 50, l = 1200
DABC*
PS = 150, l = 800, r = 80 and τ = 20
HFOA
PS = 400, α = 1, β = 2, ρ = 0.9, q0 = 0.9
HGA
PS = 200
IHS
HMS = 4, HMCRmin = 0.2, HMCRmax = 0.8
PS population size, d the number of damages, s the number of operator executions, l predetermined number of trials, r predetermined number, \(\tau \) replications, HMCR harmony memory considering rate, HMS harmony memory size, \({\text{q}}_{0}\) attraction selection threshold, \(\rho \) persistence coefficient, \(\beta \) taste strength, \(\alpha \) path strength
Computational evaluation
The performance of strategies and method
To verify the effectiveness of the proposed neighborhood operators, the proposed DABC algorithm is compared with DABC without the neighborhood operators (DABC-NO), DABC with the Inner_AGV_Insert operator (DABC-II), DABC with the Outside_AGV_Insert operator (DABC-OI), DABC with the Inner_AGV_Swap operator (DABC-IS), and DABC with the Outside_AGV_Swap operator (DABC-OS), respectively. We performed an ANOVA analysis of the experimental results. In Fig. 10, the evolutionary results of DABC-NO is worst. Four neighborhood operators have some effectiveness, but the best result is obtained by the simultaneous coordinated search of all four operators. The reason for this situation is that the instances are different and the search be in a different direction. The four operators work together to discover more directions, making the search more complete and the quality of the solution better. Thus, the neighborhood operators are effective for the DABC algorithm.
Fig. 10
Means plot and 95% confidence level HSD intervals for the neighborhood operators
×
Literature [31] is similar to the problem we studied. So, we choose DABC* in it for comparison to verify the effectiveness of the improvement of DABC. By analyzing Table 2, the DABC obtain the average RPI of all instances than DABC*, which are 0.30%, 1.55%, 4.21%, 9.09% and 3.45% respectively. we can know that the DABC algorithm is always with the better stability than DABC*. To have a clearer picture of the results shown in Table 3, in Fig. 11, the DABC generates significantly better results than DABC* in a statistical sense regardless of the size of the instances size involved. They prove that the strategies and the dynamic calculation method used in DABC are effective for solving the AGVSPDP.
Table 3
The average RPI of the DABC and DABC*
Ins
DABC* DABC
Ins
DABC* DABC
Ins
DABC* DABC
Ins
DABC* DABC
Ins
DABC* DABC
RPI
RPI
RPI
RPI
RPI
T1001
5.49
0.43
T2001
11.48
3.73
T3001
19.20
4.75
T4001
46.07
5.70
T5001
43.06
3.97
T1002
0.05
0.10
T2002
4.25
1.19
T3002
21.31
1.48
T4002
50.52
12.47
T5002
43.97
2.73
T1003
0.74
0.25
T2003
7.45
1.73
T3003
23.97
4.35
T4003
46.40
11.87
T5003
41.52
1.70
T1004
0.45
0.02
T2004
7.83
1.58
T3004
26.13
5.71
T4004
44.30
5.28
T5004
43.68
2.56
T1005
2.29
1.39
T2005
5.95
1.25
T3005
26.09
5.84
T4005
46.22
14.61
T5005
43.46
3.15
T1006
4.23
0.00
T2006
8.40
1.30
T3006
24.42
2.36
T4006
49.52
8.08
T5006
49.25
5.55
T1007
1.92
1.12
T2007
6.61
2.15
T3007
26.86
2.46
T4007
49.65
6.42
T5007
45.88
5.11
T1008
1.38
0.04
T2008
7.66
1.79
T3008
21.57
2.18
T4008
46.91
7.46
T5008
39.89
4.24
T1009
0.00
0.00
T2009
15.96
1.20
T3009
23.44
3.40
T4009
44.66
12.33
T5009
45.59
7.10
T1010
0.00
0.00
T2010
5.33
0.76
T3010
28.74
4.28
T4010
45.20
7.91
T5010
44.61
1.98
T1011
0.33
0.41
T2011
7.51
1.22
T3011
22.89
2.88
T4011
49.60
12.03
T5011
42.97
4.37
T1012
13.49
0.24
T2012
12.32
1.26
T3012
22.97
2.77
T4012
50.77
3.68
T5012
44.42
2.56
T1013
0.65
0.12
T2013
10.89
1.43
T3013
45.18
1.78
T4013
41.21
10.12
T5013
42.88
2.57
T1014
0.39
0.14
T2014
7.37
1.06
T3014
23.52
2.51
T4014
44.01
8.40
T5014
45.91
2.85
T1015
3.77
0.00
T2015
12.72
0.55
T3015
21.06
2.84
T4015
51.10
11.74
T5015
47.33
4.90
T1016
2.30
0.06
T2016
10.72
1.57
T3016
57.41
23.47
T4016
48.13
5.85
T5016
41.24
2.96
T1017
3.19
0.83
T2017
10.37
1.42
T3017
27.81
3.35
T4017
46.04
5.41
T5017
41.58
2.37
T1018
0.44
0.53
T2018
14.71
2.94
T3018
20.56
1.24
T4018
43.42
13.05
T5018
45.18
1.75
T1019
4.09
0.00
T2019
12.30
1.92
T3019
16.40
3.61
T4019
47.70
13.38
T5019
44.04
3.37
T1020
5.01
0.40
T2020
19.27
1.03
T3020
21.04
2.89
T4020
46.91
6.07
T5020
40.16
3.15
Ave
2.51
0.30
Ave
9.96
1.55
Ave
26.03
4.21
Ave
46.91
9.09
Ave
48.83
3.45
The bold values represent the optimal values in the experiment
Fig. 11
Means plot and 95% confidence level HSD intervals for the DABC and DABC*
×
The performance of discrete artificial bee colony algorithm
In this section, we prove the effectiveness and stability of DABC algorithm in the large-scale and small-scale instances by using 20 × 5 = 100 customer sizes of 10, 20, 30, 40, and 50. As mentioned above, the comparison algorithms are IG, HGA, IHS, HFOA, and ABC. All the algorithms are repeated 20 times with the same setup. The algorithm stop standard is \(\Delta T = 5s\). The response variable of the experimental analysis is RPI, and the performance of the algorithm is illustrated by analyzing the average and minimum of RPI.
Small scale instances
It can be seen from Table 4 that each algorithm has the possibility to find the most optimal results for the small-scale instances. The average minimum RPI of IG, DABC, IHS, HFOA, HGA and ABC are 2.03%, 0.05%, 2.24%, 11.04%, 2.01% and 4.92%, respectively. DABC algorithm and HGA algorithm show better performance. ABC, IHS, and HFOA have poor performance. However, from the analysis of the average RPI, we can see that the value of IG is 2.14%, which is better than other algorithms. This is because IG has only one initial solution in the same period. The convergence speed is fast and the stability is high in processing small instances, but the quality of finding solutions is worse than DABC. In conclusion, due to the small size of the instance, there is little difference in the performance of the algorithm. Comparatively speaking, the performance of DABC algorithm is better than that of the other compared algorithms.
Table 4
The average and minimum RPI value for the instances with 10 customer sizes
Instance
IG
DABC
IHS
HFOA
HGA
ABC
Ave
Min
Ave
Min
Ave
Min
Ave
Min
Ave
Min
Ave
Min
T1001
0.38
0.00
1.60
0.17
1.05
0.47
40.56
5.42
0.43
0.00
24.14
8.70
T1002
0.50
0.50
4.09
0.00
4.43
0.50
42.09
10.02
0.60
0.00
24.55
5.32
T1003
2.96
2.63
2.58
0.00
3.78
2.63
30.32
3.24
2.89
2.63
25.89
8.63
T1004
4.61
4.51
4.87
0.00
5.62
4.51
18.11
9.04
4.54
4.51
10.70
4.51
T1005
6.84
5.92
5.44
0.00
9.36
7.55
59.27
12.50
7.39
5.92
29.88
8.45
T1006
0.00
0.00
3.56
0.00
2.23
0.00
20.93
11.97
0.00
0.00
6.19
0.00
T1007
0.39
0.39
3.41
0.00
2.17
0.39
41.29
12.19
1.51
0.00
23.76
2.39
T1008
0.20
0.20
3.79
0.00
1.67
0.20
52.56
9.87
0.24
0.00
20.92
3.39
T1009
0.77
0.77
4.61
0.00
3.29
0.77
25.18
9.66
0.77
0.00
5.55
4.34
T1010
1.27
1.17
3.01
0.00
2.94
1.17
27.89
9.72
1.17
1.17
13.47
2.79
T1011
0.00
0.00
3.24
0.00
1.45
0.00
53.40
21.13
0.41
0.00
10.48
1.06
T1012
2.26
2.26
3.29
0.00
4.51
2.26
13.74
7.29
2.50
2.26
10.69
3.84
T1013
5.50
5.50
7.80
0.00
8.74
7.22
59.46
18.70
7.24
7.11
31.89
7.22
T1014
1.49
1.49
3.29
0.00
4.05
1.89
37.48
12.24
1.63
1.49
16.27
4.89
T1015
0.00
0.00
2.87
0.92
0.44
0.00
31.42
9.23
0.00
0.00
3.76
0.00
T1016
2.40
2.40
3.04
0.00
3.04
2.40
28.89
6.48
2.47
2.40
6.65
2.40
T1017
1.27
1.25
3.44
0.00
4.05
1.25
29.30
10.98
2.09
1.25
22.24
10.21
T1018
8.59
8.54
9.45
0.00
12.62
8.54
54.79
20.61
9.12
8.54
31.95
11.71
T1019
3.09
3.09
3.29
0.00
4.06
3.09
19.44
8.08
3.09
3.09
8.30
5.91
T1020
0.24
0.00
3.89
0.00
4.57
0.00
44.01
12.37
0.40
0.00
6.46
2.55
Average
2.14
2.03
4.03
0.05
4.20
2.24
36.51
11.04
2.42
2.01
16.69
4.92
The bold values represent the optimal values in the experiment
Large-scale instances
In Table 5, for instance with the customer size of 20, DABC found 19 best solutions and IHS found one. As we can see the average RPI of IG, DABC, IHS, HFOA, HGA, ABC are, respectively, 6.56%, 1.56%, 4.20%, 40.08%, 18.68%, and 27.13%. DABC is the clear winner for each termination condition in terms of the overall mean RPI value, followed by IG and IHS, and HFOA is the worst. It shows that DABC has better stability. According to Tables 6, 7 and 8, we can draw a similar conclusion that DABC performs well in most of the instances. IG performance is close to DABC. The performance of HGA is good in the small instances, but it gradually becomes unstable as the size of the instances expands. The performance of other algorithms is poor. To sum up, DABC has the best performance among the comparison algorithms for solving AGVSPDP.
Table 5
The average and minimum RPI value for the instances with 20 customer sizes
Instance
IG
DABC
IHS
HFOA
HGA
ABC
Ave
Min
Ave
Min
Ave
Min
Ave
Min
Ave
Min
Ave
Min
T2001
8.34
6.40
3.73
0.00
1.05
0.47
53.92
17.84
24.59
17.99
26.53
20.74
T2002
4.26
2.08
1.19
0.00
4.43
0.50
39.95
12.95
18.85
15.58
31.14
27.77
T2003
7.19
0.48
1.73
0.00
3.78
2.63
30.02
18.08
16.86
14.01
27.03
17.90
T2004
6.05
2.58
1.58
0.00
5.62
4.51
37.53
18.73
15.08
10.66
28.04
15.11
T2005
6.26
3.33
1.25
0.00
9.36
7.55
45.92
22.00
18.59
13.83
29.12
19.62
T2006
6.74
3.31
1.30
0.00
2.23
0.00
34.89
8.21
21.07
13.63
27.46
12.96
T2007
8.38
3.79
2.15
0.00
2.17
0.39
40.79
11.08
23.15
21.21
32.96
29.05
T2008
4.05
1.47
1.79
0.00
1.67
0.20
47.49
15.84
20.11
13.98
32.75
30.04
T2009
6.49
2.83
1.20
0.00
3.29
0.77
42.39
17.58
22.56
17.49
22.17
16.59
T2010
4.83
2.94
0.76
0.00
2.94
1.17
43.29
21.47
20.84
15.39
17.24
8.78
T2011
5.84
3.28
1.22
0.00
1.45
0.00
42.85
11.55
16.55
13.52
30.84
26.94
T2012
5.67
2.97
1.26
0.00
4.51
2.26
31.03
19.58
16.45
13.06
22.91
16.94
T2013
7.66
2.73
1.43
0.00
8.74
7.22
45.32
18.97
21.68
18.28
27.95
19.72
T2014
5.05
1.62
1.06
0.00
4.05
1.89
36.70
14.94
18.65
15.00
31.67
28.82
T2015
5.04
2.93
0.55
0.00
0.44
0.00
37.73
13.94
14.00
10.89
14.68
9.73
T2016
6.37
2.45
1.57
0.00
3.04
2.40
39.28
16.99
11.70
10.14
28.71
19.67
T2017
6.94
4.59
1.42
0.00
4.05
1.25
35.17
7.22
16.48
14.25
31.56
29.63
T2018
10.72
6.40
2.94
0.00
12.62
8.54
34.87
16.34
18.00
15.90
34.00
23.95
T2019
7.82
4.85
1.92
0.00
4.06
3.09
41.99
21.57
18.92
14.03
26.60
12.75
T2020
7.47
4.39
1.12
0.09
4.57
0.00
40.38
19.54
19.37
16.62
19.28
13.35
Average
6.56
3.27
1.56
0.00
4.20
2.24
40.08
16.22
18.68
14.77
27.13
20.00
The bold values represent the optimal values in the experiment
Table 6
The average and minimum RPI value for the instances with 30 customer sizes
Instance
IG
DABC
IHS
HFOA
HGA
ABC
Ave
Min
Ave
Min
Ave
Min
Ave
Min
Ave
Min
Ave
Min
T3001
13.18
10.83
4.75
0.00
24.19
5.88
41.93
21.05
25.72
23.16
53.00
44.77
T3002
9.19
4.73
1.48
0.00
18.03
2.38
34.91
13.07
19.85
15.33
50.89
42.06
T3003
16.81
0.00
12.19
7.51
23.50
15.60
52.72
38.52
30.73
29.13
65.08
61.19
T3004
15.11
11.51
5.71
0.00
19.23
8.34
42.98
26.84
34.52
31.19
50.58
40.17
T3005
12.71
10.14
5.84
0.00
21.99
8.26
47.75
24.55
27.90
24.86
52.26
48.09
T3006
9.76
7.26
2.36
0.00
16.06
3.03
48.55
25.51
23.14
19.17
44.83
37.98
T3007
10.78
7.84
2.46
0.00
18.81
4.83
45.82
22.21
24.40
21.59
46.97
42.47
T3008
7.73
5.67
2.18
0.00
16.54
3.52
43.94
19.04
26.29
23.70
44.46
40.92
T3009
13.75
7.78
3.40
0.00
15.34
3.89
51.45
28.95
27.57
24.91
45.90
41.49
T3010
18.18
13.50
4.28
0.00
17.47
8.43
44.26
25.92
33.89
27.72
54.31
50.59
T3011
10.82
7.73
2.88
0.00
17.79
1.68
38.51
18.50
24.84
20.99
46.55
41.84
T3012
12.40
9.97
2.77
0.00
13.69
7.15
38.77
21.80
23.03
21.61
44.36
23.88
T3013
36.29
31.31
1.78
0.00
43.67
26.37
77.13
53.77
48.70
41.94
77.20
67.95
T3014
12.16
7.33
2.51
0.00
19.94
4.41
42.57
21.22
23.26
20.54
47.77
44.01
T3015
12.67
8.84
2.84
0.00
16.20
4.76
38.77
22.10
24.87
19.56
41.53
34.71
T3016
37.78
32.88
23.47
0.00
41.48
30.93
71.79
38.07
54.54
51.94
76.82
64.06
T3017
12.99
8.03
3.35
0.00
18.70
7.38
41.58
28.30
31.57
29.72
51.21
45.23
T3018
11.08
8.40
1.24
0.00
13.30
2.35
34.68
18.33
25.47
22.41
48.58
41.52
T3019
14.14
9.25
3.61
0.00
18.48
4.29
43.42
25.99
29.62
26.79
50.82
47.12
T3020
11.55
9.64
2.89
0.00
14.35
4.69
42.25
24.57
20.54
18.05
43.85
36.66
Average
14.95
10.63
4.60
0.38
20.44
7.91
46.19
25.92
29.02
25.72
51.85
44.84
The bold values represent the optimal values in the experiment
Table 7
The average and minimum RPI value for the instances with 40 customer sizes
Instance
IG
DABC
IHS
HFOA
HGA
ABC
Ave
Min
Ave
Min
Ave
Min
Ave
Min
Ave
Min
Ave
Min
T4001
24.51
18.34
5.70
0.00
37.73
23.27
63.36
44.35
28.14
25.75
87.20
74.21
T4002
29.32
13.97
12.47
0.00
35.26
24.78
60.70
46.02
47.83
35.18
74.83
69.56
T4003
32.18
27.11
11.87
0.00
35.80
21.40
48.44
30.79
33.60
27.14
67.69
62.56
T4004
29.58
22.37
5.28
0.00
32.89
24.47
54.00
40.51
51.67
50.13
76.06
66.39
T4005
31.13
27.39
14.61
0.00
31.64
24.98
62.40
41.90
48.49
33.98
83.11
69.64
T4006
34.21
29.04
8.08
0.00
33.82
23.16
72.92
47.54
52.76
46.52
82.77
72.10
T4007
35.41
28.55
6.42
0.00
35.89
24.97
75.06
49.97
59.42
53.74
88.82
75.34
T4008
29.56
24.53
7.46
0.00
34.04
22.34
63.87
47.99
46.27
35.41
81.94
69.02
T4009
34.29
30.64
12.33
0.00
30.45
21.71
65.52
44.99
49.39
45.94
77.74
63.38
T4010
25.88
15.84
7.91
0.00
29.43
20.67
62.80
47.38
32.71
28.57
82.45
74.48
T4011
35.50
29.29
12.03
0.00
36.63
25.14
67.00
51.59
49.85
40.99
90.45
77.14
T4012
32.84
28.42
3.68
0.00
32.15
20.52
71.85
40.71
28.16
25.39
82.65
73.28
T4013
27.27
8.65
10.12
0.00
28.36
18.87
53.44
34.61
31.25
26.57
82.65
79.15
T4014
32.04
25.41
8.40
0.00
33.26
22.23
56.80
41.37
49.41
29.69
80.23
66.28
T4015
34.63
31.66
11.74
0.00
29.87
20.81
65.32
49.38
53.71
39.23
80.16
70.83
T4016
21.19
12.38
5.85
0.00
29.92
8.91
64.77
47.14
24.77
22.17
73.52
68.55
T4017
29.02
23.96
5.41
0.00
30.17
19.52
59.56
24.97
52.06
48.22
69.05
62.74
T4018
26.90
18.06
13.05
0.00
37.86
7.37
55.03
39.67
26.33
21.69
88.27
83.18
T4019
34.01
24.90
13.38
0.00
31.64
22.28
55.39
41.12
31.11
24.93
74.64
66.10
T4020
28.69
21.56
6.07
0.00
34.59
24.78
55.11
26.66
32.38
29.18
83.27
67.82
Average
30.41
23.10
9.09
0.00
33.07
21.11
61.67
41.93
41.47
34.52
80.38
70.59
The bold values represent the optimal values in the experiment
Table 8
The average and minimum RPI value for the instances with 50 customer sizes
Instance
IG
DABC
IHS
HFOA
HGA
ABC
Ave
Min
Ave
Min
Ave
Min
Ave
Min
Ave
Min
Ave
Min
T5001
24.56
12.94
3.97
0.00
35.49
22.31
53.84
25.47
27.00
25.05
86.87
76.77
T5002
31.34
26.72
2.73
0.00
31.01
4.54
53.94
41.78
48.45
43.51
81.91
76.83
T5003
14.91
9.03
1.70
0.00
31.19
21.50
52.95
32.73
26.60
24.38
79.15
68.23
T5004
25.87
21.44
2.56
0.00
31.23
20.47
50.63
24.97
32.50
24.96
81.99
76.88
T5005
23.82
17.19
3.15
0.00
31.74
3.19
53.89
34.66
29.68
27.16
81.54
77.08
T5006
36.25
32.43
5.55
0.00
30.19
21.12
59.94
43.83
48.73
40.59
93.41
83.94
T5007
28.14
21.48
5.11
0.00
27.27
21.40
48.22
33.05
28.11
26.35
78.73
68.85
T5008
28.56
23.36
4.24
0.00
33.22
17.66
63.95
38.56
49.57
45.56
93.50
80.80
T5009
30.49
23.67
7.10
0.00
33.19
19.13
58.44
34.02
32.42
28.40
87.28
79.51
T5010
23.69
18.19
1.98
0.00
24.74
3.82
64.63
43.93
45.63
32.15
91.38
79.74
T5011
22.78
13.52
4.37
0.00
28.82
5.76
44.60
24.16
30.68
25.60
74.69
59.37
T5012
19.12
13.60
2.56
0.00
31.02
17.60
53.80
38.94
30.07
28.14
79.31
74.69
T5013
26.53
11.91
2.57
0.00
30.63
19.86
59.29
41.08
32.14
30.14
89.79
77.85
T5014
27.68
16.94
2.85
0.00
29.39
20.23
56.23
43.55
36.44
34.20
89.32
79.63
T5015
32.37
24.49
4.90
0.00
28.73
20.00
62.81
46.90
34.26
32.60
83.27
78.63
T5016
24.43
15.71
2.96
0.00
34.86
21.02
46.81
38.36
25.54
19.58
75.29
71.67
T5017
21.70
17.00
2.37
0.00
28.32
6.24
42.66
23.18
25.41
22.82
79.05
75.38
T5018
24.16
17.83
1.75
0.00
28.91
18.29
51.85
40.88
30.63
28.35
88.35
80.56
T5019
30.75
26.81
3.37
0.00
28.92
21.86
56.03
25.32
45.84
43.24
80.90
75.21
T5020
28.16
14.54
3.15
0.00
25.29
19.98
45.62
30.17
27.63
26.26
75.74
72.90
Average
26.27
18.94
3.45
0.00
30.21
16.30
54.01
35.28
34.37
30.45
83.57
75.73
The bold values represent the optimal values in the experiment
Considering the statistical significance, ANOVA is used to conduct multi-factor for algorithm type and customer size analysis. The analysis results are shown in the 95% LSD confidence interval of the mean graph. In Fig. 12, there is no obvious overlap between the algorithms, indicating that the experimental results are of statistical significance. In the 10 scale instances, the performance of IG, DABC, IHS, and HGA is similar. In the 20–50 scale instances, DABC performs best, which also verifies the conclusion drawn in the above table. This means that the method and strategies proposed have obvious effect on solving AGVSPDP in DABC.
Fig. 12
The RPI of all algorithms
×
We randomly selected different scale instances, namely T2007, T3007, T4007 and T5007, to test the convergence characteristics of the algorithms. The six algorithms ABC, IHS, DABC, HFOA, HGA and IG are, respectively, run once in the above instances to find the best total cost. Figure 13a–d shows the convergence process of the algorithms in four instances. In Fig. 13, the convergence rate of HFOA and ABC is bad, and the convergence rate of other algorithms is good and similar. The four graphics show that the quality of the DABC solution has always been the best. In addition, we can find that the initial solution of DABC is superior to other algorithms to a large extent, which means that the RT truly work in the algorithm evolution, and it also explains why the DABC algorithm has good performance. IG has a strong ability to evade local optimization, but the quality of solutions is not high. DABC also can jump out of local optimum. Although we only show four instances for analysis, we can still reach the same conclusion when analyzing other instances. In conclusion, the DABC algorithm and strategies proposed in this paper are most effective in solving AGVSPDP.
Fig. 13
The convergence process of the algorithm
×
The computational complexity
We analyze the computational complexity of the algorithms. For DABC, assuming that there are n customers that need m AGVs, and the iterations in the total loop of the DABC is \({\xi }_{1}\). In the initial population, the time complexity of RT is \(O(\frac{1}{2}{n}^{2})\). In the search phase, the time complexity is \(O({\xi }_{1}n+\frac{({\xi }_{1}+1)}{m}{n}^{2})\). The complexity of the DABC is \(O(\frac{1}{2}{n}^{2}+{\xi }_{1}n+\frac{({\xi }_{1}+1)}{m}{n}^{2})\), which is \(O({n}^{2})\). The complexity of IHS is \(O\left({n}^{3}\right).\) The complexity of IG, ABC, and HGA is \(O\left({n}^{2}\right).\) The optimization result of DABC is better with the same efficiency of the algorithms. Therefore, compared with the comparison algorithms, DABC is an effective algorithm to solve AGVSPDP.
Conclusions and prospects
This paper solves an AGV scheduling problem with both delivery and pickup, which is a realistic workshop optimization problem, and that is less solved in the literature. The goal is to optimize the total cost. To make the DABC algorithm more capable of solving the AGVSPDP, the RT heuristic was proposed to improve the quality of the initial population. We designed four neighborhood operators: the Inner_AGV_Insert, the Outside_AGV_Insert, the Inner_AGV_Swap, and the Outside_AGV_Swap to help bees search for more promising areas. In addition, to further enhance the search capability of the algorithm, we proposed a problem-based search strategy based on high-quality solution, which retains as much information as possible about the current best solution. It is worth mentioning that to improve transportation efficiency, a dynamic calculation method is embedded. To reduce unnecessary searches, we adopted a rule, which can reduce the number of infeasible solutions and effectively save computation time. Extensive experimental analysis has shown that the operators and strategies proposed above are effective in DABC algorithm and the DABC algorithm is feasible and has better performance in the comparison algorithms.
In the future, we will further consider AGV scheduling under different constraints or other objectives. For example, a machine breakdown or an emergency customer situation. In addition, more attention should be paid to national policies. Low carbon has always been a key issue, we will optimize AGV scheduling to reduce energy consumption of AGV.
Acknowledgements
This work was supported by National Natural Science Foundation of China (62273221, 52205529), the Shandong Province Colleges and Universities Youth Innovation Talent Introduction and Education Program, Discipline with Strong Characteristics of Liaocheng University—Intelligent Science and Technology under Grant 319462208, Research Fund Project of Liaocheng University under Grant No. 318011922, the Natural Science Foundation of Shandong Province (ZR2021QF036, ZR2021QE195).
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
