# Macroscopic Fundamental Diagram Based Discrete Transportation Network Design

Authors: Guojing Hu; Weike Lu; Feng Wang; Robert W. Whalin
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

The presence of demand uncertainty brings challenges to network design problems (NDP), because fluctuations in origin-destination (OD) demand have a prominent effect on the corresponding total travel time, which is usually adopted as an index to evaluate the network design problem. Fortunately, the macroscopic fundamental diagram (MFD) has been proved to be a property of the road network itself, independent of the origin-destination demand. Such characteristics of an MFD provide a new theoretical basis to assess the traffic network performance and further appraise the quality of network design strategies. Focusing on improving network capacity under the NDP framework, this paper formulates a bi-level programming model, where at the lower level, flows are assigned to the newly extended network subject to user equilibrium theory, and the upper level determines which links should be added to achieve the maximum network capacity. To solve the proposed model, we design an algorithm framework, where traffic flow distribution of each building strategy is calculated under the dynamic user equilibrium (DUE), and updated through the VISSIM-COM-Python interaction. Then, the output data are obtained to shape MFDs, andk-means clustering algorithm is employed to quantify the MFD-based network capacity. Finally, the methodology is implemented in a test network, and the results show the benefits of using the MFD-based method to solve the network design problem under stochastic OD demands. Specifically, the capacity paradox is also presented in the test results.


---

## Body

## 1. Introduction

With a substantial increase in travel demand and existing limited road space, high priorities of governments, and the general public have been given to the problem of traffic congestion. From the perspective of supply, considerable efforts have been undertaken to mitigate traffic congestion, among which infrastructure construction such as expanding road capacity, or building a new road is a common approach. These efforts could be associated with the transportation Network Design Problem (NDP), which is recognized as a strategical decision-making problem to improve system efficiency. Depending on the continuity of involved decision variables, the NDP can be categorized into (1) the continuous network design problem (CNDP) aiming to optimize road network performance by the expansion of road capacity, (2) the discrete network design problem (DNDP) proposed to optimize road network performance by adding new road sections to an existing network, and (3) the mixed network design problem (MNDP) simultaneously taking CNDP and DNDP into consideration [1]. This research selects DNDP as a topic.Traditionally, most of the DNDPs focus on minimizing the total travel cost within a given budget while being subject to user equilibrium constraints. However, the network travel cost is hyper-sensitive to the input information, small perturbations to the origin-destination (OD) tables, or minor changes to drivers’ route choices can drastically change the traffic congestion indexes such as the total travel time, the number of bottlenecks, delay, density, and other network outputs [2]. That means, although the newly built road can decrease the network travel time most at present, when the OD demand varies in the future, the constructing strategy may not meet the original design expectations anymore, or even result in a higher cost than the original network.With these observations, in this study, we attempted a new approach to the measurement of network-wide performance in light of macroscopic fundamental diagram (MFD) concept. An MFD demonstrates a robust demand-insensitive relationship between network vehicle density and space-mean flow, which can also be expressed as the relationship between vehicle accumulations and network outflow [2]. MFD is an attribute of the network infrastructure and the control strategy implemented. It implies that fluctuations in traffic demand would not change the shape of MFD, but modifying the road infrastructure or signal control can make a difference to an MFD. To circumvent the demand uncertainty problems of a traditional traffic flow model, the MFD-based network characterization method is employed as the performance evaluation index of a road network in this paper.For a DNDP, the paper applies the MFD method to improve network capacity in order to mitigate traffic congestion by optimizing the topology of an urban road network. A bi-level programming model is developed where the upper level goal is to maximize network capacity subject to limited budgets, and the lower level presents a user equilibrium model to reflect traffic state under different road construction plans. The MFD-based DNDP is solved by a simulation-based framework, where after adding each building strategy, the traffic flow of the extended road network is dynamically updated by the Frank–Wolfe algorithm. The simulation data are then fed into MFDs.


## 2. Background

LeBlanc first addressed the DNDP for determining which links should be added to an urban road network to ease traffic congestion [3]. To explicitly describe the network design problem, LeBlanc developed a bi-level programming model, which has an upper level minimizing the total travel time, and a lower level reflecting user equilibrium routes of vehicles for a given road network configuration. Subsequently, extensive research studies have been carried out to deal with the network design problem. However, a vast majority of the earlier studies only concentrated on the objective of minimizing the system travel time to improve the network performance. In later research investigations, the researchers gradually shift their attention to equity, sustainability, consumer surplus, reserve capacity, and accessibility, etc. For example, Behbahania et al. incorporated social equity into transportation network planning for simultaneously minimizing total travel time and achieving social equity objectives [4]. Jiang and Szeto formulated a multiobjective network design model that measures network performance and health condition of residents respectively by maximizing the increase in consumer surplus and the reduction in the health cost. In the health cost function, three sustainability indicators, including traffic emissions, noise, and accidents, were considered [5]. After comparing the objectives of minimizing the total system cost and maximizing the network reserve capacity, Yang and Wang found that the equivalence relation of the two objectives varies by level of congestion. That means, the higher the congestion is, the objective of maximizing the reserve capacity deviates farther from the goal of minimizing the total travel cost. Thus, the authors suggested a combined target by applying different weightings on the two objectives [6]. Recognizing the difference between reserve capacity and system travel time, Miandoabchi et al. proposed a three-objective model that involves one reserve capacity and two new travel-related objective functions [7]. Di et al. combined traffic flow and accessibility to straightforwardly measure whether travellers could reach their destinations [1]. To summarize the above research studies, when considering other aspects like equity, sustainability, consumer surplus, reserve capacity, and/or accessibility, most studies proposed multiobjective models still including travel time as one of the objectives to optimize the network performance. However, travel time as a performance measure is susceptible to network inputs such as travel demand.


### 2.1. Demand Uncertainty

Due to the space-time uncertainty of travellers, OD demand changes over time. Most obviously, both newly constructed roads and ever-increasing population may stimulate future travel demand. In general, changes in OD demand have a great influence on system travel time, and consequently, sway the travel time-based constructing strategy in network design problems. Waller et al. proved that ignoring demand uncertainty tends to overestimate network performance and might engender an erroneous choice of improvements [8]. Patil and Ukkusuri justified that the deterministic demand-based approaches can only yield suboptimal enhancements [9]. Therefore, it would be more realistic to study the DNDP with a varied or stochastic demand.To make the DNDP consistent with reality, a few studies have considered demand uncertainty in transportation network design. Several methods have been proposed to hedge against the demand fluctuation, including the expected value model, chance-constrained model, mean-variance model, and min-max model [10]. To address demand uncertainties along with equity issues, Chen and Yang advanced two different stochastic programming models: a chance-constrained model and an expected-value model. Both of the two models aimed at minimizing the expected value of total travel time. Besides, the chance-constrained model formulated the maximal equity ratio as a chance constraint and ensured that the probability of having the maximal equity ratio less than a given equity ratio is above a predefined confidence level [11]. Ukkusuri et al. adopted the mean-variance model, simultaneously minimizing the expected value and the standard deviation of total system travel time [12]. Lou et al. aimed to minimize the worst-case travel cost under various future demand scenarios, and the model can be regarded as a min-max method [13]. But whatever methods are used to cope with demand uncertainty, NDPs are usually solved by what are deemed to be reasonable assumptions, for example, assuming OD demand as random variables with known probability distributions or under given scenario sets [1, 7, 11–14].However, it is challenging to accurately predict the long-term future demand, especially when we are always in changes and uncertainties with numerous factors affecting the course of the future growth in travel demand. In Goodwin’s report, the real growth in traffic since 1989 differs widely from that forecast by the Department for Transport in England [15]. Clearly, if the estimate of future demand is wrong, then the network design decisions would be primarily affected. Therefore, it would be necessary to develop a robust plan for NDPs with less dependence on a prediction or assumption of future demand.


### 2.2. Macroscopic Fundamental Diagram

In this paper, we adopted an alternative methodological approach that employs MFD to circumvent the demand uncertainty problem of traditional models for evaluating network improvement. Geroliminis and Daganzo first verified the existence of macroscopic fundamental diagram (MFD) linking space-mean flow, density, and speed on a large urban area using the field experiment data of Yokohama [16]. As shown in Figure 1, the shape of an MFD illustrates a unimodal relationship between weighted average flow and density. There is a similar relationship between outflow and accumulation as the ratio of network flow and outflow is constant [16]. Generally, there are three parts in an MFD, representing unsaturated, saturated, and oversaturated traffic states, respectively. In the case of the unsaturated state, network flow increases with the network density. When more and more vehicles come into the network, the network space-mean density keeps growing, and the consequential network flow gradually grows to its capacity, which is known as the saturated state. When more vehicles are added into the road network at the maximum flow, the network flow will start to decrease until a gridlock, also considered as an oversaturated state, occurring if the network density continues increasing.Figure 1
General shape of an MFD.One of the most intriguing observations of Geroliminis and Daganzo showed that MFD is a property of the road network itself and is independent of demand. More specifically, the maximum flow (or outflow) of a road network remains invariant when the demand changes. On the other hand, variations in road spatial distribution can result in different MFDs of the same neighbourhood [16]. Likewise, the space-mean flow is maximum for the same value of critical vehicle density, irrespective of the time-dependent OD tables [17]. These steady and elegant properties of MFDs can be fully utilized to develop a robust network design strategy for meeting stochastic demand in the future.Afterwards, people in different cities have proved the existence of MFD in the urban network by simulations [18], experimental methods [19, 20], and mathematical approaches of variational theory [21, 22]. Nevertheless, experimental methods to estimate MFDs are based on observations of loop detector data or probe vehicle data, both of which are unavailable in an unbuilt road network for DNDPs. The mathematical approach is only limited to homogeneous loadings; otherwise, the obtained MFD may fall far upper to the real MFD. Besides, the mathematical method is restricted to urban corridors, and is difficult in gaining the network MFD [23]. For convenience and feasibility, many applications based on MFD resorted to simulation methods [24–30]. Also, in this research, in order to compare the network improvements after building different new links, we leverage VISSIM software to simulate traffic flow and then gain MFDs.To our knowledge, there is little research undertaken for the network design problem with an application of the MFD measure. To fill the gap, this paper takes network capacity (maximum network flow) in an MFD as the measurement of network performance, and formulates a bi-level model where the upper level determines which new links from the candidates should be built in order to achieve the highest network capacity, while the lower level generates a new user equilibrium every time when the decision variable in the upper-level changes.The rest of this paper is organized as follows. Section3 presents the problem formulation with a bi-level programming model. Then, the Frank-Wolfe and k-means clustering algorithms are utilized to solve the lower and upper models, respectively. In Section 4, the model formulations and algorithms are then applied in a medium-size test network—Sioux Falls network under stochastic demands, the MFD-based methodology is verified suitable for solving network design problems. Finally, some concluding remarks and possible future extensions are presented in Section 5.


## 2.1. Demand Uncertainty

Due to the space-time uncertainty of travellers, OD demand changes over time. Most obviously, both newly constructed roads and ever-increasing population may stimulate future travel demand. In general, changes in OD demand have a great influence on system travel time, and consequently, sway the travel time-based constructing strategy in network design problems. Waller et al. proved that ignoring demand uncertainty tends to overestimate network performance and might engender an erroneous choice of improvements [8]. Patil and Ukkusuri justified that the deterministic demand-based approaches can only yield suboptimal enhancements [9]. Therefore, it would be more realistic to study the DNDP with a varied or stochastic demand.To make the DNDP consistent with reality, a few studies have considered demand uncertainty in transportation network design. Several methods have been proposed to hedge against the demand fluctuation, including the expected value model, chance-constrained model, mean-variance model, and min-max model [10]. To address demand uncertainties along with equity issues, Chen and Yang advanced two different stochastic programming models: a chance-constrained model and an expected-value model. Both of the two models aimed at minimizing the expected value of total travel time. Besides, the chance-constrained model formulated the maximal equity ratio as a chance constraint and ensured that the probability of having the maximal equity ratio less than a given equity ratio is above a predefined confidence level [11]. Ukkusuri et al. adopted the mean-variance model, simultaneously minimizing the expected value and the standard deviation of total system travel time [12]. Lou et al. aimed to minimize the worst-case travel cost under various future demand scenarios, and the model can be regarded as a min-max method [13]. But whatever methods are used to cope with demand uncertainty, NDPs are usually solved by what are deemed to be reasonable assumptions, for example, assuming OD demand as random variables with known probability distributions or under given scenario sets [1, 7, 11–14].However, it is challenging to accurately predict the long-term future demand, especially when we are always in changes and uncertainties with numerous factors affecting the course of the future growth in travel demand. In Goodwin’s report, the real growth in traffic since 1989 differs widely from that forecast by the Department for Transport in England [15]. Clearly, if the estimate of future demand is wrong, then the network design decisions would be primarily affected. Therefore, it would be necessary to develop a robust plan for NDPs with less dependence on a prediction or assumption of future demand.


## 2.2. Macroscopic Fundamental Diagram

In this paper, we adopted an alternative methodological approach that employs MFD to circumvent the demand uncertainty problem of traditional models for evaluating network improvement. Geroliminis and Daganzo first verified the existence of macroscopic fundamental diagram (MFD) linking space-mean flow, density, and speed on a large urban area using the field experiment data of Yokohama [16]. As shown in Figure 1, the shape of an MFD illustrates a unimodal relationship between weighted average flow and density. There is a similar relationship between outflow and accumulation as the ratio of network flow and outflow is constant [16]. Generally, there are three parts in an MFD, representing unsaturated, saturated, and oversaturated traffic states, respectively. In the case of the unsaturated state, network flow increases with the network density. When more and more vehicles come into the network, the network space-mean density keeps growing, and the consequential network flow gradually grows to its capacity, which is known as the saturated state. When more vehicles are added into the road network at the maximum flow, the network flow will start to decrease until a gridlock, also considered as an oversaturated state, occurring if the network density continues increasing.Figure 1
General shape of an MFD.One of the most intriguing observations of Geroliminis and Daganzo showed that MFD is a property of the road network itself and is independent of demand. More specifically, the maximum flow (or outflow) of a road network remains invariant when the demand changes. On the other hand, variations in road spatial distribution can result in different MFDs of the same neighbourhood [16]. Likewise, the space-mean flow is maximum for the same value of critical vehicle density, irrespective of the time-dependent OD tables [17]. These steady and elegant properties of MFDs can be fully utilized to develop a robust network design strategy for meeting stochastic demand in the future.Afterwards, people in different cities have proved the existence of MFD in the urban network by simulations [18], experimental methods [19, 20], and mathematical approaches of variational theory [21, 22]. Nevertheless, experimental methods to estimate MFDs are based on observations of loop detector data or probe vehicle data, both of which are unavailable in an unbuilt road network for DNDPs. The mathematical approach is only limited to homogeneous loadings; otherwise, the obtained MFD may fall far upper to the real MFD. Besides, the mathematical method is restricted to urban corridors, and is difficult in gaining the network MFD [23]. For convenience and feasibility, many applications based on MFD resorted to simulation methods [24–30]. Also, in this research, in order to compare the network improvements after building different new links, we leverage VISSIM software to simulate traffic flow and then gain MFDs.To our knowledge, there is little research undertaken for the network design problem with an application of the MFD measure. To fill the gap, this paper takes network capacity (maximum network flow) in an MFD as the measurement of network performance, and formulates a bi-level model where the upper level determines which new links from the candidates should be built in order to achieve the highest network capacity, while the lower level generates a new user equilibrium every time when the decision variable in the upper-level changes.The rest of this paper is organized as follows. Section3 presents the problem formulation with a bi-level programming model. Then, the Frank-Wolfe and k-means clustering algorithms are utilized to solve the lower and upper models, respectively. In Section 4, the model formulations and algorithms are then applied in a medium-size test network—Sioux Falls network under stochastic demands, the MFD-based methodology is verified suitable for solving network design problems. Finally, some concluding remarks and possible future extensions are presented in Section 5.


## 3. Problem Formulation

We use bi-level programming to describe the underlying process of DNDP, where the transport planner determines the detailed network design strategy at the upper level. Over the newly extended network based on each construction strategy, travellers choose their routes in a user optimal manner at the lower level. The objective of this model is to maximize the network capacity by selecting the optimal network design scheme. The following notations in Table1 are used in the model formulation.Table 1
Notations and definitions in model formulation.
Notation
Detailed definition
A
Set of all links in a new network
A
0
Set of all links in the original road network
A
¯
Set of candidate links to be built
B
The total budget for building new links
C
a
i
The capacity of linka under demand scenario i
D
Set of OD pairs
K
Set of random OD demand scenarios
P
r
s
i
Set of routes between OD pairsrs under demand scenario i
Q
Optimal network capacity
Q
i
Network weighted flow under demand scenarioi
Z
i
Total travel time of equilibrium flow under demand scenarioi
a
Link index
b
a
The construction cost of linka, a∈A¯
f
p
,
i
r
s
Flow on the routep∈Prs between OD pairs rs under traffic demand scenario i
k
Index of a random OD demand scenario
l
a
The length of linka
q
i
r
s
Travel demand between OD pairsrs under demand scenario i
t
a
i
,
f
Free-flow travel time on linka under demand scenario i
t
a
i
x
a
i
Travel time on linka relating to flow xai under demand scenario i
x
a
i
Traffic flow on linka∈A under demand scenario i
y
a
Binary decision variable which equals 1 if and only if linka∈A¯ is to be built, and 0 otherwise
δ
a
,
p
r
s
,
i
A binary variable which equals 1 if the routep between OD pairs rs under traffic demand scenario i passes link a, and 0 otherwise


### 3.1. Upper-Level Network Design

Given an existing road networkA0, if the transportation infrastructure gradually faces difficulty in undertaking the current travel demand, transport planners would like to build one or more new roads from candidates A¯ within a limited budget B to increase traffic supply and alleviate traffic congestion. The set I contains randomly generated traffic demand scenarios, where the generation and attraction of each traffic zone are diversified.To evaluate the effectiveness of each feasible construction strategy for varied traffic demands, MFD-based network capacity is proposed in this model for measuring the network performance. The network capacity is defined as the maximum network flow, which is linearly related to network outflow. Therefore, the network capacity can describe how many vehicles, at most, are able to depart from a network per hour, and the critical density corresponding to the network capacity reflects the optimal load of a road network. By comparing MFDs under different network design schemes, the optimal design strategy is determined as the design leading to the maximum network capacity.(1)Q=maxi∈IQi,s.t.(2)∑a∈A¯baya≤B,∀a∈A¯,(3)A=A0∪aya>0,a∈A¯,(4)Qi=∑a∈Axak·la∑a∈Ala,∀i∈I,(5)ya=0,1,∀a∈A¯.In objective function(1), the optimal network capacity is expressed as the maximum weighted flow in all feasible building plans under varied traffic demand scenarios. Constraint (2) ensures the total cost of building new roads does not overrun the given budget. Constraint (3) is used to calculate the extended network A based on the original network A0 and potential links to build. The MFD concept is reflected in constraint (4), where Qi is achieved by aggregating traffic flows of all the links in a road network under the demand scenario i. Constraint (5) decides whether or not to construct the new road a.


### 3.2. Lower-Level Flow Assignment

(6)
Z
i
=
min ∑a∈A∫0xaitaixaidx,∀i∈I,s.t.(7)∑p∈Prsfp,irs=qirs,∀rs∈D,i∈I,(8)xai=∑rs∈D∑p∈Prsfp,irsδa,prs,i,∀a∈A,i∈I,(9)fp,irs≥0,∀p∈Prs,rs∈D,i∈I.Travelers in the lower level are assumed to follow the user equilibrium (UE) principle whose purpose is to minimize users’ own travel cost described in formula (6). Constraint (7) depicts the OD demand conservation law under each traffic demand scenario, constraint (8) demonstrates the relationship between link flow and route flow under each traffic demand scene, and constraint (9) guarantees the nonnegativity of the route flow. To acquire the link travel time taixai in the objective function (6), the following Bureau of Public Roads (BPR) function is introduced as Equation (10) relating travel time to traffic flow [31].(10)taixai=tai,f·1+0.15xaiCai4.Updating traffic networks, achieving lower-level UE, and producing MFDs are three keys to finding a solution to the proposed model. Usually, network assignment flow can be calculated by solving UE in each feasible network design plan, but vehicle density and vehicle accumulation of each link cannot be acquired. What is more, the realistic traffic network state and influencing factors of MFDs, such as driver behaviours, network load capacity, actual network output, traffic conflict points, traffic composition, and road types, are hard to be reflected by static UE. In view of this, VISSIM is introduced in this paper to simulate equilibrium flow under randomly generated OD demands, and further to update traffic network state and output traffic data for plotting MFDs. In VISSIM, to reduce intricate network drawing work, the original network plus all candidate links are drawn in advance. All of the network information (network input, topology, and link length) can be extracted to an external control platform (Python console in this paper) by the VISSIM COM interface. In the external control platform, network flow assignment can be calculated by the following rule, and then, according to assignment results, route decisions are obtained to set up simulation configuration (Algorithm1).Algorithm 1
Step 0: Initialization:A=A0∪A¯.Draw networkA in VISSIM;Termination condition: all building plans have been enumerated;Get the information of drawn VISSIM network by calling COM interface;Remove all routes of vehicles by calling Remove Vehicle Route Static method;Step 1: Update traffic network and plot MFDs by calling VISSIM COM:While termination condition is false, for each building planP do.For each linka in A¯ do:  //Update traffic network through update travel time.If linka in plan P.ta0=ta0;Else.ta0=∞;End for.For eachi in I do://Input traffic demand.Find all links whose upstream vertexes generate traffic demand, and denote the link set asU;For each linka in U do:Set linka.VehicleInputs = The generated traffic demand in link a′s upstream vertex;End for.//Solve UE model.Solve UE model by Frank–Wolfe Algorithm;Get link equilibrium flowxai;//Reset vehicle routes and simulate traffic assignment state.For each linka in A do:Find linka′s downstream link set H;For each downstream linksda in set H do:Linka.AddVehicleRouteStatic (Destination link = da, Relative flow = xdai∑a∈Hxai);End for.End for.VISSIM. Simulation;Output simulation data;End for.Plot MFD;End whileIn the implementation process, in order to reduce the impact of abnormal data on the model, the highest centroid of clustering results of simulation data in the lower-level UE problem is selected to evaluate the network performance. More specifically, we get data points through weighting the (density, flow) sets from VISSIM output. Given the data points and the number of clusters, thek-means clustering algorithm is used to calculate the centroid of each cluster by taking the mean of all data points assigned to that centroid’s cluster. By comparing the flow values of all the centroids, the largest flow value is defined as the network capacity.


### 3.3. Solution Algorithm

For clarity, we give Figure2 to illustrate the algorithmic framework straightforwardly, notations are listed in Table 2. As shown, at the beginning of the algorithm, feasible solutions are generated by the budget constraint (2) at the upper level. Each feasible solution represents a link group which can be constructed on the original road network. Every time a new link group is added to the original network, we apply the classic Frank-Wolfe algorithm in the newly extended network to solve the flow assignment model in the lower level, and traffic flow on each link is calculated. Consequently, given link flow obtained from the above step, the VISSIM COM in a Python environment is called to determine vehicle routes. Through simulating the extended road network, the traffic flow, and density of each link can be output and used to calculate the weighted flow and density by weighting the link length. With the weighted flow and weighted density at hand, we are able to fit an MFD and extract the maximum weighted flow as the network capacity. To reduce the impact of abnormal data on the result, we use the k-means clustering algorithm to get the network capacity. By comparing with the result in the previous step, a present optimal solution can be determined. If the last link group in the feasible solution set is not reached, a new link group needs to be added to the original network again. The procedure keeps running until the last link group is examined, and then the encountered best solution will be the output.Figure 2
Algorithmic framework for solution strategies.Table 2
Notations and definitions in the solution algorithm.
Notation
Detailed definition
G
The original road network drawn in VISSIM
MFD
0
Fitted MFD for the original networkG
MFD
Y
Fitted MFD forNew_GY
MFD
Y
∗
Global optimal MFD
New
_
G
Y
An extended networkG∪Y by adding new link group Y to the original network
Q
0
The maximum weighted flow ofMFD0
Q
Y
The maximum weighted flow ofMFDY
Q
∗
Global maximum weighted flow
Sim
_
interval
Simulation interval
T
Simulation period
Y
Link group index
Y
∗
Global optimal link group index
t
Time index
Φ
The container of candidate link groups satisfying budget constraints


## 3.1. Upper-Level Network Design

Given an existing road networkA0, if the transportation infrastructure gradually faces difficulty in undertaking the current travel demand, transport planners would like to build one or more new roads from candidates A¯ within a limited budget B to increase traffic supply and alleviate traffic congestion. The set I contains randomly generated traffic demand scenarios, where the generation and attraction of each traffic zone are diversified.To evaluate the effectiveness of each feasible construction strategy for varied traffic demands, MFD-based network capacity is proposed in this model for measuring the network performance. The network capacity is defined as the maximum network flow, which is linearly related to network outflow. Therefore, the network capacity can describe how many vehicles, at most, are able to depart from a network per hour, and the critical density corresponding to the network capacity reflects the optimal load of a road network. By comparing MFDs under different network design schemes, the optimal design strategy is determined as the design leading to the maximum network capacity.(1)Q=maxi∈IQi,s.t.(2)∑a∈A¯baya≤B,∀a∈A¯,(3)A=A0∪aya>0,a∈A¯,(4)Qi=∑a∈Axak·la∑a∈Ala,∀i∈I,(5)ya=0,1,∀a∈A¯.In objective function(1), the optimal network capacity is expressed as the maximum weighted flow in all feasible building plans under varied traffic demand scenarios. Constraint (2) ensures the total cost of building new roads does not overrun the given budget. Constraint (3) is used to calculate the extended network A based on the original network A0 and potential links to build. The MFD concept is reflected in constraint (4), where Qi is achieved by aggregating traffic flows of all the links in a road network under the demand scenario i. Constraint (5) decides whether or not to construct the new road a.


## 3.2. Lower-Level Flow Assignment

(6)
Z
i
=
min ∑a∈A∫0xaitaixaidx,∀i∈I,s.t.(7)∑p∈Prsfp,irs=qirs,∀rs∈D,i∈I,(8)xai=∑rs∈D∑p∈Prsfp,irsδa,prs,i,∀a∈A,i∈I,(9)fp,irs≥0,∀p∈Prs,rs∈D,i∈I.Travelers in the lower level are assumed to follow the user equilibrium (UE) principle whose purpose is to minimize users’ own travel cost described in formula (6). Constraint (7) depicts the OD demand conservation law under each traffic demand scenario, constraint (8) demonstrates the relationship between link flow and route flow under each traffic demand scene, and constraint (9) guarantees the nonnegativity of the route flow. To acquire the link travel time taixai in the objective function (6), the following Bureau of Public Roads (BPR) function is introduced as Equation (10) relating travel time to traffic flow [31].(10)taixai=tai,f·1+0.15xaiCai4.Updating traffic networks, achieving lower-level UE, and producing MFDs are three keys to finding a solution to the proposed model. Usually, network assignment flow can be calculated by solving UE in each feasible network design plan, but vehicle density and vehicle accumulation of each link cannot be acquired. What is more, the realistic traffic network state and influencing factors of MFDs, such as driver behaviours, network load capacity, actual network output, traffic conflict points, traffic composition, and road types, are hard to be reflected by static UE. In view of this, VISSIM is introduced in this paper to simulate equilibrium flow under randomly generated OD demands, and further to update traffic network state and output traffic data for plotting MFDs. In VISSIM, to reduce intricate network drawing work, the original network plus all candidate links are drawn in advance. All of the network information (network input, topology, and link length) can be extracted to an external control platform (Python console in this paper) by the VISSIM COM interface. In the external control platform, network flow assignment can be calculated by the following rule, and then, according to assignment results, route decisions are obtained to set up simulation configuration (Algorithm1).Algorithm 1
Step 0: Initialization:A=A0∪A¯.Draw networkA in VISSIM;Termination condition: all building plans have been enumerated;Get the information of drawn VISSIM network by calling COM interface;Remove all routes of vehicles by calling Remove Vehicle Route Static method;Step 1: Update traffic network and plot MFDs by calling VISSIM COM:While termination condition is false, for each building planP do.For each linka in A¯ do:  //Update traffic network through update travel time.If linka in plan P.ta0=ta0;Else.ta0=∞;End for.For eachi in I do://Input traffic demand.Find all links whose upstream vertexes generate traffic demand, and denote the link set asU;For each linka in U do:Set linka.VehicleInputs = The generated traffic demand in link a′s upstream vertex;End for.//Solve UE model.Solve UE model by Frank–Wolfe Algorithm;Get link equilibrium flowxai;//Reset vehicle routes and simulate traffic assignment state.For each linka in A do:Find linka′s downstream link set H;For each downstream linksda in set H do:Linka.AddVehicleRouteStatic (Destination link = da, Relative flow = xdai∑a∈Hxai);End for.End for.VISSIM. Simulation;Output simulation data;End for.Plot MFD;End whileIn the implementation process, in order to reduce the impact of abnormal data on the model, the highest centroid of clustering results of simulation data in the lower-level UE problem is selected to evaluate the network performance. More specifically, we get data points through weighting the (density, flow) sets from VISSIM output. Given the data points and the number of clusters, thek-means clustering algorithm is used to calculate the centroid of each cluster by taking the mean of all data points assigned to that centroid’s cluster. By comparing the flow values of all the centroids, the largest flow value is defined as the network capacity.


## 3.3. Solution Algorithm

For clarity, we give Figure2 to illustrate the algorithmic framework straightforwardly, notations are listed in Table 2. As shown, at the beginning of the algorithm, feasible solutions are generated by the budget constraint (2) at the upper level. Each feasible solution represents a link group which can be constructed on the original road network. Every time a new link group is added to the original network, we apply the classic Frank-Wolfe algorithm in the newly extended network to solve the flow assignment model in the lower level, and traffic flow on each link is calculated. Consequently, given link flow obtained from the above step, the VISSIM COM in a Python environment is called to determine vehicle routes. Through simulating the extended road network, the traffic flow, and density of each link can be output and used to calculate the weighted flow and density by weighting the link length. With the weighted flow and weighted density at hand, we are able to fit an MFD and extract the maximum weighted flow as the network capacity. To reduce the impact of abnormal data on the result, we use the k-means clustering algorithm to get the network capacity. By comparing with the result in the previous step, a present optimal solution can be determined. If the last link group in the feasible solution set is not reached, a new link group needs to be added to the original network again. The procedure keeps running until the last link group is examined, and then the encountered best solution will be the output.Figure 2
Algorithmic framework for solution strategies.Table 2
Notations and definitions in the solution algorithm.
Notation
Detailed definition
G
The original road network drawn in VISSIM
MFD
0
Fitted MFD for the original networkG
MFD
Y
Fitted MFD forNew_GY
MFD
Y
∗
Global optimal MFD
New
_
G
Y
An extended networkG∪Y by adding new link group Y to the original network
Q
0
The maximum weighted flow ofMFD0
Q
Y
The maximum weighted flow ofMFDY
Q
∗
Global maximum weighted flow
Sim
_
interval
Simulation interval
T
Simulation period
Y
Link group index
Y
∗
Global optimal link group index
t
Time index
Φ
The container of candidate link groups satisfying budget constraints


## 4. Numerical Experiments

To test the proposed methodology, a simulation in VISSIM 10.0 with COM interface connecting to Python 3.6 is implemented in Sioux Falls network [3]. As shown in Figure 3, there are 24 nodes and 76 directed links in the original Sioux Falls network drawn in solid black lines. Each node is both an origin and a destination, so there is a total of 552 OD pairs in this network, and the OD demand is half of that in LeBlanc [3].Figure 3
Sioux Falls test network.Now the government plans to build two-way streets in the Sioux Falls network to improve the network operation. In this case study, there are four pairs of candidate links inA¯, respectively (7–16), (9–11), (11–15), and (13-14) drawn in red dashed lines. Each pair of links contains two links in opposite directions; for example, link pair (7–16) includes one link from node 7 to node 16 and one link from node 16 to node 7. Assuming the construction cost of each pair of links is the same, the capital budget can only afford one pair of links to be built.


### 4.1. MFD Results

In order to get the MFD of Sioux Falls network under demand uncertainty, OD demand is changed randomly every 200 seconds ranging from 0 to double the original input, and the simulation time is totally 40000 seconds (about 11 hours), indicating 200 demand fluctuations in the process of simulation.During a simulation, the traffic flow, density, and speed in each link are collected every second. Through weighting both flow and density with link length every 200 seconds by the following formulas:qw=∑aqala/∑alakw=∑akala/∑ala, the MFD curve is made with the weighted network density as abscissa and the space-mean network flow as the ordinate. In the formulas, qw and kw represent the weighted network flow and weighted network density respectively, la is denoted by length of link a, qa means the flow of link a, and ka stands for the density of link a.In this paper, we mainly concentrate on the saturated state of an MFD to analyze the network capacities of different networks, where thek-means clustering algorithm is used to recognize the maximum network flow. To achieve the optimal number of clusters of the k-means clustering algorithm, the Elbow method, gap statistic method, and Silhouette method are all utilized in the paper. For example, the optimal number of clusters for the MFD of the original Sioux Falls network is determined as 4, as shown in Figure 4.Figure 4
(a) Elbow method; (b) gap statistic method; (c) Silhouette method to achieve the optimal number of clusters.
(a)
(b)
(c)Then, in Figure5, the MFD is divided into four parts by the k-means clustering algorithm, where the centroid (37.63, 1140) of the highest red part implies that the network capacity of the original Sioux Falls network is 1140 veh/h and the corresponding critical density is 37.63 veh/km. This means that the Sioux Falls network functions optimally when the network density is in the neighborhood of 37.63 veh/km. Density above 37.63 veh/km can actually lead to a drop in network flow.Figure 5
K-means clustering result for an MFD of the original Sioux Falls network.A comparative graph is plotted in Figure6, where x-axis and y-axis represent weighted density and weighted flow respectively to determine an MFD, each color stands for an extended Sioux Falls network. The six scenarios are the original Sioux Falls network and extended networks by adding link pair (13-14), adding link pair (7–16), adding link pair (9–11), adding link pair (11–15), and adding all the candidate link pairs (13-14, 7–16, 9–11, 11–15) in the original Sioux Falls network. Therefore, the change of MFDs before and after constructing different link groups in the Sioux Falls network is demonstrated. To obtain the capacity of each extended network, k-means clustering algorithm is implemented to extract the saturated state of each MFD, and the centroid of saturated state shows the network capacity.Figure 6
MFDs of different extended Sioux Falls networks.As shown in Figure7, the highest centroid of each extended network is marked by a black cross with values (critical density, capacity) beyond. It is easy to derive that, under a certain budget, if only one link group is affordable in this case, the addition of link pair (11–15) leads to the maximum performance improvements, in which the network capacity quadruples from 1140 veh/h to 4032 veh/h and the corresponding critical density triples from 37.63 veh/km to 99.52 veh/km. That is to say, after building link pair (11–15), not only is the network outflow increased remarkably, but also the road network is able to accommodate many more vehicles. When the network density reaches about 100 veh/km, the original Sioux Falls network is almost at a standstill, but the extended network containing links (11−15) operates at an incredibly high throughput. In addition, both link pair (9–11) and (7–16) double the network capacity to 2250 veh/h and 2539 veh/h, respectively. However, far from increasing the network flow, the addition of link pair (13-14) reduces the network capacity from 1140 to 1110 veh/h. These results provide an order of priority for the candidate links to be built, which is link group (11–15), (9–11), (7–16), and link pair (13-14) should be avoided.Figure 7
MFDs and capacities of four extended Sioux Falls networks.
(a)
(b)
(c)
(d)


### 4.2. Capacity Paradox

Figure8 depicts the comparison of MFDs between the original Sioux Falls network and the extended network that adds link pair (13-14) to the original Sioux Falls network. To our surprise, the network capacity of the original Sioux Falls network is 1140 veh/h, but when we build new links (13-14) to the Sioux Falls network, the network capacity reduces to 1110 veh/h instead. Moreover, the optimal density decreases as well from 37.63 veh/km to 36.24 veh/km. That means, to maintain a network operating in the maximum flow, after building link pair (13-14), fewer vehicles are allowed to travel in the Sioux Falls network.Figure 8
MFD comparison of two extended networks: (a) original network; (b) adding link pair (13-14).
(a)
(b)The counter-intuitive phenomenon in Figure8 can be explained by the capacity paradox, where the addition of new links to an existing network may worsen the network in terms of reduction in maximum network flow [32]. The capacity paradox is introduced by the Braess paradox [33], in which adding a new link will result in a higher cost in a user optimized network. As highlighted before, travel time is vulnerable to OD demand, and the occurrence of Braess paradox is no exception. For example, a link adding to the existing road network could increase the network performance when the current demand is relatively low. However, if the future demand increases to a sufficient extent, the same new link may, in contrast, result in longer travel time. Therefore, the result of a travel time-based network design problem is not fit for a network with stochastic demand. Conversely, due to the stable property of MFDs, the solution of an MFD-based network design problem is robust and suited for a long-term design. The proposed methodology also has the ability to avoid capacity paradox because the objective of this model is to maximize the network capacity.Moreover, Figure9 shows the MFDs of two extended Sioux Falls networks. The network adding three link pairs achieves a better performance than the network adding four link pairs, especially when traffic is in the congested condition. For the extended network containing link pairs (7–16, 9–11, 11–15, 13-14), it is noteworthy that, once the density approaches about 150 veh/km, no more vehicles are allowed to enter the network. Traffic congestion spreads quickly, both the density and flow would experience a sudden drop, eventually forming a traffic standstill. The phenomenon is called the clockwise hysteresis loop [34]. According to Geroliminis and Sun [35, 36], the hysteresis phenomenon in the network level happens because of different degrees of spatial heterogeneity in vehicle density in the onset and offset of the peak period. However, the hysteresis phenomenon disappears in the Sioux Falls network extended by adding only three link pairs (7–16, 9–11, 11–15). As shown by the green dots in Figure 9, after the weighted density is 150 veh/km, although the network flow gradually decreases, more vehicles are allowed to pour into the network. It is verified again that building more roads is not always better, and the selection of roads to be built needs to be careful.Figure 9
MFD comparison between the extended network adding link pairs (7–16, 9–11,11–15) and extended network adding link pairs (7–16, 9–11, 11–15, 13-14).


### 4.3. Sensitivity to Network Betweenness

Betweenness for each edge is defined as the number of all the shortest paths in a connected graph that pass through the edge. We take the sum of all the betweenness of edges in a network as the network betweenness. As shown in Figure10(a), the network betweenness of the original Sioux Falls network is 1656. When adding links (11–15) to the Sioux Falls network, the network betweenness decreases to 1617, because there are fewer links that serve only as media in the network, and travelers have fewer detours. Thus, the smaller the network betweenness, the more efficient the network may be. By comparing Figures 10(a) and 10(b), we can easily discover that after adding new links, the two indicators, network betweenness and network capacity, have the opposite trends. For example, after adding links (11–15), the network betweenness decreases the most, and the network capacity increases the most. After adding links (13-14), the network betweenness decreases the minimum, and the network capacity increases the minimum. It is an interesting finding that for a network design problem, we may also use the network betweenness to measure the strategies of building new roads. The network betweenness is probably the simplest and fastest way to solve NDPs so far. But compared with the proposed MFD-based methodology, there is a downside of the betweenness-based method for its inability to recognize the capacity paradox.Figure 10
Change of two different indexes with the strategy of choosing new links. (a) network betweenness; (b) network capacity.
(a)
(b)


## 4.1. MFD Results

In order to get the MFD of Sioux Falls network under demand uncertainty, OD demand is changed randomly every 200 seconds ranging from 0 to double the original input, and the simulation time is totally 40000 seconds (about 11 hours), indicating 200 demand fluctuations in the process of simulation.During a simulation, the traffic flow, density, and speed in each link are collected every second. Through weighting both flow and density with link length every 200 seconds by the following formulas:qw=∑aqala/∑alakw=∑akala/∑ala, the MFD curve is made with the weighted network density as abscissa and the space-mean network flow as the ordinate. In the formulas, qw and kw represent the weighted network flow and weighted network density respectively, la is denoted by length of link a, qa means the flow of link a, and ka stands for the density of link a.In this paper, we mainly concentrate on the saturated state of an MFD to analyze the network capacities of different networks, where thek-means clustering algorithm is used to recognize the maximum network flow. To achieve the optimal number of clusters of the k-means clustering algorithm, the Elbow method, gap statistic method, and Silhouette method are all utilized in the paper. For example, the optimal number of clusters for the MFD of the original Sioux Falls network is determined as 4, as shown in Figure 4.Figure 4
(a) Elbow method; (b) gap statistic method; (c) Silhouette method to achieve the optimal number of clusters.
(a)
(b)
(c)Then, in Figure5, the MFD is divided into four parts by the k-means clustering algorithm, where the centroid (37.63, 1140) of the highest red part implies that the network capacity of the original Sioux Falls network is 1140 veh/h and the corresponding critical density is 37.63 veh/km. This means that the Sioux Falls network functions optimally when the network density is in the neighborhood of 37.63 veh/km. Density above 37.63 veh/km can actually lead to a drop in network flow.Figure 5
K-means clustering result for an MFD of the original Sioux Falls network.A comparative graph is plotted in Figure6, where x-axis and y-axis represent weighted density and weighted flow respectively to determine an MFD, each color stands for an extended Sioux Falls network. The six scenarios are the original Sioux Falls network and extended networks by adding link pair (13-14), adding link pair (7–16), adding link pair (9–11), adding link pair (11–15), and adding all the candidate link pairs (13-14, 7–16, 9–11, 11–15) in the original Sioux Falls network. Therefore, the change of MFDs before and after constructing different link groups in the Sioux Falls network is demonstrated. To obtain the capacity of each extended network, k-means clustering algorithm is implemented to extract the saturated state of each MFD, and the centroid of saturated state shows the network capacity.Figure 6
MFDs of different extended Sioux Falls networks.As shown in Figure7, the highest centroid of each extended network is marked by a black cross with values (critical density, capacity) beyond. It is easy to derive that, under a certain budget, if only one link group is affordable in this case, the addition of link pair (11–15) leads to the maximum performance improvements, in which the network capacity quadruples from 1140 veh/h to 4032 veh/h and the corresponding critical density triples from 37.63 veh/km to 99.52 veh/km. That is to say, after building link pair (11–15), not only is the network outflow increased remarkably, but also the road network is able to accommodate many more vehicles. When the network density reaches about 100 veh/km, the original Sioux Falls network is almost at a standstill, but the extended network containing links (11−15) operates at an incredibly high throughput. In addition, both link pair (9–11) and (7–16) double the network capacity to 2250 veh/h and 2539 veh/h, respectively. However, far from increasing the network flow, the addition of link pair (13-14) reduces the network capacity from 1140 to 1110 veh/h. These results provide an order of priority for the candidate links to be built, which is link group (11–15), (9–11), (7–16), and link pair (13-14) should be avoided.Figure 7
MFDs and capacities of four extended Sioux Falls networks.
(a)
(b)
(c)
(d)


## 4.2. Capacity Paradox

Figure8 depicts the comparison of MFDs between the original Sioux Falls network and the extended network that adds link pair (13-14) to the original Sioux Falls network. To our surprise, the network capacity of the original Sioux Falls network is 1140 veh/h, but when we build new links (13-14) to the Sioux Falls network, the network capacity reduces to 1110 veh/h instead. Moreover, the optimal density decreases as well from 37.63 veh/km to 36.24 veh/km. That means, to maintain a network operating in the maximum flow, after building link pair (13-14), fewer vehicles are allowed to travel in the Sioux Falls network.Figure 8
MFD comparison of two extended networks: (a) original network; (b) adding link pair (13-14).
(a)
(b)The counter-intuitive phenomenon in Figure8 can be explained by the capacity paradox, where the addition of new links to an existing network may worsen the network in terms of reduction in maximum network flow [32]. The capacity paradox is introduced by the Braess paradox [33], in which adding a new link will result in a higher cost in a user optimized network. As highlighted before, travel time is vulnerable to OD demand, and the occurrence of Braess paradox is no exception. For example, a link adding to the existing road network could increase the network performance when the current demand is relatively low. However, if the future demand increases to a sufficient extent, the same new link may, in contrast, result in longer travel time. Therefore, the result of a travel time-based network design problem is not fit for a network with stochastic demand. Conversely, due to the stable property of MFDs, the solution of an MFD-based network design problem is robust and suited for a long-term design. The proposed methodology also has the ability to avoid capacity paradox because the objective of this model is to maximize the network capacity.Moreover, Figure9 shows the MFDs of two extended Sioux Falls networks. The network adding three link pairs achieves a better performance than the network adding four link pairs, especially when traffic is in the congested condition. For the extended network containing link pairs (7–16, 9–11, 11–15, 13-14), it is noteworthy that, once the density approaches about 150 veh/km, no more vehicles are allowed to enter the network. Traffic congestion spreads quickly, both the density and flow would experience a sudden drop, eventually forming a traffic standstill. The phenomenon is called the clockwise hysteresis loop [34]. According to Geroliminis and Sun [35, 36], the hysteresis phenomenon in the network level happens because of different degrees of spatial heterogeneity in vehicle density in the onset and offset of the peak period. However, the hysteresis phenomenon disappears in the Sioux Falls network extended by adding only three link pairs (7–16, 9–11, 11–15). As shown by the green dots in Figure 9, after the weighted density is 150 veh/km, although the network flow gradually decreases, more vehicles are allowed to pour into the network. It is verified again that building more roads is not always better, and the selection of roads to be built needs to be careful.Figure 9
MFD comparison between the extended network adding link pairs (7–16, 9–11,11–15) and extended network adding link pairs (7–16, 9–11, 11–15, 13-14).


## 4.3. Sensitivity to Network Betweenness

Betweenness for each edge is defined as the number of all the shortest paths in a connected graph that pass through the edge. We take the sum of all the betweenness of edges in a network as the network betweenness. As shown in Figure10(a), the network betweenness of the original Sioux Falls network is 1656. When adding links (11–15) to the Sioux Falls network, the network betweenness decreases to 1617, because there are fewer links that serve only as media in the network, and travelers have fewer detours. Thus, the smaller the network betweenness, the more efficient the network may be. By comparing Figures 10(a) and 10(b), we can easily discover that after adding new links, the two indicators, network betweenness and network capacity, have the opposite trends. For example, after adding links (11–15), the network betweenness decreases the most, and the network capacity increases the most. After adding links (13-14), the network betweenness decreases the minimum, and the network capacity increases the minimum. It is an interesting finding that for a network design problem, we may also use the network betweenness to measure the strategies of building new roads. The network betweenness is probably the simplest and fastest way to solve NDPs so far. But compared with the proposed MFD-based methodology, there is a downside of the betweenness-based method for its inability to recognize the capacity paradox.Figure 10
Change of two different indexes with the strategy of choosing new links. (a) network betweenness; (b) network capacity.
(a)
(b)


## 5. Conclusions

This paper has outlined a novel approach to the measurement of network performance with respect to the network capacity, and developed a bi-level programming model for the formulation of the DNDP. The following are the main contributions of this paper: (1) Different from the existing traditional models for DNDPs, this model aims to improve the network performance by obtaining the optimal MFD-based network capacity. The proposed method is appropriate for deciding which links should be built when traffic demand is stochastic and difficult to estimate accurately or unpredictable during the planning years. (2) To solve the proposed model, an algorithm based on microsimulation software VISSIM is desgined, and the output MFDs are guaranteed to incorporate complicated driver behaviors and random demand scenarios simultaneously. (3) Results in the case study have shown the effectiveness of the proposed methodology based on MFD in solving DNDPs under stochastic demands. For the test network, the candidate link pair (11–15) is given the highest priority because it improves the network performance most, quadrupling the network capacity. (4) Interestingly, a capacity paradox occurs in the test network, where building a new link reduces the network capacity, and even incurs a hysteresis loop. The proposed approach has the ability to avoid the capacity paradox, because pursing a new network with higher capacity is the objective of this reseach. (5) According to the comparison between network capacity and network betweenness, we also provide a potential to utilize network betweenness to solve DNDPs, but the betweenness index has the inability to recognize the capacity paradox.Despite pronounced predominance, there are still limitations in this study for the inability to address upheaval of demand in a methodologically sound manner, as rapidly changing traffic demands can drastically affect MFD shape [18]. Besides, the scatter of an MFD and its shape can be influenced by the spatial distribution of network density [35]. A large scale heterogeneous network with uneven distribution of congestion may not have a well-defined MFD. Consequently, the network design problem in a large-scale heterogeneous urban network will be a future research direction.



---

*Source: 4951953-2020-01-20.xml*