# A New Plant Intelligent Behaviour Optimisation Algorithm for Solving Vehicle Routing Problem

Authors: Godfrey Chagwiza
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

A new plant intelligent behaviour optimisation algorithm is developed. The algorithm is motivated by intelligent behaviour of plants and is implemented to solve benchmark vehicle routing problems of all sizes, and results were compared to those in literature. The results show that the new algorithm outperforms most of algorithms it was compared to for very large and large vehicle routing problem instances. This is attributed to the ability of the plant to use previously stored memory to respond to new problems. Future research may focus on improving input parameters so as to achieve better results.


---

## Body

## 1. Introduction

A lot of research has been done and is ongoing on development of optimisation algorithms that are motivated by natural processes. In this research, an attempt to develop a new plant intelligence behaviour optimisation (PIBO) algorithm motivated by intelligent behaviour of plants to survive and avoid competition is presented. Natural processes such as how plants fight competition and change morphology in response to environmental changes make it worthwhile to develop an algorithm inspired by plant intelligence. Plant intelligence starts with cell molecular network. Molecular connections result in a living organism. It is believed that metabolic steps act like Boolean computer logic gates such asOr, AND, and NOR [1] and act like chemical neurones [2, 3].Pattern recognition is achieved through assembling chemical neutron together [4]. Computational elements in plant intelligence are taken to be proteins [5]. Plants can forage for their food through changing their behaviour. This is achieved by changing physiology, phenotype, and architecture [6]. Plants make decisions as they grow, thereby placing roots, shoots, and leaves at optimal points or positions depending on availability or positions of perceived resources [7, 8].Overgrown branches can trigger decision to seal the vascular connection system and redirect resources to the rest of the plant [9]. The plants have an ability to sense volume [10]. Plants can avoid competition and can respond to local opportunities that will be of use in future [11]. Roots plays a pivotal role in plant intelligence. The paper is highly motivated by adaptability of plants to severe conditions, ability to avoid competition, and ability to survive under dynamic conditions. Using this intelligence of plants to develop an optimisation algorithm can result in a better optimisation algorithm capable of adapting to conditions given. An optimisation algorithm that is flexible and adapting to different conditions is necessary with current advancement in technology. The proposed algorithm is different from other nature inspired algorithms in that it can redirect time resources to solutions that are feasible only. The remainder of the paper is arranged as follows. In Section 2, formulation of the new PIBO algorithm is presented. Computational experiments, results, and discussions are presented in Section 3, and conclusions are drawn in Section 4.


## 2. PIBO Algorithm Development

In this section an attempt to develop the new optimisation algorithm is presented. Basic steps of plant intelligence are used as steps of the new algorithm. Parameters and Variables section presents definitions of parameters and variables used.


### 2.1. Environmental Information

Environmental information comes in various forms that require different actions. A population,N, of environmental information, xi, is generated by various plant parts such as roots, leaves, and trunk. A population xi∈N is generated first before anything else. Line (3) of Algorithm 1 defines environmental information.Algorithm 1
(1) START
(2) Objective function O(xi)=(x1,x2,…,xi)T
(3) Generate initial population of N environmental information xi
(4) Define perception, Fi for xi
(5) while  N<MaxGen  do
(6) Get a plant randomly
(7) Initiate signal transduction creating response ri
(8) Evaluate ri appropriateness by finding P(ri)
(9) Set up the initial adaptive network, G0
(10) Get α,β,τ and η
(11) if  αxi>0∧βxi>0∧τxi>0∧ηxi>0∨ηxi≤0  then
(12) Find max⁡{G(xi)}
(13) Choose (α,τ,β)>0 that produces the set max{P(G)}
(14) else if  α=β=τ≤0  then
(15) Set P(G)=0
(16) Wait until α>0∧β>0∧τ>0∧η>0∨η≤0
(17) end if
(18) Construct the set V={V1,1k,…,Vjik} of the response instances
(19) Generate the response tissue integration decision M(xi,t)
(20) if  M(xi,t+1)>M(xi,t)  then
(21) Choose the response V(xi,t+1)
(22) else if  M(xi,t+1)<M(xi,t)  then
(23) Choose response V(xi,t)
(24) else if  V(xi,t)∉V  then
(25) Set M(xi,t)=0 and stop, abandon the response decision and make another decision
(26) end if
(27) Evaluate fitness, Ai
(28) if  Ai>Ai∗  then
(29) Produce intelligent phenotype, Ci
(30) else if  Ai<Ai∗  then
(31) Set Ci=C0 and re-analyse Fi
(32) end if
(33) Determine compactness, Z(xi), of Ci
(34) if  Z(xi)≥Z(xi∗)  then
(35) Set Z(xi)=Z∗(xi)
(36) else if  Z(xi)≤Z(xi∗)  then
(37) Set Z(xi∗)=Z∗(xi)
(38) end if
(39) Find best current solution, O(xi∗)
(40) end while
(41) Return the results
(42) STOP


### 2.2. Plant Perception

Plants perception, sometimes referred to as biocommunication, is a way how plants communicate. Plants have the ability to sense and respond to the environment. This can lead to adjustment in morphology, physiology, and phenotype. Reactions to chemicals, light, gravity, parasites, and many other factors have been noted in plants. Perception frequency,Fi, for environmental information, xi, is defined. This will be used in future encounters with the same information. Equation (1) represents perception frequency where γ is drawn from a uniform distribution, U[0,1]. In Algorithm 1, line (4) presents plant perception:(1)Fi=hxi,min+γhxi,max-hxi,min.


### 2.3. Signal Transduction

Signal transduction occurs when the extracellular molecule activates a receptor that in turn triggers biochemical events resulting in a response. Signal transduction (line(7) of Algorithm 1), ri, is affected by stimulus location, type, duration, and intensity. Equation (2) shows the signal transduction level of the environmental information by the plant:(2)ri=1stype+sloc+sdur+sintxi×100%.


### 2.4. Assessment

The plant will assess the information transmitted in order to make an informed decision. This is an important step of the algorithm because it is the one that affects the action to be taken. Assessment ofxi is carried out to determine the effect of the environmental information, and (3) presents assessment function. It is shown that 0≤P(ri)≤1 from (3). The smaller the value of P(ri) is, the greater the chance that the adaptive representational network, G, is formulated is. Research suggests that memory in plants cannot be constructed without first learning. Plants learn complex things such as stress, condition of drought, cold, heat, flooding, and many more through reinforcement [31–34], and this is the reason for using previous environmental information when carrying out current assessment.(3)Pri=xi∗xi,xi∗≤xi,xi≠0.


### 2.5. Adaptive Representational Network

Adjustment in the morphology or physiology and phenotype may take place depending on the type of environmental information at hand. The networkG=(B,E) will be formulated where B is the set of components (morphology, phenotype, and physiology) and E are edges. This network presents what is to be done. Use of Boolean operators AND, OR, and NOR is carried out at this stage of the algorithm. To ensure that the adaptive representational network formulated is useful, set α, β, and τ to be nonnegative. The tolerance optimiser does not matter if it is negative.


### 2.6. Tissue Integration

The state of all nodes in the adaptive representational network can be modelled as follows:(4)Y¯ik+1=Yix1k,x2k,…,xIk,i∈I.The variable Y¯i[·] is updated according to (5)Y¯ik+1Tik=Yix1kV1ik,x2kV2ik,…,xIkVJik,k∈N,j=1,2,…,J,where (6) and (7) represent Tik and Vjik, respectively.(6)Tik=minjl⁡Tjl≥t,for  somek(7)Vjik=maxl⁡Tjl:Tik>Tjl=V.The response tissue integration decision is then presented by (8)Mxi,t=max⁡Y¯i1,…,Y¯ik.


### 2.7. Fitness and Intelligent Phenotype Production

In this step, the algorithm will evaluate the fitness of tissue integration decision. Information gathered from learning previous environmental information reinforces the evaluation criteria. This means that the previous environmental information intensity,xi∗, leading to the optimal tissue integration decision, Ai∗, should be smaller than or equal to the current environmental information intensity, xi, so that the current fitness, Ai, can lead to the intelligent phenotype production, Ci.


### 2.8. Compactness and the Solution

Compactness of the intelligent phenotype produced is important for the plant to achieve the goal. The algorithm ranks the current solution and the best solution is printed. This solution must be better than the previous solution produced for the same environmental information. The PIBO algorithm is presented as in Algorithm1.Figure1 represents the algorithm flow chart of the new PIBO algorithm.Figure 1
Algorithm flow chart.Relevance estimation and value calibration (REVAC) introduced by Nannen and Eiben [35] is used to assist tuning the control parameters. Racing of Maron and Moore [36] and sharpening used by Bartz-Beielstein et al. [37] are incorporated into the REVAC algorithm to fine-tune the parameters. Default values of the REVAC algorithm are used. The best values of tuning the tolerance optimiser are η=-0.1 and η=0.13, throughput accelerator, τ=0.077, and filter parameter, α=0.89. These values of the input parameters are used to execute the PIBO algorithm using three sets of benchmark problems. Figures 2 and 3 show the graphical presentation of the tolerance optimiser of the best two values.Figure 2
Graphical representation ofη=0.13.Figure 3
Graphical representation ofη=-0.1.


## 2.1. Environmental Information

Environmental information comes in various forms that require different actions. A population,N, of environmental information, xi, is generated by various plant parts such as roots, leaves, and trunk. A population xi∈N is generated first before anything else. Line (3) of Algorithm 1 defines environmental information.Algorithm 1
(1) START
(2) Objective function O(xi)=(x1,x2,…,xi)T
(3) Generate initial population of N environmental information xi
(4) Define perception, Fi for xi
(5) while  N<MaxGen  do
(6) Get a plant randomly
(7) Initiate signal transduction creating response ri
(8) Evaluate ri appropriateness by finding P(ri)
(9) Set up the initial adaptive network, G0
(10) Get α,β,τ and η
(11) if  αxi>0∧βxi>0∧τxi>0∧ηxi>0∨ηxi≤0  then
(12) Find max⁡{G(xi)}
(13) Choose (α,τ,β)>0 that produces the set max{P(G)}
(14) else if  α=β=τ≤0  then
(15) Set P(G)=0
(16) Wait until α>0∧β>0∧τ>0∧η>0∨η≤0
(17) end if
(18) Construct the set V={V1,1k,…,Vjik} of the response instances
(19) Generate the response tissue integration decision M(xi,t)
(20) if  M(xi,t+1)>M(xi,t)  then
(21) Choose the response V(xi,t+1)
(22) else if  M(xi,t+1)<M(xi,t)  then
(23) Choose response V(xi,t)
(24) else if  V(xi,t)∉V  then
(25) Set M(xi,t)=0 and stop, abandon the response decision and make another decision
(26) end if
(27) Evaluate fitness, Ai
(28) if  Ai>Ai∗  then
(29) Produce intelligent phenotype, Ci
(30) else if  Ai<Ai∗  then
(31) Set Ci=C0 and re-analyse Fi
(32) end if
(33) Determine compactness, Z(xi), of Ci
(34) if  Z(xi)≥Z(xi∗)  then
(35) Set Z(xi)=Z∗(xi)
(36) else if  Z(xi)≤Z(xi∗)  then
(37) Set Z(xi∗)=Z∗(xi)
(38) end if
(39) Find best current solution, O(xi∗)
(40) end while
(41) Return the results
(42) STOP


## 2.2. Plant Perception

Plants perception, sometimes referred to as biocommunication, is a way how plants communicate. Plants have the ability to sense and respond to the environment. This can lead to adjustment in morphology, physiology, and phenotype. Reactions to chemicals, light, gravity, parasites, and many other factors have been noted in plants. Perception frequency,Fi, for environmental information, xi, is defined. This will be used in future encounters with the same information. Equation (1) represents perception frequency where γ is drawn from a uniform distribution, U[0,1]. In Algorithm 1, line (4) presents plant perception:(1)Fi=hxi,min+γhxi,max-hxi,min.


## 2.3. Signal Transduction

Signal transduction occurs when the extracellular molecule activates a receptor that in turn triggers biochemical events resulting in a response. Signal transduction (line(7) of Algorithm 1), ri, is affected by stimulus location, type, duration, and intensity. Equation (2) shows the signal transduction level of the environmental information by the plant:(2)ri=1stype+sloc+sdur+sintxi×100%.


## 2.4. Assessment

The plant will assess the information transmitted in order to make an informed decision. This is an important step of the algorithm because it is the one that affects the action to be taken. Assessment ofxi is carried out to determine the effect of the environmental information, and (3) presents assessment function. It is shown that 0≤P(ri)≤1 from (3). The smaller the value of P(ri) is, the greater the chance that the adaptive representational network, G, is formulated is. Research suggests that memory in plants cannot be constructed without first learning. Plants learn complex things such as stress, condition of drought, cold, heat, flooding, and many more through reinforcement [31–34], and this is the reason for using previous environmental information when carrying out current assessment.(3)Pri=xi∗xi,xi∗≤xi,xi≠0.


## 2.5. Adaptive Representational Network

Adjustment in the morphology or physiology and phenotype may take place depending on the type of environmental information at hand. The networkG=(B,E) will be formulated where B is the set of components (morphology, phenotype, and physiology) and E are edges. This network presents what is to be done. Use of Boolean operators AND, OR, and NOR is carried out at this stage of the algorithm. To ensure that the adaptive representational network formulated is useful, set α, β, and τ to be nonnegative. The tolerance optimiser does not matter if it is negative.


## 2.6. Tissue Integration

The state of all nodes in the adaptive representational network can be modelled as follows:(4)Y¯ik+1=Yix1k,x2k,…,xIk,i∈I.The variable Y¯i[·] is updated according to (5)Y¯ik+1Tik=Yix1kV1ik,x2kV2ik,…,xIkVJik,k∈N,j=1,2,…,J,where (6) and (7) represent Tik and Vjik, respectively.(6)Tik=minjl⁡Tjl≥t,for  somek(7)Vjik=maxl⁡Tjl:Tik>Tjl=V.The response tissue integration decision is then presented by (8)Mxi,t=max⁡Y¯i1,…,Y¯ik.


## 2.7. Fitness and Intelligent Phenotype Production

In this step, the algorithm will evaluate the fitness of tissue integration decision. Information gathered from learning previous environmental information reinforces the evaluation criteria. This means that the previous environmental information intensity,xi∗, leading to the optimal tissue integration decision, Ai∗, should be smaller than or equal to the current environmental information intensity, xi, so that the current fitness, Ai, can lead to the intelligent phenotype production, Ci.


## 2.8. Compactness and the Solution

Compactness of the intelligent phenotype produced is important for the plant to achieve the goal. The algorithm ranks the current solution and the best solution is printed. This solution must be better than the previous solution produced for the same environmental information. The PIBO algorithm is presented as in Algorithm1.Figure1 represents the algorithm flow chart of the new PIBO algorithm.Figure 1
Algorithm flow chart.Relevance estimation and value calibration (REVAC) introduced by Nannen and Eiben [35] is used to assist tuning the control parameters. Racing of Maron and Moore [36] and sharpening used by Bartz-Beielstein et al. [37] are incorporated into the REVAC algorithm to fine-tune the parameters. Default values of the REVAC algorithm are used. The best values of tuning the tolerance optimiser are η=-0.1 and η=0.13, throughput accelerator, τ=0.077, and filter parameter, α=0.89. These values of the input parameters are used to execute the PIBO algorithm using three sets of benchmark problems. Figures 2 and 3 show the graphical presentation of the tolerance optimiser of the best two values.Figure 2
Graphical representation ofη=0.13.Figure 3
Graphical representation ofη=-0.1.


## 3. Computational Experiments

This section presents computational experiments of the PIBO algorithm and its results are compared to those available in literature. The algorithm is implemented to solve three sets of known benchmark vehicle routing problems, 12 very large-scale vehicle routing problems (VLVRP) in Li et al. (2005) [28], 20 large-scale vehicle routing problems (LVRP) in Golden et al. (1998) [38], and 14 small- or medium-sized vehicle routing problems (SVRP) in Christofides and Eilon (1969) [39]. Computational experiments are performed in MATLAB 7.0.4 on a PC with AMD E-300 APU with Radeon™ @1.30 GHz and 4.00 GB RAM. A total of 30 runs are performed for each set of benchmark problems. Table 1 presents information of the problem instances that are used in this paper.Table 1
Information of the SVRP, LVRP and VLRP benchmark problems instance.
Type
Problem
Number of customers
Number of vehicles
Vehicles capacity
Maximum route length
Service time
SVRP
1
50
5
160
2
75
10
140
3
100
8
200
4
150
12
200
5
199
17
200
6
50
6
160
200
10
7
75
11
140
160
10
8
100
9
200
230
10
9
150
14
200
200
10
10
199
18
200
200
10
11
120
7
200
12
100
10
200
13
120
11
200
720
50
14
100
11
200
1040
90
LVRP
1
240
550
650
2
320
700
900
3
400
900
1200
4
480
1000
1600
5
200
900
1800
6
280
900
1500
7
360
900
1300
8
440
900
1200
9
255
1000
∞
10
323
1000
∞
11
399
1000
∞
12
483
1000
∞
13
252
1000
∞
14
320
1000
∞
15
396
1000
∞
16
480
1000
∞
17
240
200
∞
18
300
200
∞
19
360
200
∞
20
420
200
∞
VLVRP
1
560
10
2
600
15
3
640
10
4
720
10
5
760
20
6
800
11
7
840
20
8
880
10
9
960
10
10
1040
10
11
1120
10
12
1200
11Computational results of the PIBO algorithm are shown in Table2. Two best values of tolerance optimiser, η, are used. The third column (avail sol) presents the available solution, time (m) is the time in minutes, and number of feasible solutions is presented in the succeeding column. The average solutions are presented by the column labeled “avg sol” and best solutions by the column titled “best sol,” and D is the deviation. The results show that the PIBO algorithm performs better when η=0.13 as compared to η=-0.1.Table 2
Computational results of the SVRP, LVRP and VLVRP benchmark problems instance.
Type
Problem
η
=
-
0.1
η
=
0.13
Availbest
Time(min)
No. feasiblesol
Avgsol
Bestsol
D
% best
Time(min)
No. feasiblesol
Avgsol
Bestsol
D
%
SVRP
1
524.61
0.15
∗
30
524.61
524.6
0.00
0.15
∗
30
523.09
523.07
0.29
2
835.26
0.32
∗
30
834.09
834.09
0.14
0.32
∗
30
834.01
834
0.00
3
826.14
0.37
∗
29
825
824.9
0.15
0.35
∗
30
824.87
824.87
0.02
4
1028.42
0.80
∗
30
1028.05
1028.05
0.04
0.78
∗
30
1028.04
1028.02
0.04
5
1291.29
1.08
∗
27
1291.32
1291.31
0.00
1.07
∗
29
1292.01
1292.01
-
0.06
11
1042.11
0.48
∗
30
1042.06
1042.02
0.01
0.48
∗
30
1041.97
1041.97
0.01
12
819.56
0.34
∗
30
819.6
819.56
0.00
0.33
∗
30
819.03
819.02
0.07
LVRP
1
5627.54
1.47
30
5554.01
5553.87
1.31
1.43
30
5551.98
5548.02
0.05
2
8447.92
2.31
30
8447.92
8444.11
0.05
2.3
30
8440.99
8440.99
0.08
3
11036.22
3.2
30
11025.10
11025.1
0.10
3.2
30
11022.01
11019.76
0.15
4
13624.52
4.3
30
13602.34
13601.1
0.17
3.9
30
13548.9
13544.06
0.03
5
6460.98
1.1
30
6459.07
6459.03
0.03
1
30
6458.63
6455.52
0.08
6
8412.8
1.42
30
8409.30
8408.54
0.05
1.02
30
8402.33
8400.31
0.15
7
10181.75
1.76
30
10177.98
10177.02
0.05
1.44
30
10167.71
10152.98
0.12
8
11643.9
2.55
30
11638.02
11638.02
0.05
2.43
30
11635.7
11634.44
0.08
9
580.48
4.02
30
580.02
580.02
0.08
3.91
30
567.2
565.75
0.00
10
738.73
1.5
30
737.98
737.98
0.10
1.02
30
733.33
732.08
0.21
11
914.75
3.72
30
912.22
912.04
0.30
3.22
30
909.14
909.14
0.31
12
1106.33
4.2
30
1106.01
1106.01
0.03
3.78
30
1088.4
1088.4
0.02
13
857.19
1.7
30
857.22
857.22
0.00
1.4
30
853.49
853.02
0.01
14
1080.55
2.4
30
1080.03
1080.03
0.05
2.3
30
1077.54
1077.54
0.21
15
1340.24
3
30
1338.11
1338.1
0.16
3
30
1333.61
1333.52
0.21
16
1616.33
4.98
28
1614.20
1614.19
0.13
4.98
28
1614.2
1614.2
0.09
17
707.76
1.1
30
702.82
702.8
0.70
0.9
30
702.66
701.76
0.00
18
995.39
1.49
30
991.04
991.01
0.44
1.49
30
991.01
991.01
0.34
19
1366.14
2.2
30
1364.90
1364.9
0.09
2.22
30
1355.82
1355.76
0.02
20
1819.99
2.48
30
1815.81
1815.78
0.23
2.45
30
1811.11
1811.02
0.09
VLVRP
1
16212.74
5.90
30
16219.81
16219.81
-
0.04
5.77
30
16211.81
16211.81
0.01
2
14597.18
6.70
30
14567.09
14555.74
0.28
6.67
30
14553.78
14553.78
0.30
3
18801.12
7.65
30
18889.05
18855.99
-
0.29
7.56
30
18888.41
18888.41
-
0.46
4
21389.33
9.45
30
21373.91
21372.77
0.08
9.45
30
21370.99
21370.99
0.09
5
16902.16
11.32
30
16880.01
16784.76
0.69
11.02
30
16878.05
16878.04
0.14
6
23971.7
12.03
30
23965.70
23965.7
0.03
12.00
30
23964.17
23964.15
0.03
7
17488.74
12.64
30
17473.11
17472.21
0.09
12.76
30
17467.63
17467.63
0.12
8
26565.92
13.23
30
26566.38
26566.38
0.00
13.20
30
26565.04
26565.04
0.00
9
29154.34
15.57
30
29144.93
29144.93
0.03
15.55
30
29141.09
29141.08
0.05
10
31742.51
18.09
29
31746.72
31744.92
-
0.01
18.66
30
31746.05
31746.03
-
0.01
11
34330.84
20.10
30
34335.01
34335
-
0.01
20.11
30
34332.76
34332.76
-
0.01
12
36919.24
26.77
28
36912.51
36911.34
0.02
26.22
28
36912.03
36912.03
0.02
∗Time recorded in seconds in order to show differences.Table3 show results of the PIBO algorithm compared to the best results available in the literature for the SVRP problems. The results show that PIBO algorithm is promising. The average deviation from the previous best solution obtained by executing the PIBO algorithm to achieve optimality is 0.07, while the best result so far is 0.00 seconds obtained by a computer with processor speed of 2 G. The algorithm outperformed most of the results in literature and might even perform better if it is executed on a PC with a faster processor.Table 3
Comparison of the results of different algorithms for the SVRP benchmark problem instances.
Problem
SA
SB
SC
SD
SE
SF
SG
SH
SI
SJ
SK
SL
SM
SN
SO
SP
PIBO
1
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.29
2
0.00
0.00
0.40
0.00
0.00
0.00
0.00
0.02
0.00
0.00
0.06
0.00
0.00
0.00
0.00
0.00
0.00
3
0.00
0.00
0.29
0.00
0.15
0.00
0.00
0.16
0.00
0.00
0.00
0.15
0.00
0.00
0.00
0.00
0.02
4
0.41
0.24
0.47
0.31
0.75
0.00
0.00
0.76
0.00
0.11
0.12
0.26
0.00
0.10
1.00
0.29
0.04
5
1.90
1.77
2.09
0.69
2.54
1.56
0.00
1.24
0.00
0.45
1.01
2.64
0.00
0.22
1.58
1.07
0.03
11
3.01
0.00
0.07
0.00
0.10
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.33
0.00
0.01
12
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.07
Avg
0.76
0.29
0.47
0.14
0.51
0.22
0.00
0.31
0.00
0.08
0.17
0.44
0.00
0.05
0.42
0.19
0.07
CPU
2 G
400 M
200 M
1 G
400 M
400 M
2 G
733 M
2.8 G
3 G
2.4 G
2.4 G
2.4 G
2.8 G
2.8 G
1.6 G
1.3 G
Time (min)
24.62
5.22
3.84
5.19
21.25
6.96
0.08
28.91
0.03
17.43
5.84
4.54
23.74
5.19
8.21
-
4.51
Notes. SA, Cordeau et al. (2001) [12]; SB, Tarantilis and Kiranoudis (2002) [13]; SC, Toth and Vigo (2003) [14]; SD, Prins (2004) [15]; SE, Berger and Barkaoui (2004) [16]; SF, Tarantilis (2005) [17]; SG, Mester and Braysy (2005) [18]; SH, Ergun et al. (2006) [19]; SI, Mester and Braysy (2007) [20]; SJ, Pisinger and Ropke (2007) [21]; SK, Derigs and Kaiser (2006) [22]; SL, Derigs and Kaiser (2006) [22]; SM, Nagata (2007) [23]; SN, Prins (2009) [24]; SO, Lin et al. (2009) [25]; SP, Xiao et al. (2014) [26].In Table4, PIBO algorithm with η=0.13 is compared to the results available in literature for the LVRP set of benchmark problems. The best solutions obtained by the PIBO algorithm outperform all the other solutions they have been compared to for this set of benchmark problems. Finally, results obtained by executing PIBO to solve VLVRP are presented in Table 5. Again, the results show that PIBO algorithm outperforms all the other algorithms it has been compared with. The best average results deviation was obtained by Xiao et al. (2014) [26] as D=0.11. There is a significant difference between the result obtained by PIBO and the average best result in literature.Table 4
Comparison of the results of the LVRP benchmark problems instance.
Problem
LA
LB
LC
LD
LE
LF
LG
LH
LI
LJ
LK
LL
LM
PIBO
1
1.93
0.29
0.69
0.00
4.27
4.27
0.42
0.24
0.30
0.30
2.99
0.57
-
0.01
0.05
2
1.24
0.01
0.25
0.00
0.34
0.34
0.25
0.18
0.03
0.00
0.64
0.20
0.06
0.08
3
3.32
0.00
0.99
0.00
0.07
0.07
0.10
0.04
0.51
0.00
2.98
0.21
0.00
0.15
4
9.44
0.55
0.98
0.00
0.10
0.05
0.08
0.83
0.80
0.00
3.76
0.00
0.02
0.03
5
3.66
0.00
0.26
0.00
0.00
0.00
0.09
0.00
0.00
0.00
0.79
0.00
0.00
0.08
6
6.54
0.00
1.51
0.00
0.03
0.03
0.04
0.01
0.00
0.00
1.67
0.00
0.00
0.15
7
3.59
0.14
1.06
0.14
1.14
1.14
0.00
0.84
0.14
0.14
2.37
0.84
0.14
0.12
8
3.37
1.59
2.38
0.17
1.99
1.96
0.60
1.95
1.98
0.00
2.94
0.97
0.17
0.08
9
2.22
1.10
1.34
0.50
6.92
6.92
0.80
0.80
1.44
0.99
1.07
0.80
0.00
0.00
10
1.75
1.63
1.46
0.38
8.42
6.23
1.38
0.97
1.20
0.76
1.38
0.90
0.04
0.21
11
2.33
1.37
1.22
0.40
9.44
7.88
0.87
0.89
1.65
0.84
1.09
0.65
0.17
0.31
12
3.69
3.12
1.96
0.08
10.34
9.28
1.15
1.12
1.08
0.88
1.75
0.97
0.25
0.02
13
1.35
0.92
0.93
0.22
10.28
8.01
0.87
0.97
0.92
0.60
1.18
0.52
0.24
0.01
14
1.45
1.22
1.59
0.07
9.52
6.91
1.37
1.43
1.41
0.81
1.69
0.77
0.00
0.21
15
2.18
1.34
1.58
0.37
10.17
9.05
1.47
1.11
1.22
0.91
1.22
1.20
0.36
0.21
16
2.23
1.16
1.19
0.39
8.62
7.83
1.41
1.56
1.89
1.11
1.64
0.89
0.35
0.09
17
0.47
0.14
0.56
0.00
5.09
2.58
0.16
0.25
0.27
0.15
0.64
0.16
0.17
0.00
18
2.15
0.35
1.50
0.34
11.05
8.25
0.71
0.73
0.95
0.68
2.26
1.52
0.52
0.34
19
2.55
0.08
1.20
0.05
6.53
5.74
0.59
1.26
1.12
0.40
1.38
1.21
0.24
0.02
20
5.27
0.16
1.70
0.01
9.32
6.49
0.59
1.65
1.46
0.60
1.97
1.09
0.21
0.09
Avg
3.04
0.76
1.22
0.16
5.68
4.65
0.65
0.84
0.92
0.46
1.77
0.67
0.15
0.11
CPU
200 M
900 M
1 G
2.8 G
3 G
3 G
3 G
2.4 G
2.4 G
2.8 G
2.8 G
2.93 G
1.6 G
1.3 G
Avg time (min)
17.55
49.3
1.33
24.35
0.18
1.01
107.61
109.63
111.10
66.9
118.98
284.4
-
2.65
Notes. LA, Toth and Vigo (2003) [14]; LB, Reimann et al. (2004) [27]; LC, Li et al. (2005) [28]; LD, Mester and Braysy (2007) [20]; LE, Kytöjoki et al. (2007) [29]; LF, Kytöjoki et al. (2007) [29]; LG, Pisinger and Ropke (2007) [21]; LH, Derigs and Kaiser (2006) [22]; LI, Derigs and Kaiser (2006) [22]; LJ, Prins (2009) [24]; LK, Lin et al. (2009) [25]; LL, Chen et al. (2010) [30]; LM, Xiao et al. (2014) [26].Table 5
Comparison of the results of the VLVRP benchmark problems instance.
Problem
VA
VB
VC
VD
VE
VF
PIBO
1
1.10
2.41
0.00
0.19
0.05
0.01
0.01
2
0.37
0.23
0.00
0.40
0.40
0.14
0.30
3
1.09
0.19
0.00
0.11
0.05
0.00
-
0.46
4
1.85
0.62
0.00
0.06
0.06
0.01
0.09
5
1.47
0.00
1.14
3.72
2.7
0.65
0.14
6
0.91
0.18
0.00
0.36
0.1
0.04
0.03
7
1.91
0.71
0.00
4.34
4.26
-
0.32
0.12
8
0.15
0.85
0.00
0.1
0.1
0.00
0.00
9
0.09
0.86
0.02
0.04
0.04
0.01
0.05
10
0.74
0.71
0.00
0.2
0.2
0.00
-
0.01
11
3.02
1.28
0.00
0.06
0.06
0.00
-
0.01
12
1.36
1.24
0.03
0.29
0.29
0.77
0.02
Average
1.28
0.58
0.10
0.82
0.69
0.11
0.02
CPU
1 G
3 G
2.8 G
3 G
3 G
1.6 G
1.3 G
Avg time (min)
2.72
7.7
8
0.04
0.13
-
5.03
Notes. VA, Li et al. (2005) [28]; VB, Pisinger and Ropke (2007) [21]; VC, Mester and Braysy (2007) [20]; VD, Kytöjoki et al. (2007) [29]; VE, Kytöjoki et al. (2007) [29]; VF, Xiao et al. (2014) [26].Statistical analysis of the results is done to establish significance differences between them, if any. Analysis of variance (ANOVA) is performed on the results obtained by the 30 runs performed. Results show that the results obtained by the PIBO algorithm are significantly different from those that are available in literature with the probability valuep=0.02 and p=0.00 for the LVRP and VLVRP, respectively, but insignificantly different (p=0.65) for the SVRP instances. Since the solution space is very large for these problems, memory of previous best solution is important. The ability of the plant to change morphology, physiology, and phenotype in response to the environment and conditions and storage of memory of previous experiences may have assisted the PIBO algorithm to be more efficient when solving these problems.


## 4. Conclusion

A new optimisation algorithm called PIBO is formulated and executed to solve some benchmark vehicle routing problems. The development of the algorithm is motivated by plant intelligence behaviour. Results show that the PIBO algorithm outperforms most of the results reported in literature for LVRP and VLVRP problem instances. The PIBO algorithm is a promising optimisation algorithm to solve large vehicle routing problems which have a very large solution space. The new algorithm has an ability to adjust to changing problem conditions. It is suggested that future research be directed towards improving input parameters and testing applicability of the algorithm to a wider range of problems.



---

*Source: 9874356-2018-02-06.xml*