# Sine Cosine Algorithm with Multigroup and Multistrategy for Solving CVRP

Authors: Qingyong Yang; Shu-Chuan Chu; Jeng-Shyang Pan; Chien-Ming Chen
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Sine Cosine Algorithm (SCA) has been proved to be superior to some existing traditional optimization algorithms owing to its unique optimization principle. However, there are still disadvantages such as low solution accuracy and poor global search ability. Aiming at the shortcomings of the sine cosine algorithm, a multigroup multistrategy SCA algorithm (MMSCA) is proposed in this paper. The algorithm executes multiple populations in parallel, and each population executes a different optimization strategy. Information is exchanged among populations through intergenerational communication. Using 19 different types of test functions, the optimization performance of the algorithm is tested. Numerical experimental results show that the performance of the MMSCA algorithm is better than that of the original SCA algorithm, and it also has some advantages over other intelligent algorithms. At last, it is applied to solving the capacitated vehicle routing problem (CVRP) in transportation. The algorithm can get better results, and the practicability and feasibility of the algorithm are also proved.


---

## Body

## 1. Introduction

With the rapid development of human society and the continuous improvement of computer technology, people are facing more and more optimization problems in scientific research and engineering practice. The optimization problems can be understood as choosing a most suitable solution among many options for solving a complex problem without changing the constraints. However, with the increasing scale of the problem, the computing time also shows an exponential growth trend. When solving large-scale optimization problems, traditional algorithms seem powerless. For quite some time, people have been working hard to find new ways to better solve optimization problems. With the robustness, parallelism, and intelligence of its methods, computational intelligence (CI) can well solve many optimization problems, which has attracted the attention of many scholars. Also, computational intelligence (CI) plays an important role in scientific research and production practice.Computational intelligence is a general term for a class of algorithms that are inspired by natural and human wisdom. Computational intelligence includes three basic areas: fuzzy computing [1–3], neural networks [4, 5], and evolutionary computing [6]. Evolutionary computing is one of the important research fields of intelligent computing. Up to now, scholars have put forward many excellent intelligent optimization algorithms. Typical examples are as follows: genetic algorithm (GA) by simulating the genetic evolution of the biological world [7]; particle swarm optimization (PSO) by simulating bird swarm predation [8–10]; and ant colony algorithm (ACO) by simulating ant colony foraging behavior [11, 12]. There are many intelligent optimization algorithms proposed by simulating other phenomena in nature, such as cat swarm algorithm (CSO) [13–15], artificial bee colony algorithm (ABC) [16, 17], differential evolution algorithm (DE) [18–21], multiverse optimizer (MVO) [22, 23], flower pollination algorithm [24, 25], gray wolf algorithm (GWO) [26–28], pigeon-inspired algorithm (PIO) [29, 30], bat algorithm (BA) [31, 32], symbiotic organism search algorithm (SOS) [33, 34], and QUATRE [35–37].At present, there are so many optimization algorithms, which can solve some complex optimization problems well. Why do we need so many optimization algorithms? As demonstrated by the No Free Lunch (NFL) [38] proposed by Wolpert and Macready, no single optimization algorithm is applicable to all problems. Inspired by this, a new intelligent optimization algorithm was proposed by Australian scholar Mirjalili in 2016, which is called Sine Cosine Algorithm (SCA) [39]. The SCA algorithm iterates through the properties of the sine and cosine functions to achieve optimization. It has fewer parameter settings, is easy to implement, and has a strong optimization ability. It has been proved that it is better than PSO algorithm, genetic algorithm (GA), and firefly algorithm (FA) in convergence with accuracy and speed [39].With the rapid development of software and hardware, parallel computing has become a form of high-performance computing. In evolutionary computing, parallelism often represents the iterative updating of multiple populations at the same time. The advantage of this method is to ensure population diversity, to further improve the search ability and performance of the algorithm. Especially when solving complex optimization problems, parallelizing the algorithm is an effective way to improve the efficiency and accuracy of the algorithm. At present, many existing algorithms have successfully applied the parallel mechanism, such as parallel PSO [40], parallel ACO [41], and parallel QUATRE [42]. Inspired by this, this paper introduces the multigroup and multistrategy optimization mechanism to further improve the SCA algorithm. It is called MMSCA. When the algorithm is solved, multiple populations execute in parallel, and each population adopts different updating strategies. By comparing the results of test functions, MMSCA is better than SCA in solving accuracy and convergence ability and has certain advantages over other intelligent optimization algorithms.At present, transportation is gradually moving towards intelligent transportation. One of the important components of an intelligent transportation system is wireless sensor network technology (WSN). With the help of wireless sensor network technology [43–48], the safety, unblocking, and environmental protection problems that plague modern transportation can be fundamentally alleviated. However, there are still many transportation problems to be solved. The capacitated vehicle routing problem (CVRP) in transportation problems is taken as the application object of MMSCA in this paper. On the one hand, the practicability of the algorithm is further confirmed. On the other hand, it brings a new solution to CVRP problem.The remaining chapters of the article are arranged as follows: the original SCA algorithm and related improvements around it are reviewed in Section2. Section 3 describes the MMSCA design process in detail. The results of numerical experiments are presented and discussed in Section 4. How to apply MMSCA to CVRP is covered in Section 5. At last, Section 6 is a summary of the article and an outlook for future work.


## 2. Related Works

### 2.1. Original Sine Cosine Algorithm

In the SCA algorithm, a populationX is initialized first, where the population X contains m individuals, and each individual has n dimensions. The fitness function is used to evaluate each individual, and the best individual position Pb=Pb1,Pb2,…,PbnT among all the current individuals is selected. Then, the algorithm iterates according to the set number of iterations. During the iteration, the position of the individual is updated. The update formula is as follows:(1)Xit+1=Xit+r1×sinr2×r3×Pbt−Xit,r4<0.5,Xit+r1×cosr2×r3×Pbt−Xit,r4≥0.5,where Xit represents the position of the ith (i = 1, 2, …, m) individual in the tth iteration; r2∈0,2π, r3∈0,2, and r4∈0,1 are three random numbers. Pbt represents the best individual position after t iterations. r1 is the control parameter, which balances the exploration and exploitation stages of the algorithm. The updated formula is as follows:(2)r1=a−atT,where a is a constant, t is the number of current iterations, and T is the maximum number of iterations.Since equation (1) uses sine and cosine functions, the algorithm is named Sine Cosine Algorithm (SCA). Four important parameters play different roles in the process of iterative optimization of the algorithm: the parameter r1 is used as a control parameter to determine the moving direction of the individual position in the next iteration; the parameter r2 determines how far to move in the next iteration; as a random weight, parameter r3 affects the role of the optimal individual in the next iteration; the parameter r4 enables the algorithm to iteratively update the individual positions in the sine and cosine parts with equal probability. Like other intelligent optimization algorithms, there need to be two phases: local exploitation and global exploration. In SCA algorithm, when r1sinr2 or r1cosr2 function value is between −1 and 1, the algorithm performs local exploitation; when r1sinr2 or r1cosr2 function value is less than −1 or greater than 1, the algorithm performs global exploration.


### 2.2. Related Improvements to the SCA Algorithm

With its unique optimization principles and theoretical advantages, the SCA algorithm has been proved to be superior to PSO, genetic algorithm (GA), and other existing algorithms in the most of the examples and has been applied in many practical problems. However, there are still some disadvantages such as low solution accuracy and poor global search ability. This is because when the SCA algorithm updates the individual location, the next generation location of the individual is only expanded around the current optimal individual location. In particular, with the decrease of the diversity of the population in the later period of the algorithm, the global search ability becomes worse, which easily leads to the algorithm falling into the local optimal trap.In view of the shortcomings of the SCA algorithm, scholars at home and abroad have made some improvements. Some scholars introduced search strategies of other algorithms or improved the setting of the parameters of the SCA algorithm itself: Long et al. [49] introduced nonlinear weight factor and inertial weight based on Gaussian distribution, respectively, to improve the ability to avoid falling into the trap of local optimization and convergence speed; Qu et al. [50] proposed an improved SCA algorithm based on neighborhood search and Greedy Levy Mutation to better balance the phases of local exploitation and global exploration of the algorithm. Some scholars have also integrated the SCA algorithm with other algorithms to further improve the optimization ability of the algorithm: Chegini et al. [51] proposed to mix the SCA algorithm with the PSO algorithm to improve the global search capability of the algorithm and the calculation accuracy; Nenavath and Jatoth [52] mixed the SCA algorithm and the DE algorithm to further improve the convergence speed of the algorithm and the ability to avoid local optimization.There are many improvements to the SCA algorithm, and the improvement methods can be summarized into the abovementioned two categories. Aiming at the shortcomings of the SCA algorithm, this paper adopts a multigroup and multistrategy optimization mechanism to further improve the accuracy of the solution and the global search ability of the algorithm. The next section will detail how to improve the SCA algorithm.


## 2.1. Original Sine Cosine Algorithm

In the SCA algorithm, a populationX is initialized first, where the population X contains m individuals, and each individual has n dimensions. The fitness function is used to evaluate each individual, and the best individual position Pb=Pb1,Pb2,…,PbnT among all the current individuals is selected. Then, the algorithm iterates according to the set number of iterations. During the iteration, the position of the individual is updated. The update formula is as follows:(1)Xit+1=Xit+r1×sinr2×r3×Pbt−Xit,r4<0.5,Xit+r1×cosr2×r3×Pbt−Xit,r4≥0.5,where Xit represents the position of the ith (i = 1, 2, …, m) individual in the tth iteration; r2∈0,2π, r3∈0,2, and r4∈0,1 are three random numbers. Pbt represents the best individual position after t iterations. r1 is the control parameter, which balances the exploration and exploitation stages of the algorithm. The updated formula is as follows:(2)r1=a−atT,where a is a constant, t is the number of current iterations, and T is the maximum number of iterations.Since equation (1) uses sine and cosine functions, the algorithm is named Sine Cosine Algorithm (SCA). Four important parameters play different roles in the process of iterative optimization of the algorithm: the parameter r1 is used as a control parameter to determine the moving direction of the individual position in the next iteration; the parameter r2 determines how far to move in the next iteration; as a random weight, parameter r3 affects the role of the optimal individual in the next iteration; the parameter r4 enables the algorithm to iteratively update the individual positions in the sine and cosine parts with equal probability. Like other intelligent optimization algorithms, there need to be two phases: local exploitation and global exploration. In SCA algorithm, when r1sinr2 or r1cosr2 function value is between −1 and 1, the algorithm performs local exploitation; when r1sinr2 or r1cosr2 function value is less than −1 or greater than 1, the algorithm performs global exploration.


## 2.2. Related Improvements to the SCA Algorithm

With its unique optimization principles and theoretical advantages, the SCA algorithm has been proved to be superior to PSO, genetic algorithm (GA), and other existing algorithms in the most of the examples and has been applied in many practical problems. However, there are still some disadvantages such as low solution accuracy and poor global search ability. This is because when the SCA algorithm updates the individual location, the next generation location of the individual is only expanded around the current optimal individual location. In particular, with the decrease of the diversity of the population in the later period of the algorithm, the global search ability becomes worse, which easily leads to the algorithm falling into the local optimal trap.In view of the shortcomings of the SCA algorithm, scholars at home and abroad have made some improvements. Some scholars introduced search strategies of other algorithms or improved the setting of the parameters of the SCA algorithm itself: Long et al. [49] introduced nonlinear weight factor and inertial weight based on Gaussian distribution, respectively, to improve the ability to avoid falling into the trap of local optimization and convergence speed; Qu et al. [50] proposed an improved SCA algorithm based on neighborhood search and Greedy Levy Mutation to better balance the phases of local exploitation and global exploration of the algorithm. Some scholars have also integrated the SCA algorithm with other algorithms to further improve the optimization ability of the algorithm: Chegini et al. [51] proposed to mix the SCA algorithm with the PSO algorithm to improve the global search capability of the algorithm and the calculation accuracy; Nenavath and Jatoth [52] mixed the SCA algorithm and the DE algorithm to further improve the convergence speed of the algorithm and the ability to avoid local optimization.There are many improvements to the SCA algorithm, and the improvement methods can be summarized into the abovementioned two categories. Aiming at the shortcomings of the SCA algorithm, this paper adopts a multigroup and multistrategy optimization mechanism to further improve the accuracy of the solution and the global search ability of the algorithm. The next section will detail how to improve the SCA algorithm.


## 3. Sine Cosine Algorithm with Multigroup and Multistrategy (MMSCA)

This section describes in detail how to apply the multigroup and multistrategy mechanism to improve the Sine Cosine Algorithm (SCA).


### 3.1. Algorithm Idea

The use of a single population in basic SCA algorithm inevitably leads to the problem of falling into the local optimal trap. At the same time, when the algorithm updates individual location in each iteration, the location of candidate individuals is only expanded around the global optimal location, which results in the strong local search capability of the basic SCA algorithm and the weak global search capability. Based on the shortcomings of the abovementioned basic SCA algorithm, the concept of multigroup and multistrategy is introduced to enhance the optimization ability of SCA algorithm. In the multigroup multistrategy SCA algorithm (MMSCA), each population has the same number of individuals and uses a different update strategy. Before a certain number of generations, each population is optimized according to its own strategy, and the population does not interfere with each other. After reaching a certain number of generations, the populations communicate with each other and perform the optimal individual migration between the populations. The worst individual in each population will be replaced by the optimal individual in the other populations. Repeat the abovementioned steps until the algorithm iterates to the maximum number of iterations or the optimal solution is found.In this article, the update strategies are divided into two types: rand strategy and best strategy. In the rand strategy, the roulette wheel selection scheme in the genetic algorithm (GA) is borrowed, and the optimal individual in the group is no longer selected as the solution target of other individuals. Instead, the algorithm uses multiple roulette methods to choose the next generation of solving goals to increase the diversity of population solutions. In this way, the ability of global optimization can be enhanced and the possibility of local optimal trap will be increased. In the best strategy, the best individual in all populations is still the solution target. The purpose of doing this is to maintain the strong local optimization ability of the original algorithm and avoid the instability of the algorithm caused by the introduction of the rand strategy.The update formula is as follows:(3)Xi,jt+1=Xi,jt+r1×sinr2×r3×Pbt−Xi,jt,r4<0.5,Xi,jt+r1×cosr2×r3×Pbt−Xi,jt,r4≥0.5,where Xi,jt represents the position of the jth individual in the ith population in the tth iteration and Pbt represents the selected target individual after multiple generations of roulette wheel selection in the rand strategy executing population. Also, in the population that executes the best strategy, it represents the globally optimal individual.


### 3.2. Algorithm Steps

Based on the abovementioned description, the specific steps of the MMSCA algorithm are given below:Step 1: randomly generateN (N is an even number) populations of size m, each population having n dimensions. Initialize the maximum number of iterations, independent evolution algebra, iteration counter etc.Step 2: evaluate each population and calculate the fitness value of each individual in each population. The population with odd group numbers executes the rand strategy, and the target individual is selected using the roulette wheel selection scheme; the population with even group numbers executes the best strategy, sorts and selects the best individual.Step 3: use formula (3) to update the individual positions in the population.Step 4: if the communication conditions are met, interpopulation communication is conducted. The worst individual in a population is replaced by the best individual in another population. If the communication condition is not met, return to step 2.Step 5: if the algorithm iterates to the maximum number of iterations or the optimal individual is found to meet the convergence conditions, the algorithm is terminated; otherwise return to step 2.The algorithm flow chart is shown in Figure1.Figure 1
Flowchart of sine cosine algorithm with multigroup and multistrategy.


## 3.1. Algorithm Idea

The use of a single population in basic SCA algorithm inevitably leads to the problem of falling into the local optimal trap. At the same time, when the algorithm updates individual location in each iteration, the location of candidate individuals is only expanded around the global optimal location, which results in the strong local search capability of the basic SCA algorithm and the weak global search capability. Based on the shortcomings of the abovementioned basic SCA algorithm, the concept of multigroup and multistrategy is introduced to enhance the optimization ability of SCA algorithm. In the multigroup multistrategy SCA algorithm (MMSCA), each population has the same number of individuals and uses a different update strategy. Before a certain number of generations, each population is optimized according to its own strategy, and the population does not interfere with each other. After reaching a certain number of generations, the populations communicate with each other and perform the optimal individual migration between the populations. The worst individual in each population will be replaced by the optimal individual in the other populations. Repeat the abovementioned steps until the algorithm iterates to the maximum number of iterations or the optimal solution is found.In this article, the update strategies are divided into two types: rand strategy and best strategy. In the rand strategy, the roulette wheel selection scheme in the genetic algorithm (GA) is borrowed, and the optimal individual in the group is no longer selected as the solution target of other individuals. Instead, the algorithm uses multiple roulette methods to choose the next generation of solving goals to increase the diversity of population solutions. In this way, the ability of global optimization can be enhanced and the possibility of local optimal trap will be increased. In the best strategy, the best individual in all populations is still the solution target. The purpose of doing this is to maintain the strong local optimization ability of the original algorithm and avoid the instability of the algorithm caused by the introduction of the rand strategy.The update formula is as follows:(3)Xi,jt+1=Xi,jt+r1×sinr2×r3×Pbt−Xi,jt,r4<0.5,Xi,jt+r1×cosr2×r3×Pbt−Xi,jt,r4≥0.5,where Xi,jt represents the position of the jth individual in the ith population in the tth iteration and Pbt represents the selected target individual after multiple generations of roulette wheel selection in the rand strategy executing population. Also, in the population that executes the best strategy, it represents the globally optimal individual.


## 3.2. Algorithm Steps

Based on the abovementioned description, the specific steps of the MMSCA algorithm are given below:Step 1: randomly generateN (N is an even number) populations of size m, each population having n dimensions. Initialize the maximum number of iterations, independent evolution algebra, iteration counter etc.Step 2: evaluate each population and calculate the fitness value of each individual in each population. The population with odd group numbers executes the rand strategy, and the target individual is selected using the roulette wheel selection scheme; the population with even group numbers executes the best strategy, sorts and selects the best individual.Step 3: use formula (3) to update the individual positions in the population.Step 4: if the communication conditions are met, interpopulation communication is conducted. The worst individual in a population is replaced by the best individual in another population. If the communication condition is not met, return to step 2.Step 5: if the algorithm iterates to the maximum number of iterations or the optimal individual is found to meet the convergence conditions, the algorithm is terminated; otherwise return to step 2.The algorithm flow chart is shown in Figure1.Figure 1
Flowchart of sine cosine algorithm with multigroup and multistrategy.


## 4. Results and Discussion

### 4.1. Comparison with SCA Algorithm

In order to test the influence of multigroup and multistrategy mechanism on SCA algorithm, 19 standard test functions (f1−f7 as unimodal benchmark function, f8−f13 as multimodal benchmark function, and f14−f19 as composite benchmark function) in the SCA algorithm literature [39] are used for testing. The minimum value of test function f1−f15 is 0 except f8, f8 and f16−f19 are −2094.9145, −1.036.0.398, 3, −3.86, respectively. For the fairness of comparison, the maximum number of iterations is 1000 and each population size is set to 30. In the proposed algorithm, the independent evolutionary algebra is set to 50 and the number of groups is two. For each test function, each algorithm is run independently for 30 times and the average value is calculated. Table 1 records the experimental results, with the best optimization results in bold. All simulation experiments are implemented on the same computer, and the programming tool is Matlab2018a.Table 1
Comparison of test results with SCA algorithm.
Function
SCA
MMSCA
f
1
5.86E − 28
2.95E − 30
f
2
2.19E − 17
8.02E − 20
f
3
1.46E − 08
6.73E − 30
f
4
1.31E − 07
1.56E − 08
f
5
7.05E + 00
7.02E + 00
f
6
3.73E − 01
2.98E − 01
f
7
1.82E − 03
1.83E − 04
f
8
−2.22E + 03
−2.29E + 03
f
9
6.83E − 01
3.30E − 06
f
10
6.48E − 14
2.91E − 14
f
11
2.34E − 02
0.00E + 00
f
12
6.92E − 02
5.60E − 02
f
13
2.68E − 01
2.59E − 01
f
14
1.86E + 00
9.98E − 01
f
15
9.20E − 04
6.85E − 04
f
16
−1.03E + 00
−1.03E + 00
f
17
3.99E − 01
3.99E − 01
f
18
3.00E + 00
3.00E + 00
f
19
−3.86E + 00
−3.86E + 00As shown in the abovementioned table, in the test functionsf1−f15, except f8, the MMSCA algorithm has better solution accuracy than the original SCA algorithm. For function f16−f19, both algorithms show the same optimization performance, and the results are close to or reach the expected minimum. In general, the optimization ability of the SCA algorithm has been improved to some extent after the introduction of the multigroup and multistrategy mechanism. Figure 2 shows the convergence curves of the two algorithms on the unimodal functions f2 and f3, the multimodal functions f9 and f11, and the composite function f14. As can be seen from the figure, MMSCA algorithm has also significantly improved the convergence speed compared with SCA algorithm.Figure 2
Convergence curve of benchmark functions:f2, f3, f9, f11, f14. (a) f2. (b) f3. (c) f9. (d) f11. (e) f14.
(a)
(b)
(c)
(d)
(e)


### 4.2. Comparison with Other Intelligent Optimization Algorithms

To further verify the effectiveness of the MMSCA algorithm, this article also compares it with other three intelligent optimization algorithms: the PSO algorithm, the parallel PSO algorithm, and the DE algorithm. The population size is set to 30. 1000 is the maximum number of iterations. For each test function, each algorithm is tested 30 times and the average value is obtained. The other parameters of other algorithms are shown in Table2. The test results of MMSCA and other three intelligent optimization algorithms on 19 test functions are shown in Table 3. The bold type in the table indicates the best results of all comparison algorithms.Table 2
Parameter settings.
Algorithm
Parameters
PSO
c1 = c2 = 2, ω = 0.9
PPSO
The number of groups is 2,c1 = c2 = 2, ω = 0.7
DE
pCR = 0.2,βmax = 0.8, βmin = 0.2Table 3
Test results compared with other optimization algorithms.
Function
MMSCA
PSO
PPSO
DE
f
1
2.95E − 30
6.92E − 03
3.03E − 28
8.14E − 15
f
2
8.02E − 20
2.46E − 01
5.93E − 13
1.58E − 08
f
3
6.73E − 30
8.03E − 02
1.08E − 25
6.38E + 01
f
4
1.56E − 08
7.92E − 02
6.67E − 08
9.47E − 02
f
5
7.02E + 00
1.70E + 01
1.16E + 00
2.94E + 01
f
6
2.98E − 01
6.48E − 03
1.50E − 09
6.89E − 15
f
7
1.83E − 04
1.30E − 02
2.07E − 03
2.87E − 02
f
8
−2.29E + 03
−2.40E + 03
−2.70E + 03
−1.18E + 02
f
9
3.30E − 06
3.34E + 00
6.70E + 00
5.81E + 01
f
10
2.91E − 14
2.77E − 01
3.68E − 13
5.08E − 08
f
11
0.00E + 00
2.29E − 01
3.32E − 01
9.88E − 15
f
12
5.60E − 02
6.44E − 02
1.04E − 02
2.25E − 16
f
13
2.59E − 01
7.68E − 03
2.28E − 03
1.86E − 15
f
14
9.98E − 01
3.86E + 00
1.99E + 00
3.26E + 00
f
15
6.85E − 04
4.52E − 03
1.80E − 03
7.23E − 04
f
16
−1.03E + 00
−1.03E + 00
−1.03E + 00
−1.03E + 00
f
17
3.99E − 01
3.99E − 01
3.99E − 01
3.98E − 01
f
18
3.00E + 00
3.00E + 00
3.00E + 00
3.00E + 00
f
19
−3.86E + 00
−3.86E + 00
−3.86E + 00
−3.86E + 00As shown in Table3, compared with the PSO algorithm, PPSO algorithm, and DE algorithm, the MMSCA algorithm has obtained better results on 11 test functions. The MMSCA algorithm has the same test results on the test functions f6 and f18−f19 as the other three algorithms, and they all obtain the expected minimum. However, the test results on the test functions f6 and f13 are significantly worse than those of the other three optimization algorithms; the MMSCA algorithm obtains better results on the test function f11, and obtains a minimum value of 0.Based on the comparison results of the two subsections, compared with the original SCA algorithm, the optimization performance of the algorithm is improved after the introduction of multigroup and multistrategy mechanism; compared with other intelligent optimization algorithms, it also shows strong competitiveness. So as to further study the feasibility and practicability of the MMSCA algorithm in processing practical problems, this paper selects the capacitated vehicle routing problem (CVRP) in transportation as the application object. The next section will describe in detail how to apply the MMSCA algorithm and solve it.


## 4.1. Comparison with SCA Algorithm

In order to test the influence of multigroup and multistrategy mechanism on SCA algorithm, 19 standard test functions (f1−f7 as unimodal benchmark function, f8−f13 as multimodal benchmark function, and f14−f19 as composite benchmark function) in the SCA algorithm literature [39] are used for testing. The minimum value of test function f1−f15 is 0 except f8, f8 and f16−f19 are −2094.9145, −1.036.0.398, 3, −3.86, respectively. For the fairness of comparison, the maximum number of iterations is 1000 and each population size is set to 30. In the proposed algorithm, the independent evolutionary algebra is set to 50 and the number of groups is two. For each test function, each algorithm is run independently for 30 times and the average value is calculated. Table 1 records the experimental results, with the best optimization results in bold. All simulation experiments are implemented on the same computer, and the programming tool is Matlab2018a.Table 1
Comparison of test results with SCA algorithm.
Function
SCA
MMSCA
f
1
5.86E − 28
2.95E − 30
f
2
2.19E − 17
8.02E − 20
f
3
1.46E − 08
6.73E − 30
f
4
1.31E − 07
1.56E − 08
f
5
7.05E + 00
7.02E + 00
f
6
3.73E − 01
2.98E − 01
f
7
1.82E − 03
1.83E − 04
f
8
−2.22E + 03
−2.29E + 03
f
9
6.83E − 01
3.30E − 06
f
10
6.48E − 14
2.91E − 14
f
11
2.34E − 02
0.00E + 00
f
12
6.92E − 02
5.60E − 02
f
13
2.68E − 01
2.59E − 01
f
14
1.86E + 00
9.98E − 01
f
15
9.20E − 04
6.85E − 04
f
16
−1.03E + 00
−1.03E + 00
f
17
3.99E − 01
3.99E − 01
f
18
3.00E + 00
3.00E + 00
f
19
−3.86E + 00
−3.86E + 00As shown in the abovementioned table, in the test functionsf1−f15, except f8, the MMSCA algorithm has better solution accuracy than the original SCA algorithm. For function f16−f19, both algorithms show the same optimization performance, and the results are close to or reach the expected minimum. In general, the optimization ability of the SCA algorithm has been improved to some extent after the introduction of the multigroup and multistrategy mechanism. Figure 2 shows the convergence curves of the two algorithms on the unimodal functions f2 and f3, the multimodal functions f9 and f11, and the composite function f14. As can be seen from the figure, MMSCA algorithm has also significantly improved the convergence speed compared with SCA algorithm.Figure 2
Convergence curve of benchmark functions:f2, f3, f9, f11, f14. (a) f2. (b) f3. (c) f9. (d) f11. (e) f14.
(a)
(b)
(c)
(d)
(e)


## 4.2. Comparison with Other Intelligent Optimization Algorithms

To further verify the effectiveness of the MMSCA algorithm, this article also compares it with other three intelligent optimization algorithms: the PSO algorithm, the parallel PSO algorithm, and the DE algorithm. The population size is set to 30. 1000 is the maximum number of iterations. For each test function, each algorithm is tested 30 times and the average value is obtained. The other parameters of other algorithms are shown in Table2. The test results of MMSCA and other three intelligent optimization algorithms on 19 test functions are shown in Table 3. The bold type in the table indicates the best results of all comparison algorithms.Table 2
Parameter settings.
Algorithm
Parameters
PSO
c1 = c2 = 2, ω = 0.9
PPSO
The number of groups is 2,c1 = c2 = 2, ω = 0.7
DE
pCR = 0.2,βmax = 0.8, βmin = 0.2Table 3
Test results compared with other optimization algorithms.
Function
MMSCA
PSO
PPSO
DE
f
1
2.95E − 30
6.92E − 03
3.03E − 28
8.14E − 15
f
2
8.02E − 20
2.46E − 01
5.93E − 13
1.58E − 08
f
3
6.73E − 30
8.03E − 02
1.08E − 25
6.38E + 01
f
4
1.56E − 08
7.92E − 02
6.67E − 08
9.47E − 02
f
5
7.02E + 00
1.70E + 01
1.16E + 00
2.94E + 01
f
6
2.98E − 01
6.48E − 03
1.50E − 09
6.89E − 15
f
7
1.83E − 04
1.30E − 02
2.07E − 03
2.87E − 02
f
8
−2.29E + 03
−2.40E + 03
−2.70E + 03
−1.18E + 02
f
9
3.30E − 06
3.34E + 00
6.70E + 00
5.81E + 01
f
10
2.91E − 14
2.77E − 01
3.68E − 13
5.08E − 08
f
11
0.00E + 00
2.29E − 01
3.32E − 01
9.88E − 15
f
12
5.60E − 02
6.44E − 02
1.04E − 02
2.25E − 16
f
13
2.59E − 01
7.68E − 03
2.28E − 03
1.86E − 15
f
14
9.98E − 01
3.86E + 00
1.99E + 00
3.26E + 00
f
15
6.85E − 04
4.52E − 03
1.80E − 03
7.23E − 04
f
16
−1.03E + 00
−1.03E + 00
−1.03E + 00
−1.03E + 00
f
17
3.99E − 01
3.99E − 01
3.99E − 01
3.98E − 01
f
18
3.00E + 00
3.00E + 00
3.00E + 00
3.00E + 00
f
19
−3.86E + 00
−3.86E + 00
−3.86E + 00
−3.86E + 00As shown in Table3, compared with the PSO algorithm, PPSO algorithm, and DE algorithm, the MMSCA algorithm has obtained better results on 11 test functions. The MMSCA algorithm has the same test results on the test functions f6 and f18−f19 as the other three algorithms, and they all obtain the expected minimum. However, the test results on the test functions f6 and f13 are significantly worse than those of the other three optimization algorithms; the MMSCA algorithm obtains better results on the test function f11, and obtains a minimum value of 0.Based on the comparison results of the two subsections, compared with the original SCA algorithm, the optimization performance of the algorithm is improved after the introduction of multigroup and multistrategy mechanism; compared with other intelligent optimization algorithms, it also shows strong competitiveness. So as to further study the feasibility and practicability of the MMSCA algorithm in processing practical problems, this paper selects the capacitated vehicle routing problem (CVRP) in transportation as the application object. The next section will describe in detail how to apply the MMSCA algorithm and solve it.


## 5. Applying MMSCA to Solve CVRP

VRP (Vehicle Routing Problem) has always been the focus of research in the field of transportation. At the same time, there are many applications in real life, including express delivery, air transportation, bus route planning, and so on. VRP was first proposed by scholars Dantzing and Ramser [53] in the late 1950s. Since it was proposed, it has received extensive attention from scholars at home and abroad, and scholars have also carried out a lot of fruitful work on it. After years of research and development, more models of VRP have been derived, and the solving algorithms have become more diverse. Solution algorithms can be divided into two categories: the first type is accurate algorithm and the second is approximate algorithm or heuristic algorithm. Since the VRP problem has been proved to be an NP-Hard problem, the second kind of solution algorithm is the main method to solve it [54]. The GA algorithm, the ACO algorithm, the SA (simulated annealing) algorithm, the PSO algorithm, and other algorithms have been successfully applied to solve VRP problems and achieved good results. In this paper, CVRP (Capacitated Vehicle Routing Problem) is selected as the application object of MMSCA algorithm to further verify the practicability of the algorithm.


### 5.1. CVRP Problem Description and Model

Problem description: a central warehouse hask distribution vehicles, and the maximum load capacity of each distribution vehicle is Q. Now, we need to transport and distribute materials to n customers (nodes), how to arrange a certain number of vehicles to meet the needs of these customers, and make the total driving distance of vehicles shortest. The following constraints must also be met:(1)
All delivery vehicles start from the central warehouse and eventually return to the central warehouse(2)
Each delivery vehicle is not allowed to exceed the maximum load capacityQ(3)
Each customer can only be served once, and each vehicle can only take one routeFor the convenience of description, the following symbols are defined:D: total length of all vehicle pathsk: total number of vehiclesn: total number of customersv: vehicle number (1, 2, ..., k)(4)xijv=1,if vehiclevtravels from customerito customerj,0,else,yiv=1,if customerineeds to be fulfilled by vehiclev,0,else,cij: the distance between customer point i and jgi: the demand of the i-th customer (i = 1, 2, …, n)Q: the maximum loading capacity of the vehicleThe central warehouse number is 0, and the customer number isi (i = 1, 2, …, n). The CVRP mathematical model is expressed as follows:Objective function:(5)minD=∑i=0n∑j=0n∑v=0kcijxijv.Constraint conditions:(6)∑i=0nxijv=yjv,j=1,2,…,n;v=1,2,…,k,(7)∑j=0nxijv=yjv,i=1,2,…,n;v=1,2,…,k,(8)∑i=0ngiyiv≤Q,v=1,2,…,k,(9)∑v=1kyiv=1,i=1,2,…,n.Among them, equations (6) and (7) are traffic flow constraints, requiring a car to leave a customer node after it has completed service; formula (8) represents the vehicle capacity constraint and indicates that the total customer demand on the route served by vehicle v cannot exceed the vehicle loading capacity Q; formula (9) ensures that each customer can only be served by one vehicle.


### 5.2. MMSCA Algorithm for CVRP

The MMSCA algorithm is a continuous space algorithm, but the CVRP problem is an integer programming problem, so it needs to be modified in the implementation process.(1)
Encoding and decodingEncoding: using natural number coding, each individual in the population corresponds to a unique arrangement from 1 ton, and each individual corresponds to a distribution scheme.Decoding: arrange the vehicles according to the sequence of customers in the distribution scheme and the constraint of maximum loading capacity. That is, it is sequentially included in the path of the first car according to the customer’s coding order, and the second car’s path is arranged until the maximum load of the first car is exceeded.(2)
Evaluation criteriaThe total length of the vehicle path is used to evaluate all individuals and the merits of each distribution scheme.(3)
Implementation processAccording to the abovementioned coding method, each population is generated. Each individual (distribution scheme) is evaluated according to the evaluation criteria. Update each individual with formula (3) to generate a new distribution scheme. According to the constraint conditions, the actual vehicle path is generated and evaluated. In the process of updating with formula (3), integer specification constraints are required to avoid generating infeasible solutions.


### 5.3. Simulation and Results Analysis

In this paper, five standard VRPLIB test samples are selected for testing, and the test results of the MMSCA algorithm are compared with the PSO algorithm [55] and the GA algorithm. Table 4 shows the experimental results. In the experiment, the population number of MMSCA algorithm is divided two groups, the number of individuals in each group is 50, the solution is thirty times, and the number of iterations is 10,000. During the solution process, the best solution result is recorded.Table 4
Comparison of MMSCA and other two algorithms.
Data set
Best known results
MMSCA
PSO
GA
Best
Dev (%)
Best
Dev (%)
Best
Dev (%)
A-n32-k5
784
808
3.06
829
5.73
818
4.34
A-n33-k5
661
690
4.39
705
6.65
674
1.97
A-n39-k6
831
868
4.45
872
6.08
866
5.35
A-n46-k7
914
964
5.47
977
6.89
957
4.7
A-n60-k9
1408
1426
1.28
1476
4.83
1410
0.14Where the Best column represents the known optimal results, the Dev column indicates the deviation between the optimal solutions obtained by the algorithm and the best known results. As can be seen from the abovementioned table, the MMSCA algorithm has achieved better results and has certain advantages compared with the PSO algorithm and the genetic algorithm. But, there is still a certain gap with the currently known optimal solutions, indicating that the algorithm still has room for improvement. Figure3 shows the convergence curve when the MMSCA algorithm solves the CVRP instance A-n60-k9.Figure 3
Convergence curve (A-n60-k9).


## 5.1. CVRP Problem Description and Model

Problem description: a central warehouse hask distribution vehicles, and the maximum load capacity of each distribution vehicle is Q. Now, we need to transport and distribute materials to n customers (nodes), how to arrange a certain number of vehicles to meet the needs of these customers, and make the total driving distance of vehicles shortest. The following constraints must also be met:(1)
All delivery vehicles start from the central warehouse and eventually return to the central warehouse(2)
Each delivery vehicle is not allowed to exceed the maximum load capacityQ(3)
Each customer can only be served once, and each vehicle can only take one routeFor the convenience of description, the following symbols are defined:D: total length of all vehicle pathsk: total number of vehiclesn: total number of customersv: vehicle number (1, 2, ..., k)(4)xijv=1,if vehiclevtravels from customerito customerj,0,else,yiv=1,if customerineeds to be fulfilled by vehiclev,0,else,cij: the distance between customer point i and jgi: the demand of the i-th customer (i = 1, 2, …, n)Q: the maximum loading capacity of the vehicleThe central warehouse number is 0, and the customer number isi (i = 1, 2, …, n). The CVRP mathematical model is expressed as follows:Objective function:(5)minD=∑i=0n∑j=0n∑v=0kcijxijv.Constraint conditions:(6)∑i=0nxijv=yjv,j=1,2,…,n;v=1,2,…,k,(7)∑j=0nxijv=yjv,i=1,2,…,n;v=1,2,…,k,(8)∑i=0ngiyiv≤Q,v=1,2,…,k,(9)∑v=1kyiv=1,i=1,2,…,n.Among them, equations (6) and (7) are traffic flow constraints, requiring a car to leave a customer node after it has completed service; formula (8) represents the vehicle capacity constraint and indicates that the total customer demand on the route served by vehicle v cannot exceed the vehicle loading capacity Q; formula (9) ensures that each customer can only be served by one vehicle.


## 5.2. MMSCA Algorithm for CVRP

The MMSCA algorithm is a continuous space algorithm, but the CVRP problem is an integer programming problem, so it needs to be modified in the implementation process.(1)
Encoding and decodingEncoding: using natural number coding, each individual in the population corresponds to a unique arrangement from 1 ton, and each individual corresponds to a distribution scheme.Decoding: arrange the vehicles according to the sequence of customers in the distribution scheme and the constraint of maximum loading capacity. That is, it is sequentially included in the path of the first car according to the customer’s coding order, and the second car’s path is arranged until the maximum load of the first car is exceeded.(2)
Evaluation criteriaThe total length of the vehicle path is used to evaluate all individuals and the merits of each distribution scheme.(3)
Implementation processAccording to the abovementioned coding method, each population is generated. Each individual (distribution scheme) is evaluated according to the evaluation criteria. Update each individual with formula (3) to generate a new distribution scheme. According to the constraint conditions, the actual vehicle path is generated and evaluated. In the process of updating with formula (3), integer specification constraints are required to avoid generating infeasible solutions.


## 5.3. Simulation and Results Analysis

In this paper, five standard VRPLIB test samples are selected for testing, and the test results of the MMSCA algorithm are compared with the PSO algorithm [55] and the GA algorithm. Table 4 shows the experimental results. In the experiment, the population number of MMSCA algorithm is divided two groups, the number of individuals in each group is 50, the solution is thirty times, and the number of iterations is 10,000. During the solution process, the best solution result is recorded.Table 4
Comparison of MMSCA and other two algorithms.
Data set
Best known results
MMSCA
PSO
GA
Best
Dev (%)
Best
Dev (%)
Best
Dev (%)
A-n32-k5
784
808
3.06
829
5.73
818
4.34
A-n33-k5
661
690
4.39
705
6.65
674
1.97
A-n39-k6
831
868
4.45
872
6.08
866
5.35
A-n46-k7
914
964
5.47
977
6.89
957
4.7
A-n60-k9
1408
1426
1.28
1476
4.83
1410
0.14Where the Best column represents the known optimal results, the Dev column indicates the deviation between the optimal solutions obtained by the algorithm and the best known results. As can be seen from the abovementioned table, the MMSCA algorithm has achieved better results and has certain advantages compared with the PSO algorithm and the genetic algorithm. But, there is still a certain gap with the currently known optimal solutions, indicating that the algorithm still has room for improvement. Figure3 shows the convergence curve when the MMSCA algorithm solves the CVRP instance A-n60-k9.Figure 3
Convergence curve (A-n60-k9).


## 6. Conclusion

Firstly, in view of the problems existing in the SCA algorithm update process, this paper proposes multigroup multistrategy SCA algorithm (MMSCA). The algorithm contains multiple populations with the same number of individuals, and each population performs a different update strategy. Multiple strategies include rand strategy and best strategy. The rand strategy can improve the global optimization ability of the algorithm, and the algorithm can still be disturbed at the later stage to avoid algorithm stagnation. The best strategy is responsible for keeping the algorithm stable and speeds up the convergence speed of the algorithm. Through numerical experiments on the test function, the MMSCA algorithm has a certain improvement in the accuracy and convergence speed of the original SCA algorithm. Finally, this paper successfully applies the MMSCA algorithm to solve CVRP (Capacitated Vehicle Routing Problem) and obtains better results, which further confirms the practicability and effectiveness of the algorithm. The next research direction will continue to improve the algorithm and apply it to more practical engineering problems.



---

*Source: 8184254-2020-03-27.xml*