# Approximating Dynamic Equilibrium Analysis in Multi-Region Network Based on Macroscopic Fundamental Diagram

Authors: Bo Liu; Yanqing Cen; Xianghui Song
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

Modeling and control of road traffic in large-scale urban networks present considerable challenges. The traffic equilibrium phenomena, with the question of route choice behavior in case of heterogeneous urban networks, has not been thoroughly investigated in parsimonious and classical models due to the limitation, like large network size, spatiotemporal propagation of congestion, and the interaction between driver decisions, etc. In this paper, we propose a bi-level approximating dynamic equilibrium model (BLADEM) for the approximating dynamic equilibrium analysis in multi-region network based on macroscopic fundamental diagram (MFD). The proposed model combines the region-based model and the internal-region model. With the information from region MFD, the region-based model is used to implement the time-dependent regional route choice estimation. Traffic equilibrium condition (dynamic user equilibrium, DUE) is considered in an internal-region model with time-aggregated regional OD demand from the region level. Furthermore, the complexity of the proposed model is derived. Then, the comparative analysis of the algorithm complexity between the proposed model and the DUE model is given. The proposed model is evaluated based on the high-resolution vehicle trajectory data (or connected vehicles trajectory data) from the DiDi platform collected in Chengdu, China with more than 3,000,000 GPS points during a typical workday. The evaluation results show that the proposed model can obtain the approximating traffic dynamics compared with the DUE algorithm. Pleasantly, the improved calculation efficiency is between 21% and 42%. The results indicate the promising potential of using the proposed model to analyze approximating dynamic equilibrium in the multi-region heterogeneous network.


---

## Body

## 1. Introduction

Improving mobility and accessibility in large-scale urban networks presents substantial challenges in the development of modeling, estimation, evaluation and control techniques. As the research foundations of estimation and evaluation in the network, traffic assignment is the main factor for traffic managers to estimate the expected state of the network and the development direction of the planning. However, due to some limitations, including large network size, unpredictability of travelers’ behavior, spatiotemporal propagation of congestion, and the interaction between driver decisions and so on [1], the dynamic traffic assignment (DTA) with high complexity is difficult problem. Considering severe model uncertainty, and excessive computational burden associated with detailed link-level modeling and control methods, such the DTA approaches appear to be practically inefficient under congested conditions in large-scale urban networks. As an alternative to these link-level approaches, network-level methods employing aggregated modeling and control approaches using the parameter characteristics of regions and correlation between regions, receive increasing attention as practicable approaches for city-wide traffic control. Therefore, developing an aggregated model for large-scale urban networks is essential for both feasibility and efficiency reasons.Macroscopic fundamental diagram (MFD) has been widely used for aggregate modeling of urban traffic network dynamics to tackle the dimensionality problem of microscopic approaches. The MFD provides a unimodal, low-scatter, and demand-insensitive relationship between network vehicle density and space-mean flow in homogeneous urban areas (with small spatial link density heterogeneity) [2]. Furthermore, based on the emerging high-resolution vehicle trajectory data from the floating cars or CVs (connected vehicles), a range of advanced methods are adopted to measure the real-time MFD information of the network or the region. The MFD as a concept was first proposed in Godfrey (1969) [3] with an optimum accumulation and similar approaches were introduced later by [4–6]. The idea of network-level traffic control with an MFD-based model was originally proposed by Daganzo (2007) [6] for a single region. The work first proposes a steady-state approximation to establish the relation between regional outflow (i.e. trip completion rate) and accumulation. Based on this work, numerous MFD-based modeling and control methods have been developed for multi-region urban networks, like optimal control [7, 8], robust control [9, 10], model predictive control (MPC) [11–15], model-free adaptive control [16, 17], demand management [18].In addition to purely control efforts, using the MFD framework to describe the dynamics of large-scale urban traffic network, has been further excavated. Recent research works have been dedicated to combining the DTA and the MFD framework by incorporating route choices or preferences for networks modeled by multiple MFD regions. Different from the existing vehicle dispatching frameworks, this fusion framework has analytically tractable nature [19] and gives rise to a promising solution to the challenge of spatial dimensionality in the meanwhile. Yildirimoglu and Geroliminis (2014) [20] proposed an aggregated DTA procedure for MFD-based dynamic stochastic user equilibrium (DSUE) conditions at the network level. Then, they developed the procedure with dynamic user equilibrium (DUE) for route choice behaviors [21]. Keyvan Ekbatani et al. (2015) [22] proposed a DTA procedure which was used in the multiple concentric gating traffic control method. To extend the MFD-based perimeter control to heterogeneous regions, Ramezani et al. (2015) [23] proposed a hierarchical (bi-level) perimeter control method. Yildirimoglu et al. (2018) [24] built a two-level route guidance system based on the MPC scheme to minimize the total travel time. These works proposed the region-based model with user equilibrium conditions and achieved a good effect. However, the limitations are obvious because there are no dispatching models within the region. The sub-regions divided by regions are the smallest control objects. As is well-known, although we use MFD to analyze the aggregate dynamics at network level, the detailed description of strategy more likely to be accepted for travelers and managers at link level. Therefore, in this paper, we developed the model of Yildirimoglu et al. (2015) [21] to establish links as the smallest control objects. Moreover, the results of modeling at link level can be approximately equal to that at the sub-region level on a larger scale. Nevertheless, ignoring the probability that the path selection behavior obeys the wardrop principle [25] and other disturbances, the sub-region level model has drawbacks in a simple sub-region (only few links inside).Recently, several researches introduced some points worth paying attention, including modeling the boundary dynamics, the network separability and the DUE application principle. For modeling the boundary dynamics, a mechanism of dynamically rescaling the MFD after excluding the queued vehicle was proposed by Ni and Cassidy (2020) [26]. The mechanism assumes that the region’s capacity to the within-region traffic diminishes in proportion to the import lanes spaces occupied by the queued vehicles. However, this proportion varies with boundary node topology and control mode so that it is difficult to measure in practical. Guo and Ban (2020) [27] assumes that the region is not completely jammed so that the queued vehicles in its buffer zone will not severely affect the overall congestion of the entire region. Obviously, for the congested region, the state of buffer zone can affect the overall congestion of the entire region based on the transmissibility of traffic flow. Not to mention, the buffer zone is inside the region, not really an independent zone. In this paper, we focused directly on link-level within the region so that the dynamics of boundary nodes can be obtained from the dynamics of the links in all directions. For the network separability, Aghamohammadi and Laval (2019) [28] verify that the large-scale network or region can partition into smaller “cells” (sub-regions) and assume that congestion is homogeneously distributed in each cell. We adopt this point in this paper as an assumption to divide the experimental network into four regions (see in Section 3) and the region is further divided into sub-regions (see in Section 4.3). For the DUE application principle, Huang et al. (2020) [29] proposed the DUE model through the differential variational inequality based on the multi-region MFD dynamics with saturated state and inflow constraints. Then, a methodological framework for estimating traffic-dependent distributions of trip lengths was proposed by Batista et al. (2021) [30], which incorporated in the R-DTA proposed by Batista and Leclercq (2019) [31]. However, different from the proposed model in this paper, the DUE models established by these studies are limited to the region level and cannot guarantee DUE conditions within regions.To sum up, this paper provides contributions in DUE conditions on the following directions: (i) developing the approximate traffic equilibrium conditions to be integrated in a large-scale network which is modeled with multiple MFDs for different regions, (ii) collaborating the DUE model between the region and within region based on the consistency of the boundary nodes dynamics, instead of the DUE condition which is limited to the region level. The remainder of the paper is organized as follows; in Section2, we introduce the dynamics of the region-based model and the internal-region model, including the calculation procedure and complexity analysis. In Section 3, the detailed experimental design is given based on the high-resolution vehicle trajectory data from the DiDi platform. Section 4 presents and discusses results of the experimental design with different analysis perspectives. Finally, Section 5 concludes the paper with future work directions.


## 2. Method

In this study, a methodological framework, called bi-level approximating dynamic equilibrium model (BLADEM), that combines region-based model and internal-region model is introduced, which can integrate aggregated route choice into advanced traffic management strategy (e.g., perimeter control) in real time and optimize the network operation performance. The urban network is partitioned inton regions with a low-scatter MFD in each region (that means each region has a homogeneous distribution of congestion). With the travel production (veh.m/s) and region accumulation (veh) from MFD, the region-based model is used to implement the time-dependent regional route choice estimation. Traffic equilibrium condition (dynamic user equilibrium, DUE) is considered in an internal-region model with time-aggregated regional O-D demand from region level. Based on the regional path and network topology within a region, the internal-region traffic dynamics is re-described by one-to-all time-dependent shortest path algorithm depending on DUE. Furthermore, the region accumulation and average trip length are also updated, which will cause a change in the estimated result of regional route choice. Therefore, there is an iterative process until the convergence conditions are reached between the BLADEM model.From the above, the bi-level modeling framework enables to measure and control traffic state at different layers and incorporate heterogeneity effect in the urban network dynamics, see Figure1. Methodology section is structured as follows. The next subsection introduces the aggregated network dynamics with the newly proposed dynamic aggregated region route choice. The following subsection provides a detailed DUE process which expounds internal-region traffic dynamics. The last subsection presents traffic equilibrium analysis flowchart in a bi-level model and methods for updating aggregate route choice parameters during the process.Figure 1
Methodological framework.


### 2.1. Aggregated Route Choice in Region-Based Model

Let us assume that a large-scale networkG=V,E,n is partitioned into n regions with a heterogeneous distribution of congestion, ℝ=R1,R2,…,Rn. In network topology with multi-regions, V and E represent nodes (intersections) and edges (links), respectively. For internal-region, the traffic dynamics is well described by a low-scatter MFD FPrRnNRn,NRn, where PrRnNRnt is defined as the travel production[veh.m/s] at time t corresponding region Rn accumulation NRnt (veh). What is more, according to the characteristics of MFD, the average trip length LRnt is constant if there is no change for the route choice and traffic control scheme. Then, we can get the trip completion rate MRnt=PrRnNRnt/LRnt (veh/s) and the average speed vRnt=PrRnNRnt/LRnt, which have been reported in [7, 8, 11].In an urban networkG=V,E,n, any given traditional OD demand (represented by a sequence of nodes or links) can be transformed into a region path pU,K from region U to the final destination K. As shown in Figure 2, a region trip is denoted as pA,EB&DRA,RB,RD,RE. Accordingly, pA,EB is a path containing the sequence of regions to reach E starting from A and through the region B. Obviously, pA,EB&D is a form of pA,EB. Let QUt (veh/s) denote the total traffic demand generated in the region U at the time t, QU,Kt be the exogenous traffic flow demand generated in the region U with the final destination K. Particularly, QU,Ut is defined as internal traffic flow demand in the region U without going through another region. For U,K∈ℝ, we have QUt=∑K∈ℝQU,Kt.Figure 2
The schematic of a multi-region urban network and a path example.Approximately,NUt [veh] is the total accumulation in the region U at the time t and NU,Kt is the vehicle accumulation from region U to the final destination K. In traffic flow conversion process in n regions, more than one route collaboratively to complete the transfer trips for a given OD pair. Let NU,KRnt denote the outflow from the region U to the final destination K through the region Rn; U,K∈ℝ, NUt=∑Rn∈HU∑K∈ℝNU,KRnt, where HU is set of next regions(directly adjacent regions) for the region U. Let qpU,KRn be the demand of pU,KRn. Consequently, the instantaneous accumulation is computed as follow:(1)NRnt=∑U∈ℝ∑K∈ℝ∑p∈WU,KRnqpU,KRnt,(2)NU,KRnt=QU,Rnt=∑p∈WU,KRnqpU,KRnt,Where WU,KRn is the set of paths which reach K starting from U and through region Rn. The trip completion rate MU,KRnt for the vehicles from region U to the final destination K through the next region Rn∈HU is calculated by the following equation.(3)MU,KRnt=minvUt⋅NU,KRntLU,Rnt,CU,RnNRnt⋅NU,KRnt∑I∈ℝNU,IRnt,Where LU,Rnt [m] is the average trip length and CU,RnNRnt is the boundary capacity corresponding region trips from region U to adjacent region Rn∈HU. (3) indicates that the transfer flow between the consecutive regions is the minimum of two terms: (i) the transfer flow which depends on the traffic dynamics in region U and (ii) the boundary capacity between consecutive regions and the proportion of vehicles from region U to destination K through the region Rn∈HU, among all the vehicles that cross the same boundary, i.e. ∑I∈ℝNU,IRnt. More details about the boundary capacity can be founded in previous publications (e.g., [21, 23]).In an regions MFD system, the traffic flow dynamic equations are listed below.(4)dNUtdt=QUt−∑Rn∈HUMU,RnRnt+∑Rn∈HUMRn,UUt,(5)dNU,Ktdt=QU,Kt−∑Rn∈HUMU,KRnt+∑Rn∈HUMRn,KUt.The traffic flow conservation of region is illuminated in (4), while the transfer flow dynamic is described by (5). It is noteworthy that, the vehicle paths to include more than one getting through the same boundaries is permitted, i.e., a region path pB,BC&DRB,RC,RD,RB. For each region path p, p, ppp, p between origin O and destination D, the travel time TO,Dp is calculated based on total trip length LO,Dp and region average speed vRn. For example, to a region path pA,EB&D (see Figure 2), we have:(6)LA,EpA,EB&Dt=LA,Bt+LB,Dt+LD,Et,(7)TA,EpA,EB&Dt=LA,Bt⋅NA+NBvA⋅NA+vB⋅NB+LB,Dt⋅NB+NDvB⋅NB+vD⋅ND+LD,Et⋅ND+NEvD⋅ND+vE⋅NE.(7) indicates that average trip time is obtained by integrating average trip length and average speed between adjacent regions. Note that, in the region-based model, region path defines the sequence of regions from an origin node to a destination node, not the detailed sequence of links. However, the DUE condition is considered in an internal-region model that represents the connectivity about traffic flow distribution of links. Also, traffic equilibrium is based on the accumulation of the vehicles in the corresponding region. In other words, the accumulation is extracted and updated from DUE in the internal-region model. Finally, the region path re-decision based on the changed average trip length and average speed in the region. The trip length between two adjacent regions, like LA,Bt etc., can be calculated by the (12) (the initial length calculation method) and (14) (the length calculation method during iterative process). The DUE process and the estimation of traffic dynamic parameters LU,Rnt, TO,Dpt and CU,RnNRnt in region level are discussed in the following subsection.


### 2.2. Traffic Dynamics in an Internal-Region Model

Consider time-aggregated regional OD demand whose dynamic variation trend is well described by aggregated route choice in the previous subsection. In other words, the traffic demandQU,Rnt,Rn∈HU in consecutive regions is calculated in real time. Let VU∩Rni denote the node i which belongs to the set of boundary nodes between the region U and adjacent region Rn, VU∩Rn=VU∩Rn1,VU∩Rn2,…,VU∩Rni, like red nodes as shown in Figure 3. At internal-region level, the adjacent region trip pU,Rn is taken into account as two form of sub-trip: (i) origin O or internal node in the region U to boundary node VU∩Rni and (ii) boundary node VU∩Rni to internal node in the region Rn or destination D.Figure 3
The schematic of a multi-region network with internal topology.Consequently, the traffic demandQU,Rnt of the adjacent region trip pU,Rn is conducted by two-time DTA (dynamic traffic assignment) algorithm. Furthermore, a DUE condition which requires minimal and equal travel times on alternative paths at the same time t [6], is considered for the internal-region traffic dynamics. Note that, in the region trip transformation process, there may be more than one path in each form of sub-trip and application of all boundary nodes in consecutive regions is permitted. That is, for each origin node o, we apply one-to-all time-dependent shortest path algorithm [32] depending on DUE to all boundary nodes, corresponding all-to-one time-dependent shortest path algorithm [33] is used to destination node d from all boundary nodes. For example, a region trip pA,DB with origin node 6 to destination node 26 can be transferred as three-stage sub-trip, including origin node 6 to boundary nodes VA∩B=VA∩B9,VA∩B10,VA∩B11; up-boundary nodes VA∩B to down-boundary nodes VB∩D=VB∩D17,VB∩D18,VB∩D19; boundary nodes VB∩D to destination node 26 (see Figure 3).The boundary capacityCU,RnNRnt as mentioned in the previous subsection can be regarded as the integration of the capacity of the boundary nodes on the driving direction of vehicles. In an urban network, boundary node generally represents the signal control intersection and have the different capacity at different directions, where the capacity of the node VU∩Rni at direction com denotes as CcomVU∩Rni.(8)CU,RnNRn=∑VU∩Rni∈VU∩RnCcomVU∩Rni⋅δcom,r,A.Where δcom,r is an indicator function with a value equal to 1 if the direction com is the same as the path r, otherwise zero. Let co,dr represent the experienced travel time of route r from origin node o to destination node d, corresponding q⌢o,dr denotes as the assigned demand of route r from QU,Rn and lr is the experienced trip length of the route r. The travel time of link te is calculated by BPR (Bureau of Public Roads) function, and we have co,dr=∑e∈Eteδer, where δer is an indicator function with a value equal to 1 if the route r passes through the link e, otherwise zero. Time t is omitted from the following equations for the sake of notational simplicity. The traffic flow conservation equation at the boundary of regions is as follow:(9)QU,Rn|Rn∈HU=∑o∈U∑r∑VU∩Rni∈VU∩Rnq⌢o,VU∩Rnir=∑d∈Rn∑r∑VU∩Rni∈VU∩Rnq⌢VU∩Rni,dr.The results taken from DUE are processed through a well-known heuristic solution called a method of successive averages (MSA). It is effective and highly implemented in DTA [34]. In internal-region model, MSA is employed in each iteration to project future traffic information as part of the direction-finding mechanism in searching for a solution. The establishing DUE state can be summarized as follows:Step 0. Initialization.(a)
Set iteration numberλ=1.(b)
Extract the traffic region demandQU,Rntλ at a time tλ from region-based level for ∀U∈ℝ,Rn∈HU.Step 1. Calculating assignment ratios(10)ηo,VU∩Rnitλ=e−co,VU∩Rni∑ie−co,VU∩Rni.(a)
For each origin internal-region nodeo, apply one-to-all time-dependent shortest path algorithm to boundary nodes and reserve the travel time co,VU∩Rnitλ which represents the lowest travel time origin o to boundary node VU∩Rni at a time tλ.(b)
Based on the lowest travel timeco,VU∩Rnitλ, compute the radio of the demand from origin o to boundary node VU∩Rni with the following logit formula:(c)
Calculate the internal-region OD demand:q⌢o,VU∩Rnitλ=ηo,VU∩Rnitλ⋅QU,Rntλ.(d)
For each boundary nodes, which demand is calculated by (10) based on from origin node o, apply all-to-one time-dependent shortest path algorithm to destination node d. Note that, implement a)-c) process in Step 1 for up-boundary nodes to down-boundary nodes. For example, the travel time cVA∩Bi,VB∩Ditλ can be calculated to compute the radio of the demand for ∀i.Step 2. DUE implementation(11)xeλ+1=xeλ+1λyeλ−xeλ.(a)
Based onStep 1, well-informed internal-region OD demand can be calculated, and we have traffic flow xetλ=∑w∑rq⌢wrtλ⋅δer for each internal-region OD pair w∈W⌢, where W⌢ is the set of internal-region OD pairs.(b)
Apply shortest path algorithm for each OD pair and perform an all-or-nothing assignment for the chosen shortest path. Letyeλtλ represents the updated link flow after an all-or-nothing assignment.(c)
Find the iteration-direction based on MSA and timetλ is omitted from the following equation:Step 3. Stopping test(a)
For each (o,d, r) trio, evaluate ε=yeλ−xeλ.(b)
Ifε≥ℑ, where ℑ is a pre-defined threshold, set λ=λ+1 and go to Step 1. Otherwise, finish the procedure and return the updated region accumulation NRntλ.Note that the DUE process in internal-region model includes two main steps; Calculate well-informed internal-region OD demand based on region demand from region-based level and DUE implementation by MSA. The former is key to connecting region-based level and internal-region level. For the logit model, which manages the travelers’ perception of travel time, can be replaced with C-logit or a cross-nested logit model if necessary. On the other hand, because fixed step sizeα=1/λ, traffic assignment by MSA is general for small “toy” networks, corresponding slow convergence problems in large-scale networks. However, in this study, MSA is only used in the internal-region level assignment. Therefore, there are no limitations to use MSA because internal-region level can be regarded as small “toy” networks. Even if a more intricate is an alternative, it is not expected to improve the results and will bring additional time cost.


### 2.3. Traffic Equilibrium Analysis in the Bi-Level Model

Traditional traffic equilibrium analysis is complex and difficult to tackle in a large-scale network with a large number of nodes and links because it is difficult to get full path alternatives and determining the complex effective-path sets is time-consuming. As an alternative, the problem of traffic equilibrium analysis in this study is to provide the region path (met the DUE condition) in the region-based model and establish a DUE state in the internal-region model. Different from traditional traffic equilibrium analysis, this study produces a faster process and considers traffic dynamics in a rolling horizon framework, meaning that the method establishes a DUE state at the internal-region level and optimizes the region path based on updated region accumulations.The region-based model employs time-dependent aggregated parameters to compute region path with demand assignment, i.e.NU,KRnt, MU,KRnt and LU,Rnt. Such a region path represents the behavior of the overall travelers for route choice. Based on the aggregated route choice at the macroscopic level, the DUE state is established at the internal-region level, and actual traffic flow distribution and chosen path are obtained. In this way, the results of the traffic equilibrium analysis are approximate to traditional models, and the corresponding numerical test is provided in section 4.For an initialized urban network (traffic flow has been loaded), based on traffic information database of ITS (intelligent transportation system), accumulation of region and distribution of traffic flow are well known before the network optimization based on detector data, i.e. the vehicle trajectory data from equipped GPS (Global Position System) on vehicle and fixed loop detector or camera at the intersection. Therefore, the computing region path is not a complicated project. What is more, compared with the traditional model, reducing the application scope DUE to internal-region level makes the calculation time greatly reduced.LetNU,Kt=NU,Kt0 and MU,KRnt=MU,KRnt0 for U,K∈ℝ,Rn∈HU at the initial time t0. Consequently, we can get the initialized average trip length LU,Rnt0 as follow.(12)LU,Rnt0=vUt0⋅NU,KRnt0MU,KRnt0.Note that, we assume that complete information about MFD is taken from ITS of an initialized urban network. The traffic equilibrium analysis flowchart in the bi-level model is presented in Figure1, while the corresponding algorithm is summarized as follows:Step 0. Initialization.(a)
Set iteration numberm=1.(b)
Initialize region accumulationNRnt0 and speeds vRnt0 based on traffic data acquisition from the network.(c)
Apply (1)–(5) to gain the required inputs, i.e. MU,KRnt0, NU,Kt0. The initialized average trip length LU,Rnt0 is calculated by (12).(d)
Based on the initializedO-D demand, get the conversion of the exogenous traffic flow demand QU,Kt0 (aggregated region O-D demand). Note that, the demand which needs to be assigned QU,Kt1=QU,Kt0 because no optimization has been made at the initial time t0.Step 1. Calculating aggregate route choice parameters(13)ϕU,Kptm=e−TU,Kp∑pe−TU,Kp.(a)
For each origin regionU to the final destination K, apply (6) and (7) to calculate the travel time TU,Kp of effective region path p for ∀p∈WU,K.(b)
Based on the travel timeTU,Kp, compute path assignment ratios with the following logit formula:(c)
Calculate the path assignment demand:qU,Kptm=ϕU,Kptm⋅QU,Ktm.(d)
Update aggregated region demandQU,Rntm by (2) for ∀U∈ℝ,Rn∈HU.Step 2. Establishing DUE state(a)
Apply Step 1-3 from the DUE algorithm.(b)
Return the new accumulationNRntλ based on the DUE result in the internal-region model.Step 3. Update aggregate route choice parameters(14)LU,Rntm=∑o∈U∑r∑VU∩Rni∈VU∩Rnq⌢o,VU∩Rnir⋅lr+∑d∈Rn∑r∑VU∩Rni∈VU∩Rnq⌢VU∩Rni,dr⋅lrNU,KRntm.(a)
Update the aggregate parameters: let the new region accumulationNRntm=NRntλ in region level and implement a region-based model (1)–(5) to get region level dynamics, i.e. MU,KRntm, NU,Ktm.(b)
Calculate the new average trip length as follow:Step 4. Stopping criteria(a)
EvaluateM=∑Rn∈ℝNRntm−NRntm−12.(b)
IfM≥ℵ, where ℵ is a pre-defined threshold, set m=m+1 and go to Step 1. Otherwise, finish the procedure.It is noteworthy that the iteration number (m and λ) is different in the bi-level model, meaning that each iteration in the region-based model corresponds to a complete DUE process in internal-region level. In the rolling horizon framework, all parameters can be obtained or calculated in real time. Therefore, the proposed traffic equilibrium analysis in this study is applicable for network performance analysis or route guidance with high timeliness. Particularly, the aggregated region OD demand QU,Kt can be regarded as a constant without elastic demand in the network. In other words, the proposed model be able to work well in the day-to-day network because the aggregated region OD demand is dynamic in each iteration.


### 2.4. The Complexity of Approximating Dynamic Equilibrium Analysis

The input information of the proposed model of approximating dynamic equilibrium analysis is mainly based on the initial network flow distribution and macroscopic traffic parameter information (NU,KRnt, MU,KRnt, LU,Rnt) at time t provided by the MFD of each region. The complexity of the proposed model is as follows:Step 0.The complexity of establishing the initialized network:(a)
-b) Obtain the MFD and MFD parameters according to the average network flow and network density based on the network flow distribution. Set the number of links in the regionRn as ERn and the total of the nodes as VRn. There are g pairs in the directly connected regions. Calculating the average network flow is a weighted average of the link flow. The complexity is O∑RnERn. Similarly, the complexity of the average network density is O∑RnERn;(c)
Get the MFD of the regions and calculateMU,KRnt0, NU,Kt0, LU,Rnt0. The complexity is O3⋅n∧2. It is worth noting that, the value of MU,KRnt0 is zero for indirectly connected regions, however, it still needs to be calculated to form a matrix list of the parameter information of each region;(d)
Construct the regional OD matrix: only allocate the traffic demand to all the OD pairs at timet, and add them to the corresponding regional OD matrix.Step 1. The complexity of calculating the regional route choice parameters:(15)O=n⋅On⋅logn+K+g⋅logg=On∧2⋅logn+n⋅K+g⋅logg.(a)
Calculate the travel cost of the route between regions. The total of routes needs to be calculated isWU,K. The maximum complexity is Οn⋅n−2!. However, because the number of routes between regions is small and the proposed model has an iterative process, all routes between regions will be involved in the iterative process. Therefore, taking the k shortest paths between the origin region and the destination region in each iteration is enough. The complexity is as follows:(b)
-c) The complexity of calculating the probability of all route choices isOk⋅n and allocating the region demand is Ok⋅n;(d)
According to the traffic demand allocated by the regional route, to determine the traffic flow between various regions only needs to traverse the regional route of the allocated traffic demand and superimpose the traffic of the same regional pair, which is similar to the flow conversion between routes and links in a standard traffic network. If the regional route containshRn inter-regional links on average, the complexity is OhRn⋅k⋅n.Step 2. The complexity of DUE in region a) According to the traffic demandQU,Rntm between regions and the inter-regional traffic demand, solve the DUE by MSA algorithm. Assume that any shortest path has hRnin links and DUE needs to be iterated λ times in the region, the complexity is as follows according to the analysis of DUE in Appendices. (16)Oλ⋅∑RnERn+VU∩Rni⋅VRn+VRn+hRnin+1⋅VRn∧2.(b)
Update the average traffic flow of each region according to the link flow calculated by the DUE in the region. The complexity isO∑RnERn.Step 3. The complexity of calculating the macroscopic parameter(a)
The complexity of updating the macroscopic parameterMU,KRntm and NU,Ktm is O2⋅n∧2;(b)
Based on the updating formula ofLU,Rntm, count the number of combinations of internal-region nodes and boundary nodes between the regions. The complexity is O2VU∩Rni⋅VRn.Step 4. The complexity of stopping criteriaThe complexity of evaluatingM is On.The iterative process is Step 1 to Step 4, and the number of iterations is m times. In summary, the complexity of the proposed model is as follows:(17)OBLADEM=2⋅O∑RnERn+O3⋅n∧2+OV∧2+m⋅Οn⋅n−2!+On∧2⋅logn+n⋅k+g⋅logg+2⋅Ok⋅n+OhRn⋅k⋅n+Oλ⋅∑Rn2ERn+VU∩Rni⋅VRn+VRn+hRnin+1⋅VRn∧2+O∑RnERn+O2⋅n∧2+O2∑RnVU∩Rni⋅VRn+On.Based on the qualitative analysis of the network topology, the complexity of the proposed model can be simplified. First of all, the number of regions that the urban transportation network is divided into is limited. Therefore, the general value isn=3,6 and logn≈1,2. In the k shortest search algorithm, k can be selected according to actual needs. In the proposed model, the value is 3. Due to the limited layout of the regional locations, there is less direct communication between regions. Therefore, the value of g is lower and set logg≈1,3. hRnin is the average number of links contained in the shortest path within the region. Since any region is much smaller than the entire transportation network, hRnin≪h can be speculated. VU∩Rni indicates the number of boundary nodes between regions and ∑RnVU∩Rni≪V. Through ignoring the smaller complexity, the simplified expression of the complexity of BLADEM is as follows:(18)OBLADEM≈2m⋅λ+m+2⋅OE+OV∧2+m⋅Oλ⋅∑RnVU∩Rni⋅VRn+VRn+hRnin+1⋅VRn∧2+O2∑RnVU∩Rni⋅VRn.


### 2.5. Comparative Analysis of the Algorithm Complexity

According to the complexity of the DUE (see in Appendices) modelODUE and the proposed model OBLADEM, it is possible to evaluate the pros and cons of the two models in terms of operational efficiency and applicability in the actual traffic environment by the difference comparison method. The complexity difference function fOΔ of the two models is shown below:(19)fOΔ=ODUE−OBLADEM=OJ⋅mDUE⋅2E+V+h+1⋅V∧2−V∧2−2mBLADEM⋅λ+mBLADEM+2⋅E−2mBLADEM∑RnVU∩Rni⋅VRn−mBLADEM⋅λ⋅∑RnVU∩Rni⋅VRn+VRn+hRnin+1⋅VRn∧2.The complexity difference function can be adjusted as follows:(20)fOΔ=OJ⋅mDUE−mBLADEM⋅λ−0.5mBLADEM−1⋅2E−OJ⋅mDUE−1⋅V∧2−O2mBLADEM∑RnVU∩Rni⋅VRn+OJ⋅mDUE⋅V+h⋅V∧2−OmBLADEM⋅λ⋅∑RnVU∩Rni⋅VRn+VRn+hRnin+1⋅VRn∧2.In order to facilitate the analysis,fOΔ can be split into four parts fOΔ1, fOΔ2, fOΔ3 and fOΔ4:(21)fOΔ1=OJ⋅mDUE−mBLADEM⋅λ−0.5mBLADEM−1⋅2E,fOΔ2=OJ⋅mDUE−1⋅V∧2−O2mBLADEM∑RnVU∩Rni⋅VRn,fOΔ3=OJ⋅mDUE⋅V∧2−Oλ⋅mBLADEM⋅∑RnVU∩Rni⋅VRn,fOΔ4=OJ⋅mDUE⋅V+h−1⋅V∧2−O∑Rnλ⋅mBLADEMVRn+hRnin+1⋅VRn∧2.(a)
ForfOΔ1, because mDUE is the number of iterations of traffic assignment for the overall network, and λ is the number of iterations of traffic assignment within the regional network, there is mDUE>λ. The number of iterations mBLADEM of traffic assignment between each regional network is generally less than 10. However, any vehicle entering the link at the beginning of Δt cannot leave the link before the end of Δt. Therefore, the value of is generally not small. Therefore, the value of J is generally not small. For example, the total research time is only 30 minutes, however, J is generally controlled at 25,35 to meet the constraints of DUE. To sum up, fOΔ1∈0,+∞.(b)
ForfOΔ2, In generally, the number of nodes on the boundary is less than the total number of nodes in the region VU∩Rni<VRn. Existing V=∑RnVRn and J⋅mDUE≫2mBLADEM, the following can be obtained:(22)V∧2=∑RnVRn∧2≫∑RnVRn∧2>∑RnVU∩Rni⋅VRn.To sum up,fOΔ2∈0,+∞.(c)
Obviously, forfOΔ3, there is fOΔ3∈0,+∞. Due to V∧2≫∑RnVRn∧2, the following can be obtained:(23)J⋅mDUE⋅V+h−1>λ⋅mBLADEMVRn+hRnin+1.To sum up,fOΔ4∈0,+∞. Note that, h and hRnin are the average number of links contained in the shortest path between the regions and within the region respectively. Therefore, there must be h>hRnin for a given network.In summary,fOΔ=ODUE−OBLADEM≫0 can be concluded. That is, the complexity of BLADEM model must be lower than the DUE model. Moreover, based on the analysis of fOΔ1, fOΔ2, fOΔ3 and fOΔ4, when the topology structure of the network is complicated, the difference between the number of nodes in the network and the number of nodes in the regional network is greater, leading to the value of fOΔ to be larger. Therefore, the BLADEM model has more obvious advantages in computational efficiency.


## 2.1. Aggregated Route Choice in Region-Based Model

Let us assume that a large-scale networkG=V,E,n is partitioned into n regions with a heterogeneous distribution of congestion, ℝ=R1,R2,…,Rn. In network topology with multi-regions, V and E represent nodes (intersections) and edges (links), respectively. For internal-region, the traffic dynamics is well described by a low-scatter MFD FPrRnNRn,NRn, where PrRnNRnt is defined as the travel production[veh.m/s] at time t corresponding region Rn accumulation NRnt (veh). What is more, according to the characteristics of MFD, the average trip length LRnt is constant if there is no change for the route choice and traffic control scheme. Then, we can get the trip completion rate MRnt=PrRnNRnt/LRnt (veh/s) and the average speed vRnt=PrRnNRnt/LRnt, which have been reported in [7, 8, 11].In an urban networkG=V,E,n, any given traditional OD demand (represented by a sequence of nodes or links) can be transformed into a region path pU,K from region U to the final destination K. As shown in Figure 2, a region trip is denoted as pA,EB&DRA,RB,RD,RE. Accordingly, pA,EB is a path containing the sequence of regions to reach E starting from A and through the region B. Obviously, pA,EB&D is a form of pA,EB. Let QUt (veh/s) denote the total traffic demand generated in the region U at the time t, QU,Kt be the exogenous traffic flow demand generated in the region U with the final destination K. Particularly, QU,Ut is defined as internal traffic flow demand in the region U without going through another region. For U,K∈ℝ, we have QUt=∑K∈ℝQU,Kt.Figure 2
The schematic of a multi-region urban network and a path example.Approximately,NUt [veh] is the total accumulation in the region U at the time t and NU,Kt is the vehicle accumulation from region U to the final destination K. In traffic flow conversion process in n regions, more than one route collaboratively to complete the transfer trips for a given OD pair. Let NU,KRnt denote the outflow from the region U to the final destination K through the region Rn; U,K∈ℝ, NUt=∑Rn∈HU∑K∈ℝNU,KRnt, where HU is set of next regions(directly adjacent regions) for the region U. Let qpU,KRn be the demand of pU,KRn. Consequently, the instantaneous accumulation is computed as follow:(1)NRnt=∑U∈ℝ∑K∈ℝ∑p∈WU,KRnqpU,KRnt,(2)NU,KRnt=QU,Rnt=∑p∈WU,KRnqpU,KRnt,Where WU,KRn is the set of paths which reach K starting from U and through region Rn. The trip completion rate MU,KRnt for the vehicles from region U to the final destination K through the next region Rn∈HU is calculated by the following equation.(3)MU,KRnt=minvUt⋅NU,KRntLU,Rnt,CU,RnNRnt⋅NU,KRnt∑I∈ℝNU,IRnt,Where LU,Rnt [m] is the average trip length and CU,RnNRnt is the boundary capacity corresponding region trips from region U to adjacent region Rn∈HU. (3) indicates that the transfer flow between the consecutive regions is the minimum of two terms: (i) the transfer flow which depends on the traffic dynamics in region U and (ii) the boundary capacity between consecutive regions and the proportion of vehicles from region U to destination K through the region Rn∈HU, among all the vehicles that cross the same boundary, i.e. ∑I∈ℝNU,IRnt. More details about the boundary capacity can be founded in previous publications (e.g., [21, 23]).In an regions MFD system, the traffic flow dynamic equations are listed below.(4)dNUtdt=QUt−∑Rn∈HUMU,RnRnt+∑Rn∈HUMRn,UUt,(5)dNU,Ktdt=QU,Kt−∑Rn∈HUMU,KRnt+∑Rn∈HUMRn,KUt.The traffic flow conservation of region is illuminated in (4), while the transfer flow dynamic is described by (5). It is noteworthy that, the vehicle paths to include more than one getting through the same boundaries is permitted, i.e., a region path pB,BC&DRB,RC,RD,RB. For each region path p, p, ppp, p between origin O and destination D, the travel time TO,Dp is calculated based on total trip length LO,Dp and region average speed vRn. For example, to a region path pA,EB&D (see Figure 2), we have:(6)LA,EpA,EB&Dt=LA,Bt+LB,Dt+LD,Et,(7)TA,EpA,EB&Dt=LA,Bt⋅NA+NBvA⋅NA+vB⋅NB+LB,Dt⋅NB+NDvB⋅NB+vD⋅ND+LD,Et⋅ND+NEvD⋅ND+vE⋅NE.(7) indicates that average trip time is obtained by integrating average trip length and average speed between adjacent regions. Note that, in the region-based model, region path defines the sequence of regions from an origin node to a destination node, not the detailed sequence of links. However, the DUE condition is considered in an internal-region model that represents the connectivity about traffic flow distribution of links. Also, traffic equilibrium is based on the accumulation of the vehicles in the corresponding region. In other words, the accumulation is extracted and updated from DUE in the internal-region model. Finally, the region path re-decision based on the changed average trip length and average speed in the region. The trip length between two adjacent regions, like LA,Bt etc., can be calculated by the (12) (the initial length calculation method) and (14) (the length calculation method during iterative process). The DUE process and the estimation of traffic dynamic parameters LU,Rnt, TO,Dpt and CU,RnNRnt in region level are discussed in the following subsection.


## 2.2. Traffic Dynamics in an Internal-Region Model

Consider time-aggregated regional OD demand whose dynamic variation trend is well described by aggregated route choice in the previous subsection. In other words, the traffic demandQU,Rnt,Rn∈HU in consecutive regions is calculated in real time. Let VU∩Rni denote the node i which belongs to the set of boundary nodes between the region U and adjacent region Rn, VU∩Rn=VU∩Rn1,VU∩Rn2,…,VU∩Rni, like red nodes as shown in Figure 3. At internal-region level, the adjacent region trip pU,Rn is taken into account as two form of sub-trip: (i) origin O or internal node in the region U to boundary node VU∩Rni and (ii) boundary node VU∩Rni to internal node in the region Rn or destination D.Figure 3
The schematic of a multi-region network with internal topology.Consequently, the traffic demandQU,Rnt of the adjacent region trip pU,Rn is conducted by two-time DTA (dynamic traffic assignment) algorithm. Furthermore, a DUE condition which requires minimal and equal travel times on alternative paths at the same time t [6], is considered for the internal-region traffic dynamics. Note that, in the region trip transformation process, there may be more than one path in each form of sub-trip and application of all boundary nodes in consecutive regions is permitted. That is, for each origin node o, we apply one-to-all time-dependent shortest path algorithm [32] depending on DUE to all boundary nodes, corresponding all-to-one time-dependent shortest path algorithm [33] is used to destination node d from all boundary nodes. For example, a region trip pA,DB with origin node 6 to destination node 26 can be transferred as three-stage sub-trip, including origin node 6 to boundary nodes VA∩B=VA∩B9,VA∩B10,VA∩B11; up-boundary nodes VA∩B to down-boundary nodes VB∩D=VB∩D17,VB∩D18,VB∩D19; boundary nodes VB∩D to destination node 26 (see Figure 3).The boundary capacityCU,RnNRnt as mentioned in the previous subsection can be regarded as the integration of the capacity of the boundary nodes on the driving direction of vehicles. In an urban network, boundary node generally represents the signal control intersection and have the different capacity at different directions, where the capacity of the node VU∩Rni at direction com denotes as CcomVU∩Rni.(8)CU,RnNRn=∑VU∩Rni∈VU∩RnCcomVU∩Rni⋅δcom,r,A.Where δcom,r is an indicator function with a value equal to 1 if the direction com is the same as the path r, otherwise zero. Let co,dr represent the experienced travel time of route r from origin node o to destination node d, corresponding q⌢o,dr denotes as the assigned demand of route r from QU,Rn and lr is the experienced trip length of the route r. The travel time of link te is calculated by BPR (Bureau of Public Roads) function, and we have co,dr=∑e∈Eteδer, where δer is an indicator function with a value equal to 1 if the route r passes through the link e, otherwise zero. Time t is omitted from the following equations for the sake of notational simplicity. The traffic flow conservation equation at the boundary of regions is as follow:(9)QU,Rn|Rn∈HU=∑o∈U∑r∑VU∩Rni∈VU∩Rnq⌢o,VU∩Rnir=∑d∈Rn∑r∑VU∩Rni∈VU∩Rnq⌢VU∩Rni,dr.The results taken from DUE are processed through a well-known heuristic solution called a method of successive averages (MSA). It is effective and highly implemented in DTA [34]. In internal-region model, MSA is employed in each iteration to project future traffic information as part of the direction-finding mechanism in searching for a solution. The establishing DUE state can be summarized as follows:Step 0. Initialization.(a)
Set iteration numberλ=1.(b)
Extract the traffic region demandQU,Rntλ at a time tλ from region-based level for ∀U∈ℝ,Rn∈HU.Step 1. Calculating assignment ratios(10)ηo,VU∩Rnitλ=e−co,VU∩Rni∑ie−co,VU∩Rni.(a)
For each origin internal-region nodeo, apply one-to-all time-dependent shortest path algorithm to boundary nodes and reserve the travel time co,VU∩Rnitλ which represents the lowest travel time origin o to boundary node VU∩Rni at a time tλ.(b)
Based on the lowest travel timeco,VU∩Rnitλ, compute the radio of the demand from origin o to boundary node VU∩Rni with the following logit formula:(c)
Calculate the internal-region OD demand:q⌢o,VU∩Rnitλ=ηo,VU∩Rnitλ⋅QU,Rntλ.(d)
For each boundary nodes, which demand is calculated by (10) based on from origin node o, apply all-to-one time-dependent shortest path algorithm to destination node d. Note that, implement a)-c) process in Step 1 for up-boundary nodes to down-boundary nodes. For example, the travel time cVA∩Bi,VB∩Ditλ can be calculated to compute the radio of the demand for ∀i.Step 2. DUE implementation(11)xeλ+1=xeλ+1λyeλ−xeλ.(a)
Based onStep 1, well-informed internal-region OD demand can be calculated, and we have traffic flow xetλ=∑w∑rq⌢wrtλ⋅δer for each internal-region OD pair w∈W⌢, where W⌢ is the set of internal-region OD pairs.(b)
Apply shortest path algorithm for each OD pair and perform an all-or-nothing assignment for the chosen shortest path. Letyeλtλ represents the updated link flow after an all-or-nothing assignment.(c)
Find the iteration-direction based on MSA and timetλ is omitted from the following equation:Step 3. Stopping test(a)
For each (o,d, r) trio, evaluate ε=yeλ−xeλ.(b)
Ifε≥ℑ, where ℑ is a pre-defined threshold, set λ=λ+1 and go to Step 1. Otherwise, finish the procedure and return the updated region accumulation NRntλ.Note that the DUE process in internal-region model includes two main steps; Calculate well-informed internal-region OD demand based on region demand from region-based level and DUE implementation by MSA. The former is key to connecting region-based level and internal-region level. For the logit model, which manages the travelers’ perception of travel time, can be replaced with C-logit or a cross-nested logit model if necessary. On the other hand, because fixed step sizeα=1/λ, traffic assignment by MSA is general for small “toy” networks, corresponding slow convergence problems in large-scale networks. However, in this study, MSA is only used in the internal-region level assignment. Therefore, there are no limitations to use MSA because internal-region level can be regarded as small “toy” networks. Even if a more intricate is an alternative, it is not expected to improve the results and will bring additional time cost.


## 2.3. Traffic Equilibrium Analysis in the Bi-Level Model

Traditional traffic equilibrium analysis is complex and difficult to tackle in a large-scale network with a large number of nodes and links because it is difficult to get full path alternatives and determining the complex effective-path sets is time-consuming. As an alternative, the problem of traffic equilibrium analysis in this study is to provide the region path (met the DUE condition) in the region-based model and establish a DUE state in the internal-region model. Different from traditional traffic equilibrium analysis, this study produces a faster process and considers traffic dynamics in a rolling horizon framework, meaning that the method establishes a DUE state at the internal-region level and optimizes the region path based on updated region accumulations.The region-based model employs time-dependent aggregated parameters to compute region path with demand assignment, i.e.NU,KRnt, MU,KRnt and LU,Rnt. Such a region path represents the behavior of the overall travelers for route choice. Based on the aggregated route choice at the macroscopic level, the DUE state is established at the internal-region level, and actual traffic flow distribution and chosen path are obtained. In this way, the results of the traffic equilibrium analysis are approximate to traditional models, and the corresponding numerical test is provided in section 4.For an initialized urban network (traffic flow has been loaded), based on traffic information database of ITS (intelligent transportation system), accumulation of region and distribution of traffic flow are well known before the network optimization based on detector data, i.e. the vehicle trajectory data from equipped GPS (Global Position System) on vehicle and fixed loop detector or camera at the intersection. Therefore, the computing region path is not a complicated project. What is more, compared with the traditional model, reducing the application scope DUE to internal-region level makes the calculation time greatly reduced.LetNU,Kt=NU,Kt0 and MU,KRnt=MU,KRnt0 for U,K∈ℝ,Rn∈HU at the initial time t0. Consequently, we can get the initialized average trip length LU,Rnt0 as follow.(12)LU,Rnt0=vUt0⋅NU,KRnt0MU,KRnt0.Note that, we assume that complete information about MFD is taken from ITS of an initialized urban network. The traffic equilibrium analysis flowchart in the bi-level model is presented in Figure1, while the corresponding algorithm is summarized as follows:Step 0. Initialization.(a)
Set iteration numberm=1.(b)
Initialize region accumulationNRnt0 and speeds vRnt0 based on traffic data acquisition from the network.(c)
Apply (1)–(5) to gain the required inputs, i.e. MU,KRnt0, NU,Kt0. The initialized average trip length LU,Rnt0 is calculated by (12).(d)
Based on the initializedO-D demand, get the conversion of the exogenous traffic flow demand QU,Kt0 (aggregated region O-D demand). Note that, the demand which needs to be assigned QU,Kt1=QU,Kt0 because no optimization has been made at the initial time t0.Step 1. Calculating aggregate route choice parameters(13)ϕU,Kptm=e−TU,Kp∑pe−TU,Kp.(a)
For each origin regionU to the final destination K, apply (6) and (7) to calculate the travel time TU,Kp of effective region path p for ∀p∈WU,K.(b)
Based on the travel timeTU,Kp, compute path assignment ratios with the following logit formula:(c)
Calculate the path assignment demand:qU,Kptm=ϕU,Kptm⋅QU,Ktm.(d)
Update aggregated region demandQU,Rntm by (2) for ∀U∈ℝ,Rn∈HU.Step 2. Establishing DUE state(a)
Apply Step 1-3 from the DUE algorithm.(b)
Return the new accumulationNRntλ based on the DUE result in the internal-region model.Step 3. Update aggregate route choice parameters(14)LU,Rntm=∑o∈U∑r∑VU∩Rni∈VU∩Rnq⌢o,VU∩Rnir⋅lr+∑d∈Rn∑r∑VU∩Rni∈VU∩Rnq⌢VU∩Rni,dr⋅lrNU,KRntm.(a)
Update the aggregate parameters: let the new region accumulationNRntm=NRntλ in region level and implement a region-based model (1)–(5) to get region level dynamics, i.e. MU,KRntm, NU,Ktm.(b)
Calculate the new average trip length as follow:Step 4. Stopping criteria(a)
EvaluateM=∑Rn∈ℝNRntm−NRntm−12.(b)
IfM≥ℵ, where ℵ is a pre-defined threshold, set m=m+1 and go to Step 1. Otherwise, finish the procedure.It is noteworthy that the iteration number (m and λ) is different in the bi-level model, meaning that each iteration in the region-based model corresponds to a complete DUE process in internal-region level. In the rolling horizon framework, all parameters can be obtained or calculated in real time. Therefore, the proposed traffic equilibrium analysis in this study is applicable for network performance analysis or route guidance with high timeliness. Particularly, the aggregated region OD demand QU,Kt can be regarded as a constant without elastic demand in the network. In other words, the proposed model be able to work well in the day-to-day network because the aggregated region OD demand is dynamic in each iteration.


## 2.4. The Complexity of Approximating Dynamic Equilibrium Analysis

The input information of the proposed model of approximating dynamic equilibrium analysis is mainly based on the initial network flow distribution and macroscopic traffic parameter information (NU,KRnt, MU,KRnt, LU,Rnt) at time t provided by the MFD of each region. The complexity of the proposed model is as follows:Step 0.The complexity of establishing the initialized network:(a)
-b) Obtain the MFD and MFD parameters according to the average network flow and network density based on the network flow distribution. Set the number of links in the regionRn as ERn and the total of the nodes as VRn. There are g pairs in the directly connected regions. Calculating the average network flow is a weighted average of the link flow. The complexity is O∑RnERn. Similarly, the complexity of the average network density is O∑RnERn;(c)
Get the MFD of the regions and calculateMU,KRnt0, NU,Kt0, LU,Rnt0. The complexity is O3⋅n∧2. It is worth noting that, the value of MU,KRnt0 is zero for indirectly connected regions, however, it still needs to be calculated to form a matrix list of the parameter information of each region;(d)
Construct the regional OD matrix: only allocate the traffic demand to all the OD pairs at timet, and add them to the corresponding regional OD matrix.Step 1. The complexity of calculating the regional route choice parameters:(15)O=n⋅On⋅logn+K+g⋅logg=On∧2⋅logn+n⋅K+g⋅logg.(a)
Calculate the travel cost of the route between regions. The total of routes needs to be calculated isWU,K. The maximum complexity is Οn⋅n−2!. However, because the number of routes between regions is small and the proposed model has an iterative process, all routes between regions will be involved in the iterative process. Therefore, taking the k shortest paths between the origin region and the destination region in each iteration is enough. The complexity is as follows:(b)
-c) The complexity of calculating the probability of all route choices isOk⋅n and allocating the region demand is Ok⋅n;(d)
According to the traffic demand allocated by the regional route, to determine the traffic flow between various regions only needs to traverse the regional route of the allocated traffic demand and superimpose the traffic of the same regional pair, which is similar to the flow conversion between routes and links in a standard traffic network. If the regional route containshRn inter-regional links on average, the complexity is OhRn⋅k⋅n.Step 2. The complexity of DUE in region a) According to the traffic demandQU,Rntm between regions and the inter-regional traffic demand, solve the DUE by MSA algorithm. Assume that any shortest path has hRnin links and DUE needs to be iterated λ times in the region, the complexity is as follows according to the analysis of DUE in Appendices. (16)Oλ⋅∑RnERn+VU∩Rni⋅VRn+VRn+hRnin+1⋅VRn∧2.(b)
Update the average traffic flow of each region according to the link flow calculated by the DUE in the region. The complexity isO∑RnERn.Step 3. The complexity of calculating the macroscopic parameter(a)
The complexity of updating the macroscopic parameterMU,KRntm and NU,Ktm is O2⋅n∧2;(b)
Based on the updating formula ofLU,Rntm, count the number of combinations of internal-region nodes and boundary nodes between the regions. The complexity is O2VU∩Rni⋅VRn.Step 4. The complexity of stopping criteriaThe complexity of evaluatingM is On.The iterative process is Step 1 to Step 4, and the number of iterations is m times. In summary, the complexity of the proposed model is as follows:(17)OBLADEM=2⋅O∑RnERn+O3⋅n∧2+OV∧2+m⋅Οn⋅n−2!+On∧2⋅logn+n⋅k+g⋅logg+2⋅Ok⋅n+OhRn⋅k⋅n+Oλ⋅∑Rn2ERn+VU∩Rni⋅VRn+VRn+hRnin+1⋅VRn∧2+O∑RnERn+O2⋅n∧2+O2∑RnVU∩Rni⋅VRn+On.Based on the qualitative analysis of the network topology, the complexity of the proposed model can be simplified. First of all, the number of regions that the urban transportation network is divided into is limited. Therefore, the general value isn=3,6 and logn≈1,2. In the k shortest search algorithm, k can be selected according to actual needs. In the proposed model, the value is 3. Due to the limited layout of the regional locations, there is less direct communication between regions. Therefore, the value of g is lower and set logg≈1,3. hRnin is the average number of links contained in the shortest path within the region. Since any region is much smaller than the entire transportation network, hRnin≪h can be speculated. VU∩Rni indicates the number of boundary nodes between regions and ∑RnVU∩Rni≪V. Through ignoring the smaller complexity, the simplified expression of the complexity of BLADEM is as follows:(18)OBLADEM≈2m⋅λ+m+2⋅OE+OV∧2+m⋅Oλ⋅∑RnVU∩Rni⋅VRn+VRn+hRnin+1⋅VRn∧2+O2∑RnVU∩Rni⋅VRn.


## 2.5. Comparative Analysis of the Algorithm Complexity

According to the complexity of the DUE (see in Appendices) modelODUE and the proposed model OBLADEM, it is possible to evaluate the pros and cons of the two models in terms of operational efficiency and applicability in the actual traffic environment by the difference comparison method. The complexity difference function fOΔ of the two models is shown below:(19)fOΔ=ODUE−OBLADEM=OJ⋅mDUE⋅2E+V+h+1⋅V∧2−V∧2−2mBLADEM⋅λ+mBLADEM+2⋅E−2mBLADEM∑RnVU∩Rni⋅VRn−mBLADEM⋅λ⋅∑RnVU∩Rni⋅VRn+VRn+hRnin+1⋅VRn∧2.The complexity difference function can be adjusted as follows:(20)fOΔ=OJ⋅mDUE−mBLADEM⋅λ−0.5mBLADEM−1⋅2E−OJ⋅mDUE−1⋅V∧2−O2mBLADEM∑RnVU∩Rni⋅VRn+OJ⋅mDUE⋅V+h⋅V∧2−OmBLADEM⋅λ⋅∑RnVU∩Rni⋅VRn+VRn+hRnin+1⋅VRn∧2.In order to facilitate the analysis,fOΔ can be split into four parts fOΔ1, fOΔ2, fOΔ3 and fOΔ4:(21)fOΔ1=OJ⋅mDUE−mBLADEM⋅λ−0.5mBLADEM−1⋅2E,fOΔ2=OJ⋅mDUE−1⋅V∧2−O2mBLADEM∑RnVU∩Rni⋅VRn,fOΔ3=OJ⋅mDUE⋅V∧2−Oλ⋅mBLADEM⋅∑RnVU∩Rni⋅VRn,fOΔ4=OJ⋅mDUE⋅V+h−1⋅V∧2−O∑Rnλ⋅mBLADEMVRn+hRnin+1⋅VRn∧2.(a)
ForfOΔ1, because mDUE is the number of iterations of traffic assignment for the overall network, and λ is the number of iterations of traffic assignment within the regional network, there is mDUE>λ. The number of iterations mBLADEM of traffic assignment between each regional network is generally less than 10. However, any vehicle entering the link at the beginning of Δt cannot leave the link before the end of Δt. Therefore, the value of is generally not small. Therefore, the value of J is generally not small. For example, the total research time is only 30 minutes, however, J is generally controlled at 25,35 to meet the constraints of DUE. To sum up, fOΔ1∈0,+∞.(b)
ForfOΔ2, In generally, the number of nodes on the boundary is less than the total number of nodes in the region VU∩Rni<VRn. Existing V=∑RnVRn and J⋅mDUE≫2mBLADEM, the following can be obtained:(22)V∧2=∑RnVRn∧2≫∑RnVRn∧2>∑RnVU∩Rni⋅VRn.To sum up,fOΔ2∈0,+∞.(c)
Obviously, forfOΔ3, there is fOΔ3∈0,+∞. Due to V∧2≫∑RnVRn∧2, the following can be obtained:(23)J⋅mDUE⋅V+h−1>λ⋅mBLADEMVRn+hRnin+1.To sum up,fOΔ4∈0,+∞. Note that, h and hRnin are the average number of links contained in the shortest path between the regions and within the region respectively. Therefore, there must be h>hRnin for a given network.In summary,fOΔ=ODUE−OBLADEM≫0 can be concluded. That is, the complexity of BLADEM model must be lower than the DUE model. Moreover, based on the analysis of fOΔ1, fOΔ2, fOΔ3 and fOΔ4, when the topology structure of the network is complicated, the difference between the number of nodes in the network and the number of nodes in the regional network is greater, leading to the value of fOΔ to be larger. Therefore, the BLADEM model has more obvious advantages in computational efficiency.


## 3. Experimental Design

The experimental network presented in Figure4, including 44 signal-controlled intersections (nodes) and 70 links (edges), consists of four regions, where region 1 is a university area, region 2 is the workspace with a transportation hub, region 3 is tourist areas within the city, and region 4 is a representative CBD (Central Business District) area. To analyze the high-level traffic demand and time-varying traffic conditions in every region, the detailed traffic information (as inputs of the model) such as traffic flow, speed, the density of links need to be real time updated based on fixed-location detectors. However, subjecting to research conditions, only high-precision trajectory data of the floating car can be obtained through the GAIA opening data plan by DiDi. The trajectories data were collected from 10 : 00 a.m. to 12 : 00 a.m. on one workday (11/25/2016) and the total number of trajectory data points is 3,330,870. Each trajectory data point includes information on Vehicle_ID, GPS coordinates, and instantaneous speed at the frequency of 3 s.Figure 4
The topology of the experimental network. (a) Regional representation (b) Link-level representation.
(a)(b)The scheme of experimental design is as follows:(i)
Get the traffic flow of links. An analytical method for traffic flow estimation based on high-resolution vehicle trajectories can be adopted to get the traffic flow of links in the experimental network, seeing literature [35] for details.(ii)
Estimate the OD matrix. Since the purpose of this experimental design is to verify the efficiency and applicability of the BLADEM model, the actual traffic demand of network is only the basic input information during each iteration of the model. Therefore, the estimation of the OD matrix only requires approximate accuracy. In the experimental design, the method of estimating the OD matrix is adopted, seeing literature [36] for details.(iii)
Set the OD matrix as the initial input information of all models (including DUE model, BLADEM model and the previous model) in the experimental design.(iv)
The regional OD pairs are aggregated based on the distribution of origin and destination points across the regions. The boundary capacity of regions can be regarded as the integration of the capacity of intersection on the driving direction.(v)
Analyze results from three different perspectives: (1) Comparison of the traffic dynamics with the DUE algorithm; (2) Comparison of the running time with the DUE algorithm; (3) Comparison of the traffic dynamics with the previous algorithm.Regarding the DUE state, the MSA method is adopted in the entire network or the internal-region (presented in Section2.2) to achieve that the actual travel times experienced by travelers departing at the same time are equal and minimal for each OD pair [37]. However, different application scopes of the DUE model lead to significant differences in computing efficiency. Theoretical analysis is given in detail (presented in Section 2.5), and experimental results are presented in the following section.It’s worth noting that, the reason of choosing the real urban network as the experimental network is two-fold: to observe the application of the proposed model in the complex traffic network and to provide qualitative analysis of traffic dynamics. Regarding the former, due to the inputted traffic information is updated in real time and the topology of the network is extracted from the real urban network, the experimental design is more convenient for practice. For the other, based on the characteristics of regions, the rationality of regional dynamics can be discussed. The purpose of experimental design is elaborated as follows:(1)
Verify the accuracy of the proposed model in traffic assignment. Regarding the dynamic user equilibrium assignment, we incorporate the MFD framework into the bi-level model. Through the macro-control at the regional level and micro-assignment at the link-level, DTA in a new profile is studied to satisfy DUE conditions. Compared to the DUE method, the bi-level model is valid if the difference between the results of traffic assignment is less than the threshold value under the DUE state.(2)
Verify the degree of improvement of computational efficiency. Due to multi-MFDs and dynamic regional paths are incorporated into the proposed model, the computational complexity is lower than the DUE algorithm. The difference in computational complexity is proved by comparing the running time of the proposed model and the traditional model to reach the DUE state under the same traffic demand in the same period.In this paper, a large-scale network can be represented as a structure: network-region-link. There is an assumption: the network can be divided into several regions (with small spatial link density heterogeneity) with stable MFD. On the principle of partitioning, the fewer divided regions is the better under the condition that the MFD of the divided region is stable. This is because too many regions can greatly affect the computational complexity of network management control strategies. The proposed model seeks for approximate dynamic equilibrium after the region division is completed. Therefore, under the condition that the results of region division are consistent, region division does not affect the comparative analysis of the proposed model with traditional DUE model and other models. Moreover, the partition structure shown in Figure4 is confirmed according to the partition principle. That is, the stability of the region MFD has been verified and the range of region is as large as possible.


## 4. Results and Discussion

This section consists of three subsections. Section4.1 investigates how well the proposed model developed in section 2.3 can approximate the dynamics of the DUE algorithm. The results of the running time from the proposed model comparing the DUE algorithm with different traffic demand are presented in Section 4.2. Furthermore, comparison of the traffic dynamics with the previous algorithm (has the similar model structure) is discussed in Section 4.3. It should be clearly noted that the proposed model analyses approximate dynamic user equilibrium. The object that proposed models need to compare is DUE model. Therefore, we compared the degree of approximation to DUE model from various perspectives in section of results and discussion, including accumulations of 4 regions, path travel time, MFD dynamics of each region, the average speed of vehicles in the regions, as shown in Figures 5–7. Figures 5–7 and Table 1 mainly demonstrates approximation and computational efficiency. The difference between proposed model and MRRGM model is mainly DUE application layer, not approximation and computational efficiency. As a matter of fact, the algorithm structure of the link level is more complex than the sub-region level, and the proposed model should be lower than the MRRGM model in computational efficiency.Figure 5
Accumulation of regions with different models.Figure 6
The travel time of cross-region path for the same OD pair.Figure 7
Consistency validation of dynamic characteristics in MFD.Table 1
Notation list.
VariableSpecificationGRepresents the large-scale network andG=V,E,nℝRepresents the set of multi-regions,ℝ=R1,R2,…,RnFPrRnNRn,NRnRepresents the MFD of regionRnPrRnNRntThe travel production (veh.m/s) at timet of region RnNRntThe accumulation (veh) at timet of region RnLRntThe average trip length at timet of region RnMRntThe trip completion rate at timet of region RnvRntThe average speed at timet of region RnpU,KRnRepresents a region path from regionU to the final destination K through the region RnQUtThe total traffic demand generated in the regionU at the time tQU,KtThe exogenous traffic flow demand generated in regionU with the final destination KNU,KRntThe outflow from the regionU to the final destination K through the region RnqpU,KRnThe demand of the region pathpU,KRnHUThe set of next regions (directly adjacent regions) for the region UWU,KRnThe set of paths which reachK starting from U and through region RnMU,KRntThe trip completion rate for the vehicles from regionU to the final destination K through the next region Rn∈HUCU,RnNRntThe boundary capacity corresponding region trips from regionU to adjacent region Rn∈HUco,drRepresent the experienced travel time of router from origin node o to destination node dq⌢o,drDenotes as the assigned demand of router from QU,RnlrThe experienced trip length of the routerteThe travel time of the linke


### 4.1. Comparison of the Traffic Dynamics with the DUE Algorithm

This section introduces the comparison of the dynamic equilibrium conditions in the experimental network with the DUE algorithm. The purpose of the comparison is to prove the proposed model can obtain approximate traffic equilibrium analysis with the DUE algorithm. The comprehensive comparison includes multi-level analysis, such as region accumulation, the experienced travel time of path, the MFD characteristics of each region, the average speed of vehicles in the regions, etc.The 2 hours of floating car trajectory data on the day of 11/25/2016 is divided into 6 sub-datasets. Every 2 minutes, the MFD information of the region is calculated and the OD matrix is estimated for each sub-dataset. That is, the BLADEM model and the DUE model are run in each sub-dataset (in each period). It is easy to get the traffic dynamics of each region to investigate how well the BLADEM model can approximate the dynamics of the DUE algorithm.Figure5 compares the accumulations of 4 regions with different models. Intuitively, the proposed model fits well with the evolution trend of accumulations from the DUE algorithm. Due to the limit of the topology of region network (the minimum arterials and area), the lowest region accumulation is region 1. However, similar the topology of region network does not necessarily have the same level of region accumulation, like region 2 and region 3. The commuting behavior of travelers will affect the distribution of traffic demand. Therefore, the region accumulation of region 2 is significantly higher than region 3. To some extent, it proves that the trajectory data extracted from the real urban network can help to analyze the rationality of regional dynamics. Note that approximate region accumulation does not imply complete agreement because a little deviation is inevitable. However, it can be applied well to the perimeter control of network flow with less elaborate requirement on macroscopic level.Another important question is how reliable the proposed model is in dynamic user equilibrium states. Based on DUE conditions, for each OD pair, if the actual travel times experienced by travelers departing at the same time are equal and minimal. As shown in Figure6, the random selected paths with the same origin node and destination node (node 5 and node 24) have approximately uniform path travel time. In other word, any path has the same chosen probability for each OD pair. Because the calculation of travel time within each region by internal-region model has some deviations, the aggregated deviations are inevitable in cross-region paths. However, these minor aggregated deviations are allowed within the margin of error. What is more, Figure 6 provides indirect evidence that the proposed model achieves approximate equilibrium conditions. As the blue line and pink line in Figure 6, the DUE-Path (calculated by the DUE algorithm) and the Proposed-Path (calculated by the proposed model) with same node transition sequence have the similar path travel time.In order to analyze multi-region MFD dynamics, the travel production and region accumulation are calculated inside each region. It is worth noting that the similar MFD shapes are obtained for each region as shown in Figure7. Based on the intuitive observation, the MFD dynamics of the region 2 have the best consistency between the DUE model and the proposed model, subjectively. On the contrary, some fluctuations were detected in the region 1 and 4. In general, the travel choices are increasingly unpredictable in densely populated areas, like the university area of region 1 and the CBD area of region 4. Therefore, the method of time-aggregated regional OD demand analysis based on the aggregated route choice in the region-based model is more different from the DUE algorithm in densely populated areas. It is worth noting that, since the experimental data are taken from the real traffic environment during 10 : 00 AM to 12 : 00 AM, the MFD dynamics of each region does not include the low traffic flow stage, such as the origin where the accumulation of regions is 0.To verify the consistency of the MFD dynamics with the DUE algorithm,K-S test (Kolmogorov-Smirnov test) is employed as a numerical test, and related indicators are illustrated in Figure 8. In statistics, the K-S test [38] is a nonparametric test of the equality of continuous, one-dimensional probability distributions that can be used to compare two samples (two-sample K-S test). The two-sample K-S test is one of the most useful and general nonparametric methods for comparing two samples, as it is sensitive to differences in both location and shape of the empirical cumulative distribution functions of the two samples. Cumulative probability distribution as an indicator, is applied to check the evolution trend. The null hypothesis, which assumes the MFD dynamics are subject to the same distribution as the DUE algorithm, is accepted when probability (K-S test returns) is above 0.05. Then set the logical value of the hypothesis h to zero, otherwise equal to 1.Figure 8
K-S test results for different MFD dynamics.It is evident that the MFD dynamics based on the proposed model are subject to the same distribution as the DUE algorithm because all returned probabilities are more than 0.05. In other words, the proposed model can follow the evolution of MFD dynamics from the DUE algorithm, which is very important in the perimeter flow control for multi-region networks and can help traffic engineers to develop better traffic management projects. The optimal consistency in region 2 is confirmed due to the supreme returned probabilityP=0.909. It is same with intuitive observation in Figure 7.According to the above formula and the traffic distribution of the road network at each time, the average vehicle speed of the region can be calculated, as shown in Figure9. The average speed of vehicles in the four regions is dynamic. To some extent, the average speed of vehicles in the road network indirectly reflects the degree of congestion of the road network. For example, in the initial period of the study period 0–54 min, the average speed of vehicles in region 4 is the lowest, indicating that the congestion level in region 4 is relatively high during this time range. In the 54–76 min period, the average speed of vehicles in region 2 is the lowest. From 76 minutes to the end of the study period, compared with other regions, the congestion degree of region 1 becomes the highest.Figure 9
The average speed of vehicles in the regions.In addition, there are two key points in Figure9:(1)
Although the time when the average vehicle speed of each region reaches the lowest point is different, it is concentrated between 30 and 50 minutes, that is, within the time period of 10 : 50–11 : 10. It shows that the congestion degree of the region is more obvious during the peak period;(2)
The average speed of vehicles in the regions is similar at any time. The reason for this phenomenon is that the upper model of BLADEM model reasonably allocates the region OD matrix based on the average length of region paths. At the region level, as shown in Figure4(a), the travel costs of all region paths are approximately equal when the BLADEM model converges. When the difference of region OD matrix is not very large, the congestion degree of each region in a balanced state is not very different. This point can indirectly prove that the road network has approached the equilibrium state.


### 4.2. Comparison of the Running Time with the DUE Algorithm

In the same calculation and analysis environment, the BLADEM model and the DUE model are respectively applied to calculate and analyze the equilibrium state of the network based on the 6 sub-datasets. The advantages of the two models in calculation efficiency are compared according to the calculation running time. In experimental design, the configuration of the computer is: Intel(R) Core (TM) i7-8650U CPU; 16.0 GB RAM; MATLAB version is R2017a.As shown in Table2, under the same calculation and analysis environment, the calculation time of the BLADEM model is generally lower than the DUE model. Therefore, combined with the verification and analysis in Section 4.1, compared with the DUE model, the BLADEM model can effectively improve the calculation efficiency under the premise of obtaining approximate calculation results. The improved calculation efficiency is between 21% and 42%, which means that the average calculation time is saved by 35.59%. It is worth noting that although the data types of the 6 sub-datasets are the same, there are still differences in computing time under the same computing environment using the same model. The reason for this difference is not only the impact of different CPU temperatures during the calculation and analysis, but also the impact of the difference in the distribution of traffic demand in the initial state of the road network in 6 groups and 4 regions. However, the calculation time of the BLADEM model is relatively more stable.Table 2
Comparison of the running time.
Periods of timeDUE model (sec)BLADEM model (sec)Degree of improvement (%)10 : 00–10 : 20311.16245.5721.0810 : 20–10 : 40394.27239.3839.2910 : 40–11 : 00385.12241.6537.2511 : 00–11 : 20412.61241.0341.5811 : 20–11 : 40384.57234.5339.0211 : 40–12 : 00401.65259.8335.31Compared with other periods, the traffic flow of the traffic network is the lowest in the periods “10 : 00–10 : 20”, as shown in Figure7. This means that there are the less regional OD pairs when the OD matrix is estimated. Because the path of region OD is too long, it will increase the computational complexity of the DUE model. Therefore, the computational time of the DUE model will be reduced. However, for the proposed model, due to the bi-level distribution processing, there is no significant difference in computational complexity between the regional OD pairs and the OD pairs within regions. In other words, without increasing regions, the change of network traffic flow does not affect the computational complexity of the proposed model.


### 4.3. Comparison of the Traffic Dynamics with the Previous Algorithm

The allocation of region OD matrix based on the MFD information of the region has been carried out by many researchers. The most prominent one is the Multi-Region Route Guidance Model (MRRGM) based on dynamic MFD proposed by Yildirimoglu et al. [21]. The main research approach is as follows:(1)
Divide multiple sub-regions within the region, assuming that each sub-region has a stable MFD;(2)
Based on the MFD information of the sub-region, calculate the average travel speed of the vehicle in the sub-region, and then calculate the travel impedance in the sub-region;(3)
According to the travel impedance in the sub-region, calculate the dynamic traffic assignment of the sub-region route in each region, and update the MFD of the sub-region;(4)
Recalculate the MFD information of the region according to the updated MFD of the sub-region, and readjust the traffic demand assignment result of the region route.The MRRGM model provides travel guidance information for region route, which is mainly expressed in the form of region sequences. For the large-scale urban transportation network, there are two shortcomings when facing the control of the actual transportation network:(1)
The travel guidance information of the region route can only facilitate managers to control the traffic flow distribution of the regions. But for travelers, the travel guidance information is still the best constructed by the links, so that the travelers follow the guidance information to change the travel route. Therefore, the travel route guidance provided by the MRRGM model has a limited range of actual traffic applications.(2)
The MRRGM model assumes that the region can be divided into multiple sub-regions with stable MFD, but the reasonable division of the network itself is a complex traffic problem. The reasonable division of multiple sub-regions will be too much time and resources are consumed, which reduces the application efficiency of the model. In addition, in the actual traffic environment, the region may not be exactly divided into a limited number of sub-regions with stable MFD to completely cover the region.The BLADEM model is different from the MRRGM model in that: first, the BLADEM model only needs to calculate the MFD of region; secondly, the BLADEM model provides a standard path composed of links.For the same network (the topology is regions-subregions-links-nodes, as shown in Figure10), the output of the MRRGM model of is the equalization of sub-region flow. The output of the BLADEM model is the equalization of link flow. However, the traffic flow of each sub-region can be deduced inversely based on the traffic distribution of the link calculated by the BLADEM model. Comparing the sub-region flow from the BLADEM model and the MRRGM model, it can be found that the distribution of traffic in sub-regions is sometimes consistent and sometimes inconsistent. The BLADEM model verifies the approximation to DUE. The deduced inversely sub-region flow meets the DUE requirements. Therefore, the BLADEM model can obtain the sub-region flow more in line with DUE.Figure 10
The topology of the network at the sub-region level.In order to verify this point, reconstruct the topology of the network shown in Figure4 to obtain the network as shown in Figure 10: the network topology is G=Rn,Sub−Rn,E,V, that is, the network contains V nodes, E edges (links), n regions Rn and nsub sub-regions Sub−Rn.As shown in Figure10, different colors represent different regions, and each region is divided into 2–3 sub-regions. The sub-region is divided according to the nature of the land and the level of surrounding links. The model of the region divided into sub-regions is not used for calculation, but the stability of the sub-region MFD has been verified based on the traffic distribution calculated by the BLADEM model. It proves the rationality of the divided sub-region. The comparison of the accumulations in the sub-region of the BLADEM model and the MRRGM model are shown in Figure 11. From the accumulation curve, the similar results of both models were achieved in most sub-region.Figure 11
The accumulation curve in sub-region. (a) Subregion 1∼5. (b) Subregion 6∼10.
(a)(b)The results of sub-region 3 and sub-region 9 are the most similar, and the difference in sub-region 1 is the largest. The reason for this deviation is the topology of sub-region 1. Except for the boundary nodes of the network, there are no other nodes and links in the sub-region 1. Therefore, when the travel path needs to pass through the sub-region 1, the traveler makes travel route decisions between the boundary nodes of the sub-region 1, and does not need to enter the region. However, the boundary is shared by adjacent sub-regions. Like sub-region 1, if the path decision passing only at the boundary, it is not appropriate to use only MFD information as route decision information at the sub-region level of the MRRGM model. Obviously, the BLADEM model uses links as a medium to connect internal nodes and boundary nodes. Even if it is from one boundary node to another, the BLADEM model is possible to adjust the path reasonably for travelers.It should be clearly noted that the differences between link level and sub-region level is a normal phenomenon, because there are essential differences in the details of the algorithm. Figure11 is aim to show the difference between the results at the segment level and the results at the sub-region level, rather than showing that the two can be similar. When fluctuation is allowed, the sub-regions with some differences are not analyzed, such as sub-regions 4,7,8,10. Therefore, Only the most prominent differences (sub-region 1) are properly analyzed in this paper. As for the reasons for the existence of fluctuations, this paper does not carry out theoretical derivation, which will be carried out in the next stage of research.To sum up, when the MRRGM model is applied, the sub-region divided within the region requires stable MFD information. Furthermore, the MRRGM model requires the sub-region to have a certain scale (at least one link inside the sub-region). Before the application of the MRRGM model, the work of dividing sub-regions is more complicated and has many constraints. Therefore, the BLADEM model, which takes the links as the research object within the region, is more suitable for the actual traffic environment.


## 4.1. Comparison of the Traffic Dynamics with the DUE Algorithm

This section introduces the comparison of the dynamic equilibrium conditions in the experimental network with the DUE algorithm. The purpose of the comparison is to prove the proposed model can obtain approximate traffic equilibrium analysis with the DUE algorithm. The comprehensive comparison includes multi-level analysis, such as region accumulation, the experienced travel time of path, the MFD characteristics of each region, the average speed of vehicles in the regions, etc.The 2 hours of floating car trajectory data on the day of 11/25/2016 is divided into 6 sub-datasets. Every 2 minutes, the MFD information of the region is calculated and the OD matrix is estimated for each sub-dataset. That is, the BLADEM model and the DUE model are run in each sub-dataset (in each period). It is easy to get the traffic dynamics of each region to investigate how well the BLADEM model can approximate the dynamics of the DUE algorithm.Figure5 compares the accumulations of 4 regions with different models. Intuitively, the proposed model fits well with the evolution trend of accumulations from the DUE algorithm. Due to the limit of the topology of region network (the minimum arterials and area), the lowest region accumulation is region 1. However, similar the topology of region network does not necessarily have the same level of region accumulation, like region 2 and region 3. The commuting behavior of travelers will affect the distribution of traffic demand. Therefore, the region accumulation of region 2 is significantly higher than region 3. To some extent, it proves that the trajectory data extracted from the real urban network can help to analyze the rationality of regional dynamics. Note that approximate region accumulation does not imply complete agreement because a little deviation is inevitable. However, it can be applied well to the perimeter control of network flow with less elaborate requirement on macroscopic level.Another important question is how reliable the proposed model is in dynamic user equilibrium states. Based on DUE conditions, for each OD pair, if the actual travel times experienced by travelers departing at the same time are equal and minimal. As shown in Figure6, the random selected paths with the same origin node and destination node (node 5 and node 24) have approximately uniform path travel time. In other word, any path has the same chosen probability for each OD pair. Because the calculation of travel time within each region by internal-region model has some deviations, the aggregated deviations are inevitable in cross-region paths. However, these minor aggregated deviations are allowed within the margin of error. What is more, Figure 6 provides indirect evidence that the proposed model achieves approximate equilibrium conditions. As the blue line and pink line in Figure 6, the DUE-Path (calculated by the DUE algorithm) and the Proposed-Path (calculated by the proposed model) with same node transition sequence have the similar path travel time.In order to analyze multi-region MFD dynamics, the travel production and region accumulation are calculated inside each region. It is worth noting that the similar MFD shapes are obtained for each region as shown in Figure7. Based on the intuitive observation, the MFD dynamics of the region 2 have the best consistency between the DUE model and the proposed model, subjectively. On the contrary, some fluctuations were detected in the region 1 and 4. In general, the travel choices are increasingly unpredictable in densely populated areas, like the university area of region 1 and the CBD area of region 4. Therefore, the method of time-aggregated regional OD demand analysis based on the aggregated route choice in the region-based model is more different from the DUE algorithm in densely populated areas. It is worth noting that, since the experimental data are taken from the real traffic environment during 10 : 00 AM to 12 : 00 AM, the MFD dynamics of each region does not include the low traffic flow stage, such as the origin where the accumulation of regions is 0.To verify the consistency of the MFD dynamics with the DUE algorithm,K-S test (Kolmogorov-Smirnov test) is employed as a numerical test, and related indicators are illustrated in Figure 8. In statistics, the K-S test [38] is a nonparametric test of the equality of continuous, one-dimensional probability distributions that can be used to compare two samples (two-sample K-S test). The two-sample K-S test is one of the most useful and general nonparametric methods for comparing two samples, as it is sensitive to differences in both location and shape of the empirical cumulative distribution functions of the two samples. Cumulative probability distribution as an indicator, is applied to check the evolution trend. The null hypothesis, which assumes the MFD dynamics are subject to the same distribution as the DUE algorithm, is accepted when probability (K-S test returns) is above 0.05. Then set the logical value of the hypothesis h to zero, otherwise equal to 1.Figure 8
K-S test results for different MFD dynamics.It is evident that the MFD dynamics based on the proposed model are subject to the same distribution as the DUE algorithm because all returned probabilities are more than 0.05. In other words, the proposed model can follow the evolution of MFD dynamics from the DUE algorithm, which is very important in the perimeter flow control for multi-region networks and can help traffic engineers to develop better traffic management projects. The optimal consistency in region 2 is confirmed due to the supreme returned probabilityP=0.909. It is same with intuitive observation in Figure 7.According to the above formula and the traffic distribution of the road network at each time, the average vehicle speed of the region can be calculated, as shown in Figure9. The average speed of vehicles in the four regions is dynamic. To some extent, the average speed of vehicles in the road network indirectly reflects the degree of congestion of the road network. For example, in the initial period of the study period 0–54 min, the average speed of vehicles in region 4 is the lowest, indicating that the congestion level in region 4 is relatively high during this time range. In the 54–76 min period, the average speed of vehicles in region 2 is the lowest. From 76 minutes to the end of the study period, compared with other regions, the congestion degree of region 1 becomes the highest.Figure 9
The average speed of vehicles in the regions.In addition, there are two key points in Figure9:(1)
Although the time when the average vehicle speed of each region reaches the lowest point is different, it is concentrated between 30 and 50 minutes, that is, within the time period of 10 : 50–11 : 10. It shows that the congestion degree of the region is more obvious during the peak period;(2)
The average speed of vehicles in the regions is similar at any time. The reason for this phenomenon is that the upper model of BLADEM model reasonably allocates the region OD matrix based on the average length of region paths. At the region level, as shown in Figure4(a), the travel costs of all region paths are approximately equal when the BLADEM model converges. When the difference of region OD matrix is not very large, the congestion degree of each region in a balanced state is not very different. This point can indirectly prove that the road network has approached the equilibrium state.


## 4.2. Comparison of the Running Time with the DUE Algorithm

In the same calculation and analysis environment, the BLADEM model and the DUE model are respectively applied to calculate and analyze the equilibrium state of the network based on the 6 sub-datasets. The advantages of the two models in calculation efficiency are compared according to the calculation running time. In experimental design, the configuration of the computer is: Intel(R) Core (TM) i7-8650U CPU; 16.0 GB RAM; MATLAB version is R2017a.As shown in Table2, under the same calculation and analysis environment, the calculation time of the BLADEM model is generally lower than the DUE model. Therefore, combined with the verification and analysis in Section 4.1, compared with the DUE model, the BLADEM model can effectively improve the calculation efficiency under the premise of obtaining approximate calculation results. The improved calculation efficiency is between 21% and 42%, which means that the average calculation time is saved by 35.59%. It is worth noting that although the data types of the 6 sub-datasets are the same, there are still differences in computing time under the same computing environment using the same model. The reason for this difference is not only the impact of different CPU temperatures during the calculation and analysis, but also the impact of the difference in the distribution of traffic demand in the initial state of the road network in 6 groups and 4 regions. However, the calculation time of the BLADEM model is relatively more stable.Table 2
Comparison of the running time.
Periods of timeDUE model (sec)BLADEM model (sec)Degree of improvement (%)10 : 00–10 : 20311.16245.5721.0810 : 20–10 : 40394.27239.3839.2910 : 40–11 : 00385.12241.6537.2511 : 00–11 : 20412.61241.0341.5811 : 20–11 : 40384.57234.5339.0211 : 40–12 : 00401.65259.8335.31Compared with other periods, the traffic flow of the traffic network is the lowest in the periods “10 : 00–10 : 20”, as shown in Figure7. This means that there are the less regional OD pairs when the OD matrix is estimated. Because the path of region OD is too long, it will increase the computational complexity of the DUE model. Therefore, the computational time of the DUE model will be reduced. However, for the proposed model, due to the bi-level distribution processing, there is no significant difference in computational complexity between the regional OD pairs and the OD pairs within regions. In other words, without increasing regions, the change of network traffic flow does not affect the computational complexity of the proposed model.


## 4.3. Comparison of the Traffic Dynamics with the Previous Algorithm

The allocation of region OD matrix based on the MFD information of the region has been carried out by many researchers. The most prominent one is the Multi-Region Route Guidance Model (MRRGM) based on dynamic MFD proposed by Yildirimoglu et al. [21]. The main research approach is as follows:(1)
Divide multiple sub-regions within the region, assuming that each sub-region has a stable MFD;(2)
Based on the MFD information of the sub-region, calculate the average travel speed of the vehicle in the sub-region, and then calculate the travel impedance in the sub-region;(3)
According to the travel impedance in the sub-region, calculate the dynamic traffic assignment of the sub-region route in each region, and update the MFD of the sub-region;(4)
Recalculate the MFD information of the region according to the updated MFD of the sub-region, and readjust the traffic demand assignment result of the region route.The MRRGM model provides travel guidance information for region route, which is mainly expressed in the form of region sequences. For the large-scale urban transportation network, there are two shortcomings when facing the control of the actual transportation network:(1)
The travel guidance information of the region route can only facilitate managers to control the traffic flow distribution of the regions. But for travelers, the travel guidance information is still the best constructed by the links, so that the travelers follow the guidance information to change the travel route. Therefore, the travel route guidance provided by the MRRGM model has a limited range of actual traffic applications.(2)
The MRRGM model assumes that the region can be divided into multiple sub-regions with stable MFD, but the reasonable division of the network itself is a complex traffic problem. The reasonable division of multiple sub-regions will be too much time and resources are consumed, which reduces the application efficiency of the model. In addition, in the actual traffic environment, the region may not be exactly divided into a limited number of sub-regions with stable MFD to completely cover the region.The BLADEM model is different from the MRRGM model in that: first, the BLADEM model only needs to calculate the MFD of region; secondly, the BLADEM model provides a standard path composed of links.For the same network (the topology is regions-subregions-links-nodes, as shown in Figure10), the output of the MRRGM model of is the equalization of sub-region flow. The output of the BLADEM model is the equalization of link flow. However, the traffic flow of each sub-region can be deduced inversely based on the traffic distribution of the link calculated by the BLADEM model. Comparing the sub-region flow from the BLADEM model and the MRRGM model, it can be found that the distribution of traffic in sub-regions is sometimes consistent and sometimes inconsistent. The BLADEM model verifies the approximation to DUE. The deduced inversely sub-region flow meets the DUE requirements. Therefore, the BLADEM model can obtain the sub-region flow more in line with DUE.Figure 10
The topology of the network at the sub-region level.In order to verify this point, reconstruct the topology of the network shown in Figure4 to obtain the network as shown in Figure 10: the network topology is G=Rn,Sub−Rn,E,V, that is, the network contains V nodes, E edges (links), n regions Rn and nsub sub-regions Sub−Rn.As shown in Figure10, different colors represent different regions, and each region is divided into 2–3 sub-regions. The sub-region is divided according to the nature of the land and the level of surrounding links. The model of the region divided into sub-regions is not used for calculation, but the stability of the sub-region MFD has been verified based on the traffic distribution calculated by the BLADEM model. It proves the rationality of the divided sub-region. The comparison of the accumulations in the sub-region of the BLADEM model and the MRRGM model are shown in Figure 11. From the accumulation curve, the similar results of both models were achieved in most sub-region.Figure 11
The accumulation curve in sub-region. (a) Subregion 1∼5. (b) Subregion 6∼10.
(a)(b)The results of sub-region 3 and sub-region 9 are the most similar, and the difference in sub-region 1 is the largest. The reason for this deviation is the topology of sub-region 1. Except for the boundary nodes of the network, there are no other nodes and links in the sub-region 1. Therefore, when the travel path needs to pass through the sub-region 1, the traveler makes travel route decisions between the boundary nodes of the sub-region 1, and does not need to enter the region. However, the boundary is shared by adjacent sub-regions. Like sub-region 1, if the path decision passing only at the boundary, it is not appropriate to use only MFD information as route decision information at the sub-region level of the MRRGM model. Obviously, the BLADEM model uses links as a medium to connect internal nodes and boundary nodes. Even if it is from one boundary node to another, the BLADEM model is possible to adjust the path reasonably for travelers.It should be clearly noted that the differences between link level and sub-region level is a normal phenomenon, because there are essential differences in the details of the algorithm. Figure11 is aim to show the difference between the results at the segment level and the results at the sub-region level, rather than showing that the two can be similar. When fluctuation is allowed, the sub-regions with some differences are not analyzed, such as sub-regions 4,7,8,10. Therefore, Only the most prominent differences (sub-region 1) are properly analyzed in this paper. As for the reasons for the existence of fluctuations, this paper does not carry out theoretical derivation, which will be carried out in the next stage of research.To sum up, when the MRRGM model is applied, the sub-region divided within the region requires stable MFD information. Furthermore, the MRRGM model requires the sub-region to have a certain scale (at least one link inside the sub-region). Before the application of the MRRGM model, the work of dividing sub-regions is more complicated and has many constraints. Therefore, the BLADEM model, which takes the links as the research object within the region, is more suitable for the actual traffic environment.


## 5. Conclusions

The emerging high-resolution vehicle trajectory data from the floating cars or CVs provide invaluable opportunities to measure the real-time MFD information of the network or the region. Such data can be collected through V2C communication to generate dynamics of regions both in real time and offline.In this paper, the authors developed an innovative approach to get approximating dynamic equilibrium state in multi-region network based on MFD, considering the impact of complex traffic conditions between the regions. In the proposed approach, the network is divided into some regions with the stable MFD, and the DUE model is applied within the region to assign the internal-region O-D demand. For the region level, the length of region path (defines the sequence of regions) is established and the aggregated route choice is analyzed in region-based model. Furthermore, the complexity of the proposed model is derived. Then, the comparative analysis of the algorithm complexity between the proposed model and the DUE model is given.The proposed model is evaluated by using real-world vehicle trajectory data from the DiDi platform. Based on the comprehensive comparison, including region accumulation, the experienced travel time of path, the MFD characteristics of each region and the average speed of vehicles in the regions, we verify that the proposed model can obtain the approximate traffic equilibrium analysis result. Moreover, the proposed model shows superior performance on calculation efficiency. Comparing with the DUE model, the improved calculation efficiency is between 21% and 42% under the same calculation and analysis environment. In addition, because the proposed model is more suitable for the actual traffic environment than the MRRGM model, it has the potentials of supporting the management, route guidance, and performance monitoring.However, this work still has some limitations:(1)
We assume that the network can be divided into some regions with the stable MFD. However, in practical, only a reasonable division of the network can ensure the stability of the region MFD. Namely, the network partitioning method need to be studied before the proposed model applying to the large urban network.(2)
A dynamic route choice mechanism for travelers is incorporated into the model framework. We assume that the travelers preferentially choose the route with the lowest generalized cost. However, in the actual traffic environment, the probability of travelers being completely rational is low, and there will generally be information perception errors. Therefore, the information perception error factors need to be considered in the follow-up research to further optimize the model.



---

*Source: 2604150-2022-08-26.xml*