# An Efficient Two-Objective Hybrid Local Search Algorithm for Solving the Fuel Consumption Vehicle Routing Problem

Authors: Weizhen Rao; Feng Liu; Shengbin Wang
Journal: Applied Computational Intelligence and Soft Computing
 (2016)

---

## Abstract

The classical model of vehicle routing problem (VRP) generally minimizes either the total vehicle travelling distance or the total number of dispatched vehicles. Due to the increased importance of environmental sustainability, one variant of VRPs that minimizes the total vehicle fuel consumption has gained much attention. The resulting fuel consumption VRP (FCVRP) becomes increasingly important yet difficult. We present a mixed integer programming model for the FCVRP, and fuel consumption is measured through the degree of road gradient. Complexity analysis of FCVRP is presented through analogy with the capacitated VRP. To tackle the FCVRP’s computational intractability, we propose an efficient two-objective hybrid local search algorithm (TOHLS). TOHLS is based on a hybrid local search algorithm (HLS) that is also used to solve FCVRP. Based on the Golden CVRP benchmarks, 60 FCVRP instances are generated and tested. Finally, the computational results show that the proposed TOHLS significantly outperforms the HLS.


---

## Body

## 1. Introduction

In recent years, consequences from natural resource depletion and environmental degradation have made sustainability a more important objective than profitability for public and private transportation systems. As a result, sustainability has become one of the most popular topics studied by both practitioners and academic researchers in transportation area [1–7]. For instance, logistics service providers (LSPs) are paying increasing attention to the environmental externalities of the transportation operations [1], for example, fuel consumption and carbon dioxide equivalent (CO2e) emissions. These emissions can cause a lot of serious problems such as respiratory diseases and global warming. As pointed out in Demir et al. [5, 6], most LSPs have been using heavy- and medium-duty vehicles such as trucks and vans to perform a large amount of freight transportation operations at the local and regional levels. Trucks, whose power mainly comes from diesel engines, are one of the major sources of CO2e emissions (e.g., nitrogen oxides (N2O), particulate matter (PM), and carbon dioxide (CO2)). Thus, minimizing the CO2e emissions from trucks as well as other types of vehicles while simultaneously completing the required transportation tasks has always been a key issue for these LSPs in the past two decades. This paper aims to provide an insight and a methodology to efficiently resolve this issue.In the most recent literature, vehicle carbon emission problems have been addressed in the area of transportation research, for example, Bigazzi and Bertini [8], Eglese and Black [9], Demir et al. [10], Dekker et al. [11], Lin et al. [12], and Demir et al. [5, 6]. The models proposed in these papers are mainly variants of the well-known vehicle routing problem (VRP), which focuses on determining the optimal visiting routes for a fleet of vehicles in a transportation network to satisfy the transportation demands of a set of customers subject to given constraints. The classical VRP model typically minimizes either the total vehicle travelling distance/time or the total number of all vehicles dispatched in field [13–16]. Of all the extended VRPs, the fuel consumption VRP (FCVRP) has received most attentions over the years. The FCVRP is a variant of the capacitated VRP (CVRP); the latter imposes additional vehicle capacity constraint for a certain commodity on the regular VRP. One of the differences between the FCVRP and CVRP is that the objective function of FCVRP is to minimize total fuel consumption instead of the total traveling distance or cost. However, this difference makes FCVRP more difficult to solve using existing methodologies due to the following reasons. First, the solution space is huge as a result of additional factors (such as road gradient) considered that could affect the fuel consumption. For example, even for the same route, the fuel consumption for a vehicle traveling in one direction is different from that in the opposite direction because of the consideration of road gradient. Likewise, the complexities of basic improvement operations (2-opt,or-opt,exchange, andswap) can also increase. In this paper, we focus on the FCVRP and provide a mixed integer programming (MIP) model in which fuel consumption is measured by the degree of road gradient. We propose an efficient two-objective hybrid local search algorithm (TOHLS) to solve this problem. The TOHLS algorithm is an extension of a hybrid local search algorithm (HLS) that is also able to solve the FCVRP. In addition, we generate 60 FCVRP instances based on the Golden CVRP benchmarks. These testing instances are used to compare the performances of the TOHLS and HLS algorithms. The computational results demonstrate that the TOHLS is very effective and efficient in solving the FCVRP.The remainder of this paper is organized as follows. In Section2, we provide a detailed literature review of FCVRP and other related work. In Section 3, we formally formulate the problem as a MIP model and perform a complexity analysis through analogy with CVRP. After that, an efficient two-objective hybrid local search algorithm (TOHLS) is proposed to solve this model in Section 4. Section 5 performs computational studies of the proposed algorithm on 60 testing problem instances. Finally, Section 6 concludes the paper.


## 2. Literature Review

One of the most important issues in FCVRP research is how to accurately estimate the vehicle fuel consumption. There are a few studies that provide insightful estimation methodologies, for example, Bigazzi and Bertini [8], Eglese and Black [9], and Demir et al. [10]. Demir et al. [6] categorized the existing factors that can determine the fuel consumption into five classes: vehicle, environment, traffic, driver, and operations. Vehicle factors include vehicle curb weight, vehicle shape, engine size, and fuel type. Environment factors include road gradient, pavement type, and surface. Traffic factors include speed, acceleration or deceleration, and traffic congestion. Driver factors include driver aggressiveness, gear selection, and idle time. Finally, operations related factors include fleet size/mix, payload, and empty kilometers. According to Demir et al. [6], the vehicle, traffic, and environment factors are measurable and have received more research interest, whereas the driver and operations factors can hardly be measured and are sometimes treated as externalities to affect fuel consumption. In this paper, we focus on the vehicle, traffic, and environment factors. In particular, we are interested in how the vehicle type, vehicle speed, and the degree of road gradient can affect fuel consumption. First, the manufacturing information for a certain type of vehicles somehow determines their fuel consumption levels. A heavy-duty truck essentially consumes more energy than a medium-duty one assuming they are required to complete the same tasks. Second, speed is more effective than traveling distance for emission estimates since speed can affect inertia, rolling resistance, and air resistance [6, 9]. Demir et al. [10] stated a rule of thumb for a medium-duty vehicle: if the speed is above 55 kilometers/hour, every kilometer/hour increase leads to a fuel consumption increase of 0.001 liters/kilometer approximately. An optimum driving speed at each point of a certain transportation network was obtained in Demir et al. [17] to minimize the emissions. Third, coupled with speed, road gradient is also considered to have an impact on the emissions. Intuitively, on an uphill slope, vehicles require more horsepower and fuel consumption due to gravity force than on a downhill road. According to Demier et al. [10], if a medium-duty vehicle is traveling on a 100-kilometer road segment with 1% road slope, its fuel consumption may take up to six liters more than on the flat road. Meanwhile, in most cases fuel consumption data derived under real driving conditions are significantly different from those provided by vehicle manufacturers [18]. In sum, by combining the vehicle type, speed, and the degree of road gradient information, the fuel consumption in our model can be measured accurately. Demier et al. [6] summarized three approaches of modeling fuel consumption (with increasing complexity): factor models, macroscopic models, and microscopic models. In this research, we adopt the microscopic fuel consumption model.FCVRP has been extensively studied in the literature. Urquhart et al. [19] focused on vehicle routing problem with time windows and studied the trade-offs between carbon dioxide savings, traveling distance, and the number of vehicles using evolutionary algorithms. The authors found out that up to 10% savings could be achieved. Bandeira et al. [20] performed three distinctive case studies in the USA and Portugal to evaluate the impact of traffic peak hours on ecofriendly routes changes. A microscopic fuel consumption model was used in their paper. The empirical results indicated that the most ecofriendly routes during off-peak and peak hours are essentially the same. In a follow-up study, Bandeira et al. [21] examined how to make the emission information available to drivers to help them select their preferred vehicle routes. It was found that the selected route has a substantial impact on pollutant emission rate and that a considerable emission reduction could be obtained from a smoother driving style. Correia et al. [22] proposed fuel consumption model to analyze ecofriendly routes in France. They utilized geographical features for eco-routing search, and the results indicated that ecoroutes were able to provide fuel savings between 1% and 36% comparing with fastest routes. Minett et al. [23] incorporated different roadway types (e.g., motorway, local, and provincial routes) into their fuel consumption model. Their results from the field study showed that driving in provincial routes saved for the drivers an average of 10.41 minutes and 1.25 liters of fuel comparing to driving in local routes and motorway routes, respectively.A few papers combine the total fuel consumption and the total cost together in the objective function. Bektaş and Laporte [24] extended the VRP with time windows to a vehicle pollution routing problem by considering both total fuel consumption and total cost as the objective function. The decisions to be made in their model included the vehicle routing to serve a set of customers and the vehicle speed on each segmented route. The computational studies indicated that up to 10% energy savings could be achieved. Similarly, Demir et al. [17] also constructed a fuel consumption model and proposed an algorithm that iteratively improved the solutions to the model between vehicle routing problem with time window and a speed optimization problem. In order to precisely estimate the fuel consumption, the authors randomly selected cities from the United Kingdom and used real geographical distances to generate benchmark instances. The computational results indicated that around 10% carbon dioxide emission reduction could be achieved. Since fuel consumption and cost are inherently contradicting each other, their trade-offs must be considered when they both appear as the objectives. Demir et al. [5] studied the trade-offs between the two factors and concluded that a fuel consumption reduction did not always come at a cost of long driving time. Ramos et al. [25] considered a multicommodity transportation network consisting of multiple depots. The authors applied a decomposition solution procedure to determine the optimal vehicle routing in order to minimize the carbon dioxide emission. The computational result of a case study indicated that up to 20% potential savings could be achieved if the company agreed to reshape the service areas and vehicle routes according to solutions. Franceschetti et al. [26] minimized the total fuel consumption, carbon dioxide emission, and driver costs under traffic congestion. They developed the optimal waiting conditions at certain locations for vehicles to avoid being stuck in traffic and to reduce the fuel consumption. Using the same instances generated in Demir et al. [17], the authors obtained a 20% reduction of total cost.In comparison with the aforementioned studies, the main contribution of this research is a formulation of the sustainable FCVRP that incorporates road gradient into the fuel consumption model and a two-objective hybrid local search algorithm to efficiently solve the FCVRP. The complexity results are critical for connecting our problem with the numerous existing results in CVRP studies. Like most studies in VRP, the optimization techniques proposed here can also be applied to other transportation and routing problems in similar environments.


## 3. Problem Formulation

### 3.1. Problem Statement

The research problem we investigate is defined as follows. The transportation network consists of a distribution center (DC) denoted by0 and a set of n customers: V
0
=
{
1,2
,
…
,
n
}. Each customer demands a given number of goods that are distributed from the DC. The DC and customers are all located in a given three-dimensional space. The position of each customer is described using the spacial coordinates with meter as unit, (
x
i
,
y
i
,
z
i
)
(
0
≤
i
≤
n
), where x
i and y
i are horizontal coordinates and z
i is vertical coordinate. The DC holds a set of vehicles for delivery purposes, but the exact number of vehicles to be used is unknown and must be determined optimally. Each vehicle has a loading capacity of Q with kilogram (kg) as its unit, and the curb weight of the vehicle is given by r
·
Q (r
>
0). The demand of each customer is given by q
i that must satisfy 0
≤
q
i
≤
Q, 1
≤
i
≤
n. The Euclidean distance between any two customers in V
0 is calculated as d
i
j
=
(
x
i
-
x
j
)
2
+
(
y
i
-
y
j
)
2
+
(
z
i
-
z
j
)
2. For any two customers that have the same vertical coordinates, their plane distance is hence c
i
j
=
(
x
i
-
x
j
)
2
+
(
y
i
-
y
j
)
2. Let v
i
j denote the speed of the vehicle traveling from customer i to customer j and Q
i
j denote the loading weight of the vehicle traversing the directed a
r
c
(
i
,
j
). In addition, we have the following assumptions.(i)
All vehicles are identical; that is, they have the same type of engine, fuel consumption rate, and loading capacity.
(ii)
The road gradient between any two customers is approximated by the difference between their vertical coordinates. Each directed arc has a unique road gradient angle.
(iii)
The traveling speed in the transportation network for all vehicles is the same for the same arc and different for different arcs. The details about the derivation of vehicle traveling speed are elaborated in Section3.
(iv)
The fuel consumption is determined by engine operations.
(v)
Each vehicle must start and end at the DC.
(vi)
The loading capacity constraint for each vehicle cannot be violated.
(vii)
Each customer must be serviced once and only once and by a single vehicle.
(viii)
Each vehicle has a given maximum traveling distanceL.We must determine an optimal number of vehicles and their optimal delivery routes such that the total fuel consumption for all vehicles is minimized. The resulting problem is called fuel consumption vehicle routing problem or FCVRP. The main difference between FCVRP and VRP model lies in the objective function where we consider minimizing total fuel consumption instead of total operations cost.


### 3.2. The FCVRP Model

In this subsection, we first analyze the factors that affect the fuel consumption rate (fuel consumption amount per time unit) and then formulate the problem as mixed integer programming model.We begin with an existing fuel consumption rate model following Barth et al. [27]: (1)
F
R
=
φ
k
·
N
·
V
s
+
P
/
η
μ
P
=
P
t
r
a
c
t
η
t
f
+
P
a
c
c
P
t
r
a
c
t
=
M
·
a
+
M
·
g
sin
⁡
θ
+
0.5
C
d
ρ
S
·
v
2
+
M
·
g
·
C
r
cos
⁡
θ
v
1000
,where FR is the fuel consumption rate with gallon/second as the unit while all the other denotations are the factors that determine fuel consumption. These factors can be categorized into the following two groups.The first group contains all factors that are irrelevant to vehicle routing decisions:φ: the air-fuel-ratio, N: the operating engine speed, μ: the fuel consumption coefficient, η
t
f: the traditional efficiency, C
d: the aerodynamic drag coefficient, S: the vehicle’s frontal area size, ρ: the air density, k: the engine fraction factor, V
s: the engine discharge rate, g: the gravity coefficient that is equal to 9.81 in this paper, P
a
c
c: the other vehicle energy requirements, η: the engine efficiency parameter, and C
r: the roll damping coefficient. The second group contains all factors that are directly relevant to vehicle routing decisions: d: the vehicle traveling distance, M: the combined weight of the vehicle itself and the loaded goods, θ: the angle degree of road gradient, v: the vehicle traveling speed, and a: the vehicle acceleration rate that is equal to 0 in this paper.Note that the values ofd, M, θ, and v can change according to various distribution and routing results in reality. For example, v is determined by the vehicle’s route and speed limit, M is determined by vehicle visiting sequences, and d is determined by the degrees of road gradients in a route. Consequently, we must incorporate a dynamic driving status in the model. The vehicle driving status between customers i and j can be described using the second-class factors d
i
j, M
i
j, θ
i
j, and v
i
j and is shown in Figure 1.Figure 1
The vehicle driving status when going uphill and downhill.
(a)
Driving downhill
(b)
Driving uphillThese two groups of factors play different roles in calculating the fuel consumption coefficientω
i
j of the directed a
r
c
(
i
,
j
). Group 1 factors are constants (C
1, C
2, and C
3 in the following formula), while group 2 factors are arc-specific parameters. The detailed formula for ω
i
j is as follows: (2)
ω
i
j
=
FR
·
t
=
C
1
d
i
j
v
i
j
+
C
2
M
i
j
g
d
i
j
sin
⁡
θ
i
j
+
C
3
v
i
j
2
d
i
j
+
M
i
j
g
d
i
j
C
r
cos
⁡
θ
i
j
,where C
1
=
φ
k
N
V
s
/
μ, C
2
=
φ
/
(
1000
η
μ
η
t
f
), and C
3
=
0.5
C
d
ρ
S.In formula (2), we can see that ω
i
j is a function of M
i
j, θ
i
j, d
i
j, and v
i
j. The first three values are predetermined in the problem, and v
i
j is determined by the two distances from each customer to the city center: (3)
v
i
j
=
v
m
i
n
+
u
d
i
+
u
d
j
2
u
d
·
v
m
a
x
-
v
m
i
n
,where v
m
a
x is the highest speed limit in the given urban area, v
m
i
n is the vehicle speed in the downtown area, u
d is the maximum distance between the border of the downtown area and the border of the suburban area, and u
d
i and u
d
j are the distances from customers i and j to the city center, respectively, satisfying max
⁡
{
u
d
i
∣
1
≤
i
≤
n
}
≤
u
d. City center is considered as a traffic congestion factor that affects fuel consumption. Vehicle can travel at a higher speed when it is farther away from the city center. To summarize, the vehicle fuel consumption from customer i to customer j
(
1
≤
i
≠
j
≤
n
) can be calculated as follows: (4)
ω
i
j
=
f
i
j
M
i
j
,
d
i
j
,
θ
i
j
,
v
i
j
=
f
1
i
j
+
f
2
i
j
f
2
i
j
>
0
f
1
i
j
f
2
i
j
≤
0
f
1
i
j
=
C
1
d
i
j
v
i
j
f
2
i
j
=
C
2
M
i
j
g
d
i
j
sin
⁡
θ
i
j
+
C
3
v
i
j
2
d
i
j
+
M
i
j
g
d
i
j
C
r
cos
⁡
θ
i
j
M
i
j
=
r
Q
+
Q
i
j
θ
i
j
=
arcsin
⁡
z
j
-
z
i
d
i
j
,where f
1
i
j is the fuel consumption caused by engine usage and f
2
i
j is the fuel consumption caused by driving on an upward gradient road. Note that when vehicle is driving on a downward gradient road, large values of θ
i
j can lead to negative values of f
2
i
j. This situation makes no sense in practice, and therefore when this case occurs, we make ω
i
j
=
f
1
i
j.The constant parameters in formula (4) can be determined from formula (2) and the empirical results in Table 1 (see Barth and Boriboonsomsin [28]).Table 1
Values of parameters affecting vehicle fuel consumption.
Parameters
φ
k
N
V
s
μ
g
η
t
f
C
d
η
S
C
r
ρ
Values
1
0.2
16–48 r/s
2–8 L
44
9.81
0.45
0.4
0.6
2.1–5.6 m2
0.01
1.20 kg/m3In this paper, we consider a medium-duty vehicle, a van manufactured by Chinese Jianghuai Shuailing, Inc., and the vehicle factors areV
s
=
4.5 L, S
=
7 m2, and N
=
41.6 r/s. Based on the values in Table 1, we have C
1
=
0.851, C
2
=
6.313
×
10
-
5, and C
3
=
1.686.The relationship between vehicle velocity and fuel consumption has been widely explored in literature. One representative result can be attributed to Carslawa et al. [29]. In order to validate our model, we empirically examine the relationship between v
i
j and ω
i
j and compare the empirical result with that obtained in Carslawa et al. [29]. We fix C
1
=
0.851, C
2
=
6.313
×
10
-
5, C
3
=
1.686, M
i
j
=
1500 kg, θ
i
j
=
0, and d
i
j
=
1000 m and increase v
i
j from 1.0 to 30 (m/s) with 0.1 as the step length. The total number of values for v
i
j would be 291. The relationship mapping between v
i
j and ω
i
j is drawn and compared with the mapping between vehicle speed and CO2 emission in Carslawa et al. [29]. The results are summarized in Figure 2.Figure 2
The relationships between driving speed and CO2 emission and fuel consumption.
(a)
CO2 emission
(b)
Fuel consumptionFrom Figure2, we can observe that our fuel consumption model has a similar curve as illustrated in Carslawa et al. [29]. As the velocity increases, the fuel consumption decreases sharply. If the velocity exceeds a certain threshold, the fuel consumption will increase, but slowly. Thus, our fuel consumption function model is verified.We have so far derived the fuel consumption model and determined the parameters used in the model. According to formula (4), we are able to calculate the entire fuel consumption of all vehicles. Let x
i
j
k be a binary variable. Consider x
i
j
k
=
1 when a directed a
r
c
(
i
,
j
) is serviced by vehicle k and x
i
j
k
=
0 otherwise. The mixed integer programming model for the FCVRP that minimizes the total fuel consumption for all vehicles is formulated as follows:FCVRP:(5)
min
⁡
∑
k
=
1
m
∑
i
=
0
n
∑
j
=
0
n
w
i
j
x
i
j
k
(6)
subject  to
∑
i
=
1
n
∑
j
=
1
n
q
i
x
i
j
k
≤
Q
1
≤
k
≤
m
(7)
q
j
x
i
j
k
≤
Q
i
j
≤
Q
-
q
i
x
i
j
k
i
,
j
∈
A
1
≤
k
≤
m
(8)
∑
j
=
0
n
Q
j
i
-
Q
i
j
=
q
i
i
∈
V
0
(9)
∑
i
=
0
n
∑
j
=
0
n
d
i
j
x
i
j
k
≤
L
1
≤
k
≤
m
(10)
∑
j
=
1
n
∑
k
=
1
m
x
i
j
k
=
1
1
≤
i
≤
n
(11)
∑
i
=
1
n
∑
k
=
1
m
x
i
j
k
=
1
1
≤
j
≤
n
(12)
∑
j
=
1
n
∑
k
=
1
m
x
0
j
k
=
∑
i
=
1
n
∑
k
=
1
m
x
i
0
k
=
m
1
≤
i
,
j
≤
n
(13)
∑
i
,
j
∈
H
×
H
x
i
j
k
≤
H
-
1
,
H
⊂
V
k
,
H
≠
⊘
,
(14)
x
i
j
k
=
1
t
h
e
k
t
h
v
e
h
i
c
l
e
t
r
a
v
e
r
s
e
a
r
c
i
,
j
0
o
t
h
e
r
w
i
s
e
(15)
Q
i
j
≥
0
i
,
j
∈
A
.The objective function (5) is the total fuel consumption for a feasible delivery schedule, and ω
i
j is calculated according to formula (4). Constraint (6) are vehicle loading capacity constraints. Constraint (7) ensure that a vehicle is not overloaded on any arc it travels. Constraint (8) indicate the loading quantity is decreased by q
i after visiting customer i. Constraint (9) are the vehicle traveling distance constraints. Constraints (10) and (11) are routing constraints, meaning each customer is served by only one vehicle. Constraint (12) ensure all vehicles start and end at the DC. Constraint (13) ensures that each vehicle route is a simple cycle, where V
k is the set of customers serviced by vehicle k
(
1
≤
k
≤
m
). Finally constraints (14) and (15) are variable integrity and nonnegativity requirements.


### 3.3. Complexity Analysis of the FCVRP Model

The following theorem specifies the relationship between FCVRP and CVRP.Theorem 1.
When it holds thatr
≫
1, v
i
j
=
v for (
i
,
j
)
∈
A, z
i
=
z for i
∈
V, the FCVRP can be reduced to CVRP.Proof.
ω
i
j in the objective function can be expressed as follows:(16)
ω
i
j
=
C
1
d
i
j
v
i
j
+
C
2
M
i
j
g
d
i
j
sin
⁡
θ
i
j
+
C
3
v
i
j
2
d
i
j
+
M
i
j
g
d
i
j
C
r
cos
⁡
θ
i
j
=
C
1
d
i
j
v
+
C
2
C
3
v
2
d
i
j
+
r
Q
+
Q
i
j
g
d
i
j
C
r
≈
C
1
d
i
j
v
+
C
2
C
3
v
2
d
i
j
+
r
Q
g
d
i
j
C
r
=
C
1
v
+
C
2
C
3
v
2
+
r
Q
g
C
r
c
i
j
=
β
c
i
j
.
Sinceβ is a constant that is independent of vehicle route selection, the fuel consumption for traveling from customer i to customer j can be replaced by the length of a
r
c
(
i
,
j
), c
i
j. To minimize the total fuel consumption is equivalent to minimizing the total lengths of all vehicle routes, given the constraints on the vehicle traveling distances. Therefore, Theorem 1 holds.
Since CVRP is a special case of FCVRP, the computational complexity of FCVRP is higher than CVRP. The following argument elaborates the complexity analysis from two perspectives: the size of the solution space and the complexity of improvement operations in solutions.
First, letΩ
E and Ω
C denote the solution space for FCVRP and CVRP, respectively. Based on Theorem 1, we have Ω
C
⊂
Ω
E. One feasible solution to CVRP is also a feasible solution to FCVRP. We use the following notations to determine the exact relationship between the two sets.(i)
k is the number of vehicles.
(ii)
n
i
s is the number of customers serviced by vehicle i.
(iii)
u is the number of vehicles satisfying n
i
s
=
1; we have 0
≤
u
≤
n.
(iv)
k
m
i
n is the minimum number of vehicles required when there are u vehicles; each of these vehicles services only one customer in its route.
(v)
K is the number of those vehicles that can serve at least 2 customers in its route (n
i
s
≥
2).
We havek
∈
[
k
m
i
n
,
n
], and (17)
k
m
i
n
=
u
+
K
m
i
n
,
K
m
i
n
=
∑
i
=
1
n
q
i
-
Q
u
Q
K
=
k
-
u
≥
k
m
i
n
-
u
=
K
m
i
n
,
K
≤
n
2
n
i
s
e
v
e
n
K
≤
n
-
1
2
n
i
s
o
d
d
∑
i
=
1
k
n
i
s
=
∑
i
=
1
u
n
i
s
+
∑
i
=
u
+
1
k
n
i
s
=
u
+
∑
i
=
u
+
1
k
n
i
s
=
n
1
≤
s
≤
U
n
k
,where Q
u is the total demand of u customers and U
n
k is the total number of ways to separate n customers into k groups that can be serviced by k vehicles. U
n
k is just the number of combinations (n, k). For example, there are two ways to separate four customers to two groups, 2-2 or 1–3. It means that we can use one of the vehicles to serve two customers and the other vehicle to serve the remaining two customers or we can use one vehicle to serve one customer and the other vehicle to serve the remaining three customers.
For CVRP, we have(18)
Ω
C
=
∑
k
=
k
m
i
n
n
∑
s
=
1
U
n
k
C
s
·
∏
i
=
u
+
1
k
n
i
s
+
1
-
1
!
2
=
∑
k
=
k
m
i
n
n
∑
s
=
1
U
n
k
C
s
·
∏
i
=
u
+
1
k
n
i
s
!
2
,where C
s is the number of different combination ways for a certain separating method s.
For FCVRP, we have(19)
Ω
E
=
∑
k
=
k
m
i
n
n
∑
s
=
1
U
n
k
C
s
·
∏
i
=
u
+
1
k
n
i
s
+
1
-
1
!
=
2
K
∑
k
=
k
m
i
n
n
∑
s
=
1
U
n
k
C
s
·
∏
i
=
u
+
1
k
n
i
s
!
2
.
Thus, we haveΩ
E
≥
2
K
m
i
n
·
Ω
C. Due to K
m
i
n
≥
1, we are able to obtain that the number of feasible solutions to FCVRP is at least twice that to CVRP.
Next, we evaluate the four common types of solution improvement operations for FCVRP:2-opt,or-opt,exchange, andswap. The selection criterion for these operations is whether the total fuel consumption can be improved. From Figures 3 and 4, we can see that2-opt andor-opt operations may only change the route of one vehicle, whereasexchange andswap operations may change the routes of two vehicles.Figure 3
The2-opt andor-opt operations.
(a)
2-opt
(b)
or-optFigure 4
Theexchange andswap operations.
(a)
Exchange
(b)
SwapFrom formula (4), Q
i
j is required to calculate the fuel consumption in FCVRP. In order to evaluate the fuel consumption increment, the changes of Q
i
j caused by the four operations must be considered. On the contrary, in CVRP only the difference between the total length of newly added arcs and that of deleted arcs needs to be considered to evaluate objective increment. Because k
m
i
n
≥
2, we obtain the following results on the complexity for one step of operation for the four operations: (20)
c
o
m
p
l
e
x
i
t
y
E
2
-
o
p
t
=
O
j
+
1
-
i
-
1
=
O
i
+
p
-
i
=
O
p
≤
O
n
k
≈
O
n
k
m
i
n
≤
O
n
c
o
m
p
l
e
x
i
t
y
E
o
r
-
o
p
t
=
O
t
-
i
=
O
p
+
3
=
O
p
≤
O
n
k
≈
O
n
k
m
i
n
≤
O
n
c
o
m
p
l
e
x
i
t
y
E
e
x
c
h
a
n
g
e
=
O
b
+
O
d
≤
O
n
k
+
n
k
-
1
≈
O
2
n
k
m
i
n
≤
O
n
c
o
m
p
l
e
x
i
t
y
E
s
w
a
p
=
O
b
+
O
d
≤
O
n
k
+
n
k
-
1
≈
O
2
n
k
m
i
n
≤
O
n
.According to complexity theory, these four operations complexities areO
(
n
) for FCVRP. However, the results for CVRP are merely O
(
1
). Combining the results of Ω
E
≥
2
K
m
i
n
·
Ω
C (K
m
i
n
≥
1), we can conclude that FCVRP is more complicated and requires more time to solve than CVRP.


## 3.1. Problem Statement

The research problem we investigate is defined as follows. The transportation network consists of a distribution center (DC) denoted by0 and a set of n customers: V
0
=
{
1,2
,
…
,
n
}. Each customer demands a given number of goods that are distributed from the DC. The DC and customers are all located in a given three-dimensional space. The position of each customer is described using the spacial coordinates with meter as unit, (
x
i
,
y
i
,
z
i
)
(
0
≤
i
≤
n
), where x
i and y
i are horizontal coordinates and z
i is vertical coordinate. The DC holds a set of vehicles for delivery purposes, but the exact number of vehicles to be used is unknown and must be determined optimally. Each vehicle has a loading capacity of Q with kilogram (kg) as its unit, and the curb weight of the vehicle is given by r
·
Q (r
>
0). The demand of each customer is given by q
i that must satisfy 0
≤
q
i
≤
Q, 1
≤
i
≤
n. The Euclidean distance between any two customers in V
0 is calculated as d
i
j
=
(
x
i
-
x
j
)
2
+
(
y
i
-
y
j
)
2
+
(
z
i
-
z
j
)
2. For any two customers that have the same vertical coordinates, their plane distance is hence c
i
j
=
(
x
i
-
x
j
)
2
+
(
y
i
-
y
j
)
2. Let v
i
j denote the speed of the vehicle traveling from customer i to customer j and Q
i
j denote the loading weight of the vehicle traversing the directed a
r
c
(
i
,
j
). In addition, we have the following assumptions.(i)
All vehicles are identical; that is, they have the same type of engine, fuel consumption rate, and loading capacity.
(ii)
The road gradient between any two customers is approximated by the difference between their vertical coordinates. Each directed arc has a unique road gradient angle.
(iii)
The traveling speed in the transportation network for all vehicles is the same for the same arc and different for different arcs. The details about the derivation of vehicle traveling speed are elaborated in Section3.
(iv)
The fuel consumption is determined by engine operations.
(v)
Each vehicle must start and end at the DC.
(vi)
The loading capacity constraint for each vehicle cannot be violated.
(vii)
Each customer must be serviced once and only once and by a single vehicle.
(viii)
Each vehicle has a given maximum traveling distanceL.We must determine an optimal number of vehicles and their optimal delivery routes such that the total fuel consumption for all vehicles is minimized. The resulting problem is called fuel consumption vehicle routing problem or FCVRP. The main difference between FCVRP and VRP model lies in the objective function where we consider minimizing total fuel consumption instead of total operations cost.


## 3.2. The FCVRP Model

In this subsection, we first analyze the factors that affect the fuel consumption rate (fuel consumption amount per time unit) and then formulate the problem as mixed integer programming model.We begin with an existing fuel consumption rate model following Barth et al. [27]: (1)
F
R
=
φ
k
·
N
·
V
s
+
P
/
η
μ
P
=
P
t
r
a
c
t
η
t
f
+
P
a
c
c
P
t
r
a
c
t
=
M
·
a
+
M
·
g
sin
⁡
θ
+
0.5
C
d
ρ
S
·
v
2
+
M
·
g
·
C
r
cos
⁡
θ
v
1000
,where FR is the fuel consumption rate with gallon/second as the unit while all the other denotations are the factors that determine fuel consumption. These factors can be categorized into the following two groups.The first group contains all factors that are irrelevant to vehicle routing decisions:φ: the air-fuel-ratio, N: the operating engine speed, μ: the fuel consumption coefficient, η
t
f: the traditional efficiency, C
d: the aerodynamic drag coefficient, S: the vehicle’s frontal area size, ρ: the air density, k: the engine fraction factor, V
s: the engine discharge rate, g: the gravity coefficient that is equal to 9.81 in this paper, P
a
c
c: the other vehicle energy requirements, η: the engine efficiency parameter, and C
r: the roll damping coefficient. The second group contains all factors that are directly relevant to vehicle routing decisions: d: the vehicle traveling distance, M: the combined weight of the vehicle itself and the loaded goods, θ: the angle degree of road gradient, v: the vehicle traveling speed, and a: the vehicle acceleration rate that is equal to 0 in this paper.Note that the values ofd, M, θ, and v can change according to various distribution and routing results in reality. For example, v is determined by the vehicle’s route and speed limit, M is determined by vehicle visiting sequences, and d is determined by the degrees of road gradients in a route. Consequently, we must incorporate a dynamic driving status in the model. The vehicle driving status between customers i and j can be described using the second-class factors d
i
j, M
i
j, θ
i
j, and v
i
j and is shown in Figure 1.Figure 1
The vehicle driving status when going uphill and downhill.
(a)
Driving downhill
(b)
Driving uphillThese two groups of factors play different roles in calculating the fuel consumption coefficientω
i
j of the directed a
r
c
(
i
,
j
). Group 1 factors are constants (C
1, C
2, and C
3 in the following formula), while group 2 factors are arc-specific parameters. The detailed formula for ω
i
j is as follows: (2)
ω
i
j
=
FR
·
t
=
C
1
d
i
j
v
i
j
+
C
2
M
i
j
g
d
i
j
sin
⁡
θ
i
j
+
C
3
v
i
j
2
d
i
j
+
M
i
j
g
d
i
j
C
r
cos
⁡
θ
i
j
,where C
1
=
φ
k
N
V
s
/
μ, C
2
=
φ
/
(
1000
η
μ
η
t
f
), and C
3
=
0.5
C
d
ρ
S.In formula (2), we can see that ω
i
j is a function of M
i
j, θ
i
j, d
i
j, and v
i
j. The first three values are predetermined in the problem, and v
i
j is determined by the two distances from each customer to the city center: (3)
v
i
j
=
v
m
i
n
+
u
d
i
+
u
d
j
2
u
d
·
v
m
a
x
-
v
m
i
n
,where v
m
a
x is the highest speed limit in the given urban area, v
m
i
n is the vehicle speed in the downtown area, u
d is the maximum distance between the border of the downtown area and the border of the suburban area, and u
d
i and u
d
j are the distances from customers i and j to the city center, respectively, satisfying max
⁡
{
u
d
i
∣
1
≤
i
≤
n
}
≤
u
d. City center is considered as a traffic congestion factor that affects fuel consumption. Vehicle can travel at a higher speed when it is farther away from the city center. To summarize, the vehicle fuel consumption from customer i to customer j
(
1
≤
i
≠
j
≤
n
) can be calculated as follows: (4)
ω
i
j
=
f
i
j
M
i
j
,
d
i
j
,
θ
i
j
,
v
i
j
=
f
1
i
j
+
f
2
i
j
f
2
i
j
>
0
f
1
i
j
f
2
i
j
≤
0
f
1
i
j
=
C
1
d
i
j
v
i
j
f
2
i
j
=
C
2
M
i
j
g
d
i
j
sin
⁡
θ
i
j
+
C
3
v
i
j
2
d
i
j
+
M
i
j
g
d
i
j
C
r
cos
⁡
θ
i
j
M
i
j
=
r
Q
+
Q
i
j
θ
i
j
=
arcsin
⁡
z
j
-
z
i
d
i
j
,where f
1
i
j is the fuel consumption caused by engine usage and f
2
i
j is the fuel consumption caused by driving on an upward gradient road. Note that when vehicle is driving on a downward gradient road, large values of θ
i
j can lead to negative values of f
2
i
j. This situation makes no sense in practice, and therefore when this case occurs, we make ω
i
j
=
f
1
i
j.The constant parameters in formula (4) can be determined from formula (2) and the empirical results in Table 1 (see Barth and Boriboonsomsin [28]).Table 1
Values of parameters affecting vehicle fuel consumption.
Parameters
φ
k
N
V
s
μ
g
η
t
f
C
d
η
S
C
r
ρ
Values
1
0.2
16–48 r/s
2–8 L
44
9.81
0.45
0.4
0.6
2.1–5.6 m2
0.01
1.20 kg/m3In this paper, we consider a medium-duty vehicle, a van manufactured by Chinese Jianghuai Shuailing, Inc., and the vehicle factors areV
s
=
4.5 L, S
=
7 m2, and N
=
41.6 r/s. Based on the values in Table 1, we have C
1
=
0.851, C
2
=
6.313
×
10
-
5, and C
3
=
1.686.The relationship between vehicle velocity and fuel consumption has been widely explored in literature. One representative result can be attributed to Carslawa et al. [29]. In order to validate our model, we empirically examine the relationship between v
i
j and ω
i
j and compare the empirical result with that obtained in Carslawa et al. [29]. We fix C
1
=
0.851, C
2
=
6.313
×
10
-
5, C
3
=
1.686, M
i
j
=
1500 kg, θ
i
j
=
0, and d
i
j
=
1000 m and increase v
i
j from 1.0 to 30 (m/s) with 0.1 as the step length. The total number of values for v
i
j would be 291. The relationship mapping between v
i
j and ω
i
j is drawn and compared with the mapping between vehicle speed and CO2 emission in Carslawa et al. [29]. The results are summarized in Figure 2.Figure 2
The relationships between driving speed and CO2 emission and fuel consumption.
(a)
CO2 emission
(b)
Fuel consumptionFrom Figure2, we can observe that our fuel consumption model has a similar curve as illustrated in Carslawa et al. [29]. As the velocity increases, the fuel consumption decreases sharply. If the velocity exceeds a certain threshold, the fuel consumption will increase, but slowly. Thus, our fuel consumption function model is verified.We have so far derived the fuel consumption model and determined the parameters used in the model. According to formula (4), we are able to calculate the entire fuel consumption of all vehicles. Let x
i
j
k be a binary variable. Consider x
i
j
k
=
1 when a directed a
r
c
(
i
,
j
) is serviced by vehicle k and x
i
j
k
=
0 otherwise. The mixed integer programming model for the FCVRP that minimizes the total fuel consumption for all vehicles is formulated as follows:FCVRP:(5)
min
⁡
∑
k
=
1
m
∑
i
=
0
n
∑
j
=
0
n
w
i
j
x
i
j
k
(6)
subject  to
∑
i
=
1
n
∑
j
=
1
n
q
i
x
i
j
k
≤
Q
1
≤
k
≤
m
(7)
q
j
x
i
j
k
≤
Q
i
j
≤
Q
-
q
i
x
i
j
k
i
,
j
∈
A
1
≤
k
≤
m
(8)
∑
j
=
0
n
Q
j
i
-
Q
i
j
=
q
i
i
∈
V
0
(9)
∑
i
=
0
n
∑
j
=
0
n
d
i
j
x
i
j
k
≤
L
1
≤
k
≤
m
(10)
∑
j
=
1
n
∑
k
=
1
m
x
i
j
k
=
1
1
≤
i
≤
n
(11)
∑
i
=
1
n
∑
k
=
1
m
x
i
j
k
=
1
1
≤
j
≤
n
(12)
∑
j
=
1
n
∑
k
=
1
m
x
0
j
k
=
∑
i
=
1
n
∑
k
=
1
m
x
i
0
k
=
m
1
≤
i
,
j
≤
n
(13)
∑
i
,
j
∈
H
×
H
x
i
j
k
≤
H
-
1
,
H
⊂
V
k
,
H
≠
⊘
,
(14)
x
i
j
k
=
1
t
h
e
k
t
h
v
e
h
i
c
l
e
t
r
a
v
e
r
s
e
a
r
c
i
,
j
0
o
t
h
e
r
w
i
s
e
(15)
Q
i
j
≥
0
i
,
j
∈
A
.The objective function (5) is the total fuel consumption for a feasible delivery schedule, and ω
i
j is calculated according to formula (4). Constraint (6) are vehicle loading capacity constraints. Constraint (7) ensure that a vehicle is not overloaded on any arc it travels. Constraint (8) indicate the loading quantity is decreased by q
i after visiting customer i. Constraint (9) are the vehicle traveling distance constraints. Constraints (10) and (11) are routing constraints, meaning each customer is served by only one vehicle. Constraint (12) ensure all vehicles start and end at the DC. Constraint (13) ensures that each vehicle route is a simple cycle, where V
k is the set of customers serviced by vehicle k
(
1
≤
k
≤
m
). Finally constraints (14) and (15) are variable integrity and nonnegativity requirements.


## 3.3. Complexity Analysis of the FCVRP Model

The following theorem specifies the relationship between FCVRP and CVRP.Theorem 1.
When it holds thatr
≫
1, v
i
j
=
v for (
i
,
j
)
∈
A, z
i
=
z for i
∈
V, the FCVRP can be reduced to CVRP.Proof.
ω
i
j in the objective function can be expressed as follows:(16)
ω
i
j
=
C
1
d
i
j
v
i
j
+
C
2
M
i
j
g
d
i
j
sin
⁡
θ
i
j
+
C
3
v
i
j
2
d
i
j
+
M
i
j
g
d
i
j
C
r
cos
⁡
θ
i
j
=
C
1
d
i
j
v
+
C
2
C
3
v
2
d
i
j
+
r
Q
+
Q
i
j
g
d
i
j
C
r
≈
C
1
d
i
j
v
+
C
2
C
3
v
2
d
i
j
+
r
Q
g
d
i
j
C
r
=
C
1
v
+
C
2
C
3
v
2
+
r
Q
g
C
r
c
i
j
=
β
c
i
j
.
Sinceβ is a constant that is independent of vehicle route selection, the fuel consumption for traveling from customer i to customer j can be replaced by the length of a
r
c
(
i
,
j
), c
i
j. To minimize the total fuel consumption is equivalent to minimizing the total lengths of all vehicle routes, given the constraints on the vehicle traveling distances. Therefore, Theorem 1 holds.
Since CVRP is a special case of FCVRP, the computational complexity of FCVRP is higher than CVRP. The following argument elaborates the complexity analysis from two perspectives: the size of the solution space and the complexity of improvement operations in solutions.
First, letΩ
E and Ω
C denote the solution space for FCVRP and CVRP, respectively. Based on Theorem 1, we have Ω
C
⊂
Ω
E. One feasible solution to CVRP is also a feasible solution to FCVRP. We use the following notations to determine the exact relationship between the two sets.(i)
k is the number of vehicles.
(ii)
n
i
s is the number of customers serviced by vehicle i.
(iii)
u is the number of vehicles satisfying n
i
s
=
1; we have 0
≤
u
≤
n.
(iv)
k
m
i
n is the minimum number of vehicles required when there are u vehicles; each of these vehicles services only one customer in its route.
(v)
K is the number of those vehicles that can serve at least 2 customers in its route (n
i
s
≥
2).
We havek
∈
[
k
m
i
n
,
n
], and (17)
k
m
i
n
=
u
+
K
m
i
n
,
K
m
i
n
=
∑
i
=
1
n
q
i
-
Q
u
Q
K
=
k
-
u
≥
k
m
i
n
-
u
=
K
m
i
n
,
K
≤
n
2
n
i
s
e
v
e
n
K
≤
n
-
1
2
n
i
s
o
d
d
∑
i
=
1
k
n
i
s
=
∑
i
=
1
u
n
i
s
+
∑
i
=
u
+
1
k
n
i
s
=
u
+
∑
i
=
u
+
1
k
n
i
s
=
n
1
≤
s
≤
U
n
k
,where Q
u is the total demand of u customers and U
n
k is the total number of ways to separate n customers into k groups that can be serviced by k vehicles. U
n
k is just the number of combinations (n, k). For example, there are two ways to separate four customers to two groups, 2-2 or 1–3. It means that we can use one of the vehicles to serve two customers and the other vehicle to serve the remaining two customers or we can use one vehicle to serve one customer and the other vehicle to serve the remaining three customers.
For CVRP, we have(18)
Ω
C
=
∑
k
=
k
m
i
n
n
∑
s
=
1
U
n
k
C
s
·
∏
i
=
u
+
1
k
n
i
s
+
1
-
1
!
2
=
∑
k
=
k
m
i
n
n
∑
s
=
1
U
n
k
C
s
·
∏
i
=
u
+
1
k
n
i
s
!
2
,where C
s is the number of different combination ways for a certain separating method s.
For FCVRP, we have(19)
Ω
E
=
∑
k
=
k
m
i
n
n
∑
s
=
1
U
n
k
C
s
·
∏
i
=
u
+
1
k
n
i
s
+
1
-
1
!
=
2
K
∑
k
=
k
m
i
n
n
∑
s
=
1
U
n
k
C
s
·
∏
i
=
u
+
1
k
n
i
s
!
2
.
Thus, we haveΩ
E
≥
2
K
m
i
n
·
Ω
C. Due to K
m
i
n
≥
1, we are able to obtain that the number of feasible solutions to FCVRP is at least twice that to CVRP.
Next, we evaluate the four common types of solution improvement operations for FCVRP:2-opt,or-opt,exchange, andswap. The selection criterion for these operations is whether the total fuel consumption can be improved. From Figures 3 and 4, we can see that2-opt andor-opt operations may only change the route of one vehicle, whereasexchange andswap operations may change the routes of two vehicles.Figure 3
The2-opt andor-opt operations.
(a)
2-opt
(b)
or-optFigure 4
Theexchange andswap operations.
(a)
Exchange
(b)
SwapFrom formula (4), Q
i
j is required to calculate the fuel consumption in FCVRP. In order to evaluate the fuel consumption increment, the changes of Q
i
j caused by the four operations must be considered. On the contrary, in CVRP only the difference between the total length of newly added arcs and that of deleted arcs needs to be considered to evaluate objective increment. Because k
m
i
n
≥
2, we obtain the following results on the complexity for one step of operation for the four operations: (20)
c
o
m
p
l
e
x
i
t
y
E
2
-
o
p
t
=
O
j
+
1
-
i
-
1
=
O
i
+
p
-
i
=
O
p
≤
O
n
k
≈
O
n
k
m
i
n
≤
O
n
c
o
m
p
l
e
x
i
t
y
E
o
r
-
o
p
t
=
O
t
-
i
=
O
p
+
3
=
O
p
≤
O
n
k
≈
O
n
k
m
i
n
≤
O
n
c
o
m
p
l
e
x
i
t
y
E
e
x
c
h
a
n
g
e
=
O
b
+
O
d
≤
O
n
k
+
n
k
-
1
≈
O
2
n
k
m
i
n
≤
O
n
c
o
m
p
l
e
x
i
t
y
E
s
w
a
p
=
O
b
+
O
d
≤
O
n
k
+
n
k
-
1
≈
O
2
n
k
m
i
n
≤
O
n
.According to complexity theory, these four operations complexities areO
(
n
) for FCVRP. However, the results for CVRP are merely O
(
1
). Combining the results of Ω
E
≥
2
K
m
i
n
·
Ω
C (K
m
i
n
≥
1), we can conclude that FCVRP is more complicated and requires more time to solve than CVRP.


## 4. A Two-Objective Hybrid Local Search Algorithm for Solving FCVRP

In literature, capacitated vehicle routing problem is solved mainly through various heuristics. Since fuel consumption vehicle routing problem is more difficult than capacitated vehicle routing problem, these well-established heuristics for capacitated vehicle routing problem are not sufficient for our problem. In addition, it is usually required that a satisfactory solution is obtained within a reasonable computational time. Thus, in order to solve fuel consumption vehicle routing problem efficiently, we design a new algorithm that improves an existing hybrid local search approach used in both problems. This algorithm is based on the following analysis of the impact of the road gradient on the relationship between two problems.


### 4.1. The Impact of Road Gradient

Our proposed approach is primarily based on the analysis of the impact of the road gradient on capacitated and fuel consumption vehicle routing problems. This impact is illustrated in the following example (two scenarios) below.A fuel consumption vehicle routing problem example consisting of one distribution center and 99 customers is generated from the benchmark instance kroa100 in TSP library. Assume that only one vehicle is required to service these 99 customers and that the location of the DC is given by coordinates(
1380,939
). The optimal total traveling distance for kroa100 is known to be 21282 m. The location of the city center is defined as the average coordinates of all customers and distribution center. The city radius u
d is the maximum distance from all the customers or the distribution center to the city center. In the first scenario, we generate all vertical coordinates z
i for the distribution center and all customers randomly in order to add road gradient to the problem instance. These coordinates along with other parameters are summarized in Table 2.Table 2
The problem instance generated from kroa100.
DC and customers
z (km)
q (kg)
Value of parameters
1
0
0
l
=
0.001 km
C
r
=
0.01
2–20
0.02
30
r
=
0.5
C
1
=
0.851
21–40
0.03
40
Q
=
5000 kg
C
2
=
6.313
×
10
-
5
41–60
0.04
50
v
m
a
x
=
25 m/s
C
3
=
1.686
61–80
0.05
60
v
m
i
n
=
5 m/s
81–100
0.06
70
g
=
9.81From Table2, the total demand of 99 customers equals 4970 kg, and the loading capacity of each vehicle is 5000 kg. Therefore, one vehicle is sufficient to service all customers in terms of the total loading weight. According to Theorem 1, the optimal solution to fuel consumption vehicle routing problem in this case is also the optimal solution to kroa100 (capacitated vehicle routing problem). The length of the total traveling distance is 21282
×
l
=
21282
×
0.0001km = 21.282 km. Associated with this optimal solution, two routing schedules with opposite directions can be generated, and their corresponding fuel consumption can also be calculated. The result is shown in Figure 5.Figure 5
The comparison of fuel consumption of driving clockwise and anticlockwise.
(a)
Clockwise
(b)
AnticlockwiseFrom Figure5, the vehicle that travels the same distance of 21.282 km in opposite directions consumes different levels of fuel: 4749.513 g and 5054.377 g. The difference is a result of the existence of road gradient since vehicles consume more fuel when they travel uphill than downhill. This example demonstrates that when road gradient exists, total fuel consumption of opposite vehicle routes for the same optimal sequence (thus same total distance) can have approximately 6% difference. Therefore, a simple application of existing capacitated vehicle routing problem algorithms to fuel consumption vehicle routing problem is not reliable. However, those algorithms can certainly guide solutions of fuel consumption vehicle routing problem. This is validated in the second scenario below.In the second scenario, we further evaluate how road gradient affects the relationships between two problems. To do this, we fix all thez
i parameter values for the distribution center and the customers and let l take 101 consecutive values: 0.001,0.00101,0.00102
,
…
,
0.002 (km). These l values are defined as the increment of the horizontal plane distance between two locations in the network. That is, the horizontal distance between any two customers in the entire network is increased by l. Through this way, we can alter the degree of road gradient by changing the ratio of vertical distance and horizontal distance. These l values are used to simulate 101 geographic environments with different road gradients. In addition, based on the solutions in Figure 5, we randomly generate an integer number n
1 that satisfies 1
<
n
1
≤
91 and then randomly rearrange the visiting sequence of 10 customers from n
1 to n
1
+
9 to generate 1000 neighborhood solutions. The correlation between the total traveling distance and the total fuel consumption is evaluated through the 1000 solutions. The correlation coefficient is defined as C
o
e
f. Besides, we also define an indicator S
l
o
p
e
D
e
g
r
e
e to measure the average road gradient. S
l
o
p
e
D
e
g
r
e
e is calculated as follows: (21)
S
l
o
p
e
D
e
g
r
e
e
=
∑
k
=
1
K
V
k
n
V
k
=
∑
i
=
1
n
k
-
1
s
d
S
i
,
S
i
+
1
+
s
d
S
n
k
,
S
1
s
d
i
j
=
z
i
-
z
j
d
i
j
z
i
≥
z
j
z
j
-
z
i
d
i
j
z
i
<
z
j
,where K stands for the number of vehicles in solution S and n
k stands for the number of customers served by vehicle k.The mapping ofS
l
o
p
e
D
e
g
r
e
e against C
o
e
f is shown in Figure 6. We can see that when S
l
o
p
e
D
e
g
r
e
e
≤
9
%, C
o
e
f
>
0.9 and that as S
l
o
p
e
D
e
g
r
e
e increases, C
o
e
f decreases. When l
=
0.001 in Figure 5, S
l
o
p
e
D
e
g
r
e
e
=
12.63
% and C
o
e
f
=
0.81. The details regarding the 1000 pairs of total distances and total fuel consumption are described in Figure 7.Figure 6
Relationship betweenS
l
o
p
e
D
e
g
r
e
e and C
o
e
f.Figure 7
Relationship between distance and fuel consumption.


### 4.2. Solving Strategy Design

In China, the requirement on the degree of road gradient for inter- and intracity highways is less than 12%. In many cities, the average degree of road gradientS
l
o
p
e
D
e
g
r
e
e is usually less than 7%. From Figure 6, when S
l
o
p
e
D
e
g
r
e
e
=
7
%, the correlation coefficient between fuel consumption and traveling distance satisfies C
o
e
f
≥
0.95. According to the relationship, we can claim that the capacitated vehicle routing problem’s optimal solutions are highly correlated with fuel consumption vehicle routing problem’s optimal solutions in our case where road slope is reasonable. However, combining the first scenario, we find the difference between the two problems solutions is still significant. Thus, given a capacitated vehicle routing problem solution, we must adjust it through a way until it becomes a fuel consumption vehicle routing problem solution.Based on the above observation, we design the two-objective hybrid local search (TOHLS) algorithm to solve the fuel consumption vehicle routing problem. The main idea behind our approach is to divide the solution procedure into two stages, and in each stage we solve an optimization problem towards a different objective function. In the first stage, an optimal solution to capacitated vehicle routing problem, in which we minimize the total traveling distance, is obtained using a hybrid of several existing local search heuristics in literature. The obtained solution can be used in two ways to calculate the total fuel consumption. One way is to directly calculate the total fuel consumption offline using the route sequence generated from this solution. We call this approach a hybrid local search (HLS) algorithm. The other way is to use it as an input for the second stage. In the second stage, the capacitated vehicle routing problem optimal solution in the first stage is improved by iteratively adjusting the traveling directions towards lower fuel consumption (new objective) until a satisfactory solution is obtained. This approach is our two-objective hybrid local search algorithm. The details about the algorithm that incorporates2-opt,or-opt,exchange, andswap are shown in Algorithm 1.Algorithm 1:Two-objective hybrid local search algorithm.
(1) Read ProblemInformation and ParameterInformation;
(2) EstimateSlopeDegreebased on Landscape of distribution area;
(3)  InputT;
(4)  DetermineT
1 and T
2;
(5)  Solution = InitialSolution();
(6)  BestSolution = Solution;
//∗
∗
At first stage, the objective is minimizing the length of solution according to CVRP model
∗
∗//
(7)  StartTime = clock();
(8)  While EndTime-StartTime <T
1 do
(9)    ImproveStrategy = RandChoose(2-opt, or-opt, exchange, swap);
(10)NextSolution = ImproveStrategy(BestSolution);
(11)   If FunctionOf CVRP(NextSolution) < FunctionOf CVRP(BestSolution)
(12)    BestSolution = NextSolution;
(13)   else
(14)    EndTime = clock();
(15)    Continue do while;
(16)   EndIf
(17)  EndWhile
//∗
∗
At second stage, the objective is minimizing the energy consumption of solution according to FCVRP model
∗
∗//
(18)  StartTime = clock();
(19)  While EndTime-StartTime <T
2 do
(20)   ImproveStrategy = RandChoose(2-opt, or-opt, exchange, swap);
(21)   NextSolution = ImproveStrategy(BestSolution);
(22)   If FunctionOf FCVRP(NextSolution) < FunctionOf FCVRP(BestSolution)
(23)    BestSolution = NextSolution;
(24)   else
(25)    EndTime = clock();
(26)    Continue do while;
(27)   EndIf
(28)  EndWhile
(29)  Return BestSolution;A key issue in implementing the aforementioned approach is the allocation of limited computational resource. It is usually required in practice that the dynamic problem setting change should be completed in a given time periodT. In order to efficiently utilize available computational resource, we allocate T into the two stages based on two factors. The first factor is the ratio of the operational complexity of fuel consumption vehicle routing problem to that of capacitated vehicle routing problem, n
/
k
m
i
n, and the second factor is the fuel-distance correlation coefficient, C
o
e
f. The specific allocation is as follows:(22)
T
=
T
1
+
T
2
T
1
=
α
T
α
=
k
m
i
n
C
o
e
f
n
-
n
-
k
m
i
n
C
o
e
f
,where T
1 is the running time for Stage 1 of the two-objective hybrid local search algorithm, T
2 is the running time for Stage 2, n is the number of customers, C
o
e
f is the correlation coefficient, and k
m
i
n is the minimum number of vehicles required in the routing schedule. The values of C
o
e
f for various S
l
o
p
e
D
e
g
r
e
e are shown in Table 3.Table 3
The relationship betweenS
l
o
p
e
D
e
g
r
e
e and C
o
e
f.
S
l
o
p
e
D
e
g
r
e
e
0
(0,1%]
(1%, 2%]
(2%, 3%]
(3%, 4%]
(4%, 5%]
(5%, 8%]
≥8%
C
o
e
f
0.99
0.98
0.97
0.96
0.95
0.94
0.90
0.80


## 4.1. The Impact of Road Gradient

Our proposed approach is primarily based on the analysis of the impact of the road gradient on capacitated and fuel consumption vehicle routing problems. This impact is illustrated in the following example (two scenarios) below.A fuel consumption vehicle routing problem example consisting of one distribution center and 99 customers is generated from the benchmark instance kroa100 in TSP library. Assume that only one vehicle is required to service these 99 customers and that the location of the DC is given by coordinates(
1380,939
). The optimal total traveling distance for kroa100 is known to be 21282 m. The location of the city center is defined as the average coordinates of all customers and distribution center. The city radius u
d is the maximum distance from all the customers or the distribution center to the city center. In the first scenario, we generate all vertical coordinates z
i for the distribution center and all customers randomly in order to add road gradient to the problem instance. These coordinates along with other parameters are summarized in Table 2.Table 2
The problem instance generated from kroa100.
DC and customers
z (km)
q (kg)
Value of parameters
1
0
0
l
=
0.001 km
C
r
=
0.01
2–20
0.02
30
r
=
0.5
C
1
=
0.851
21–40
0.03
40
Q
=
5000 kg
C
2
=
6.313
×
10
-
5
41–60
0.04
50
v
m
a
x
=
25 m/s
C
3
=
1.686
61–80
0.05
60
v
m
i
n
=
5 m/s
81–100
0.06
70
g
=
9.81From Table2, the total demand of 99 customers equals 4970 kg, and the loading capacity of each vehicle is 5000 kg. Therefore, one vehicle is sufficient to service all customers in terms of the total loading weight. According to Theorem 1, the optimal solution to fuel consumption vehicle routing problem in this case is also the optimal solution to kroa100 (capacitated vehicle routing problem). The length of the total traveling distance is 21282
×
l
=
21282
×
0.0001km = 21.282 km. Associated with this optimal solution, two routing schedules with opposite directions can be generated, and their corresponding fuel consumption can also be calculated. The result is shown in Figure 5.Figure 5
The comparison of fuel consumption of driving clockwise and anticlockwise.
(a)
Clockwise
(b)
AnticlockwiseFrom Figure5, the vehicle that travels the same distance of 21.282 km in opposite directions consumes different levels of fuel: 4749.513 g and 5054.377 g. The difference is a result of the existence of road gradient since vehicles consume more fuel when they travel uphill than downhill. This example demonstrates that when road gradient exists, total fuel consumption of opposite vehicle routes for the same optimal sequence (thus same total distance) can have approximately 6% difference. Therefore, a simple application of existing capacitated vehicle routing problem algorithms to fuel consumption vehicle routing problem is not reliable. However, those algorithms can certainly guide solutions of fuel consumption vehicle routing problem. This is validated in the second scenario below.In the second scenario, we further evaluate how road gradient affects the relationships between two problems. To do this, we fix all thez
i parameter values for the distribution center and the customers and let l take 101 consecutive values: 0.001,0.00101,0.00102
,
…
,
0.002 (km). These l values are defined as the increment of the horizontal plane distance between two locations in the network. That is, the horizontal distance between any two customers in the entire network is increased by l. Through this way, we can alter the degree of road gradient by changing the ratio of vertical distance and horizontal distance. These l values are used to simulate 101 geographic environments with different road gradients. In addition, based on the solutions in Figure 5, we randomly generate an integer number n
1 that satisfies 1
<
n
1
≤
91 and then randomly rearrange the visiting sequence of 10 customers from n
1 to n
1
+
9 to generate 1000 neighborhood solutions. The correlation between the total traveling distance and the total fuel consumption is evaluated through the 1000 solutions. The correlation coefficient is defined as C
o
e
f. Besides, we also define an indicator S
l
o
p
e
D
e
g
r
e
e to measure the average road gradient. S
l
o
p
e
D
e
g
r
e
e is calculated as follows: (21)
S
l
o
p
e
D
e
g
r
e
e
=
∑
k
=
1
K
V
k
n
V
k
=
∑
i
=
1
n
k
-
1
s
d
S
i
,
S
i
+
1
+
s
d
S
n
k
,
S
1
s
d
i
j
=
z
i
-
z
j
d
i
j
z
i
≥
z
j
z
j
-
z
i
d
i
j
z
i
<
z
j
,where K stands for the number of vehicles in solution S and n
k stands for the number of customers served by vehicle k.The mapping ofS
l
o
p
e
D
e
g
r
e
e against C
o
e
f is shown in Figure 6. We can see that when S
l
o
p
e
D
e
g
r
e
e
≤
9
%, C
o
e
f
>
0.9 and that as S
l
o
p
e
D
e
g
r
e
e increases, C
o
e
f decreases. When l
=
0.001 in Figure 5, S
l
o
p
e
D
e
g
r
e
e
=
12.63
% and C
o
e
f
=
0.81. The details regarding the 1000 pairs of total distances and total fuel consumption are described in Figure 7.Figure 6
Relationship betweenS
l
o
p
e
D
e
g
r
e
e and C
o
e
f.Figure 7
Relationship between distance and fuel consumption.


## 4.2. Solving Strategy Design

In China, the requirement on the degree of road gradient for inter- and intracity highways is less than 12%. In many cities, the average degree of road gradientS
l
o
p
e
D
e
g
r
e
e is usually less than 7%. From Figure 6, when S
l
o
p
e
D
e
g
r
e
e
=
7
%, the correlation coefficient between fuel consumption and traveling distance satisfies C
o
e
f
≥
0.95. According to the relationship, we can claim that the capacitated vehicle routing problem’s optimal solutions are highly correlated with fuel consumption vehicle routing problem’s optimal solutions in our case where road slope is reasonable. However, combining the first scenario, we find the difference between the two problems solutions is still significant. Thus, given a capacitated vehicle routing problem solution, we must adjust it through a way until it becomes a fuel consumption vehicle routing problem solution.Based on the above observation, we design the two-objective hybrid local search (TOHLS) algorithm to solve the fuel consumption vehicle routing problem. The main idea behind our approach is to divide the solution procedure into two stages, and in each stage we solve an optimization problem towards a different objective function. In the first stage, an optimal solution to capacitated vehicle routing problem, in which we minimize the total traveling distance, is obtained using a hybrid of several existing local search heuristics in literature. The obtained solution can be used in two ways to calculate the total fuel consumption. One way is to directly calculate the total fuel consumption offline using the route sequence generated from this solution. We call this approach a hybrid local search (HLS) algorithm. The other way is to use it as an input for the second stage. In the second stage, the capacitated vehicle routing problem optimal solution in the first stage is improved by iteratively adjusting the traveling directions towards lower fuel consumption (new objective) until a satisfactory solution is obtained. This approach is our two-objective hybrid local search algorithm. The details about the algorithm that incorporates2-opt,or-opt,exchange, andswap are shown in Algorithm 1.Algorithm 1:Two-objective hybrid local search algorithm.
(1) Read ProblemInformation and ParameterInformation;
(2) EstimateSlopeDegreebased on Landscape of distribution area;
(3)  InputT;
(4)  DetermineT
1 and T
2;
(5)  Solution = InitialSolution();
(6)  BestSolution = Solution;
//∗
∗
At first stage, the objective is minimizing the length of solution according to CVRP model
∗
∗//
(7)  StartTime = clock();
(8)  While EndTime-StartTime <T
1 do
(9)    ImproveStrategy = RandChoose(2-opt, or-opt, exchange, swap);
(10)NextSolution = ImproveStrategy(BestSolution);
(11)   If FunctionOf CVRP(NextSolution) < FunctionOf CVRP(BestSolution)
(12)    BestSolution = NextSolution;
(13)   else
(14)    EndTime = clock();
(15)    Continue do while;
(16)   EndIf
(17)  EndWhile
//∗
∗
At second stage, the objective is minimizing the energy consumption of solution according to FCVRP model
∗
∗//
(18)  StartTime = clock();
(19)  While EndTime-StartTime <T
2 do
(20)   ImproveStrategy = RandChoose(2-opt, or-opt, exchange, swap);
(21)   NextSolution = ImproveStrategy(BestSolution);
(22)   If FunctionOf FCVRP(NextSolution) < FunctionOf FCVRP(BestSolution)
(23)    BestSolution = NextSolution;
(24)   else
(25)    EndTime = clock();
(26)    Continue do while;
(27)   EndIf
(28)  EndWhile
(29)  Return BestSolution;A key issue in implementing the aforementioned approach is the allocation of limited computational resource. It is usually required in practice that the dynamic problem setting change should be completed in a given time periodT. In order to efficiently utilize available computational resource, we allocate T into the two stages based on two factors. The first factor is the ratio of the operational complexity of fuel consumption vehicle routing problem to that of capacitated vehicle routing problem, n
/
k
m
i
n, and the second factor is the fuel-distance correlation coefficient, C
o
e
f. The specific allocation is as follows:(22)
T
=
T
1
+
T
2
T
1
=
α
T
α
=
k
m
i
n
C
o
e
f
n
-
n
-
k
m
i
n
C
o
e
f
,where T
1 is the running time for Stage 1 of the two-objective hybrid local search algorithm, T
2 is the running time for Stage 2, n is the number of customers, C
o
e
f is the correlation coefficient, and k
m
i
n is the minimum number of vehicles required in the routing schedule. The values of C
o
e
f for various S
l
o
p
e
D
e
g
r
e
e are shown in Table 3.Table 3
The relationship betweenS
l
o
p
e
D
e
g
r
e
e and C
o
e
f.
S
l
o
p
e
D
e
g
r
e
e
0
(0,1%]
(1%, 2%]
(2%, 3%]
(3%, 4%]
(4%, 5%]
(5%, 8%]
≥8%
C
o
e
f
0.99
0.98
0.97
0.96
0.95
0.94
0.90
0.80


## 5. Computational Studies

### 5.1. Experiment Design Based on VRP Benchmark Instances

Since fuel consumption vehicle routing problem considering road gradient has rarely been studied in the VRP research community, it is difficult to directly compare our approach with the other cutting-edge algorithms by solving the same benchmark problems. Thus, we design 60 fuel consumption vehicle routing problem instances based on the 20 capacitated vehicle routing problem benchmark problems proposed in Golden et al. [30]. In the 20 problems, the number of customers ranges from 200 to 483. All customers and the DC are located on a horizontal plane where the position of the distribution center is (
0,0
) and all customers are within a circle that has a radius of R. The vertical coordinates (z
i, 0
≤
i
≤
n) and a city center are added to generate the fuel consumption vehicle routing problem instances.(i)
The DC and the city center are both located at(
0,0
,
0
).
(ii)
z
i’s for the 483 customers and the DC are shown in Table 4.
(iii)
The loading capacity of each vehicleQ is set to be 5000 kg, and the demand of each customer is assigned accordingly.
(iv)
The arc length between any two customers is converted to three possible values, 5000, 3000 and 1000, according to the radius of location circle,R.Table 4
Thez
i values for DC and customers 1–483 of 20 instances.
DC and customers
z
i (m)
Customer
z
i (m)
Customer
z
i (m)
Customer
z
i (m)
0–25
100
126–150
75
251–275
50
376–400
25
26–50
95
151–175
70
276–300
45
401–425
20
51–75
90
176–200
65
301–325
40
426–450
15
76–100
85
201–225
60
326–350
35
451–475
10
101–125
80
226–250
55
351–375
30
476–483
5The 20 capacitated vehicle routing problem instances along with 3R values produce the 60 fuel consumption vehicle routing problem instances. In order to test the performance of two-objective hybrid local search algorithm, we use a hybrid of three local search heuristics, petal, nearest neighborhood, and insertion to generate optimal capacitated vehicle routing problem solutions in the first stage. In the second stage, we locally adjust the solutions from the first stage to improve them towards the direction of reducing fuel consumption, and to finally solve the 60 instances. Recall that we can also generate fuel consumption vehicle routing problem solutions from hybrid local search by using solutions obtained from the first stage. The maximum running time limit T takes 4 values: 2 minutes, 5 minutes, 10 minutes, and 30 minutes. The other parameters of fuel consumption vehicle routing problem model are shown in Tables 4 and 5. Our computational results show that two-objective hybrid local search algorithm significantly outperforms hybrid local search.Table 5
The parameter values in the model.
Parameter
Value
r
1
Q
2000 kg
v
m
a
x
25 m/s
v
m
i
n
5 m/s
g
9.81
u
d
R
C
r
0.01
C
1
0.851
C
2
6.313
×
10
-
5
C
3
1.686The results are shown in Tables6–8. The problem instances are entitled as “G
o
l
d
e
n
+
n
+
(
n
u
m
),” where n is the number of customers and n
u
m is the n
u
mth instance. In Tables 6–8, the objective function values (i.e., the total fuel consumption) obtained by hybrid local search algorithm for the four different time limits are given. However, in order to make the comparison between two-objective hybrid local search algorithm and hybrid local search more clear, we present the results of two-objective hybrid local search algorithm as the relative percentages of the results of hybrid local search.Table 6
Comparison between HLS and TOHLS whenR
=
5000 (m).
Num
Instances
SlopeDegree (%)
HLS (fuel consumption g)
TOHLS (percentage of HLS)
T
=
2
T
=
5
T
=
10
T
=
30
T
=
2
T
=
5
T
=
10
T
=
30
1
Golden200
0.85
15362
14340
14004
13764
95.05
96.30
96.51
99.20
2
Golden240-1
0.46
23257
21787
21001
20532
94.52
95.66
97.95
99.84
3
Golden240-2
0.62
109506
102754
99391
96499
95.01
96.00
96.15
101.96
4
Golden252
0.62
112108
104938
100907
98835
94.58
95.71
95.32
101.21
5
Golden255
0.44
194771
180280
174719
173283
94.32
96.44
95.94
100.15
6
Golden280
0.55
20332
18756
18192
17650
93.22
94.40
96.66
101.68
7
Golden300
0.80
79789
73536
70472
69125
91.26
94.96
95.75
97.75
8
Golden320-1
0.61
25602
23703
22353
22237
90.58
93.99
95.95
96.14
9
Golden320-2
0.68
93881
87009
82038
81793
91.42
93.39
95.04
96.35
10
Golden323
0.56
152931
141203
134915
133108
90.84
93.42
94.68
98.60
11
Golden360-1
0.70
25209
22926
21707
21624
89.22
92.47
95.96
97.18
12
Golden360-2
1.01
58882
54023
51342
50186
89.37
91.46
95.85
96.66
13
Golden396
0.84
82670
75431
70798
69388
88.33
92.53
95.82
95.28
14
Golden399
0.84
125088
112599
106819
104470
88.31
91.73
95.78
101.08
15
Golden400
0.78
27921
25116
23953
23622
87.98
91.05
96.15
96.46
16
Golden420
1.25
49122
44707
41595
41042
85.99
90.30
94.03
98.54
17
Golden440
0.86
29214
26152
24487
24001
85.97
90.74
93.02
101.06
18
Golden480-1
0.95
27753
24649
23155
22552
84.85
89.12
94.48
100.61
19
Golden480-2
1.03
73902
66191
61692
60096
85.61
89.63
92.02
97.52
20
Golden483
0.85
103757
93077
85876
84082
86.27
89.15
91.53
95.74
Average
0.77
—
—
—
—
90.14
92.92
95.23
98.65Table 7
Comparison between HLS and TOHLS whenR
=
3000 (m).
Num
Instances
SlopeDegree (%)
HLS (fuel consumption g)
TOHLS (percentage of HLS)
T
=
2
T
=
5
T
=
10
T
=
30
T
=
2
T
=
5
T
=
10
T
=
30
1
Golden200
1.42
9983
9339
9129
9029
94.32
95.79
96.88
99.11
2
Golden240-1
0.77
15435
14540
13899
13810
93.74
94.86
95.48
99.29
3
Golden240-2
1.03
67896
63440
61547
60481
92.61
95.48
95.52
96.24
4
Golden252
1.03
69959
64928
62091
62468
92.22
94.34
94.86
95.58
5
Golden255
0.74
118322
109121
106592
105149
93.11
95.40
95.90
98.63
6
Golden280
0.91
13350
12445
11908
11803
91.82
94.07
94.31
97.20
7
Golden300
1.34
50545
46835
44908
44338
90.39
93.66
94.41
96.02
8
Golden320-1
1.02
17023
15794
14930
14553
90.48
92.43
94.86
100.15
9
Golden320-2
1.13
59402
54070
52388
51780
90.08
92.75
96.41
95.18
10
Golden323
0.93
93293
85550
81135
80035
89.97
92.84
94.43
95.61
11
Golden360-1
1.17
16717
15115
14527
14134
88.93
91.87
94.11
95.32
12
Golden360-2
1.69
39053
35573
33553
33521
86.99
91.22
93.09
98.01
13
Golden396
1.41
53097
47672
45872
44972
87.73
91.10
91.23
98.94
14
Golden399
1.41
76742
70105
65006
63782
86.67
89.76
92.27
96.44
15
Golden400
1.30
18574
16678
15825
15412
87.68
90.96
93.04
94.67
16
Golden420
2.08
34960
31362
29610
29080
84.86
89.15
91.19
93.99
17
Golden440
1.43
19582
17665
16584
16197
85.65
90.22
91.69
98.27
18
Golden480-1
1.59
18661
16569
15587
15049
83.66
87.86
92.20
95.61
19
Golden480-2
1.72
48506
43162
40209
39808
83.34
87.72
90.92
95.39
20
Golden483
1.41
63871
56936
53273
52020
83.88
88.47
92.92
96.05
Average
1.28
—
—
—
—
88.91
92.00
93.79
96.79Table 8
Comparison between HLS and TOHLS whenR
=
1000 (m).
Num
Instances
SlopeDegree (%)
HLS (fuel consumption g)
TOHLS (percentage of HLS)
T
=
2
T
=
5
T
=
10
T
=
30
T
=
2
T
=
5
T
=
10
T
=
30
1
Golden200
4.25
5031
4755
4540
4527
92.11
93.04
94.31
98.37
2
Golden240-1
2.30
7914
7443
7070
6980
92.54
95.00
95.05
94.72
3
Golden240-2
3.10
26936
25023
24356
23936
91.07
92.99
93.08
98.58
4
Golden252
3.08
28830
27057
25759
25705
91.39
93.54
93.24
99.22
5
Golden255
2.21
42113
39456
37685
37518
92.96
94.40
96.44
95.84
6
Golden280
2.74
7045
6508
6231
6202
91.74
93.70
96.71
95.79
7
Golden300
4.01
23740
22107
20943
20607
88.71
90.40
92.69
96.77
8
Golden320-1
3.06
8941
8138
7851
7771
89.85
92.41
93.49
92.93
9
Golden320-2
3.38
26673
24542
23180
23232
90.12
91.07
93.53
96.97
10
Golden323
2.80
33992
31158
29856
29131
90.31
91.61
95.54
93.69
11
Golden360-1
3.52
8805
8082
7652
7480
87.53
89.98
92.43
92.40
12
Golden360-2
5.07
22894
21090
19853
19529
86.09
88.43
89.98
94.14
13
Golden396
4.22
26017
23479
22470
21643
85.28
88.65
91.27
93.27
14
Golden399
4.22
28684
25974
24655
24092
86.14
87.81
92.28
93.48
15
Golden400
3.91
9716
8805
8250
8177
85.54
88.54
90.49
96.86
16
Golden420
6.24
22858
20569
19385
19022
81.61
85.18
89.50
90.21
17
Golden440
4.30
10397
9319
8831
8539
85.32
86.89
90.22
92.46
18
Golden480-1
4.75
10139
9093
8375
8296
83.44
86.36
91.15
91.12
19
Golden480-2
5.15
25464
22499
21190
20716
82.06
86.61
91.06
91.72
20
Golden483
4.23
24684
22102
20643
20038
84.01
86.84
91.92
92.35
Average
3.83
—
—
—
—
87.89
90.17
92.72
94.54


### 5.2.  Results and Analysis

From Table6, when z
i take values in Table 4 and R
=
5000 (m), the average slope S
l
o
p
e
D
e
g
r
e
e of the 20 Golden instances is 0.77% which is less than 1%. In this case, within given computational time two-objective hybrid local search algorithm can effectively improve the performance of hybrid local search. When T
=
2,5
,
10 (minutes), the results of two-objective hybrid local search algorithm on 20 instances are all better than those of hybrid local search. The average solution percentages under these three time durations are 90.13%, 92.92%, and 95.23%, respectively. As the running time increases, the effectiveness of two-objective hybrid local search algorithm unfortunately decreases. When T
=
30 (minutes), the results of two-objective hybrid local search algorithm for Golden240-2, Golden252, Golden255, Golden280, Golden399, Golden440, and Golden480-1 are slightly worse than those of hybrid local search. This is because fuel consumption vehicle routing problem is more complicated than capacitated vehicle routing problem. When the running time is sufficiently long, the performance of hybrid local search is close to that of two-objective hybrid local search algorithm. However, two-objective hybrid local search algorithm overall outperforms hybrid local search. Another observation that can be made from Table 6 is that the resulting difference between two-objective hybrid local search algorithm and hybrid local search increases as the problem size grows. This can be attributed to the fact that larger-size problems require longer running time for the algorithms to converge.In Tables7 and 8, R value is decreased to 3000 (m) and 1000 (m), while z
i still take values in Table 4. The average slope for the 20 problem instances is increased to 1.28% and 3.83%. Although the slope is changed, the effectiveness of two-objective hybrid local search algorithm with respect to n and T has similar trend in Tables 7 and 8 as in Table 6. We can also see that the superiority of two-objective hybrid local search algorithm over hybrid local search is more significant as the slope increases. This seems contradictive to the previous argument that larger slope should lead to smaller correlation between fuel consumption and distance. However, this can be explained from two aspects. First, the slope limit for practical roads is less than 12%, but we confine the average slope in problem instances to be less than 6%. Under this level of slope, the fuel consumption is still highly correlated with routing distance (as shown in Figure 2(a)). Second, with other parameters fixed, the increase in the degree of road gradient leads to a longer converging time for the algorithm.We select one of the testing instances, Golden200 from Table6 with T
=
30 (minutes), and plot the solution converging processes of the two algorithms within 30 minutes in Figure 8. This figure is used to better demonstrate the superiority of two-objective hybrid local search algorithm to hybrid local search. In Figure 8, local optimal total fuel consumption obtained by hybrid local search and two-objective hybrid local search algorithm in every minute is recorded and plotted. For this problem case, we have S
l
o
p
e
D
e
g
r
e
e
=
0.85
% from Table 6 and C
o
e
f
=
0.95 from Table 4. Based on the above information, we can obtain T
1
=
579.66 seconds and that e initial fuel consumption = 8324 (g). From Figure 8, the objective function values of two-objective hybrid local search algorithm decrease sharply in the first stage, because the correlation coefficient is 0.95 (very significant) and minimizing the total traveling distance can minimize the total fuel consumption.Figure 8
The optimization procedures of HLS and TOHLS for Golden200 whenT
=
30.


## 5.1. Experiment Design Based on VRP Benchmark Instances

Since fuel consumption vehicle routing problem considering road gradient has rarely been studied in the VRP research community, it is difficult to directly compare our approach with the other cutting-edge algorithms by solving the same benchmark problems. Thus, we design 60 fuel consumption vehicle routing problem instances based on the 20 capacitated vehicle routing problem benchmark problems proposed in Golden et al. [30]. In the 20 problems, the number of customers ranges from 200 to 483. All customers and the DC are located on a horizontal plane where the position of the distribution center is (
0,0
) and all customers are within a circle that has a radius of R. The vertical coordinates (z
i, 0
≤
i
≤
n) and a city center are added to generate the fuel consumption vehicle routing problem instances.(i)
The DC and the city center are both located at(
0,0
,
0
).
(ii)
z
i’s for the 483 customers and the DC are shown in Table 4.
(iii)
The loading capacity of each vehicleQ is set to be 5000 kg, and the demand of each customer is assigned accordingly.
(iv)
The arc length between any two customers is converted to three possible values, 5000, 3000 and 1000, according to the radius of location circle,R.Table 4
Thez
i values for DC and customers 1–483 of 20 instances.
DC and customers
z
i (m)
Customer
z
i (m)
Customer
z
i (m)
Customer
z
i (m)
0–25
100
126–150
75
251–275
50
376–400
25
26–50
95
151–175
70
276–300
45
401–425
20
51–75
90
176–200
65
301–325
40
426–450
15
76–100
85
201–225
60
326–350
35
451–475
10
101–125
80
226–250
55
351–375
30
476–483
5The 20 capacitated vehicle routing problem instances along with 3R values produce the 60 fuel consumption vehicle routing problem instances. In order to test the performance of two-objective hybrid local search algorithm, we use a hybrid of three local search heuristics, petal, nearest neighborhood, and insertion to generate optimal capacitated vehicle routing problem solutions in the first stage. In the second stage, we locally adjust the solutions from the first stage to improve them towards the direction of reducing fuel consumption, and to finally solve the 60 instances. Recall that we can also generate fuel consumption vehicle routing problem solutions from hybrid local search by using solutions obtained from the first stage. The maximum running time limit T takes 4 values: 2 minutes, 5 minutes, 10 minutes, and 30 minutes. The other parameters of fuel consumption vehicle routing problem model are shown in Tables 4 and 5. Our computational results show that two-objective hybrid local search algorithm significantly outperforms hybrid local search.Table 5
The parameter values in the model.
Parameter
Value
r
1
Q
2000 kg
v
m
a
x
25 m/s
v
m
i
n
5 m/s
g
9.81
u
d
R
C
r
0.01
C
1
0.851
C
2
6.313
×
10
-
5
C
3
1.686The results are shown in Tables6–8. The problem instances are entitled as “G
o
l
d
e
n
+
n
+
(
n
u
m
),” where n is the number of customers and n
u
m is the n
u
mth instance. In Tables 6–8, the objective function values (i.e., the total fuel consumption) obtained by hybrid local search algorithm for the four different time limits are given. However, in order to make the comparison between two-objective hybrid local search algorithm and hybrid local search more clear, we present the results of two-objective hybrid local search algorithm as the relative percentages of the results of hybrid local search.Table 6
Comparison between HLS and TOHLS whenR
=
5000 (m).
Num
Instances
SlopeDegree (%)
HLS (fuel consumption g)
TOHLS (percentage of HLS)
T
=
2
T
=
5
T
=
10
T
=
30
T
=
2
T
=
5
T
=
10
T
=
30
1
Golden200
0.85
15362
14340
14004
13764
95.05
96.30
96.51
99.20
2
Golden240-1
0.46
23257
21787
21001
20532
94.52
95.66
97.95
99.84
3
Golden240-2
0.62
109506
102754
99391
96499
95.01
96.00
96.15
101.96
4
Golden252
0.62
112108
104938
100907
98835
94.58
95.71
95.32
101.21
5
Golden255
0.44
194771
180280
174719
173283
94.32
96.44
95.94
100.15
6
Golden280
0.55
20332
18756
18192
17650
93.22
94.40
96.66
101.68
7
Golden300
0.80
79789
73536
70472
69125
91.26
94.96
95.75
97.75
8
Golden320-1
0.61
25602
23703
22353
22237
90.58
93.99
95.95
96.14
9
Golden320-2
0.68
93881
87009
82038
81793
91.42
93.39
95.04
96.35
10
Golden323
0.56
152931
141203
134915
133108
90.84
93.42
94.68
98.60
11
Golden360-1
0.70
25209
22926
21707
21624
89.22
92.47
95.96
97.18
12
Golden360-2
1.01
58882
54023
51342
50186
89.37
91.46
95.85
96.66
13
Golden396
0.84
82670
75431
70798
69388
88.33
92.53
95.82
95.28
14
Golden399
0.84
125088
112599
106819
104470
88.31
91.73
95.78
101.08
15
Golden400
0.78
27921
25116
23953
23622
87.98
91.05
96.15
96.46
16
Golden420
1.25
49122
44707
41595
41042
85.99
90.30
94.03
98.54
17
Golden440
0.86
29214
26152
24487
24001
85.97
90.74
93.02
101.06
18
Golden480-1
0.95
27753
24649
23155
22552
84.85
89.12
94.48
100.61
19
Golden480-2
1.03
73902
66191
61692
60096
85.61
89.63
92.02
97.52
20
Golden483
0.85
103757
93077
85876
84082
86.27
89.15
91.53
95.74
Average
0.77
—
—
—
—
90.14
92.92
95.23
98.65Table 7
Comparison between HLS and TOHLS whenR
=
3000 (m).
Num
Instances
SlopeDegree (%)
HLS (fuel consumption g)
TOHLS (percentage of HLS)
T
=
2
T
=
5
T
=
10
T
=
30
T
=
2
T
=
5
T
=
10
T
=
30
1
Golden200
1.42
9983
9339
9129
9029
94.32
95.79
96.88
99.11
2
Golden240-1
0.77
15435
14540
13899
13810
93.74
94.86
95.48
99.29
3
Golden240-2
1.03
67896
63440
61547
60481
92.61
95.48
95.52
96.24
4
Golden252
1.03
69959
64928
62091
62468
92.22
94.34
94.86
95.58
5
Golden255
0.74
118322
109121
106592
105149
93.11
95.40
95.90
98.63
6
Golden280
0.91
13350
12445
11908
11803
91.82
94.07
94.31
97.20
7
Golden300
1.34
50545
46835
44908
44338
90.39
93.66
94.41
96.02
8
Golden320-1
1.02
17023
15794
14930
14553
90.48
92.43
94.86
100.15
9
Golden320-2
1.13
59402
54070
52388
51780
90.08
92.75
96.41
95.18
10
Golden323
0.93
93293
85550
81135
80035
89.97
92.84
94.43
95.61
11
Golden360-1
1.17
16717
15115
14527
14134
88.93
91.87
94.11
95.32
12
Golden360-2
1.69
39053
35573
33553
33521
86.99
91.22
93.09
98.01
13
Golden396
1.41
53097
47672
45872
44972
87.73
91.10
91.23
98.94
14
Golden399
1.41
76742
70105
65006
63782
86.67
89.76
92.27
96.44
15
Golden400
1.30
18574
16678
15825
15412
87.68
90.96
93.04
94.67
16
Golden420
2.08
34960
31362
29610
29080
84.86
89.15
91.19
93.99
17
Golden440
1.43
19582
17665
16584
16197
85.65
90.22
91.69
98.27
18
Golden480-1
1.59
18661
16569
15587
15049
83.66
87.86
92.20
95.61
19
Golden480-2
1.72
48506
43162
40209
39808
83.34
87.72
90.92
95.39
20
Golden483
1.41
63871
56936
53273
52020
83.88
88.47
92.92
96.05
Average
1.28
—
—
—
—
88.91
92.00
93.79
96.79Table 8
Comparison between HLS and TOHLS whenR
=
1000 (m).
Num
Instances
SlopeDegree (%)
HLS (fuel consumption g)
TOHLS (percentage of HLS)
T
=
2
T
=
5
T
=
10
T
=
30
T
=
2
T
=
5
T
=
10
T
=
30
1
Golden200
4.25
5031
4755
4540
4527
92.11
93.04
94.31
98.37
2
Golden240-1
2.30
7914
7443
7070
6980
92.54
95.00
95.05
94.72
3
Golden240-2
3.10
26936
25023
24356
23936
91.07
92.99
93.08
98.58
4
Golden252
3.08
28830
27057
25759
25705
91.39
93.54
93.24
99.22
5
Golden255
2.21
42113
39456
37685
37518
92.96
94.40
96.44
95.84
6
Golden280
2.74
7045
6508
6231
6202
91.74
93.70
96.71
95.79
7
Golden300
4.01
23740
22107
20943
20607
88.71
90.40
92.69
96.77
8
Golden320-1
3.06
8941
8138
7851
7771
89.85
92.41
93.49
92.93
9
Golden320-2
3.38
26673
24542
23180
23232
90.12
91.07
93.53
96.97
10
Golden323
2.80
33992
31158
29856
29131
90.31
91.61
95.54
93.69
11
Golden360-1
3.52
8805
8082
7652
7480
87.53
89.98
92.43
92.40
12
Golden360-2
5.07
22894
21090
19853
19529
86.09
88.43
89.98
94.14
13
Golden396
4.22
26017
23479
22470
21643
85.28
88.65
91.27
93.27
14
Golden399
4.22
28684
25974
24655
24092
86.14
87.81
92.28
93.48
15
Golden400
3.91
9716
8805
8250
8177
85.54
88.54
90.49
96.86
16
Golden420
6.24
22858
20569
19385
19022
81.61
85.18
89.50
90.21
17
Golden440
4.30
10397
9319
8831
8539
85.32
86.89
90.22
92.46
18
Golden480-1
4.75
10139
9093
8375
8296
83.44
86.36
91.15
91.12
19
Golden480-2
5.15
25464
22499
21190
20716
82.06
86.61
91.06
91.72
20
Golden483
4.23
24684
22102
20643
20038
84.01
86.84
91.92
92.35
Average
3.83
—
—
—
—
87.89
90.17
92.72
94.54


## 5.2.  Results and Analysis

From Table6, when z
i take values in Table 4 and R
=
5000 (m), the average slope S
l
o
p
e
D
e
g
r
e
e of the 20 Golden instances is 0.77% which is less than 1%. In this case, within given computational time two-objective hybrid local search algorithm can effectively improve the performance of hybrid local search. When T
=
2,5
,
10 (minutes), the results of two-objective hybrid local search algorithm on 20 instances are all better than those of hybrid local search. The average solution percentages under these three time durations are 90.13%, 92.92%, and 95.23%, respectively. As the running time increases, the effectiveness of two-objective hybrid local search algorithm unfortunately decreases. When T
=
30 (minutes), the results of two-objective hybrid local search algorithm for Golden240-2, Golden252, Golden255, Golden280, Golden399, Golden440, and Golden480-1 are slightly worse than those of hybrid local search. This is because fuel consumption vehicle routing problem is more complicated than capacitated vehicle routing problem. When the running time is sufficiently long, the performance of hybrid local search is close to that of two-objective hybrid local search algorithm. However, two-objective hybrid local search algorithm overall outperforms hybrid local search. Another observation that can be made from Table 6 is that the resulting difference between two-objective hybrid local search algorithm and hybrid local search increases as the problem size grows. This can be attributed to the fact that larger-size problems require longer running time for the algorithms to converge.In Tables7 and 8, R value is decreased to 3000 (m) and 1000 (m), while z
i still take values in Table 4. The average slope for the 20 problem instances is increased to 1.28% and 3.83%. Although the slope is changed, the effectiveness of two-objective hybrid local search algorithm with respect to n and T has similar trend in Tables 7 and 8 as in Table 6. We can also see that the superiority of two-objective hybrid local search algorithm over hybrid local search is more significant as the slope increases. This seems contradictive to the previous argument that larger slope should lead to smaller correlation between fuel consumption and distance. However, this can be explained from two aspects. First, the slope limit for practical roads is less than 12%, but we confine the average slope in problem instances to be less than 6%. Under this level of slope, the fuel consumption is still highly correlated with routing distance (as shown in Figure 2(a)). Second, with other parameters fixed, the increase in the degree of road gradient leads to a longer converging time for the algorithm.We select one of the testing instances, Golden200 from Table6 with T
=
30 (minutes), and plot the solution converging processes of the two algorithms within 30 minutes in Figure 8. This figure is used to better demonstrate the superiority of two-objective hybrid local search algorithm to hybrid local search. In Figure 8, local optimal total fuel consumption obtained by hybrid local search and two-objective hybrid local search algorithm in every minute is recorded and plotted. For this problem case, we have S
l
o
p
e
D
e
g
r
e
e
=
0.85
% from Table 6 and C
o
e
f
=
0.95 from Table 4. Based on the above information, we can obtain T
1
=
579.66 seconds and that e initial fuel consumption = 8324 (g). From Figure 8, the objective function values of two-objective hybrid local search algorithm decrease sharply in the first stage, because the correlation coefficient is 0.95 (very significant) and minimizing the total traveling distance can minimize the total fuel consumption.Figure 8
The optimization procedures of HLS and TOHLS for Golden200 whenT
=
30.


## 6. Conclusions

In this paper, we study the FCVRP in which road gradient is considered as one of the factors to measure fuel consumption. After constructing an MIP model, we present complexity analysis for this FCVRP based on comparison with CVRP. To solve this model, we propose an efficient algorithm called TOHLS. This algorithm is based on a hybrid local search algorithm (HLS) that is also used in this paper to solve FCVRP. Based on the existing CVRP testing problems, 60 FCVRP instances are generated and solved by both HLS and TOHLS. The computational results show that the proposed TOHLS has a better performance than the HLS algorithm in terms of solution qualities.Some important concluding remarks can be summarized as follows. First, the size of solution space of FCVRP is2
K
m
i
n times that of CVRP, and the complexities of common improvement operations including2-opt,or-opt,exchange, andswap are n times that in CVRP. Second, TOHLS algorithm can effectively improve the performance of HLS and reduce the total fuel consumption by 2%–13%. The improvement is more significant for problem instances with limited response time, large number of customers, and average road gradient. Third, it is indicated that the TOHLS is particularly appropriate for FCVRP problems that have large sizes, consider road gradients, and require quick response. Fourthly, it is also worth pointing out that the idea behind the proposed TOHLS can be applied to improve algorithms other than HLS. Thus, one of the most promising future research directions is to apply the two-objective idea to various existing heuristics in CVRP to improve their algorithm performances.There are also several limitations in our research. One of our assumptions is that the road gradient between any two customers is approximated by the difference between their vertical coordinates. This assumption may not be appropriate in the case where there are two city centers located at same geographic attitude but with a mountain somewhere in the middle. In this scenario, fuel consumption for vehicles traveling between the two city centers should be more than the one we proposed. Therefore, experimentally determining the more accurate fuel consumption in such case shall be one of the future research directions. In addition, our current modeling approach simplifies the speed factors and patterns by assuming that speeds are determined by the distance to the city center. However, in practice there are often more than one-road sections connecting customers with the city center, and these road sections often have different characteristics and traffic performance levels. In such case, it will be much more complicated to model the exact speeds between different locations. Thus, a thorough investigation on the speed patterns from a more practical point of view is needed for the future studies. Last but not least, in order to implement our approach, we can utilize the current available real-time traffic data sources, such as FCD, loop detectors, and GPS, to facilitate parameterizing our model. In particular, given the location and transportation situation of a city center, instead of simulation, it could easily adapt our model by generating real traffic data from these resources to be used for calculating the gradient, the speed, the fuel consumption, and the other related parameters. These data can be further used as inputs in our solution approach. And, finally, the optimal fuel consumption could be achieved by selecting the appropriate vehicle routes under the guidance of these advanced devices.



---

*Source: 3713918-2016-03-07.xml*