Analysis of Travel Times and CO 2 Emissions in Time‐Dependent Vehicle Routing

Abstract

Due to the growing concern over environmental issues, regardless of whether companies are going to voluntarily incorporate green policies in practice, or will be forced to do so in the context of new legislation, change is foreseen in the future of transportation management. Assigning and scheduling vehicles to service a pre‐determined set of clients is a common distribution problem. Accounting for time‐dependent travel times between customers, we present a model that considers travel time, fuel, and CO₂ emissions costs. Specifically, we propose a framework for modeling CO₂ emissions in a time‐dependent vehicle routing context. The model is solved via a tabu search procedure. As the amount of CO₂ emissions is correlated with vehicle speed, our model considers limiting vehicle speed as part of the optimization. The emissions per kilometer as a function of speed are minimized at a unique speed. However, we show that in a time‐dependent environment this speed is sub‐optimal in terms of total emissions. This occurs if vehicles are able to avoid running into congestion periods where they incur high emissions. Clearly, considering this trade‐off in the vehicle routing problem has great practical potential. In the same line, we construct bounds on the total amount of emissions to be saved by making use of the standard VRP solutions. As fuel consumption is correlated with CO₂ emissions, we show that reducing emissions leads to reducing costs. For a number of experimental settings, we show that limiting vehicle speeds is desired from a total cost perspective. This namely stems from the trade‐off between fuel and travel time costs.

Keywords

vehicle routing problems time‐dependent travel times green logistics

1. Introduction

The ever‐growing concern over greenhouse gases (GHG) has led many countries to take policy actions aiming at emissions reductions. Most notable is the Kyoto Protocol, which requires countries to reduce a basket of the six major GHG by the year 2012 by 5.2% on average (compared to their 1990 emission levels). Next to this, a number of other initiatives have emerged particularly to control CO₂ emissions. For example, more than 12,000 industrial plants in the EU are subjected to CO₂ caps, enabling the trade of emissions rights between parties. For a comprehensive survey of GHG trade market models, the reader is referred to Springer (2004).

The importance of environmental issues is continuously translated into regulations, which potentially have a tangible impact on supply chain management. As a consequence, there has been an increasing amount of research on the intersection between logistics and environmental factors. Sbihi and Eglese (2007) identified potential combinatorial optimization problems where Green Logistics is relevant. Corbett and Kleindorfer (2001,2001) discussed the integration of environmental management in operations management. Kleindorfer et al. (2001) did so in the context of sustainable operations management. Lee and Klassen (2008) mapped factors that initiated and improved environmental capabilities in small‐ and medium‐sized enterprises over time.

European road freight transport uses considerable amounts of energy (Baumgartner et al. 2008). Vanek and Campbell (1999) note that predictions are that the United Kingdom will meet the Kyoto targets. However, they highlight that within the period from 1985 until 1995, energy use across all sectors grew only by 7% while transport energy use grew by 31%. Similar findings were observed by Léonardi and Baumgartner (2004). They state that in the period 1991–2001 road freight traffic in Germany increased by 40%. Moreover, in 2001 traffic was responsible for about 6% of total CO₂ emissions in Germany. More substantial CO₂ increases are observed in India by Singha et al. (2004), where the CO₂ emissions from road transport in the year 2000 have increased by almost 400% compared to 1985. In the context of examining scenarios for GHG, Yang et al. (2008) mention that in California the transportation sector accounted for over 40% of GHG for 2006, making it by far the largest contributor. Baumgartner et al. (2008) acknowledge that new vehicle designs are more efficient in terms of emissions. However, this is outweighed by the transport growth rate in the EU. Ericsson et al. (2006) mention that CO₂, which is directly related to the consumption of carbon‐based fuel, is regarded as one of the most serious threats to the environment through the greenhouse effect. Globally, transportation accounts for about 21% of CO₂ emissions. In the same spirit, CO₂ is identified as the most important greenhouse gas in the Netherlands, as it accounted for 80% of total emissions in 1995 (see e.g., Kramer et al. 1999). Thus, there is a clear necessity to control CO₂ emissions.

Road transport accounts for a large portion of CO₂ emissions, of which goods transport constitutes a sizeable portion. Thus, there is a need to address environmental concerns in the context of goods transport. Carrier companies may voluntarily adopt green policies if this is aligned with profitability. This could be in the form of GHG trading mechanisms, or when CO₂ becomes a taxable commodity. Another reason for adopting green policies is the marketing potential of a greener company image, for example, controlling the carbon footprint. Furthermore, new regulations might force companies to change practices. It is worth mentioning that the department for environment, food and rural affairs in the United Kingdom values the social cost of carbon between £ 35 and £ 140 per tonne. In essence, pricing carbon emissions leads to an assessment of its economic impact and regulations might be formed accordingly. In conclusion, either for exogenous or endogenous reasons, change is anticipated in transportation management because of environmental factors. We argue that logistics service providers should contemplate how to deal with these issues.

The focus of this article is on incorporating CO₂‐related considerations in road freight distribution, specifically in the framework of the Vehicle Routing Problem (VRP). CO₂ emissions and fuel consumption both depend on the vehicle speed, which changes throughout the day due to congestion. Thus, it is relevant to study the problem in conjunction with time‐dependent travel times, i.e., where the travel time depends on the time of day at which a distance is traversed. Time‐dependency is modeled by partitioning the planing horizon into free flow speed periods and periods with congestion, that is, lower speeds. We introduce a new variant of the VRP that accounts for travel time, fuel, and CO₂ emissions costs. This results in the Emissions‐based Time‐Dependent Vehicle Routing Problem, denoted by E‐TDVRP. The E‐TDVRP builds on the possibility that carrier companies limit the speed of their vehicles. Thus, the vehicle speed limit is explicitly part of the optimization. The traditional Time‐Dependent Vehicle Routing Problem (TDVRP) optimizes exclusively on travel times and does not consider limiting vehicle speed. However, we show that when accounting for fuel, travel time, and emissions, controlling vehicle speed is desirable from a total cost point of view.

The E‐TDVRP is clearly a complex problem, as in addition to the complexity of the TDVRP, it also determines the free flow speed. This implies that one needs to allocate customers to vehicles, determine the exact order in which customers are visited, and set the free flow speed. The free flow speed impacts the resulting travel time function of each arc, and in return, affects the moment vehicles go into congestion. We assume that the congestion speed remains constant, as it is imposed by traffic conditions. This leads to a situation where speeds can be controlled in particular time periods of the day, that is exclusively in free flow periods. The E‐TDVRP can be reduced to two sub‐problems: one where only the CO₂ emissions are taken into account in the optimization (that is, a pure environmental model) and one where only travel times are considered (i.e., a pure logistical cost model). As such, we study the trade‐off between minimizing CO₂ emissions as opposed to minimizing total travel times. In addition, we develop bounds for the potential reduction in CO₂ emissions. These bounds are based on solutions of the standard time‐independent VRP. Since most optimization tools used in industry consider time‐independent travel times, such bounds can concretely aid decision makers in evaluating the maximum reduction in emissions.

The remainder of the article is organized as follows, Section 2 reviews the relevant literature. Section 3 describes the E‐TDVRP model. It also introduces bounds for the potential savings in CO₂ emissions. The solution method is discussed in section 4 The experimental settings and results are presented in section 5 Finally, section 6 highlights the main findings and indicates directions for future research.

2. Literature Review

Van Woensel et al. (2001) highlighted the value of traffic flow information in relation to emissions. Their results showed that calculating emissions under constant speed assumptions can be misleading, with differences of up to 20% in CO₂ emissions on an average day for gasoline vehicles and 11% for diesel vehicles. During congested periods of the day these differences rose 40%. Similar results were shown by Palmer (2008), for a number of roads. Such results are motivated mainly by the fact that CO₂ emissions are proportional to fuel consumption (Kirby et al. 2000), and thus are speed dependent. The relation between emissions and vehicle speed leads to the study of the VRP problem in a time‐dependent framework. In what follows, we first discuss the literature concerning the TDVRP, and then review the literature dealing with routing and emissions.

Assigning and scheduling vehicles with a limited capacity to service a set of clients with known demand, is a problem faced by numerous carrier companies. It has been extensively researched in the literature as the well‐known VRP. For a comprehensive review, the reader is referred to Laporte (2007). In its most standard version, the problem deals with minimizing costs subject to demand satisfaction and vehicle capacity constraints. Each customer is visited by a single vehicle, each vehicle starts and ends its route at the depot. The relevance of the VRP to real‐life practice coupled with the hard nature of the problem has attracted much research. To model reality more accurately, numerous features have been added to the problem. One of these is including speed changes over the day, in an attempt to account for traffic congestion experienced in certain periods of the day.

Lately, a number of researchers incorporated time‐dependent travel times between customers into the VRP, which gave rise to the TDVRP. The objective of the TDVRP, in most cases, is similar to that of the VRP, that is, minimizing costs (Hill and Benton 1992). However, in the TDVRP the travel time cost depends on the time of day a distance is traversed. Modeling time‐dependency is mostly done by associating different speeds to a number of time zones within the planning horizon. Malandraki and Daskin (1992) motivate variability in travel time by random events, such as accidents and cyclic temporal variations in traffic flow. They propose a mixed integer programming formulation for the TDVRP. Malandraki and Dial (1996) propose a dynamic programming formulation to solve the time‐dependent Traveling Salesman Problem (TSP). However, both these articles modeled travel times by discrete step functions where travel times are associated with different time zones. Although this modeling approach does capture variability in travel times, it enables the undesired effect of surpassing. This effect implies that a vehicle departing at a certain time might surpass another vehicle that started traveling earlier. This limitation was discussed by Fleischmann et al. (2004), Ichoua et al. (2003), Nannicini et al. (2010), and Van Woensel et al. (2008). All these articles model time‐dependencies complying with the First‐In First‐Out (FIFO) assumption, which does not allow for surpassing. This is done by using appropriate piecewise linear functions for travel times. In this article, we adopt travel time functions similar to the ones used by Ichoua et al. (2003), and thus adhere to the FIFO assumption.

Ichoua et al. (2003) modeled the TDVRP by partitioning the day into three speed zones, where the speed differences due to congestion were determined by different factors of the free flow speeds. The travel time profiles were constructed by piecewise linear functions. Fleischmann et al. (2004) discuss a general framework for integrating time‐dependent travel times in a number of VRP algorithms. Furthermore, they provide an overview of traffic information systems from which data can be collected. Modeling of time‐dependent travel times would benefit from these data. Based on empirical traffic data, queueing models were developed by Van Woensel (2003) to model congestion, where the model parameters were set to incorporate different traffic flows and weather conditions. The analysis of the data resulted in average speeds for different time zones (see also Van Woensel and Vandaele 2006). These speeds were later used in Van Woensel et al. (2008) to solve the TDVRP with tabu search. Jung and Haghani (2001) proposed a modified genetic algorithm to solve the TDVRP.

Not much research has been conducted on the VRP under minimizing emissions. Cairns (1999) studied the environmental impact of grocery home delivery, but this was done by converting distance into emissions, irrespective of speed changes. The effect of speed changes is incorporated in the work of Palmer (2008). He studied emissions in the context of grocery home delivery vehicles, where real traffic data were used to derive fuel consumption and emissions. A similar detailed methodology was used by Ericsson et al. (2006). Both Palmer (2008) and Ericsson et al. (2006) considered CO₂ minimization as an optimization criteria. Bektaş and Laporte (2011) introduced the pollution routing problem where they accounted for the amount of greenhouse emissions, fuel, travel times, and their costs. The authors present a comprehensive formulation of the problem and solve moderately sized instances. Scott et al. (2010) investigated the influence of the minimization of CO₂ emissions on the solutions to shortest path and traveling salesman problems in freight delivery applications. Real life examples are studied using the road network of Scotland. In a more aggregate view, Sugawara and Niemeier (2002) presented an emissions‐based trip assignment optimization model. They also explored potential emission reduction under the assumption that drivers choose emission minimizing routes. Assessing vehicle emissions can be very complex, as emissions depend on factors such as the age of the vehicle, engine state, engine size, speed, type of fuel, and weight (Taniguchi et al. 2001). For our study, we use speed emission functions from the MEET model (European Commission 1999). In this article, we focus on CO₂ and leave other pollutants for additional research.

3. Description of E‐TDVRP

This section starts with a complete description of the E‐TDVRP model and details the most relevant parts of this model. Section 3.1 elaborates on the computation of the travel times. Section 3.2 explains the computation of the CO₂ emissions and fuel consumptions. Finally, in section 3.3 the bounds on CO₂ emissions are presented.

In general, the VRP is described by a complete directed graph G = (V,A) where V = {0,1,…,n} is a set of vertices and A = {(i,j):i<>j ∈ V} is the set of directed arcs. The vertex 0 denotes the depot; the rest of the vertices represent customers. For each customer, a non‐negative demand

q_{i}

is given (

q_{0} = 0

). A non‐negative cost

c_{ij}

is associated with each arc (i,j). The objective is to find, for a given number of vehicles N, the minimum costs where the following conditions hold: every customer is visited exactly once by one vehicle, all vehicle routes start and end at the depot, and every route has a total demand not exceeding the vehicle capacity Q. This definition is valid for the E‐TDVRP model presented in this study.

The E‐TDVRP differs from the VRP as it considers time‐dependent travel times. Furthermore, it considers fuel and emissions costs. The objective function of the E‐TDVRP is the sum of all these costs. Limiting the free flow speed of the vehicles is examined in this problem. Therefore, in addition to the routing solution the E‐TDVRP has a decision variable

v_{f}

corresponding to the upper limit of the vehicle speed. The speed limit

v_{f}

is considered a tactical choice of the carrier company. Thus,

v_{f}

is imposed on all vehicles, that is, all routes have the same limit.

We define a solution as a set S with s routes

{R_{1}, R_{2}, \dots, R_{s}}

where s ≤ N,

R_{r} = (0, \dots, i, \dots, 0)

, that is, each route begins and ends at the depot. We write

i \in R_{r}

, if the vertex i ≥ 1 is part of the route

R_{r}

(each vertex belongs to exactly one route). We write

(i, j) \in R_{r}

, if i and j are two consecutive vertices in

R_{r}

. An E‐TDVRP solution is defined by the solution set S coupled with a vehicle speed limit

v_{f}

A solution (

S, v_{f}

) results in travel times

TT (S, v_{f})

and emissions

E (S, v_{f})

. The computation of

TT (S, v_{f})

is explained in section 3.1 The computation of

E (S, v_{f})

is discussed in section 3.2

We define three cost factors in the E‐TDVRP: the hourly cost of a driver (with a cost of α €/hour), the cost of fuel (costing β €/liter), and the cost of CO₂ emissions (γ €/kg). Since fuel consumption is directly related to CO₂ emission, we use the factor of h (equal to

\frac{1}{2.7}

liter/kg) for converting CO₂ emissions into fuel consumption, similar to Palmer (2008). The objective function for E‐TDVRP is given by Equation (1).

F (S, v_{f}; α, β, γ) = α TT (S, v_{f}) + (β h + γ) E (S, v_{f})

The first part of the objective function considers the travel time costs. The second part considers the composite costs combining fuel and emissions. We explicitly consider both, as the cost parameters for fuel (β) and emissions (γ) are different.

The E‐TDVRP can be reduced into two special cases. Setting α to zero the model minimizes solely the costs of fuel and CO₂, which is equivalent to minimizing

E (S, v_{f})

, with an objective function value

F (S, v_{f}; 0, β, γ)

. Similarly, setting both β and γ to zero results in a model that minimizes

TT (S, v_{f})

, with an objective function value

F (S, v_{f}; α, 0, 0)

. These special cases facilitate a trade‐off analysis showing the additional travel time required to obtain minimal CO₂ emissions.

For completeness, we summarize the speed‐related notation we will use in the remainder of this section:

v_{f}

: The speed limit set in E‐TDVRP.

v_{c}

: The congestion speed imposed by traffic.

v^{*}

: The speed that yields the optimal CO₂ emission per km value.

v_{f}^{*}

: The optimal speed for

E (S, v_{f})

v_{h}

: The upper bound value of

v_{f}^{*}

v^{'}

: The speed used for computing the upper bound on

E (S, v_{f})

3.1. Determining
$TT (S, v_{f})$

The time‐dependency of travel times throughout the planning horizon, is in essence, driven by changing speeds in different time zones. We subject all links to given speed profiles. This stems from the notion that most motorways, on average, follow the same pattern of having morning and evening congestion periods (see Ichoua et al. 2003 for a similar reasoning). Moreover, collecting data for each link and each time zone is infeasible from an operational standpoint.

Figure 1 provides an illustration of how speeds are translated into travel time profiles. The left side depicts a speed profile that starts with a congestion speed

v_{c}

until time a. After time a the vehicle can travel at free flow speed

v_{f}

. Subjecting a given distance d to the speed profile on the left side of the figure results in the travel time profile on the right side of Figure 1. Note that while the x‐axis for the speed profile is the time of day, the x‐axis for the travel time figure is starting time. For a given distance d and for every starting time, the figure on the right provides the travel time. The main intuition for modeling the profile is that during the first period (up to

a - {TT}_{c}

) it takes

{TT}_{c}

time units to traverse d since, throughout that period the vehicle will be driving with speed

v_{c}

along the entire link. However, starting from time

a - {TT}_{c}

up to point a, the vehicle will be in the transient zone, where it will start traversing the link with speed

v_{c}

and the remainder with speed

v_{f}

. Starting at point a the speed will remain constant at

v_{f}

with the travel time equaling

{TT}_{f}

. Thus, the travel time is a continuous piecewise linear function over the starting times.

Figure 1

The Conversion of Speed into Travel Times

The linearity in the transient zone stems from the stepwise speed change which imposes different speeds over time. The slope can be defined as

\frac{{TT}_{f} - {TT}_{c}}{{TT}_{c}}

. By substituting

{TT}_{c}

with

\frac{d}{v_{c}}

and

{TT}_{f}

with

\frac{d}{v_{f}}

, we obtain that the slope is equal to

\frac{v_{c} - v_{f}}{v_{f}}

, which is independent of d. However, the intersection with the travel time axis is a function of the distance and it is equal to

\frac{(v_{f} - v_{c})}{v_{f}} a + \frac{d}{v_{f}}

. Therefore, the travel time function between customers i and j depends on the distance

d_{ij}

between these customers. We define g(t) as the travel time function associated with any starting time t for Figure 1.

g (t) = {\begin{matrix} {TT}_{c} & if t \leq a - {TT}_{c} \\ \frac{v_{c} - v_{f}}{v_{f}} t + \frac{(v_{f} - v_{c})}{v_{f}} a + {TT}_{f} & if a - {TT}_{c} < t < a \\ {TT}_{f} & if t \geq a \end{matrix}

For starting times within

(0, a - {TT}_{c})

the FIFO is satisfied since the speed associated with these starting times is constant. Given two starting times within this interval t and t + Δ, both will arrive

{TT}_{c}

time units after their departure. Similarly, FIFO holds for starting times after a. The line in the transient zone

(a - {TT}_{c}, a)

can be viewed as a consequence of the FIFO assumption as well. Given two starting times t and t + Δ, both in the transient zone, the arrival times are t + g(t) and t + Δ + g(t + Δ), respectively, the difference between the arrival times of t + Δ and t is

Δ + \frac{v_{c} - v_{f}}{v_{f}} Δ > 0

. Thus, the FIFO assumption holds in the transient zone. Note that in a speed decreasing situation the FIFO assumption holds even for step travel time changes. Nonetheless, for consistency, speed drops are constructed exactly in the same manner as speed increases. We further note that the construction of travel times is equivalent to integrating the distance over the different speeds.

The proposed model is convenient since it requires speed values and the points in time at which the speed changes.

{TT}_{ijt}

represents the travel time between node i and node j when starting at time t. The starting time t belongs to a time zone from the set

{t_{1}, t_{2}, \dots, t_{k}}

. The travel time is computed depending on the specific zone that t belongs to. Equation (2) considers the total travel time associated with a solution S and

v_{f}

TT (S, v_{f}) = \sum_{r} \sum_{t} \sum_{(i, j) \in R_{r}} {TT}_{ijt}

3.2. Determining E(S,v_f)

In this article, we use emission functions provided in the MEET report (European Commission 1999). The function θ(v) provides the emissions in grams per kilometer for speed v. Equation (3) depicts the amount of emissions per km, given that a vehicle is at speed v.

θ (v) = K + av + {bv}^{2} + {cv}^{3} + d \frac{1}{v} + e \frac{1}{v^{2}} + f \frac{1}{v^{3}}

The coefficients (K,a,…,f) differ per vehicle type and size. Here, we focus on heavy duty trucks weighing 32–42 tons. The coefficients for the CO₂ emissions for this specific vehicle category are (K,a,b,c,d,e,f) = (1576, −17.6, 0, 0.00117, 0, 36067, 0). Figure 2 depicts this CO₂ (kg/km) emissions function. This function has a unique minimum and we define

v^{*}

as the integer speed which achieves the lowest CO₂ emissions (

v^{*} = 71

km/hour).

Figure 2

CO₂ Emissions vs. Speed

We denote the amount of CO₂ emissions in grams produced by traversing arc (i,j) at time t with a free flow speed

v_{f}

E_{ijt} (v_{f})

. The average speeds are used to calculate the emissions per km by Equation (3). Multiplication of emissions per km by distances traversed yields the total amount of CO₂ emissions. We define

Ω [d_{ij}, t, v_{f}]

as the average speed for traversing arc (i,j) when leaving i at time zone t, with speed limit

v_{f}

. Consequently,

E_{ijt} (v_{f})

is given by Equation (4).

E_{ijt} (v_{f}) = θ (Ω [d_{ij}, t, v_{f}]) d_{ij}

The objective function for term

E (S, v_{f})

is defined in Equation (5) summing the total CO₂ emissions produced by the different routes r in solution S with speed limit

v_{f}

E (S, v_{f}) = \sum_{r} \sum_{t} \sum_{(i, j) \in R_{r}} E_{ijt} (v_{f})

Both from a practical and an optimization point, we choose to work with integer speeds. Optimizing on

E (S, v_{f})

implies then finding an optimal integer free flow speed applied to all routes r in S. The dependence of

E_{ijt}

on the speeds associated with

d_{ij}

makes the free flow speed

v_{f}

a decision variable. We emphasize that limiting the speed of a vehicle means that in free flow the vehicle's speed is limited. However, in congestion the vehicle is restricted by the congestion speed. In essence, while congestion zones can be seen as constraints, in free flow zones the maximum speed is decided upon.

Modifying the speed profile affects the travel time profiles. As explained in section 1, the change of speed at point a starts affecting the travel times already at point

a - {TT}_{c}

. If there is a speed drop at point a from a certain free flow speed

v_{f}

to a congestion speed

v_{c}

, travel times for a given distance d will start to increase if it is traversed after time

a - \frac{d}{v_{f}}

. If the free‐flow speed is decreased, the travel time profile is affected, since the vehicle will start experiencing congestion at earlier starting times. We demonstrate the effect of free flow speed on the total emissions produced with the example depicted in Figure 3. Let

v_{c} = 40

km/hour and consider two options for free flow speed:

v_{1} = 71

km/hour, and

v_{2} = 72

km/hour, with starting time 200 and a = 500 (in minutes). Setting the free flow speed to

v_{1}

produces 2.8 kg more CO₂ emissions than setting it to

v_{2}

. Moreover, setting the free flow speed to

v_{1}

results in an increase of 15 minutes in travel times, with respect to

v_{2}

Figure 3

Example for Two Free Flow Speeds

Considering optimizing on

E (S, v_{f})

, that is, only on the amount of emissions, let the optimal speed be

v_{f}^{*}

. Proposition 1 shows that only a sub‐set of potential speeds need to be taken into account for the

E (S, v_{f})

optimization. This proposition makes it possible to considerably reduce the search space for this problem.

Proposition

Given

v_{c} < v^{*}

, there exists a

v_{h} > v^{*}

such that

θ (v_{c}) = θ (v_{h})

and

v^{*} \leq v_{f}^{*} \leq v_{h}

For the case of θ(v) being convex having a unique minimum as is in the case of the CO₂ emission function considered, Proposition 1 is straightforward to show. Since

v_{c}

is smaller than

v^{*}

there exists another speed

v_{h}

which is higher than

v^{*}

such that

θ (v_{c}) = θ (v_{h})

. We show that

v_{c} < v_{f}^{*} < v_{h}

for the setting in question.

Proof

Arguing by contradiction, assume that

v_{f}^{*} > v_{h}

. The shape of the emission per km function implies that

θ (v_{f}^{*}) > θ (v_{h}) = θ (v_{c})

. In such a case, being in free flow zones, that is, where the speed is set to

v_{f}^{*}

, will produce higher emissions than in congestion. Any

\tilde{v} \in [v_{c}, v_{h}]

will produce less emissions since

θ (\tilde{v}) < θ (v_{f}^{*})

and thus

v_{f}^{*}

is not optimal. Again by contradiction, assume that

v_{c} < v_{f}^{*} < v^{*}

. For any

\tilde{v} \in [v_{c}, v^{*}]

there exists a

\hat{v} > v^{*}

such that

θ (\hat{v}) = θ (\tilde{v})

. Since for

\hat{v}

the total time spent in congestion will be lower than that for

\tilde{v}

, we conclude that

v^{*} < v_{f}^{*} < v_{h}

As previously mentioned, we only consider integer values for speeds. Thus,

v_{h}

is rounded up to the nearest integer value.

3.3. Bounds for

E (S, v_{f})

The

E (S, v_{f})

on its own is a difficult problem to handle: one needs to find a solution in a time‐dependent setting in combination with setting the free flow speed. In this section we present bounds using the solutions of the standard VRP (i.e., time‐independent). Throughout the years various solution techniques have been developed to tackle this problem. Moreover, from a practical standpoint, most carrier companies developed software solutions for the standard VRP. Hence, bounds based on these basic VRP solutions may be easily computed in practice as well.

The lower bound is realized by traversing the total distance in the VRP solution with a speed

v^{*}

, since this implies the minimum distance traversed using the optimal emissions speed. In essence, the upper bound can be constructed by subjecting the VRP solutions to a speed profile with a single speed drop, similar to Profile I in Figure 4. However, our TDVRP setting is similar to Profile II in Figure 4. For a given distance to be traversed starting at time zero, optimizing CO₂ emissions under Profile II would generate results superior or equivalent to the same optimization under profile I. For minimizing emissions, the optimal performance under profile I is an upper bound on the performance of Profile II. Thus, we construct an upper bound on the total CO₂ emissions by assuming a single speed decrease that is outperformed by a profile consisting of a speed drop followed by a speed increase.

Figure 4

Speed Profiles for the Bounds on E‐TDVRP

We analyze the case of subjecting the VRP solutions to Profile I. We denote the distance of an arbitrary route by d. We distinguish two cases:

If the vehicle is not fast enough to avoid congestion, that is, v < d/a, then the total emissions are given by the emissions in free flow θ(v)av plus the emissions in congestion which are

θ (v_{c}) (d - av)

If the vehicle travels fast enough to avoid congestion, that is, v ≥ d/a, then the total emissions would simply be given by θ(v) times the covered distance d.

According to the above distinction, define

E_{1} (d, v)

and

E_{2} (d, v)

as follows:

\begin{matrix} E_{1} (d, v) & = θ (v) av + θ (v_{c}) (d - av) \\ E_{2} (d, v) & = θ (v) d . \end{matrix}

Then, total emissions as a function of distance d can be written as a function of speed:

E_{d} (v) : = {\begin{matrix} E_{1} (d, v) & if v \in (0, \frac{d}{a}] \\ E_{2} (d, v) & if v \in [\frac{d}{a}, + \infty) \end{matrix}

In our case

E_{1} (d, v)

E_{2} (d, v)

, and θ(v) are convex and have a unique minimum. The problem of finding an optimal speed involves finding the minimum of

E_{d}

\min {\min_{v \in (0, \frac{d}{a}]} E_{1} (d, v), \min_{(v \in [\frac{d}{a}, + \infty)} E_{2} (d, v)} .

Lemma

There exists a universal speed

v^{'} > v^{*}

such that for all a,d > 0 there exists a unique solution

v_{f}^{*}

to problem (6) given by:

v_{f}^{*} = {\begin{matrix} v^{*} & if d \leq {av}^{*} \\ d / a & if {av}^{*} < d < {av}^{'} \\ v^{'} & if d \geq {av}^{'} . \end{matrix}

Proof

E_{1} (d, v)

has a unique optimal

v^{'}

. This can be easily seen by differentiation

\frac{\partial E_{1} (d, v)}{\partial v} = a (θ^{'} (v) v + θ (v) - θ (v_{c})) .

As earlier observed

E_{2} (d, v)

has a unique optimal speed

v^{*}

. Furthermore

E_{1} (d, d / a) = E_{2} (d, d / a)

, so that

E_{d}

is continuous. Now, since by convexity we know that

E_{1}

is decreasing for

v < v^{'}

and increasing for

v > v^{'}

E_{2}

is decreasing for

v < v^{*}

and increasing for

v > v^{*}

it is sufficient to put together

E_{1}

and

E_{2}

, distinguishing between the following three cases.

Case

(i) : d \leq {av}^{*}

E_{d} (v) = {\begin{matrix} E_{1} (v), decreasing & if v \leq d / a \\ E_{2} (v), decreasing & if d / a < v < v^{*} \\ E_{2} (v), increasing & if v^{*} \leq v \end{matrix}

so the minimum value is reached when

v = v^{*}

Case

(ii) : {av}^{*} < d < {av}^{'}

E_{d} (v) = {\begin{matrix} E_{1} (v), decreasing & if v \leq d / a \\ E_{2} (v), increasing & if d / a < v \end{matrix}

so the minimum value is reached when v = d/a.

Case

(iii) : {av}^{'} \leq d

E_{d} (v) = {\begin{matrix} E_{1} (v), decreasing & if v \leq v^{'} \\ E_{1} (v), increasing & if v^{'} < v < d / a \\ E_{2} (v), increasing & if d / a \leq v \end{matrix}

so the minimum value is reached when

v = v^{'}

The importance of Lemma 1 is that for large enough distances,

d \geq {av}^{'}

there exists a single speed

v^{'}

which is optimal under Profile I. We use

v^{'}

to construct the upper bound on

E (S, v_{f})

Let

S^{'}

be the optimal solution for the standard VRP. Let

d_{i}^{'}

be the distance of route

R_{i}

S^{'}

. We arrange the different routes in descending order, with respect to their distance,

S^{'} = {d_{[1]}^{'}, \dots, d_{[s]}^{'}}

. Equation (7) represents a lower bound on the amount of CO₂ emissions produced. The lower bound assumes that all distances can be traversed in

v^{*}

, so that absolute minimum emissions can be achieved.

\sum_{i = 1}^{s} d_{[i]}^{'} θ (v^{*}) \leq E (S, v_{f})

The upper bound is constructed by imposing Profile I with

v_{f} = v^{'}

onto

S^{'}

. We define u as the largest index such that

d_{[u]} > {av}^{'}

. Thus, routes

{d_{[1]}^{'}, \dots, d_{[u]}^{'}}

will run into congestion. However, the routes

{d_{[u + 1]}^{'}, \dots, d_{[s]}^{'}}

will not suffer congestion. Equation (8) depicts this upper bound.

\begin{matrix} E (S, v_{f}) & \leq θ (v^{'}) {uav}^{'} + θ (v_{c}) \sum_{i = 1}^{u} (d_{i}^{'} - {av}^{'}) + θ (v^{'}) \sum_{i = u + 1}^{s} d_{i}^{'} \\ \leq [θ (v^{'}) - θ (v_{c})] {uav}^{'} + θ (v_{c}) \sum_{i = 1}^{u} d_{i}^{'} + θ (v^{'}) \sum_{i = u + 1}^{s} d_{i}^{'} \end{matrix}

Given the standard VRP solution, these bounds are rather straightforward to calculate, and enable decision makers to easily assess the maximal reduction in CO₂ emissions. Furthermore, these bounds are used to validate the proposed solution procedure.

4. Solution Method

We propose a tabu search procedure for the E‐TDVRP. Tabu search was first introduced by Glover (1989,1989). It makes use of adaptive memory to escape local optima. The method has been extensively used for solving the VRP; see Gendreau et al. (1994,1996 Hertz et al. 2000) for examples. Tabu search is also used to deal with the time‐dependent version of the VRP (see Ichoua et al. 2003, Jabali et al. 2009, Van Woensel et al. 2008). The E‐TDVRP model differs from the TDVRP as it includes the free flow speed

v_{f}

as a decision variable. We chose to adapt a tabu search procedure to fit the E‐TDVRP. Essentially, the procedure works on local search principles while updating the

v_{f}

. The algorithm searches a neighborhood with

v_{f}

. After a number of iterations it checks the performance of the best solution so far for different integer values of

v_{f}

. If a value which yields better results is found, the speed is updated and the search continues. Next, we describe the main components of the algorithm. The overall procedure is described in pseudo‐code in Algorithm 1.

Algorithm 1 E‐TDVRP algorithmic structure

Construct initial solution

S_{0}

with

v_{f} = v_{0}

and compute

F (S_{0}, v_{f}; α, β, γ)

Set the best solution

S_{b}

and the best feasible solution

S^{*}

both to

S_{0}

Set S to

S_{0}

si = σ.

for

1 \leq i \leq I_{\max}

Generate the neighborhood of S

Choose the solution

S^{'}

that minimizes

F_{2} (S, v_{f}; α, β, γ)

and is not tabu or satisfies its aspiration criteria.

Update the tabu list.

S^{'}

is feasible and it is better than the current best feasible solution

S^{*}

then

Update the best feasible solution, i.e., set

S^{*}

S^{'}

Set si = i + φσ.

end if

S^{'}

is not feasible and is better than the current best solution

S_{b}

then

Update the best solution i.e., set

S_{b}

S^{'}

end if

Update w if necessary according to the feasibility status of

S^{'}

if i > si then

Set the current solution S to the best solution

S_{b}

Check for the new best speed within

[v_{f} - τ, v_{f} + τ]

and update

v_{f}

accordingly.

Set si = i + σ.

end if

if new best solution found and

I_{\max} - i < ψ

then

set

I_{\max} = i + 2 ψ

end if

Update S to

S^{'}

end for

return the best feasible solution

S^{*}

The initial solution

S_{0}

is the output of a nearest neighbor heuristic with

v_{f} = v_{0}

. A neighborhood is evaluated by considering all possible 1‐interchanges as proposed by Osman (1993). The (0,1) interchanges of node

v_{r} \in R_{r}

to route

R_{p}

are considered only if

R_{p}

contains one of η nearest neighbors of

v_{r}

. The (1,1) interchanges between nodes

v_{r} \in R_{r}

and

v_{p} \in R_{p}

are considered if

R_{p}

contains one of η nearest neighbor of

v_{r}

and

R_{r}

contains one of η nearest neighbor of

v_{p}

. After completing the neighborhood search, a 2‐opt intra‐route move is executed for each altered route. If node

v_{r}

is removed from

R_{r}

, reinserting

v_{r}

back into

R_{r}

is tabu for ℓ iterations. ℓ is randomly chosen between

[ℓ_{\min}, ℓ_{\max}]

. However, we use an aspiration criterion similar to Cordeau et al. (2003). This criterion revokes the tabu status of a move if it yields a solution with lower costs.

Similar to Gendreau et al. (1994), we allow capacity‐infeasible solutions, i.e., routes with total demand exceeding the vehicle capacity. Such infeasible solutions are penalized, in proportion to the capacity violation, by the following objective function, extending

F (S, v_{f}; α, β, γ)

F_{2} (S, v_{f}; α, β, γ) = F (S, v_{f}; α, β, γ) + w \sum_{R \in Z} {[(\sum_{i \in R} q_{i}) - Q]}^{+}

In Equation (8) (9) each unit of excess demand is penalized by a factor w. This penalty w is decreased by multiplication with a factor ν after ϕ consecutive feasible moves. Similarly, w is increased (multiplied by factor

ν^{- 1}

) after ϕ infeasible iterations.

Every σ iterations, we consider the best found solution

(S, v_{f})

and evaluate the solution for speeds within the interval

[v_{f} - τ, v_{f} + τ]

. The speed that minimizes

F_{2} (S, \cdot; α, β, γ)

is chosen as the new

v_{f}

. If a new best feasible solution is found then

v_{f}

is kept for another σφ iterations. The algorithm is run for

I_{\max}

iteration. However, if a best solution is found and the remaining number of iterations is less than ψ, the remaining number of iterations is updated to 2ψ.

5. Experimental Settings

We conducted two types of experiments. Section 1 describes our experiments with a single speed profile. The other experiments include two speed profiles and are presented in section 2 We experiment with sets from Augerat et al. (1998). The number of nodes in these sets ranges between 32 and 80. To achieve more realistic travel times, the coordinates of these sets were multiplied by 4.9. Note that a test set named “32 k5” means 32 customers including the depot with five vehicles. Optimal VRP solutions for these sets are available from Ralphs (2011).

5.1. Single Speed Profile

We set up the speed profile with two congested periods, while throughout the rest of the day the speed is set to the free flow speed (Figure 5, left). Many European roads face such a morning and afternoon congestion period (see Van Woensel and Vandaele 2006). The right side of Figure 5 depicts the travel time function for each starting time for an arbitrary distance. We set

v_{2}

and

v_{4}

to congestion speed

v_{c}

. Furthermore,

v_{5} = v_{3} = v_{1}

are considered as free flow speeds, that is, they correspond to the decision variable

v_{f}

F (S, v_{f}; α, β, γ)

. The points a, b, c, d, e correspond to 6:00, 9:00, 16:00, 19:00, and 0:00 hours. All links are subjected to this profile. Based on empirical data, the congestion speed is set to 50 km/hour (Lecluyse et al. 2009).

Figure 5

Speed and Travel Time Profile for the Experimental Setting

Observe that a starting time after 9:00 hours is superior to starting time before 9:00 hours, since the latter risks going twice into congestion. Consequently, we assume that all vehicles leave the depot at 9:00 hours. To compute the upper bound, we set a in Equation (8) to c − b. Considering

v_{c} = 50

together with this profile and based on Proposition 1 leads to the conclusion that

71 \leq v_{f}^{*} \leq 91

. Furthermore, by Lemma 1, the speed for computing the upper bound on

E (S, v_{f})

v^{'} = 74

km/hour.

The parameters chosen for the costs and the tabu search algorithm in section 4 are summarized in Table 1. We note that γ is based on the actual carbon market cost of the first half of April 2009 (Point Carbon 2009). All runs are performed on a Intel Core Duo with 2.4 GHz and 2 GB of RAM.

5.1.1. Validating the Proposed Model

Table 2 shows the results for the reduced model where we focus on emissions, that is, with the objective function

F (S, v_{f}; 0, 0, 1) = E (S, v_{f})

. Table 2 gives the CO₂ emissions (kg), the speed limit

v_{f}

, and the resulting travel time, denoted by

TT (F (S, v_{f}; 0, 0, 1))

; the last column gives the run times. There is a relation between the amount of CO₂ emissions and the travel time. For example, set 33 k5 achieves the lowest emissions and the lowest travel time. The speeds achieving lowest emissions range between 72 and 77 km/hour.

Table 1
Cost and Tabu Search Parameter Values

Cost Parameter Description Value

α Travel time cost (€ /hour) 20

β Fuel cost € /l (diesel) 1.2

γ Carbon cost € / ton 11

Tabu Search Parameter Description Value

η Number of closest customers considered for the neighborhood search, where n is the number of nodes [0.4n]

ℓ The tabu tenure length Randomly chosen in the interval [15, 25]

w The penalty for infeasible solutions Initial objective function value divided by 30

ϕ Number of iterations considered in updating w 5

ν Updating factor for w 0.75

$I_{\max}$ The maximum number of iterations 640

ψ Threshold for updating
$I_{\max}$
160

σ Number of iterations keeping the same speed 120

φ Updating factor for σ 1.5

τ Half‐width of the interval of speed search 1

Cost Parameter	Description	Value
α	Travel time cost (€ /hour)	20
β	Fuel cost € /l (diesel)	1.2
γ	Carbon cost € / ton	11

Tabu Search Parameter	Description	Value
η	Number of closest customers considered for the neighborhood search, where n is the number of nodes	[0.4n]
ℓ	The tabu tenure length	Randomly chosen in the interval [15, 25]
w	The penalty for infeasible solutions	Initial objective function value divided by 30
ϕ	Number of iterations considered in updating w	5
ν	Updating factor for w	0.75
$I_{\max}$	The maximum number of iterations	640
ψ	Threshold for updating $I_{\max}$	160
σ	Number of iterations keeping the same speed	120
φ	Updating factor for σ	1.5
τ	Half‐width of the interval of speed search	1

We tested the performance of our algorithm on the standard time‐independent VRP from Augerat et al. (1998). The algorithm reached an average optimality gap of 4% over the different sets. Furthermore, we evaluated the performance when setting the free flow speed to 71 km/hour (F(S,71;0,0,1)), which is the speed that minimized the CO₂ emissions function as observed in Figure 2. The results showed that adopting this speed leads to an average increase of 2.9% and 6.0% in emissions and travel times, respectively, when compared to the results in Table 2 (see Online Appendix S1 for further details).

Table 2

Results for the

F

(

S, v_{f}; 0, 0, 1

) Model (One Speed Profile)

Instance	$F (S, v_{f}; 0, 0, 1)$	$v_{f}$	$TT (F (S, v_{f}; 0, 0, 1))$	Run time (minutes)
32 k5	2976	72	3420	4.8
33 k5	2489	74	2836	3.3
33 k6	2777	73	3168	4.2
34 k5	2929	73	3377	3.8
36 k5	3088	75	3449	2.3
37 k5	2516	72	2911	8.5
37 k6	3613	74	4122	4.9
38 k5	2819	73	3209	5.0
39 k5	3175	72	3852	6.6
39 k6	3151	73	3603	7.7
44 k6	3575	72	4122	8.3
45 k6	3644	74	4162	3.0
45 k7	4466	74	4918	2.7
46 k7	3458	74	3912	4.6
48 k7	4156	73	4727	7.4
53 k7	3875	72	4500	13.6
54 k7	4563	77	5023	4.0
55 k9	4174	74	4713	4.0
60 k9	5362	72	6230	16.0
61 k9	4060	74	4536	8.4
62 k8	5104	73	5871	13.2
63 k9	6209	73	7130	13.3
63 k10	5115	73	5869	12.2
64 k9	5379	73	6168	13.6
65 k9	4666	75	5228	6.9
69 k9	4508	75	4996	31.1
80 k10	7062	73	8097	30.9
Average	4034	73	4598	9.0

To validate the model, we compare the results of

F (S, v_{f}; 0, 0, 1)

with the upper bound (UB) and the lower bound (LB) presented in . We generate the bounds using the optimal VRP solutions from Ralphs (2011) for the Augerat sets. Table 3 compares the amount of CO₂ emissions produced using the

F (S, v_{f}; 0, 0, 1) = E (S, v_{f})

objective function with the bounds.

F (S, v_{f}; 0, 0, 1)

/LB compares the emissions produced by the E‐TDVRP with the lower bound. On average the E‐TDRVP is within 4.3% from the lower bound. We note that the LB is computed under the assumption of no congestion. The last column in Table 3 quantifies the gap between UB and LB. The quality of the bounds is good as the average gap is only 4.7%. Based on this analysis, we conclude that the solution method is efficient and that the bounds are useful in real‐life decision‐making.

Table 3

Upper and Lower Bounds for

F

(

S, v_{f}; 0, 0, 1

) (One Speed Profile)

Set	UB	LB	$F (S, v_{f}; 0, 0, 1)$	$F (S, v_{f}; 0, 0, 1)$ /LB	UB/LB
32 k5	3081	2904	2976	102.5%	106.1%
33 k5	2546	2443	2489	101.9%	104.2%
33 k6	2838	2738	2777	101.4%	103.6%
34 k5	3016	2880	2929	101.7%	104.7%
36 k5	3135	2957	3088	104.4%	106.0%
37 k5	2602	2479	2516	101.5%	105.0%
37 k6	3684	3510	3613	102.9%	105.0%
38 k5	2822	2706	2819	104.2%	104.3%
39 k5	3220	3056	3175	103.9%	105.4%
39 k6	3240	3071	3151	102.6%	105.5%
44 k6	3634	3463	3575	103.2%	104.9%
45 k6	3648	3483	3644	104.6%	104.7%
45 k7	4458	4229	4466	105.6%	105.4%
46 k7	3531	3386	3458	102.1%	104.3%
48 k7	4172	3960	4156	104.9%	105.3%
53 k7	3897	3735	3875	103.7%	104.3%
54 k7	4553	4320	4563	105.6%	105.4%
55 k9	4078	3961	4174	105.4%	103.0%
60 k9	5238	4998	5362	107.3%	104.8%
61 k9	3925	3830	4060	106.0%	102.5%
62 k8	5041	4771	5104	107.0%	105.7%
63 k9	6344	5980	6209	103.8%	106.1%
63 k10	5042	4843	5115	105.6%	104.1%
64 k9	5437	5164	5379	104.2%	105.3%
65 k9	4498	4356	4666	107.1%	103.2%
69 k9	4438	4298	4508	104.9%	103.3%
80 k10	6900	6512	7062	108.5%	106.0%
Average				104.3%	104.7%

5.1.2. Numerical Results for

F (S, v_{f}; α, β, γ)

Table 4 gives an overview of the cost‐based solutions for all sets (α = 20 €/hour, β = 1.2 €/l and γ = 11 €/ton). The last three columns give the allocation of costs between its three major components.

Table 4
Results for
$F$
(
$S_{0}, v_{f}; α, β, γ$
) (One Speed Profile)

Cost partition

Set $F (S_{0}, v_{f}; α, β, γ)$
$v_{f}$
CO₂ (kg) Driver cost Fuel cost CO₂ cost

32 k5 2411 84 3092 41.6% 57.0% 1.4%

33 k5 1999 87 2615 40.4% 58.1% 1.4%

33 k6 2267 85 2924 41.3% 57.3% 1.4%

34 k5 2380 86 3061 41.4% 57.2% 1.4%

36 k5 2494 85 3221 41.2% 57.4% 1.4%

37 k5 2043 85 2636 41.2% 57.3% 1.4%

37 k6 2934 86 3799 41.0% 57.6% 1.4%

38 k5 2247 84 2937 40.5% 58.1% 1.4%

39 k5 2671 85 3423 41.6% 56.9% 1.4%

39 k6 2788 86 3626 40.8% 57.8% 1.4%

44 k6 2952 87 3893 39.9% 58.6% 1.5%

45 k6 2984 82 3750 42.8% 55.9% 1.4%

45 k7 3837 87 4958 41.1% 57.4% 1.4%

46 k7 2856 84 3680 41.3% 57.3% 1.4%

48 k7 3341 86 4349 40.7% 57.8% 1.4%

53 k7 3245 86 4208 40.9% 57.6% 1.4%

54 k7 3714 82 4676 42.7% 55.9% 1.4%

55 k9 3463 80 4327 43.1% 55.5% 1.4%

60 k9 4534 80 5632 43.4% 55.2% 1.4%

61 k9 3341 82 4247 42.1% 56.5% 1.4%

62 k8 4370 86 5655 41.1% 57.5% 1.4%

63 k9 5026 86 6476 41.3% 57.3% 1.4%

63 k10 4414 80 5505 43.2% 55.4% 1.4%

64 k9 4612 85 5916 41.6% 57.0% 1.4%

65 k9 3604 83 4628 41.5% 57.1% 1.4%

69 k9 3679 84 4773 40.9% 57.7% 1.4%

80 k10 5631 84 7187 41.9% 56.7% 1.4%

Average 41.5% 57.1% 1.4%

				Cost partition
32 k5	2411	84	3092	41.6%	57.0%	1.4%
33 k5	1999	87	2615	40.4%	58.1%	1.4%
33 k6	2267	85	2924	41.3%	57.3%	1.4%
34 k5	2380	86	3061	41.4%	57.2%	1.4%
36 k5	2494	85	3221	41.2%	57.4%	1.4%
37 k5	2043	85	2636	41.2%	57.3%	1.4%
37 k6	2934	86	3799	41.0%	57.6%	1.4%
38 k5	2247	84	2937	40.5%	58.1%	1.4%
39 k5	2671	85	3423	41.6%	56.9%	1.4%
39 k6	2788	86	3626	40.8%	57.8%	1.4%
44 k6	2952	87	3893	39.9%	58.6%	1.5%
45 k6	2984	82	3750	42.8%	55.9%	1.4%
45 k7	3837	87	4958	41.1%	57.4%	1.4%
46 k7	2856	84	3680	41.3%	57.3%	1.4%
48 k7	3341	86	4349	40.7%	57.8%	1.4%
53 k7	3245	86	4208	40.9%	57.6%	1.4%
54 k7	3714	82	4676	42.7%	55.9%	1.4%
55 k9	3463	80	4327	43.1%	55.5%	1.4%
60 k9	4534	80	5632	43.4%	55.2%	1.4%
61 k9	3341	82	4247	42.1%	56.5%	1.4%
62 k8	4370	86	5655	41.1%	57.5%	1.4%
63 k9	5026	86	6476	41.3%	57.3%	1.4%
63 k10	4414	80	5505	43.2%	55.4%	1.4%
64 k9	4612	85	5916	41.6%	57.0%	1.4%
65 k9	3604	83	4628	41.5%	57.1%	1.4%
69 k9	3679	84	4773	40.9%	57.7%	1.4%
80 k10	5631	84	7187	41.9%	56.7%	1.4%
Average				41.5%	57.1%	1.4%

The vast majority of costs are attributed to driving cost and fuel cost, which together on average account for 98.6% of the costs. The cost of CO₂ is rather insignificant when compared to others: 1.4% on average. Specifically, the current market cost of CO₂ has no tangible economic impact on the results. However, due to the direct relation between fuel consumption and CO₂, speeds associated with this model are between 80 and 87 km/hour. In fact, in all instances the resulting speed is strictly less than 90 km/hour. This implies that even with the current cost structure speeds are likely to be <90 km/hour.

5.1.3. The Reduced Models:

F (S, v_{f}; 0, 0, 1)

and

F (S, v_{f}; 1, 0, 0)

We analyze the results for the two reduced models. The first one optimizes only on the emissions (

F (S, v_{f}; 0, 0, 1)

), the second one focuses on travel times (

F (S, v_{f}; 1, 0, 0)

). This facilitates a trade‐off analysis between travel times and emissions. We ran the settings F(S,80;1,0,0) and F(S,90;1,0,0), that is, we fixed the speed limits to 80 and 90 respectively. The truck speed limit in most European countries is 80 or 90 km/hour, so these two specific settings depict an interesting European benchmark.

Let

TT (F (S, v_{f}; 0, 0, 1))

be the travel times resulting from the (reduced) model with objective function

F (S, v_{f}; 0, 0, 1)

. Specifically, the objective function only depends on emissions. The resulting solution (

S, v_{f}

) is then evaluated in terms of the travel time resulting in

TT (F (S, v_{f}; 0, 0, 1))

. Similarly, we define the emissions corresponding to the (reduced) model with objective function F(S,80;1,0,0) as E(F(S,80;1,0,0)). This means that we generate a solution (

S, v_{f}

) by minimizing the travel time and then evaluate this solution in terms of its emissions, which is denoted by E(F(S,80;1,0,0)). We use the following notation.

\begin{matrix} Δ {TT}_{80} & = \frac{TT (F (S, v_{f}; 0, 0, 1)) - F (S, 80; 1, 0, 0)}{F (S, 80; 1, 0, 0)} \\ Δ E_{80} & = \frac{F (S, v_{f}; 0, 0, 1) - E (F (S, 80; 0, 0, 1))}{E (F (S, 80; 1, 0, 0))} \\ Δ {TT}_{90} & = \frac{TT (F (S, v_{f}; 0, 0, 1)) - F (S, 90; 1, 0, 0)}{F (S, 90; 1, 0, 0)} \\ Δ E_{90} & = \frac{F (S, v_{f}; 0, 0, 1) - E (F (S, 90; 0, 0, 1))}{E (F (S, 90; 1, 0, 0))} \end{matrix}

In the above expressions the current situation corresponds to the setting with a fixed speed, that is, 80 or 90 km/hour, where the minimization is on the total travel time. In the alternative situation the objective is to minimize emissions, that is, the objective function

F (S, v_{f}; 0, 0, 1)

Table 5 gives an overview of the potential savings in emissions, compared to the amount of travel time needed to be sacrificed to achieve this saving. Columns 2 and 3 exhibit the decrease in emissions, while the last two columns exhibit the increase in emissions. Considering the speed limit of 90 km/hour, Table 5 implies that an average reduction of 11.4% in CO₂ emissions can be achieved. However, such a reduction will result in an average increase in travel time by 17.1%. Looking to the situation with a speed limit of 80 km/hour an average of 3.2% reduction in emissions can be achieved, which would require an average increase of 6.6% in travel time. These results show that in the case of 90 km/hour a substantial reduction of CO₂ emissions can be achieved.

Table 5
Trade‐off between Emissions and Travel Times (One Speed Profile)

Instance $Δ E_{80}$
$Δ E_{90}$

$Δ {TT}_{80}$

$Δ {TT}_{90}$

32 k5 −0.8% − 9.2% 10.3% 20.2%

33 k5 −4.2% −8.5% 4.9% 20.6%

33 k6 −5.3% −12.4% 4.0% 15.1%

34 k5 −2.8% −12.6% 7.3% 19.1%

36 k5 −1.4% −8.2% 6.5% 20.2%

37 k5 −2.1% −9.0% 9.0% 21.5%

37 k6 −1.1% −11.2% 7.3% 17.5%

38 k5 −1.4% −16.1% 11.1% 17.0%

39 k5 −8.5% −12.0% 6.4% 21.0%

39 k6 −2.0% −16.0% 8.9% 10.3%

44 k6 −5.3% −9.5% 5.6% 20.4%

45 k6 −3.9% −9.7% 7.6% 19.2%

45 k7 −0.8% −9.3% 4.5% 12.0%

46 k7 −1.4% −14.3% 8.1% 13.2%

48 k7 −2.1% −12.3% 6.3% 13.5%

53 k7 −5.1% −9.9% 5.8% 20.5%

54 k7 −1.5% −6.7% 5.1% 17.1%

55 k9 −2.1% −12.7% 7.4% 18.0%

60 k9 −4.9% −11.9% 5.5% 17.0%

61 k9 −2.4% −10.3% 7.7% 22.6%

62 k8 −6.4% −13.9% 2.5% 11.5%

63 k9 −5.3% −8.6% 3.6% 17.6%

63 k10 −3.4% −11.7% 6.6% 16.7%

64 k9 −4.7% −14.2% 4.4% 13.1%

65 k9 −3.3% −12.0% 5.0% 15.3%

69 k9 −2.5% −10.2% 6.2% 20.3%

80 k10 −0.7% −14.5% 9.7% 10.5%

Average −3.2% −11.4% 6.6% 17.1%

Instance	$Δ E_{80}$	$Δ E_{90}$	$Δ {TT}_{80}$	$Δ {TT}_{90}$
32 k5	−0.8%	− 9.2%	10.3%	20.2%
33 k5	−4.2%	−8.5%	4.9%	20.6%
33 k6	−5.3%	−12.4%	4.0%	15.1%
34 k5	−2.8%	−12.6%	7.3%	19.1%
36 k5	−1.4%	−8.2%	6.5%	20.2%
37 k5	−2.1%	−9.0%	9.0%	21.5%
37 k6	−1.1%	−11.2%	7.3%	17.5%
38 k5	−1.4%	−16.1%	11.1%	17.0%
39 k5	−8.5%	−12.0%	6.4%	21.0%
39 k6	−2.0%	−16.0%	8.9%	10.3%
44 k6	−5.3%	−9.5%	5.6%	20.4%
45 k6	−3.9%	−9.7%	7.6%	19.2%
45 k7	−0.8%	−9.3%	4.5%	12.0%
46 k7	−1.4%	−14.3%	8.1%	13.2%
48 k7	−2.1%	−12.3%	6.3%	13.5%
53 k7	−5.1%	−9.9%	5.8%	20.5%
54 k7	−1.5%	−6.7%	5.1%	17.1%
55 k9	−2.1%	−12.7%	7.4%	18.0%
60 k9	−4.9%	−11.9%	5.5%	17.0%
61 k9	−2.4%	−10.3%	7.7%	22.6%
62 k8	−6.4%	−13.9%	2.5%	11.5%
63 k9	−5.3%	−8.6%	3.6%	17.6%
63 k10	−3.4%	−11.7%	6.6%	16.7%
64 k9	−4.7%	−14.2%	4.4%	13.1%
65 k9	−3.3%	−12.0%	5.0%	15.3%
69 k9	−2.5%	−10.2%	6.2%	20.3%
80 k10	−0.7%	−14.5%	9.7%	10.5%
Average	−3.2%	−11.4%	6.6%	17.1%

5.2. Two Speed Profiles

In this section we consider two speed profiles. In addition to the profile considered in section 1, we add a similar profile but with a congestion speed equal to 70 km/hour similar to (Van Woensel and Vandaele 2006), instead of 50 km/hour. The two profiles were randomly assigned to the various distances in the instances.

We ran

F (S_{0}, v_{f}; α, β, γ)

for the two speed profile setting. Table 6 gives an overview of the performance of the solutions for all sets; the last three columns give the allocation of cost among its three components. Similar to the single speed profile case, the majority of costs are attributed to driving cost and fuel cost. However, due to the direct relation between fuel consumption and CO₂, speeds associated with this model are between 81 and 85 km/hour.

Table 6
Results for
$F (S, v_{f}; α, β, γ)$
(Two Speed Profiles)

Cost partition

Set $F (S_{0}, v_{f}; α, β, γ)$
$v_{f}$
CO₂ (kg) Driver cost Fuel cost CO₂ cost

32 k5 2487 85 3231 40.8% 57.7% 1.4%

33 k5 1968 85 2564 40.7% 57.9% 1.4%

33 k6 2234 83 2887 41.1% 57.4% 1.4%

34 k5 2332 85 3039 40.7% 57.9% 1.4%

36 k5 2450 84 3161 41.2% 57.3% 1.4%

37 k5 2004 85 2625 40.4% 58.2% 1.4%

37 k6 2925 85 3823 40.5% 58.1% 1.4%

38 k5 2199 85 2874 40.5% 58.1% 1.4%

39 k5 2632 85 2874 40.8% 57.7% 1.4%

39 k6 2763 84 3571 41.1% 57.4% 1.4%

44 k6 2875 84 3728 40.9% 57.6% 1.4%

45 k6 2850 85 3729 40.4% 58.2% 1.4%

45 k7 3633 85 4744 40.5% 58.0% 1.4%

46 k7 2781 85 3641 40.4% 58.2% 1.4%

48 k7 3393 83 4371 41.3% 57.2% 1.4%

53 k7 3221 85 4198 40.6% 57.9% 1.4%

54 k7 3736 84 4851 40.9% 57.7% 1.4%

55 k9 3319 81 4243 41.8% 56.8% 1.4%

60 k9 4371 82 5593 41.7% 56.9% 1.4%

61 k9 3189 82 4114 41.2% 57.3% 1.4%

62 k8 4279 85 5588 40.5% 58.0% 1.4%

63 k9 4976 83 6394 41.5% 57.1% 1.4%

63 k10 4069 84 5300 40.7% 57.9% 1.4%

64 k9 4554 85 5951 40.5% 58.1% 1.4%

65 k9 3826 85 5027 40.2% 58.4% 1.4%

69 k9 3639 85 4804 39.9% 58.7% 1.5%

80 k10 5673 82 7250 41.8% 56.8% 1.4%

average 40.8% 57.7% 1.4%

				Cost partition
32 k5	2487	85	3231	40.8%	57.7%	1.4%
33 k5	1968	85	2564	40.7%	57.9%	1.4%
33 k6	2234	83	2887	41.1%	57.4%	1.4%
34 k5	2332	85	3039	40.7%	57.9%	1.4%
36 k5	2450	84	3161	41.2%	57.3%	1.4%
37 k5	2004	85	2625	40.4%	58.2%	1.4%
37 k6	2925	85	3823	40.5%	58.1%	1.4%
38 k5	2199	85	2874	40.5%	58.1%	1.4%
39 k5	2632	85	2874	40.8%	57.7%	1.4%
39 k6	2763	84	3571	41.1%	57.4%	1.4%
44 k6	2875	84	3728	40.9%	57.6%	1.4%
45 k6	2850	85	3729	40.4%	58.2%	1.4%
45 k7	3633	85	4744	40.5%	58.0%	1.4%
46 k7	2781	85	3641	40.4%	58.2%	1.4%
48 k7	3393	83	4371	41.3%	57.2%	1.4%
53 k7	3221	85	4198	40.6%	57.9%	1.4%
54 k7	3736	84	4851	40.9%	57.7%	1.4%
55 k9	3319	81	4243	41.8%	56.8%	1.4%
60 k9	4371	82	5593	41.7%	56.9%	1.4%
61 k9	3189	82	4114	41.2%	57.3%	1.4%
62 k8	4279	85	5588	40.5%	58.0%	1.4%
63 k9	4976	83	6394	41.5%	57.1%	1.4%
63 k10	4069	84	5300	40.7%	57.9%	1.4%
64 k9	4554	85	5951	40.5%	58.1%	1.4%
65 k9	3826	85	5027	40.2%	58.4%	1.4%
69 k9	3639	85	4804	39.9%	58.7%	1.5%
80 k10	5673	82	7250	41.8%	56.8%	1.4%
average				40.8%	57.7%	1.4%

Both for the single and for the two speed profile case the resulting speeds (

v_{f}

) are within the same range. For the single speed profile case, where congestion speed is 50 km/hour, the best strategy to limit fuel and emissions costs is to try to avoid congestion, and thus speeds are higher than

v^{*} (= 71

km/hour). For the two speed profile case, the congestion speeds are 70 and 50 km/hour. The congestion speed of 70 km/hour is rather similar to

v^{*}

. For these cases, minimizing fuel and emissions costs leads to prefering congestion and to reduce the speed. However, this is countered by the travel time cost.

As the resulting speeds for both one and two speed profiles are within similar ranges, we examine the case where we set

v_{f}

to 85 km/hour for all sets. This value is observed in 14 sets from Table 6. Furthermore, having a single value for all sets might be easier from an operational point of view. Similar to the previous definitions, we define the following relations.

\begin{matrix} Δ (TT)_{85} & = \frac{TT (F (S, v_{f}; α, β, γ)) - TT (F (S, 85; α, β, γ))}{TT (F (S, 85; α, β, γ))} \\ Δ (E)_{85} & = \frac{E (F (S, v_{f}; α, β, γ)) - E (F (S, 85; α, β, γ))}{E (F (S, 85; α, β, γ))} \\ Δ (F)_{85} & = \frac{F (S, v_{f}; α, β, γ) - F (S, 85; α, β, γ)}{F (S, 85; α, β, γ)} \\ Λ (F)_{85} & = F (S, v_{f}; α, β, γ) - F (S, 85; α, β, γ) \end{matrix}

Table 7 exhibits the results of setting

v_{f}

to 85 km/hour. We note that the differences are not substantial. The cost for

F (S, v_{f}; α, β, γ))

is on average only 1.1% lower than the cost for F(S,85;α,β,γ). However, in absolute values, as depicted by

Λ (F)_{85}

, differences of up to 144.6 € are observed. For the analyzed sets, we conclude that setting the vehicle speed to 85 km/hour results in a good compromise between travel time minimization and emissions minimization.

Table 7

Comparison of F(

S, v_{f}; α, β, γ

) and F(S,85;α,β,γ) (Two Speed Profiles)

Set	$F (S_{0}, 85; α, β, γ)$	$Δ (TT)_{85}$	$Δ (E)_{85}$	$Δ (F)_{85}$	$Λ (F)_{85}$
32 k5	2489	0.0%	0%	0%	0
33 k5	1968	0.0%	0%	0%	0.0
33 k6	2234	−2.9%	−5%	−4%	−100.1
34 k5	2384	0.0%	0%	0%	0.0
36 k5	2450	−0.7%	−5%	−4%	−89.0
37 k5	2040	0.0%	0%	0%	0.0
37 k6	2960	0.0%	0%	0%	0.0
38 k5	2229	0.0%	0%	0%	0.0
39 k5	2632	−0.9%	−2%	−2%	−47.9
39 k6	2763	−1.7%	−2%	−2%	−54.8
44 k6	2875	−3.8%	−5%	−4%	−129.0
45 k6	2899	0.0%	0%	0%	0.0
45 k7	3643	0.0%	0%	0%	0.0
46 k7	2908	0.0%	0%	0%	0.0
48 k7	3393	2.0%	−2%	0%	−8.5
53 k7	3258	0.0%	0%	0%	0.0
54 k7	3736	0.1%	−1%	−1%	−25.9
55 k9	3319	3.9%	−4%	−1%	−25.4
60 k9	4371	1.6%	−2%	−1%	−35.8
61 k9	3189	0.2%	−5%	−3%	−104.7
62 k8	4282	0.0%	0%	0%	0.0
63 k9	4976	0.5%	−3%	−2%	−78.6
63 k10	4069	−2.9%	−4%	−4%	−144.6
64 k9	4738	0.0%	0%	0%	0.0
65 k9	3891	0.0%	0%	0%	0.0
69 k9	3665	0.0%	0%	0%	0.0
80 k10	5673	0.9%	−4%	−2%	−124.5
average		−0.1%	−1.7%	−1.1%	−35.9

6. Conclusions and Future Research

Carrier companies need to consider employing greener practices in the future. This article establishes a framework for modeling CO₂ emissions in a time‐dependent VRP context, by the E‐TDVRP model. It proposes an efficient solution method for the E‐TDVRP. We show the potential reduction in emissions when weighed against travel time. Furthermore, we show that reducing emissions may have a positive impact with respect to reducing cost.

We analyzed the effect of limiting vehicle speed in a time‐dependent VRP setting on the generated amount of CO₂ emissions. Time‐dependency was established by subjecting distances to variable speed profiles. CO₂ emissions were modeled as a function of speed. The speed, which optimizes CO₂ emissions per km, was not observed in any of our experimental settings. This is explained by the relation between limiting free flow speed and the likelihood of running into congestion. In congestion, the vehicle is forced to drive more slowly and emits more CO₂. Thus, increasing the free flow speed decreases the amount of time spent in congestion, and thereby may result in less emissions.

Based on the optimal VRP solutions in the literature, we constructed an upper and lower bound for CO₂ emissions. We showed that these bounds are tight, on average the gap was 4.7%. From a practical point of view these bounds are simple and fast to calculate. They require standard VRP solutions that are commonly used in practice. The bounds enable the assessment of the potential reduction in CO₂ emissions.

Considering CO₂ emissions, the results of the E‐TDVRP were rather close to the lower bound, with a difference of 4.3% on average. This indicates that the chosen solution strategy was adequate. We compared two extreme cases of the E‐TDVRP model, considering only travel times and considering only CO₂ emissions. For the first case, two possible speed limits were considered, 80 and 90 km/hour. For a speed limit of 90 km/hour our results showed that achieving an average reduction of 11.4% in CO₂ emissions required an average increase in travel time of 17.1%. However, for a speed limit of 80 km/hour, an average increase of 6.6% in travel times achieves a reduction of 3.2% in CO₂ emissions.

Considering one and two congestion speeds, the experiments showed that from a realistic cost perspective it is beneficial for vehicles to go below 90 km/hour. We also showed that adopting a speed limit of 85 km/hour yields good results in terms of total cost over all sets. Finally, we conclude that minimizing CO₂ emissions by limiting vehicle speed can be costly in terms of travel time. Nevertheless, limiting vehicle speed to a certain extent might be both cost and emission effective.

Additional enhancement of the algorithm may facilitate the solution of larger instances. Future research can also focus upon more accurate emissions modeling. For example, the weight of the vehicle has an impact on the amount of emissions, and in the VRP context this can be incorporated as a function of satisfied demand. In addition, more sophisticated travel time profiles can be constructed to encompass acceleration and deceleration, which in return will enable more accurate emissions modeling. Furthermore, the proposed model can be employed to investigate the costs and benefits of using alternative fuels in the context of VRP.

We have shown that the current market cost of CO₂ has no tangible economic impact on the results. However, exploring this value is yet another possible extension to this work. Examining the impact of this value on transportation‐related strategies is a relevant research question.

Footnotes

Acknowledgments

The research of Ola Jabali has been funded by the Netherlands Organization for Scientific Research (NWO), project number 400‐05‐185. Thanks are due to the referees for their valuable comments.

References

Augerat

Belenguer

J. M.

Benavent

Corberan

Naddef

. 1998. Separating capacity constraints in the CVRP using tabu search. Eur. J. Oper. Res. 106(2–3): 546–557.

Baumgartner

Léonardi

Kruscha

. 2008. Improving computerized routing and scheduling and vehicle telematics: A qualitative survey. Transport. Res. Part D 13(6): 377–382.

Bektaş

Laporte

. 2011. The pollution‐routing problem. Transport. Res. Part B: Methodological 45(8): 1232–1250.

Cairns

1999. The home delivery of shopping: The environmental consequences. TSU Working paper, ESRC Transport Studies Unit, University of London, London.

Corbett

C. J.

Kleindorfer

P. R.

. 2001a. Environmental management and operations: Introduction to part 2 (integrating operations and environmental management systems). Prod. Oper. Manag. 10(3): 225–227.

Corbett

C. J.

Kleindorfer

P. R.

. 2001b. Environmental management and operations management: Introduction to part 1 (manufacturing and eco‐logistics). Prod. Oper. Manag. 10(2): 107–111.

Cordeau

J.‐F.

Laporte

Mercier

. 2003. A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. 52(8): 928–936.

Ericsson

Larsson

Brundell‐Freij

. 2006. Choice for lowest fuel consumption—potential effects of a new driver support tool. Transport. Res. Part C 14(6): 369–383.

European Commission . 1999. Methodology for calculating transport emissions and energy consumption. Available at http://www.inrets.fr/ur/lte/cost319/M22.pdf (accessed date December 20, 2011).

10.

Fleischmann

Gietz

Gnutzmann

. 2004. Time‐varying travel times in vehicle routing. Transport. Sci. 38(2): 160–173.

11.

Gendreau

Hertz

Laporte

. 1994. A tabu search heuristic for the vehicle routing problem. Manage. Sci. 40(10): 1276‐1290.

12.

Gendreau

Laporte

Séguin

. 1996. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Oper. Res. 44(3): 469–477.

13.

Glover

1989a. Tabu search I. ORSA J. Comput. 1(3): 190–206.

14.

Glover

1989b. Tabu search part ii. ORSA J. Comput. 2(2): 4–32.

15.

Hertz

Laporte

Mittaz

. 2000. A tabu search heuristic for the capacitated arc routing problem. Oper. Res. 48(1): 129–135.

16.

Hill

A. V.

Benton

W. C.

. 1992. Modeling intra‐city time‐dependent travel speeds for vehicle scheduling problems. Eur. J. Oper. Res. 43(4): 343–351.

17.

Ichoua

Gendreau

Potvin

J.‐Y.

. 2003. Vehicle dispatching with time‐dependent travel times. Eur. J. Oper. Res. 144(2): 379–396.

18.

Jabali

Van Woensel

de Kok

A. G.

Lecluyse

Peremans

. 2009. Time‐dependent vehicle routing subject to time delay perturbations. IIE Trans. 41(12): 1049–1066.

19.

Jung

Haghani

. 2001. A genetic algorithm for the time dependent vehicle routing problem. Transport. Res. Rec. J. Transtport. Res. Board 1771: 161–171.

20.

Kirby

H. R.

Hutton

McQuaid

R. W.

Raeside

Zhang

. 2000. Modelling the effects of transport policy levers on fuel efficiency and national fuel consumption. Transport. Res. Part D 5(3): 265–282.

21.

Kleindorfer

P. R.

Singhal

Van Wassenhove

L. N.

. 2001. Sustainable operations management. Prod. Oper. Manag. 14(4): 482–492.

22.

Kramer

K. J.

Moll

H. C.

Nonhebel

Wilting

H. C.

. 1999. Greenhouse gas emissions related to Dutch food consumption. Energy Policy 27(4): 203–216.

23.

Laporte

2007. What you should know about the vehicle routing problem. Naval Res. Logist. 54(8): 811–819.

24.

Lee

S.‐Y.

Klassen

R. D.

. 2008. Drivers and enablers that foster environmental management capabilities in small‐ and medium‐sized suppliers in supply chains. Prod. Oper. Manag. 17(6): 573–586.

25.

Lecluyse

Van Woensel

Peremans

. 2009. Vehicle routing with stochastic time‐dependent travel times. 4OR: A Quart. J. Oper. Res. 7(4): 363–377.

26.

Léonardi

Baumgartner

. 2004. CO

_{2}

efficiency in road freight transportation: Status quo measures and potential. Transport. Res. Part D 9(6): 451–464.

27.

Malandraki

Daskin

M. S.

. 1992. Time dependent vehicle routing problems: Formulations properties and heuristic algorithms. Transport. Sci. 26(3): 185–200.

28.

Malandraki

Dial

R. B.

. 1996. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. Eur. J. Oper. Res. 90(1): 45–55.

29.

Nannicini

Baptiste

Barbier

Krob

Liberti

. 2010. Fast paths in large‐scale dynamic road networks. Comput. Optim. Appl. 45(1): 143–158.

30.

Osman

I. H.

1993. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann. Oper. Res. 41(4): 421–451.

31.

Palmer

2008. The development of an integrated routing and carbon dioxide emissions model for goods vehicles. Ph.D. dissertation, Cranfield University, United Kingdom.

32.

Point Carbon . 2009. Trading analytics. Available at http://www.pointcarbon.com/trading (accessed date December 20, 2011).

33.

Ralphs

2011. Branch cut and price resource web. Available at http://www.branchandcut.org (accessed date December 2011).

34.

Sbihi

Eglese

R. W.

. 2007. Combinatorial optimization and green logistics. 4OR: A Quart. J. Oper. Res. 5(2): 99–119.

35.

Scott

Urquhart

Hart

. 2010. Influence of topology and payload on CO2 optimized vehicle routing. Appl. Evol. Comput. Lecture Notes Comput. Sci. 6025/2010: 141–150.

36.

Singha

Gangopadhyaya

Nandaa

P. K.

Bhattacharyab

Sharmab

Bhana

. 2004. Trends of greenhouse gas emissions from the road transportsector in India. Sci. Total Envriron. 390(1): 124–131.

37.

Springer

2004. The market for tradable GHG permits under the Kyoto Protocol: A survey of model studies. Energy Econom. 25(5): 527–551.

38.

Sugawara

Niemeier

D. A.

. 2002. How much can vehicle emissions be reduced? Exploratory analysis of an upper boundary using an emissions‐optimized trip assignment. Tranport. Res. Record 1815: 29–37.

39.

Taniguchi

Thompson

R. G.

Yamada

Van Duin

. 2001. City Logistics: Network Modelling and Intelligent Transport Systems. Pergamon, Oxford.

40.

Vanek

F. M.

Campbell

J. B.

. 1999. UK road freight energy use by product: Trends and analysis from 1985 to 1995. Transport. Policy 6(4): 237–246.

41.

Van Woensel

2003. Modelling uninterrupted traffic flows: A queueing approach. Ph.D. dissertation, University of Antwerp, Belgium.

42.

Van Woensel

Vandaele

. 2006. Empirical validation of a queueing approach to uninterrupted traffic flows. 4OR: A Quart. J. Oper. Res. 4(1): 59–72.

43.

Van Woensel

Creten

Vandaele

. 2001. Managing the environmental externalities of traffic logistics: The issue of emissions. Prod. Oper. Manag. 10(2): 207–223.

44.

Van Woensel

Kerbache

Peremans

Vandaele

. 2008. Vehicle routing with dynamic travel times: A queueing approach. Eur. J. Oper. Res. 186(3): 990–1007.

45.

Yang

McCollum

McCarthy

Leighty

. 2008. Meeting an 80% reduction in greenhouse gas emissions from transportation by 2050: A case study in California. Trans. Res. Part D. 14(3): 147–156.

				Cost partition
Set	$F (S_{0}, v_{f}; α, β, γ)$	$v_{f}$	CO₂ (kg)	Driver cost	Fuel cost	CO₂ cost
32 k5	2411	84	3092	41.6%	57.0%	1.4%
33 k5	1999	87	2615	40.4%	58.1%	1.4%
33 k6	2267	85	2924	41.3%	57.3%	1.4%
34 k5	2380	86	3061	41.4%	57.2%	1.4%
36 k5	2494	85	3221	41.2%	57.4%	1.4%
37 k5	2043	85	2636	41.2%	57.3%	1.4%
37 k6	2934	86	3799	41.0%	57.6%	1.4%
38 k5	2247	84	2937	40.5%	58.1%	1.4%
39 k5	2671	85	3423	41.6%	56.9%	1.4%
39 k6	2788	86	3626	40.8%	57.8%	1.4%
44 k6	2952	87	3893	39.9%	58.6%	1.5%
45 k6	2984	82	3750	42.8%	55.9%	1.4%
45 k7	3837	87	4958	41.1%	57.4%	1.4%
46 k7	2856	84	3680	41.3%	57.3%	1.4%
48 k7	3341	86	4349	40.7%	57.8%	1.4%
53 k7	3245	86	4208	40.9%	57.6%	1.4%
54 k7	3714	82	4676	42.7%	55.9%	1.4%
55 k9	3463	80	4327	43.1%	55.5%	1.4%
60 k9	4534	80	5632	43.4%	55.2%	1.4%
61 k9	3341	82	4247	42.1%	56.5%	1.4%
62 k8	4370	86	5655	41.1%	57.5%	1.4%
63 k9	5026	86	6476	41.3%	57.3%	1.4%
63 k10	4414	80	5505	43.2%	55.4%	1.4%
64 k9	4612	85	5916	41.6%	57.0%	1.4%
65 k9	3604	83	4628	41.5%	57.1%	1.4%
69 k9	3679	84	4773	40.9%	57.7%	1.4%
80 k10	5631	84	7187	41.9%	56.7%	1.4%
Average				41.5%	57.1%	1.4%

Analysis of Travel Times and CO 2 Emissions in Time‐Dependent Vehicle Routing

Abstract

Keywords

1. Introduction

2. Literature Review

3. Description of E‐TDVRP

3.1. Determining TT ( S , v f )

Algorithm 1 E‐TDVRP algorithmic structure

5. Experimental Settings

5.1. Single Speed Profile

Footnotes

Acknowledgments

References

3.1. Determining
$TT (S, v_{f})$