Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
124,500 characters · 21 sections · 78 citation commands
Load Asymptotics and Dynamic Speed Optimization for the Greenest Path Problem: A Comprehensive Analysis
\RUNAUTHOR{Moradi et al.}
\RUNTITLE{Load Asymptotics and Dynamic Speed Optimization for the Greenest Path Problem}
\TITLE{Load Asymptotics and Dynamic Speed Optimization for the Greenest Path Problem: \\ A Comprehensive Analysis}
\ARTICLEAUTHORS{ \AUTHOR{Poulad Moradi, Joachim Arts} \AFF{Luxembourg Centre for Logistics and Supply Chain Management, University of Luxembourg, Luxembourg City, Luxembourg, 6, rue Richard Coudenhove-Kalergi L-1359, \EMAIL{\{poulad.moradi, joachim.arts\}@uni.lu}} \AUTHOR{Josué C. Velázquez-Martínez} \AFF{Center for Transportation and Logistics, Massachusetts Institute of Technology, Cambridge, MA, USA,\\1 Amherst Street, MA 02142, \EMAIL{[email removed]} \URL} }
\ABSTRACT{ We study the effect of using high-resolution elevation data on the selection of the most fuel-efficient (greenest) path for different trucks in various urban environments. We adapt a variant of the Comprehensive Modal Emission Model (CMEM) to show that the optimal speed and the greenest path are slope dependent (dynamic). When there are no elevation changes in a road network, the most fuel-efficient path is the shortest path with a constant (static) optimal speed throughout. However, if the network is not flat, then the shortest path is not necessarily the greenest path, and the optimal driving speed is dynamic. We prove that the greenest path converges to an asymptotic greenest path as the payload approaches infinity and that this limiting path is attained for a finite load. In a set of extensive numerical experiments, we benchmark the CO$_2$ emissions reduction of our dynamic speed and the greenest path policies against policies that ignore elevation data. We use the geo-spatial data of 25 major cities across 6 continents. We observe numerically that the greenest path quickly diverges from the shortest path and attains the asymptotic greenest path even for moderate payloads. Based on an analysis of variance, the main determinants of the CO$_2$ emissions reduction potential are the variation of the road gradients along the shortest path as well as the relative elevation of the source from the target.
}
\KEYWORDS{Sustainability, Routing, Asymptotics, Last-Mile}
The transportation sector is one of the largest sources of anthropogenic CO$_2$ emissions, as attested by the IPCCWGI2021, GHGInventory, and the EEA2021. In 2020, 36.3% of U.S. CO$_2$ emissions from fossil fuel combustion came from the transportation sector, of which 45.2% was generated by heavy-, medium-, and light-duty trucks GHGInventory. Similarly, the transportation sector accounted for 22% of the EU's CO$_2$ emissions in 2020 EEA2021. Accordingly, there has been considerable attention on reducing CO$_2$ emissions through “green routing”; see e.g. Demir2012, Scora2015, Raeesi2019. The objective to reduce CO$_2$ emissions in transportation aligns with efforts to reduce fuel expenditure. The reduction of fuel consumption has become imperative as fuel increases in price and volatility due to recent geopolitical events, namely the Russian invasion of Ukraine WLJ2022.
Road gradient and vehicle speed are two major factors that influence the carbon footprint of a diesel truck Demir2014. Demir2011 demonstrate through numerical analysis that a medium-duty truck may consume an additional six liters of diesel per 100 kilometer while traveling up a hill with a 1% gradient. The same study also shows that increasing the speed of an empty medium-duty truck from 50 km/h to 100 km/h can raise fuel consumption by more than 3% on a level path. Gravity is an important factor in finding the most efficient path between two points. Johann Bernoulli posed such a problem as early as 1696, in which a path was deemed efficient if the travel time was minimized and only gravity could be used to accelerate. The solution to this problem gave rise to so-called brachistochrone curves, which differ from the shortest path between two points. Gravity and speed interact when finding the greenest (or most fuel-efficient) route between two points in a road network. The aim of the present paper is to provide a thorough analysis of the difference between shortest paths and greenest paths as a function of speed and vehicle type for a large variety of geographic settings.
In principle, empirical methods are the most precise way of measuring carbon emissions associated with traversing a road with a certain vehicle at a certain speed. Unfortunately, it is not practical to empirically find carbon emissions for all roads, speeds, and vehicle types as well as many other parameters (e.g. road surface type) that affect fuel efficiency. Hence, several CO$_2$ emissions models for trucks have been proposed in literature. Demir2014 offers a summary of these models. The Comprehensive Modal Emission Model (CMEM) is an instantaneous emissions modeling approach that was introduced by Barth2005, Scora2006, Boriboonsomsin2009. Bektas2011 and Demir2012 present a simplified variant of CMEM that is differentiable with respect to speed. This model is convenient in practical applications. Rao2016 and Brunner2021 show that this model can be made more realistic for cases where a vehicle travels downhill. Their modification of the CMEM, unfortunately, renders it no longer differentiable at all speeds. Over the past decade, CMEM has been the prevalent emissions model utilized in green/pollution vehicle routing problems Bektas2011, Franceschetti2013, Huang2017, Xiao2020.
We call an optimization problem that seeks a path between an origin and destination a {\em path selection} problem. In this paper, we focus on the selection of the greenest (most fuel-efficient) path. The greenest path is the path with the least CO$_2$ emissions. Some authors also call this the eco-friendly path Scora2015,Andersen2013,Boriboonsomsin2009,Schroder2019. Path selection is the backbone of a multitude of transport-based supply chain problems, from strategic supply chain network design to operational vehicle routing problems. The complexity of transportation problems forces many solution approaches to use path selection as a
activity. It is common to use either the shortest or the fastest path in this pre-rocessing step. The implicit assumption is that these paths are also the greenest. In this paper, we show that the actual topology of urban road networks requires that we consider the greenest path selection as a part of the main optimization problem, e.g. vehicle routing problem (VRP) or supply chain network design (SCND).
The development of Geographic Information Systems (GIS) have made high-resolution geospatial data available at low cost. It is not sufficient to only consider the elevation of the origin and destination of a path. Rather, for any path, elevation along different sections of a path determine whether gravity increases or decreases the amount of fuel needed for travel. Thus, detailed elevation data of each segment of a possible path is required to find the greenest path. Furthermore, the slope along different segments of a path also determines the most fuel efficient speed along each segment of a path.
In this paper, we show that the most fuel efficient speed will change along different segments of any path. Thus, dynamic speed optimization is important to find the greenest path between any origin and destination. The greenest path also depends on the payload of a vehicle. We prove that the greenest path converges to an asymptotic greenest path as the payload approaches infinity and that this limiting path is attained for a finite payload. Our results are illustrated through numerical experiments. These experiments consider a setting wherein a logistics service provider seeks to reduce the CO$_2$ emissions of their transport operations. The company's fleet consists of heavy-, medium-, and light-duty trucks that operate in an urban environment. We use the modified CMEM proposed by Brunner2021 and focus our analysis on the effects that road gradient, speed, payload, and truck type have on CO$_2$ emissions.
We use an extensive numerical study to provide statistical answers to empirical research questions listed at the end of this section. We utilize the real road network and elevation data of 25 cities across six continents. It is worth noting that the closest paper to our work in terms of the CO$_2$ emissions model is Brunner2021. Apart from the differences of our objective functions, the main differences between our study and Brunner2021 are twofold. Firstly, Brunner2021 base their analysis on the static speed policy along different segments of a path. We show that a static speed policy can be suboptimal in terms of CO$_2$ emissions for traversing a path in a city with uneven topography. In addition, we demonstrate that the speed policy influences which path is the greenest. Secondly, Brunner2021 solve the path selection problem as a
activity for their main VRP problem. Moving the path selection to a
step forces them to consider fixed loads and speeds. By contrast, we consider dynamic speed optimization, and study asymptotics greenest paths as payloads increase.
The main contributions of this paper are listed below:
The rest of this paper is organized as follows. We review the related literature in Section (ref). Section (ref) describes the mathematical model used in this study and the policies that can minimize CO$_2$ emissions. Section (ref) provides the setting and results of the extensive numerical studies
Finally, we offer the conclusions and final remarks in Section (ref).
Green transportation has been studied extensively over various decision-making settings. Asghari2021,Moghdani2021,Demir2014 give reviews on the most important recent literature on the green VRP. Additionally, Waltho2019 reviews pivotal studies in the field of green SCND from 2010 to 2017. In most of the main stream green VRP and SCND, the path between every two nodes of interest is computed as a
step Demir2012. This has been partially relaxed for the VRP by Behnke2017. In other words, road networks are reduced to distances between origin and destination pairs to simplify later computations. The implicit assumption is that distances or travel times are the main drivers of costs and/or emissions. This paper extensively studies to which extent this implicit assumption is tenable.
A large body of work in the field of green transportation relies on macroscopic (average aggregate), microscopic (instantaneous) fuel consumption models, or a combination of both. Demir2014 and Zhou2016 provide an extensive review of fuel consumption models. A number of studies, including Boriboonsomsin2012,Scora2015, and Ericsson2006, estimate the CO$_2$ emissions of a specific vehicle based on the measurement of that vehicle. Demir2014 explain the main factors that influence fuel consumption in road freight transportation. Among the pertinent determinants for the case of the greenest path are road gradient, speed, truck type, and payload.
The path optimization under environmental consideration (the greenest path) has been explored over the past two decades. This problem can be formulated based on a variant of the shortest path algorithm of Dijkstra1959 to minimize the total fuel consumption of a vehicle between two nodes. Ericsson2006 studies the CO$_2$ emissions of light-duty cars by using a navigation system that computes the greenest path based on in-vehicle data and traffic information in Lund, Sweden. They conclude that selecting the greenest path can reduce fuel consumption by 4% on average in Lund. Boriboonsomsin2012 presents an Eco-Routing Navigation System (EFNav) as a framework to integrate GIS and traffic data with emissions model estimates to compute eco-friendly paths for light vehicles. Scora2015 extend the EFNav model to heavy-duty trucks (EFNav-HDT) and conduct a numerical study to test the benefits of EFNav-HDT across different vehicle weights in Southern California. Scora2015 provide excellent insights into the specifications of the greenest path for trucks. Both Boriboonsomsin2012 and Scora2015 base their studies on the CMEM model and estimate the energy/emissions model using linear regression over data from actual measurements. Boriboonsomsin2012 take advantage of a logarithmic transformation and Scora2015 use a minimum fuel cutoff point to avoid negative fuel consumption results. Andersen2013 take advantage of free road network data, such as OpenStreetMap, and use Controller Area Network (CAN bus) data to compute the greenest path by assigning weights to the different segments of the network. Since this work does not rely on a fuel consumption model, it is very accurate for the paths and vehicles for which fuel consumption data is available, but it does not transfer to other settings without the collection of a large amount of data in that setting. Pamucar2016 utilize a similar approach and include other negative externalities associated with transportation, such as noise, land use, and pollutants other than CO$_2$ . Schroder2019 consider a Digital Elevation Model and Copert III emissions model to compute the greenest path. Dundar2022 propose an approach to increase the resolution of the road network and compute the fuel consumption over along a path more accurately.
Speed optimization as a means to reduce the emissions and driving costs was first introduced by Demir2012. Franceschetti2013 present a speed optimization technique that can also be used for traffic congestion. Both of these works, as well as many other well-cited papers, such as Lai2021, rely on the CMEM model of Demir2011, which results in negative fuel consumption over many downhill paths Brunner2021. Brunner2021 modify the fuel consumption model, yet only consider a constant travel speed. Some papers consider the
under dynamic speeds induced by congestion Ehmke2016a, Ehmke2016b, Huang2017, Ehmke2018.
In our paper, we consider the modified CMEM Brunner2021. We explore the individual and combined effects of elevation, speed optimization, truck type, payload, and characteristic city topography on CO$_2$ emissions reduction and the greenest path policies. This paper, is the first paper to provide asymptotic results for a path selection problem and the the greenest path problem in particular.
In this section, we introduce the notations (Section (ref)) and mathematical foundations of our research, including the CO$_2$ emissions models (Section (ref)) together with the optimal speed policies (Section (ref)). We formally introduce the greenest paths between two locations in a city road network and discuss how optimal speed policies complicate the computation of the greenest path (Section (ref)). We study the asymptotic behavior of the greenest path when the payload increases (Section (ref)). In Section (ref), we only consider speed, payload, and/or path (or a single arc) as the explicit arguments of functions, since these three factors are the focus of our analysis in Sections (ref), (ref), and (ref).
Let a directed graph $\mathcal{G}=(V,A)$ represent the road network of a city, where $V = \{1, \dots, m\}$ is the set of $m$ vertices, the points of interest along the roads (e.g. road intersections), and $A \subseteq V \times V$ is the set of arcs (road segments) that connects the vertices. Any arc $a \in A$ has the following features: the length $\delta:A\to \mathbb{R}_{++}$, the angle $\theta: A \to \mathbb{R}$, the maximum allowable speed by $\varv^{\max}: A \to \mathbb{R}_{++}$, and the minimum allowable speed by $\varv^{\min}: A \to \mathbb{R}_{++}$, where $\mathbb{R}_{++}=\{x \in \mathbb{R} : x>0\}$. We consider an internal combustion engine truck that traverses an arc $a\in A$ with speed $v \in [\varv^{\min} (a) , \varv^{\max} (a)]$. $v$ is constant along arc $a$, but the speed of the truck can vary on other arcs. The truck consumes $f_a$ liters of diesel fuel and produces $e_a$ kilograms of CO$_2$ to traverse arc $a \in A$ ($v$ will be selected to minimize $f_a$ and $e_a$ according to different emission models). Notation, including those of truck properties, are listed in Table (ref).
We discuss two emission models. The first of these models is most commonly used in recent papers on the green/pollution routing problem Bektas2011, Demir2012, Franceschetti2013, Dabia2017. We will call this the standard model. The second model is a small improvement on the standard model to disallow negative fuel consumption on downward sloping road segments.
The CMEM Barth2005,Scora2006,Boriboonsomsin2009 is a microscopic truck fuel consumption model that has been widely used in literature for pollution/green vehicle routing problems. The Standard model is an instantiation of the CMEM approach. Suppose a truck with the parameters given in Table (ref) and payload $l$ travels along arc $a \in V$ with speed $v$. In the standard emission model introduced by Bektas2011 and Demir2012, the truck's fuel consumption is given by:
The main assumption behind Equation (ref) is that the truck parameters remain constant along each arc $a \in V$. This model sets aside a number of minor sources of fuel consumption, such as air conditioning and compressed air systems. Burning one liter of diesel in a combustion engine produces $c_e=2.67$ kg/L of CO$_2$ EmissionFacts2005. Thus we find that the CO$_2$ emissions associated with traversing an arc $a$ with load $l$ at speed $v$ is given by, \[ \tilde{e}_a(v,l) = c_e \Tilde{f}_a(v,l) = 2.67 \Tilde{f}_a(v,l) \] under the standard model.
Rao2016 and Brunner2021 establish that the standard emission model gives rise to negative fuel consumption on some negative road angles that are not realistic for internal combustion engine vehicles. Thus, Brunner2021 propose the following adjustment to Equation (ref):
where $(\cdot)^+=\max \{\cdot,0\}$. Equation (ref) shows that gravity works in favor of the vehicle over downhills arcs to compensate the energy loss caused by drag and rolling resistance force. This equation assumes that any engine-powered brakes consume a negligible amount of fuel. The standard and improved emission models (ref) and (ref) are identical on a flat network ($\theta(a)=0$ for all $a\in A$). We note that a slight modification of the above models can also allow for electric vehicles with regenerative braking; see Larminie2012. As before we now find that the CO$_2$ emissions associated with traversing arc $a$ with load $l$ at speed $v$ is given by,
The most fuel efficient speed to traverse an arc depends on the emission model that is used. We will show below that there is one optimal speed for all arcs in a network under the standard emission model, but that the optimal speed may differ by arc for the improved emission model.
The speed optimization problem (SO) is to compute the speed policy which minimizes the carbon emissions when a vehicle travels across an arc $a \in A$. Under the standard emissions model, SO can be formulated as,
This implies that the most fuel efficient speed is the same along any arc $a \in A$ and is given by $\varv^s: A \to \mathbb{R}_{++}$ that is defined by,
where $c_{\varv}$,
is the optimal speed without any speedlimits. Expressions for $P$ and $R$ are given by Equations (ref) and (ref). Equation (ref) is obtained by solving the first order conditions to minimize (ref) with respect to $v$. Since $c_{\varv}$ is constant along all arcs, we use the term {\em static speed} policy to denote a policy that will have a vehicle traverse every arc at the speed $\varv^s$. We note that for practically meaningful values of $\varv^{\min}(a)$ and $\varv^{\max}(a)$ the optimal speed is usually given by (ref), or the second case in (ref).
In the improved emissions model, the most fuel-efficient speed to traverse an arc depends on its slope. Under the improved emissions model (ref), the speed optimization problem is formulated as,
Note that the derivative of $e_a(v,l)=\frac{c_e P \delta(a)}{v} + c_e \left(Q \delta(a) (g \sin \theta(a) + C_r g \cos \theta(a)) (w+l) + R \delta(a) v^2 \right)^+$ with respect to $v$ is given by \[ \frac{\partial e_a(v,l)}{\partial v}=
\] where $\varv^t: A \times \mathbb{R}_+ \to \mathbb{R}_{+}$ is defined by,
This derivation shows that the CO$_2$ emissions of an arc $e_a(v,l)$ is not differentiable with respect to $v$ at the point $\varv^t(a,l)$. The speed $\varv^t$ has a physical interpretation as the terminal velocity of a vehicle on a slope with inclination $\theta$. It is the speed at which the gravitational force along the slope equals the sum of the drag and rolling resistance forces (see e.g. fox2020). A vehicle reaches a non-zero terminal velocity on an arc if the angle falls below $-\arctan{C_r}$. The optimal solution to the speed optimization problem in (ref) is slightly more involved as it needs to account for the terminal velocity. The solution is given in Proposition (ref).
\proof{Proof of Proposition (ref).} We consider the case where the terminal velocity is zero, and where it is strictly positive separately.
Case 1 ($\tan \theta(a) \geq -C_r$; $\varv^t(a,l)=0$): Equation (ref) reduces to Equation (ref) so that one may verify that \[ \varv^d (a,l) = c_{\varv} > \varv^t(a,l) = 0. \]
Case 2 ($\tan \theta(a) < -C_r$; $\varv^t(a,l) >0$): In this case,
It is straightforward to verify that $e_a(v,l)$ is continuous, $e_a^1$ is convex and non-increasing in $v$, and $e_a^2$ is convex in $v$ with a minimum at $c_{\varv}$. Consequently, the optimal speed exceeds the terminal velocity, i.e. $\varv^d (a,l)\geq \varv^t(a,l)$.
As $e_a(v,l)$ is convex in $v$ on $[\varv^t(a,l),\infty)$, it has an extremum at $c_{\varv}$ if $\varv^t(a,l) \leq c_{\varv}$, or at $\varv^t(a,l)$ if $\varv^t(a,l) > c_{\varv}$. It follows that the optimal speed is $\max \{c_{\varv}, \varv^t(a,l)\}$ if it lies within the allowable speed interval, $[\varv^{\min}(a),\varv^{\max}(a)]$. In case $\max \{c_{\varv}, \varv^t(a,l)\} < \varv^{\min}(a)$, then $e_a(v,l)$ is non-decreasing in $v \in [\varv^{\min}(a),\varv^{\max}(a)]$ and the optimal speed is $\varv^{\min}(a)$. If $\max \{c_{\varv}, \varv^t(a,l)\} \geq \varv^{\max}(a)$, then $e_a(v,l)$ is non-increasing in $v \in [\varv^{\min}(a),\varv^{\max}(a)]$ and the optimal speed is $\varv^{\max}(a)$. \Halmos \endproof The main insight from Proposition (ref) is that it is efficient to use gravity to reduce the required engine power and emission. Proposition (ref) indicates that a static speed policy is not optimal on a path that contains downhill arcs. Thus, a {\em dynamic speed} policy ($\varv^d$), as per Proposition (ref), reduces a truck's fuel consumption, CO$_2$ emissions, and travel time since it requires higher speeds on downhills.
Let $n_s$ and $n_t$ be two different vertices of $\mathcal{G}$ such that $n_t$ is reachable from $n_s$. Let $\Pi$ be the set of all possible paths between $n_s$ and $n_t$. Under a given speed policy $\varv: A \to \mathbb{R}_{++}$ and a constant payload $l$, the total CO$_2$ emissions of a truck to travel between $n_s$ and $n_t$ along a path $\pi \in \Pi$, $\mathcal{E}(\pi, \varv, l)$, is defined as,
Based on this definition, the greenest path problem (GPP) is to compute the path with the least CO$_2$ emissions, $\pi^g$, between $n_s$ and $n_t$, i.e.
We define the shortest path problem (SPP) as the computation of the minimum-distance path ($\pi^{sp}$) between $n_s$ and $n_t$, i.e.
The following proposition
\proof{Proof of Proposition (ref)} Let angle $\theta(a)=0$ for all $a \in A$, and the payload $l$ and speed policy $\varv(a)$ be identical, i.e. $\varv(a)= \varv^*$, where $\varv^* \in \mathbb{R}$ is constant. Taking into account that $\sin \theta(a) = 0$ and $\cos \theta(a) =1$ for all $a \in A$, the GPP implies that,
Thus, the $\pi^{sp}$ satisfies this problem that proves the proposition. \Halmos \endproof
It is straightforward to verify that the greenest path is the fastest path when all road gradients are zero
; see Proposition (ref). Further notice that by Proposition (ref), the speed $c_{\varv}$ in (ref) is optimal for all arcs when $\theta(a)=0$ for all $a\in A$. This implies that a decision maker will believe the shortest path is the greenest path when she ignores elevation data.
Nonetheless, the improved emissions model and Proposition (ref) show that if the elevation data is considered, the speed along each segment of a path can change. Even under the static speed policy, the greenest path is not necessarily the shortest due to the non-linearity of emission along an arc when in the gradient. We note that the emission model does not explicitly account for acceleration and deceleration of a vehicle and so the estimates emissions $\mathcal{E}^*(\varv^d,l)$ are a lower-bound for the CO$_2$ emissions of a truck traveling from $n_s$ to $n_t$.
In this section, we explore the greenest path as the payload becomes arbitrarily large. Let $e_a^\prime (v)$ be the CO$_2$ emissions per unit payload when a truck traverses arc $a \in A$ with speed $v$, that is to say,
Consider two distinct connected vertices $n_s$ and $n_t$. Observe that under a speed policy $\varv:A\to\mathbb{R}^+$ and a constant load $l \in \mathbb{R}_+$, the greenest path, i.e. $\pi^g (\varv,l)$, minimizes the total CO$_2$ emissions and the total CO$_2$ emissions per unit payload between $n_s$ and $n_t$. Thus, we can interchangeably use the total CO$_2$ emissions and the total CO$_2$ emissions per unit payload to compute the greenest path.
Let $\Pi$ be the set of all paths from $n_s$ to $n_t$. Let $\Pi_d \subseteq \Pi$ be the subset of paths $\Pi$ that are entirely downhill with a slope below $\arctan(-C_r)$, i.e. $\tan \theta(a) < -C_r$ for all $a\in \pi$ with $\pi\in\Pi_d$. We can now state the definition of the asymptotic greenest path:
Note that the set $\Pi_d$ plays an important role in this definition. The emission per load vanishes for any sufficiently steep down downhill path ($\Pi_d\neq\emptyset$) because gravity will get the vehicle to its destination. Among all sufficiently steep downhill paths ($\pi\in\Pi_d$), the one with the least absolute emission is given by the second case in (ref). When gravity does not suffice to move a vehicle from its origin to its destination ($\Pi_d=\emptyset$) then the asymptotic greenest path is the one that minimizes emissions per load; see case 1 in (ref). The following proposition demonstrates that $\pi^{\infty}(\varv)$ exists and provides an explicit form to compute it.
We call $\pi^{\infty} (\varv)$ the asymptotic greenest path. Proposition (ref) explains that $\pi^{\infty} (\varv)$ is the fastest downward path $\pi \in \Pi_d$, if $\Pi_d$ is non-empty. Otherwise, it is the path with the minimum total augmented ascents, $h^{\prime}$. Evidently, $\pi^{\infty} (\varv)$ can be computed using the algorithms offered to solve the shortest path problem (e.g. Dijkstra1959). The requirement that $-90^\circ < \theta(a)+\arctan C_r < 90^\circ$ for all $a \in A$ is completely benign. \proof{Proof of Proposition (ref)} For all payloads $l \in \mathbb{R}_+$, and any speed policy $\varv$, $\pi^g(\varv, l)$ exists from $n_s$ to $n_t$, since by Equations (ref) and (ref) there are no negative emissions cycles between the vertices. Suppose that the payload $l$ satisfies,
Then for arc $a \in A$,
by Equations (ref) and (ref).
Suppose that $\Pi_d$ is a non-empty set. For this case, we use the total CO$_2$ emissions to compute the $\pi^{\infty}(\varv)$. Thus, by Equations (ref),
Then it follows that from Equation (ref) that
since $P$ and $c_e$ are constant across all arcs $a \in A$.
Now, suppose that $\Pi_d$ is an empty set. For this case, we use the total CO$_2$ emissions per unit load to compute $\pi^{\infty}(\varv)$. Thus, by Equation (ref),
as $-90^\circ < \theta(a)+\arctan C_r < 90^\circ$ for all $a \in A$ by supposition. Again, since $c_e$, $Q$, and $C_r$ are constant for all $a \in A$, by Equation (ref),
\endproof Proposition (ref) demonstrates the convergence of the $\pi^g(\varv , l)$ to the $\pi^{\infty}(\varv)$ for a very large payload. On the other hand, by Proposition (ref) the shortest path, $\pi^{sp}$, is the greenest path under the dynamic speed policy, i.e. $\pi^g(\varv^d,l)$, if $w+l=0$ and $\varv^{\min}(a) \leq c_{\varv} \leq\varv^{\max}(a)$ for all $a \in A$. The reason is that if $w+l=0$, the dynamic speed policy equals the static speed policy ($\varv^d=\varv^s$) by Proposition (ref). Therefore, one can argue that $\pi^g(\varv , l)$ diverges from $\pi^{sp}$ and converges to the $\pi^{\infty}(\varv)$ as the load increases. We will explore this idea in Section (ref) through numerical experiments.
Finally, if the payload $l$ satisfies Inequality (ref), by Proposition (ref), $\varv^d (a,l)$, for arc $a \in A$ can be computed as follows.
Consequently, if $\varv^{\min}(a)$ and $\varv^{\max}(a)$ are constant for all arcs $a \in A$ and if $\Pi_d$ is non-empty, then $\pi^{\infty}(\varv^d) = \pi^{\infty}(\varv^s)$, by Proposition (ref). Evidently, if $\Pi_d$ is empty then Proposition (ref) requires $\pi^{\infty}(\varv,l)$ to be independent of the speed policy $\varv$. As a result, $\pi^{\infty}(\varv^d) = \pi^{\infty}(\varv^s)$ if $\varv^{\min}(a)$ and $\varv^{\max}(a)$ are constant for all arcs $a \in A$.
In this section, we explore the value of using elevation data to inform routing and speed decisions to reduce emissions over a comprehensive data set. Additionally, we explore the major drivers of CO$_2$ emissions reduction. We benchmark the greenest path ($\pi^g$) and dynamic speed policy ($\varv^d$) against the shortest path ($\pi^{sp}$) and the static speed policy ($\varv^s$). Note that the shortest path is also the greenest path under a dynamic speed policy (i.e. $\pi^g(\varv^d,l) = \pi^{sp}$) if the effect of road gradients is ignored, as shown in Proposition (ref). We also study how the greenest path changes, $\pi^g (\varv , l)$, as the payload $l$ increases and how the asymptotic greenest path $\pi^{\infty}(\varv)$ performs in terms of CO$_2$ emissions reduction and similarity to $\pi^g (\varv , l)$. In our numerical experiments the asymptotic greenest path under the dynamic speed policy, i.e. $\pi^{\infty}(\varv^d)$, and the one under the static speed policy, i.e. $\pi^{\infty}(\varv^s)$, are identical since $\varv^{\min}(a)$ and $\varv^{\max}(a)$ are constant for all $a \in A$ (see Section (ref)), i.e. $\pi^{\infty} =\pi^{\infty}(\varv^d)=\pi^{\infty}(\varv^s)$.
Given a pair of source and target vertices and a constant payload $l$, we compute the relative CO$_2$ emissions reduction of one policy in comparison with another. In particular we study the CO$_2$ reduction of using path-speed policy 2, $d_2= (\pi_2, \varv_2, l)$, relative to path-speed policy 1, $d_1= (\pi_1, \varv_1, l)$, ($\%\mathcal{E}_{d_1}^{d_2}$) to quantify the benefit of using the elevation data in CO$_2$ reduction. That is to say, \[ \%\mathcal{E}_{d_1}^{d_2}=100 \cdot \frac{\mathcal{E} (\pi_1, \varv_1, l) - \mathcal{E} (\pi_2, \varv_2, l)}{\mathcal{E} (\pi_1, \varv_1, l)}, \] where $\mathcal{E} (\pi_i, \varv_i, l), i=1,2$ is the total CO$_2$ emissions as per Equation (ref). If $\pi_i$, $i=1,2$, is a greenest path then $\pi_i = \pi^g(\varv_i,l)$. Similarly, we compute the relative distinction between the paths of policies $\pi_1$ and $\pi_2$ ($\%\delta_{\pi_1}^{\pi_2}$) weighted by distance, as follows. \[ \%\delta_{\pi_1}^{\pi_2} =100 \cdot \sum_{a \in \pi_1 \setminus \pi_2} \delta(a) \mathbin{/} \sum_{a \in \pi_1} \delta(a). \] Table (ref) briefly summarizes the ratios that we use in our comparative studies.
In Section (ref), we outline the test-bed that we consider. This test-bed comprises 25 cities and all the ratios in Table(ref) are computed for instances in this test-bed. We present the results of our computations in Sections (ref) through (ref). Section (ref) focuses on the results for the CO$_2$ emissions reduced by $\pi^g$ and $\varv^d$ relative to $\pi^{sp}$ and $\varv^s$. In Section (ref), we address the distinctions between $\pi^g$ and $\pi^{sp}$ and the effect of the speed policies $\varv^s$ and $\varv^d$ on the greenest path. In Section (ref), we study the asymptotic greenest path $\pi^{\infty}$ and explore the performance of $\pi^{\infty}$ relative to the shortest path $\pi^{sp}$ and the greenest path $\pi^g$ in terms of CO$_2$ emissions reduction. In Sections (ref) through (ref), we elaborate on how payload affects our results. Finally, Section (ref) concentrates on the major determinants of CO$_2$ emissions reduction and path alteration.
We consider the 25 cities shown in Table (ref) and three truck types, namely heavy-duty diesel (HDD), medium-duty diesel (MDD), and light-duty diesel (LDD) for which we utilise the typical parameters as found in Table (ref) of koc2014.
We use OpenStreetMap's database OpenStreetMap to obtain the information of a 2D road network including all vertices within a 20 km radius around a manually selected point for each city. We only use roads that the database designates as public and driveable OMNXDoc. We only consider arcs with a gradient ranging from $-10\%$ to $10\%$ (i.e. $[-5.71^{\circ},5.71^{\circ}]$) so that gradients are in line with the implicit assumptions of the modified emissions model (ref). We retrieve the elevation (height above sea level) of the vertices from the USGS's SRTM 1 Arc-Second Global data sets. We consider payloads of $30\%$, $40\%$, $50\%$, $60\%$, $70\%$, and $80\%$ of the maximum capacity for each truck type. For all arcs the $\varv^{\max}=90$ km/h and $\varv^{\min}=20$ km/h.
We select several unique pairs of source and target vertices uniformly at random for each city. We make sure that the vertices in each pair are non-identical and connected. The number of selected pairs of vertices (sample size) for each city is presented in Table (ref).
The Dijkstra algorithm Dijkstra1959 is used to solve the shortest path and the greenest path problems. We use the arcs' distance $\delta (a)$, $a \in A$, to compute the shortest path $\pi^{sp}$. We consider two speed policies, namely dynamic speed policy, $\varv^d$, and static speed policy, $\varv^s$ to calculate the the CO$_2$ emissions, $e_a(\varv,l)$, for all arcs. Then we use the calculated $e_a(\varv,l)$ to compute the greenest paths ($\pi^g(\varv^d,l)$ and $\pi^g(\varv^s,l)$). We use the Dijkstra algorithm to compute $\pi^{\infty}$ as per Proposition (ref).
We consider two sets of ratios, as shown in Table (ref), to compare the different path ($\pi^{sp}$, $\pi^g$, and $\pi^{\infty}$) and speed ($\varv^s$ and $\varv^d$) policies. The first group of ratios measure the relative CO$_2$ emissions reduction and the second group measures the geometrical distinctions between the paths. We compute the ratios for a full factorial combination of trucks and payloads traversing all samples, resulting in a total of more than $58.5$ million path selection instances with a total shortest distance of more than $1.27$ billion km. Evidently, it is hardly possible to determine CO$_2$ emissions experimentally by letting trucks drive $1.27$ billion km as the approaches of Boriboonsomsin2012 and Scora2015. The confidence intervals of any estimate reported later are negligibly small due to the large sample size. Considering the large test-bed, we notice that the distribution and the sample mean of the ratios varies between different cities. For a given city, we use the overbar to denote the average of a ratio across all instances within a city. For instance, $\overline{\%\mathcal{E}}_{(\pi^{sp}, \varv^s, l)}^{(\pi^g, \varv^d, l)}$ for a city represents the sample mean of $\%\mathcal{E}_{(\pi^{sp}, \varv^s, l)}^{(\pi^g, \varv^d, l)}$ for that city.
In this section, we consider the payload as a percentage of the truck's maximum carrying capacity rather than the payload in kilograms, to make the notations simpler. For instance, $l=60\%$ indicates that the payload equals 60% of the maximum capacity of the truck. Since the payload varies the results, we use $l=60\%$ as our base case to maintain consistency.
Figures (ref) through (ref) visualize the empirical distribution of CO$_2$ emissions reduction ratios for the base case instances. We present the distributions separately for each truck type and each city. The sample size of each empirical distribution is listed in Table (ref).
Figure (ref) shows that $\overline{\%\mathcal{E}}_{(\pi^{sp}, \varv^s, 60\%)}^{(\pi^g, \varv^d, 60\%)}$ lies between $4.11\%$ and $10.15\%$ for HDD trucks across all cities except Amsterdam. Figure (ref) also shows that $\%\mathcal{E}_{(\pi^{sp}, \varv^s, 60\%)}^{(\pi^g, \varv^d, 60\%)}$ decreases in truck class such that $\overline{\%\mathcal{E}}_{(\pi^{sp}, \varv^s, 60\%)}^{(\pi^g, \varv^d, 60\%)}$ ranges from $3.27\%$ to $8.65\%$ for MDD, and from $2.41\%$ to $7.00\%$ for LDD trucks, in the same cities. Amsterdam, a known flat city, is the lone exception, but even here $\overline{\%\mathcal{E}}_{(\pi^{sp}, \varv^s, 60\%)}^{(\pi^g, \varv^d, 60\%)}$ are $2.44\%$, $1.78\%$, and $1.19\%$, respectively, showing that it is possible to use significantly more fuel-efficient paths. The distribution of $\%\mathcal{E}_{(\pi^{sp}, \varv^s, 60\%)}^{(\pi^g, \varv^d, 60\%)}$, on the other hand, sheds more light on the potential CO$_2$ emissions reduction by using the greenest path with a dynamic speed policy, $\pi^g (\varv^d,60\%)$. In Los Angeles, for instance, $25\%$ of cases have a $\%\mathcal{E}_{(\pi^{sp}, \varv^s, 60\%)}^{(\pi^g, \varv^d, 60\%)}$ of at least $13.57\%$ for HDD, $10.14\%$ for MDD, and $7.00\%$ for LDD trucks. It may appear that these effects are larger than the numerical results of earlier studies, for instance Scora2015, Schroder2019 and Brunner2021. We submit that this is due to the long tail of the distribution of fuel savings which is found only with a sufficiently large sample.
To discern the individual effect of road gradient on CO$_2$ emissions reduction, we fix a speed policy $\varv \in \{\varv^s,\varv^d\}$ and then take into account the CO$_2$ emissions reduction by traveling along the greenest path $\pi^g(\varv , l)$ rather than the shortest path $\pi^{sp}$. We consider two ratios $\%\mathcal{E}_{(\pi^{sp}, \varv^s, l)}^{(\pi^g, \varv^s, l)}$ and $\%\mathcal{E}_{(\pi^{sp}, \varv^d, l)}^{(\pi^g, \varv^d, l)}$ to assess this effect. Figures (ref) and (ref) indicate the distribution and mean of these ratios for base case instances in different cities. Figure (ref) demonstrates that the selection of $\pi^g(\varv^s,60\%)$ rather than $\pi^{sp}$ can reduce, on average, $1.76\%$ to $8.15\%$ of the CO$_2$ emissions, if $l=60\%$ and $\varv^s$ is decided. As explained before, this CO$_2$ emissions reduction capacity is lower for the MDD and LDD trucks, yet remains substantive. In the case of a dynamic speed policy $\varv^d$, the statistics, i.e. $\%\mathcal{E}_{(\pi^{sp}, \varv^d, l)}^{(\pi^g, \varv^d, l)}$, remain close to that of $\varv^s$, i.e. $\%\mathcal{E}_{(\pi^{sp}, \varv^s, l)}^{(\pi^g, \varv^s, l)}$, but they are slightly smaller. This implies that regardless of speed, taking into account the road gradient results in significant reductions in CO2 emissions.
Next, to investigate the effect of speed policies on fuel-efficient paths and CO2 emissions reduction, we appraise the carbon reduction by modifying the policy from $(\pi^g, \varv^s, l)$ to $(\pi^g, \varv^d, l)$ for the same truck, i.e. $\%\mathcal{E}_{(\pi^g, \varv^s, l)}^{(\pi^g, \varv^d, l)}$. Figure (ref) shows that for most cities, $\overline{\%\mathcal{E}}_{(\pi^g, \varv^s, 60\%)}^{(\pi^g, \varv^d, 60\%)}$ is between $2\%$ and $4\%$, and in all cases the estimates do not depend on the truck type.
We contrast $\%\mathcal{E}_{(\pi^g, \varv^s, 60\%)}^{(\pi^g, \varv^d, 60\%)}$ and $\%\mathcal{E}_{(\pi^{sp}, \varv^d, 60\%)}^{(\pi^g, \varv^d, 60\%)}$, as shown in Figure (ref), in order to experimentally evaluate the relative efficacy of the greenest path and speed optimization in reducing CO2 emissions for each type of vehicle (i.e. HDD, MDD, and LDD). For HDD trucks, the road gradient is more crucial than the dynamic speed policy, whereas the dynamic speed policy has more impact for LDD trucks. The greenest path and dynamic speed policy can bring down the CO$_2$ emissions of MDD trucks to the same extent.
To analyze the effect of payload on CO$_2$ emissions reduction, we vary payload ratio for the base case instances ($30\%$, $40\%$, $50\%$, $70\%$, and $80\%$) and repeat the same experiments. Figures (ref) through (ref) present the distributions of the sample mean of the relative CO$_2$ emissions reduction ratios over the 25 cities, where the sample size of each box plot is 25. The figures also present the alteration of the distributions as the payload increases. These results show that, on average, $\overline{\%\mathcal{E}}_{(\pi^{sp}, \varv^s, l)}^{(\pi^g, \varv^d, l)}$ (Figure (ref)), $\overline{\%\mathcal{E}}_{(\pi^{sp}, \varv^s, l)}^{(\pi^g, \varv^s, l)}$ (Figure (ref)), and $\overline{\%\mathcal{E}}_{(\pi^{sp}, \varv^d, l)}^{(\pi^g, \varv^d, l)}$ (Figure (ref)) are non-decreasing in payload. However, all graphs are concave, so that the growth rate of $\overline{\%\mathcal{E}}$ decreases in payload. In many cities, this phenomenon results in a slow increase, and in one case (Shiraz) slight decrease of $\%\mathcal{E}_{(\pi^{sp}, \varv^s, l)}^{(\pi^g, \varv^d, l)}$ for HDD trucks. The same concave pattern takes place for $\overline{\%\mathcal{E}}_{(\pi^g, \varv^s, l)}^{(\pi^g, \varv^d, l)}$ (Figure (ref)) with the exception that the maxima of the concave functions are typically in the MDD or LDD regions. This result can explain the close range of $\%\mathcal{E}_{(\pi^g, \varv^s, l)}^{(\pi^g, \varv^d, l)}$ across different truck types as shown in Figure (ref).
The differences between the greenest path and the shortest path have been covered in earlier sections, along with an analysis of the impact of speed and road gradient. Although our findings indicate significant differences in fuel consumption and CO2 emissions, it is important to consider whether the shortest path's trajectory differs significantly from the trajectory produced by the greenest path.
To illustrate this difference, we consider a LDD truck that delivers cargo weighing 60% of its maximum capacity from point A to B within a district of Los Angeles, see Figure (ref). Figure (ref) displays the greenest paths ($\pi^g (\varv^d,l)$ and $\pi^g (\varv^s,l)$) and the shortest path path ($\pi^{sp}$) on the map, and Figure (ref) shows the elevation of the vertices and total CO$_2$ emissions for different path and speed choices. In this instance, $\pi^{sp}$ differs significantly from $\pi^g (\varv^d,l)$ and $\pi^g (\varv^s,l)$, whereas the two greenest paths share a number of arcs. In this section, we examine whether such an observation is common throughout our test-bed.
Figures (ref) through (ref) encapsulate the distribution and sample mean of $\%\delta_{(\pi^g, \varv^d, 60\%)}^{(\pi^g, \varv^s, 60\%)}$, $\%\delta_{\pi^{sp}}^{\pi^g (\varv^d, 60\%)}$, and $\%\delta_{\pi^{sp}}^{\pi^g (\varv^s, 60\%)}$ for the base cases. Figure (ref) shows that the average difference of $\pi^g (\varv^s, 60\%)$ and $\pi^g (\varv^d, 60\%)$ is between $1.16\%$ and $12.01\%$ across the cities. In fact, the quartiles of $\%\delta_{(\pi^g, \varv^d, 60\%)}^{(\pi^g, \varv^s, 60\%)}$ show that for the most part $\pi^g (\varv^d, 60\%)$ are quite similar to $\pi^g (\varv^s, 60\%)$. In other words, in a majority of instances, the greenest path is independent of the speed policy. Additionally, for heavier trucks the greenest path is less likely to vary as a result of speed optimization. Figures (ref) and (ref) show that the distinction between the shortest and the greenest paths, i.e. $\%\delta_{\pi^{sp}}^{\pi^g(\varv^d,60\%)}$ and $\%\delta_{\pi^{sp}}^{\pi^g(\varv^s,60\%)}$, are conspicuously larger than the distinction between the greenest paths, i.e. $\%\delta_{\pi^g(\varv^d,60\%)}^{\pi^g(\varv^s,60\%)}$. This gap intensifies with heavier truck classes.
To expand our understanding of the payload's influence on paths, we study whether $\pi^g (\varv^s, l)$ and $\pi^g (\varv^d, l)$ converge to each other and diverge from $\pi^{sp}$ as the payload increases. Figures (ref) and (ref) demonstrate that both $\overline{\%\delta}_{\pi^{sp}}^{\pi^g (\varv^d, l)}$ and $\overline{\%\delta}_{\pi^{sp}}^{\pi^g (\varv^s, l)}$ are non-decreasing in payload in contrast to $\overline{\%\delta}_{(\pi^g, \varv^d, l)}^{(\pi^g, \varv^s, l)}$ which is mostly decreasing, as indicated by Figure (ref). Note that, $\overline{\%\delta}_{\pi^{sp}}^{\pi^g (\varv^s, l)}$ is always higher than $\overline{\%\delta}_{\pi^{sp}}^{\pi^g (\varv^d, l)}$ since the more efficient dynamic speed policy of $\pi^g (\varv^d , l)$ usually allows for a shorter (and faster) path relative to $\pi^g (\varv^s , l)$. However, increase in payload erodes the impact of speed policy.
The greenest path converges to the asymptotic greenest path for arbitrarily large payloads as shown in Section (ref). In this section, we study the performance of the asymptotic greenest path relative to the shortest path and the greenest path. Then we study the rate of convergence of the greenest path to the asymptotic greenest path for the dynamic speed policy. In Appendix (ref) we study these things under the static speed policy. Figures (ref) and (ref) show that the distribution of the CO$_2$ emissions reduction of $\pi^{\infty}$ relative to $\pi^{sp}$ and $\pi^g(\varv^d, 60\%)$ for different cities. Similar to Section (ref), we present the results for the base cases (60% payload ratio).
Figure (ref) shows that for the most part an LDD truck emits slightly more CO$_2$ if it traverses $\pi^{\infty}$ instead of $\pi^{sp}$ in 18 cities. Whereas, the $\pi^{\infty}$ is greener than the $\pi^{sp}$ for MDD and HDD trucks in more than 50% of the instances in all cities.
The CO$_2$ emissions reduction of $(\pi^{\infty},\varv^d , 60\%)$ relative to $(\pi^g,\varv^d , 60\%)$, i.e. $\%\mathcal{E}_{(\pi^g, \varv^d, 60\%)}^{(\pi^{\infty}, \varv^d, 60\%)}$, is consistent with this observation. Figure (ref) shows that the median of extra CO$_2$ emissions along $\pi^{\infty}$ compared to the $\pi^g(\varv^d,60\%)$ ranges from 0.48% to 2.70% for LDD trucks. This range decreases to between 0.11% and 1.40% for MDD trucks, and 0% and 0.45% for HDD trucks. Figure (ref) shows the distribution of the sample mean of $\%\mathcal{E}_{(\pi^{sp}, \varv^d, l)}^{(\pi^{\infty}, \varv^d, l)}$ across the 25 cities for various payload ratios, i.e. $\overline{\%\mathcal{E}}_{(\pi^{sp}, \varv^d, l)}^{(\pi^{\infty}, \varv^d, l)}$. Correspondingly, Figure (ref) presents $\overline{\%\mathcal{E}}_{(\pi^g, \varv^d, l)}^{(\pi^{\infty}, \varv^d, l)}$.
The two figures show that the average CO$_2$ emissions along $\pi^{\infty}$ relative to $\pi^{sp}$ and $\pi^g (\varv^d,l)$ is non-increasing in load, $l$. Evidently, $\pi^{sp}$ outperforms $\pi^{\infty}$ in terms of average CO$_2$ emissions for LDD trucks with any payload ratio. Whereas, $\pi^{\infty}$ is on average greener than $\pi^{sp}$ for MDD and HDD truck types for all payload ratios. The mean excess CO$_2$ emissions of $\pi^{\infty}$ relative to $\pi^g (\varv^d,l)$ is less than 1%, 2%, and 3% for HDD, MDD, and LDD trucks, respectively.
The median of the difference between $\pi^g (\varv^d, l)$ and $\pi^{\infty}$, i.e. $\%\delta^{\pi^{\infty}}_{\pi^g (\varv^d, 60\%)}$, varies between 4.97% and 49.14% for the LDD trucks in base cases as Figure (ref) shows. However, the similarity increases in MDD and HDD truck types as the median $\%\delta^{\pi^{\infty}}_{\pi^g (\varv^d, 60\%)}$ ranges from 2.84% to 34.81% for MDD trucks and 0% to 18.14% for HDD trucks.
Moreover, the difference between the $\pi_{(\pi^g, \varv^d, l)}$ and $\pi^{\infty}$ reduces in the payload ratio in all truck types.
Figures (ref) and (ref) show that $\pi^g ( \varv^d, l)$ converges to $\pi^{\infty}$ in the payload ratio as established in Proposition (ref). These results confirm that $\pi^g ( \varv^d, l)$ diverges from $\pi^{sp}$ (Figures (ref) and (ref)) and converges to $\pi^{\infty}$ (Figures (ref) and (ref)) as the payload (and curb weight) increases.
In this section, we address the major determinants of the CO$_2$ emissions reduction and path alteration. We consider the following input features: city, truck type, payload, the elevation difference of source and target ($\Delta h$), the distance of the shortest path ($\delta^{sp}$) and the standard deviation of the gradients along the shortest path ($\sigma^{sp}({\theta})$). The latter characterizes the hilliness of the shortest path. All of these features can be efficiently computed. We use linear regression accompanied by the analysis of variance (ANOVA) to regress these features against seven responses, namely $\%\mathcal{E}_{(\pi^{sp}, \varv^s, l)}^{(\pi^g, \varv^d, l)}$, $\%\mathcal{E}_{(\pi^{sp}, \varv^d, l)}^{(\pi^g, \varv^d, l)}$, $\%\mathcal{E}_{(\pi^{sp}, \varv^s, l)}^{(\pi^g, \varv^s, l)}$, $\%\mathcal{E}_{(\pi^g, \varv^s, l)}^{(\pi^g, \varv^d, l)}$, $\%\delta_{\pi^{sp}}^{\pi^g (\varv^d, l)}$, $\%\delta_{\pi^{sp}}^{\pi^g (\varv^s, l)}$, and $\%\delta_{(\pi^g, \varv^d, l)}^{(\pi^g, \varv^s, l)}$. We apply min-max normalization for the continuous features and dummy encode the categorical features. The encoding removes the redundant dummy features including Canberra and HDD among cities and trucks, respectively. We use the type III sum of squares in the ANOVA. The full report is available in Appendix (ref).
Table (ref) summarizes the ranking and sign of different features in the ANOVA as per Appendix (ref). By the results, $\sigma^{sp}(\theta)$, i.e. the standard deviation of road gradient along the $\pi^{sp}$ has the most explanatory power for CO$_2$ reduction capacity. In addition, $\sigma^{sp}(\theta)$ is has the strongest association with the dissimilarity of the greenest and shortest paths. That is to say, a higher $\sigma^{sp}(\theta)$ indicates a higher potential of CO$_2$ emissions reduction by selecting the greenest path instead of the shortest path. Next comes difference in elevation between the target and the source, $\Delta h$, which is negatively associated with the CO$_2$ emissions reduction capacity. This relation is strongest when comparing the dynamic speed policy with the static speed policy as in $\%\mathcal{E}_{(\pi^g,\varv^s,l)}^{(\pi^g,\varv^d,l)}$. This implies that using elevation data in routing policies is more pivotal for downward trips. Table (ref) also reveals the positive association of $\%\mathcal{E}_{(\pi^{sp}, \varv^d,l)}^{(\pi^g, \varv^d,l)}$ and $\%\mathcal{E}_{(\pi^{sp}, \varv^s,l)}^{(\pi^g, \varv^s,l)}$ with payload. Our analysis shows that relative dissimilarity of the shortest and greenest paths increases in distance of the shortest path, i.e. $\delta^{sp}$. However, $\delta^{sp}$ is less important for CO$_2$ emissions reduction. A city's individual characteristics have a fair impact on the CO$_2$ emissions reduction capacity, albeit this effect is not comparable with that of $\sigma^{sp}(\theta)$ and $\Delta h$. Finally, the truck type has an effect that is similar to the payload. It follows that curb weight and payload of truck are more significant than other parameters for the CO$_2$ emissions reduction.
\begin{rev2}
The first outcome of our experiments in Sections (ref) and (ref) is that high-resolution topographical data should be incorporated into urban truck transportation decisions when minimizing CO$_2$ emissions is the objective. Specifically, pre-computation of the greenest paths is not feasible due to the non-linear effects of speed decisions, road gradients, and payload. A similar argument has previously been made regarding the need to integrate high-resolution traffic speed data into emissions-minimizing transportation decisions Ehmke2016b.
Secondly, our results show that optimal speed decisions are dynamic, with dynamic speed choices reducing CO$_2$ emissions by 2% to 4% in free-flow conditions compared to static speed choices. While the difference between dynamic and static speed decisions is less significant in traffic, we found that optimized speeds still achieve significantly lower emissions than traffic speeds, even when acceleration is restricted by traffic congestion.
Thirdly, we observed that the greenest path is relatively insensitive to whether speed decisions are static or dynamic, even in free-flow conditions. Additionally, the greenest path begins to converge to the asymptotic greenest path at low payload ratios under both free-flow and traffic conditions. Therefore, a pre-computed greenest path for a given speed decision (e.g., static) and payload level (e.g., 50% or 100%) can be a good approximation for the greenest paths across different speed decisions and payloads. This approximation can help reduce the computational complexity of green transportation problems like PRP. \end{rev2}
In this paper, we studied the greenest path selection problem for a logistics service provider that operates a fleet of heavy-, medium-, and light-duty trucks in an urban environment. We established that the policies for the speed and path that minimize CO$_2$ emissions are slope-dependent (dynamic). We also showed that the greenest path converges to a fixed path as the payload increases and provided an efficient algorithm to compute the asymptotic greenest path. We conducted extensive numerical experiments using elevation data of 25 cities around the world to investigate the potential CO$_2$ reduction by such dynamic policies
The results in section (ref) showed that, on average, the combined dynamic path and speed selection can reduce CO$_2$ emissions by 1.19% to 10.15% based on the truck type and city. Our analysis also showed that in most cities, the average emissions reduction potential of dynamic speed optimization lies between 2% to 4% regardless of the truck type. Nonetheless, the effect of slope-dependent path selection (the greenest path) depends on the payload and truck type.
In section (ref), we explained that the greenest path significantly differs from the shortest path. While the greenest path depends on the speed policy, the experiments show that this dependence is weak and that the greenest path under the static speed policy is usually optimal or near optimal
Moreover, we demonstrated, in Sections (ref) and (ref), that the greenest path diverges from the shortest path as the payload increases and converges to the asymptotic greenest path, i.e. the greenest path for the arbitrary large payloads.
These results could be used for the approximation of the greenest path to simplify complex transportation problems. The analysis of variance (ANOVA) indicated that the potential CO$_2$ emissions reduction by the greenest path and the dynamic speed policy is associated positively with the variability of arc gradients along the shortest path, and negatively with the relative elevation of the source and target.
\ACKNOWLEDGMENT{ We thank Dennis Davydov for sharing initial explorations on this topic and Tiffany Nguyen for extensive feedback on early drafts. }
The authors did not receive support from any organization for the submitted work. The authors have no relevant financial or non-financial interests to disclose.