Expert Systems With Applications: G. Poonthalir, R. Nadarajan
Expert Systems With Applications: G. Poonthalir, R. Nadarajan
Expert Systems With Applications: G. Poonthalir, R. Nadarajan
a r t i c l e i n f o a b s t r a c t
Article history: A bi-objective Fuel efficient Green Vehicle Routing Problem (F-GVRP) with varying speed constraint is
Received 13 September 2017 discussed in this paper as an extension of Green Vehicle Routing Problem (G-VRP). F-GVRP is modelled
Revised 29 January 2018
to minimize both route cost and fuel consumption using goal programming. The problem is solved using
Accepted 30 January 2018
Particle Swarm Optimization with Greedy Mutation Operator and Time varying acceleration coefficient
(TVa-PSOGMO). The objective of this paper is to study the behaviour of F-GVRP under varying speed
Keywords: environment and its impact on the route cost and fuel consumption. Experiments are conducted with
Green Vehicle Routing Problem constant and varying speed constraints and it is observed that better routing plan with minimum fuel
Bi-objective optimization consumption can be achieved under varying speed environment.
Particle Swarm Optimization
© 2018 Elsevier Ltd. All rights reserved.
https://doi.org/10.1016/j.eswa.2018.01.052
0957-4174/© 2018 Elsevier Ltd. All rights reserved.
132 G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144
variants on VRP exist, this literature reviews various models on that gives solution to the problem. When vehicle equipped with
green VRP. artificial fuel need to take long distance tour, it has to halt for refu-
Literature on vehicle routing problems that halts for refuelling elling in alternate fuelling station. When AFS are limited, a vehicle
at fuel stations or recharging their batteries at re-charging sta- has to take up a route forcefully to refuel in the limited number of
tions are limited in comparison with other traditional variants. AFS which can increase the route cost. This problem can be tack-
VRP with a limitation on the capacity of vehicle was addressed led if vehicle can switch between battery and fuel depending on
by Bard, Huang, Jaillet, and Dror (1998) where the vehicle stops the requirements as proposed by Mancini (2017) in hybrid VRP. An
at satellite facilities to reload their capacity and continue the tour. MILP formulation of the problem is carried out and is solved using
Erdogan and Miller Hooks (2012) formulated a Green Vehicle Rout- a large neighbourhood search based matheuristic.
ing Problem (G-VRP) where the refuelling stations are modelled VRP that concentrates in minimizing GHG emission and their
with environment friendly fuel like biogas and the vehicle halts modelling is also discussed under Green VRP in literature. A fuel
for re fuelling with the idea conceived from Bard et al. (1998). emission minimization model that concentrated in reducing emis-
They solved the problem using Density Based Clustering Algo- sion for solid waste collection trucks was done by Apaydin and
rithm (DBCA) and Modified Clarke and Wright Savings (MCWS) Gonullu (2008). Emission minimization VRP was proposed by
algorithm. Schneider, Stenger, and Goeke (2014) extended G-VRP Figliozzi (2010) that concentrated in routing vehicles with less
and discussed Electric Vehicle Routing Problem with Time Win- emission where emission minimization is taken as an additional
dows (E-VRPTW) and recharging stations. They solved the prob- objective. Bektas and Laporte (2011) developed a Pollution Rout-
lem using Tabu search with variable neighbourhood algorithm and ing Problem (PRP) which is an extension of VRPTW that considers
got better results than Erdogan and Miller Hooks (2012). Later, both load and speed as major factors in emission and proposed a
Schneider, Stenger, and Hof (2015) developed Vehicle Routing Prob- non linear mixed integer programming model to solve the prob-
lem with Intermediate Stops (VRP-IS) and solved the problem us- lem. Later, Demir, Bektaş, and Laporte (2012) solved the PRP using
ing adaptive variable neighbourhood search algorithm. Felipe, Or- an Adaptive Large Neighbourhood Search (ALNS) heuristic to min-
tuño, Righini, and Tirado (2014) have studied a variation of Electric imize fuel consumption, emission and driver cost. The algorithm
VRP (E-VRP) which includes partial recharges with several recharg- for solving PRP iterates between solving VRPTW and speed opti-
ing technologies. They determined the amount of energy recharged mization. Initial routes are formed for VRPTW using fixed speed
and solved the problem using constructive and local search heuris- and are improved using a speed optimization algorithm. They fur-
tics within a simulated annealing framework. Poonthalir, Nadara- ther extended the work to solve PRP as a bi objective optimiza-
jan, and Geetha (2015) discussed a bi objective vehicle routing tion problem (Demir, Bektaş, & Laporte, 2014a) that concentrated
problem with limited refuelling halts, where the number of halts in arriving at a trade off between the conflicting objectives of fuel
made by vehicles at refuelling station is minimized along with consumption and total driving time. The problem is modelled with
route cost. They solved the problem using Particle Swarm Opti- four different a posteriori methods using an enhanced ALNS pro-
mization with Greedy Mutation Operator (PSO-GMO). cedure where speed optimization is done at each iteration. They
A simulated annealing based exact solution approach using have used a comprehensive emission model to estimate the fuel
branch and cut technique (Koc & Karaoglan, 2016) was used to consumption.
solve G-VRP. An electric vehicle routing problem that considers ve- Pitera, Sandoval, and Goodchild (2011) formulated an emission
hicle load on battery consumption was studied by Lin, Zhou, and minimization routing decision for urban pick up system with het-
Wolfson (2016). A multi space sampling heuristic for G-VRP was erogeneous fleet. Their study demonstrated a significant improve-
solved by Montoya, Guéret, Mendoza, and Villegas (2016). They ment in emission reduction. A bi objective GVRP using NSGA II was
used a two phase approach that builds the routes using random- formulated by Jemai, Zekri, and Mellouli (2012) with objectives to
ized travelling salesman heuristic and in the second phase, they minimize distance and CO2 emission. A green vehicle distribution
solved it by formulating a set partitioning problem of the routes. model for public transport network was developed as a non lin-
The model concentrated in reducing the length of route and CO2 ear optimization problem by Jovanović, Pamučar, and Pejčić-Tarle
emission. The formulation of G-VRP as proposed by Erdogan and (2014). They designed an Adaptive Neuro Fuzzy Inference System
Miller Hooks (2012) includes multiple copies of AFS, to enable (ANFIS) model with environmental parameters, passenger costs,
each visit to the refuelling station. This increases the complexity of and their impact on green routing to solve the problem. Ćirović,
the problem. Bruglieri, Mancini, Pezzella, and Pisacane (2016) gave Pamučar, and Božanić (2014) concentrated in routing light deliv-
an alternate formulation which prevents the creation of multiple ery vehicles using adaptive neural network that concentrated in re-
copies of AFS which eventually reduces the use of number of vari- ducing air pollution, noise level, and logistics operating costs. They
ables. Their model includes a pre computation of AFS to be in- concentrated in routing limited Environmentally Friendly Vehicles
cluded between each pair of customers. (EFV) and Unfriendly Vehicles (EUV) separately. The input parame-
An exact algorithm to solve G-VRP (Andelmin & Bartolini, 2017) ters for neural network were logistics operating costs and environ-
was formulated as a set partitioning problem where columns rep- mental parameters which were used to assess the performance of
resented the feasible routes like simple circuits in multiple graphs network links for calculating routes and then a Clarke and Wright
and several valid inequalities were added. Computational exper- Savings algorithm was used.
iments were carried out on G-VRP test instances. Leggieri and Xiao and Konak (2015) presented a time dependent heteroge-
Haouari (2017) gave a non linear formulation for time and en- neous green vehicle and scheduling problem, with the objectives to
ergy consumption constraints of G-VRP. An MILP formulation of minimize CO2 emission and weighted tardiness. Travel schedules
the problem is proposed by linearizing the constraints using of vehicles were determined using travelled distance in different
Reformulation-Linearization technique. Their approach reduced the time periods and solved using dynamic programming approach.
use of number of variables and constraints and included a set A Satisfactory-GVRP was developed by Afshar-Bakeshloo, Mehrabi,
of pre processing conditions which made the problem to be ef- Safari, Maleki, and Jolai (2016) as an extension of pollution rout-
ficiently solvable using commercial solvers. A path based Mixed ing problem that takes into account the economic, environmen-
Integer Linear Programming formulation was done for G-VRP by tal, and customer satisfaction as objectives. A periodic G-VRP with
Pisacane, Bruglieri, Mancini, and Pezzella (2017). They generated all time dependent urban traffic and time window was studied by
feasible routes and eliminated all dominated paths from the feasi- Mirmohammadi, Babaee Tirkolaee, Goli, and Dehnavi-Arani (2017).
ble set which is given as an input to a set partitioning formulation They modelled the problem to minimize carbon emission, ear-
G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144 133
This section describes the modelling of F-GVRP as a bi objective Triangular distribution is used to design the varying speed con-
optimization problem using goal programming and the simulation straint. A triangular distribution is a continuous probability distri-
of varying speed constraint using triangular distribution. bution with the lowest possible value a, the highest possible value
b and most likely value c where a < b and a ≤ c ≤ b. It’s proba-
3.1. Multi objective optimization bility distribution function is shaped like a triangle. It is a useful
tool when a variable is to be estimated subjectively. The expected
A general multi objective optimization deals with more than value of a triangular distribution is one third of the sum of the
one objective where a single objective is not possible to solve the three parameters. It is represented in Fig. 1.
134 G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144
3.3.1. Fuel consumption calculation for varying speed in F-GVRP using F-GVRP is defined on an undirected connected graph G = (V, E)
triangular distribution where the vertex set V has a set of N customer nodes C = {C1 ,C2 ,...,
This section describes the fuel consumption calculation for the CN }, M Refuelling Stations (RFS) R = {R1 ,R2 ,..., RM } and depot (V0 ).
vehicles that travel from node i to node j. In real life, it is not pos- The vertex set V is defined as a combination of V = C∪{V0 }. There is
sible for vehicles to travel with constant speed. Given a minimum a limited number of RFS available with unlimited capacity of fuel.
speed limit ϑmin and maximum speed limit ϑmax , a vehicle may A set R is used to represent several visits to each RFS to enable
travel with varying speed within ϑmin and ϑmax . To portray this, multiple visits to refuelling station R. Hence, the set of vertices is
a triangular distribution is used. If a vehicle travels with constant represented by V = V∪R . The depot V0 has a set of homogenous ve-
speed, fuel consumption will be a constant. Since varying speed is hicles K, with fuel capacityQ gallons. Each vertex i ∈ V has a service
used, the fuel consumption is calculated as explained below and is time ρ i which is the time a vehicle spends at customer location or
based on the work of Kuo (2010). at refuelling station. The depot can also be served as a refuelling
G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144 135
di j ∗
∗
∗
min f gphi j ∗ yi j ≤ G2 (7) d jV0 dji
asi j f j ≥ min r, r + diV0 where j ∈ C, i ∈ R (23)
i, j∈V,i = j mpg mpg
Where The objective function is redefined to include only the deviation
1 if vehicle k travels from i to j necessary for a minimization problem and is given in Eqs. (10) and
xi jk = (8) (11). Constraints (12) and (13) specify the difference between the
0 otherwise
goals and the attained solution. Constraint (14) specifies that from
1 if route exists between i and j a customer vertex, any vertex can be visited. Constraint (15) shows
yi j = (9) that refuelling station can have customer /refuelling station/depot
0 otherwise
as its successor. Flow conservation is ensured using (16). Con-
The objective function defined in (6) is to minimize route cost straints (17) and (18) ensure that, the number of vehicles entering
with target defined as G1 and the objective function defined in and leaving the depot is at most K. The arrival time at each vertex
(7) aims to reduce fuel consumption with target as G2. Eqs. (8) and is tracked using (19). Constraint (20) ensures that each vehicle re-
(9) specify the decision variables. As goal programming does not turns to depot within the maximum time. The remaining fuel level
maximize or minimize the objective function directly as in linear is tracked using constraint (21), based on the distance between i
programming problem, it seeks to minimize the deviation between and j and the average expected speed between i and j. Constraint
the goals and the obtained solution. Hence, the objective functions (22) ensures that the fuel level reaches its maximum capacity Q in
(6) and (7) are written as, refuelling station and depot. Constraint (23) is used to check that
there is enough fuel to reach either refuelling station or depot and
di j xi jk − w1 + v1 = G1
i, j∈V,k∈K,i = j no vehicle is left stranded.
di j ∗
asi j
f gphi j ∗ yi j − w2 + v2 = G2
i, j∈V,i = j 4. Proposed TVa-PSOGMO for solving F-GVRP
Where w1, w2, v1 and v2 are non negative deviational variables
and w1, w2, v1, v2 ≥ 0, and are used to measure the deviation PSO is a stochastic search technique. It mimics the behaviour
between the set goals. Then, the objective is to minimize the devi- of fish schooling or birds flocking. The highlight of PSO is group
ation given as, behaviour and the interaction among individuals that motivates
to make a bigger move. PSO is a population based Meta heuris-
Min w1 (10) tic. Each individual solution is called a particle in PSO. Each par-
ticle has d dimension and is represented as a vector as, X i =
Min w2 (11) (xi1 , xi2 , . . . , xid , ) which indicates the position of the ith parti-
cle in the swarm. Each particle is updated by a velocity V i =
Subject to, (vi1 , vi2 , . . . , vid , ) which guides the PSO to achieve global best po-
sition. Each particle has its personal best solution pbest that gets
di j xi jk − w1 + v1 = G1 (12)
updated with iteration once better position is obtained than the
i, j∈V,k∈K,i = j
current position. Each swarm has a global best solution gbest which
di j ∗ identifies the best move over all iterations. Each particle in the
f gphi j ∗ yi j − w2 + v2 = G2 (13)
asi j swarm tries to achieve the global best solution. To prevent PSO
i, j∈V,i = j
from local or premature convergence, a Greedy Mutation Opera-
tor (GMO) proposed by Poonthalir et al. (2015) is used with time
xi jk = 1 ∀j ∈ V k ∈ K (14)
varying acceleration which guides the search for better exploration.
i∈C,i = j
136 G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144
Multi objective PSO has an archive α which is used to store the 4.1.5. Velocity updation
set of all global non dominated solutions and also stores the best Each particle (xi1 ,xi2 ,..., xiN ) is updated by a velocity as given in
solution attained by each particle as suggested by Coello, Pulido, Eq. (28)
and Lechuga (2004). A detailed study on multi objective PSO can
vi+1, j = ω.vi j + c1 r1 ( pbest − xi j ) + c2 r2 (gbest − xi j )
be found in the works of Hu and Eberhart (2002), Tripathi, Bandy- (28)
xi+1, j = xi j + vi+1, j
opadhyay, and Pal (2007) and Parsopoulos and Vrahatis (2002).
pbest is particle’s personal best and gbest is particle’s global best po-
sition. Each particle’s position is updated using velocity based on
4.1. Sequential steps of TVa-PSOGMO
the particle’s individual performance which is captured in pbest and
the particle’s global performance which is captured in gbest that are
This section describes the steps carried out in TVa-PSOGMO.
influential in guiding the particle in the search space. In each iter-
ation, both pbest and gbest are updated based on individual best po-
4.1.1. Initial population sition and global best position of the particles. Here, c1 and c2 are
An initial swarm of particles are generated. Each particle has called cognition and social parameters respectively which are used
only customer positions {C1 ,C2 ,..., CN }. To generate initial swarm of to enhance the individual and social performance of the particle. c1
particles Nearest Neighbour Heuristic (NNH) is used with a ran- is responsible for exploration and c2 for exploitation of particles. r1
dom selected customer. Almost, 75% of particles are generated us- and r2 are random numbers defined within the interval [0, 1].
ing NNH and the remaining 25% of the particles are generated ran-
domly. Let (xi1 ,xi2 ,..., xiN ) be a representation of the ith particle 4.1.6. Time varying inertia
with N customers {C1 ,C2 ,..., CN } with swarm sizes S. Generally, to improve the convergence of the particles inertia
weight (ω) is used. Since the search space of the multi objective
optimization is complex, a time variant inertia weight is used. Ini-
4.1.2. Solution encoding
tially, particles are subjected to high inertia weight which leads
Each generated particle represents the sequence of customers
to high global exploration and as iteration progresses the parti-
to be served. These particles are converted to feasible routes
cles are subjected to low inertia weight to guide local exploitation.
by inserting refuelling stations and depot. Let (V0 ,xi1 ,xi2 ,RFS1 ,...,
Hence, varying inertia weight (ωcurr_iter ) is used to optimize the be-
xiL ,V0 ,...xij ,...., V0 ) be the solution encoding of the particle (xi1 ,xi2 ,...,
haviour of the search with global exploration and local exploitation
xiN ) with depot and refuelling station. Hence there are two rep-
as specified in Eq. (29).
resentations used, particle represents the customer sequence and
solution represents the route formed. max _iter − cur r _iter
ωcurr_iter = (ωmax − ωmin )∗ + ωmin (29)
max _iter
4.1.3. Fitness function Where ωmax and ωmin are the maximum and minimum iner-
To evaluate the strength of each particle, an evaluation method tia weights respectively and max _iter , cur r _iter are the maximum
called fitness function is defined. It is calculated based on the dis- number of iterations and current iteration number, respectively.
tance between two nodes k and l where k, l ∈ V. As already men-
tioned, there are two encoding used, one is customer encoding 4.1.7. Time varying acceleration
which is stored as particle which is subjected to velocity update Time varying acceleration concentrates in enhancing global
and the other is solution encoding which takes the particle en- search in the early part of the search and convergence in the lat-
coding and converts it to route by inserting refuelling station and ter part of the search. c1 and c2 are used to achieve this, where
depot. Fitness/cost of the route are calculated using Eq. (24). Eq. c1 is the cognitive acceleration coefficient and c2 is the social ac-
(25) gives the total route cost of k ∈ K vehicles. The second ob- celeration coefficient. In the initial stage of the iteration c1 is re-
jective which aims for calculating fuel consumption is done as de- duced from a specified maximum value c1max to a minimum value
fined in Eqs. (4) and (5) c1min and cognitive acceleration coefficient c2 is increased from
c2min to c2max As explained by Ratnaweera, Halgamuge, and Wat-
son (2004), a small cognitive component and a large social com-
Route_Costb = CostV0 ,depot + Costi, j +Cost j,V0 ∀i ∈ V/{V0 }
ponent allows particle to converge to global optimum in the latter
i, j∈V/{V0 }
part of the optimization process and is given in Eqs. (30) and (31).
(24)
cur r _iter
c1 = (c1 max − c1 min )∗ + c1 min (30)
max _iter
T otal _Route_Cost = Route_Costb (25)
k∈K cur r _iter
c2 = (c2 max − c2 min )∗ + c2 min (31)
max _iter
4.1.4. pbest and gbest Time variant acceleration coefficients are employed to have a
The initial fitness of the particle constitutes the initial pbest better compromise between exploration and exploitation for multi
value and the best of all pbest value is the gbest value for the swarm. objective optimization. The performance of PSO improves with the
Each particle’s pbest is calculated using Eq. (26) and gbest using Eq. introduction of acceleration and inertia coefficients varying it over
(27). the iterations.
fitnesst t=1
pbest = (26) 4.1.8. Particle encoding and decoding
min ( pbest , fitnesst ) t>1 Each particle is converted to a feasible route and the dimension
of each particle will be different based on the inclusion of refu-
elling station and depot. To update velocity, routes are converted to
gbest = min pbestt ∀t = 1 . . . max _iter (27) particle positions using Rank of Value (ROV) as given by Eq. (32),
where fitnesst is the T otal _Rout e_C ost at iteration t and is updated
(xmax − xmin )
with the best of pbest xi j = xmin + ( yi j − 1 + r1 ) (32)
N
G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144 137
Proof. Consider a random particle Xi with customer positions The proposed algorithm is tested on the G-VRP data set of
asXi = (xi1 ,xi2 ,..., xik ,xil ,xim ,..., xiN ). To calculate the fuel consumption Erdogan and Miller Hooks (2012). Their results are improved
between any two customers, say, xil and xim , the speed travelled by many researchers and the Best Known Solution (BKS) from
138 G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144
Table 1
Fuel consumption and route cost of uniformly distributed customers.
Data set Best known solution F-GVRP using TVa-PSOGMO with varying speed Percentage deviation
BKS Fuel consumption Speed Route cost Expected fuel consumption Expected speed
Montoya et al. (2016) are displayed against each data set. All the The results specify the total fuel consumption under constant
data set have 10 data instances. There are 4 small data sets with and varying speed environment with speed varying between a
20 customers each. There are 3 refuelling stations. Each vehicle has minimum and maximum speed limit of 10 and 70 respectively
a maximum time limit of 11 h and each vehicle travels at a con- taken in an interval of 10 as [10 20 30 40 50 60 70]. To derive the
stant speed of 40 miles/h with a constant fuel consumption rate comparison between constant and varying speed fuel consumption
of 0.2 gallons/mile. The capacity of the fuel tank is 60 gallons. The rate, the algorithm is run with the goal G1 taken as the BKS’s route
service time at customer and refuelling station is 30 and 15 min, cost and the corresponding non dominated solution obtained for
respectively. The locations of customer and refuelling station are the fuel consumption is displayed. It is observed that, as fuel con-
specified with latitude and longitude values and are converted to sumption is less, it is possible to serve more customers with less
Euclidean distance co-ordinates with the radius of the earth taken number of vehicles and a substantial decrease in the route cost can
as 4182.4449. It is implemented on Intel core I3-3220 processor be achieved, if goal G1 is relaxed. A positive percentage deviation
with 3.30 GHz and 4 GB RAM using MATLAB R2014a. is obtained for almost all data instances which represents the effi-
TVa-PSOGMO works well for all the data sets and the obtained ciency of the varying speed constraint.
route cost and fuel consumption details are projected in Tables 2– The results project that TVa-PSOGMO performs well and is
5. The first goal G1 is the route cost of BKS and the second goal competent with BKS. It is observed that, even though the route
G2 is the fuel consumption which is initially taken as a large value cost obtained using varying and constant speed is the same, the
and is updated with a better solution over the iterations. fuel consumption need not be the same. It is dependent on the
The parameter setting of TVa-PSOGMO is based on road condition, traffic conditions, the speed of the vehicle, and sev-
Tripathi et al. (2007). The swarm size is 30. The cognitive eral other factors which are influential in the fuel consumption cal-
and social acceleration coefficients are taken as c1max = 0.5 and culation. For example, if the route 0-2-8-5-0 costs 14.2 and the
c1min = 2.5, c2min = 0.5 to c2max = 2.5 A linearly decreasing in- route cost of 0-8-5-2-0 is also 14.2, it is not necessary that both
ertia coefficient is used with initial and final inertia weight as should travel with same fuel consumption as it may vary with the
ωmax = 0.4 and ωmin = 0.9 respectively. Particle positions are road condition, speed, traffic congestion, and many other factors.
taken as xmin = 2.0 and xmax = 0.0 respectively. The cross over and For data instances S2_4i6s, S2_4i8s, S2_4i10s, the cost of the route
mutation probabilities are taken as 0.9 and 0.4 respectively. The is the same and the constant fuel rate gives the same fuel con-
important advantage of using varying acceleration coefficient is to sumption for all the three instances. But, in varying speed environ-
have better compromise between exploration and exploitation as ment, the fuel consumption varies and is dependent on the speed.
specified in Ratnaweera et al. (2004). As observed from Tables 1–4, though the route cost is the same,
Comparison of fuel consumption with varying and constant speed the routes obtained for F-GVRP using TVa-PSOGMO is different
The route cost obtained with the proposed method is compe- from the route obtained using G-VRP. To show the structural dif-
tent with the BKS. To compare the fuel consumption of F-GVRP, ference between the routes obtained with fuel consumption as an
the fuel consumption of G-VRP should be calculated. Since G- additional objective, the route obtained for the data set 20c3sU1
VRP use constant speed with a constant fuel consumption rate of is plotted and is depicted in Fig. 3. It is seen that the routes ob-
0.2 gallons/mile, Eq. (33) is used to determine the total fuel con- tained for constant and varying speed is different and the vehicle
sumption of G-VRP. has taken a different route because of lesser fuel consumption. The
route obtained for F-GVRP is served by one vehicle less than the
fuel_consumption = route_cost × fuel_consumption_rate (33)
route obtained for G-VRP because the vehicle can travel for longer
To validate the performance of the proposed algorithm, the to- duration as the vehicle spends less time in the refuelling station,
tal increase or decrease in the fuel consumption is calculated using since fuel consumption is less. Almost in half of the data instances,
Eq. (34). there is a decrease in the use of the number of vehicles, attributed
by the fuel consumption.
optimal cost − obtained cost Pareto Optimal Front
× 100 (34)
optimal cost The problem is modelled as a bi-objective optimization problem
The results obtained for all 4 data sets contribute to a decrease to minimize both route cost and fuel consumption. The challenge
in the fuel consumption when varying speed is used. Tables 1–4 is to determine the route with the BKS’s route cost and to esti-
project the average expected speed of the entire route. A 20.48% mate the fuel consumption for the obtained route cost. Goal G1 is
decrease in the fuel consumption is realized using varying speed. set as BKS and the algorithm is run for a specified maximum num-
Since the entire distance is not travelled by the vehicle with uni- ber of iterations or till the best route is obtained. The best routes
form speed there is a drop in the use of fuel. Hence, up to 20% are stored in the archive. The route that archives G1 with compro-
in the cost of the fuel can be saved which indirectly contribute to mising fuel consumption is taken as the non dominated solution
lesser carbon footprint. and is displayed in Tables 1–4. As already noted, if G1 is relaxed,
G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144 139
Table 2
Fuel consumption and route cost of clustered customers.
Best known solution F-GVRP using TVa-PSOGMO with varying speed Percentage deviation
Data set BKS Fuel consumption Speed Route cost Expected fuel consumption Expected speed
Table 3
Fuel consumption and route cost of both uniform and clustered customers.
Best known solution F-GVRP using TVa-PSOGMO with varying speed Percentage deviation
Data set BKS Fuel consumption Speed Route cost Expected fuel consumption Expected speed
Table 4
Fuel consumption and route cost of both uniform and clustered customers.
Best known solution F-GVRP using TVa-PSOGMO with varying speed Percentage deviation
Data set BKS Fuel consumption Speed Route cost Expected fuel consumption Expected speed
Table 5
Impact of fuel consumption on uniform customers for different speed intervals.
Data set Route cost Expected fuel consumption Expected speed Expected fuel consumption Expected speed Expected fuel consumption Expected speed
then most of the instances may give a better route cost when com- fuel consumption is obtained. A depiction of the Pareto dominant
pared with best solutions. But, there are no published results to solution front obtained for various data sets is displayed in Fig. 4.
compare the performance of the proposed TVa-PSOGMO, hence to Impact of speed intervals on fuel consumption
derive the comparison between the route cost of G-VRP, F-GVRP’s The speed variation result in substantial decrease in the fuel
goal G1 is based on the BKS’s route cost and the corresponding consumption. It is important to analyze the impact of various
speed intervals on fuel consumption intervals. Experiments are
140 G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144
Table 6
Impact of fuel consumption on clustered customers for different speed intervals.
Data set Route cost Expected fuel consumption Expected speed Expected fuel consumption Expected speed Expected fuel consumption Expected speed
Table 7
Impact of fuel consumption on uniform and clustered customers for different speed intervals.
Data set Route cost Expected fuel consumption Expected speed Expected fuel consumption Expected speed Expected fuel consumption Expected speed
Fig. 3. Routes obtained for constant and varying speed for 20c3sU1.
conducted to find the relationship between various speed intervals the results are recorded. To study the fuel consumption details un-
and fuel consumption. der varying speed in different categories, the algorithm is run to
A snap shot of triangular distribution for various categories of get the same BKS for the goal G1 in the route cost. The results de-
speed intervals is derived and is projected in Fig. 5. picted are the best obtained from 10 runs of each instance of the
To study the behaviour of speed under various speed intervals, data set.
speed is categorised with 4 different speed intervals. Category 1 The speed obtained for various categories are displayed in
has speed in the range [10 20 30 40 50 60 70] with interval 10, Tables 5–8. It is noted that, there is a positive correlation between
category 2 [5 10 15 20 25 30 35 40 45 50 55 60 65 70 75] has speed and the fuel consumption. The expected average speed in-
speed interval as 5, category 3 [1 20 40 60 80] is taken with inter- creases when the length of the interval increases. The expected av-
val 20 and category 4 [10 30 60] with interval 30. The maximum erage speed is 40.10 in category 2 where the speed has an interval
speed is taken not to exceed 80. The Tables from 1 to 4 are run of 5miles/h, 41.19 in category 3 with the interval being 20 miles/h
with category 1 where the mean speed for each travel from node and in category 4 it is 46.48 with an interval of 30 miles/h.
i to node j, where i, j ∈ V is taken at random and the impact of Prominent deviations are not observed with the speed intervals
the varying speed on each instance of the data set is studied and of 10 or 5 miles difference. When speed is taken in intervals of
G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144 141
30 as in category 4, an increase in the speed with high fuel con- hicle to serve successive customers. Hence, the algorithm performs
sumption is observed for most of the data instances, though for poor when the interval is taken with 30miles/h difference. Though
few instances it gives better fuel consumption rate. It shows that, better fuel consumption can be realized with varying speed, to de-
though varying speed reduces fuel consumption, the speed inter- rive a better routing plan, proper selection of speed interval is im-
val should not be more to realize the benefits from the fuel con- portant. As seen from the results, category 1 and 2 are able to
sumption. Also, it is hard to get the BKS at this rate as there is a get better fuel consumption minimization for most of the data in-
frequent requirement for fuel or the time is insufficient for the ve- stances.
142 G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144
Table 8
Impact of fuel consumption on uniform and clustered customers for different speed intervals.
Data set Route cost Expected fuel consumption Expected speed Expected fuel consumption Expected speed Expected fuel consumption Expected speed
Fig. 6. Expected speed for various speed categories. Fig. 7. Fuel consumption for various speed categories.
References
Afshar-Bakeshloo, M., Mehrabi, A., Safari, H., Maleki, M., & Jolai, F. (2016). A green
6. Conclusion and future work
vehicle routing problem with customer satisfaction criteria. Journal of Industrial
Engineering International, 12(4), 529–544.
F-GVRP is introduced as an extension of G-VRP in this paper. Andelmin, J., & Bartolini, E. (2017). An Exact algorithm for the green vehicle routing
The problem is modelled as a bi objective optimization problem problem. Transportation Science. doi:10.1287/trsc.2016.0734.
Apaydin, O., & Gonullu, M. T. (2008). Emission control with route optimization in
to minimize both route cost and fuel consumption. This paper ad- solid waste collection process: A case study. Sadhana, 33(2), 71–82.
dresses speed as a varying constraint and proposes a model to cal- Bard, J. F., Huang, L., Jaillet, P., & Dror, M. (1998). A decomposition approach to the
culate the route cost and fuel consumption for vehicles that travel inventory routing problem with satellite facilities. Transportation science, 32(2),
189–203.
with varying speed. Experiments are conducted with constant and Bektaş, T., & Laporte, G. (2011). The pollution-routing problem. Transportation Re-
varying speed constraint to study the impact of route cost and fuel search Part B: Methodological, 45(8), 1232–1250.
consumption where a substantial reduction in fuel consumption is Bektas, T., Demir, E., & Laporte, G. (2016). Green vehicle routing. In Green transporta-
tion logistics (pp. 243–265). Springer International Publishing.
realized using varying speed constraint. The proposed method sug- Bruglieri, M., Mancini, S., Pezzella, F., & Pisacane, O. (2016). A new mathematical
gests a routing plan with less fuel consumption, where the carbon programming model for the green vehicle routing problem. Electronic Notes in
emission can be greatly reduced. Discrete Mathematics, 55, 89–92.
Calvete, H. I., Galé, C., Oliveros, M. J., & Sánchez-Valverde, B. (2007). A goal program-
The contribution of this research is three fold. First, a bi ob- ming approach to vehicle routing problems with soft time windows. European
jective optimization model F-GVRP that intends to minimize both Journal of Operational Research, 177(3), 1720–1733.
route cost and fuel consumption is introduced and is modelled us- Charnes, A., & Cooper, W. W. (1977). Goal programming and multiple objective op-
timizations: Part 1. European Journal of Operational Research, 1(1), 39–54.
ing goal programming approach. Second, speed is taken as a vary-
Coello, C. A. C., Pulido, G. T., & Lechuga, M. S. (2004). Handling multiple objectives
ing constraint to study the behaviour of F-GVRP which is simulated with particle swarm optimization. IEEE Transactions on Evolutionary Computa-
using triangular distribution. Experiments are conducted with four tion, 8(3), 256–279.
different categories of speed intervals and the corresponding route Ćirović, G., Pamučar, D., & Božanić, D. (2014). Green logistic vehicle routing problem:
Routing light delivery vehicles in urban areas using a neuro-fuzzy model. Expert
cost and fuel consumption are estimated and analyzed. Significant Systems with Applications, 41(9), 4245–4258.
improvement in fuel consumption is realized under varying speed Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management
environment. Better routing plan is achieved with less number of Science, 6(1), 80–91.
Erdoğan, S., & Miller-Hooks, E. (2012). A green vehicle routing problem. Transporta-
vehicles. Third, a particle swarm optimization with greedy muta- tion Research Part E: Logistics and Transportation Review, 48(1), 100–114.
tion operator and time varying acceleration is used to solve the Demir, E., Bektaş, T., & Laporte, G. (2012). An adaptive large neighborhood search
problem and the results are compared with benchmark data sets heuristic for the pollution-routing problem. European Journal of Operational Re-
search, 223(2), 346–359.
which prove the efficiency of the algorithm. Demir, E., Bektaş, T., & Laporte, G. (2014a). The bi-objective pollution-routing prob-
The impact of this research is to address the environmental lem. European Journal of Operational Research, 232(3), 464–478.
concern associated with the planning and routing of delivery vehi- Demir, E., Bektaş, T., & Laporte, G. (2014b). A review of recent research on green
road freight transportation. European Journal of Operational Research, 237(3),
cles and the influence of speed on the fuel consumption rate which 775–793.
has a direct consequence on fuel emission minimization. Organiza- Felipe, Á., Ortuño, M. T., Righini, G., & Tirado, G. (2014). A heuristic approach for the
tion can plan their vehicles to opt for a better speed interval plan green vehicle routing problem with multiple technologies and partial recharges.
Transportation Research Part E: Logistics and Transportation Review, 71, 111–128.
to realize fuel consumption minimization.
Figliozzi, M. (2010). Vehicle routing problem for emissions minimization. Trans-
Some insights are observed during the study, the use of num- portation Research Record: Journal of the Transportation Research Board, 2197, 1–7.
ber of vehicles get reduced as vehicles can serve more customers Ghoseiri, K., & Ghannadpour, S. F. (2010). Multi-objective vehicle routing problem
since fuel consumption is minimized. The average expected speed with time windows using goal programming and genetic algorithm. Applied Soft
Computing, 10(4), 1096–1107.
increases with an increase in the speed interval. Also, speed inter- Hu, X., & Eberhart, R. (2002). Multiobjective optimization using dynamic neighbor-
val is important in determining the fuel consumption minimiza- hood particle swarm optimization. In Proceedings of the congress on evolutionary
tion. Better routing plan can be derived with cautious selection of computation: 2 (pp. 1677–1681).
Jabali, O., Woensel, T., & De Kok, A. G. (2012). Analysis of travel times and CO2 emis-
speed. It is also observed that regardless of the speed intervals, sions in time dependent vehicle routing. Production and Operations Management,
constant speed consumes more fuel than varying speed. 21(6), 1060–1074.
An immediate extension of this study is to model F-GVRP with Jabir, E., Panicker, V. V., & Sridharan, R. (2017). Design and development of a hybrid
ant colony-variable neighbourhood search algorithm for a multi-depot green
fuel emission as an additional objective and to study the behaviour vehicle routing problem. Transportation Research Part D: Transport and Environ-
with constant and varying speed environment. Also, this research ment, 57, 422–457.
can be further extended to study the impact on route cost and fuel Jemai, J., Zekri, M., & Mellouli, K. (2012 April). An NSGA-II algorithm for the green
vehicle routing problem. In European conference on Evolutionary Computation in
consumption in electric VRP where speed variation can occur with
Combinatorial Optimization (pp. 37–48). Berlin, Heidelberg: Springer.
partial and fully charged batteries. The model can also be used to Jovanović, A. D., Pamučar, D. S., & Pejčić-Tarle, S. (2014). Green vehicle routing in
study the impact of speed and fuel consumption with hybrid vehi- urban zones – A neuro-fuzzy approach. Expert Systems with Applications, 41(7),
3189–3203.
cles, when there is a switch over between battery and fuel which
Jovičić, N. M., Bošković, G. B., Vujić, G. V., Jovičić, G. R., Despotović, M. Z., Milo-
has an effect on the speed. It can also be extended to study the vanović, D. M., et al. (2010). Route optimization to increase energy efficiency
behaviour of heterogeneous vehicles under varying speed environ- and reduce fuel consumption of communal vehicles. Thermal Science, 14(suppl.),
ment. Additional constraints like road conditions, vehicle load can 67–78.
Kara, I., Kara, B., & Yetis, M. K. (2007 August). Energy minimizing vehicle routing
be included with varying speed environment in F-GVRP and their problem. In international conference on Combinatorial Optimization and Applica-
impact on route cost and fuel consumption can be studied. tions (pp. 62–71). Berlin, Heidelberg: Springer.
144 G. Poonthalir, R. Nadarajan / Expert Systems With Applications 100 (2018) 131–144
Kazemian, I., & Aref, S. (2017). A green perspective on capacitated time-depen- Proceedings of the annual workshop of the EURO working group on vehicle routing
dent vehicle routing problem with time windows. International Journal of Supply and logistics (VeRoLog) 10–12 July, Amsterdam.
Chain and Inventory Management, 2(1), 20–38. Pitera, K., Sandoval, F., & Goodchild, A. (2011). Evaluation of emissions reduction in
Koç, Ç., & Karaoglan, I. (2016). The green vehicle routing problem: A heuristic based urban pickup systems. Transportation Research Record: Journal of the Transporta-
exact solution approach. Applied Soft Computing, 39, 154–164. tion Research Board, 2224(1), 8–16.
Kuo, Y. (2010). Using simulated annealing to minimize fuel consumption for the Poonthalir, G., Nadarajan, R., & Geetha, S. (2015). Vehicle routing problem with lim-
time-dependent vehicle routing problem. Computers & Industrial Engineering, ited refueling halts using particle swarm optimization with greedy mutation op-
59(1), 157–165. erator. RAIRO-Operations Research, 49(4), 689–716.
Leggieri, V., & Haouari, M. (2017). A practical solution approach for the green vehicle Ratnaweera, A., Halgamuge, S. K., & Watson, H. C. (2004). Self-organizing hierarchi-
routing problem. Transportation Research Part E, 104, 97–112. cal particle swarm optimizer with time-varying acceleration coefficients. IEEE
Li, J. (2012). Vehicle routing problem with time windows for reducing fuel con- Transactions on evolutionary computation, 8(3), 240–255.
sumption. Journal of Computers, 7(12), 3020–3027. Schneider, M., Stenger, A., & Goeke, D. (2014). The electric vehicle-routing prob-
Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. Y. (2014). Survey of green vehicle lem with time windows and recharging stations. Transportation Science, 48(4),
routing problem: Past and future trends. Expert Systems with Applications, 41(4), 500–520.
1118–1138. Schneider, M., Stenger, A., & Hof, J. (2015). An adaptive VNS algorithm for vehicle
Lin, J., Zhou, W., & Wolfson, O. (2016). Electric vehicle routing problem. Transporta- routing problems with intermediate stops. OR Spectrum, 37(2), 353–387.
tion Research Procedia, 12, 508–521. Scott, C., Urquhart, N., & Hart, E. (2010, April). Influence of topology and payload
Mancini, S. (2017). The hybrid vehicle routing problem. Transportation Research Part on CO2 optimised vehicle routing. In the European conference on Applications of
C, 78, 1–12. Evolutionary Computation (pp. 141–150). Berlin, Heidelberg: Springer.
Mirmohammadi, S. H., Babaee Tirkolaee, E., Goli, A., & Dehnavi-Arani, S. (2017). Suzuki, Y. (2011). A new truck-routing approach for reducing fuel consumption and
The periodic green vehicle routing problem with considering of time-depen- pollutants emission. Transportation Research Part D: Transport and Environment,
dent urban traffic and time windows. Iran University of Science & Technology, 16(1), 73–77.
7(1), 143–156. Teng, L., & Zhang, Z. (2016). Green vehicle routing problem with load factor. Ad-
Montoya, A., Guéret, C., Mendoza, J. E., & Villegas, J. G. (2016). A multi-space sam- vances in Transportation Studies, 3, 75–82.
pling heuristic for the green vehicle routing problem. Transportation Research Tripathi, P. K., Bandyopadhyay, S., & Pal, S. K. (2007). Multi-objective particle swarm
Part C: Emerging Technologies, 70, 113–128. optimization with time variant inertia and acceleration coefficients. Information
Pan, S., Ballot, E., & Fontane, F. (2013). The reduction of greenhouse gas emissions Sciences, 177(22), 5033–5049.
from freight transport by pooling supply chains. International Journal of Produc- Xiao, Y., Zhao, Q., Kaku, I., & Xu, Y. (2012). Development of a fuel consumption op-
tion Economics, 143(1), 86–94. timization model for the capacitated vehicle routing problem. Computers & Op-
Parsopoulos, K. E., & Vrahatis, M. N. (2002, March). Particle swarm optimization erations Research, 39(7), 1419–1431.
method in multiobjective problems. In Proceedings of the ACM symposium on Xiao, Y., & Konak, A. (2015). Green vehicle routing problem with time-varying traf-
applied computing (pp. 603–607). fic congestion. In Proceedings of the fourteenth INFORMS computing society con-
Pisacane, O., Bruglieri, M., Mancini, S., & Pezzella, F. (2017). A path-based mixed in- ference (pp. 134–148).
teger linear programming formulation for the green vehicle routing problem. In