# Cement Transport Vehicle Routing with a Hybrid Sine Cosine Optimization Algorithm

Authors: Vu Hong Son Pham; Van Nam Nguyen
Journal: Advances in Civil Engineering
 (2023)

---

## Abstract

This study will solve the classical vehicle routing problem, the goal is to generatek trips with the shortest distance for h customers with predetermined locations and needs.. The proposed solution to the classical vehicle routing problem is a hybrid sine cosine algorithm. The sine cosine algorithm is hybridized with the grey wolf optimizer, which is used in combination with the methods of tournament selection, opposition learning, and the mutation and crossover method to build the optimal routing plan for the means of transporting cement. To demonstrate the advantages of the developed hybrid sine cosine algorithm, this algorithm is evaluated and compared with modern algorithms such as sine cosine algorithm, dragonfly algorithm, grey wolf optimizer, ant lion optimizer, particle swarm optimization, modified hybrid particle swarm optimization, genetic algorithm, and the double-population genetic algorithm in case studies. The hybrid sine cos algorithm gives optimal results in these cases because it balances mining and exploration. Thus, the results of this study indicate that managers can use the developed hybrid sine cosine algorithm to create optimal vehicle routing plans to reduce transportation distances.


---

## Body

## 1. Introduction

The TSP problem is computationally complex [1]. In this problem, for n cities, 1/2×n−1! paths are possible. For example, if n = 16, the number of possible paths is 6.54 × 1011; thus, the number of paths is too high in the TSP. The VRP is an extension of the TSP; thus, the VRP has considerably high computational complexity.In the classical vehicle routing problem, which is an extended version of the traveling salesman problem, the objective is to generate a set ofk trips with the shortest distance or minimum cost for h customers whose locations and demands are predetermined. Each vehicle travels to and from a fixed location and satisfies some associated constraints. The vehicle routing problem can be solved using many methods, such as linear programming, genetic algorithm (GA), ant lion optimizer (ALO), dragonfly algorithm (DA), particle swarm optimization (PSO), modified hybrid particle swarm optimization (MHPSO), and double population genetic algorithm (DPGA).The vehicle routing problem (VRP) is a classical NP-hard problem that is difficult to not only solve but also define. According to Laporte [2], the VRP cannot be precisely defined because of the diversity and complexity of the binding requirements in this problem (e.g., time, distance, cost, pick-up and delivery, and capacity). Therefore, studies should focus on the most important parameters such as distance [3], cost [4], and time and CO2 emissions [5] when solving the VRP. According to Liu et al. [6], the main difference between the traveling salesman problem (TSP) and VRP is that in the VRP, multiple routes can be created to pass through all nodes under the condition of limited vehicle capacity. Because of the VRP’s complexity, almost all studies on this problem have attempted to solve it by using heuristic and meta-heuristic methods.The VRP problem has attracted the attention of many authors because of its practical applicability. In fact, there cannot be a vehicle that can hold goods to deliver to customers when the number of customers is too large and the goods are too bulky in size, while it may be assumed that such a vehicle exists, it remains an unattainable assumption to deliver goods on time to customers when multiple orders are placed at the same time. We know that each vehicle will have a certain capacity and load, so it is necessary to plan the routing of delivery vehicles to meet the daily needs of customers. Regardless of the method used, the researchers want to provide the optimal solution of the objective function: cost, distance, delivery time, and CO2 emissions, to deliver goods to customers from one repository [7, 8] or from multiple repositories [9, 10]. The issue of optimizing CO2 emissions has been studied a lot in recent years [6, 11] because of global warming and countries starting to tax the amount of CO2 emissions from transport vehicles.Nowadays, optimization algorithms are applied in many different fields. In recent years optimization algorithms are being developed rapidly such as the monarch butterfly optimization (MBO) [12], slime mold algorithm (SMA) [13], moth search algorithm (MSA) [14], hunger games search (HGS) [15], Runge–Kutta method (RUN) [16], colony predation algorithm (CPA) [17], weIghted meaN oF vectOrs (INFO) [18], Harris hawks optimization (HHO) [19, 20], improvement of trajectory tracking by robot manipulator based on a new cooperative optimization algorithm [21], optimal design of low computational burden model predictive control based on SSDA towards autonomous vehicle under vision dynamics [22], improved grey wolf optimizer based on opposition and quasi learning approaches for optimization [23], effective nonlinear model predictive control scheme tuned by improved NN for robotic manipulators [24], GSA-based design of dual proportional integral load frequency controllers for nonlinear hydrothermal power system [25], development of an IoT architecture based on a deep neural network against cyber attacks for automated guided vehicles [26], reliable deep learning and IoT-based monitoring system for secure computer numerical control machines against cyber-attacks with experimental verification [27], a multistrategy-enhanced sine cosine algorithm for global optimization and constrained practical engineering problems [28], optimal allocation of distributed generators in active distribution networks using a new oppositional hybrid sine cosine muted differential evolution algorithm [29], and sine cosine algorithm with multigroup and multistrategy for solving CVRP [30].This study combines the sine-cosine algorithm with the grey wolf optimizer, combined with tournament selection, adversarial learning, mutation crossover, and other methods, to obtain the optimal path scheme for cement transportation creation. This combined algorithm is called the hybrid SCA (HSCA). The SCA with outstanding strength in expanding the search space and GWO algorithm with outstanding mining ability is used in the search for optimal results. The TS method improves the ability to select individuals in the population to run the algorithm. The OBL method enhances global discoverability and enhances local mining through the convergence acceleration parameter, the MCS method increases the chance of finding optimal results through transformability and improves the ability to discover. From there, the HSCA algorithm will help the VRP problem achieve the best balance between the discovery and mining stages. The study will focus on the application of the HSCA algorithm to discover a routing plan for cement transport vehicles so that “the total delivery distance between the nodes is the shortest.”In this study, a new algorithm HSCA (SCA-GWO-OBL-MCS) was created and used to solve the CVRP problem of distance optimization, saving logistics costs. HSCA has proven its improvement effectively compared to other algorithms by 2 case studies presented in Chapter 4.


## 2. Literature Review

The VRP has been studied for more than 60 years [31, 32], with diverse objectives being adopted and diverse solutions being proposed. When considering distance and customer demands in the VRP [33], this problem can be solved using the “3-opt” model and mixed-integer linear programming (MILP) if the vehicles have the same size or different sizes, respectively [34].Anbuudayasankar and Mohandas [3] used MILP to optimize the pick-up and delivery of commodities at 13 nodes under different distances and customer demands. Moreover, Wang et al. [35] considered travel and service times in the VRP and solved this problem using the ant colony optimization (ACO) algorithm. Qi and Hu [4] solved the VRP for the transportation of frozen commodities to 13 locations by attempting to minimize vehicle damage, fuel costs, and refrigeration costs.Reed et al. [36] used ant colony system (ACS) to route vehicles for nodes in cyberspace and extended it for modeling the usage of multichambered vehicle to sort waste. A reasonable solution to the VRP reduced delivery costs by 15% in a management science project at E. I. Du Pont, Inc. [33]. Venkata Narasimha et al. [37] formulated a VRP that is different from the traditional min-max multidepot vehicle routing problem to reduce the travel time of the vehicle that travels the longest distance. Such a reduction is meaningful in emergency response scenarios to minimize the arrival time of any customer. In addition, some researchers have considered carbon emissions for effectively solving the VRP. Liu et al. [6] used the genetic algorithm (GA) to identify the minimal-carbon-footprinttime-dependentheterogeneous-fleet vehicle routing problem with alternative paths under different vehicle capacities and vehicle speeds (the vehicle speed changes at different delivery times during a day). Wang et al. [5] used a GA-based method to optimize a cold cargo distribution route in China for minimizing the carbon tax to be paid, travel time, and transportation cost.A MILP model developed in 2016 by Afshar-Bakeshloo et al. [8] provided a VRP problem-solving model with heterogeneous vehicle capacity to serve a group of customers in a predetermined time period; in this model, in addition to cost optimization, emissions and customer satisfaction are also considered. In this paper [38], an accurate heuristic-based approach is developed to solve the green vehicle routing problem, which extends the classical vehicle routing problem by considering a limited range of vehicles with limited refueling infrastructure. In 2019, Wang [9] combined 3 algorithms Clarke and Wright savings heuristic algorithm, the sweep algorithm, and the multiobjective particle swarm optimization algorithm to solve the problem of routing vehicles with many different warehouses. This is a 2-objective model of CO2 emissions and operating costs and it also implements a penalty function for early or late delivery to reduce waiting times and improve customer satisfaction. When it comes to customer satisfaction, Wang says that finding the shortest distance sometimes also falls short of goals for cost and minimum CO2 emissions.In 2020, Zhang proposed a [10] multidepot green vehicle routing problem, in which clean fuel vehicles start from different depots; after serving the customer, the vehicle will have to return to the original warehouse with the goal of reducing CO2 emissions to the environment because there is not enough fuel, and the vehicle will have to go to the station to refuel; the two-stage ant colony system method is proposed to solve this problem. In addition, the VRP problem is also known in another form as the dynamic problem, Khouadjia et al. [39] used particle swarm optimization and variable neighborhood search to solve this dynamic vehicle routing problem. In the dynamic vehicle routing problem, new orders appear when the goods plan is being delivered, so the routes have to be rearranged to deliver goods to the customer while the old model is still in progress, this is also an extended problem of the traditional VRP problem.


## 3. Materials and Methods

Chapter3 identifies the VRP problem and introduces the hybrid SCA methods with GWO, OLB, MCS, and TS applied to the case study in Chapter 4.


### 3.1. Description of VRP Problem

There are many documents on how to solve the VRP problem according to different definitions. According to Bodin’s definition [40], the VRP problem is developed through the mixed-integer programming (MIP) in which the variables are integers associated between the arcs of the location. This model is also called as vehicle flow model. Another quite effective way of describing the capacity problem of VRP is introduced by Shan and Wang [41] which is described as a summation model for the problems and optimization is implemented by the particle swarm optimization (PSO) which is quite effective.The CVRP problem is specifically defined by Shan and Wang [41] as follows:It is assumed that there is a warehouse and vehicles will transport commodity to predetermined customers from the warehouse, and after delivery, the vehicles will return to the warehouse. And the additional constraints are given as follows:Cargo vehicles are limited in capacityEach customer comes to deliver the commodity only one timeObjective: to optimize the delivery distance of many vehicles at the same time.Variables:(1)D=totaldistancetravelledbyallvehicles,xijs=1,vehiclesdepartfromitoj0,otherwise,yis=1,customeriisservedbyvehicles0,otherwise.Coefficients:(2)cij=costformcustomeritocustomerj,gi=thedemandofthithcustomeri=1,2,3…,h,h=totalnumberofcustomer,k=totalnumberofvehicle,qs=capacityofvehicles,s=the.vehicle.numberi=1,2,3…,k.Objective function:(3)MinD=∑i=oh∑j=0h∑s=1kcijxijs.Constraints:(4)∑i=0hxijs=yjs,j=1,2,…,h,s=1,2,⋯,k,(5)∑i=0hxijs=yis,j=1,2,…,h,s=1,2,…,k,(6)∑i=0hgiyis≤qsyis,s=1,2,…,k,(7)∑s=1kyis=1,i=1,2,3,…,hk,i=0.Equation (3) presents the VRP’s objective function. In this equation, xijs is a binary variable that indicates whether the current path has been selected. Equations (4) and (5) indicate that only one path exists between a vehicle and a specific customer. Equation (6) incorporates vehicle capacity as a limitation. Equation (7) indicates that each customer is served by only one vehicle and that the warehouse is served by k vehicles.


### 3.2. Introduction of SCA

The SCA, which was introduced by Mirjalili [42], is a population-based optimization method. The SCA generates many initial choices and allows them to fluctuate toward the best solution by using the sine and cosine functions.The optimization process of population-based optimization algorithms is divided into two phases: exploitation and exploration [42].The equation represents the two phases of exploitation and exploration follows:(8)Xit+1=Xit+r1∗sinr2∗r3∗P−Xit,(9)Xit+1=Xit+r1∗cosr2∗r3∗P−Xit.The two formulas (8) and (9) are combined as follows:(10)Xit+1=Xit+r1∗sinr2∗r3∗P−Xit;r4≤0.5Xit+r1∗cosr2∗r3∗P−Xit;r4≥0.5,where r4 is a random value in the interval 0;1.The main parameters in formulas (7)–(9) are r1,r2,r3, and r4.(i)
r1 shows different directions within the space between the solution and the destination or the space outside the solution.(ii)
r2 determines the distance to travel outward or toward the destination.(iii)
r3 gives random weights to emphasize the weights of the processes of exploration (r3 > 1) or exploitation (r3 < 1).Effects of sine and cosine in equations (8) and (9) are illustrated in Figure 1. This figure shows how equations (8) and (9) define the spatial region between two solutions in the search space. The two-dimensional model is illustrated in Figure 1, however, the search space can be extended to higher dimensions. The cyclical model of sine and cosine functions allows repositioning around a different solution. This way certainly ensures the exploitation of the space defined between the two solutions.Figure 1
Effects of the sine and cosine function in updating the latest value [43].In addition, in order to avoid local optimization, solutions shall be searched outside the space between the solutions and the destination. To achieve this, it is necessary to change the ranges of the sine and cosine functions shown in Figure2.Figure 2
Effects of sine and cosine in formulas (7) and (8) on the next region and position.The conceptual model of the effects of sine and cosine functions in the range (−2, 2) is illustrated in Figure3. Figure 3 shows that changing the range of the sine and cosine functions will lead to one solution which changes the position of this solution itself with another.Figure 3
Effects of the function in the range (−2, 2) enabling a solution to go outside or around the destination [42, 43].For a good algorithm, a balance of the two phases of exploration and exploitation is requested to discover promising regions of the search space to reach the global optimization.For SCA, in order to balance the exploration and exploitation, the range of sine and cosine functions in formulas (7)–(9) is changed by the following formula:(11)r1=a−taT,where t is the current iteration, T is the maximum number of iterations, and a is a constant.Figure4 shows that equation (11) reduces the range of sine and cosine functions over iterations. Based on Figures 3 and 4, it can be seen that the SCA algorithm shall explore the search area when the range of sine and cosine functions is in the interval 1,2 and −2,−1. However, the algorithm shall exploit the search space when the range is in the interval (−1, 1) (see Algorithm 1).Figure 4
Model of descending the range of sine and cosine functions (a = 3).Algorithm 1: Steps of SCA algorithm [41].
Initialize a set of search agents (solutions) (X).DoEvaluate each of the search agents by the objective function.Update the best solution obtained so far (P = X∗)Updater1, r2, r3, and r4Update the position of search agents using equation (10)While (t < maximum number of iterations)Return the best solution obtained so far as the global optimum.The SCA algorithm starts the optimization with a set of random solutions. The algorithm then saves the best solutions obtained so far, assigns it as the destination, and updates other solutions with respect to it. Meanwhile, the scope of the sine and cosine functions is updated to emphasize the exploitation of the search space as the iteration counter increases. The SCA algorithm terminates the optimization process when the iteration counter goes higher than the maximum number of iterations by default. However, any other termination condition can be considered such as maximum number of function evaluation or the accuracy of the global optimum obtained. The flowchart of SCA algorithm is another demonstration of Figure5.Figure 5
The flowchart of SCA algorithm.


### 3.3. Introduction of OBL and MCS Methods

#### 3.3.1. OBL Method

The concept of opposition-based learning and its applications was introduced in 2005 by Tizhoosh [44] (illustrated in Figure 6).Figure 6
OBL method.LetPx1,x2,…,xn be a point in n-dimensional space, where x1,x2,…,xn∈R and xi∈ai,bi∀i∈1,2,…,n. The opposite point of P is defined as P¯x1¯,x2¯,…,xn¯, where(12)xn¯=ai+bi−xi.Assumef (x) is a suitable function used to measure the solution’s optimum. If fP¯≥fP, then the point P can be replaced by P¯, otherwise we shall continue with P.


### 3.4. Introduction of MCS Method

#### 3.4.1. MCS Method

This method is introduced by Roseline and Saravanan [45] as follows:Mutation and crossover are popular exploitation algorithms in various phases of optimization. Eachxi=xi1,xi2,...,xin is a vector of n directions (n dimensions).Step 1.
Mutation.
The mutation algorithm can generate a mutation vectorui by choosing random components from the directions of the original vector xi and reassign the value in the specified domain of such direction as follows:(13)uij=randxij∈Domainofxij;rand≤pc.xij,otherwise.Step 2.
Crossover.
The crossover algorithm can generate a new vectorvi by using a crossover with the mutation vector. New vector vi is generated by random selection of components from vector ui and target vector xi based on the probability factor pc.(14)vij=uij,rand≤pcorj=jo,xij,otherwise,where pc is the probability factor which controls the population diversity and reduces the risk of local optimization (set pc = 0.1 in this study) and j0 is an indicator belonging to (1, 2, 3, …, n) to ensure that vector vi contains at least one element from the mutation vector ui.


### 3.5. Introduction of Tournament Selection Method

In the SCA algorithm, the roulette method in the individual selection step is replaced by tournament selection. The tournament selection procedure randomly selectsk elements and compares the values of the objective function. We selected elements with better objective function values. This technique helps to improve the ability to quickly find the optimal value of the SCA algorithm.


### 3.6. Introduction of GWO

In 2014, Mirjalili et al. [46] introduced the GWO algorithm. We approached hunting and hierarchical leadership like wolves in the wild, where there are 4 levels: alpha, beta, delta, and omega. The first three wolves will be the best variant of the population, and omega (ω) is the population variant. Wolf population has 2 stages: siege and hunt for prey.The siege phase is displayed as follows:(15)d⟶=c.x⟶pt−x⟶t,x⟶t+1=x⟶t−a⟶.d⟶,wherex⟶t is the wolf’s position in iteration t, xt is the prey’s position, and vectors a⟶ and c⟶ are coefficient vectors, computed as follows:(16)a⟶=2l.r1,c⟶=2r2.Hunting phase: To simulate hunting behavior, Mirjalili assumes that the knowledge of the potential position of the prey is known by alpha, beta, and delta based on its experience as follows:(17)d⟶α=c⟶1.x⟶α−x⟶,d⟶β=c⟶2.x⟶β−x⟶,d⟶δ=c⟶3.x⟶δ−x⟶,x⟶1=x⟶α−a⟶1.d⟶α,x⟶2=x⟶β−a⟶2.d⟶β,x⟶3=x⟶δ−a⟶3.d⟶δx⟶1+x⟶2+x⟶33,When searching and attacking prey,a⟶ is a random value in the range of (−2a, 2a). When a⟶<1, random prey value is attacked by wolves, it is the mining stage. When a⟶>1, wolves are forced to ignore their prey in search of better prey [47].Another parameter that affects the decoy search is thatc has a value in the range (0, 2), and c⟶ will randomly and suddenly update the value of the solution to avoid local optimization. If c > 1, the solution converges towards the prey, and if c < 1, the solution moves away from the prey to find new prey.Finally, the flowchart of the SCA-GWO-TS-OBL-MCS algorithm is shown in Figure7.Figure 7
The flowchart of HSCA.


## 3.1. Description of VRP Problem

There are many documents on how to solve the VRP problem according to different definitions. According to Bodin’s definition [40], the VRP problem is developed through the mixed-integer programming (MIP) in which the variables are integers associated between the arcs of the location. This model is also called as vehicle flow model. Another quite effective way of describing the capacity problem of VRP is introduced by Shan and Wang [41] which is described as a summation model for the problems and optimization is implemented by the particle swarm optimization (PSO) which is quite effective.The CVRP problem is specifically defined by Shan and Wang [41] as follows:It is assumed that there is a warehouse and vehicles will transport commodity to predetermined customers from the warehouse, and after delivery, the vehicles will return to the warehouse. And the additional constraints are given as follows:Cargo vehicles are limited in capacityEach customer comes to deliver the commodity only one timeObjective: to optimize the delivery distance of many vehicles at the same time.Variables:(1)D=totaldistancetravelledbyallvehicles,xijs=1,vehiclesdepartfromitoj0,otherwise,yis=1,customeriisservedbyvehicles0,otherwise.Coefficients:(2)cij=costformcustomeritocustomerj,gi=thedemandofthithcustomeri=1,2,3…,h,h=totalnumberofcustomer,k=totalnumberofvehicle,qs=capacityofvehicles,s=the.vehicle.numberi=1,2,3…,k.Objective function:(3)MinD=∑i=oh∑j=0h∑s=1kcijxijs.Constraints:(4)∑i=0hxijs=yjs,j=1,2,…,h,s=1,2,⋯,k,(5)∑i=0hxijs=yis,j=1,2,…,h,s=1,2,…,k,(6)∑i=0hgiyis≤qsyis,s=1,2,…,k,(7)∑s=1kyis=1,i=1,2,3,…,hk,i=0.Equation (3) presents the VRP’s objective function. In this equation, xijs is a binary variable that indicates whether the current path has been selected. Equations (4) and (5) indicate that only one path exists between a vehicle and a specific customer. Equation (6) incorporates vehicle capacity as a limitation. Equation (7) indicates that each customer is served by only one vehicle and that the warehouse is served by k vehicles.


## 3.2. Introduction of SCA

The SCA, which was introduced by Mirjalili [42], is a population-based optimization method. The SCA generates many initial choices and allows them to fluctuate toward the best solution by using the sine and cosine functions.The optimization process of population-based optimization algorithms is divided into two phases: exploitation and exploration [42].The equation represents the two phases of exploitation and exploration follows:(8)Xit+1=Xit+r1∗sinr2∗r3∗P−Xit,(9)Xit+1=Xit+r1∗cosr2∗r3∗P−Xit.The two formulas (8) and (9) are combined as follows:(10)Xit+1=Xit+r1∗sinr2∗r3∗P−Xit;r4≤0.5Xit+r1∗cosr2∗r3∗P−Xit;r4≥0.5,where r4 is a random value in the interval 0;1.The main parameters in formulas (7)–(9) are r1,r2,r3, and r4.(i)
r1 shows different directions within the space between the solution and the destination or the space outside the solution.(ii)
r2 determines the distance to travel outward or toward the destination.(iii)
r3 gives random weights to emphasize the weights of the processes of exploration (r3 > 1) or exploitation (r3 < 1).Effects of sine and cosine in equations (8) and (9) are illustrated in Figure 1. This figure shows how equations (8) and (9) define the spatial region between two solutions in the search space. The two-dimensional model is illustrated in Figure 1, however, the search space can be extended to higher dimensions. The cyclical model of sine and cosine functions allows repositioning around a different solution. This way certainly ensures the exploitation of the space defined between the two solutions.Figure 1
Effects of the sine and cosine function in updating the latest value [43].In addition, in order to avoid local optimization, solutions shall be searched outside the space between the solutions and the destination. To achieve this, it is necessary to change the ranges of the sine and cosine functions shown in Figure2.Figure 2
Effects of sine and cosine in formulas (7) and (8) on the next region and position.The conceptual model of the effects of sine and cosine functions in the range (−2, 2) is illustrated in Figure3. Figure 3 shows that changing the range of the sine and cosine functions will lead to one solution which changes the position of this solution itself with another.Figure 3
Effects of the function in the range (−2, 2) enabling a solution to go outside or around the destination [42, 43].For a good algorithm, a balance of the two phases of exploration and exploitation is requested to discover promising regions of the search space to reach the global optimization.For SCA, in order to balance the exploration and exploitation, the range of sine and cosine functions in formulas (7)–(9) is changed by the following formula:(11)r1=a−taT,where t is the current iteration, T is the maximum number of iterations, and a is a constant.Figure4 shows that equation (11) reduces the range of sine and cosine functions over iterations. Based on Figures 3 and 4, it can be seen that the SCA algorithm shall explore the search area when the range of sine and cosine functions is in the interval 1,2 and −2,−1. However, the algorithm shall exploit the search space when the range is in the interval (−1, 1) (see Algorithm 1).Figure 4
Model of descending the range of sine and cosine functions (a = 3).Algorithm 1: Steps of SCA algorithm [41].
Initialize a set of search agents (solutions) (X).DoEvaluate each of the search agents by the objective function.Update the best solution obtained so far (P = X∗)Updater1, r2, r3, and r4Update the position of search agents using equation (10)While (t < maximum number of iterations)Return the best solution obtained so far as the global optimum.The SCA algorithm starts the optimization with a set of random solutions. The algorithm then saves the best solutions obtained so far, assigns it as the destination, and updates other solutions with respect to it. Meanwhile, the scope of the sine and cosine functions is updated to emphasize the exploitation of the search space as the iteration counter increases. The SCA algorithm terminates the optimization process when the iteration counter goes higher than the maximum number of iterations by default. However, any other termination condition can be considered such as maximum number of function evaluation or the accuracy of the global optimum obtained. The flowchart of SCA algorithm is another demonstration of Figure5.Figure 5
The flowchart of SCA algorithm.


## 3.3. Introduction of OBL and MCS Methods

### 3.3.1. OBL Method

The concept of opposition-based learning and its applications was introduced in 2005 by Tizhoosh [44] (illustrated in Figure 6).Figure 6
OBL method.LetPx1,x2,…,xn be a point in n-dimensional space, where x1,x2,…,xn∈R and xi∈ai,bi∀i∈1,2,…,n. The opposite point of P is defined as P¯x1¯,x2¯,…,xn¯, where(12)xn¯=ai+bi−xi.Assumef (x) is a suitable function used to measure the solution’s optimum. If fP¯≥fP, then the point P can be replaced by P¯, otherwise we shall continue with P.


## 3.3.1. OBL Method

The concept of opposition-based learning and its applications was introduced in 2005 by Tizhoosh [44] (illustrated in Figure 6).Figure 6
OBL method.LetPx1,x2,…,xn be a point in n-dimensional space, where x1,x2,…,xn∈R and xi∈ai,bi∀i∈1,2,…,n. The opposite point of P is defined as P¯x1¯,x2¯,…,xn¯, where(12)xn¯=ai+bi−xi.Assumef (x) is a suitable function used to measure the solution’s optimum. If fP¯≥fP, then the point P can be replaced by P¯, otherwise we shall continue with P.


## 3.4. Introduction of MCS Method

### 3.4.1. MCS Method

This method is introduced by Roseline and Saravanan [45] as follows:Mutation and crossover are popular exploitation algorithms in various phases of optimization. Eachxi=xi1,xi2,...,xin is a vector of n directions (n dimensions).Step 1.
Mutation.
The mutation algorithm can generate a mutation vectorui by choosing random components from the directions of the original vector xi and reassign the value in the specified domain of such direction as follows:(13)uij=randxij∈Domainofxij;rand≤pc.xij,otherwise.Step 2.
Crossover.
The crossover algorithm can generate a new vectorvi by using a crossover with the mutation vector. New vector vi is generated by random selection of components from vector ui and target vector xi based on the probability factor pc.(14)vij=uij,rand≤pcorj=jo,xij,otherwise,where pc is the probability factor which controls the population diversity and reduces the risk of local optimization (set pc = 0.1 in this study) and j0 is an indicator belonging to (1, 2, 3, …, n) to ensure that vector vi contains at least one element from the mutation vector ui.


## 3.4.1. MCS Method

This method is introduced by Roseline and Saravanan [45] as follows:Mutation and crossover are popular exploitation algorithms in various phases of optimization. Eachxi=xi1,xi2,...,xin is a vector of n directions (n dimensions).Step 1.
Mutation.
The mutation algorithm can generate a mutation vectorui by choosing random components from the directions of the original vector xi and reassign the value in the specified domain of such direction as follows:(13)uij=randxij∈Domainofxij;rand≤pc.xij,otherwise.Step 2.
Crossover.
The crossover algorithm can generate a new vectorvi by using a crossover with the mutation vector. New vector vi is generated by random selection of components from vector ui and target vector xi based on the probability factor pc.(14)vij=uij,rand≤pcorj=jo,xij,otherwise,where pc is the probability factor which controls the population diversity and reduces the risk of local optimization (set pc = 0.1 in this study) and j0 is an indicator belonging to (1, 2, 3, …, n) to ensure that vector vi contains at least one element from the mutation vector ui.


## 3.5. Introduction of Tournament Selection Method

In the SCA algorithm, the roulette method in the individual selection step is replaced by tournament selection. The tournament selection procedure randomly selectsk elements and compares the values of the objective function. We selected elements with better objective function values. This technique helps to improve the ability to quickly find the optimal value of the SCA algorithm.


## 3.6. Introduction of GWO

In 2014, Mirjalili et al. [46] introduced the GWO algorithm. We approached hunting and hierarchical leadership like wolves in the wild, where there are 4 levels: alpha, beta, delta, and omega. The first three wolves will be the best variant of the population, and omega (ω) is the population variant. Wolf population has 2 stages: siege and hunt for prey.The siege phase is displayed as follows:(15)d⟶=c.x⟶pt−x⟶t,x⟶t+1=x⟶t−a⟶.d⟶,wherex⟶t is the wolf’s position in iteration t, xt is the prey’s position, and vectors a⟶ and c⟶ are coefficient vectors, computed as follows:(16)a⟶=2l.r1,c⟶=2r2.Hunting phase: To simulate hunting behavior, Mirjalili assumes that the knowledge of the potential position of the prey is known by alpha, beta, and delta based on its experience as follows:(17)d⟶α=c⟶1.x⟶α−x⟶,d⟶β=c⟶2.x⟶β−x⟶,d⟶δ=c⟶3.x⟶δ−x⟶,x⟶1=x⟶α−a⟶1.d⟶α,x⟶2=x⟶β−a⟶2.d⟶β,x⟶3=x⟶δ−a⟶3.d⟶δx⟶1+x⟶2+x⟶33,When searching and attacking prey,a⟶ is a random value in the range of (−2a, 2a). When a⟶<1, random prey value is attacked by wolves, it is the mining stage. When a⟶>1, wolves are forced to ignore their prey in search of better prey [47].Another parameter that affects the decoy search is thatc has a value in the range (0, 2), and c⟶ will randomly and suddenly update the value of the solution to avoid local optimization. If c > 1, the solution converges towards the prey, and if c < 1, the solution moves away from the prey to find new prey.Finally, the flowchart of the SCA-GWO-TS-OBL-MCS algorithm is shown in Figure7.Figure 7
The flowchart of HSCA.


## 4. Application of the HSCA to Solve the VRP

### 4.1. Case Study 1

The developed HSCA was evaluated against other algorithms in solving the problem of [48] (case study 1).This problem is expressed as follows. For a central warehouse, eight customers are served by two trucks, each of which has a capacity of 8 units. The matrix of travel distances and customer demands is presented in Table1. The requirement is that two vehicles should deliver the goods so that the shortest total delivery distance is achieved and the conditions of the VRP stated in Section 3 are satisfied.Table 1
Matrix of travel distances and customer demands case study 1 [48].
Customer012345678Demand00467.5920101681406.541057.511101266.507.510107.57.57.5237.547.5010599151491010100107.57.51025205105100797.516107.57.597.5707104716117.567.597010288107.515107.5101002A personal laptop with an 11th Gen Intel(R) Core(TM) i7-1165G7@ 2.80 GHz processor was used to run each algorithm 20 times with 20 search agents in 50 iterations. The HSCA was programmed in Java. The shortest distance obtained was 67.5 units, and the following paths were obtained in Java for the two vehicles (in the output order in Java):Vehicle 1: 0 -> Customer6 -> Customer7 -> Customer 4 -> 0.Vehicle 2: 0 -> Customer1 -> Customer3 -> Customer5 -> Customer8 -> Customer 2 -> 0.Figure8 depicts the HSCA’s optimal solution, and Table 2 presents the smallest number of iterations required for obtaining the optimal result with different algorithms. The aforementioned figure and table indicate that the HSCA can search for optimum solutions faster and more efficiently than the other algorithms used in this study.Figure 8
Optimal values obtained by the HSCA and SCA after 20 runs in case study 1.Table 2
Optimal results obtained with different algorithms after 20 runs in case study 1.
HSCASCADAPSOALOMHPSO∗ [48]DPGA∗ [48]SGA∗[48]Generation25912861845The results obtained with the HSCA, SCA, DA, PSO, and ALO were compared. The results indicated that the HSCA achieved convergence faster than the other four algorithms. Figure9 displays the average best solutions obtained with the aforementioned five algorithms after 50 iterations and 20 runs.Figure 9
Optimal average values were obtained with different algorithms after 20 runs in case study 1.Table3 presents the results obtained in case study 1 when using different algorithms. The average distance value obtained with the HSCA (i.e., 67.675 units) was lower than those obtained with the other algorithms.Table 3
Best solutions obtained in case study 1 with different algorithms after 20 runs.
Distribution of optimum solutionsMaxMinMeanHSCA67.56867.567.567.56967.567.67568.567.567.567.567.567.56868686867.567.567.567.567.5SCA69686968686967.568.0256869.567.567.568696867.567.567.56867.56867.567.5DA71.567.571.56867.571.567.568.725697070.568697067.567.5696867.5686867.569ALO71.56871.56867.571.567.569.150697070.56869706871696871.5686867.569MHPSO69.567.56969707067.568.87569.5706967.567.56969.5697067.5706967.57067.5PSO67.5707069697067.568.9506869707068.568.568.567.568707067.569.56969.5DPGA706967.571697267.569.55070.57267.571.56967.569717067.570.56969.57169SGA697273.5697075.567.570.4257167.5696975.57069.5697369747069.56970Bold values represent better HSCA search results than other algorithms.The results obtained with the HSCA were more stable (i.e., had a smaller deviation) than those obtained with the other algorithms, and the global optimal solution was obtained with the HSCA. Thus, the HSCA can be used for cement vehicle routing. Cement vehicles have similar capacities and are delivered to different warehouses and distribution stores daily. The HSCA can be used to obtain optimal routes for cement vehicles depending on the delivery case and time of day.


### 4.2. Case Study 2: Real Problem of Cement Delivery to Customers

The real problem of a cement distribution agent (case study 2) is expressed as follows: In 1 day, a cement distribution agent with a central warehouse must serve 30 customers by using five trucks, each of which has a maximum capacity of 90 cement bags during a single delivery. The matrix of travel distances and customer demands for case study 2 is presented in Table4. The requirement is that five vehicles should deliver the goods, such that the shortest total delivery distance is achieved and the relevant conditions of the VRP stated in Section 3 are satisfied.Table 4
Matrix of travel distances and customer demands for case study 2.
Node12345678910111213141516171819202122232425262728293031Demand1067543315505146401248612552424345575436295334443437458461643026701213564116967448585085917031110551043354827647186946985110828717354121087601761778864938631869413881111018979105727852445282233962443335870358165473423306157471176332531171622345359653559764963551564603506066602822577535654552565461303756472925301872572231106501161781600456389588270267287117610690867097618459524766739702751966165664502589494926423365494388587850713295807848223853911384674774760632507638251650943641966346231481488808044135655891994048883428898976040649263794480663965184652632342514489855040171012586423225849384003653344330533448423117412450454913505328535114850933057824925643603562202280644948202321828184473575628812126185866175702616925335062155673307942774658291049495594636910471325913157352642506334626205963195881706148744361403622582214521414527086476572339794320155904173156428643344199386885114656396715423194114587654344302256634108226232027171133647076435581587591643110137652114964805380731973820751008879679359744942416913306010174555883356764319663463058152675049155020291582798244296958871718571011125541068866394844798164231004903925392256627684597810072782019544310131619058346542942702820881539047251730848690544384699218203635891730867862183148776164277950254703135493951593975825053142129487916377050314617204648331767203925310261862616529446444688225327105225697714852412358744411932922173526039748186545890698520233464723447613214632421294319335915563049183907568693227544577122444717853298495882350821046193647482628439627475027364810182472082534865259255980804245819440867049797686516181682709369159271219263794446530527880514984953688764282849059658669369038915326191727469523518474844441347592251434144595439295432483638055431546828588582597266221389503545814556929784375445827101919155059651011329461102376577385685537563226581136910084826490548259534359036701730168239492239535550286269146358305872695044694547272615653603863143876263317091894053881045296756087789253688577201219461017038016A personal laptop was used to run each algorithm 20 times with 50 search agents in 200 iterations. The HSCA was programmed in Java. The best solution for the total distance was 701.1625 units. Figure10 displays optimal values obtained by the HSCA. The following paths were obtained in Java for the five vehicles (in the output order in Java):Figure 10
Optimal values obtained by the HSCA after 20 runs in case study 2. Route 1: 0 -> customer3 -> customer19 -> customer8 -> customer17 -> customer1 -> customer21 -> customer14 -> customer 9 -> 0. Route 2: 0 -> customer20 -> customer18 -> customer10 -> customer16 -> customer13 -> customer 22 -> 0. Route 3: 0 -> customer7 -> customer27 -> customer11 -> customer6 -> customer28 -> customer5 -> customer2 -> customer 15 -> 0. Route 4: 0 -> customer12 -> customer29 -> customer25 -> customer24 -> customer30 -> customer23 -> customer 4 -> 0. Route 5: 0 -> customer 26 -> 0.A comparison of the results obtained with the DA, PSO, ALO, the SCA, and the HSCA in case study 2 indicated that the HSCA converged faster than the other algorithms. Figure11 displays the average best solutions obtained with the different algorithms after 200 iterations and 20 runs.Figure 11
Optimal average values were obtained with different algorithms after 20 runs in case study 2.Table5 presents the maximum values, minimum values, mean values, and deviations to the best solution obtained with the different algorithms used in this study. After 200 iterations, 20 runs, and 50 agents, the HSCA obtained a maximum distance of 849.61 units and a minimum distance of 701.16 units (its optimal result); thus, the optimal result of the HSCA was superior to those of the SCA, PSO, DA, and ALO. In addition, the optimal results of the SCA, PSO, ALO, and DA exhibited deviations of 14.7%, 16.9%, 34.7%, and 37.5%, respectively, from the optimal result of the HSCA; thus, the results of the SCA and PSO were stable and more accurate than those of ALO and DA. In summary, in the problem of cement transport by five vehicles to 30 delivery points, the results obtained by the HSCA were superior to those obtained by the SCA, PSO, ALO, and DA.Table 5
Best solutions obtained with different algorithms after 20 runs in case study 2.
Distribution of optimum solutionsMaxMinMean% dev best solution (%)HSCA783.81838.27748.79822.01746.90849.61701.16791.590.0834.89799.94849.61821.61780.01793.50701.16800.64771.84821.79806.97768.76844.78719.23777.37SCA928.49994.701029.051026.16885.601119.50804.05960.5814.7888.461080.391029.57923.55804.051119.501018.73946.19947.45945.02985.59959.19893.72853.84952.38DA1122.721036.271153.791095.201158.851308.59964.441132.0137.51122.291101.741079.451197.041250.211128.741246.841061.991308.59969.30964.441230.521125.791138.421148.06ALO1165.86951.441049.491173.53971.981221.77944.211049.6934.71066.321087.11947.101089.851027.151061.551021.481061.001045.88944.211022.591007.741098.781221.77978.85PSO946.91987.621053.831209.331042.761209.33819.48965.3516.91140.71953.78881.51820.44924.56983.83823.341068.281019.84978.391056.59819.48872.88837.93884.95Bold values represent better HSCA search results than other algorithms.


## 4.1. Case Study 1

The developed HSCA was evaluated against other algorithms in solving the problem of [48] (case study 1).This problem is expressed as follows. For a central warehouse, eight customers are served by two trucks, each of which has a capacity of 8 units. The matrix of travel distances and customer demands is presented in Table1. The requirement is that two vehicles should deliver the goods so that the shortest total delivery distance is achieved and the conditions of the VRP stated in Section 3 are satisfied.Table 1
Matrix of travel distances and customer demands case study 1 [48].
Customer012345678Demand00467.5920101681406.541057.511101266.507.510107.57.57.5237.547.5010599151491010100107.57.51025205105100797.516107.57.597.5707104716117.567.597010288107.515107.5101002A personal laptop with an 11th Gen Intel(R) Core(TM) i7-1165G7@ 2.80 GHz processor was used to run each algorithm 20 times with 20 search agents in 50 iterations. The HSCA was programmed in Java. The shortest distance obtained was 67.5 units, and the following paths were obtained in Java for the two vehicles (in the output order in Java):Vehicle 1: 0 -> Customer6 -> Customer7 -> Customer 4 -> 0.Vehicle 2: 0 -> Customer1 -> Customer3 -> Customer5 -> Customer8 -> Customer 2 -> 0.Figure8 depicts the HSCA’s optimal solution, and Table 2 presents the smallest number of iterations required for obtaining the optimal result with different algorithms. The aforementioned figure and table indicate that the HSCA can search for optimum solutions faster and more efficiently than the other algorithms used in this study.Figure 8
Optimal values obtained by the HSCA and SCA after 20 runs in case study 1.Table 2
Optimal results obtained with different algorithms after 20 runs in case study 1.
HSCASCADAPSOALOMHPSO∗ [48]DPGA∗ [48]SGA∗[48]Generation25912861845The results obtained with the HSCA, SCA, DA, PSO, and ALO were compared. The results indicated that the HSCA achieved convergence faster than the other four algorithms. Figure9 displays the average best solutions obtained with the aforementioned five algorithms after 50 iterations and 20 runs.Figure 9
Optimal average values were obtained with different algorithms after 20 runs in case study 1.Table3 presents the results obtained in case study 1 when using different algorithms. The average distance value obtained with the HSCA (i.e., 67.675 units) was lower than those obtained with the other algorithms.Table 3
Best solutions obtained in case study 1 with different algorithms after 20 runs.
Distribution of optimum solutionsMaxMinMeanHSCA67.56867.567.567.56967.567.67568.567.567.567.567.567.56868686867.567.567.567.567.5SCA69686968686967.568.0256869.567.567.568696867.567.567.56867.56867.567.5DA71.567.571.56867.571.567.568.725697070.568697067.567.5696867.5686867.569ALO71.56871.56867.571.567.569.150697070.56869706871696871.5686867.569MHPSO69.567.56969707067.568.87569.5706967.567.56969.5697067.5706967.57067.5PSO67.5707069697067.568.9506869707068.568.568.567.568707067.569.56969.5DPGA706967.571697267.569.55070.57267.571.56967.569717067.570.56969.57169SGA697273.5697075.567.570.4257167.5696975.57069.5697369747069.56970Bold values represent better HSCA search results than other algorithms.The results obtained with the HSCA were more stable (i.e., had a smaller deviation) than those obtained with the other algorithms, and the global optimal solution was obtained with the HSCA. Thus, the HSCA can be used for cement vehicle routing. Cement vehicles have similar capacities and are delivered to different warehouses and distribution stores daily. The HSCA can be used to obtain optimal routes for cement vehicles depending on the delivery case and time of day.


## 4.2. Case Study 2: Real Problem of Cement Delivery to Customers

The real problem of a cement distribution agent (case study 2) is expressed as follows: In 1 day, a cement distribution agent with a central warehouse must serve 30 customers by using five trucks, each of which has a maximum capacity of 90 cement bags during a single delivery. The matrix of travel distances and customer demands for case study 2 is presented in Table4. The requirement is that five vehicles should deliver the goods, such that the shortest total delivery distance is achieved and the relevant conditions of the VRP stated in Section 3 are satisfied.Table 4
Matrix of travel distances and customer demands for case study 2.
Node12345678910111213141516171819202122232425262728293031Demand1067543315505146401248612552424345575436295334443437458461643026701213564116967448585085917031110551043354827647186946985110828717354121087601761778864938631869413881111018979105727852445282233962443335870358165473423306157471176332531171622345359653559764963551564603506066602822577535654552565461303756472925301872572231106501161781600456389588270267287117610690867097618459524766739702751966165664502589494926423365494388587850713295807848223853911384674774760632507638251650943641966346231481488808044135655891994048883428898976040649263794480663965184652632342514489855040171012586423225849384003653344330533448423117412450454913505328535114850933057824925643603562202280644948202321828184473575628812126185866175702616925335062155673307942774658291049495594636910471325913157352642506334626205963195881706148744361403622582214521414527086476572339794320155904173156428643344199386885114656396715423194114587654344302256634108226232027171133647076435581587591643110137652114964805380731973820751008879679359744942416913306010174555883356764319663463058152675049155020291582798244296958871718571011125541068866394844798164231004903925392256627684597810072782019544310131619058346542942702820881539047251730848690544384699218203635891730867862183148776164277950254703135493951593975825053142129487916377050314617204648331767203925310261862616529446444688225327105225697714852412358744411932922173526039748186545890698520233464723447613214632421294319335915563049183907568693227544577122444717853298495882350821046193647482628439627475027364810182472082534865259255980804245819440867049797686516181682709369159271219263794446530527880514984953688764282849059658669369038915326191727469523518474844441347592251434144595439295432483638055431546828588582597266221389503545814556929784375445827101919155059651011329461102376577385685537563226581136910084826490548259534359036701730168239492239535550286269146358305872695044694547272615653603863143876263317091894053881045296756087789253688577201219461017038016A personal laptop was used to run each algorithm 20 times with 50 search agents in 200 iterations. The HSCA was programmed in Java. The best solution for the total distance was 701.1625 units. Figure10 displays optimal values obtained by the HSCA. The following paths were obtained in Java for the five vehicles (in the output order in Java):Figure 10
Optimal values obtained by the HSCA after 20 runs in case study 2. Route 1: 0 -> customer3 -> customer19 -> customer8 -> customer17 -> customer1 -> customer21 -> customer14 -> customer 9 -> 0. Route 2: 0 -> customer20 -> customer18 -> customer10 -> customer16 -> customer13 -> customer 22 -> 0. Route 3: 0 -> customer7 -> customer27 -> customer11 -> customer6 -> customer28 -> customer5 -> customer2 -> customer 15 -> 0. Route 4: 0 -> customer12 -> customer29 -> customer25 -> customer24 -> customer30 -> customer23 -> customer 4 -> 0. Route 5: 0 -> customer 26 -> 0.A comparison of the results obtained with the DA, PSO, ALO, the SCA, and the HSCA in case study 2 indicated that the HSCA converged faster than the other algorithms. Figure11 displays the average best solutions obtained with the different algorithms after 200 iterations and 20 runs.Figure 11
Optimal average values were obtained with different algorithms after 20 runs in case study 2.Table5 presents the maximum values, minimum values, mean values, and deviations to the best solution obtained with the different algorithms used in this study. After 200 iterations, 20 runs, and 50 agents, the HSCA obtained a maximum distance of 849.61 units and a minimum distance of 701.16 units (its optimal result); thus, the optimal result of the HSCA was superior to those of the SCA, PSO, DA, and ALO. In addition, the optimal results of the SCA, PSO, ALO, and DA exhibited deviations of 14.7%, 16.9%, 34.7%, and 37.5%, respectively, from the optimal result of the HSCA; thus, the results of the SCA and PSO were stable and more accurate than those of ALO and DA. In summary, in the problem of cement transport by five vehicles to 30 delivery points, the results obtained by the HSCA were superior to those obtained by the SCA, PSO, ALO, and DA.Table 5
Best solutions obtained with different algorithms after 20 runs in case study 2.
Distribution of optimum solutionsMaxMinMean% dev best solution (%)HSCA783.81838.27748.79822.01746.90849.61701.16791.590.0834.89799.94849.61821.61780.01793.50701.16800.64771.84821.79806.97768.76844.78719.23777.37SCA928.49994.701029.051026.16885.601119.50804.05960.5814.7888.461080.391029.57923.55804.051119.501018.73946.19947.45945.02985.59959.19893.72853.84952.38DA1122.721036.271153.791095.201158.851308.59964.441132.0137.51122.291101.741079.451197.041250.211128.741246.841061.991308.59969.30964.441230.521125.791138.421148.06ALO1165.86951.441049.491173.53971.981221.77944.211049.6934.71066.321087.11947.101089.851027.151061.551021.481061.001045.88944.211022.591007.741098.781221.77978.85PSO946.91987.621053.831209.331042.761209.33819.48965.3516.91140.71953.78881.51820.44924.56983.83823.341068.281019.84978.391056.59819.48872.88837.93884.95Bold values represent better HSCA search results than other algorithms.


## 5. Conclusion

In this study, an HSCA was developed to solve two case studies of the classical VRP:(1)
In case study 1 [48], the developed HSCA provided stable results and the global optimal solution. Moreover, under the same numbers of search agents and iterations, the HSCA outperformed the DA, PSO, ALO, and SCA.(2)
In case study 2, in which the number of delivery points was 30, the HSCA again provided the global optimal solution and outperformed the aforementioned algorithms. The results of this study indicate that the developed HSCA can be used by cement distributors to optimize their vehicle routing plans to shorten travel distance and reduce travel cost.In conclusion, a routing planning model for cement transport trucks using HSCA is proposed based on its strong optimization. With case studies from 1 to 2, there will be a more overview of the VRP problem, the increasing complexity of VRP, and comparison of HSCA with the algorithms of previous studies. With the available data and related constraints of the VRP problem, it is found that the study has high practical application in supporting the routing planning for cement transportation vehicles. Further studies will further solve some problems such as delivery with a delivery time window, multiple warehouses, and time-limited delivery of hazardous materials by optimal methods.



---

*Source: 2728039-2023-02-17.xml*