An Alternative Approach for Solving the Environmentally-Oriented Discrete Network Design Problem

Abstract

This paper addresses the discrete network design problem (DNDP) with emphasis on the environmental benefits. These benefits are traditionally quantified by emission models, which in general account for vehicle speeds, traffic flows and emission coefficients. An alternative approach for approximating the environmental impact of traffic is developed. This approach finds the route that keeps the most balanced speed profile throughout the route, which contributes to fuel consumption reduction. The paper formulates an optimization problem that includes the described approach for the DNDP. The solution of the problem consists of projects that contribute the most to the generation of such “balanced speed routes”. The paper illustrates the problem and the solution for a real-size network with a medium-size set of candidate projects.

1 Introduction

Due to their scale and character, transportation infrastructure projects bear tremendous implications on the environment. These implications are caused as a result of the change of flow patterns, once different infrastructure projects are implemented in the network. For this reason, when planning such projects, their environmental impacts should be considered alongside other impacts, such as network system time, travel costs, or road safety. This notion has contributed to the development of different models for the evaluation of environmental impacts of transportation.

When attempting to define the different environmental externalities caused by transportation development, several components may be considered, such as emissions, noise, loss of open space etc. Among these components, no environmental evaluation is complete without traffic emissions. This component stands in the center of the current paper.

In order to evaluate the emissions at the network level, macroscopic traffic models integrated with emission models are generally applied. In most cases, the speed and the flow on the links, which can be inferred from traffic assignment models, serve as main components in the emission model. By calculating the emission for each link in the network, the total emission can be derived. The total emission then serves as an indicator to the total environment impact of a certain network configuration.

Alongside the development of emission models, another view has been evolved in recent years, which stresses the role of the users in decreasing emissions and fuel consumption. This view plays a key role in the development of two new concepts: eco-driving and eco-routing. According to the eco-driving concept, in order to decrease emissions, the driver should strive to drive as smoothly as possible, by maintaining steady speeds and avoiding too many accelerations and decelerations (Boriboonsomsin et al. 2010). Eco-routing, on the other hand, promotes the idea of choosing routes that result in lower emissions. These routes are those where eco-driving principles can be most easily implemented. This is mainly due to the relatively stable speed-profile of these routes.

In this paper, we present an alternative method for the evaluation of the environmental impact of traffic in a network. This method is inspired by the eco-routing and eco-driving concepts. According to this method, the optimal network configuration would be one that will generate routes which are characterized by a smooth speed-pattern, that is, routes with minimal speed variability. Based on this new method, we solve an environmentally-oriented discrete network design problem (DNDP) and apply it on a real-size network.

The outline of this paper is as follows. In the next section, a review of previous studies in the field of emission models, and the use of eco-driving and eco-routing concepts is presented. Then the methodology used in this paper is detailed, followed by a case study applying the presented methodology. Finally, conclusions and further research directions are proposed.

2 Literature Review

Evaluating the environmental externalities caused by transportation projects can be very challenging. Not only do the evaluation methods of environmental externalities change from one agency to another, but the decision regarding which components should be evaluated changes as well. Some agencies such as the US transportation agency divide these externalities according to the costs they incur. The fixed costs take into account the loss of natural spaces, while the variable costs take into account emissions. With this respect, efforts are being made in two directions: reducing emissions per vehicle mile and reducing vehicle miles traveled (Lee 2000). In Japan, the externalities taken into account are noise and emissions (Murisugi 2000), and in the UK the environmental evaluation is comprised of a series of different measures including global emissions, local air quality, noise, landscape, biodiversity and water (Vickerman 2000).

The above examples show that although the project evaluation methods might vary from one place to the other, they always include the evaluation of emissions. Therefore in the following sub-sections different aspects related to emission evaluation and integration in transportation models are reviewed. First emission models are presented, then transportation models integrating emission models and network optimization accounting for emission reduction. The last section presents the eco-routing and eco-driving concepts that inspired the development of the proposed method.

2.1 Emission Models

When evaluating emissions, several vehicle-related features should be examined such as the model of the vehicle, its size, fuel type and mileage, and in addition operational factors such as speed, acceleration, gear selection or road gradient (Boulter et al. 2009).

Different models have been developed over the years for the evaluation of emissions. Some of these models are designated for evaluating the network-wide emissions, while others are too detailed for implementation on a large scale. Among the models applicable for large networks are traffic situation models, average speed models and regression models (Wismans et al. 2011a). These models differ from each other in their required level of detail. Average speed models are prominently based on the speed on the links; situation models and regression models make use of additional information such as the current condition of the traffic (e.g. ‘stop-and-go-driving’, ‘free-flow motorway driving’) (Smit et al. 2010), and a set of additional descriptive parameters (e.g. acceleration and number of stops per kilometer) (Wismans et al. 2011a).

Other types of models suitable for analysis of specific parts of the networks are driving mode/modal models or instantaneous speed-based models (Wismans et al. 2011a). In contrast to network-wide models, these models are much more detailed, and require additional information such as traffic density, queue length and signal settings (Treiber and Kesting 2013).

Several software tools are commonly used for evaluating network-wide emissions. In the US for example, MOVES - Motor Vehicle Emission Simulator, developed by the EPA is used (EPA 2015). MOVES is used for calculating overall emissions and emission factors based on a varied data such as vehicle types and age, pollutant types, road types, time periods and geographical areas. The data is supplied either by the user or generated based on existing default database, or by using a mixture of both user-supplied and default data. Several studies have been conducted taking advantage of this tool, for various purposes. In Gardner et al. (2013), regression functions representing the overall energy consumption and the emission factors were calculated based on the MOVES, as function of the average speed. Later on, these functions were used to examine the impacts of using plug-in electric vehicles in the network on the overall emission level and the consumed energy.

2.2 Transportation Models Integrating Emission Models

With the increase in environmental awareness, there have been additional applications of emission models integrated with traffic assignment models. These models can be useful for policies promoting emission reduction. Szeto et al. (2012) provided a comprehensive review of different studies concentrating on the development of models used for sustainability optimization. As this review confirms, various models have been developed in recent years, putting sustainability issues in the spotlight. Those models highlighted different aspects with respect to sustainability, especially when compared to traditional traffic models, concentrating on system time minimization.

Benedek and Rilett (1998) compared between the user equilibrium and system optimum values when travel time minimization versus CO emission minimization is sought. In their sample network, the reduction in CO emission did not exceed 7%, when the emission-based traffic assignment was compared with travel time-based one.

Ahn and Rakha (2008) examined the total emission in a small sample network. The results in this case showed that neither system optimum nor user equilibrium ensures emission minimization. In other studies, the focus was shifted towards determining the optimal flow in the network when several objectives are considered, as in Tzeng and Chen (1993). In this case, travel time minimization, travel distance minimization and emission reductions were sought in parallel. For this purpose, the objective function was formulated using a weighted sum of all objectives.

In addition to the use of static macro-simulation used in the aforementioned studies, other models relied on other simulation-based tools. Zhang et al. (2010) developed a static mesoscopic model, which considered both travel time and emissions. As in Tzeng and Chen (1993), here also both objectives were integrated into a single objective function using a weighted sum. In other cases, dynamic models were used. These models were based on either mesoscopic simulation (Abdul Aziz and Ukkusuri 2012) or micro-simulation (Nesamani et al. 2007). These dynamic models, as opposed to the static ones, allowed for the examination of emissions over time. A study conducted by Wismans et al. (2011b) confirmed that dynamic models outperform the static ones, when estimation of emissions is considered.

2.3 The Discrete Network Design Problem Solved for Emission Reduction

The Discrete Network Design Problem (DNDP) is well-known in the transportation literature (e.g. LeBlanc 1975). The problem is to find the optimal set of transportation projects, out of a given candidate set, under a given budget. Usually the focus is on minimizing the system time of the network (Farvaresh and Sepehri 2013), but in recent years, several other models have been developed focusing on additional objectives, including environmental aspects.

Over the years many studies have been conducted, developing different models solving different variations of the Network Design Problem (NDP), while emphasizing different aspects of the problem (Uchida et al. 2007; Miandoabchi et al. 2012). In their review, Xu et al. (2016) discussed recently developed models, which integrate both system time minimization and emission reduction. Sharma and Mathew (2011), for example, developed a multi-objective model that concentrated on minimizing both travel time and emissions, and was formulated as a bi-level problem. The upper level was formulated as an optimization problem seeking to minimize both the travel time and emissions depending on the links chosen for expansion, and in the lower level, user equilibrium was solved. The genetic algorithm was used for finding the Pareto-optimal solutions. In this case, the problem was not discrete, as the capacity expansion of a link could take any value up to 100% increase of original the capacity.

Noise is also considered in many cases together with emissions. Szeto et al. (2014) solved the DNDP for capacity expansions, for multiple objectives: minimizing emissions, noise and travel time. A single objective function represented the sum of all objectives, expressed in monetary terms. The Chemical Reaction Optimization, a relatively new meta-heuristic method, was used to solve the problem. Gallo et al. (2012) also integrated both travel time minimization with emission minimization, and formulated the objective function as a weighted sum of both these measures. In this case, the optimization problem was solved using the scatter search algorithm. In another recent study of Jiang and Szeto (2015), the DNDP problem was solved for several consecutive time periods. In this study, the emission model was also considered alongside the noise, travel time and the network safety level. In another study (Szeto et al. 2015) also taking into account several time periods, and concentrating on optimal capacity expansions, four different indicators were taken into consideration: vehicle emissions, consumer surplus, the landowner profit and the variance of the generalized user cost over time.

Note that all the described studies used emission models that are mainly based on the average link speed together with other aggregate information such as the emission per unit length, and the length of a link (Sharma and Mathew 2011), or the emission per unit time (Abdul Aziz and Ukkusuri 2012). In other cases, some more detailed information such as the emission level for different vehicle types is used (Jiang and Szeto 2015).

Instead of integrating the environmental impacts as an additional or main objective, in several other formulations these impacts are considered as a constraint. One of the relevant questions when using this sort of formulation is to what extent the optimal solution deteriorates when using such an approach. This issue was examined in a recent study (Lin et al. 2016). In this study, an approach was proposed for examining the loss of optimality caused as a result of integrating environmental impacts as a constraint while solving the NDP. In this paper we choose the former presented approach, and consider the environmental impacts in the objective function.

2.4 The eco-Driving and eco-Routing Concepts

Considering emissions in transportation modeling is one of the first steps towards creating a more sustainable transport. However, alongside the development of emission models, several other notions have been recently developed, highlighting the role of the user in creating a more sustainable transport. According to these notions, users can contribute substantially to the environment by adapting a set of principles concerning their travel habits. These include (but not limited to) purchasing fuel-efficient vehicles, using more sustainable travel-modes like public transit, car pooling or cycling, and changing their driving style (Barckenbus 2010).

Changing the driving style to a more sustainable one has become known as “eco-driving”. This term stands for adapting a “smoother” driving style that includes moderate accelerations, avoidance of sudden starts and stops, maintaining even driving pace, driving at or below speed limit and avoiding excessive idling (Barckenbus 2010). The benefits of adopting eco-driving style with respect to the reduction of emissions were confirmed in studies focusing specifically on the effects of different driving patterns on the level of emission and fuel consumption (Ericsson 2001; Saboohi and Farzaneh 2009). The overall benefits of adapting such a driving style are not limited to emissions reduction but also advance increased safety and reduced driving costs (Barckenbus 2010).

Several studies have been conducted aiming at utilizing the advantages of eco-driving. These studies concentrated on real-time feedback regarding recommended driving speed, based on traffic conditions that would minimize speed variation (Barth and Boriboonsomsin 2009; Boriboonsomsin et al. 2010). With this respect, vehicle to infrastructure systems (V2I) can also be used to assist with formulating such speed recommendations (Rakha and Kamalanathsharma 2011; Barth et al. 2011). In these studies, the focus was put on efficient fuel consumption at signalized intersections and arterial corridors, where information concerning the signal phase was transmitted to the vehicle. Other studies focused on supplying the users with an analysis of their travels, in the light of eco-driving principles (number of steep accelerations / deceleration, emission level evaluation, etc.) after the travels have been performed (Ando et al. 2010).

The common focus of the above studies is on studying driver behavior, trying to provide the drivers with a set of recommendations that would make their driving style a more “eco-driving oriented”. A different approach put a greater emphasis on the choice of the routes, by providing drivers with recommendations concerning the route that would minimize their emission production (Minett et al. 2011; Boriboonsomsin et al. 2012). This approach is called “eco-routing”. The choice of the proposed route is based on the calculation of emissions, using emission models.

Several models and applications have been developed utilizing the idea of eco-routing. Minett et al. (2011) compared the emission of different routes connecting several OD pairs, which were calculated based on speed profiles, to the real values obtained in a field-test. In Boriboonsomsin et al. (2012) a navigation system was developed for proposing optimal routes based on pre-specified minimization criteria (distance, travel time, fuel consumption or emissions). In this case, the proposed routes were based on multiple data sources including real-time traffic information. Rakha et al. (2012) developed a micro-simulation model that dynamically assigns vehicles to routes according to their expected fuel consumption, based on experience of other vehicles. In a later study, Ahn and Rakha (2013) developed a model to evaluate system-wide impacts of using eco-routing strategies. The evaluation was performed with respect to the fuel consumption and emissions, when compared with traffic assignment based on travel time minimization. The results of this study showed that implementing eco-routing strategies in a network could significantly affect the overall fuel consumption, depending on the network configuration.

Other studies addressed the issue of eco-routing with respect to the dynamically changing traffic conditions of the network throughout the day, as in Bandeira et al. (2011). In some other cases, several more objectives were incorporated in the problem. In Guo et al. (2015), for instance, a system was developed which supplies time-dependent recommendations about the optimal paths based on three objectives: minimizing emission, travel time and travel length.

The eco-routing studies above focus on the operating stage, namely, advise drivers which route they should choose, given a set of traffic conditions. However, to the best of our knowledge, the idea of generating routes which are characterized by relatively low emissions, has not yet been applied with respect to the planning stage. Inspired by both the eco-routing and eco-driving concepts, in this study we aim at solving the DNDP, while using an alternative environmental approximation. This approximation is based on finding the speed variability along the used routes.

3 Methodology

This section starts with the general definition of the DNDP problem. Then we present the environmental approximation that will be later integrated in the upper level of the DNDP. After that, the use of this approximation method is demonstrated on a small network.

3.1 DNDP General Problem Formulation

The general DNDP problem follows a bi-level formulation, where the upper level represents the decision makers’ perspective, and the lower level, the users’ perspective (e.g. Yang and Bell 1998). In our case, the decision makers’ objective is to minimize the environmental impact of traffic in the network. This is performed by changing the current configuration of the network. The lower level is a solution to the user equilibrium, representing the users’ point of view, seeking to minimize their travel time.

In this paper, we consider two types of projects: lane additions to existing roads, and interchange constructions. Each project type corresponds to a different network configuration, and correspondently each combination of projects is represented by changing the network topology according to the specific set of projects in the combination. To properly address the different combinations, the lower level of the problem (which corresponds in this paper to the deterministic user equilibrium problem) is modified to cope with the different set of links that will compose a project (or a combination of projects). In order to keep the mathematical formulation as general as possible, in the formulation we consider another type of project, not considered in this paper - the addition of new sections to the network.

This model can be stated as follows:

Upper level:

$$ \mathrm{Maximize}\ Z\left( x, f\right) $$

(1)

s.t.

$$ \sum_{i\_ e\in I\_ E}{c_{i\_ e}\bullet x}_{i\_ e}+\sum_{i\_ v\in I\_ V}{c_{i\_ v}\bullet x}_{i\_ v}\le B $$

(2)

$$ 1+\sum_{l\_ e\in i\_ e}{\gamma}_{l\_ e}-{N\_ L}_{i\_ e}\le M\bullet {x}_{i\_ e}\forall {i}_e\in I\_ E $$

(3)

$$ 1+\sum_{l\_ v\in i\_ v}{\gamma}_{l\_ v}-{N\_ L}_{i\_ v}\le M\bullet {x}_{i\_ v}\forall {i}_v\in I\_ V $$

(4)

Lower level:

$$ \begin{array}{l}\mathrm{Minimize}\ H=\sum_{l\_ p\in L\_ P}\underset{0}{\overset{f\_{o}_{l\_ p}}{\int }} t\_{o}_{l\_ p}\left(\theta \right) d\theta +\sum_{l\_ e\in L\_ E}\underset{0}{\overset{f_{l\_ e}}{\int }}{t}_{l\_ e}\left(\theta \right) d\theta \\ {}+\sum_{l\_ v\in L\_ V}\underset{0}{\overset{f_{l\_ v}}{\int }}{t}_{l\_ v}\left(\theta \right) d\theta +\sum_{l\_ v\in L\_ V}\underset{0}{\overset{f\_{o}_{l\_ v}}{\int }} t\_{o}_{l\_ v}\left(\theta \right) d\theta \end{array} $$

(5)

s.t.

$$ \sum_{k\_ rs\in K\_ RS}\ {h}_{k\_ rs}^{rs}={q}_{rs}\kern0.5em \forall r, s\in D $$

(6)

$$ {h}_{k\_ rs}^{rs}\ge 0\kern0.5em \forall r, s\in D;\forall k\in K\_ RS $$

(7)

$$ {f}_{l\_ e}{\le M\bullet \gamma}_{l\_ e}\forall l\_ e\in L\_ E $$

(8)

$$ {f}_{l\_ v}{\le M\bullet \gamma}_{l\_ v}\forall l\_ v\in L\_ V $$

(9)

$$ {f\_ o}_{l\_ v}{\le M\bullet \gamma \_ o}_{l\_ v}\forall l\_ v\ \in\ L\_ V $$

(10)

$$ {\gamma}_{l\_ v}\le M\bullet \left(1\_\gamma \_ ol\_ v\right)\forall l\_ v\ \in\ L\_ V $$

(11)

$$ {f}_{l\_ p}=\sum_{r\in D}\sum_{s\in D}\sum_{k\_ rs\in K\_ RS}\sum_{p\in P}{h}_{k\_ rs}^{r s}\bullet {\delta}_{l\_ p, k\_ rs}^{r s}\forall l\_ p\in L\_ P $$

(12)

$$ {f}_{l\_ e}=\sum_{r\in D}\sum_{s\in D}\sum_{k\_ rs\in K\_ RS}\sum_{e\in E}{h}_{k\_ rs}^{r s}\bullet {\delta}_{l\_ e, k\_ rs}^{r s}\forall l\_ e\in L\_ E $$

(13)

$$ {f}_{l\_ v} + {f\_ o}_{l\_ v} = \sum_{r\in D}\sum_{s\in D}\sum_{k\_ rs\in K\_ RS}\sum_{v\in V}{h}_{k\_ rs}^{r s}\bullet {\delta}_{l\_ v, k\_ rs}^{r s}\forall l\_ v\in L\_ V\kern0.5em $$

(14)

$$ {x}_{i\_ e}\in \left\{0,1\right\}\kern1.75em \forall i\_ e\in I\_ E $$

(15)

$$ {x}_{i\_ v}\in \left\{0,1\right\}\kern1.75em \forall i\_ v\in I\_ V $$

(16)

$$ {\gamma}_{l\_ e}\in \left\{0,1\right\}\kern1.75em \forall l\_ e\in L\_ E $$

(17)

$$ {\gamma}_{l\_ v}\in \left\{0,1\right\}\kern1.75em \forall l\_ v\in L\_ V $$

(18)

$$ {\gamma \_ o}_{l\_ v}\in \left\{0,1\right\}\kern1.75em \forall l\_ v\in L\_ V $$

(19)

where,

G(N, A):

transportation network, with N and A being the sets of nodes and links, respectively A = {P ∪ E ∪ V}

Z :

approximation of the benefit of the environmental impact of a certain network configuration

c _{i_e} :

the cost of “new section” project i_e

c _{i_v} :

the cost of “lane addition / interchange construction” project i_v

x _{i_e} :

$\left\{\begin{array}{cc}1& {}^{"}\mathrm{new}{\mathrm{section}}^{"}\mathrm{project} i\_ e\mathrm{is}\ \mathrm{chosen}\ \mathrm{for}\ \mathrm{implementation}\\ {}0& \mathrm{otherwise}\end{array}\right.$

x _{i_v} :

$\left\{\begin{array}{cc}1& {}^{"}\mathrm{lane}\ \mathrm{addition}/\mathrm{interchange}\ {\mathrm{construction}}^{"}\mathrm{project} i\_ v\mathrm{is}\ \mathrm{chosenfor}\ \mathrm{implementation}\\ {}0& \mathrm{otherwise}\end{array}\right.$

i_e :

a “new section” project

i_v :

a “lane addition / interchange construction” project

B :

the given budget

l_p :

a link in the original network

l_e :

a new link in the network, as a result of implementing a “new section” project

l_v :

a link modified by “lane addition / interchange construction” project

γ _{l_e} :

a binary variable indicating whether there is a flow in the project link l_e

γ _{l_v} :

a binary variable indicating whether there is a flow in the project link l_v

γ_o _{l_v} :

a binary variable indicating whether there is a flow in the original link l_v

${\delta}_{l\_ p, k\_ rs}^{rs}$ :

a binary parameter indicating whether link l_p, connecting origin r and destination s, is also part of route k_rs

${\delta}_{l\_ e, k\_ rs}^{rs}$ :

a binary parameter indicating whether link l_e, connecting origin r and destination s, is also part of route k_rs

${\delta}_{l\_ v, k\_ rs}^{rs}$ :

a binary parameter indicating whether link l_v, connecting origin r and destination s, is also part of route k_rs

N_L _{i_e} :

the number of links comprising the “new section” project i_e

N_L _{i_v} :

the number of links comprising the “lane addition / interchange construction” project i_v

M :

a big integer

f_o _{l_p} :

the flow on the original link l_p

f _{l_e} :

the flow on the project link l_e

f _{l_v} :

the flow on the project link l_v

f_o _{l_v}  :

the flow on the original link l_v

f :

network flow

t_o _{l_p} :

the travel time on the original link l_p

t _{l_e} :

the travel time on project link l_e

t _{l_v} :

travel time on the project link l_v

t_o _{l_v} :

the travel time on the original link l_v

${h}_{k\_ rs}^{rs}$ :

the flow on route k_rs connecting origin node r and destination node s

D :

the set of origin and destination pairs

r , s :

origin and destination nodes (r, s ∈ D)

q _rs :

total demand of origin destination pair rs (r, s ∈ D)

The upper level of the objective function is based on the environmental approximation that is presented in the next sub-section.

The links in the network are classified into three types: links of the type p are links which are included in the original network only, and are not included in any project; links of the type e are new links, included in the “new section” projects; and links of the type v included in the “lane addition / interchange construction” projects, which are used either in their original form, or in their updated form, when the projects are implemented.

The first constraint of the upper problem is the budget constraint (2), which takes into account projects of three types: construction of a new section, lane additions and a construction of a new interchange. The next two constraints (3,4) connect the relevant project links to the respective projects, and ensure that only once all the relevant links are used, the project will be considered implemented.

The lower level represents the solution of the deterministic user equilibrium. The objective function value, H is given in (5), taking into account the different links types. Constraints (6) and (7) ensure flow conservation and non-negative flows on each route, k_rs. Constraints (8–11) indicate the used links in the network. Constraints (11–14) define the flow on each link to be the sum of flows on the relevant link in each path, for all types of links in the network.

3.2 The Proposed Environmental Impact Approximation

Before focusing our attention at solving the DNDP problem, we present the method for evaluating the environmental impact of traffic in the network. This evaluation will be later integrated in the upper level of the DNDP.

The approximation of the environmental impact is inspired by the eco-routing and eco-driving concepts. The eco-routing concept concentrates on locating the routes that minimize emissions and fuel consumption (Minett et al. 2011; Boriboonsomsin et al. 2012). Most of the techniques used for finding those routes make use of emission models (Ahn and Rakha 2008; Boriboonsomsin et al. 2012; Ahn and Rakha 2013), i.e. calculate the emission levels on different links in the networks, and recommend the “most environmental route” based on these estimations. Our proposed approach is also based on the eco-routing concept, but in a different way, utilizing eco-driving principles, as described below.

As mentioned in the literature, eco-driving style concentrates on “smoother” driving, which is mainly characterized by keeping an even driving pace and avoidance of sudden starts, stops and unnecessary accelerations. This means that a more homogeneous driving speed would significantly reduce fuel consumption. Our approach is to seek routes in the network that facilitate the implementation of eco-driving principles, i.e. routes in which the speed variability is minimized. The underlying idea here is that routes with relatively “stable” speed profile will contribute to the decrease in the overall emission level. In order to approximate the stability of speed in the network, we calculate the standard deviation of the speed along the different used routes as follows:

$$ {u}_{k\_ rs}^{rs}=\frac{1}{N_{k\_ rs}^{rs}}\sum_{a\in k\_ rs}{\left({v}_a-{v}_{k\_ rs}^{rs}\right)}^2 $$

(20)

where ${u}_{k\_ rs}^{rs}$ is the standard deviation of speed along the route k_rs connecting origin node r with destination node s; N _{k_rs} is the number of links comprising route k_rs; v _a is the average speed on link a, which is part of route k_rs and ${v}_{k\_ rs}^{rs}$ is the average speed on route k_rs.

An approximation of the overall emission level is then obtained by calculating the standard deviation of the speed along different routes multiplied by the flow on these routes and their length. The summation of these products (the standard deviation of speed, flow and length) for all used routes will yield an overall relative approximation of the environmental impact of a certain network configuration. The presented measure can be stated as follows:

$$ EA=\sum_{rs\in RS}\sum_{k\_ rs\in K\_ RS}\ {w}_{k\_ rs}^{rs}\bullet {u}_{k\_ rs}^{rs}\bullet {l}_{k\_ rs}^{rs} $$

(21)

where EA is the value of the presented environmental approximation, ${w}_{k\_ rs}^{rs}$ is the flow on route k_rs connecting origin node r with destination node s and ${l}_{k\_ rs}^{rs}$ is the length of route k. Solving the user equilibrium using path-based traffic assignment, allows retrieving the used routes and calculating the proposed approximation.

The proposed method is illustrated using a simple network, composed of two correlated routes used by Prashker and Bekhor (1998), as shown in Fig. 1.

Fig. 1

Two correlated routes network. The letters indicate the capacity

In this example there is a single OD pair between nodes 1 and 3 with a demand of 4000 vehicles per hour, where a and b represent the capacity (b > a). The length of each link was assumed to be 10 km, and the free flow travel time of each link is 10 min.

We examine two cases, in both of them the value of b is fixed and set to 2000 vehicles per hour, while a equals 1800 vehicles per hour in the first case and 1300 vehicles per hour in the second one. There are three possible routes between nodes 1 to 3: 1–3 (referred to as route 1), 1–2-3 using the lower link or 1–2-3 using the upper link (referred to as routes 2 and 3 respectively).

The link performance function used to determine the travel time on each link is based on the link performance function used by the Bureau of Public Records (1964):

$$ {t}_a={t_0}_a\bullet \left[1+\alpha \bullet {\left(\frac{v_a}{C_a}\right)}^{\beta}\right] $$

(22)

where, t _a is the travel time on link a, t _0a is the free flow travel time on link a, v _a is the flow on link a, C _a is the practical capacity on link a, and α and β are scale parameters set to 0.15 and 4, respectively. It should be noted that in general, the capacity of the link will change according to the link type. In case the link is part of a new section, it will be assigned a capacity according to the specifications of the project; in case the link is included in a lane addition or interchange construction project, the capacity of the link will increase when compared with its original value; otherwise the capacity will maintain its original value.

For the given simple network, the deterministic user equilibrium solution can be calculated analytically. Note that for this specific network, the equilibrium travel times on the 3 routes will be the same. We obtained the flow and speed of every link in the network, and using these results, we calculate the environmental impact approximation, using (21), as shown in Table 1.

Table 1 Solution of the user equilibrium for two cases

The environmental approximation in this network is determined only by routes 2 and 3, since route 1 includes a single link and therefore the standard deviation of the speed there is 0. Note that the flow on route 2 and route 3 is the same. A comparison between the two cases shown in Table 1 reveals that the negative environmental impact can be significantly reduced if a, representing the capacity is set to 1300 vehicles per hour. This is because the equilibrium solution results in more similar speeds on links 1–2 and 2–3, when compared with the case where a equals 1800.

As mentioned earlier, evaluation of the emissions in the network is usually performed using an emission model. Since both emission models and our proposed environmental approximation are supposed to answer the same need, namely evaluate the environmental impact, it is of interest to examine the above example also using an emission model and compare the results. For this purpose, we use the model presented in Shefer et al. (2015) that is based on Parra et al. (2006), as shown below:

$$ {E}_{i, l}=\sum_{j=1}^n{V}_{j, l}\bullet {L}_l\bullet {F}_{i, j}\left({S}_l\right) $$

(23)

where,

E _i , l :

the hot exhaust emission of pollutant i on link l (g/h)

V _j , l :

the hourly flow on link l, for vehicle category j (veh/hour)

L _l :

the length of link l (km)

F _i , j :

the hot exhaust emission factor for pollutant i and vehicle category j (g/km)

S _l :

the average speed on link l (kph)

n :

the number of vehicle categories

In order to obtain the required hot exhaust emission factors, F _i , j , of the different pollutants, we used the MOVES2014a software of the EPA (EPA 2015). This software allows, among others, the calculation of local emission rates based on varied input data. We calculated the emissions factors for different values of average travel speed. To this end, we used local default data on Essex County in New Jersey (such as meteorology data and average speed distribution data), complemented by default national data (such as the age distribution of vehicles and the fleet distribution). The emission factors were calculated for a typical weekday in July 2016, between 9 and 10 a.m.

In order to obtain the emission factors for different average speed values, we used two different methods. The first method is based on Gardner et al. (2013), and calculates the emission factors based on a regression model. To this end, we developed a regression model using curve fitting in Microsoft Excel, for the emission factor of each examined pollutant based on the average travel speed, as extracted from MOVES. An example of the curve fitting for two of the examined pollutants (HC and CO) is shown in Figs. 2 and 3 along with the emission factor functions and the R square values.

Fig. 2

HC Emission factor

The second method we used was based on linear interpolation. Using both these methods, we were able to calculate the emission factors for each link, based on its speed. Then, using this emission factors, together with the speed and flow of the links, as presented in Table 1, we calculated the emission of different pollutants in the network, based on (23), for the case where a equals 1800 and 1300. The results are shown in Table 2.

Table 2 Calculation of the total emission in the network of different pollutants for two cases and two methods

As can be seen from Table 2, the results obtained by both methods are quite close. When a equals 1300 vehicles per hour, using both methods, all the pollutants get lower values, meaning that the total negative environmental impact of the network can be reduced by setting a to 1300 vehicles per hour. This result is consistent with the results obtained using the proposed environmental approximation, which also indicates that in order to minimize the negative environmental impact in the network, the value of a, representing the capacity, should be equal to 1300 vehicles per hour.

3.3 Integrating the EA in the Upper Level of the DNDP

The evaluation of the upper objective function is based on the approximation presented in (21). When examining different network configurations, we will prefer configurations with low values of this measure. The lower this measure, the more stable the speed along the routes in the network. Consequently, the upper objective function can be formulated as follows:

$$ {Z= EA}_{base}-{EA}_{current} $$

(24)

where, Z is the objective function value to be maximized, EA _base is the environmental approximation when no projects are implemented in the network and EA _current is the environmental approximation of a certain project combination. Note that the objective function is a relative measure used to compare different network configurations. Lower negative environmental impact is expected for the case where a lower measure is obtained. Therefore, Z is determined by the set of selected projects for implementation x, and the flow on the links f.

3.4 Demonstrative Example

To illustrate this measure, we use the simple network of the two correlated routes (Fig. 1), and test 11 different cases, in which the value of b is fixed and set to 2000 vehicles per hour, and the value of a changes between 800 to 1800 vehicles per hour. The length of the links and the demand are the same as presented earlier. For each of the 11 examined cases we calculated the flow on each route, the travel time (which is equal on all routes) and the speed. We also calculated the proposed environmental approximation measure. The flow on the routes and the speed on the different links for each of the 11 examined cases are shown in Figs. 4 and 5. The environmental approximation measure is shown in Fig. 6. In all three figures the presented values depend on the changing value of a - the free flow travel time.

Figure 4 shows that at first, when a increases, the flow on route 1 slightly decreases, and then when a exceeds 1300, an increase of the flow is observed. An opposite trend is observed with respect to the flow of the two other routes. Consequently, the speed on link 1–2 increases and on link 2–3 decreases. The speed on link 1–3, is also affected and tends to increase at first, and to decrease later on when a exceeds 1300. The speed on links 1–2 and 2–3 (on both the upper and the lower link) changes in opposite directions. This fact can be explained by the definition of the network; as the capacity on link 1–2 increases, the speed on the link increases as well. On link 2–3, on the other hand, an increase of a will result in a decrease of the capacity, which will decrease the speed on this link.

As mentioned earlier, the environmental approximation in this network is determined only by routes 2 and 3, since route 1 includes a single link and therefore the standard deviation of the speed there is 0. As can be seen from Fig. 6, this approximation first decreases for increasing values of a and then increases. This is due to the speed differences on links 1–2 and 2–3. At first these differences decrease until a equals 1300, and then they increase. The combination of the speed and the flow on both these links determines the trend of the environmental approximation for different values of a. For relative small values of a, the flow and the speed barely change, and therefore the changes of the environmental approximation are moderate. However, when a is bigger than 1400 vehicles per hour, the flow and the speed change more dramatically, and these changes are also reflected by more substantial changes of the environmental approximation.

From a planning perspective, in order to decrease the negative environmental impact using the above example, it is most beneficial to design the network in which a equals 1300 vehicles per hour. This is because this network will generate the lowest speed variation in all used routes. This is the leading principle of the developed method presented in this model. Using this perspective, we apply the DNDP model for a case study using a larger network.

4 Case Study

4.1 Network and Project Data

The road network used for the case study is the interurban road network of Israel, which was used in previous studies (e.g. Bekhor et al. 2013). This network includes 8334 links and 680 traffic analysis zones.

The demand is based on the rush-hour demand of the year 2013, with 614,565 private-vehicle travels. 50 projects selected from the 2040 transportation master plan (Israel Ministry of Transport and Road Safety 2013) form the initial set of candidate projects, which affect 479 links. The projects are of 2 types: adding lanes to existing roads or interchange construction. The network including the 50 candidate projects is shown in Fig. 7.

The cost of each project is estimated in advance, and the total cost estimation of all projects is 13,014 million Israeli Shekels (IS) (approx. 3253 million US dollars). The budget was set to 3000 million IS.

The features of all selected projects are summarized in Table 3.

Table 3 Summary features of the candidate projects

5 Results

In order to solve the environmentally-oriented DNDP using the presented network, we used the genetic algorithm (GA) (Holland 1975) for solving the upper level optimization problem. We used three different population sizes of 20, 50 and 100, and run the GA 5 times for each population size in MATAB, using an Intel i7 CPU with 8GB RAM.

Each solution vector in the population represents a selected combination of projects. In our case, there are 50 candidate projects. Therefore each solution consists of 50 chromosomes. Each chromosome equals either 1, implying that a project is selected, or 0, implying otherwise. Since the solution vectors are binary, that requires using designated crossover and mutation procedures, to ensure that the offspring are also valid binary solutions. To this end, the implemented GA function in MATLAB uses the MI-LXPM algorithm (Deep et al. 2009), which is developed for solving integer and mixed integer constraint optimization problems.

MI-LXPM employs a crossover technique based on the Laplace crossover (Deep and Thakur 2007a), and a mutation technique based on Power mutation (Deep and Thakur 2007b). The selection method used is based on the tournament selection (Goldberg and Deb 1991). The recommended crossover probability and mutation probability for using these methods is 0.5 and 0.005 respectively (Deep and Thakur 2007a). In order to satisfy the budget constraint, the fitness function includes a penalty term (Deb 2000). The stopping criteria for the algorithm is based on the number of generations, in which a significant change of the objective function was not achieved. The number of generations in this case was set to 50, and the tolerance objective function value was 1e-6.

The GA is likely to generate different results each time due to its stochastic character. Therefore, the 5 repetition runs for each population size were used to check the robustness of the results. The average running times for a single run were 15.19 h, 46.54 h and 107.50 when using the population size of 20, 50 and 100 respectively.

For the lower level optimization problem, focusing on solving the user equilibrium, we coded in MATLAB a deterministic path-based assignment. The path-based assignment is needed to find the flows for each used route, and to calculate the proposed environmental approximation. The paths were generated using the penalty method (De La Barra et al. 1993). For the 44,273 OD pairs in the network a total of 411,818 paths were built, with a maximum of 10 paths per OD pair. The required number of paths per OD pairs was determined in accordance with Bekhor et al. (2008).

We now examine the results obtained from solving the DNDP. We start by examining the upper objective function value obtained in different iteration runs, for each population size, and the budget spent. In Table 4, the average, standard deviation and the coefficient of variation (CV) of the objective function are displayed for each population size.

Table 4 Summarized results of the solution of the DNDP for each population size

As expected, increase of the population size improves the objective function value. This is evident when examining the objective function value for the population size of 100 against the lower population sizes. In addition, as the standard deviation of the objective function reveals, the range of the obtained values using population size of 100 is much smaller, when compared with the other population sizes used. This indicates an increase in the robustness of the results with the increase in population size. This decreased range of values can be further verified when examining the coefficient of variation (CV) of the objective function, for each population size. When the population size is 100, the CV is significantly lower when compared with the population size of 20 and 50. The robustness of the results obtained using population size of 100, as reflected by the CV obviated the need to perform further runs using a larger population size.

With respect to the used budget, it is clear that when using population size of 100 the budget is almost fully spent, whereas for lower population sizes it is not always the case. Note that since adding more projects cannot necessarily guarantee an improvement of the environmental approximation measure, an optimal solution may in some cases be obtained also when the budget is not fully exhausted.

To further examine the robustness of the results, we investigate the consistency of the selected projects. This is performed by counting the number of times a project is selected in the optimal set, out of the 5 runs, for each population size. The percentage of selected projects for the examined population sizes is presented in Fig. 8.

Inspection of Fig. 8 reveals that as the population size increases, so does the robustness of the results. That is to say, either a project is repeatedly selected in most runs or it is not selected at all. Table 5, which shows the number of times a project was selected in different runs, further demonstrates this point.

Table 5 The number times a project was selected in different runs for each population size

When attempting to characterize the type of selected projects, it seems that projects of the type “interchange construction” are much more frequently selected than projects of the type “lane addition”. This is evident when examining Fig. 8. There, projects of the type “interchange construction” are numbered as projects 27–50. When focusing specifically on the population size of 100, this finding becomes even more remarkable, as projects of this type are repeatedly selected. In fact, 10 of the 11 projects that were selected for this population size in all 5 runs are of this type. This pattern repeats itself also when looking at projects which were selected 3 or 4 times out of the 5 runs. The group of projects that were selected 3 or more time out of the 5 runs consists of 17 projects. Out of them, only one project is of the type “lane addition” (the one mentioned earlier), while all the rest are of the type “interchange construction”. The total cost of this group of 17 projects is 3118 million IS, only about 4% above the budget limit.

The preference towards “interchange construction” over “adding lanes” projects may indicate that in this specific network a greater contribution to the generation of smoother speed profiles is possible by constructing interchanges and not by adding lanes. This means that the congestion near intersections is much more significant than the congestion along the sections.

To demonstrate how a construction of an interchange can decrease the environmental approximation, we compare two cases. In the first one, the 17 projects which were repeatedly selected are implemented in the network. This case is referred as the best case. In the second case, no projects are implemented in the network. This case is referred as the base case. The comparison is performed with respect to a certain OD pair. The chosen OD pair is located near an interchange selected for construction in the best case. The speed along the chosen routes for the chosen OD pair is shown in Fig. 9.

The construction of the interchange is indicated as project 34 in Fig. 9. As Fig. 9 shows, implementation of this projects leads to an increase of the speed near the intersection, and contributes to a smoother speed profile between the OD pair A-B, when compared with the base case. Since a single route is used between OD pair A-B, no change in the distribution of flow is expected between the two examined cases. Therefore, the only component that changes when calculating the environmental impact in both cases is the standard deviation of speed on the presented links. Due to the smoother speed profile in the best case, the environmental approximation is lower for the best case.

The reduction in the total environmental approximation is also observed when examining the whole network, and not only a specific OD pair as presented above. For the base case the total environmental approximation is 22.56E + 08, while for the best case it is 22.18E + 08. While this reduction is quite moderate (2%), it should be examined with respect to the percentage of links changed in the best case, out of the whole network. This value is only 0.4%. This shows that the relative impact of the changes made is much greater than their actual “weight” in the network (where weight here refers to the part of network changed relative to the whole network).

Finally we would like to examine whether the best case outperforms the base case also when calculating the total emission level in the network using the emission model presented in (23). For this purpose, we assume that the distribution of vehicles in the links corresponds to the distribution of vehicles in Israel, extracted from the Israel Central Bureau of Statistics (2016), and that the emission factor, F _i , j , for the different vehicle categories corresponds to the values measured by Israel Ministry of Environmental Protection (2011).

Israel Ministry of Environmental Protection provides tables for calculating the emission factors based on the average travel speed and the vehicle type. Here, we preferred using linear interpolation in order to obtain the emission factor values, based on the average speed, instead of using regression. This is mainly because for some pollutants, simple curve fitting can sometimes disregard the trends of the emission factor across different speed values. This phenomenon can be witnessed when examining Fig. 3, representing the emission factor for the CO. There the increase of the emission factor in high speeds is not captured by the fitted curve. That also results in a relatively lower R square value (in this case 0.8504).

Fig. 3

CO Emission factor

Fig. 4

Route flows for different values of a

Fig. 5

The speed on each link for different values of a

Fig. 6

The environmental approximation measure for different values of a

Fig. 7

The examined network and the candidate project set

Fig. 8

Percentage of times a project was selected for each population size

Fig. 9

The speed in route A-B in the base case (on the left) and in the best case (on the right)

When attempting to evaluate the overall emission based on such an emission factor for a large-scale network, as in our case, the accumulated inaccuracy involved might be significant. Therefore, in this case, it was decided to use interpolation instead of regression, for evaluating the emission factor for each link. The calculation of the emission level for both cases is presented in Table 6.

Table 6 Comparison of the total emission level of the base case and the best case

As Table 6 shows, for every examined pollutant the emission level in the best case is lower than the emission level in the base case. This result, which is consistent with the results obtained when calculating the environmental approximation, further demonstrates the ability of the proposed method to identify environmentally-beneficial network configurations.

6 Conclusions and Further Research

In this paper a new method was introduced for approximating the environmental impact of different network configurations. This method is inspired by the eco-routing and eco-driving concepts and is based on evaluating the speed variability on the used routes. The approach of this paper was to formulate an equivalent DNDP, in which the objective was to minimize the negative environmental impact of traffic in the network. The method was applied for a real-size network with a set of 50 candidate projects. To solve the problem, the GA algorithm was applied with three different population sizes.

The results show that an increase in the population size improves the value of the objective function and also contributes to the robustness of the results, with respect to the set of selected projects. For this specific case we attained a CV of 2% for the biggest population size used, which indicates a great similarity between the obtained results of different runs.

In the case study used, it was found that a larger environmental benefit was achieved when a larger share of the budget was spent. Note that this is not necessarily the case for every solution of the environmental-oriented DNDP. That is because the combination that uses the largest share of the budget does not necessarily achieve the largest benefit with respect to the minimization of the environmental impact. There may be other sets of candidate projects, where the minimization of the environmental impact would be achieved using smaller share of the given budget.

It was also found that construction of interchanges in the presented network is more environmentally-beneficial, than adding more lanes. This is probably due to the fact that the given network is more congested near intersections than along the sections. A different network may provide different results in this respect.

It is known fact that the total emission level is affected by many factors including the average driving speed but also changes of speed, and especially accelerations. Emission models implemented on large-scale networks usually do not take this effect into account when calculating the emission level. The presented method, on the other hand, does relate to this fact. That is because it is based on evaluating the variability of speed along the used routes,

In addition, the presented method unlike emission models is not location-specific. As could be seen from the examples shown in this paper, emission models require the use of emission factors, which change according to the examined area. The proposed methods, on the other hand, can be calculated without using any location-specific data, making it very easy to implement on a wide variety of networks.

The presented method should be used as a decision-aiding tool in early planning stages, to gain insights with respect to the environmental impact of different network configurations. When detailed data for the examined area exists, the proposed method can be used as a complementary approach to existing methods, thus gaining a more complete understanding on the environmental aspects concerning the examined area.

One major obstacle common to all used algorithms when solving the environmental-oriented DNDP, is the need to repeatedly solve the traffic assignment problem. This time-consuming task limits the size of the instances used (i.e. a combination of the network size and the number of candidate projects) that can be solved using the existing methods. In this paper, we were able to demonstrate our method using a real-size network with a set of 50 candidate projects. A possible improvement of the proposed method would be to try and reduce the number of times the traffic assignment has to be solved.

Additional possible research direction includes extending the proposed method to allow also the examination of additional types of projects. For example policy measures such as traffic restrictions in city center, or congestion pricing. In this case, the lower level objective function should include elastic demand formulation (e.g. Friesz et al. 2004). A different research direction would be using dynamic traffic assignment instead of the static traffic assignment used in this paper. This will allow for additional analyses to be made, with respect to the variations of the emission level throughout the day.

With respect to the applicability of this model to solve different types of DNDP variations, the proposed model can be further extended to include also additional objectives as time minimization, road safety, equity etc. In addition, simplifying assumptions concerning various features of the problem can be released to allow for sensitivity analysis. For example, examining the problem under changing budget, or introducing uncertainty with respect to the costs of the projects. Another possible research direction includes extending the problem to several time periods, and analyzing the schedule of projects over the planning horizon.