# Multiobjective Dynamic Vehicle Routing Problem and Time Seed Based Solution Using Particle Swarm Optimization

Authors: Omprakash Kaiwartya; Sushil Kumar; D. K. Lobiyal; Pawan Kumar Tiwari; Abdul Hanan Abdullah; Ahmed Nazar Hassan
Journal: Journal of Sensors
 (2015)

---

## Abstract

A multiobjective dynamic vehicle routing problem (M-DVRP) has been identified and a time seed based solution using particle swarm optimization (TS-PSO) for M-DVRP has been proposed. M-DVRP considers five objectives, namely, geographical ranking of the request, customer ranking, service time, expected reachability time, and satisfaction level of the customers. The multiobjective function of M-DVRP has four components, namely, number of vehicles, expected reachability time, and profit and satisfaction level.  Three constraints of the objective function are vehicle, capacity, and reachability. In TS-PSO, first of all, the problem is partitioned into smaller size DVRPs. Secondly, the time horizon of each smaller size DVRP is divided into time seeds and the problem is solved in each time seed using particle swarm optimization. The proposed solution has been simulated in ns-2 considering real road network of New Delhi, India, and results are compared with those obtained from genetic algorithm (GA) simulations. The comparison confirms that TS-PSO optimizes the multiobjective function of the identified problem better than what is offered by GA solution.


---

## Body

## 1. Introduction

Recently, intelligent transport system (ITS) has diversified the application area of dynamic vehicle routing problem (DVRP) enormously. E-commerce, print media, medical, public transportation, and oil sector are only few examples [1]. DVRP is an extension of traditional vehicle routing problem (VRP) in terms of complexity. The traditional VRP can be symbolically stated on a connected network N
c
(
N
s
,
C
s
,
C
m
), where N
s
=
{
n
0
,
n
1
,
n
2
,
n
3
,
…
,
n
n
} indicates the set of nodes; C
s
=
{
(
n
i
,
n
j
)
,
n
i
,
n
j
∈
N
s and i
≠
j
} represents the set of connections, and C
m
=
C
m
(
i
,
j
)
(
n
i
,
n
j
)
∈
C
s denotes communication cost matrix defined over C
s. Traditionally, the node n
0 is the central depot from where all the vehicles start and end their services. The remaining nodes of N
s denote the customers spread over geographically distinct locations. The VRP is nothing but finding a set of routes for a given set of vehicles such that each vehicle visits the customers exactly once and overall travel cost of the vehicles should be minimum [2]. An example of traditional VRP has been illustrated in Figure 1. The central depot has four delivery vehicles to serve the demands of four customers. According to the availability of routes, the journey for delivery vehicles has been planned by the central depot. Due to the rapid technological advancements in real time wireless communication, the shape of VRP has been transformed into DVRP (cf. Figure 2). In the past, a number of variants of traditional VRP as DVRP have been suggested by incorporating different set of constraints [3]. Some variants of VRP have been illustrated in Table 1.Table 1
The most common variants of VRP.
Serial number
Problem
Problem description
Features
Ref.
1
VRP-PD
VRP with pickup and delivery
It is transportation problem for a given set of goods from some pickup locations to the delivery locations. No central depot for the delivery vehicles is required.
[37]
2
C-VRP
Capacitated VRP
It is a simple VRP with vehicles having prespecified and same goods carrying capacity.
[38]
3
H-VRP
Heterogeneous VRP
It is slightly different from C-VRP. Here, the vehicles have prespecified but different goods carrying capacity.
[39]
4
VRP-LIFO
VRP with last-in-first out
In this VRP, the items that have been picked up most recently must be the items that need to be delivered in the next locations.
[40]
5
VRP-TW
VRP with time window
It is a VRP with delivery time interval for each customer. The delivery vehicles can visit the customers in the given time interval.
[41]
6
O-VRP
Open VRP
In this VRP, the delivery vehicles are not required to report back to the central depot after visiting all the assigned customers.
[42]
7
DAF-VRP
Dial-A-flight VRP
It is a VRP in public transport through airline.
[43]
8
DAR-VRP
Dial-A-ride VRP
It is an on-road general public transport problem.
[44]
9
VRP-MT
VRP with multiple trips
In this VRP, the delivery vehicles take more than one tour once it finishes the assigned tour.
[45]Figure 1
The traditional VRP.Figure 2
Conversion of VRP into DVRP.An example of DVRP has been illustrated in Figure2. Due to real time communication among central depot, new customers, and delivery vehicles, the VRP depicted in Figure 1 has been transformed into DVRP shown in Figure 2. The planned route of all the four delivery vehicles depicted in the VRP (cf. Figure 1) has been changed dynamically due to real time communication of dynamic request. The optimal solution of the above mentioned variants of VRP as DVRPs with large number of customers and their demand parameters could not be obtained within reasonable time due to NP-hard nature of the problems [4]. In the last ten years, various nature inspired metaheuristic techniques have been applied to solve the customized instances of various DVRPs. Genetic algorithm (GA), ant colony optimization (ACO), and particle swarm optimization (PCO) have been commonly used for solving the above listed DVRPs [5–7]. Nowadays, these techniques have also been gaining popularity in vehicular ad hoc networks (VANETs) [8] and high performance computing [9].In this paper, a multiobjective dynamic vehicle routing problem (M-DVRP) has been identified. A time seed based solution using particle swarm optimization (TS-PSO) for M-DVRP has been proposed. The five objectives considered in the proposed problem are geographical ranking of requests, customer ranking, service time, expected reachability time, and satisfaction level of customers. Each of these objectives has been materialized in terms of both conceptual and mathematical formulation. A multiobjective function has been generated having four components, namely, vehicle count/number of vehicles, expected reachability time, profit, and satisfaction level. The mathematical formulations have been derived for each of the component objectives using the metric of the problem. Three constraints of the multiobjective function, namely vehicle, capacity, and reachability have been defined. The proposed solution TS-PSO broadly operates into two steps. In the first step, the identified problem is partitioned into smaller size DVRPs. In the second step, time horizon of each smaller size DVRP has been divided into time seeds and the problem has been solved in each time seed using particle swarm optimization. A complete algorithm has also been developed for the proposed solution technique. The network simulator ns-2.34 has been used for the simulation along with two other supporting software programs MOVE and ArcGIS. The fifteen data sets OPK-01 to OPK-15 used in the simulation have been generated considering real vehicular environment and highly dynamic customer requirements. The simulation results have been compared with the genetic algorithm (GA) solution technique.The rest of the paper is organized as follows. Section2 presents some early and recent developments in dynamic vehicle routing problem. In Section 3, details of the identified problem M-DVRP are described. In Section 4, the TS-PSO is proposed and described. The analytical and simulation results are presented in Section 5. Conclusion is derived in Section 6.


## 2. Early and Recent Developments in VRP and DVRP

The VRP was first proposed by Dantzig and Ramser in 1959. The authors optimized the routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal. They have used linear programing formulation for obtaining near optimal solution [10]. After the induction, VRP has been one of the challenging areas of research that has witnessed consistent attention of the researchers from both industries and academia. The research contribution can be categorized into two dimensions: probabilistic optimization and static optimization. In probabilistic optimization, the components of the problem such as demand, number of customers, and service time have been considered as future events and probabilistic models have been used to predict the future behavior of these components [11, 12]. In static optimizations, available information about the components has been considered without including future behavior of the components. Some of the most recent works in DVRP have been described below. Multiobjective dynamic vehicle routing problem with fuzzy travel times and customers’ satisfaction in supply chain management has been suggested in [13]. The authors have investigated fuzzy time window and fuzzy travel time in depth for the VRP. The travel distance, number of vehicles, and waiting time of vehicles have been minimized and the satisfaction rate of customers has also been minimized. A set based discrete particle swarm optimization approach for optimizing vehicle routing problem (S-PSO-VRPTW) with time window has been suggested in [14]. The solution approach selects an optimal subset from the universal set and subsequently solves the selected subset problem. The authors have derived new mathematical formulations for velocity and position update to realize discrete PSO. A fitness function for candidate solution evaluation has also been formulated. The line haul feeder vehicle routing problem with virtual depots has been presented in [15]. Feeder vehicle and virtual depot concepts have been introduced by the authors. Travel distance and waiting time for vehicles have been minimized using heuristic cost sharing methods. A patrol routing algorithm has been constructed in [16] for police, ambulance, and taxi services. The algorithm has been explored in terms of expression, execution, evaluation, and engagement. A domain specific language (DSL) turn has been used to express the algorithm. PatrolSim a custom simulator has been used for the execution of the algorithm. Response time, network coverage, and hotspot coverage metrics have been used for the evaluation of the algorithm. For a web based geographic information system (GIS) portal, CAPS Map has been used for end user engagement of the algorithm. Multidepot capacitated arc routing problem (MCARP) has been introduced in [17]. An evolutionary approach has been constructed by integrating some classical heuristics into a canonical evolutionary framework. The near optimum MCARP solution has been used to learn two distinct kinds of heuristic information. The evolutionary process has been guided by this heuristic information. An arc guided evolutionary algorithm for solving vehicle routing problem with time window has been developed in [18]. In the population, individuals have been represented using arcs so that evolution strategy can be adapted to the VRP-TW. The ruin and recreate principle have been used for mutation process. A trajectory local search algorithm has been developed to minimize distance. A route elimination procedure has been also suggested. Moreover, VRP has always been in the full attention of researchers.


## 3. Multiple-Objective Dynamic Vehicle Routing Problem (M-DVRP)

In this section, a different aspect of DVRP is identified by incorporating five objectives, namely, geographical ranking of requests, customer ranking, service time, expected reachability time, and satisfaction level of customers. The M-DVRP can be symbolically stated on a connected networkN
c
(
N
s
,
C
s
,
C
m
,
C
m
v
), where N
s
=
n
0
,
n
1
,
n
2
,
n
3
,
…
,
n
n indicates the set of nodes; C
s
=
{
(
n
i
,
n
j
)
,
n
i
,
n
j
∈
N
s and i
≠
j
} represents the set of connections, C
m
=
C
m
(
i
,
j
)
(
n
i
,
n
j
)
∈
C
s denotes communication cost matrix defined over C
s and matrix vector C
m
v
=
(
C
1
,
C
2
,
C
3
,
C
4
,
C
5
) is group of five objectives attached with each request. The DVRP in this consideration is nothing but finding a set of routes for a given set of vehicles such that it optimizes both C
m and C
m
v. In some of the earlier DVRP, strict time window has been considered for service time of the customers. Consequently, the customers provide their satisfaction values in binary digit, that is, 0 or 1 for each request. In other words, the customer either is fully satisfied or rejects the requested order in its totality [19]. But the binary digit satisfaction value consideration does not comply with real scenario. Inspired by the importance and continuous research in fuzzy set theory [20], the consideration of fuzzy time window is gaining momentum in VRP for complying with real customer scenario [21]. For developing a mathematical model for M-DVRP, a flexible time window is considered in which customers are ready to accept the delivery in relaxed time window. The other two important considerations of the problem are request vector and order vector. As soon as a customer enters in the system, he/she sends request information to the central depot via VANETs communication [22–29]. Each customer request is a vector of length six as illustrated in Figure 3. Once a request vector reaches the central depot system, an order vector is generated corresponding to the request vector. The order vector of length six considered in the problem is shown in Figure 4. The other considerations of M-DVRP are briefly described in following subsections.Figure 3
Customer request vector.Figure 4
Order vector for each of the customer requests.


### 3.1. Geographical Ranking

In M-DVRP, the geographical ranking of a request not only is dependent on distance of the customer from the central depot but also is an implicit complex function of four variables, namely, average density of request (ADR), distance (DIST), safety and reliability (SR), and road networks (RN). Thus, a vector of length four is associated with each request by central depot reflecting geographical ranking. The components of the geographical ranking vector and corresponding weighting parameters have been shown in Figure5. Considering α
i as weighting parameter and length of the vector v
GR, the constraint ∑
i
=
1
v
GR
α
i
=
1 always holds. The geographical ranking of a request can be calculated as
(1)
G
r
=
∑
i
=
1
4
α
i
r
i
v
GR
-
1
,
where r
i denotes the ranks and thus a request has been geographically ranked between 0 and 1.Figure 5
Geographical ranking of the request with weighing parameters.


### 3.2. Customer Ranking

In M-DVRP, the customers are categorized into four categories, namely, very important customer (VIC), important customer (IC), regular customer (RC), and casual customer (CC). A minimum guaranteed satisfactory level in the range[
0,1
] is defined for each of these categories of customers (cf. Figure 6). Based on the minimum guaranteed satisfaction level, service time window of the customers is also defined. The VIC has strict service time window due to highest satisfactory level that is 1. The minimum satisfactory level for IC is defined in the range [
0.75
,
1
). Although the IC also has smaller service time window but the system provides services in the maximum possible relaxable time window. Considering long run importance of RC, the minimum satisfactory level is defined in the range [
0.5
,
0.75
) for RC. The best possible service is provided in the flexible service time window. The lowest satisfactory level range [
0
,
0.5
) is defined for the CC considering their random entry and incredible request vector. Based on their doubtable credibility, the delivery of requests is processed on the way during servicing the other category of customers.Figure 6
Customer categorization, ranking, and guaranteed satisfaction level range.


### 3.3. Service Time

In M-DVRP, once the order of items reaches customer’s place, the time spent on delivering the items to the customers is known as service time(
ST
) of a request. The service time is defined by considering the quantity and type of items of the request. It is determined by the central depot on receipt of a request from the customers in real time fashion. The service time can be calculated as
(2)
ST
=
∑
i
=
1
N
item
q
i
I
i
S
i
r
,
where N
item denotes number of items, q
i is the quantity of i
th item, I
i is the type of i
th item, and S
i
r is the service rate of i
th item.


### 3.4. Expected Reachability Time

In M-DVRP, the average time required to reach a delivery vehicle from the central depot to the assigned customers is defined as expected reachability time(
ERT
). It depends on current geographical position of vehicle GP
curr
v, the geographical position of customer GP
c, average speed of vehicle s
avg
v, and weightage of geographical ranking GRwt. It can be calculated as
(3)
ERT
=
GP
curr
v
-
GP
c
s
avg
v
GR
wt
.


### 3.5. Satisfaction Level of Customers

The delivery of service up to the customer’s expectation is the notion of satisfaction level(
SL
) for a particular request. It is defined as a function with domain ERT and range [
0
,
1
]. It is expressed as
(4)
SL
ERT
=
0
,
ERT
<
PLDT
-
STIL
or
ERT
>
PUDT
+
STIU
1
,
PLDT
≪
ERT
≪
PUDT
ERT
-
(
PLDT
-
STIL
)
STIL
,
PLDT
-
STIL
<
ERT
PLDT
-
STIL
<
PLDT
PUDT
+
STIU
-
ERT
STIL
,
PUDT
<
ERT
PUDT
<
PUDT
+
STIU
.
After defining all the considered objective of the identified problem, the formulation of multiobjective function and corresponding constraints is briefly described below. There are four components in the multiobjective function, namely, number of vehicles or vehicle count N
v, expected reachability time, profit PF, and satisfaction level. The three constraints of the multiobjective function are vehicle, capacity, and reachability. The vehicle constraint states that only one vehicle can be assigned to a customer for a request. The capacity constraint states that each vehicle has prespecified capacity and this capacity could not be exceeded to deliver the request of customers. The reachability constraint states that the difference of ERT between two successive customers must be greater than or equal to the sum of service time of the previous customer and the travel time between the customers. For the multiobjective function, its components and constraints are expressed below
(5)
Max
⁡
f
1
-
1
,
f
2
-
1
f
3
,
f
4
,
where
(6)
f
1
=
N
v
,
f
2
=
∑
i
=
1
N
v
∑
j
=
1
N
c
∑
k
=
1
N
c
ERT
j
k
χ
j
k
i
,
f
3
=
∑
j
=
1
N
c
PF
j
,
f
4
=
∑
l
=
1
N
c
SL
ERT
l
·
CPF
l
wt
,
χ
j
k
i
=
1
,
i
th
vehicle
goes
from
j
th
customer
to
k
th
customer
0
,
otherwise
,
CPF
l
wt
=
GR
l
+
CR
l
Max
⁡
GR
i
j
+
CR
i
j
,
i
=
1,2
,
3
,
j
=
1,2
,
3,4
,
s
.
t
.
∑
i
=
1
N
v
∑
j
N
c
χ
j
k
i
=
1
,
k
=
1,2
,
3
,
…
,
N
c
,
∑
j
N
c
∑
k
N
c
χ
j
k
i
·
d
k
c
≪
c
h
,
i
=
1,2
,
3
,
…
,
N
v
,
χ
j
k
i
ERT
j
i
+
t
j
k
+
ST
r
≪
χ
j
k
i
·
ERT
j
i
,
r
=
1,2
,
3
,
…
,
N
c
,
i
=
1,2
,
3
,
…
,
N
v
,
where N
v denotes the number of vehicles and N
c represents the number of customers. The χ
j
k
i is the characteristic function and CPF
l
wt is the weight of preference of customer. For solving the above identified problem, time seed based solution using particle swarm optimization has been proposed and described in the next section.


## 3.1. Geographical Ranking

In M-DVRP, the geographical ranking of a request not only is dependent on distance of the customer from the central depot but also is an implicit complex function of four variables, namely, average density of request (ADR), distance (DIST), safety and reliability (SR), and road networks (RN). Thus, a vector of length four is associated with each request by central depot reflecting geographical ranking. The components of the geographical ranking vector and corresponding weighting parameters have been shown in Figure5. Considering α
i as weighting parameter and length of the vector v
GR, the constraint ∑
i
=
1
v
GR
α
i
=
1 always holds. The geographical ranking of a request can be calculated as
(1)
G
r
=
∑
i
=
1
4
α
i
r
i
v
GR
-
1
,
where r
i denotes the ranks and thus a request has been geographically ranked between 0 and 1.Figure 5
Geographical ranking of the request with weighing parameters.


## 3.2. Customer Ranking

In M-DVRP, the customers are categorized into four categories, namely, very important customer (VIC), important customer (IC), regular customer (RC), and casual customer (CC). A minimum guaranteed satisfactory level in the range[
0,1
] is defined for each of these categories of customers (cf. Figure 6). Based on the minimum guaranteed satisfaction level, service time window of the customers is also defined. The VIC has strict service time window due to highest satisfactory level that is 1. The minimum satisfactory level for IC is defined in the range [
0.75
,
1
). Although the IC also has smaller service time window but the system provides services in the maximum possible relaxable time window. Considering long run importance of RC, the minimum satisfactory level is defined in the range [
0.5
,
0.75
) for RC. The best possible service is provided in the flexible service time window. The lowest satisfactory level range [
0
,
0.5
) is defined for the CC considering their random entry and incredible request vector. Based on their doubtable credibility, the delivery of requests is processed on the way during servicing the other category of customers.Figure 6
Customer categorization, ranking, and guaranteed satisfaction level range.


## 3.3. Service Time

In M-DVRP, once the order of items reaches customer’s place, the time spent on delivering the items to the customers is known as service time(
ST
) of a request. The service time is defined by considering the quantity and type of items of the request. It is determined by the central depot on receipt of a request from the customers in real time fashion. The service time can be calculated as
(2)
ST
=
∑
i
=
1
N
item
q
i
I
i
S
i
r
,
where N
item denotes number of items, q
i is the quantity of i
th item, I
i is the type of i
th item, and S
i
r is the service rate of i
th item.


## 3.4. Expected Reachability Time

In M-DVRP, the average time required to reach a delivery vehicle from the central depot to the assigned customers is defined as expected reachability time(
ERT
). It depends on current geographical position of vehicle GP
curr
v, the geographical position of customer GP
c, average speed of vehicle s
avg
v, and weightage of geographical ranking GRwt. It can be calculated as
(3)
ERT
=
GP
curr
v
-
GP
c
s
avg
v
GR
wt
.


## 3.5. Satisfaction Level of Customers

The delivery of service up to the customer’s expectation is the notion of satisfaction level(
SL
) for a particular request. It is defined as a function with domain ERT and range [
0
,
1
]. It is expressed as
(4)
SL
ERT
=
0
,
ERT
<
PLDT
-
STIL
or
ERT
>
PUDT
+
STIU
1
,
PLDT
≪
ERT
≪
PUDT
ERT
-
(
PLDT
-
STIL
)
STIL
,
PLDT
-
STIL
<
ERT
PLDT
-
STIL
<
PLDT
PUDT
+
STIU
-
ERT
STIL
,
PUDT
<
ERT
PUDT
<
PUDT
+
STIU
.
After defining all the considered objective of the identified problem, the formulation of multiobjective function and corresponding constraints is briefly described below. There are four components in the multiobjective function, namely, number of vehicles or vehicle count N
v, expected reachability time, profit PF, and satisfaction level. The three constraints of the multiobjective function are vehicle, capacity, and reachability. The vehicle constraint states that only one vehicle can be assigned to a customer for a request. The capacity constraint states that each vehicle has prespecified capacity and this capacity could not be exceeded to deliver the request of customers. The reachability constraint states that the difference of ERT between two successive customers must be greater than or equal to the sum of service time of the previous customer and the travel time between the customers. For the multiobjective function, its components and constraints are expressed below
(5)
Max
⁡
f
1
-
1
,
f
2
-
1
f
3
,
f
4
,
where
(6)
f
1
=
N
v
,
f
2
=
∑
i
=
1
N
v
∑
j
=
1
N
c
∑
k
=
1
N
c
ERT
j
k
χ
j
k
i
,
f
3
=
∑
j
=
1
N
c
PF
j
,
f
4
=
∑
l
=
1
N
c
SL
ERT
l
·
CPF
l
wt
,
χ
j
k
i
=
1
,
i
th
vehicle
goes
from
j
th
customer
to
k
th
customer
0
,
otherwise
,
CPF
l
wt
=
GR
l
+
CR
l
Max
⁡
GR
i
j
+
CR
i
j
,
i
=
1,2
,
3
,
j
=
1,2
,
3,4
,
s
.
t
.
∑
i
=
1
N
v
∑
j
N
c
χ
j
k
i
=
1
,
k
=
1,2
,
3
,
…
,
N
c
,
∑
j
N
c
∑
k
N
c
χ
j
k
i
·
d
k
c
≪
c
h
,
i
=
1,2
,
3
,
…
,
N
v
,
χ
j
k
i
ERT
j
i
+
t
j
k
+
ST
r
≪
χ
j
k
i
·
ERT
j
i
,
r
=
1,2
,
3
,
…
,
N
c
,
i
=
1,2
,
3
,
…
,
N
v
,
where N
v denotes the number of vehicles and N
c represents the number of customers. The χ
j
k
i is the characteristic function and CPF
l
wt is the weight of preference of customer. For solving the above identified problem, time seed based solution using particle swarm optimization has been proposed and described in the next section.


## 4. TS-PSO for M-DVRP

The traditional particle swarm optimization (PSO) [30] has been generally used in solving optimization problem in continuous search space. But, a novel method set based particle swarm optimization (S-PSO) [31] has been suggested for solving combinatorial optimization problems in discrete search space. TS-PSO is inspired from the S-PSO. In TS-PSO, the identified problem M-DVRP is partitioned into number of smaller size DVRPs considering solution feasibility. Thereafter, the time horizon of each smaller size DVRP is divided into a number of smaller time seeds. The duration of time seeds in a particular DVRP depends on the degree of dynamism. Higher degree of dynamism in a DVRP requires smaller time seeds as compared to a DVRP with lower degree of dynamism. A solution for a smaller size DVRP is generated for each of the time seeds. The solutions of all the smaller size DVRPs are combined that represents the solution of the identified M-DVRP. The partitioning of the problem and division of time seeds is more specifically presented below
(7)
N
c
=
Connectioned
Component
of
smaller
DVRPs
N
k
c
,
k
=
1,2
,
3
,
…
,
n
and
time
horizon
of
k
th
smaller
size
DVRP
,
T
k
H
=
∑
i
=
1
N
TS
T
i
,
k
s
.
In TS-PSO, the search space is considered as set of all known and dynamically appearing connections C
s, in the given time seed of a particular partition of the problem. A particle in the search space also known as candidate solution is an ordered vector of connected connections from C
s with vehicle information. Initially we generate particles of some predefined length whose size can increase/decrease in successive time seeds to incorporate dynamic request of customers in efficient manner. The pictorial representation of initial structured of the vector, which has been found very useful in the construction of particles, is described in Figure 7. Initially, the vector has been filled up with fixed number of −1’s randomly. The vector has been kept open towards the right-end to indicate that it can grow in size in the successive time seeds. The total number of −1 in the vector represents the number of vehicles used in the solution. The ordinal numbering of customers in a solution vector or particle is based on initial order vectors calculated by central depot for each customer request vector accepted for a particular times seed in a smaller size DVRP. In Figure 8, a particle with 14 customers and 4 vehicles has been depicted. A vehicle is visiting the customers 3, 14, and 6 in order and returning to the depot represented by −1. Another vehicle is visiting 4, 8, 9, and 2 in order and returning to the depot. Similarly, the routes for other vehicle tours are shown. In successive iterations, particles are enhanced by incorporating new information from customers, vehicles, and order vectors. Due to these enhancements, the ordinal numbering of customers, number of customers handled by a particular vehicle, and number of vehicles in a particle may change.Figure 7
Initial structure of a particle.Figure 8
An instance of a particle in a time seed of a smaller size DVRP.The mathematical formulation of the proposed solution in terms of particle swarm optimization is given below. The formulas used for updating position and velocity of particles in the traditional particle swarm optimization have been expressed as(8)
V
i
′
=
ω
×
V
i
+
α
1
×
r
1
n
L
best
-
X
i
+
α
2
×
r
2
n
G
best
-
X
i
,
(9)
X
i
′
=
X
i
+
V
i
′
,
where ω denotes inertia weight, α
1 and α
2 are the acceleration coefficients that define the rate of impact of L
best and G
best, respectively, and r
1
n and r
2
n represent two random numbers in the range [
0
,
1
]. In TS-PSO, the above two mathematical formulations have been used for updating position and velocity of the particles. But each component operation of the two operations defined in (8) and (9) has been redefined in the framework of TS-PSO in the next subsections.


### 4.1. Position Representation of a Particle

In TS-PSO, position of a particle is a vector of ordered connections along with vehicle information. Actually, an instance of a particle represents the position of the particle. (cf. Figure8). The position vector of a particle is represented as
(10)
X
i
=
C
1
5,7
C
2
9,4
,
C
3
2,6
,
v
1
C
3
3,1
,
C
4
12,8
,
v
2
⋯
v
3
C
n
50,49
C
n
+
1
52,47
,
…
,
where C
i
l
,
m is the i
th connection between the customers l and m and v
j is the j
th vehicle used by the group of following customers.


### 4.2. Velocity Representation of a Particle

In TS-PSO, the velocity of a particle is a vector of connections associated with three inclusion probabilities. Each connection of the vector is associated with three inclusion probabilitiesP
ERT, P
PF, and P
SL. P
ERT
∈
0,1 is the insertion probability of a connection into solution giving importance to the expected reachability time. Similarly, P
PF
∈
[
0,1
] and P
SL
∈
[
0,1
] are insertion probability considering profit and satisfaction level. The velocity vector of a particle is expressed as
(11)
V
i
=
C
1
15,17
0.2,0.4,0.5
,
C
2
19,24
(
0.1,0.2,0.3
)
,
v
1
,
…
,
C
m
50,49
0.6,0.9,0.8
v
s
.


### 4.3. Velocity Updating of a Particle

As mentioned above, in TS-PSO, the velocity of a particle is updated using the traditional velocity updating equation (8). But the component operation is redefined in the framework of TS-PSO. The component operation ω
×
V
i changes the three probabilities attached to the connections of V
i. The component operation L
best
-
X
i or G
best
-
X
i represents connection set reduction operation and multiplication of coefficient into position; that is, α
1
×
r
1
n
L
best
-
X
i or α
2
×
r
2
n
G
best
-
X
i associates the three probabilities to each connection of the position. Each of these operations has been more clearly defined below
(12)
ω
×
V
i
=
[
C
j
l
,
m
P
ERT
′
,
P
PF
′
,
P
SL
′
∣
j
∈
C
s
,
l
,
m
∈
N
s
]
,
P
ERT
′
=
1
,
if
ω
×
P
ERT
>
1
ω
×
P
ERT
,
otherwise
,
P
PF
′
=
1
,
if
ω
×
P
PF
>
1
ω
×
P
PF
,
otherwise
,
P
SL
′
=
1
,
if
ω
×
P
SL
>
1
ω
×
P
SL
,
otherwise
,
X
i
-
X
j
=
C
x
l
,
m
v
t
∣
∀
v
t
∈
X
i
,
v
t
∈
X
j
,
C
x
l
,
m
∈
X
i
,
C
x
l
,
m
∉
X
j
,
α
1
or
2
×
r
1
or
2
n
X
i
=
[
C
j
l
,
m
P
ERT
,
P
PF
,
P
SL
∣
j
∈
X
i
,
l
,
m
∈
N
s
]
,
P
ERT
=
1
,
if
α
1
or
2
×
r
1
or
2
n
>
1
α
1
or
2
×
r
1
or
2
n
,
otherwise
,
P
PF
=
1
,
if
α
1
or
2
×
r
1
or
2
n
>
1
α
1
or
2
×
r
1
or
2
n
,
otherwise
,
P
SL
=
1
,
if
α
1
or
2
×
r
1
or
2
n
>
1
α
1
or
2
×
r
1
or
2
n
,
otherwise
.


### 4.4. Position Updating of a Particle

The position of a particle is updated using the traditional position updating equation (9). But the addition operation of the equation has been redefined in the framework of TS-PSO. The addition operation reconfigures all connections of the position X
i to generate a new position X
i
′. The reconfigured connection of X
i
′ is defined as
(13)
X
i
′
=
[
C
j
l
,
m
′
v
t
∣
∀
C
j
l
,
m
,
v
t
∈
X
i
]
,
m
′
=
p
,
if
C
j
l
,
p
∈
V
i
′
and
satisfies
ρ
i
q
,
if
C
j
l
,
q
∈
D
i
c
and
satisfies
ρ
i
m
,
otherwise
,
where ρ
i denotes the constraint set and D
i
c is the dynamic connection set for the i
th time seed. A complete algorithm for the proposed solution approach TS-PSO is presented in Algorithm 1.Algorithm 1:TS-PSO.
Notations:
N
c: Connected network graph;  N
v: Number of vehicles; N
sr
⁡: Number of static request; ST: Service time
CRV: Customer Request Vector; OV: Order vector; GR: Geographical Ranking; CRK: Customer ranking vector;
N
i
c: Number of customers in ith partition of network; N
dr
i: Number of dynamic request in ith partition of network;
X
g
best
(
G
): Global best position of Gth generation; X
i
l
best
(
G
): Local best position of ith particle in  Gth generation
T
k
H: Time horizon for kth sub-networks; T
i
,
k
S: ith time seed of the kth sub-network; ERT: Expected reachability time
X
α: Threshold solution used for stopping criteria. Input-
N
c
(
N
s
,
C
s
,
C
m
,
C
v
), N
v, N
sr
⁡, N
dr
i.Output-
X
g
best
G
Process-
(1)Initialize a connected network N
c
(
N
s
,
C
s
,
C
m
,
C
v
).
(2)for  i
=
1 to N
sr
⁡ // Generating CRV
(4)generate CRV (Q, PLDT, PUDT, STIL, STIU, ECPUT) randomly
(5)endfor
(6)for  i
=
1 to N
sr
⁡ // Generating OV
(7)generate GR vector (ADR, Dist., RN, SR) randomly and calculate Gr using (1)
(8)generate CRK vector (VIC, IC, RC, CC) randomly and assign weight according to ranks
(9)calculate ST using (2)
(10)calculate ERT using (3)
(11)endfor
(12)Partition  N
c
(
N
s
,
C
s
,
C
m
,
C
v
) into k sub-networks as N
c
=
⋃
i
=
1
k
N
i
c
(13)for  i
=
1 to k
(14)Divide  time horizon T
k
H into t time seeds as T
k
H
=
T
1
,
k
S
+
T
2
,
k
S
+
T
3
,
k
S
⋯
+
T
t
,
k
S
(15)for each time seed T
i
,
k
S
(16)N
dr
i
=
rand
(
0
-
N
c
i
)
(17)for  i
=
1 to N
dr
i // Generating Customer Request Vector for Dynamic Requests
(18)generate CRV (Q, PLDT, PUDT, STIL, STIU, ECPUT) randomly
(19)endfor
(20)for  i
=
1 to N
dr
i // Generating Customer Order Vector for Dynamic Requests
(21)generate GR vector (ADR, Dist., RN, SR) randomly and calculate Gr using (1)
(22)generate CRK vector (VIC, IC, RC, CC) and assign weight according to ranks
(23)calculate ST using (2)
(24)calculate ERT using (3)
(25)endfor
(26)
G
=
0
(27)
Generate  position X
j
(
G
) and velocity V
j
(
G
) for j
th particle in Gth generation from COV
(28)
while  X
g
best
G
-
X
g
best
G
-
1
<
X
α
do
(29)
G
=
G
+
1
(30)for each particle P
j
(
X
j
G, V
j
G
) of the search space
(31)evaluate fitness using objective function (5) as Fitt
P
j
X
j
G
,
V
j
G
(32)if  (Fitt
[
P
j
(
X
j
G, V
j
G
)
]
=
=
Fitt
[
P
j
(
X
j
G
-
1, V
j
G
-
1
)
])
(33)X
j
l
best
G
=
X
j
G
(34)endfor
(35)X
g
best
G
=
X
1
l
best
G
(36)for  j
=
2 to number of particles in the swarm
(37)if  (
Fitt
[
P
j
(
X
j
l
best
G, V
j
G
)
]
>
Fitt
[
P
m
(
X
g
best
G, V
m
G
)
]
)
(38)X
g
best
G
=
X
j
l
best
G
(39)endfor
(40)
endwhile
(41)store  X
g
best
G for ith time seed
(42)endfor
(43)store  the set ofX
g
best
G for kth partition
(44)endfor


## 4.1. Position Representation of a Particle

In TS-PSO, position of a particle is a vector of ordered connections along with vehicle information. Actually, an instance of a particle represents the position of the particle. (cf. Figure8). The position vector of a particle is represented as
(10)
X
i
=
C
1
5,7
C
2
9,4
,
C
3
2,6
,
v
1
C
3
3,1
,
C
4
12,8
,
v
2
⋯
v
3
C
n
50,49
C
n
+
1
52,47
,
…
,
where C
i
l
,
m is the i
th connection between the customers l and m and v
j is the j
th vehicle used by the group of following customers.


## 4.2. Velocity Representation of a Particle

In TS-PSO, the velocity of a particle is a vector of connections associated with three inclusion probabilities. Each connection of the vector is associated with three inclusion probabilitiesP
ERT, P
PF, and P
SL. P
ERT
∈
0,1 is the insertion probability of a connection into solution giving importance to the expected reachability time. Similarly, P
PF
∈
[
0,1
] and P
SL
∈
[
0,1
] are insertion probability considering profit and satisfaction level. The velocity vector of a particle is expressed as
(11)
V
i
=
C
1
15,17
0.2,0.4,0.5
,
C
2
19,24
(
0.1,0.2,0.3
)
,
v
1
,
…
,
C
m
50,49
0.6,0.9,0.8
v
s
.


## 4.3. Velocity Updating of a Particle

As mentioned above, in TS-PSO, the velocity of a particle is updated using the traditional velocity updating equation (8). But the component operation is redefined in the framework of TS-PSO. The component operation ω
×
V
i changes the three probabilities attached to the connections of V
i. The component operation L
best
-
X
i or G
best
-
X
i represents connection set reduction operation and multiplication of coefficient into position; that is, α
1
×
r
1
n
L
best
-
X
i or α
2
×
r
2
n
G
best
-
X
i associates the three probabilities to each connection of the position. Each of these operations has been more clearly defined below
(12)
ω
×
V
i
=
[
C
j
l
,
m
P
ERT
′
,
P
PF
′
,
P
SL
′
∣
j
∈
C
s
,
l
,
m
∈
N
s
]
,
P
ERT
′
=
1
,
if
ω
×
P
ERT
>
1
ω
×
P
ERT
,
otherwise
,
P
PF
′
=
1
,
if
ω
×
P
PF
>
1
ω
×
P
PF
,
otherwise
,
P
SL
′
=
1
,
if
ω
×
P
SL
>
1
ω
×
P
SL
,
otherwise
,
X
i
-
X
j
=
C
x
l
,
m
v
t
∣
∀
v
t
∈
X
i
,
v
t
∈
X
j
,
C
x
l
,
m
∈
X
i
,
C
x
l
,
m
∉
X
j
,
α
1
or
2
×
r
1
or
2
n
X
i
=
[
C
j
l
,
m
P
ERT
,
P
PF
,
P
SL
∣
j
∈
X
i
,
l
,
m
∈
N
s
]
,
P
ERT
=
1
,
if
α
1
or
2
×
r
1
or
2
n
>
1
α
1
or
2
×
r
1
or
2
n
,
otherwise
,
P
PF
=
1
,
if
α
1
or
2
×
r
1
or
2
n
>
1
α
1
or
2
×
r
1
or
2
n
,
otherwise
,
P
SL
=
1
,
if
α
1
or
2
×
r
1
or
2
n
>
1
α
1
or
2
×
r
1
or
2
n
,
otherwise
.


## 4.4. Position Updating of a Particle

The position of a particle is updated using the traditional position updating equation (9). But the addition operation of the equation has been redefined in the framework of TS-PSO. The addition operation reconfigures all connections of the position X
i to generate a new position X
i
′. The reconfigured connection of X
i
′ is defined as
(13)
X
i
′
=
[
C
j
l
,
m
′
v
t
∣
∀
C
j
l
,
m
,
v
t
∈
X
i
]
,
m
′
=
p
,
if
C
j
l
,
p
∈
V
i
′
and
satisfies
ρ
i
q
,
if
C
j
l
,
q
∈
D
i
c
and
satisfies
ρ
i
m
,
otherwise
,
where ρ
i denotes the constraint set and D
i
c is the dynamic connection set for the i
th time seed. A complete algorithm for the proposed solution approach TS-PSO is presented in Algorithm 1.Algorithm 1:TS-PSO.
Notations:
N
c: Connected network graph;  N
v: Number of vehicles; N
sr
⁡: Number of static request; ST: Service time
CRV: Customer Request Vector; OV: Order vector; GR: Geographical Ranking; CRK: Customer ranking vector;
N
i
c: Number of customers in ith partition of network; N
dr
i: Number of dynamic request in ith partition of network;
X
g
best
(
G
): Global best position of Gth generation; X
i
l
best
(
G
): Local best position of ith particle in  Gth generation
T
k
H: Time horizon for kth sub-networks; T
i
,
k
S: ith time seed of the kth sub-network; ERT: Expected reachability time
X
α: Threshold solution used for stopping criteria. Input-
N
c
(
N
s
,
C
s
,
C
m
,
C
v
), N
v, N
sr
⁡, N
dr
i.Output-
X
g
best
G
Process-
(1)Initialize a connected network N
c
(
N
s
,
C
s
,
C
m
,
C
v
).
(2)for  i
=
1 to N
sr
⁡ // Generating CRV
(4)generate CRV (Q, PLDT, PUDT, STIL, STIU, ECPUT) randomly
(5)endfor
(6)for  i
=
1 to N
sr
⁡ // Generating OV
(7)generate GR vector (ADR, Dist., RN, SR) randomly and calculate Gr using (1)
(8)generate CRK vector (VIC, IC, RC, CC) randomly and assign weight according to ranks
(9)calculate ST using (2)
(10)calculate ERT using (3)
(11)endfor
(12)Partition  N
c
(
N
s
,
C
s
,
C
m
,
C
v
) into k sub-networks as N
c
=
⋃
i
=
1
k
N
i
c
(13)for  i
=
1 to k
(14)Divide  time horizon T
k
H into t time seeds as T
k
H
=
T
1
,
k
S
+
T
2
,
k
S
+
T
3
,
k
S
⋯
+
T
t
,
k
S
(15)for each time seed T
i
,
k
S
(16)N
dr
i
=
rand
(
0
-
N
c
i
)
(17)for  i
=
1 to N
dr
i // Generating Customer Request Vector for Dynamic Requests
(18)generate CRV (Q, PLDT, PUDT, STIL, STIU, ECPUT) randomly
(19)endfor
(20)for  i
=
1 to N
dr
i // Generating Customer Order Vector for Dynamic Requests
(21)generate GR vector (ADR, Dist., RN, SR) randomly and calculate Gr using (1)
(22)generate CRK vector (VIC, IC, RC, CC) and assign weight according to ranks
(23)calculate ST using (2)
(24)calculate ERT using (3)
(25)endfor
(26)
G
=
0
(27)
Generate  position X
j
(
G
) and velocity V
j
(
G
) for j
th particle in Gth generation from COV
(28)
while  X
g
best
G
-
X
g
best
G
-
1
<
X
α
do
(29)
G
=
G
+
1
(30)for each particle P
j
(
X
j
G, V
j
G
) of the search space
(31)evaluate fitness using objective function (5) as Fitt
P
j
X
j
G
,
V
j
G
(32)if  (Fitt
[
P
j
(
X
j
G, V
j
G
)
]
=
=
Fitt
[
P
j
(
X
j
G
-
1, V
j
G
-
1
)
])
(33)X
j
l
best
G
=
X
j
G
(34)endfor
(35)X
g
best
G
=
X
1
l
best
G
(36)for  j
=
2 to number of particles in the swarm
(37)if  (
Fitt
[
P
j
(
X
j
l
best
G, V
j
G
)
]
>
Fitt
[
P
m
(
X
g
best
G, V
m
G
)
]
)
(38)X
g
best
G
=
X
j
l
best
G
(39)endfor
(40)
endwhile
(41)store  X
g
best
G for ith time seed
(42)endfor
(43)store  the set ofX
g
best
G for kth partition
(44)endfor


## 5. Simulation and Analysis of Results

In this section extensive simulations have been performed to analyze the optimization accuracy of the proposed solution TS-PSO in solving the identified problem M-DVRP. The four objectives considered for optimization accuracy assessment are vehicle count, expected reachability time, profit, and satisfaction level. The simulation results have been compared with that of genetic algorithm (GA) based solution.


### 5.1. Simulation Environment and Methodology

Network simulator ns-2.34 has been used in the simulation of TS-PSO algorithm. The realistic mobility model and realistic urban traffic environment have been generated using mobility model generator for vehicular networks (MOVE) [32]. An open-source micro-traffic simulator known as simulation of urban mobility (SUMO) has been used to develop MOVE [33]. Most of the necessary scenario of urban traffic environment such as roads, lanes in each road, number of flows in each lane, junctions, traffic lights in a particular junction, vehicle speed, left or right turning probability of a vehicle at a particular point, and static nodes as customers has been set up through two main modules of MOVE, namely, road map editor and vehicle movement editor. The mobility trace generated by MOVE with the help of SUMO has been directly used in ns-2. The performance of TS-PSO has been tested using the fifteen data sets, namely, OPK-
01
,
OPK-
02
,
…
,
OPK-
15 generated by considering realistic vehicular traffic environment and highly dynamic customer requirements. These datasets have been generated using real traffic data of California Vehicle Activity Database (CalVAD) [34] and US Department of Transportation [35] which can be downloaded from the website “Wireless Communication Research Lab” [36]. The reason behind generating the data sets is that a lot of dynamic features such as geographical ranking, customer ranking, expected reachability time, satisfaction level, and dynamic traffic hazards have been considered in the proposed solution TS-PSO that could not be tested with the existing VRP or modified-VRP data sets. To realize the twenty-three hours’ time horizon between 6 AM and 5 AM in the next morning, in the simulation, twenty- three-minute time horizon has been considered in the closed interval [
0
,
1380
] seconds. The other important simulation parameter is summarized in Table 2. After setting the network and traffic flow with the above discussed parameters, the simulation has been performed using the different data sets. The complete simulation process has been summarized in Figure 9. The satellite image of New Delhi, India (cf. Figure 10), has been obtained via Google Earth and it is imported in ArcGIS 10.2.2 for the coordinate assignments. The data set containing customer, vehicle, route, and connection information has been given input to MOVE that generates New Delhi Map with network information. Thereafter, configuration and trace file have been generated and ultimately vehicular traffic flow in the New Delhi Map has been produced. TS-PSO has been implemented in ns-2 using the trace file generated through MOVE.Table 2
Simulation parameters.
Parameters
Values
Simulation area
1500
×
1000 m2
Simulation time
1380 s
Number of vehicles
28–115
Vehicle speed
1.4–16.7 m/s
Transmission range
250 m
Packet senders
30
Traffic type
CBR
Packet size
512 bytes
Packet type
UDP
Ifqlen
50
CBR rate
6 packets/s
Channel type
Wireless
Propagation model
Shadowing
Antenna model
Omnidirectional
MAC protocol
IEEE 802.11p
MAC data rate
5 Mbps
Query period
3 s
Hello time-out
1 s
Frequency
5.9 GHz
Routing protocols
P-GEDIRFigure 9
Work flow diagram of the simulation process.Figure 10
The satellite image of New Delhi, India, via Google Earth.


### 5.2. Result Analysis

In this analysis, we have considered whether the Pareto based solution generated by the proposed algorithm TS-PSO covers the solution achieved by GA considering only one objective function while keeping others as constant. The comparison results between TS-PSO and GA have been depicted in Table3.Table 3
Simulation results.
Data set
Functions
TS-PSO
Randomized solution
N
v
GA
=
N
v
TS-PSO
N
v
GA
=
1.5
N
v
TS-PSO
N
v
GA
=
1.8
N
v
TS-PSO
N
v
GA
=
2
N
v
TS-PSO
OPK-01
f
1
-
1
0.0357
0.0357
0.0238
0.0198
0.0179
f
2
-
1
0.0008
0.0007
0.0007
0.0007
0.0008
f
3
86U
8U
13U
16U
21U
f
4
0.665
0.195
0.237
0.264
0.289
OPK-02
f
1
-
1
0.0244
0.0244
0.0163
0.0136
0.0122
f
2
-
1
0.0009
0.0007
0.0007
0.0007
0.0008
f
3
105U
19U
25U
30U
35U
f
4
0.713
0.234
0.284
0.301
0.325
OPK-03
f
1
-
1
0.0179
0.0179
0.0119
0.0099
0.0089
f
2
-
1
0.0012
0.0008
0.0009
0.0009
0.0011
f
3
137U
36U
44U
48U
52U
f
4
0.742
0.306
0.368
0.397
0.437
OPK-04
f
1
-
1
0.0167
0.0167
0.0111
0.0093
0.0083
f
2
-
1
0.0013
0.0008
0.0009
0.0010
0.0012
f
3
149U
41U
48U
53U
56U
f
4
0.752
0.342
0.395
0.425
0.456
OPK-05
f
1
-
1
0.0154
0.0154
0.0103
0.0085
0.0077
f
2
-
1
0.0014
0.0008
0.0010
0.0011
0.0013
f
3
162U
47U
55U
58U
62U
f
4
0.764
0.368
0.426
0.453
0.483
OPK-06
f
1
-
1
0.0143
0.0143
0.0095
0.0079
0.0071
f
2
-
1
0.0015
0.0008
0.0011
0.0012
0.0014
f
3
178U
53U
61U
64U
68U
f
4
0.773
0.417
0.443
0.478
0.501
OPK-07
f
1
-
1
0.0133
0.0133
0.0089
0.0074
0.0067
f
2
-
1
0.0016
0.0009
0.0012
0.0014
0.0016
f
3
196U
61U
66U
69U
72U
f
4
0.782
0.436
0.471
0.492
0.532
OPK-08
f
1
-
1
0.0125
0.0125
0.0083
0.0069
0.0063
f
2
-
1
0.0018
0.0009
0.0013
0.0015
0.0017
f
3
207U
68U
70U
73U
76U
f
4
0.795
0.465
0.490
0.520
0.554
OPK-09
f
1
-
1
0.0118
0.0118
0.0078
0.0065
0.0059
f
2
-
1
0.0020
0.0009
0.0015
0.0018
0.0020
f
3
219U
77U
76U
79U
83U
f
4
0.807
0.483
0.514
0.542
0.568
OPK-10
f
1
-
1
0.0111
0.0111
0.0074
0.0062
0.0056
f
2
-
1
0.0024
0.0009
0.0017
0.0021
0.0023
f
3
239U
83U
81U
84U
87U
f
4
0.812
0.516
0.532
0.571
0.595
OPK-11
f
1
-
1
0.0105
0.0105
0.0070
0.0058
0.0053
f
2
-
1
0.0027
0.0010
0.0019
0.0025
0.0026
f
3
253U
89U
87U
90U
92U
f
4
0.823
0.542
0.563
0.594
0.617
OPK-12
f
1
-
1
0.0100
0.0100
0.0067
0.0056
0.0050
f
2
-
1
0.0033
0.0010
0.0022
0.0030
0.0031
f
3
269U
96U
91U
95U
98U
f
4
0.831
0.589
0.601
0.637
0.650
OPK-13
f
1
-
1
0.0095
0.0095
0.0063
0.0053
0.0048
f
2
-
1
0.0041
0.0010
0.0026
0.0037
0.0039
f
3
204U
73U
69U
64U
56U
f
4
0.844
0.593
0.627
0.650
0.674
OPK-14
f
1
-
1
0.0091
0.0091
0.0060
0.0051
0.0045
f
2
-
1
0.0054
0.0011
0.0031
0.0050
0.0051
f
3
183U
69U
62U
53U
49U
f
4
0.856
0.618
0.649
0.663
0.685
OPK-15
f
1
-
1
0.0087
0.0087
0.0058
0.0048
0.0043
f
2
-
1
0.0076
0.0011
0.0039
0.0065
0.0071
f
3
172U
64U
57U
48U
41U
f
4
0.862
0.631
0.672
0.691
0.721The results depicted in Table2 show that the solution provided by the proposed algorithm is found to be competitive enough as compared to the solution provided by the genetic algorithm. It is also noteworthy that our algorithm considers all the objective functions of M-DVRP model concurrently whereas single objective has been considered in genetic algorithms. Additionally in GA solution, by increasing number of vehicles two times N
v
GA
=
2
N
v
TS-PSO as compared to TS-PSO, the solutions provided by GA come close to the proposed solution in terms of SL but the profit earned by the TS-PSO is far better than what is offered by GA solution. To closely analyze the performance of TS-PSO in optimizing the functions f
2
-
1, f
3, and f
4, the following results have been obtained.The results in Figure11(a) show the comparison of optimization of function f
2
-
1, that is, ERT between TS-PSO and GA solutions. It can be clearly observed that the proposed solution optimizes the function far better than that of the compared GA solutions considering equal vehicle count. This can be attributed to the fact that the geographical ranking of requests in the proposed solution results in better ERT. The optimization accuracy of GA in terms of ERT improves with increasing vehicle count in the solution as N
v
R
=
N
v
SDP, N
v
R
=
1.5
N
v
SDP, N
v
R
=
1.8
N
v
SDP, and N
v
R
=
2
N
v
SDP due to easy availability of vehicles for individual customers. Thus, TS-PSO uses lesser number of vehicles while reducing ERT as compared to GA solutions. The results of comparison of optimization accuracy for function f
3, that is, PF between TS-PSO and GA solutions, have been depicted in Figure 11(b). It clearly reveals that the TS-PSO more effectively maximizes the PF as compared to GA solutions. This is due to the effective customer ranking in the proposed solution. It is also noteworthy that increasing the vehicle count beyond a particular optimized point deteriorates the PF earned by the solution. The optimization accuracy of f
4, that is, SL between the proposed solution and GA, has been compared in the results shown in Figure 11(c). The results confirm that the maximization of SL by the proposed solution is significantly higher than the compared GA solutions. This is due to the consideration of CPF
l
wt in the proposed solution. Moreover, the maximization of SL increases with increasing vehicle count for both the solution approaches. But the difference in maximization of SL between the proposed solution and GA is clearly visible in the results.The optimization performance of TS-PSO in optimizing (a)f
2
-
1, (b) f
3, and (c) f
4.
(a)
(b)
(c)


## 5.1. Simulation Environment and Methodology

Network simulator ns-2.34 has been used in the simulation of TS-PSO algorithm. The realistic mobility model and realistic urban traffic environment have been generated using mobility model generator for vehicular networks (MOVE) [32]. An open-source micro-traffic simulator known as simulation of urban mobility (SUMO) has been used to develop MOVE [33]. Most of the necessary scenario of urban traffic environment such as roads, lanes in each road, number of flows in each lane, junctions, traffic lights in a particular junction, vehicle speed, left or right turning probability of a vehicle at a particular point, and static nodes as customers has been set up through two main modules of MOVE, namely, road map editor and vehicle movement editor. The mobility trace generated by MOVE with the help of SUMO has been directly used in ns-2. The performance of TS-PSO has been tested using the fifteen data sets, namely, OPK-
01
,
OPK-
02
,
…
,
OPK-
15 generated by considering realistic vehicular traffic environment and highly dynamic customer requirements. These datasets have been generated using real traffic data of California Vehicle Activity Database (CalVAD) [34] and US Department of Transportation [35] which can be downloaded from the website “Wireless Communication Research Lab” [36]. The reason behind generating the data sets is that a lot of dynamic features such as geographical ranking, customer ranking, expected reachability time, satisfaction level, and dynamic traffic hazards have been considered in the proposed solution TS-PSO that could not be tested with the existing VRP or modified-VRP data sets. To realize the twenty-three hours’ time horizon between 6 AM and 5 AM in the next morning, in the simulation, twenty- three-minute time horizon has been considered in the closed interval [
0
,
1380
] seconds. The other important simulation parameter is summarized in Table 2. After setting the network and traffic flow with the above discussed parameters, the simulation has been performed using the different data sets. The complete simulation process has been summarized in Figure 9. The satellite image of New Delhi, India (cf. Figure 10), has been obtained via Google Earth and it is imported in ArcGIS 10.2.2 for the coordinate assignments. The data set containing customer, vehicle, route, and connection information has been given input to MOVE that generates New Delhi Map with network information. Thereafter, configuration and trace file have been generated and ultimately vehicular traffic flow in the New Delhi Map has been produced. TS-PSO has been implemented in ns-2 using the trace file generated through MOVE.Table 2
Simulation parameters.
Parameters
Values
Simulation area
1500
×
1000 m2
Simulation time
1380 s
Number of vehicles
28–115
Vehicle speed
1.4–16.7 m/s
Transmission range
250 m
Packet senders
30
Traffic type
CBR
Packet size
512 bytes
Packet type
UDP
Ifqlen
50
CBR rate
6 packets/s
Channel type
Wireless
Propagation model
Shadowing
Antenna model
Omnidirectional
MAC protocol
IEEE 802.11p
MAC data rate
5 Mbps
Query period
3 s
Hello time-out
1 s
Frequency
5.9 GHz
Routing protocols
P-GEDIRFigure 9
Work flow diagram of the simulation process.Figure 10
The satellite image of New Delhi, India, via Google Earth.


## 5.2. Result Analysis

In this analysis, we have considered whether the Pareto based solution generated by the proposed algorithm TS-PSO covers the solution achieved by GA considering only one objective function while keeping others as constant. The comparison results between TS-PSO and GA have been depicted in Table3.Table 3
Simulation results.
Data set
Functions
TS-PSO
Randomized solution
N
v
GA
=
N
v
TS-PSO
N
v
GA
=
1.5
N
v
TS-PSO
N
v
GA
=
1.8
N
v
TS-PSO
N
v
GA
=
2
N
v
TS-PSO
OPK-01
f
1
-
1
0.0357
0.0357
0.0238
0.0198
0.0179
f
2
-
1
0.0008
0.0007
0.0007
0.0007
0.0008
f
3
86U
8U
13U
16U
21U
f
4
0.665
0.195
0.237
0.264
0.289
OPK-02
f
1
-
1
0.0244
0.0244
0.0163
0.0136
0.0122
f
2
-
1
0.0009
0.0007
0.0007
0.0007
0.0008
f
3
105U
19U
25U
30U
35U
f
4
0.713
0.234
0.284
0.301
0.325
OPK-03
f
1
-
1
0.0179
0.0179
0.0119
0.0099
0.0089
f
2
-
1
0.0012
0.0008
0.0009
0.0009
0.0011
f
3
137U
36U
44U
48U
52U
f
4
0.742
0.306
0.368
0.397
0.437
OPK-04
f
1
-
1
0.0167
0.0167
0.0111
0.0093
0.0083
f
2
-
1
0.0013
0.0008
0.0009
0.0010
0.0012
f
3
149U
41U
48U
53U
56U
f
4
0.752
0.342
0.395
0.425
0.456
OPK-05
f
1
-
1
0.0154
0.0154
0.0103
0.0085
0.0077
f
2
-
1
0.0014
0.0008
0.0010
0.0011
0.0013
f
3
162U
47U
55U
58U
62U
f
4
0.764
0.368
0.426
0.453
0.483
OPK-06
f
1
-
1
0.0143
0.0143
0.0095
0.0079
0.0071
f
2
-
1
0.0015
0.0008
0.0011
0.0012
0.0014
f
3
178U
53U
61U
64U
68U
f
4
0.773
0.417
0.443
0.478
0.501
OPK-07
f
1
-
1
0.0133
0.0133
0.0089
0.0074
0.0067
f
2
-
1
0.0016
0.0009
0.0012
0.0014
0.0016
f
3
196U
61U
66U
69U
72U
f
4
0.782
0.436
0.471
0.492
0.532
OPK-08
f
1
-
1
0.0125
0.0125
0.0083
0.0069
0.0063
f
2
-
1
0.0018
0.0009
0.0013
0.0015
0.0017
f
3
207U
68U
70U
73U
76U
f
4
0.795
0.465
0.490
0.520
0.554
OPK-09
f
1
-
1
0.0118
0.0118
0.0078
0.0065
0.0059
f
2
-
1
0.0020
0.0009
0.0015
0.0018
0.0020
f
3
219U
77U
76U
79U
83U
f
4
0.807
0.483
0.514
0.542
0.568
OPK-10
f
1
-
1
0.0111
0.0111
0.0074
0.0062
0.0056
f
2
-
1
0.0024
0.0009
0.0017
0.0021
0.0023
f
3
239U
83U
81U
84U
87U
f
4
0.812
0.516
0.532
0.571
0.595
OPK-11
f
1
-
1
0.0105
0.0105
0.0070
0.0058
0.0053
f
2
-
1
0.0027
0.0010
0.0019
0.0025
0.0026
f
3
253U
89U
87U
90U
92U
f
4
0.823
0.542
0.563
0.594
0.617
OPK-12
f
1
-
1
0.0100
0.0100
0.0067
0.0056
0.0050
f
2
-
1
0.0033
0.0010
0.0022
0.0030
0.0031
f
3
269U
96U
91U
95U
98U
f
4
0.831
0.589
0.601
0.637
0.650
OPK-13
f
1
-
1
0.0095
0.0095
0.0063
0.0053
0.0048
f
2
-
1
0.0041
0.0010
0.0026
0.0037
0.0039
f
3
204U
73U
69U
64U
56U
f
4
0.844
0.593
0.627
0.650
0.674
OPK-14
f
1
-
1
0.0091
0.0091
0.0060
0.0051
0.0045
f
2
-
1
0.0054
0.0011
0.0031
0.0050
0.0051
f
3
183U
69U
62U
53U
49U
f
4
0.856
0.618
0.649
0.663
0.685
OPK-15
f
1
-
1
0.0087
0.0087
0.0058
0.0048
0.0043
f
2
-
1
0.0076
0.0011
0.0039
0.0065
0.0071
f
3
172U
64U
57U
48U
41U
f
4
0.862
0.631
0.672
0.691
0.721The results depicted in Table2 show that the solution provided by the proposed algorithm is found to be competitive enough as compared to the solution provided by the genetic algorithm. It is also noteworthy that our algorithm considers all the objective functions of M-DVRP model concurrently whereas single objective has been considered in genetic algorithms. Additionally in GA solution, by increasing number of vehicles two times N
v
GA
=
2
N
v
TS-PSO as compared to TS-PSO, the solutions provided by GA come close to the proposed solution in terms of SL but the profit earned by the TS-PSO is far better than what is offered by GA solution. To closely analyze the performance of TS-PSO in optimizing the functions f
2
-
1, f
3, and f
4, the following results have been obtained.The results in Figure11(a) show the comparison of optimization of function f
2
-
1, that is, ERT between TS-PSO and GA solutions. It can be clearly observed that the proposed solution optimizes the function far better than that of the compared GA solutions considering equal vehicle count. This can be attributed to the fact that the geographical ranking of requests in the proposed solution results in better ERT. The optimization accuracy of GA in terms of ERT improves with increasing vehicle count in the solution as N
v
R
=
N
v
SDP, N
v
R
=
1.5
N
v
SDP, N
v
R
=
1.8
N
v
SDP, and N
v
R
=
2
N
v
SDP due to easy availability of vehicles for individual customers. Thus, TS-PSO uses lesser number of vehicles while reducing ERT as compared to GA solutions. The results of comparison of optimization accuracy for function f
3, that is, PF between TS-PSO and GA solutions, have been depicted in Figure 11(b). It clearly reveals that the TS-PSO more effectively maximizes the PF as compared to GA solutions. This is due to the effective customer ranking in the proposed solution. It is also noteworthy that increasing the vehicle count beyond a particular optimized point deteriorates the PF earned by the solution. The optimization accuracy of f
4, that is, SL between the proposed solution and GA, has been compared in the results shown in Figure 11(c). The results confirm that the maximization of SL by the proposed solution is significantly higher than the compared GA solutions. This is due to the consideration of CPF
l
wt in the proposed solution. Moreover, the maximization of SL increases with increasing vehicle count for both the solution approaches. But the difference in maximization of SL between the proposed solution and GA is clearly visible in the results.The optimization performance of TS-PSO in optimizing (a)f
2
-
1, (b) f
3, and (c) f
4.
(a)
(b)
(c)


## 6. Conclusion

In this paper, a novel variation of DVRP has been identified by incorporating multiple objectives such as geographical ranking, customer ranking, service time, expected reachability time, and satisfaction level. The identified DVRP is called multiobjective dynamic vehicle routing problem (M-DVRP). A time seed based solution using particle swarm optimization (TS-PSO) for the identified problem has been proposed. The proposed solution could be useful in the framework of various dynamic vehicle routing problems of real environments such as logistics, courier, and E-commerce because the M-DVRP has more realistic assumptions about the real environment. It effectively optimizes the considered parameters of the problem, for example, vehicle count, expected reachability time, profit, and satisfaction level. The optimization of expected reachability time by TS-PSO is far better than what is obtained from GA solution. It should also be noted that TS-PSO uses less vehicles. The optimization of profit by TS-PSO is almost three times better than what is obtained in case of GA approach. The satisfaction level has been effectively optimized by TS-PSO. In future research, authors will explore evolutionary multiobjective optimization (EMO) for solving M-DVRP.



---

*Source: 189832-2015-02-02.xml*