# Particle Swarm Optimization For Evacuation Vehicle Routing Problem Biology Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract-An optimal evacuation route plan has to be established to overcome the problem of poor coordination and uneven distribution of vehicles before or during disaster. This article introduces evacuation vehicle routing problem (EVRP) as a new variant to vehicle routing problem (VRP). EVRP is a process of evacuating people from vehicle location to the potentially flooded area (PFA), and from PFA to relief center using a number of capacitated vehicles. The purpose of this paper is to examine the use of a multi-valued discrete particle swarm optimization (DPSO) focusing on the routing of vehicles from vehicle location to PFA. A solution representation is adopted and modified from the solution of shortest path problem (SPP) to accommodate this problem. Experimental results tested based on the objective function which is to find a minimum total travelling using datasets from a flash flood evacuation operation. The findings reveal that DPSO obtain better results compared to a genetic algorithm (GA).

Keywords-discrete particle swarm optimization; evacuation route plan; evacuation vehicle routing problem; potentially flooded area; vehicle routing problem

introduction

During evacuation, it is difficult to find the possible evacuation route to move people to safety due to lack of information required by the relevant agencies to response to floods. The inadequacy in flood response had triggered NSC to formulate sustainable emergency procedure to safe evacuees and properties. Nevertheless, the guideline on disaster management [3] has limited advantages. It merely serves as reference that is very generic and it is only a manual guidance on responses to disaster. In all circumstances of evacuation planning, immediate response is crucial as time is the decisive factor. Therefore, emergency evacuation route plan should be generated immediately after warning has been issued by considering the safe routes for evacuees, location, and allocation of evacuees. An optimization algorithm is required to help in producing an optimal emergency evacuation plan to help local authorities and related agencies making prompt and informed decision.

Few optimization algorithms have been developed in other countries for several types of natural disaster in evacuation planning, namely Capacity Constrained Route Planning [5-7], A* [7], Flip High Flip Edge [8], greedy heuristic [9-10], Bottleneck Relief Heuristic [9-10], BEST [11], SP-TAG [11], and multi-ant colony system [Zong et al., 2010]. Some of them have demonstrated good performance in optimizing evacuation planning but they does not emphasis on the capacity of vehicle during routing. Thus, this paper introduces evacuation vehicle routing problem (EVRP) as a new variant to vehicle routing problem (VRP) since it has same core process to VRP. EVRP consider routing of number of vehicles that has been assigned with a number of people. Prior to solve the EVRP, a list of assigned vehicles with its capacity is generated using DPSO-VAP from [isci, 2010]. Moreover, in finding solutions to EVRP, it does not matter to observe the solution from the shortest path problem (SPP) since SPP is a basic process of a VRP.

In this paper, we focus on the use a multi-valued discrete particle swarm optimization (DPSO) considering a static routing of capacitated vehicles from vehicle location to PFA to find a minimum total evacuation time. This is because PSO has shown a significant results to SPP and outperformed a GA in [5]. A range of random discrete priority values (PVs) that represent all of the nodes in a network graph offer 95% optimal solution for PSO in this research.

The other reason is based on the performance of the employment of DPSO in a variants of VRP which is closely related to EVRP. It has been observed that EVRP is closely related to the capacitated vehicle routing problem (CVRP) primarily in handling capacity constraints (Lin et al. 2006; Ling et al. 2006; Zhishou and Yueting, 2006; (Marinakis and Marinaki, 2010)]). In particular, EVRP deals with routing of a number of capacitated vehicles to PFA, whereas CVRP deals with the delivery of goods to customers. CVRP assumes that each customer is served by exactly one vehicle without exceeding the capacity constraints of each vehicle. This assumption appear to be similar to the EVRP.

Several optimization algorithms were employed in (Lin et al. 2006; Ling et al. 2006; Zhishou and Yueting, 2006; (Marinakis and Marinaki, 2010)]) for solving CVRP. In general, they obtained an effective results in processing time but an optimal result is not guarantee. For example, GA with local search is applied in [Lin et al. 2006] and DPSO with binary position and a hybrid of DPSO-SA in Ling et al. 2006. In addition, with the embedded of the two solution representations for CVRP in PSO which is SR-1 and SR-2 are shown that the PSO is effective for solution quality and computational time (Ai and Kachivichyanukul, 2009b). They use a real value for the particle position representation comprises of customer priority and vehicle priority. SR-1 finds a sequence of route for each vehicle and route the vehicle to customer based on the Euclidean distance from between customer and vehicle reference point while SR-2 embedded the coverage of radius based on vehicle orientation point for vehicle routing. Local improvement were added to change the customer route direction to directly improve the routing cost. Although this solution seems possible for finding an optimal results for EVRP, but we have some limitation of information to generate PFA' priority and vehicle priority value to be able for generating a real value. Consequently, the EVRP solution will be based on the problem formulation given in Section III and concentrates on a discrete particle representation.

This paper is organized as follows. Section II presents the reviews of particle swarm optimization (PSO). Section III presents the problem formulation. Section IV elaborates the solution representation and the DPSO algorithm is discussed in Section V. Section VI explains the computational results and discussion. Finally, Section VII concludes the paper and addresses some future work.

Particle swarm optimization

PSO was introduced by Kennedy and Eberhart in the mid-1990s (Kennedy and Eberhart, 1995). It is a population-based stochastic approach grouped under swarm intelligence (Engelbrecht 2002) to solve continuous and discrete problems. PSO indicates the velocity and position of particles in multi-dimensional space. By updating both the velocity and position, a feasible solution would be achieved. The fitness values comprises of Gbest and Pbest that derives from a simulated behaviour of a group of particles (Guner and Sevkli, 2008). PSO is able to explore regions of the search space and exploit the search to refine a feasible solutions. These search strategies are influenced by the parameters acceleration constant and inertia weight (Engelbrecht 2002; Shi and Eberhart, 1999). Equation 1 and equation 2 present the velocity and position formulas for the canonical PSO (Shi et al. 1999), respectively.

Vid(new)=W x Vid(old) + C1 x r x(Pbest - Xid(old) + C2 x r x (Gbest-Xid(old)) (1)

Xid(new)=Xid(old) + Vid(new) (2)

where Vid(new) and Vid(old) are the velocity of particle i, Xid(old) and Xid(new) are the particle position, and W is the inertia weight. C1 and C2 are the acceleration constant parameters, r is the random function in the range of [0,1], Pbest is the personal best of the ith particle, and Gbest is the best position derived from all particles in the swarm.

Many researchers have demonstrated the advantages of using PSO to solve several types of problems. These include the travelling salesman problem (Tasgetiren et al. 2007; Zhong et al. 2007) and vehicle routing (Ling et al. 2006). PSO is easy to implement and is computationally efficient (Li et al. 2006, Eberhart et al. 1995). Improvements for PSO have been developed to measure the performance of PSO for various types of problems (Veeramachaneni et al. 2007; Alhajri et al. 1997) and across standard benchmark datasets (Zhong et al. 2007; Veeramachaneni et al. 2007; Al-Kazemi et al. 2005). For example, the canonical PSO applies inertia weight in updating velocity to simulate the social behaviour of birds. This approach was improved by using a constriction coefficient (CF) to solve a continuous problem (Eberhart et al. 2000).

After two years of PSO development, a discrete problem had concentrated on the initial work involving discrete binary PSO begun by Kennedy and Eberhart (1997). They proposed a new way of updating the position of particles (Kennedy et.al, 1997) to accommodate a discrete binary problem. This approach was then improved in several studies based on a benchmark dataset (Eberhart et al. 2000; Bui et al. 2007) and a real-world situation (Gong et al. 2008, Gao et al. 2006) of the discrete problem. When compared to other optimization methods, the performance of DPSO is competitive with a genetic algorithm (Gong et al. 2008). This demonstrates that DPSO, with its global search capability and local exploitation, is a promising approach to finding the optimum solution and, therefore, it should be further investigated.

Problem formulation

This paper emphasizes on EVRP that involve with routing of a number of vehicles from vehicle location to a single destination (only one PFA). EVRP addresses the objective function to find a minimum total traveling time for all the capacitated vehicle from vehicle location to PFA. This problem is mathematically formulated based on some terminology that was adopted from the previous research on VRP [vrp10 ropke][vrp7][vrp16]. The problem can be formally defined as follows: Let G = (N, E) be a weighted directed graph. Define N = {N0, N2, N3, ... Nn}. N0 represents a vehicle location and Nn is a destination node (PFA). E is the set of edges. Cij are matrices representing travelling cost of traversing from i to j. For each edge (i, j) ∈ E, a distance dij≥0 and travel time tij≥ 0, is a non negative integers. Vij is the set of all vehicles that are able to move from node i and j, where V={V1, V2, ...., Vk}. The capacity of vehicle, c ∈ V is denoted as Vc . Decision variable, Xijk,is a binary variable which 1 if vehicle k travel from node i to node j, otherwise 0. The objective function is to find a minimum total travelling time for all vehicles from N0 to Nn. The EVRP is mathematically formulated as shown below:

Subject to:

Constraints (4) and (5) ensure that all vehicles travelled. Constraint (6) is the set of bound decision variables.

solution representation

The solution representation for EVRP is adopted from [Mohemmed et al., 2008] for the reason that the solution representation proposed in this research obtained good performance in SPP. To accommodate the EVRP, we enhance this representation taken into account a number of capacitated vehicles. However, the use of PV which representing each of nodes is maintained as shown in Figure 1. Figure 2 shows the representation of a particle consists of an array of PVs that is assigned to each of the capacitated vehicles. In other word, a particle comprises of matrix of PVn x Vm.

PV0

PV1

PV 2

PV3

## ...

PV n-1

PVn

N0

N1

N 2

N3

## ...

N n-1

Nn

Figure 1. Each of PV is assigned to each node

PV0

PV1

PV 2

PV3

## ...

PV n-1

PVn

V1

PV0

PV1

PV2

PV3

## ...

PV n-1

PVn

V2

PV0

PV1

PV 2

PV3

## ...

PV n-1

PVn

V3

## ...

## ...

## ...

## ...

## ...

## ...

## ...

## .

## .

PV

PV1

PV 2

PV3

## ...

PV n-1

PVn

Vm

Figure 2. A particle consists of an array of PVs that is assigned to each of the capacitated vehicles

Each vehicle traverses from vehicle location, N0, try to find a valid path to PFA, Nn. During traversing on each path, for example from N0 to N1, if it is a valid path then, the travelling time for the vehicle is calculated. The travelling time is depending on the distance for the valid path and the standard travelling speed of the vehicle is calculated as using Equation 7.

tv = d/tsv (7)

where tv is travelling time for each vehicle for the valid path travelled, d is a distance between two nodes (edge), tsv is a standard travelling speed for each vehicle. The total travelling time for each of vehicle travelled through valid path is then calculated as using Equation 8.

= (8)

where ttv is the total travelling time for each vehicle travelled through all the valid paths. Total travelling time for all vehicles is based on number of vehicles travel on the valid path using Equation 9.

= (9)

ttvs is presented as the fitness value calculated for each population of particle. The total travelling time might be different because the number of vehicles travelled are depending on the vehicles generated from the [] and its standard travelling speed. The next section explains the solution representation into the DPSO.

discrete partilce swarm optmization

The new representation for EVRP solution is therefore implemented in the DPSO as shown in Fig. 3. The algorithm starts with the normal process of PSO initialization, which initializes the number of population, coefficient values, C1 and C2 in step 2 and step 3. Step 4 is the initialization PVs and velocities. Step 5 retrieve vehicle's information include the vehicle id, vehicle capacity, and its standard travelling speed. Step 6 until 10 follows the similar steps as in [].

Pbest is the total distance for each particle, whereas Gbest is the minimum total distance obtains from all particles. The iteration process starts at line 7 until 20 until a maximum iteration is achieved. In this iteration, each particle is updated with a new velocity update and position using Equation 6 and 7. The new velocity and new position value are in the form of positive integers. Then, PVs for all sub particles are updated using step 11. Step 12 performs the decomposition and random selection of PV.

Pbest(new) and Gbest(new) are calculated in step 13 and 14, respectively. Step 15 until 19 are the condition for the selection of the best current fitness for each iteration.

Begin

Initialize number of particle's population

Declare C1 and C2

Initialize PVs, Vmin and Vmax for all particles in random

Retrieve vehicle's information from []

For each vehicles

Construct a path

If it is a valid path

Calculate fitness value (total travelling time)

else

Return its as 0

If there is a vehicle arrive at destination

Other vehicle uses the PV used by this vehicle

Calculate Pbest(old) and Gbest(old)

Do

For each particle

Calculate V(new) using equation (6)

Calculate PV(new) using equation (7)

Update PVs

If there is a vehicle arrive at destination

other vehicles uses the PV used by this vehicle

Calculate Pbest (new)

Calculate Gbest (new)

If (Gbest (new) > Gbest(old))

Assign Gbest(old) as the best current fitness

If (Gbest (new) =< Gbest(old))

Gbest(old))= Gbest (new)

Assign Gbest(new) as the best current fitness

While (maximum iteration is achieved or all vehicles arrived at destination)

End

Computational result and discussion

This section presents the computational results to see the performance of the DPSO algorithm's behavior in the context of applying a discrete particle position in EVRP. The novel DPSO algorithm; myDPSO-VR was implemented in JAVA language and run on a PC with an Intel Core 2 CPU (3.0 GHz) and 2GB memory. In order to verify the proposed approach, a genetic algorithm using the same solution representation as DPSOs is executed. Dijkstra algorithm as an exact method is used as the benchmark for comparing the total travelling time for each dataset. Prior to

experiments these algorithms, Section ? and Section ?, in brief explains the datasets of EVRP, and parameters for the computational experiments.

with flash flood evacuation Datasets were from a flash flood in Kota Tinggi district in December 2006. Routes from vehicle location to potentially flooded area were taken from GIS MAP software. Each route consists of source nodes (vehicle location), nodes, edges, destination node (PFA). All of the routes are transformed into graph abstraction as illustrated in Figure ?. This figure shows the sample of graph abstraction for the routing of a vehicle (V1) starting from node 0 to node 35. The graph is then transferred into an adjacency matrix for easily transform into the algorithm.

9.7.2 Datasets for EVRP

Datasets for this problem were collected from local authorities of Malaysia who are directly involve

The number the capacitated vehicles for each of the dat set are generated using the improved DPSO algorithm from [marina et al., 2010 in published icsi]. Table ? shows the sample of the generated vehicles comprises of vehicle id, destination node for each vehicle, number of people assigned to the particular vehicle, and travelling speed for each vehicle.

Table 9.1 List of vehicles generated from [marina-icsi]

Each of the data set comprises of routes and the generated vehicles (as shown in Table ?). Table ? are list of the datasets used in the computational experiment. It consist of number of nodes, total number of people need to be evacuated, number of the generated vehicles and the number of PFAS. As discussed in Section ? , benchmark instance of VRP is not appropriate for this problem as it was defined differently [].

Table 9.2 List of datasets for computational experiment for datasets from flash flood evacuation in 2006 for a single PFA/ destination

## Datasets

## Number of nodes

## Number people

## Number of generated vehicle [icsi]

VR1_06

12

5853

600

VR2_06

35

26

3

VR3_06

12

1215

154

VR4_06

21

448

52

VR5_06

25

524

59

VR6_06

36

1429

224

Parameter Settings

Parameter selection is defined based on the suggestion from the previous research as can be seen in the list of parameter in Table 7.4. The total traveling time (fitness value) and CPU processing times of each algorithm were evaluated using the datasets from the Table 7.2. In addition, t-test were used to confirm the results. A significant level of 95 percent (α = 0.05) is considered. H0 and H1 are defined as in equation 13 and 14 to determine whether there is a significant difference in terms of its total travelling time and CPU processing time between the two algorithms. The comparisons involve 30 experiments of each datasets.

Table 7.4 List of parameter

## Parameter

## Value

PVmax

-100

PVmin

100

C1

2.05

C2

2.05

Initial Vmin

-10

Initial Vmax

10

Initial weight, w

1.2 [(Shi et al. 1999)]

Stopping condition

Until all vehicle arrives destination or certain 200 iterations

## Vehicle id

## Destination nodes

## Number of people

## Standard Traveling Speed

0

12

6

80

1

12

6

80

2

12

6

90

3

12

15

90

4

12

15

90

5

12

6

90

Comparisons of DPSOs and GAs using datasets of flash flood 2006

The performance of these algorithms is analyzed based on the objective function that was highlighted in the EVRP problem formulation section. The comparisons involve three aspects; total travelling time for all vehicles from vehicle location to PFA/ PFAs, the number of vehicles arrived at destination to reflect the number of people to be pick up at destination (PFAs) and CPU processing time. The total travelling times were compared to Dijkstra algorithm to confirm minimum total travelling times calculated for all vehicles.

The computational experiment starts with datasets with a single node for its destination, with only one PFA. Figure 7.6 shows the total travelling time gathered from 600 vehicles, which all vehicles are arrived at destination, N12 using one iteration in one experiment. Overall, as demonstrated in Table and Figure 7.7, myDPSO_VR_2 outperformed the others resulted with a minimum total travelling and least of Processing times. The results has shown that the embedded graph decomposition in myDPSO_VR_2 has improved the results. The use of PVs representation in myDPSO_VR_1 and GA_VR_1, has an ability to find optimal path to destination, although the results are less good compared with myDPSO_VR_2 and GA_VR_2. This confirm the results in Mohemmed et al., (2008). Additionally, comparing to myDPSO_VR_2 and GA_VR_2, in a genetic algorithm procedure, the off-springs that is generated from a matrix of PVs, the value of PVs is not updated after an iteration. However, DPSO has capability of choosing and updating the PVs as stated in line ? in Figure ? in myDPSO_VR_2 algorithm. Consequently, the results in GA_VR_2 is not stable as can be seen in Figure 7.6, at the 10 populations and 40 populations.

Figure 9.3 Performances of DPSOs and GAs using dataset VR1_06

p

DPSO

GA

PT (s)

i

PT (s)

i

10

9.165

0.343

23

9.136

0.415

1

20

9.136

0.328

2

9.136

0.313

1

30

9.136

0.296

2

9.136

0.319

1

40

9.136

0.390

1

9.136

0.313

1

50

## 8.797

0.452

1

9.136

0.378

1

The next comparison highlights the results of the dataset VR2_06 with 35 nodes, thus more paths require to traverse by vehicles. Table 7.5 demonstrates that he adopted version of DPSO and GA obtained no results after 200 iterations, meanwhile DPSO and GA with graph decomposition obtained optimal solutions, a minimum total travelling time with all vehicles arrived at destinations. Again, the novel solution

representation of discrete particle has shown better than the previous. The results of myDPSO_VR_2 and GA_VR_2 are competitive since they obtained almost similar CPU processing times (second) and similar total travelling time.

The results is based on all vehicle arrive at destination, all people at the destination is assigned to vehicles as in VAP.

Table 9.5 Performance of DPSOs and GAs using dataset VR2_06

From the above results of the above two datasets, 30 population of particles has shown acceptable to obtain good results as suggested in Mohemmed et al., (2008). The computational experiment is continued with dataset VR3_06. In this dataset, 154 vehicles were used need to travel until N12. As can be seen in Table 7.6, both myDPSO_VR_2 and GA_VR_2 are reported similar results in one iteration. On the other hand, the other two algorithms gave optimum total travelling time, but in few iterations. GA_VR_1 is unstable, in population 10 and 30, results were not converge

where all vehicles fail to arrive at destination. This can be seen as the nature of a GA, during its cross over, there is nothing much changes in its PV, and as mentioned above, its PV values does not changed even though after 200 generations of its chromosomes.

Table 9.6 Performance of DPSOs and GAs using dataset VR3_06

P

DPSO

GA

PT (s)

i

PT (s)

i

10

6.459

0.070

2

## -

## -

200

20

6.459

0.072

7

6.459

0.140

1

30

6.459

0.070

23

## -

## -

200

40

6.459

0.080

6

6.459

0.095

1

50

6.459

0.074

12

6.459

0.072

2

Table 7.8 Performance of DPSOs and GAs using dataset VR4_06

P

myDPSO_VR_1

GA_VR_1

PT (s)

i

PT (s)

i

10

1.297

0.046

50

## -

## -

200

20

1.116

0.048

16

## -

## -

200

30

1.102

0.045

8

## -

## -

200

40

1.116

0.046

2

1.116

0.059

2

50

1.116

0.046

2

## -

## -

200

Results for the dataset VR5_06 has reported the similar results to dataset VR2_06, both myDPSO_VR_1 and GA_VR_1 fail to obtain results in 200 iterations, meanwhile the other two algorithms perform good results and achieved the minimum total travelling time, and all vehicles are

arrived at destinations. The results are demonstrated in Table 7.7.

Table 9.7 Performance of DPSOs and GAs using dataset VR5_06

Figure 9.8 Performance of DPSOs and GAs using dataset VR6_06

Figure 9.9 Performance of DPSOs and GAs using dataset VR6_06

From the results above, it can be said that DPSO with branch decomposition with random selection of PV, offer good performance in its fitness and Processing times, and it is very competitive to GA. The solutions representations can be applied to more complex graph abstraction, with more than one number of destinations. The following results emphasis on the results for more than one destination with varies number of nodes and number of vehicles required to traverse from vehicle location to PFAs (many destinations)

- DISCUSS PEOPLE, PARAMETER, NUMBER OF VEHICLES AFFECTED TRAVELLING TIME, ET

Conclusion and recommendation