View of Hybrid Swarm Intelligence Algorithm for Solving Vehicle Routing Problem with Time Windows

(1)

http://annalsofrscb.ro 967

Hybrid Swarm Intelligence Algorithm for Solving Vehicle Routing Problem with Time Windows

C.S. Sundar Ganesh¹,Dr.R. Sivakumar², Dr.N. Rajkumar³

1Assistant Professor, Department of EEE, Karpagam College of Engineering, Coimbatore, India.

2Professor, Department of Mechatronics Engineering, Akshaya College of Engineering, Coimbatore, India.

3Associate Professor, Department of Computer Science and Engineering, Akshaya College of Engineering, Coimbatore, India

ABSTRACT

Vehicle Routing Problem is formulated to tackle the issues related to distributing fuel to delivery stations, in certain cases, the client shall specify a period-window for the delivery and this comes under the class of vehicle routing problem with time windows. The vehicle routing issue considered in this paper is the dynamic VRPTW with Solomon’s data sets. The target is to find the minimum number of vehicles and distance travelled based on hybrid swarm intelligence algorithm. The proposed methodology hybridized the exploration and exploitation ability of the Multi Verse Optimization Algorithm (MVO) and the Ant Lion Optimizer (ALO) algorithm. The performance of the proposed hybrid optimization algorithm is analyzed with respect to the number of vehicles, distance travelled, and computational time for all the developed techniques and to validate the proposed models.

Assessed results registered utilizing the proposed hMVO-GHO technique is compared with the available techniques of literature for solving the Solomon VRPTW problem to illustrate the effectiveness of the proposed hMVO-GHO algorithm.

Keywords:

Vehicle Routing Problem, VRPTW, Solomon’s data set, hybrid MVO-GHO

1.Introduction

The optimal route selection for specific number of vehicles that are scheduled to serve the customers who are available in certain time windows is a serious problem of concern. The ultimate aim of the problem is to reduce the transportation cost by reducing the travelling distance with constrain of all the customers should be visited only once, such problem is termed as vehicle routing problem with time window. One of the important combinatorial optimization problems is the VRPTW and is a notable problem in transportation problems. VRPTW is more towards finding the optimal routes for the movement of identical vehicles with limited capacity and as well that gets departed from a central yard and function for different customers who are geographically located with pre-set time windows and of known demands. The vehicles return to the central yard (depot) at a specified time window and with an optimal route. In this process, each customer is visited only once by one vehicle with respect to the specified time window (Moradi 2019). The time window definition will be based on the initial and final time for beginning the service. VRPTW problems are widely employed in real-time scenarios of food delivery, postal services, waste material accumulation, college and school bus routing, Delivery of cash at bank and ATM points and several other maintenance operations. In large-scale VRPTW, a multi-objective optimization problem is one of the difficult problems wherein the exact techniques fail to find required solutions because of the run time parameter. The key objectives to be determined in this multi-objective combinatorial optimization problem is,

 Minimization of the number of vehicles in the routing path

 Minimization of total distance travelled employing a minimal number of vehicles.

(2)

Figure. 1A simple VRPTW

Figure 1 shows a simple VRPTW, the central yard of location is specified by ‘Z’ and the customers are represented from 1 to 12. The Figure shows four routes and their four solution routes are given by Z-6-1-4-Z, Z-3-11-9-5-Z, Z-7-10-12-Z, and Z-2-8-Z. Considering the complexity and applicability, exhaustive research work has been carried out employing scrupulous and approximate techniques which include heuristic and meta-heuristic algorithms to solve VRPTW. Approximate reasoning techniques are capable of determining optimal/ near- optimal solutions for these multi-objective VRPTW instances incurring minimal run time.

VRPTW being a constrained multi-objective optimization problem belong to the non- deterministic polynomial hard problem and henceforth are the stochastic population-based evolutionary optimization techniques and swarm intelligent approaches which can provide suitable solutions to these problems. Thus, in this proposed work, the focus is done on the development of hybrid multi-verse optimizer to attain near-optimal solution to this multi- objective VRPTW.

2. Existing Works of Literature

To solve the multi-depot green optimization algorithm (MDVRP) a modified anlt colony optimization algorithm is developed by Li et al. (2019). Stodola (2020) introduced probabilistic techniques with state- of art methods to solve MVDRP. On considering the flexible timing windows the vehicle routing problem is solved by a hybrid ant colony optimization algorithm, Zheng et al. (2019). An evolutionary optimization algorithm is developed to solve VRPTW based on combining the features of evolutionary scatter optimizer and PSO strategy, the association between the total vehicle traveled and the total distance is employed to identify the search direction. Mendoza et al. (2020) employed a hybrid grasshopper optimization algorithm to solve the VRP to identify the optimal routes. Alinaghian & Shokouhi (2018) discussed on routing problem with constrain where the split delivery cannot be accepted and only one vehicle should be employed to deliver the products. PSO is employed to optimize the capacitated vehicle routing

(3)

problem, the total waste collection efficiency, fuel efficiency, the total cost is employed as problem constraints(Hannan et al. 2018 ). Goel & Maini (2018) incorporated a firefly optimization strategy with Ant colony algorithm to solve the routing problem. Sedighizadeh &

Mazaheripour (2018). The PSO and ACO is combined to present a hybrid strategy that is employed to solve the routing problem. Dewi & Utama (2021) proposed a hybrid WOA optimizer on combining the characteristics of WOA and the Tabu search optimization algorithm.

Sitek et al. (2021) applied a hybrid approach to solve a CVRP with alternative pic-up delivery and time windows. Pan et al. (2021) studied a Duration Minimizing VRP with timing window by employing an adaptive large neighborhood search and Tabu algorithm. Euchi, and Sadok (2021) proposed a hybrid GA for VRP that utilizing a drones. An effective model for Vehicle routing problem was proposed by Moradi (2019) with timing window by a novel interrogative way, the performance has tested with benchmarks. A multi-adaptive model which concerns three adaptive strategies of vehicle directing issue with timing window, which uses (PSO algorithm) particle swarm optimization and the model has tested with two datasets that includes 56 and 300 instances, also compared with some other PSO versions by Marinakis et al. (2019). The model with CLP- Constraint Logic Programming and MP Mathematical Programming was introduced by Sitek & Wikarek (2019) for handling the delivery of postal, place of dispatch, and the timing window that is delivery time. Performance of the model has improved by introducing heuristic in the place of MP. The same issues with multi-commodity network are considered by Yang et al.

(2020) using Lagrangian relaxation formula. A Multi Objective model with SA - Simulate Annealing and IACO - Improved Ant Colony Optimization was introduced by Wang et al. (2020) to handle the service choice problem and timing window problem. The model has been tested using solomon’s and Cordeau's benchmarks. By considering the minimized travelling time and various vehicles from various depots Zhen et al (2020) propose a model with release date and timing window. This model uses hybrid PSO and Genetic Algorithm with the improved efficiency. Shen et al. (2020) introduced a model to reduce the total travelling distance by considering the timing window. The model has designed by hybridizing BSO (Brain Storm Optimization) and ACS (Ant Colony System). Along with the distance reduced cost and the time in health care been introduced by the model proposed by Euchi et al.(2020) using artificial intelligence techniques. The survey demonstrates the implementation of various swarm intelligence algorithms for solving of VRPTW. Nevertheless, specific problems cannot be solved in an efficient way employing a single one technique since each of them possesses its own merits and demerits. These observed limitations are the driving power behind the development of hybrid optimization techniques. When two or more techniques are combined, the merits of the individual algorithms are brought out and tend to provide more effective solutions for complex problems. Based on the utility of these algorithms and considering the no free lunch theorem, there is always a need for the development and hybridization of the optimization algorithms. The main reason behind the development of hybrid MVO-GHO technique includes,

 Parallel and redundant mechanism of these two algorithms is brought out.

 Designed to be fault- tolerant as they apply intensive computation

 Improves both the exploration and exploitation process

 Both these algorithms are gradient-free and moves towards attaining better solutions in the broader search space.

 MVO and GHO tend to be co-operative with each other

 Continuous adaptation of the algorithms



(4)

3 Problem Statements

The VRPTW is defined as follows: There exist ‘n’ customers who are about to be served and each of these customers need a product or services to be done. A convoy of indistinguishable vehicles is located in the central yard for rendering service to the customers. The volume and capacity of every vehicle should be greater than or equal to the sum of all the demands on the traversed route by the vehicles. Each customer has to be compulsorily served only once and only by one vehicle within the specified time window. The time window will be based on the pre-set time interval indicated by the initial and final arrival time. The vehicles have to reach the customer place before the final time of arrival. A vehicle may be permitted to reach before the initial arrival time, wherein in this case, it has to wait until the initial arrival time and then tends to provide service to the customer. Every customer authorizes an additional assistance time to the course for stacking or emptying the items or dependent on an opportunity to convey the items or perform different administrations. Each vehicle has to leave from the customer place and go back to the central yard (depot) within a particular time window. For the VRPTW problem, the solution will be the set of routes wherein the vehicle begins from the central yard, meets the customer services, and comes back to the initial start point concerning the capacity and indicate time window constraints. The number of routes on the network is equal to the size of the convoy and a single vehicle will be dedicated to a single route.

VRPTW, a multi-objective optimization problem comprises minimizing the number of vehicles to be used (convoy size) and the total distance that is covered by the vehicles for meeting the required demands of the customers. The mathematical foundation of VRPTW is as given below:

There exists a non-directed complete graph CG = (N, Y), with N = {n0, n1, n2,…., nn} and Y = {(ni, nj)| ni, nj  N, i  j} represents the node-set and the arc set. The given ‘n0’ indicates the central yard point and n_i ( i = 1,2,3,…,n) specifies the customers. The customers get serviced from the convoy of identical vehicles using the same volume capacity ‘V’. Each node is linked with a demand quantity vi and indicated via a time window [yi, ti], here the node n0 gets associated with v0=0 and [0, t0].

In respect to the time window constraint, a vehicle ‘p’ has to come to the customer ‘i’ location t_i^p before the final arrival time fi. Also, moving before the initial arrival time ai comes across waiting time wi. Every customer ‘i’ possess a serving time si, and it is the original time the delivery takes when the vehicle has arrived at the customer point. Every vehicle has to complete its route within the specified time window given by the central yard. Every arc present in the network indicates a connection that exists between two nodes along with a travelling distance TDij, which is the Euclidean distance among the nodes n_i and n_j, and a travelling time TT_ij, that is proportional to the travelling distance. Let ‘N’ specify the number of customers and the ‘S’ indicates the number of vehicles or the convoy size, then the optimization model of the VRPTW is defined as given below.

 













  

    N

1 i

N i j , 0 j

p ij P

1

p ij

2

1 2 1

x TD f

S f

with f , f ) x ( F min

(1)

Where, the functions ‘f₁’ and ‘f₂’ are the two objective functions to be minimized in this NP-Hard combinatorial optimization problem subject to the constraints,

(5)

 

 

    

N 1 j

N 1 i

p 0 i p

j

0 x 1,p 1,2,3,...,P

x (2)

 

 



^N    

i j , 0 j

N

P ,..., 3 , 2 , 1

i j , 0 j

k ji p

ij x 1,i 1,2,3,...,N ,p

x (3)

 

 

    

P 1 p

N j i , 0 i

p

ij 1, j 1,2,.3,...,N

x (4)

 

 

    

P 1 p

N i j , 0 j

p

ij 1,i 1,2,.3,...,N

x (5)

 

 

    

N 0 i

N i j , 0 j

p ij

i x V,p 1,2,.3,...,P

q (6)

   



^t ^w



^t ^,ⁱ

^

⁰^,¹^,²^,³^,...,^N

^

^,^p

^

¹^,²^,....,^S

^

y

S ,..., 2 , 1 p , j i , N ,..., 3 , 2 , 1 j , i , t t s w t

i p i p i i

p j ij i p i p i



















(7) In the above,





otherwise 0

v to v from travels ' p ' vehicle when

x_ij^p 1 ⁱ ^j (8)

Equation (1) specifies the two objective (fitness) functions f₁ and f₂ to be minimized indicating the number of vehicles employed and the total distance traversed respectively.

Equations (2) and (3) give the constraints that guarantee the vehicles initiate the delivery process from the central yard and provide service to customers individually one by one and then finally comes back to the central yard. The constraints provided in the Equations (4) and (5) represents that a customer is traversed only once and by only one vehicle. The constraint in equation (6) indicates the number of services or the products delivered by each vehicle that cannot exceeds its capacity V. Equation (7) indicates the computation of the travel time and the existence of time windows. Equation (8) represents that x_ij^pis equal to 1 when vehicle ‘p’ moves from node ni to node nj, and becomes equal to ‘0’ otherwise. The ultimate aim is to solve this NP-Hard combinatorial VRPTW by the proposed hybrid optimization algorithm in order to achieve the best optimal route with all the specified constraints given in equations (2) to (8) and to minimize the objective function given in equation (1).

4. Proposed Methodology

In this article a novel hybrid strategy is developed on combining the best characteristics of Multi- Verse Optimizer and the Grasshopper Optimization algorithm (hMVO-GHO). The Multi-verse optimizer is viewed as an effective strategy for its exploration mechanism and it suffers to handle the poor exploitation ability, so in order improve its exploitation ability the grasshopper optimization technique is hybridized with it. The combined version of MVO with Grasshopper Optimization (GHO) moves towards the optimal solutions for VRPTW by exploring and exploiting the search space. The modified hybrid MVO-GHO technique is applied for the VRP with small-time windows and large time windows for Solomon problem instances and the fitness function minimization is carried out.

(6)

4.1 Multiverse Optimization Algorithm – An Overview

The concept of cosmology is inspired to develop a Multi-verse optimizer algorithm, Mirjalili et al. (2016). The multi-verse concept is contradictory to the concept of the universe and this specifies the presence of other universes along with the universe we are living in. The theory that multiple universes get interacted with each other through the white holes, black holes, and wormholes and as well get collided among themselves is the foundation of multi-verse theory. In MVO modelling, for exploring the search space white holes and black holes are used and for exploiting the search space wormholes are being employed. MVO optimization procedure is initiated by creating a population of distinct solutions and attempts to determine solutions based on the defined number of iterations. The update mechanism is done in MVO based on one of the theories of the potential existence of the multiple universes. Hence, a single universe represents an optimization solution and each object in the universe corresponds to the decision variable about the problem. The elements of the Universe is presented in Figure 2 and the operation of MVO is based on the following factors,

 Higher probability of white holes occurs with a higher inflation rate

 Lower probability of black hole specifies higher inflation rate

 The transfer of objects in the universe takes place from a white hole into a black hole

 Considering all universes, the objects tend to move towards the best universe

(a)White hole (b) Worm hole (c) Black hole

Figure 2 Elements of Multiverse optimizer

Black holes with lower expansion rates get the items from the white holes with a higher swelling rate. Through the iterative process, the mean inflation rate is improved and the universes gets arranged to their inflation rates during each iteration and the white hole gets assigned to the universe using roulette wheel selection. The matrix that defines the population is given by,



















d n n

d d

pop

x x

U

. .

. . . .

. .

2 2

1 1

(9)

In Equation (9), the variable ‘Upop’ represents the universes called population, ‘n’ is the number of universes and the number of dimensions is indicated by ‘d’. The decision variable is generated using,

 



^low^_^bd ^rand⁽⁾ ^upr^_^bd ^low^_^bd ¹

x_i^j  _j  _j  _j  (10)

with i=1,2,..n and j=1,2,…d, the lower bound and upper bound specifies the bound limit of the decision variable and rand( ) generates a random number from 0 to 1. During the iterative

(7)

process, the decision variable that possesses a black hole changes its value employing two choices as given by,

 









 

i j

i

i j

j np

i x rand1( ) NormUV

UV Norm )

( 1 rand

x x (11)

Where, ‘x_i^j’ indicates the j-th decision variable of the i-th universe, ‘UVi’ specifies the i- th universe, ‘Norm(UVi)’ represents the normalized inflation rate in respect of the i-th universe,

‘rand1( )’ is a randomly generated number between [0,1] and ‘x_np^j ’ represents the j-th variable of m-th universe, that is selected here using Roulette Wheel. The diversity of the solutions has to be increased and this is carried out with the wormhole and the algorithm progresses assuming that wormholes exist in the solution randomly. This is given by,

 









 





























wh j

i

wh j

j j

j _ fit

j j

_ fit j

i

P 3 r x

P 3 5 r . 0 2 r bd _ low 1 r bd _ low bd _ upr x

5 . 0 2 r bd _ low 1 r bd _ low bd _ upr x

x 



(12) In Equation (12), ‘xfit_j’represents j-th fittest universe variable that has been generated as of then, the minimum bound limit and maximum bound limit of j-th parameter is given by low_bdj and upr_bdj respectively with x_i^jindicating the j-th parameter of the i-th universe, r1, r2 and r3 are random numbers from 0 to 1, ‘’ is the rate of distance travelled and ‘Pwh’ indicates the probability of the presence of wormholes. The adaptive variation of the parameters ‘’ and ‘Pwh’ are given by,

ea / 1

) iteration (max_

) iteration _

current 1(

 (13)



 



 





 max_iteration

C iteration C

_ current C

P_wh _min ^max ^min (14)

Where, ‘ea’ represents the exploitation accuracy during the iterative process, ‘Cmin’ and ‘Cmax’

indicate the predefined constant values which help for the exploitation phase during iterations.

Higher the value of ‘ea’, more accurate and faster is the exploitation mechanism. The procedural steps adopted during the algorithmic process of MVO are presented below:

Step 1: Initialize the necessary parameters

Step 2: Generate the solution set of the individuals

Step 3: Compute the fitness function for all the generated solution sets

Step 4: Based on the computed fitness function, arrange the solution sets in the order of best to worst.

Step 5: Update each solution based on the white/black holes and wormholes For considered ‘j’-th decision variable of solution (xi)

Generate random value rand1() and compare it with the objective function value xi and exchange it with ‘j’

Case 1 – The value gets replaced with better solutions Case 2 – The value remains the same

Generate random value ‘r2’ to compare with the probability of wormhole existence ‘P_wh’ and exchange it with ‘i',

Case 1 – The value gets replaced from the best solution after adding ‘’ value.

Case 2 – The value gets replaced from the best solution after Subtracting ‘’ value.

(8)

Perform steps 3 to 5 repeatedly until the required end fitness value is achieved.

Step 6: Return the best solution evaluated during the iterative process.

4.2 Grasshopper Optimization Algorithm – An Overview

The Grasshopper Optimizer is a swarm intelligence algorithm developed based on inspiring the social behaviour of grasshoppers, they are capable of migrating over large distances and during their traversal path they consume vegetation and once they move to adulthood, they tend to swarm in the air. The key feature of the swarm is a slow movement in the larval stage and small steps of grasshoppers but in contradictory the adulthood feature is abrupt movements and large steps. One of the significant qualities of amassing of grasshoppers is the mode wherein they reach and look for the food. This is done by grasshoppers using the exploration and exploitation process; at the exploration phase the search agents are motivated to move abruptly and at the exploitation phase they move locally. The exploration and exploitation mechanism and that of the identifying and seeking the target food source is carried out by grasshopper naturally. The life cycle of grasshopper is presented in Figure 3.

Figure 3 Grasshopper life cycle

The swarming behaviour of grasshopper is represented by the mathematical equation, ]

1 , 0 [ , ,

,

3 2 1 3

2

1   







r r r where A

r G r S r X

included behaviour

random with

A G S X

i i i i

i i i

i (15)

In Equation (15), ‘Xi’ denotes the i-th grasshopper position, ‘Si’ the social interaction, ‘Gi’ the gravity force exerted on the grasshopper, and ‘Ai’ denotes the wind advection. The entities social interaction, gravity force, and wind advection are given by,

 

w u i

g g i

al p p ij

N

i j

1

j ij

i

eˆ d A

eˆ C G

e fe ) p ( s , as function s

with dˆ d s S













 ^ ^





(16)

Where ‘dij’– the distance between the ‘i’-th and ‘j’-th grasshopper, ‘dij=|xj-xi|’ ,‘s’ – the capability of societal group forces, ‘f’ is the intensity of attraction, ‘al’ – attractive length scale, ‘C_g’–

gravitational constant, ‘eˆ_g’- Unity vector towards the center of the earth. ‘du’ – drift constant,‘

(9)

http://annalsofrscb.ro 975 ew

ˆ ’- Unity vector towards the wind direction, ‘N’ – Number of grasshoppers. Equation (16) in equation (15) becomes,

 

^d ^dˆ ^r ^C ^eˆ ^r ^d ^eˆ ^where ^r ^,^r ^,^r ^[⁰^,¹^]

s r

X ^N _ij ₂ _g _g ₃ _u _w ₁ ₂ ₃

i j

1

j ij

1

i     

 (17)

In general, grasshoppers tend to reach the comfort zone and the swarm does not converge to a specified point. Considering this the equation (17) is modified as,

 

target

ij i d j

i d j N

i j

1

i j Oˆ

d x x x

x 2 s

bd _ lw bd _ cup c

X 















 

 

 

 (18)

Where, ‘up_bd’ represents the upper bound in the specified d-th dimension, ‘lw_bd’ is the lower bound in the specified d-th dimension, ‘c’ is the constant that diminish comfort, repulsive and attractive force, ‘Oˆ_t_arg_et’ is the target along the direction of wind.

To adjust the exploration and exploitation course, the diminishing coefficient ‘c’ must be reduced relatively to the quantity of iteration. This coefficient is given by,

iterations max_

c min_

c iteration max_

_ current c

max_

c    (19)

Where, ‘max_c’ is the maximum value and ‘min_c’ specifies the minimum value. The value of

‘max_c’ is chosen as 1 and that of ‘min_c’ is chosen as 10^-5.

4.3 Proposed hybrid MVO-GHO optimization algorithm (hMVO-GHO)

A single optimization algorithm suffers to handle specific problem statement such as local stagnation issue, delayed convergence, pre-mature convergence and so on. These observed limitations are the driving power behind the development of hybrid optimization techniques.

When two or more techniques are combined, the merits of the individual algorithms are brought out and tend to provide more effective solutions for complex problems. To attain better exploration and exploitation ability the exploitation mechanism of GHO is combined with the exploration mechanism of MVO, the hybrid MVO-GHO algorithm is developed. Initially the model is set to find the optimal solutions by MVO strategy, the fittest population generated from MVO is employed as search population for GHO, the pseudo code is presented in Algorithm 1.

The modeled hybrid multi-verse optimizer – grasshopper optimization technique is enforced for Solomon benchmark data sets for VRPTW for demonstrating the effectiveness of the proposed algorithm. During the iterative process, the fitness functions, quantity of vehicles and absolute distance voyaged are assessed and the algorithm is roused to limit these fitness values.

Employing a modified hybrid MVO-GHO technique, for selection of the decision variable from the universe Roulette wheel selection was employed and the exploration mechanism was carried out. At the time of iteration, the object updates are carried out with the white/black holes and wormholes. The classic grasshopper optimization algorithm gets invoked on attaining the first global best from the multi-verse optimization technique and it goes on with its swarming behaviour to perform position updates to attain a more effective solution. The hybrid operation of multi-verse optimizer and grasshopper optimization has resulted in achieving a balance between the exploration and exploitation mechanism due to both of its swarming nature and conditional movements inside the search space in reaching solutions. The hybrid mechanism makes the algorithm move towards solution set without getting stuck with local and global optima

(10)

problems, premature convergence, and attains faster convergence with better minimized fittest individuals in respect of the number of vehicles and total distance travelled.

Algorithm -1

//Modified hybrid MVO-GHO algorithm//

Initialize MVO-GHO parameters:

low_bd, upr_bd, number of universes, number of dimensions,

convergence criterion, ea, Cmax, Cmin, max_c, min_c and other random constants Randomly generate the swarm of population

while (convergence_criterion) not met do for all solution_set generated do

Compute the fitness function

Sort the solutions from the best one to worst one based on fitness value Perform normalization of solution set - Norm(UVi)

Update the best solution set (xbest_j)

for each solutions ‘i’ except the best solution set perform Evaluate P_wh and  using equations (5) and (6) Index_blackhole = i

for each object xj do

rand1=random(0,1) if (rand1<Norm(UV_i)) Then

Index_whitehole=RouletteWheel_selection

S(Index_blackhole, j)=Sort(Index_whitehole, j) end if

r3=random(0,1) if (r3<Pwh) then

r2=random(0,1) r1=random(0,1) if (r2<0.5) then

Update the position of solution_universe with equation (4) – case 1

else

Update the position of solution_universe with equation (4) – case 2

end if end if end for

end for Invoke GHO

T=globalbest_solution (MVO) Update c

for each search agent

Normalize(Grasshoppers_Distance)

Update grasshopper_position using equation (18) for current search agent if (boundary_exceeded)

best_agent=current_agent else

(11)

update c and proceed further end if

end for

Update T (better_solution) Iteration=iteration+1 end for

end while

Return the best optimal solution T

The developed hybrid MVO-GHO is applied for the standard benchmark functions and its suitability in solving the NP-Hard combinatorial optimization problem is analyzed. The standard benchmark test functions for which the modified hybrid MVO-GHO applied are the same as given in Table 1.

Table 1 Bench mark functions

Function Function definition Dimension Range

De Jong first

function ^^d 1 i

2

xi

) x (

f 50 [-5.12,5.12]

Rosen brock

test function ^d^_^¹

 









 

 

1 i

2 2 i

! i 2

i 100x x

x 1 )

x (

f 50 [-

2.084,2.084]

Schwefel

function ^

   

 

 ^d

1

i xisin xi

) x (

f 50 [-500, 500]

Ackley function

20 e

) x 2 d cos(

exp 1 d x

2 1 . 0 exp 20 ) x (

f ^d

1

i i

d 1 i

2 i











 







  



  50 [-32.768,

32.768]

Rastrigin

function ^

 

 



 ^d

1

i i

2

i 10cos(2 x )

x d 10 ) x (

f  50 [-5.12,5.12]

The required parameters for the run of the hMVO-GHO algorithm are initialized and the iterative optimization process is carried out. The proposed modified hybrid MVO-GHO is applied for the considered five test functions with their dimensions to be 50. The comparison of the developed algorithms was done with the existing PSO, MVO and chaotic MVO (CMVO). Table 2 provides the results attained in applying the proposed optimization technique on the test functions. For the considered five test functions with a dimension of 50, it has to be noted that using proposed hMVO-GHO, the minimum, maximum and average values are minimal than that of the PSO, MVO and CMVO (Kennedy 1955, Mirjalili et al. 2016, Ewees et al. 2019). The proposed hybrid algorithm outperforms the conventional state of art methods such as PSO and MVO which confirms the applicability of the proposed hybrid MVO-GHO more suitable for the VRPTW problem.

Table 2Test Function Results of Existing and Proposed Techniques Functions Dimension Considered

Algorithm

Convergence rate

Minimum value

Maximum value

Average value De Jong

first

50 PSO 0.78 126 172 155

MVO 0.85 96 120 102

(12)

function Chaotic

MVO

1 114 136 122

hMVO- GHO

1 60 82 71

Rosen brock function

50 PSO 1 167 192 175

MVO 1 112 146 128

Chaotic MVO

0.94 132 187 159

hMVO- GHO

1 48 70 59

Schwefel test function

50 PSO 0.72 146 165 151

MVO 0.89 124 147 133

Chaotic MVO

1 138 156 143

hMVO- GHO

1 36 57 45

Ackley function

50 PSO 0.92 189 202 195

MVO 0.81 153 180 167

Chaotic MVO

0.77 176 194 182

hMVO- GHO

1 40 61 49

Rastrigin function

50 PSO 0.85 96 120 108

MVO 0.93 73 90 81

Chaotic MVO

0.77 55 70 64

hMVO- GHO

1 38 54 46

4.4 Experimental Analysis of the proposed Vehicle

The proposed techniques were implemented in MATLAB R2018b version and run on an Intel Core i5-7200U CPU @2.50GHz, 2712 MHz, 2 Core(s) and 4 Logical Processor(s) and 8 GB RAM. The parameter settings are given in Table 3 and these parameters were set with off-line tuning methods. To evaluate the model experimentally the Solomon’s benchmark dataset that comprising of 56 sets is utilized (Solomon et al.1986, Solomon et al.1987, Solomon& Desrosiers 1988). The entire dataset is segregated into six classes such as R1, R2, S1, S2, SR1 and SR2 on considering the issues of the routing problem such as armada measure, vehicle limit, voyaging time of vehicles, spatial and worldly circulation of clients. The issues are assemblage in a class, for instance the issues in R class the customers are grouped time arrangement and S class possess sets on the basis of their location. The SR class consist of the attributes from both S class and R class. The class R1, S1 and SR1 possess the issues like the tight time arrangement for the terminal, consequently, a vehicle can serve only two clients. The other classes possess the set that are related to the case of more clients can be served by a vehicle with vast time deal. S2 and R2 allows customers to enjoy long booking skyline and large number of customers can be allotted for a single vehicle, so here the customer direction related issues are arranged in this class. On

(13)

accounting to the width of time arrangements the issues are flagged as 25, 50, 75 and 100 agreement.

Table 3 Parameter setting of the proposed hybrid algorithm Algorithmic parameters Parametric values

Population size 150

Trial runs 30

P_wh (minimum) 0.2

Pwh (maximum) 1.0

Exploitation accuracy (ea) 6.0

T₀ 36

Convergence criterion 10^-6

Maximum iterations 200

Selection Boltzmann selection

To validate the performance of the proposed hybrid MVO-GHO technique, the developed algorithms are applied over the 56 Solomon problem instances with 100 customers each. The developed hybrid optimization technique is simulated for the considered problem instances and the fitness functions – the number of vehicles and total distance travelled are minimized for the VRPTW. The algorithm hMVO-GHO is run for 30 trial runs and the best fitness values evaluated based on the object update in the universes are the required optimal solution set. The optimization iterative process is run until the convergence criterion is met and the evaluated solution sets are provided in Table 3 and Table 4 for the considered Solomon problem instances with small-time windows and large time windows respectively. The fitness function is given in Equation (1) is attained includes the number of vehicles (NV) and the Total Distance travelled (TD) for each of the vehicle routes taken. The evaluated number of vehicles and total distance travelled pertaining to the best optimal solution of the trial runs using hMVO-GHO is provided in Table 4 and Table 5 for the VRPTWby applyingSolomon data sets

Table 4 Results of hMVO-GHO Algorithm for VRPTW (Small Time Windows C1, R1, and RC1)

Problem instances Proposed hybrid MVO-GHO technique

Number of vehicles (NV) Total distance travelled (TD)

C101 10 829.81

C102 10 829.11

C103 10 828.56

C104 10 829.07

C105 10 829.09

C106 10 828.16

C107 10 829.16

C108 10 829.40

R101 18 1637.25

R102 16 1452.27

R103 12 1210.76

(14)

R104 9 962.33

R105 12 1350.24

R106 11 1234.92

R107 9 1055.01

R108 9 949.00

RC101 13 1637.02

RC102 12 1457.79

RC103 10 1259.03

RC104 9 1134.12

RC105 12 1515.77

RC106 10 1377.52

RC107 10 1208.46

RC108 9 1117.48

Table 5 Results of hMVO-GHO algorithm for VRPTW (Large time windows C2, R2, RC2) Problem

instances

Proposed hybrid MVO-GHO technique

Number of vehicles (NV) Total distance travelled (TD)

C201 3 592.24

C202 3 592.32

C203 3 592.03

C204 3 590.41

C205 3 588.11

C206 3 588.19

C207 3 586.35

C208 3 588.42

R201 3 1147.92

R202 3 1022.47

R203 3 873.60

R204 3 728.98

R205 4 952.27

R206 4 881.96

R207 3 797.31

R208 2 702.24

RC201 3 1253.76

RC202 3 1060.88

RC203 3 921.18

RC204 3 784.54

RC205 3 1148.39

RC206 3 1046.21

RC207 3 760.33

RC208 3 771.41

The developed modified optimization algorithm hMVO-GHO has attained better non-dominated solutions. The percentage variation of the fitness function values, number of vehicles and total distance travelled for the considered problem instances and that with respect to the best

(15)

techniques from Moradi et al. (2019) are evaluated and shown in Table 6. It is noted from table that the developed hybrid MVO-GHO techniques have attained better values and more suitable for the problem instances C1, C2, R1, RC1 and RC2. Only for the problem instance R2, it has resulted in the worst solutions. Henceforth, most of the solutions computed using the proposed optimization technique for Solomon’s problem instances attained promising solutions compared with the earlier employed best methods from literature. The performance of the proposed model is compared with existing works of literature such a Frog leaping technique Luo et al. (2015), Tabu search Zhang et al. (2017), Scatter search Zhang et al. (2018), Learnable evolution Moradi (2019) is presented in Table 7-Table 9.

Table 6 Mean Values of the Evaluated Fitness for Problem Instances with Proposed Techniques Problem instances Modified hybrid MVO-GHO approach

Percentage variation of number of vehicles

C1 +0.0034 +0.0098

C2 +0.0000 +0.0001

R1 +0.0136 +0.0019

R2 +5.6492 +3.2615

RC1 -1.2217 +0.0916

RC2 -0.9428 +0.0642

Table 7 Comparison of number of vehicles with existing works of literature (Small Time Windows C1, R1, RC1)

Problem instances

Luo et al (2015)

Zhang et al (2017)

Zhang et al (2018)

Moradi (2019)

Proposed Algorithm

NV NV NV NV NV

C101 10 10 10 10 10

C102 10 10 10 10 10

C103 10 10 10 10 10

C104 10 10 10 10 10

C105 10 10 10 10 10

C106 10 10 10 10 10

C107 10 10 10 10 10

C108 10 10 10 10 10

R101 20 20 19 10 18

R102 18 18 17 19 16

R103 15 14 13 17 12

R104 11 11 9 13 9

R105 15 15 14 9 12

R106 13 13 12 14 11

R107 12 11 10 12 9

R108 11 10 9 10 9

RC101 16 16 14 10 13

RC102 14 14 12 14 12

(16)

RC103 12 12 11 12 10

RC104 11 10 10 11 9

RC105 16 15 13 10 12

RC106 14 13 11 13 10

RC107 12 12 11 11 10

RC108 11 11 10 11 9

Table 8 Comparison of distance travelled with existing works of literature (Small Time Windows C1, R1, RC1)

Luo et al (2015)

Zhang et al (2017)

Zhang et al (2018)

Moradi

(2019) Proposed Algorithm

TD TD TD TD TD

C101 829.04 829.04 829.04 829.04 828.91

C102 829.04 829.04 829.04 829.04 828.21

C103 828.16 828.17 828.16 828.17 827.66

C104 828.88 828.88 828.88 828.88 828.17

C105 829.04 829.04 829.04 829.04 828.19

C106 829.04 829.04 829.04 829.04 827.16

C107 829.04 829.04 829.04 829.04 828.26

C108 829.04 829.04 829.04 829.04 828.5

R101 1650.90 1643.28 1642.98 1650.90 1636.35

R102 1486.22 1460.36 1473.02 1486.96 1451.37

R103 1292.77 1217.49 1213.83 1292.78 1209.86

R104 1007.40 987.71 976.71 1007.41 961.43

R105 1377.21 1364.01 1360.86 1377.21 1349.34

R106 1252.13 1248.00 1239.47 1252.13 1234.02

R107 1104.76 1087.60 1073.44 1104.76 1054.11

R108 960.98 961.95 950.69 960.98 948.10

RC101 1697.05 1646.27 1639.85 1697.05 1636.12

RC102 1554.85 1481.71 1461.43 1554.85 1456.89

RC103 1261.77 1280.86 1277.65 1261.77 1258.13

RC104 1135.58 1162.13 1138.23 1135.58 1133.22

RC105 1629.54 1545.40 1519.56 1629.54 1514.87

RC106 1424.83 1401.27 1378.72 1424.83 1376.62

RC107 1230.58 1235.38 1212.93 1230.58 1207.56

RC108 1139.92 1136.45 1118.67 1139.92 1116.58

Table 9 Comparison of Total Number of Vehicles of Proposed Techniques with existing works of literature (Small Time Windows C1, R1, RC1)

Luo et al (2015)

Zhang et al (2017)

Zhang et al (2018)

Moradi (2019)

Proposed Technique

TD TD TD TD TD

C201 3 3 3 3 3

C202 3 3 3 3 3

(17)

C203 3 3 3 3 3

C204 3 3 3 3 3

C205 3 3 3 3 3

C206 3 3 3 3 3

C207 3 3 3 3 3

C208 3 3 3 3 3

R201 4 6 8 4 3

R202 3 5 6 3 2

R203 3 5 6 3 2

R204 2 4 4 5 2

R205 3 5 5 7 3

R206 3 4 5 5 3

R207 2 4 4 5 2

R208 2 5 3 4 2

RC201 4 7 9 4 3

RC202 3 6 8 3 3

RC203 3 5 5 3 3

RC204 3 4 4 5 3

RC205 4 7 7 7 3

RC206 3 5 6 5 3

RC207 3 5 6 5 3

RC208 3 5 4 4 3

Table 10 Comparative Analysis of Total Distance Travelled of Proposed Techniques with Existing Techniques (Large Time Windows C2, R2, RC2)

Luo et al (2015)

Zhang et al (2017)

Zhang et al (2018)

Moradi

(2019) Proposed Technique

TD TD TD TD TD

C201 591.66 591.66 591.66 591.66 591.34

C202 591.66 591.66 591.66 591.66 591.42

C203 591.27 591.27 591.27 591.27 591.13

C204 590.7 594.99 590.7 590.7 589.51

C205 588.98 588.98 588.98 588.98 587.21

C206 588.59 588.59 588.59 588.59 587.29

C207 588.39 588.39 588.39 588.39 585.45

C208 588.42 588.42 588.42 588.42 587.52

R201 1252.47 1174.79 1152.73 1252.47 1147.02

R202 1191.8 1046.2 1036.4 1191.8 1021.57

R203 939.6 884.12 875.31 939.6 872.7

R204 825.62 750.5 737.53 731.4 728.08

R205 994.52 960.85 954.26 965.2 951.37

R206 906.24 901.07 884.35 887.7 881.06

R207 890.71 809.82 801.25 807.1 796.41

R208 726.92 723.24 706.96 703.5 701.34

(18)

RC201 1407.04 1271.88 1265.66 1407.04 1252.86

RC202 1365.74 1117.31 1096.63 1365.75 1059.98

RC203 1049.72 941.91 926.92 1049.72 920.28

RC204 798.56 801.97 786.48 788.4 783.64

RC205 1297.75 1165.91 1157.65 1297.75 1147.49

RC206 1146.42 1072.95 1057.93 1146.42 1045.31

RC207 1061.24 977.21 966.47 763.4 759.33

RC208 828.24 792.43 779.41 779.7 770.51

This section presents a detailed comparative analysis of the proposed techniques for VRPTW with that of the state-of-the-art approaches existing in the various literature works (Luo et al.

2015, Zhang et al. 2017, Zhang et al. 2018, Moradi et al.2019). In respect of VRP with small- time windows 29 problem instances were taken and with large time windows 27 problem instances were considered on a total of 56 instances were employed. Tables 7 and 8 shows the comparison with respect to the evaluated fitness number of vehicles and total distance travelled for small-time windows using the hybrid MVO-GHO technique. Both these fitness values have to be minimized during the iterative process and for small-time windows, C, R, and RC instances.

The table shows that the modified hybrid MVO-GHO for instances attained a minimum number of vehicles than the methods considered for comparison. For C106 instance, hMVO-GHO has attained 827.16 to be the distance travelled with the same 10 number of vehicles being used.

Significant improvement can be noted in the R108 instance using hMVO-GHO with possible minimized distance. Comparing RC instances, possibly more near optimal solution sets are attained and hence the proposed hybrid technique achieves better solutions for R instances than that of the C and RC Solomon problem instances which are noted from the obtained results. The VRP with large time windows is well executed for Solomon 56 problem instances and its comparative analysis with state-of-the-art techniques is provided in Tables 9 and 10. In connection with large time windows, 27 problem instances with 100 vehicles are simulated and the number of vehicles and total distance travelled are minimized during the iterative process.

The hybrid MVO-GHO technique is applied to the considered problem instances to attain minimized fitness values. Compared to R and C instances, the developed techniques have achieved better results for RC instances. For the instance RC207, it has attained a minimized distance of 759.33 with 3 vehicles better than the other methods for comparison. For the C problem instance, very near-optimal solutions have been attained using the proposed hybrid technique in comparison with the other existing techniques (Leo et al. 2015, Zhang et al. 2017, Zhang et al. 2018, Moradi et al.2019). Comparing all the problem instances, the developed hMVO-GHO method achieves better arrangements with a base number of vehicles and travelling least distance to arrive at the client end and execute the work in regard of VRPTW.

Table 11 Comparison of computational time of proposed technique with existing works of literature

Problem Instances

Zhang et al (2017)

Moradi (2019)

Proposed Technique

Zhang et al (2017)

Moradi (2019)

Proposed Technique C101 1070.42 113.05 106.26 C201 1337.71 174.75 166.29

C102 280.49 114.38 107.87 C202 348.48 200.38 193.47

C103 116.66 117.04 115.90 C203 132.09 184.07 166.02