Multiobjective Network Design For Emission and Travel-Time Trade-Off For A Sustainable Large Urban Transportation Network
Multiobjective Network Design For Emission and Travel-Time Trade-Off For A Sustainable Large Urban Transportation Network
Multiobjective Network Design For Emission and Travel-Time Trade-Off For A Sustainable Large Urban Transportation Network
doi:10.1068/b37018
Sushant Sharma
NEXTRANS, Regional University Transportation Center, Purdue University, 3000 Kent Avenue,
West Lafayette, Indiana 47906, USA; e-mail: sharma57@purdue.edu
Tom V Mathew
Indian Institute of Technology Bombay, Mumbai, 400076 India; e-mail: vmtom@iitb.ac.in
Received 23 September 2010; in revised form 12 February 2010
Abstract. Existing optimal road-network capacity-expansion models are based on minimizing travel
time and rarely consider environmental factors such as vehicular emissions. In this study we attempt
to solve such a transportation network design problem when the planner is environment conscious
and thereby tries to minimize health-damage cost due to vehicular emissions along with total system
travel time while performing optimal capacity expansion. This problem can be formulated as a
multiobjective optimization model which minimizes emissions in addition to travel time, and under
budget constraints. A prerequisite for this model is an accurate estimation of vehicle emissions due to
changes in link capacities. Since the current practice of estimation of vehicular emissions by aggregate
emission factors does not account for the improved speeds resulting from capacity improvements,
speed-dependent emission functions for various transport modes and pollutants are used in this study.
These functions help in calculating emission factors for use in the proposed model. The model uses a
nondominated sorting genetic algorithm as the optimization tool to solve the network design problem.
The model is tested on a small hypothetical network and solved for a real large-sized network in India
taking into account three pollutants and five transport modes. The Pareto-optimal solutions generated
can act as trade-offs between total emissions and total system travel time to account for the planner's
desired objectives. Also, reduction in travel time as well as in emissions supports the present model
compared with the single-objective model.
1 Introduction
Transportation-network design has always been considered to be an optimization
problem where the planner tries to arrive at the most favorable policy for the system
considering user behavior. Several variants of the network design problem (NDP) exist,
including optimal capacity expansion, optimization of road tolls, maximization of the
reserve capacity of a network, estimation of a trip matrix, and maximization of
the reliability index. Current practice in transportation-network design is to consider
environmental mitigation objectives only as incidental aspects (or effects) of travel-
related objectives. In other words, the generally accepted hypothesis in designing and
implementing traffic models and traffic-control strategies is that minimizing system
travel time will subsequently result in reducing potentially harmful vehicle emissions
and fuel-consumption rates. However, some recent research findings point to the fact
that travel-time variables are affected differently from air-quality and fuel-consumption
variables, due to various traffic-flow improvement strategies (Noland and Quddus,
2006; Yu, 1997). Further, some studies of induced travel effects have established that
road users' (drivers') behavioral reactions to capacity enhancements will lead to an
increase in total travel (Noland, 2001).
Such lack of efficient methods for minimizing emissions can be attributed to the
traditional perception within the transportation community that the minimization of
travel times will concurrently result in associated reductions in the environmentally
undesirable by-products of vehicular movement. Sustainability is concerned with attain-
ment of goals through a variety of policy instruments, given not only the transportation
Emission and travel-time trade-off for a transportation network 521
network and environmental parameters but also travel behavior (Nagurney, 2000a). The
objective of the transportation NDP is to determine where and how much link improve-
ment is required in the network for the optimal design policy. Traditionally, this
improvement does not contain any environmental objective during the design process.
There is a need to consider environmental objectives and road users' behavior while
planning for link expansion as a measure towards sustainability.
The objective of this study is to investigate the hypothesis that the exclusion of
environmental degradation in the NDP might lead to higher network-wide emissions.
The proposed model, multiobjective network design for emission and travel time
trade-offs (MONDET) accounts for emission reduction and demonstrates that its non-
compliance might lead to higher total emission values in the network. Moreover, the
model accounts not only for emission reduction but is capable of network design
considering users' behavior, constraints of acceptable total emissions (TE), and maxi-
mum budget constraint. The model is principally a multi-objective minimization of total
system travel time (TSTT) and TE. In addition, the proposed model is flexible enough to
account for the planner's desired objectives for TE and travel time. A set of Pareto-
optimal solutions are generated in a single run of the model. In general, Pareto-optimal
solutions are those in which it is impossible to make one objective better off without
necessarily making the other objective(s) worse off. Each solution has different objective
function values as well as network performance measures and link capacity-expansion
values. This is an added advantage over traditional NDP formulation. The primary
contribution of this work is in developing the bilevel multiobjective transportation NDP
by considering emissions for a sustainable solution. In addition, a solution methodology
using a fast and elitist multiobjective nondominated scoring genetic algorithm,
NSGA II, is proposed and is proved to be suitable for solving realistic large city
networks.
2 Related literature
A review of the literature was conducted and is presented in three subsections: the first
includes various studies of single and multiobjective transportation network design
problems (MONDPs); the second describes recent studies on emission factors and
emission models; and the third discusses solution methodologies for NDPs.
2.1 Single-objective NDPs and MONDPs
Since the first discrete and continuous network design formulations were proposed
(Abdulaal and LeBlanc, 1979; LeBlanc, 1975), several variations of the NDP have
been studied and some of them are single objective (Chiou, 2005; Mathew and
Sharma, 2009; Suwansirikul et al, 1987). Many MONDPs were also concurrently formu-
lated and studied. These problems have been thoroughly reviewed by Current and
Min (1986) and Current and Marsh (1993). The former study gave a proper taxonomy
and annotation for multiobjective transportation-network design by reviewing the
literature.
More recent work includes the multicriteria technique where network layout and
link capacity (including traffic lights and link layout) are optimized (Cantarella
and Vitetta, 2006). Another such study by Santos et al (2009) uses the multiobjective
approach for multilevel road-network planning while taking into account robust-
ness and equity objectives. A MONDP study by Sumalee et al (2009) designed an
optimal road-user-charging scheme to meet multiple policy objectives. The reader is
advised to refer to Sharma et al (2010) for more recent studies on multiobjective
transportation-network design along with their objectives.
522 S Sharma, T V Mathew
In the past, there has been hardly any study that has considered minimizing
emission as one of the objectives in network design. However, some studies have
attempted to minimize emission or evaluate emission pricing at the traffic-assignment
stage. Teng and Tzeng (1996) investigated traffic assignment as a multiobjective decision
model with system optimum conditions to consider the environmental parameters.
Bendek and Rilett (1998) formulated a system equitable traffic assignment which uses
generalized environmental cost as the objective function. A multiple-user class-equilibrium
assignment algorithm was formulated by Venigalla et al (1999) to determine vehicle trips
and vehicle miles of travel in various operating modes on highway links. A specialized
equilibrium assignment algorithm was used for finding emissions. Nagurney (2000a),
with the help of three distinct paradoxical phenomena tested on a hypothetical small
road network, proved that the so-called improvements to a transportation network may
result in increased emissions. Further, Nagurney (2000b) considered a multicriteria
traffic-network model with emissions as the objective function. Sugawara and Niemeier
(2003) explored a theoretical emissions-optimized trip-assignment model to estimate
maximum carbon monoxide (CO) reduction under varying congestion levels on a
hypothetical network. The experimental results indicated moderate reductions in sys-
tem-level vehicle emissions under emissions-optimized trip assignment as compared
with the conventional user-equilibrium (UE) and system-optimum models. The solu-
tions were also compared with the work of Bendek and Rilett (1998) and Venigalla et al
(1999). Recent research related to emission minimizing in networks includes imposing
emission pricing as one of the solutions. Yin and Lu (1999) studied the traffic equilib-
rium problems with environmental concerns, and proposed minimal traffic emission
(MTE) model and another bilevel MTE model for an electronic road-pricing system.
In their study the road-toll pattern was determined to minimize traffic emissions when
users make their route choices in a UE manner. Later, Yin and Lawphongpanich (2006)
studied congestion and emission pricing such that it allows decisionmakers to trade-off
between two conflicting objectives, alleviating congestion vesus reducing traffic emis-
sions. Nagurney et al (2007) studied environmental emissions as sustainable supply
chains that can be transformed into transportation networks. Sharma and Mathew
(2007) studied transportation network design in a bilevel problem when the user is
conscious about emissions in terms of emission cost. This was modeled in the traffic-
assignment stage by a generalized cost function; a convex combination of the travel-time
function and emission function. However, emissions pricing is not a readily acceptable
phenomenon among policymakers and road users in developing countries, where
road-network expansion is at its peak. Recently, Nagurney et al (2010) proposed
environmental impact-assessment indices and link-importance indicators to evaluate
the environmental effects of link-capacity degradation in transportation networks
and to decide if links needs to be destroyed.
2.2 Emission models
An accurate estimation of vehicular emissions is crucial for the development of
a transport-network design considering emissions (Sharma and Mathew, 2007).
Several studies have been conducted to develop the emissions factor depending on
speed and other traffic-related factors. Ahn et al (2002) studies fuel consumption
and emission factors based on the speed and acceleration of vehicles. Andre and
Hammarstrom (2000) studied variation in the emission factors according to driving
speed. Chan et al (2004), Lei (1998), and Younglove et al (2005) carried out experi-
ments using remote sensing of vehicle exhaust and developed emission factors as
functions of traffic characteristics. El-Shawarby et al (2005) compared the impact
of cruise speed and acceleration with emissions generated. Sbyati et al (2002) studied
Emission and travel-time trade-off for a transportation network 523
traffic-induced emissions. Ding and Rakha (2002) developed trip-based factors for fuel
consumption and emission factors. Tong et al (2000) investigated on-road motor-
vehicle emissions and fuel consumptions. Beydoun and Guldmann (2006) extended
earlier studies on the interactions between vehicular emissions and characteristics,
such as the effects of fuel economy, vehicle model and maintenance, and seasonal
factors on emissions of CO, HC (hydrocarbons), and NOx (nitrous oxides). Large num-
bers of data records were derived from the 2001 inspection and maintenance programs
(http://www.nap.edu/openbook.php?record_id=10133&page=R1) in Illinois, Maryland, and
Massachusetts, and used to estimate logit models.
Although emissions models and emission factors are well developed, their status in
many developing countries, including India, is primitive for heterogeneous traffic.
Emission factors for Indian vehicles can be found in reports by various agencies such
as the Central Pollution Control Board of India (CPCB, 2005), the Indian Institute of
Petroleum (Pundir and Das, 1985; Pundir et al, 1994), and the Automotive Research
Association of India (AFP, 2003). Emission factors for Indian vehicles have also been
reported in various studies (Bose, 1998; Gurjar et al, 2004; Luhar and Patil, 1986;
Mehta et al, 2006; Mittal and Sharma, 2003; Sharma et al, 2002). The emission factors
recommended in India by various emission studies are constant values and are mostly
independent of the speed of the vehicles. These values were developed from various
experiments conducted on a chassis dynamometer using Indian driving cycles. Mean-
while, Datta et al (2009) estimated a large future growth in the number of personal
vehicles and a subsequent increase in petrol demand and CO emission in the Indian
city of Delhi. By 2020 ^ 21, the projected growth in the number of personal vehicles
will require nearly double the quantity of petrol compared with the 2005 ^ 06 level.
Similarly, CO emission will increase to 2.5 times the 2005 level. Similar growth can be
expected in most Indian cities, and we need accurate emission factors so that suitable
policy measures can be take. Although several vehicular emission factors for Indian
vehicles have been reported in the literature, they cannot be used in studies that involve
link speeds as these factors are insensitive to changes in the link travel time. Some of the
values suggested are constants for all speeds thereby making them unsuitable for real-
world emission calculations. For example, in NDPs link-capacity expansion will cause
changes in the average speed of traffic flow on these links, and this will obviously change
the emissions from various modes of transport. In such a situation, a speed-dependent
emission factor will be very useful.
Sharma (2009) developed speed-dependent emission functions for car, sports utility
vehicle (SUV), and truck or bus modes of transportation using on-board emission-
measuring instruments. Speed-dependent emission functions for pollutants such as
HC, NOx CO, and CO2 (carbon dioxide) were derived. Anusha (2007) also derived
speed-dependent emission functions for various modes of transport to capture better
emission measurements. Although these functions were developed from limited data,
in the absence of other intensive studies, these are the best speed-dependent emission
functions currently available for Indian vehicles that can be used for NDPs. Quantify-
ing emissions as a function of acceleration, deceleration, and idling of vehicles is
equally important but this is used in operational models rather than planning models,
which are macroscopic in nature.
2.3 Solution approach for NDPs
In general, an NDP can be formulated as a bilevel problem which has an upper level
representing a system optimal design and a lower level representing travelers' route-
choice behavior. In the literature many transportation problems have been dealt with
successfully as bilevel formulations, such as the optimization of road tolls (Yang and
524 S Sharma, T V Mathew
Lam, 1996; Yin, 2000), maximization of the reserve capacity of a network (Wong
and Yang, 1997), estimation of a trip matrix (Maher et al, 2001), and maximization
of the reliability index (Current and Min, 1986). Bilevel formulations of the NDP are
nonconvex and nondifferentiable and therefore obtaining a global optimum solution is
not easy (Yin, 2000). These problems are difficult to solve and designing efficient
algorithms is still considered to be one of the most challenging tasks in transportation.
Therefore, designing an efficient solution algorithm for a bilevel large-scale continuous
NDP remains a challenging task (Meng et al, 2001). Recently, Mathew and Sharma
(2009) successfully used a genetic algorithm (GA) for large transportation-network
design. Their study was based on a single objective and the GA used was not specif-
ically for handling multiobjective problems. Over the past decade, a number of multi-
objective evolutionary algorithms have been suggested. Sine evolutionary algorithms
work with a population of solutions, a simple algorithm can be extended to maintain a
diverse set of solutions. With an emphasis on moving towards the true Pareto-optimal
region, an evolutionary algorithm is used to find multiple Pareto-optimal solutions in a
single simulation run and the recently revised NSGA II has proved to be the best for
solving multiobjective problems. Simulation results of the constrained NSGA-II for a
number of test problems, including a five-objective, seven-constraint nonlinear problem,
were compared with another constrained multiobjective optimizer and much better
performance by NSGA-II was observed (Deb et al, 2002).
From the above review and to the best of our knowledge travel time and emissions
have not been addressed simultaneously in NDPs, especially optimal capacity expan-
sion. Multiobjective optimization models are well studied and can be a good approach
for considering both travel time and emissions without any explicit conversions. Deter-
ministic UE can be used to model road-user behavior towards capacity improvement
at the traffic-assignment stage. A GA is the much preferred optimization tool owing
to its simplicity, scalability, robustness, and flexibility since our final goal is to solve
a realistic large city network. NSGA-II has been found to be a versatile and well-
established solution approach to multiobjective problems. Therefore in the next section
we propose a decision tool for optimal network capacity expansion considering both
environmental and travel characteristics subject to some budget constraint and UE
travel behavior.
of the flow, the emission factor epm (va ) for pollutant p of mode m as a function of the
average speed va on link a and the length of the link la . The upper level formulation is:
minimize Zy , Ey ,
subject to
X
Zy xa ta
xa , ya , (1)
a
XXX
Ey xam epm
va la , (2)
p m a
xam y m xa , (3)
X
ga
ya 4 B , (4)
a
ya 5 0, 8a 2 A . (5)
m
Constraint (3) represents the traffic flow x of each mode m on link a and is computed
a
after postprocessing following every traffic assignment stage. That is, the obtained
flows xa on each link a are converted using the predetermined mode share y m for the
network. The obtained flows xam for each mode m on link a are used to compute
emissions. Although a more accurate way of modeling would be by performing
multiclass UE assignment, to keep the model simplistic we stick to the assignment
postprocessing technique as it is easy to implement and understand. The function
ga ( ya ) represents the investment cost corresponding to improvement ya and B is
the total budget available for capacity-expansion constraint. Equation (4) ensures that
the cost of improvement is within the available budget. Constraint (5) ensures that all
capacity improvements are nonnegative. The emission function epm (va ) typically, has a
polynomial form with average link speed va as the dependent variables and is given
as equation (6). (It should be noted that the emission factor used is expressed as a
quantity per unit length.)
epm
va C1 va2 C2 va C3 , (6)
where C1 , C2 , and C3 are the coefficients to be calibrated from the field data. The
lower level of the bi-level formulation assigns the trip matrix into the network using
the route-choice assumption. A UE assignment based on Wardrop's first principle is
proposedöno user can experience a lower travel time by unilaterally changing routes.
This principle is behaviorally sound, computationally efficient, and possesses a unique
solution (Sheffi, 1985). The formulation for the UE assignment in the form of an
optimization problem is given as:
X
x a
subject to
X rs
fk qrs : k 2 K, r, s 2 q , (8)
8k
XXX
xa da;rsk fkrs : r, s 2 q, a 2 A, k 2 K , (9)
r s k
fkrs 5 0 : r, s 2 q, k 2 K, (10)
xa 5 0 : a 2 A , (11)
526 S Sharma, T V Mathew
where xa is the traffic flow on link a, fkrs is the flow on path k connecting origin ^
destination (OD) pair r ^ s, qrs is the trip rate between origin r and destination s, ta (.)
is the travel-time function for link a, da;rsk is a binary variable with value 1 if a link a is
on path k between OD pair r ^ s, otherwise 0. The travel-time function ta (.) is specific
to a given link a and the most widely used model is the Bureau of Public Roads (BPR)
function given by
b
xa a
Input Start
Network data
Travel-time function
Investment function
Origin ± destination
matrix Upper level
Mode split
Emission function Generate population of capacity-
expansion vector
Randomly initialize the capacity-
expansion vector
y 00
Figure 1. Flowchart representing the solution methodology for MONDET (multiobjective network
design for emission and travel time trade-off) model.
Emission and travel-time trade-off for a transportation network 527
The lower level has been solved by using the traditional Frank Wolfe algorithm; the
details of the algorithm are available in Sheffi (1985).
The algorithm starts with the upper level by reading all the inputs such as network
details, demand matrix, budget, link expansion-cost-functions, travel-time function,
investment function, and emission-cost functions. The investment function is defined
as the product of the capacity-expansion value and cost per unit expansion. A popula-
tion of link capacity-expansion vectors is created and randomly initialized. These trial
link capacity-expansion vectors are then translated into the current network-capacity
vector. The lower level algorithm is then invoked with the current link capacity vector
where the demand matrix is assigned into the network using the formulation given by
equations (7) ^ (11). It is solved using the Frank ^ Wolfe algorithm. The output of the
lower level is the link flow vector which is used to compute link travel time using
the BPR function [equation (12)]. Since the BPR equation is a monotonically increas-
ing convex function and the travel time on link a depends on the flows on that link
alone, the lower level formulation is convex. Therefore, there is a unique global solution
and it can be computed by any efficient convex combination method such as the
Frank ^ Wolfe algorithm. The Frank ^ Wolfe algorithm, used in this study, is extensively
reported in the literature and has been elaborately discussed by Sheffi (1985). The link
flows obtained are converted into different mode link flows by postprocessing after the
traffic-assignment stage. Then TSTT is computed as the sum of the product of the link
travel time and link flows in the network. The travel time is also used to compute the
average speed on each link, which is the length of each link divided by the travel time
on that link. The speed calculated is then used to derive speed-dependent emission
factors for various modes and pollutants based on equation (6). After calculating
speed-dependent emission factors for various modes and pollutants, the total emissions
generated for each pollutant are computed.
The emission of each pollutant is the cumulative sum of the product of the link
lengths, the traffic flow of the particular mode, and the emission factor of a particular
pollutant, and mode. Thus, the TSTT and the TE computed will form the two objective
function values of the current generation. Once the values of both objective functions
are obtained and if the current generation is greater than the prespecified maximum
number of generations, then the algorithm is terminated and the Pareto-optimal sol-
utions are reported in the form of TSTT, emissions for all pollutants, optimal link
capacity-expansion vector, link travel time, and total spending. Otherwise, a new set of
Pareto-optimal solutions is obtained using the NSGA II algorithm. The NSGA II
algorithm supplies a better Pareto-optimal front and this process is repeated until the
number of generations is complete.
4 Case study
To investigate the efficacy of the proposed model and the solution methodology a
study was done on a small network and a large city network. The small network
chosen for the study is hypothetical whereas the large city network is a real one from
the Indian city of Pune.
4.1 Design constants
This study requires various design parameters which are specific to the networks
considered. These parameters are the coefficients of the emission functions for various
pollutants and vehicle modes, and the health-damage cost factor that converts emissions
into monetary terms. They are discussed in detail in the following subsections.
528 S Sharma, T V Mathew
To investigate the solutions of the bilevel NDP with single-objective (TSTT) solved
using conventional GA (CGA), and of the MONDET model solved using NSGA II, a
test network having four nodes and five links and input parameters as in figure 2
Emission and travel-time trade-off for a transportation network 529
Table 2. Health-damage cost coefficients of various pollutants for two Indian cities, Mumbai and
Pune (Sengupta and Mandal, 2005).
CO HC NOx
(Rs/kg) (Rs/kg) (Rs/kg)
b
xa
ta t0 1 aa
ca ya a
d14 5000
c4 1650
l4 5
x1 x4
c1 3200
l1 4
c3 3200
x3
l3 0:5
c2 1650 x5
x2
l2 5
c5 3200
l5 4
is considered. The assumed demand from node 1 to node 4 is 5000 vehicles/hr. The
budget for link expansion is assumed to be 10 million Indian Rupees (INR) ( 0.15
million or US$0.2 million). The unit expansion cost of the link is assumed, based on the
prevailing construction-cost rates. The speed-dependent emission factors are calculated
using coefficients in table 1 and substituting them into equation (6). The values of
health-damage cost fp are from table 2 for Mumbai. The modal split for the test
network is assumed to be car 15%, two wheeler 70%, three wheeler 5%, SUV 5%,
and bus and truck combined 5%. The parameters used for the CGA to solve the
single-objective problem were population size 10, number of generations 100, crossover
probability 0.4, and mutation probability 0.05. For the multiobjective NSGA II the
parameters were population 200, generations 100, crossover probability 0.9, and muta-
tion probability 0.5. These parameters were chosen after sensitivity analysis for the
best-solution values.
The comparison of results obtained from the single-objective formulation solved by
CGA, and the MONDET model, solved by NSGA II, are reported in tables 3 and 4.
The reported solutions are final converged values after a large number of iterations for
each algorithm. The reported result of the MONDET model is the minimum value
solution for the total emissions from all Pareto-optimal solutions. Table 3 shows the
optimal link expansion values ( ya ) determined by the algorithms. It can be observed
530 S Sharma, T V Mathew
y1 0.433 0.592
y2 0.150 0
y3 0.024 0.033
y4 0.157 0
y5 0.559 0.594
a Single objective of minimizing total system travel time solved using canonical genetic algorithm
(CGA).
b Multiobjective total system travel time and total emission (MONDET) solved using NSGA II.
Table 4. Results for the single-objective CGA (conventional genetic algorithm) and the multi-
objective NSGA II using different objectives for the small test network.
that the values from the single-objective model are different from the ones obtained
from the MONDET model. The expansion value can be interpreted as the optimal
percentage of the expansion determined for each link by the given method. For
example, an expansion value of 0.5 signifies the link needs an improvement to 1.5 times
(or by 50%) its present width. It can be seen that the optimum solution by the single-
objective CGA allows all the links to expand based on the congestion to minimize the
TSTT whereas the MONDET model allows expansion of only those links which have
minimum vehicle-miles traveled to an extent that eases congestion without major
increases in the emissions. This is intuitive as the route 1 ^ 2 ^ 3 ^ 4 is shorter (8.5 units)
than 1 ^ 2 ^ 4 and 1 ^ 3 ^ 4 (both 9 units) [see figure (2)]. The MONDET model picks up
links on path 1 ^ 2 ^ 3 ^ 4, that is, links 1, 3, and 5, and expands them optimally [see y1 ,
y3 , and y5 in table (3)] causing less vehicle-miles travelled per unit whereas it ignores
other links, unlike the single-objective model. It also considers the user while choosing
the expansion value such that link expansion values (that cause reductions in link travel
time) are adequate in a way that does not cause a significant shift of traffic flow from
other links to expanded links, hence keeping the congestion in check.
Emission and travel-time trade-off for a transportation network 531
Also, table 4 shows that the average travel time of the MONDET model, compared
with the single-objective CGA solution, does not show an appreciable change, but total
emission cost has improved comparatively. The TEC, which is in monetary terms,
shows a reduction of 2.5% for the MONDET model compared with the single-objective
CGA solution. Also the emission of pollutants NOx, CO, and HC show a moderate
reduction compared with the single-objective CGA solution. It may be noticed that
the results still seem to state that the minimum value of the TSTT may result in the
minimum TE and this may be due to better convergence of the MONDET model
compared with the single-objective CGA. However, this case study was performed
to show the working of the models and demonstrate the meaning of optimal link-
expansion values. The discussion in the next case study, on a large, realistic network,
will clarify these doubts.
4.2 Pune City network
The network of Pune City in Maharastra State, India, is considered for the case study
(figure 3). The objective of solving a large city network is to demonstrate the efficacy of
the MONDET model and the performance of NSGA-II for capacity-expansion prob-
lems for large networks. This city has an area of 138 km2 and is divided into 97 traffic-
analysis zones, of which 85 are internal zones and 12 external zones. There are 273 road
nodes and 97 zone centroids with 1131 road links. The demand data include 4083
nonzero OD pairs. Various traffic-flow parameters like aa and ba (free-flow speed
and running speed) for all links were found from surveys. The peak-hour trips within
the network were 118 428 vehicles. The parameters for the link travel-time functions
were developed for various classes of roads using extensive field data. Link charac-
teristics were collected and a trip table was generated for the whole network after
validating the OD counts (Mathew and Sharma, 2009). The transport mode share in
the city, calculated from a CES (2004) study, is 13% cars, 74% two wheelers, 7% three
wheelers, 4% SUVs, and 2% buses. The health damage cost fp for Pune City from
different pollutants is taken from table 2. In order to study the performance of optimal
link expansion of the model on the network, a governmental budget constraint of
100 crores IR ( 15 million or US $22 million) was assumed. The investment cost
function ga ( ya ) corresponding to improvement ya is calculated as the product of the
unit cost of the link improvement and capacity improvement. The maximum capacity
expansion of each link is assumed to be 100%. In order to fix the number of
generations required for solving the large network and to check the ability of the
proposed solution algorithm to converge, a test run was made with 2000 generations
and a population size of 200. The results are shown in figure 4. It was observed that
the average TTST shows a drastic reduction in the first 250 generations and then the
objective function value becomes more or less constant showing a converged solu-
tion. Similarly, the average TE showed a fast convergence towards solution in the
initial 200 generations. As a whole, the convergence for the larger network of Pune
City appears to be quite satisfactory in the first 500 generations. Therefore, a pop-
ulation size of 200 and a maximum of 500 generations was adopted for the rest of the
analysis.
A comparison of the model was made with the base case and single-objective
(minimizing TSTT) CAG solution reported in Mathew and Sharma (2009). The most
optimal single objective run was for a population size of 100 and 10 000 generations
using CAG. Comparison of the results from the models is reported in table 5. All the
Pareto-optimal solutions and the network performance for each solution cannot be
shown in this paper. However, two extreme solutions are given in table 5; solutions
corresponding to least TE (MONDET 3 ) and least TSTT (MONDET 4 ). From the
results, it can be inferred that the values of TSTT and TE show a respectable improve-
ment by applying the MONDET model compared with minimizing TSTT alone (ie,
single-objective). The TSTT value of the MONDET model improves by 2.6% compared
with the single-objective CGA solution and 38% compared with the base case solution
(ie, no capacity improvement). This shows better model performance compared with the
CGA model reported earlier by Mathew and Sharma (2009). Similarly, the reduction in
TE is 3.3% with respect to the single-objective CGA. Although this improvement is
very small, its impact over the entire life of the network will be substantial (note that
this is only peak-hour improvement). In addition, the reduction in the emission of all
the pollutants shows the ability of the model to reduce overall pollution. It may be
noted from table 5, that network performance reported in the MONDET 3 column is
the solution for the least TE and in the MONDET 4 column it is for the TSTT value
from all the generated Pareto-optimal solutions. However, the reduction in emission
is not due to the minimization of TSTT since if that was the case then the TE value
by MONDET 4 would have been lower than the value at MONDET 3. This illustrates
that minimizing the TSTT does not necessarily minimize emissions in a transportation
network and hence shows the need for minimizing the emissions as an objective
separate from the TSTT.
Computation of the MONDET model for a large network was carried out using an
Intel Xeon processor with 4 clusters, 3.2 GHz, 1 GB RAM, and LINUX Fedora Core 4
operating system. The computation time taken for finding the optimal capacity expan-
sion by single-objective CGA was 72 hours whereas NSGA II took only 15.5 hours for
500 generations. Alternatively, the total number of UE evaluations required for an
optimal solution by CGA is about one million whereas the MONDET model requires
only about one hundred thousand UE evaluations. This reduces the computational
Emission and travel-time trade-off for a transportation network 533
2.5
2.4
Total system travel time (mins 106 )
2.3
2.2
2.1
2.0
1.9
1.8
1.7
(a)
7.0
6.9
6.8
6.7
Total emissions (gms 106 )
6.6
6.5
6.4
6.3
6.2
6.1
6.0
5.9
0 200 400 600 800 1000 1200 1400 1600 1800 2000
Generations
(b)
Figure 4. Convergence plot of each objective function throughout the run of MONDET (multi-
objective transportation-network design for emission and travel time trade-off) model for Pune
City. (a) Total system travel time; (b) total emissions.
534 S Sharma, T V Mathew
2009).
b Single objective of minimizing total system travel time solved using CGA.
c Pareto-optimal solutions for minimum total emission by MONDET (multiobjective transpor-
time by 78% when solving NDP by the MONDET model compared with using CGA.
In other words, MONDET requires only one tenth of UE evaluations compared with
CGA, and is able to obtain a better solution. Thus, the computation time for solving
NDP is significantly reduced. The Pareto-optimal solutions obtained as a result of the
MONDET model after 500 and 2000 generations for the Pune City network are shown
in figure 5(a) and 5(b). The figures show a distribution and fairly good convergence of
solutions. Each solution point contains different objective function values as well as
optimal link capacity-expansion values. As an academic exercise we have shown the
large population of solutions whereas for deployment the planner can reduce the solu-
tion points by choosing a lower population of solutions in the model and further by
using the analytical hierarchy process (Saaty, 1980) technique for discriminating
between competing options in the light of a range of preferred objectives (ie, TSTT
and TE) to be met.
5 Conclusion
MONDET is proposed to consider TE and TSTT trade-off for optimal link capacity
expansion of a network under a given budget constraint. The problem is formulated as
a multiobjective optimization problem with TSTT and TE as objectives. The emissions
are measured with the help of speed-dependent emission functions for various modes
and pollutants for Indian conditions. First the working of the proposed model is tested
with the help of a hypothetical network. A comparison between the results of a single-
objective solution (by conventional GA) and multiobjective solution (by MONDET) is
performed. The results show the ability of the proposed model to select only particular
links considering the shift of road users that leads to minimal TE. Next, a large real
network was studied and the model performed consistently with all the network,
showing its robustness and scalability. The reduction in emissions endorses the proposed
MONDET model compared with the single-objective model that minimized only TSTT.
Emission and travel-time trade-off for a transportation network 535
5.980
Pareto-optimal solutions
5.978
Total emissions (gm 106 )
5.976
5.974
5.972
5.970
1.784
1.786
1.788
1.790
1.792
1.794
1.796
1.798
1.800
1.802
1.804
(a)
6.000
Pareto-optimal solutions
5.998
Total emissions (gm 106 )
5.996
5.994
5.992
5.990
5.988
1.788
1.790
1.792
1.794
1.796
1.798
1.800
1.802
1.804
1.806
1.808
The results from the large network show that the NSGA II algorithm is not only
computationally superior, but also gives a better quality of solution. Further, the model
is able to give a Pareto-optimal solution that enables the planner to have more choice
in his or her decision making.
536 S Sharma, T V Mathew
Thus, the proposed model analysis will be a very useful tool for planners seeking to
find a suitable solution between emissions and travel time while performing capacity
expansion of a large city network. The present study has not used the feature available
for using maximum acceptable emission as a constraint; this can be put into use for
various pollutants as a part of future extension of the model. The NDP can be further
sophisticated by including multiclass or dynamic traffic assignment in the lower level.
References
Abdulaal M, LeBlanc L J, 1979, ``Continuous equilibrium network design problem'' Transportation
Research Part B 13 19 ^ 32
AFP, 2003 Auto Fuel Policy Ministry of Natural Gas and Petroleum, Government of India,
New Delhi
Ahn K, Rakha H, Trani A, Aerde M V, 2002, ``Estimating vehicle fuel consumptions and emissions
based on instantaneous speed and acceleration levels'' Journal of Transportation Engineering,
ASCE 128 182 ^ 190
Andre M, Hammarstrom U, 2000, ``Driving speeds in Europe for pollutant emissions estimation''
Transportation Research Record 5 321 ^ 335
Anusha S P, 2007,``Study of influence of lane restrictions on vehicular emissions under heterogenous
traffic flow'' MS thesis, Department of Civil Engineering, Indian Institute of Technology, Madras
Bendek C M, Rilett L R, 1998, ``Equitable traffic assignment with environmental cost functions''
Journal of Transportation Engineering ASCE 124 16 ^ 24
Beydoun M, Guldmann J-M, 2006, ``Vehicle characteristics and emissions: logit and regression
analyses of I/M data from Massachusets, Maryland, and Illinois'' Transportation Research
Part D 11 59 ^ 76
Bose R K, 1998, ``Automotive energy use and emissions control: a simulation model to analyse
transport strategies for Indian metropolises'' Energy Policy 26 1001 ^ 1016
Cantarella G, Vitetta A, 2006, ``The multi-criteria road network design problem in an urban area''
Transportation 33 567 ^ 588
CES, 2004 Comprehensive Study of Integrated Traffic Dispersal System for Pune City Technical
Report, Consulting Engineer Services, Navi Mumbai, India
Chan T L, Ning Z, Leung C, Hung W, Dong G, 2004, ``On-road remote sensing of petrol vehicle
emissions measured and emission factors estimations in Hong Kong''Atmospheric Environment
38 2055 ^ 2066
Chiou S W, 2005, ``Bilevel programming for continuous network design problem'' Transportation
Research Part B 39 361 ^ 383
CPCB, 2005 Transport Fuel Quality for the Year 2005 Central Pollution Control Board, New Delhi
Current J, Marsh M, 1993, ``Multiobjective transportation network design and routing problems:
taxonomy and annotation'' European Journal of Operational Research 65 4 ^ 19
Current J, Min H, 1986, ``Multi-objective design of transportation networks taxonomy and
annotation'' European Journal of Operational Research 26 187 ^ 201
Datta S, Sharfuddin A, Das D, 2009, ``Personal vehicles in Delhi: petrol demand and carbon
emission'' International Journal of Sustainable Transportation 3 122 ^ 137
Deb K, Pratap A, Agarwal S, Meyarivan T, 2002, ``A fast and elitist multiobjective genetic
algorithm: NSGA-II'' IEEE Transactions on Evolutionary Computation 6 182 ^ 197
Ding Y, Rakha H, 2002, ``Trip-based explanatory variables for estimating vehicle fuel consumption
and emission rates'' Water, Air, and Soil Pollution 2(6) 61 ^ 77
El-Shawarby, Ahn I K, Rakha H, 2005, ``Comparative field evaluation of vehicle cruise speed
and acceleration level impacts on hot stabilized emissions'' Transportation Research Part D
10 13 ^ 30
Gurjar B R, Aardenne J A, Lelieveld J, Mohan M, 2004, ``Emission estimates and trends
(1990 ^ 2000) for megacity Delhi and implications'' Atmospheric Environment 38 5663 ^ 5681
LeBlanc L J, 1975, ``An algorithm for discrete network design problem'' Transportation Science
9 183 ^ 199
Lei Y, 1998, ``Remote vehicle exhaust emission sensing for traffic simulation and optimization
models'' Transportation Research Part D 3 337 ^ 347
Luhar A K, Patil R S, 1986, ``Estimation of emission factors for Indian vehicles'' Indian Journal
of Air Pollution Control 7(4) 155 ^ 160
Emission and travel-time trade-off for a transportation network 537
Maher M J, Zhang X,Vleit D V, 2001, ``A bi-level programming approach for trip matrix estimation
and traffic control problems with stochastic user equilibrium link flows'' Transportation
Research Part B 35 23 ^ 40
Mathew T V, Sharma S, 2009, ``Capacity expansion problem for large urban transportation
networks'' Journal of Transportation Engineering 135 406 ^ 415
Mehta S, Patil R S, Sethi V, 2006, ``An emission model for heterogeneous vehicular fleet in India''
Indian Journal of Air Pollution Control 6(11) 1 ^ 9
Meng Q, Yang H, Bell M G H, 2001, ``An equivalent continuously differentiable model and a
locally convergent algorithm for the continuous network design problem'' Transportation
Research Part B 35 83 ^ 105
Mittal M L, Sharma C, 2003 Anthropogenic Emissions from Energy Activities in India: Generation
and Source Characterization ö Part II: Emissions from Vehicular Transport in India Ohio
Supercomputer Center, Columbus, OH
Nagurney A, 2000a, ``Congested urban transportation networks and emission paradoxes''
Transportation Research Part D 5 145 ^ 151
Nagurney A, 2000b Sustainable Transportation Networks (Edward Elgar, Cheltenham, Glos)
Nagurney A, Liu Z, Woolley T, 2007, ``Sustainable supply chain and transportation networks''
International Journal of Sustainable Transportation 1 29 ^ 51
Nagurney A, Qiang Q, Nagurney L S, 2010, ``Environmental impact assessment of transportation
networks with degradable links in an era of climate change'' International Journal of Sustainable
Transportation 4 154 ^ 171
Noland R B, 2001, ``Relationships between highway capacity and induced vehicle travel''
Transportation Research Part A 35 47 ^ 72
Noland R B, Quddus M A, 2006, ``Flow improvements and vehicle emission: effects of trip
generation and emission control technology'' Transportation Research Part D 11 1 ^ 14
Pundir B P, Das S, 1985 State of the Art Report on Vehicle Emissions Indian Institute of Petroleum,
Dehradun
Pundir B P, Jain A K, Gogoi D K, 1994,Vehicle Emission and Control Prespectives in India: A State
of the Art Report (Indian Institute of Petroleum, Dehradun)
Saaty T L, 1980 The Analytic Hierarchy Process (McGraw-Hill, New York)
Santos B, Antönio A, Miller E, 2009, ``Multiobjective approach to long-term interurban multilevel
road network planning'' Journal of Transportation Engineering 135 640 ^ 649
Sbyati H, Fadel M E, Kaysi I, 2002, ``Effect of roadway network aggregation levels on modeling
traffic-induced emission inventories in Beirut'' Transportation Research Part D 7 163 ^ 173
Sengupta R, Mandal S, 2005 Health Damage Cost of Automotive Air Pollution: Cost Benefit
Analysis of Fuel Quality Upgradation for Indian Cities Technical Report, National Institute of
Public Finance and Policy, New Delhi
Sharma S, 2009 Transportation Network Design Considering Environmental Parameters and Demand
Uncertainty PhD thesis, Indian Institute of Technology, Bombay, India
Sharma S, Mathew T V, 2007, ``Transportation network design considering emissions as bilevel
optimization problem'', in TRB 86th Annual Meeting Compendium of Papers CD-ROM
Transportation Research Board, Washington, DC
Sharma C, Dasgupta A, Mitra A P, 2002, ``Inventory of GHGS and other urban pollutants from
transport sector in Delhi and Calcutta'' Institute for Global Environmental Strategies, Japan,
http://www.enviroscope.iges.or.jp/contents/13/data/PDF/03-2mitra.G.(Transport).pdf
Sharma S, Ukkusuri S, Mathew T V, 2010, ``Pareto optimal multiobjective optimization for the
robust transportation network design problem'' Transportation Research Record number 2090,
95 ^ 104
Sheffi Y, 1985 Urban Transportation Networks: Equilibrium Analysis with Mathematical
Programming Methods (Prentice-Hall, Englewood Cliffs, NJ)
Sugawara S, Niemeier D A, 2003, ``How much can vehicle emissions be reduced?: exploratory
analysis of an upper boundary using an emissions optimized trip assignment'' Transportation
Research Record number 1815, 29 ^ 37
Sumalee A, Shepherd S, May A, 2009, ``Road user charging design: dealing with multi-objectives
and constraints'' Transportation 36 167 ^ 186
Suwansirikul C, Friesz T L, Tobin R L, 1987, ``Equilibrium decomposed optimization: a continuous
network design problem'' Transportation Science 21 254 ^ 263
Teng J Y, Tzeng G H, 1996,``A multiobjective programming approach for selecting non-independent
transportation investment alternatives'' Transportation Research Part B 30 291 ^ 307
538 S Sharma, T V Mathew
Tong H Y, Hung W T, Cheung C S, 2000, ``On-road motor vehicle emissions and fuel consumption
in urban driving conditions'' Journal of Air Waste Management Association 50 543 ^ 554
Venigalla M M, Chatterjee A, Bronzini M S, 1999, ``A specialized equilibrium assignment
algorithm for air quality modeling'' Transportation Research Part D 4 29 ^ 44
Wong S C, Yang H, 1997, ``Reserve capacity of a signal controlled road network'' Transportation
Research Part B 31 397 ^ 402
Yang H, Lam W H K, 1996, ``Optimal road tolls under conditions for queuing and congestion''
Transportation Research Part A 30 319 ^ 332
Yin Y, 2000, ``Genetic algorithms based approach for bi-level programming models'' Journal of
the Transportation Engineering ASCE 126 115 ^ 120
Yin Y, Lawphongpanich S, 2006, ``Internalizing emission externality on road networks''
Transportation Research Part D 11 292 ^ 301
Yin Y, Lu H, 1999, ``Traffic equilibrium problems with environmental concerns'' Journal of the
Eastern Asia Society for Transportation Study 3 195 ^ 206
Younglove T, Score G, Barth M, 2005, ``Remote vehicle exhaust emission sensing for traffic
simulation and optimization models'' Transportation Research Record number 1941, 51 ^ 59
Yu L, 1997, ``Collection and evaluation of modal traffic data for determination of vehicle emission
rates under certain driving conditions'', Technical Report, Centre of Transport Training and
Research, Texas Southern University, Houston, TX