Approximative Network Partitioning for MFDs from Stationary Sensor Data

Abstract

The macroscopic fundamental diagram (MFD) measures network-level traffic performance of urban road networks. Large-scale networks are normally partitioned into homogeneous regions in relation to road network topology and traffic dynamics. Existing partitioning algorithms rely on unbiased data. Unfortunately, widely available stationary traffic sensors introduce a spatial bias and may fail to identify meaningful regions for MFD estimations. Thus, it is crucial to revisit and develop stationary-sensor-based partitioning algorithm. This paper proposes an alternative two-step partitioning algorithm for MFD estimations based on information collected solely from stationary sensors. In a first step, possible partitioning outcomes are generated in the road networks using random walks. In a second step, the regions’ MFDs are estimated under every possible partitioning outcome. Based on previous work, an indicator is proposed to evaluate the traffic heterogeneity in regions. The proposed partitioning approach is tested with an abstract grid network and empirical data from Zurich. In addition, the results are compared with an algorithm that disregards stationary detectors’ biases. The results demonstrate that the proposed approach performs well for obtaining the quasi-optimal network partitions yielding the lowest heterogeneity among all possible partition outcomes. The presented approach not only complements existing literature, but also offers practice-oriented solutions for transport authorities to estimate the MFDs with their available data.

Recent advances in traffic flow theory as well as an increasing number of field experiments show that the aggregation of traffic flow and density (or speed) can yield a well-defined relationship representing the macroscopic fundamental diagram (MFD) ( 1 – 6 ). The MFD captures the traffic dynamics of urban road transportation networks ( 7 – 9 ) and therefore allows to advance traffic performance monitoring and network-wide traffic control to optimize mobility and infrastructure use ( 10 – 15 ). However, heterogeneous traffic distributions and biased traffic sensors make it difficult to identify well-defined and reproducible MFDs ( 3 , 16 – 21 ).

Identifying regions that are homogeneous with respect to their traffic dynamics has become a promising path of research, attracting much attention and effort. Several benchmark studies have developed partitioning approaches toward static or dynamic homogeneity patterns. Most of these studies, however, assumed the availability of perfect information (on all or a sub-set of links) to identify temporal and spatial traffic patterns. In other words, the existing approaches partition networks into regions under the conditions that unbiased link speed, flow, or density measurements are available ( 17 , 22 – 25 ), or clustered measurements based on the distance to the city center ( 26 ). This, in the real world, is too idealistic, as the dominant data collection technology consists of limited, sparsely distributed and stationary sensors, such as loop detectors or induction radars ( 27 ). While GPS-like, high resolution data, for example, floating car data (FCD) from navigation service providers, are available for traffic state estimation, they remain often inaccessible to transport authorities and researchers. In addition, FCD can introduce a significant bias, as their spatial and temporal distribution cannot be assumed to be homogeneous ( 21 , 28 ). It is thus crucial to revisit and develop stationary-sensor-based approaches, which will remain the major data source in the foreseeable future.

An important problem that arises with stationary sensors is their potential bias resulting from their placement ( 3 , 4 , 29 ). This results in MFD estimates that are sensitive to the spatial distribution of the stationary sensors. For example, if all sensors are placed very close upstream of a traffic signal, the MFD’s density will be overestimated because of recurrent queues. Literature suggests two correction methods. Whereas one method corrects the individual measurements, using detailed traffic information, the other can correct for such bias only collectively using multiple sensors simultaneously, but without the need for detailed traffic signal data ( 3 , 27 ). Given that generally the access to traffic signal data is limited, the latter method was selected to account for the bias. Previous work introduced a correction method that can correct for such issue; however, only collectively ( 3 ). In other words, not every measurement is corrected, but the resulting MFD. A comparison of individual measurements (and their respective heterogeneity levels) is therefore meaningless—only aggregated and corrected measurements are valid. This significantly complicates the search for a suitable partitioning algorithm, whose aim might be to minimize traffic heterogeneity for the identified regions. Therefore, to be able to quantify a region’s traffic heterogeneity, the sensors’ placement distribution needs to be taken into account. In other words, the heterogeneity levels can only be determined for pre-defined regions—which is the inherent part of a partitioning algorithm.

Measurements from stationary sensors might not only be biased as a result of their location within the length of the link, but they usually do not cover all links in the network. Thus, it is not advisable to partition a network based solely on their location. To account for such complexity, the authors propose to first generate many potential partitions of the road network based only on its topology, as topology is considered indeed a determinant of the MFD shape and the distribution of traffic ( 8 , 30 , 31 ). In a second step, the heterogeneity of each partition and its regions is then evaluated. For the first step, community detection techniques that allow to group links in a road network are employed ( 25 , 32 ). Comparing to classical cluster algorithms where infinite number of possibilities can be generated and then selected (e.g., enumeration based), community detection attempts to discover “behavioral” similarities. Given that the correlation of traffic dynamics on links generally decreases with increasing distance, such techniques to generate potential network partitions were deemed suitable. By varying the inputs to the community detection algorithm slightly, many different partitions can be generated, whose corrected MFD and heterogeneity levels can be evaluated individually. The partitioning outcome that results in the lowest heterogeneity can then be chosen as the quasi-optimal solution. Note that the solution from the proposed algorithm is only quasi-optimal and of approximative character, because the shape of the homogeneous neighborhoods depends on the spatial coverage of the stationary sensors that are available and their distribution within the length of the links considered. Nevertheless, the proposed algorithm is the first to account for the complexity of stationary sensors and provides a practical and very useful answer to the network partitioning problem. This approach takes into account, on one side, the connectivity of the network by searching for suitable clusters using random walks, and on the other side, it corrects for potential placement biases of loop detectors. This allows generation of geographically contiguous clusters with a low heterogeneity. The proposed portioning algorithm is static, as the algorithms by Ji and Geroliminis ( 17 ) and Saeedmanesh and Geroliminis ( 22 ), but the day-scale heterogeneity is measured instead of a short period of time to obtain an aggregated 1-day insight into congestion propagation.

The remainder of this paper is organized as follows. The next section describes the partitioning algorithm in detail. Then, the proposed algorithm is applied to an abstract grid network and empirical data from Zurich, Switzerland, and its results compared with an algorithm not taking into account the loop detectors’ biases. This paper then ends with a discussion of the contribution of this methodology.

The Partitioning Algorithm

The proposed methodology consists of two parts: (i) the generation of partition outcomes, and (ii) the MFD estimation and evaluation of heterogeneity. In the following, the authors first focus on the estimation of the MFD from stationary sensors, before discussing the generation of partition outcomes.

MFD Estimation

MFDs are estimated from stationary traffic sensors by averaging link flows $q_{i} (t)$ and densities $k_{i} (t)$ weighted by the link length $l_{i}$ ( 27 ). In case of $M$ links monitored by $M$ stationary sensors, the network average flows and densities are calculated by Equations 1 and 2, respectively.

q_{MFD} (t) = \frac{\sum_{i = 1}^{M} q_{i} (t) l_{i}}{\sum_{i = 1}^{M} l_{i}}

(1)

k_{MFD} (t) = \frac{\sum_{i = 1}^{M} k_{i} (t) l_{i}}{\sum_{i = 1}^{M} l_{i}}

(2)

As mentioned before, an important issue with stationary traffic sensors is that $k_{MFD} (t)$ is sensitive to the sensor location; that is, $k_{MFD} (t)$ is only unbiased if detectors are uniformly distributed within the length of the links ( 2 , 27 , 29 ). This condition is rarely satisfied in real urban networks. To the best of the authors’ knowledge, the network-level density or speed estimation is based on the conjecture that either information from all links is available (e.g., if utilizing a micro-simulation) or that the information collected from the limited links is representative of the whole network. Recently, it was argued and demonstrated that biases can be introduced when estimating traffic state directly from the data ( 3 ). Thus, a bias correction method was proposed by integrating information of the sensor location (with regard to its position within the link). The idea is to account for the spatial differences expressed by any sensor placement distribution, and to re-weight the density values in a way that a uniform distribution is approximated. For this, information is required on the relative location $r_{i}$ of each sensor $i$ on the monitored lane $l_{i}$ , measured by the distance to the downstream traffic signal $p_{i}$ , as described by Equation 3.

r_{i} = \frac{p_{i}}{l_{i}}

(3)

To then obtain an unbiased estimate of $k_{MFD} (t)$ , the distribution of $r_{i}$ across all sensors must be analyzed. The $M$ sensors are divided into $J$ groups according to their relative position. Each group should at least contain a couple of sensors. Then Equations 4 and 5 provide the mathematical formulation for the corrected and unbiased MFD estimation.

q_{MFD} (t) = \frac{1}{J} \sum_{j = 1}^{J} \sum_{i \in M_{j}} \frac{q_{i} (t) l_{i}}{\sum l_{i}}

(4)

k_{MFD} (t) = \frac{1}{J} \sum_{j = 1}^{J} \sum_{i \in M_{j}} \frac{k_{i} (t) l_{i}}{\sum l_{i}}

(5)

with M = ⋃_{j \in J} M_{j} and M_{j} = {i \in M | \frac{j - 1}{J} < r_{i} < \frac{j}{J}}

(5)

Last, the space-mean speed in the MFD $v_{MFD} (t)$ can then be calculated using the fundamental equation of traffic flow, that is, $v_{MFD} (t) = q_{MFD} (t) / k_{MFD} (t)$ . This approach is thus based on the findings by Courbon and Leclercq ( 29 ), who found that a uniform distribution of the loop detectors within the length of the links in the network yields an unbiased MFD. In other words, the authors propose to correct for the bias by aggregating the measurements from many loop detectors that are uniformly distributed within the length of the links. For more details on the proof of this correction method, see Ambühl et al. ( 3 ).

Network Partitioning using Community Detection

The correction method introduced in the previous section requires a priori knowledge on the stationary sensor’s placement. Thus, a potential partitioning algorithm needs to take this into account. As it is generally impossible to know the influence of the placement bias before defining the region, the authors propose to generate and evaluate many potential partition outcomes first. A naive approach could be to repeatedly generate random clusters of the stationary sensors. This, however, would disregard additional information, which is given by the network layout. In urban road networks not all links are connected with all other links, making them similar to a small-world network ( 32 ). In the literature, identifying communities in such dynamic systems can be solved with community detection methods. The community detection algorithm used in this work was defined and implemented by Pons and Latapy ( 33 ). It essentially searches for dense subgraphs, the so-called communities, in a large graph. Such communities can be captured by random walks on the edges (i.e., links) of the directed graph. The intuition behind the algorithm is that communities are likely to cover dense areas of the graph. In other words, for road networks, such community-search can always ensure the connectivity within the communities, that is, the subgraph. Furthermore, the edge weights are the geographic distance between nodes and thus ensure that more distant nodes have a lower probability of being in the same community.

In this analysis, this type of approach is applied to find communities or, in relation to traffic, possible partitions of the network, using a random-walk search algorithm that results in boundaries derived from network topology ( 25 , 34 – 37 ). This is an intuitive approach because much of the MFD’s shape is attributed to the network topology and traffic control schemes ( 25 ). Thus, the objective is to ensure sufficient initial partitions generated with reasonable community features, so that small fluctuations in the generation of partition samples is ensured by varying the step size in the random-walk process. Furthermore, the targeted number of regions that should be retrieved from the community detection algorithm was also varied.

In total, $P$ possible partitioning outcomes are generated in which the random walk ensures that each region is contiguous and connected (for consistency in the driving direction). All partitioning outcomes differ with respect to number, size, and shape of the regions, three of the most important factors defining the partitioning results.

To demonstrate the approach, the partitioning algorithm is applied on a real-world example, the network of Zurich, Switzerland. Figure 1 shows the network used and three possible outcomes of random walks in the road network. First thing to note is that the regions are all contiguous. In addition, the three outcomes show that they differ in their number of regions and the way they split the city. In other words, when a large number of partitions are generated, some might differ substantially, with some outcomes potentially representing the optimal or quasi-optimal partition of the network.

Figure 1.

Examples of neighborhood detection with random walks using the road network of the City of Zurich. (a) A simplified graph representation of the considered road network. Background map from OpenStreetMap; (b) Example A of a neighborhood detection outcome, five regions; (c) Example B of a neighborhood detection outcome, six regions; and (d) Example C of a neighborhood detection outcome, six regions.

For the MFD estimation by region, the information from sensors located within each community or region is then used. Therefore, the sensors need to be assigned o their region. This task is, in particular, necessary for sensors that are located at the boundaries. To this end, the Voronoi polygons around the intersections were built and all polygons of the same community or region amalgamated together. The resulting polygons are then used to identify the region membership of the sensors.

Evaluation of Partitions

For all $P$ partitioning outcomes generated from the community detection algorithm, the MFD was estimated according to Equations 4 and 5. The level of heterogeneity $α$ was then calculated for each region based on a re-sampling method ( 4 ). In this method, the authors not only estimate MFDs with a full sample of sensors, but also estimate MFDs by repeatedly re-sampling without replacement at 50% of the entire number of sensors in the region. A scalar alpha is defined, as computed by Equation 6, which quantifies by how much the capacity ( $Q_{1}$ ) increases (on average) if all links behaved like the 50% of the links with the highest flow.

α = \frac{Q_{0.5}}{Q_{1}}

(6)

Arguably, the more heterogeneous a region is, the more likely it is that a small number of sensors show large deviations from the mean estimated with all the measurements. The parameter $α$ is designed to reveal heterogeneity. If all sensors measure the same traffic conditions, that is, the region is completely homogeneous, then $α = 1$ . As the network becomes more heterogeneous, the value of $α$ increases. The rationale for using capacity to quantify heterogeneity is that the aim is a simple, computationally fast, and clear measure of heterogeneity. Other criteria could be implemented as well. Recall that a partition outcome consists of a number of regions. Thus, for every partitioning result, the network level of heterogeneity is evaluated by calculating the mean of all regions’ $α$ weighted by the $1 / N_{k}$ where $N_{k}$ is the number of loops in region $k$ . A weighted mean is used to allow smaller samples to have a larger heterogeneity than larger samples.

To illustrate this evaluation procedure, the partition methodology is applied to a grid network with two a priori known regions with very different MFDs: At any given moment in time, the left side of the grid network shown in Figure 2a (black points) has a three times lower flow per link than the right side of the grid (gray points). In both cases, the densities are identical. It is clear that an optimal partition would cluster the grid into these two regions. This is also the case when using the partition algorithm. As a matter of fact, when generating $P =$ 10,000 partitions, it is found that the 10 best partitions are all equal to the optimal solution. To evaluate the robustness of the proposed algorithm, the similarity of the best 1,000 partitions is compared with the optimal partition. Figure 2b shows the rand index of the best 1000 partitions compared with the optimal outcome. The rand index ranges from 0 to 1 and indicates how similar a cluster outcome is, with higher values indicating higher similarity. It is shown as a function of the rank of the partition, in which a higher rank represents overall higher heterogeneity. It is observed that the rand index decreases more or less smoothly with the increasing rank of the partition. In other words, even if the number of generated partitions is much smaller than 10,000, it will be possible to find a partition, which is very similar to the optimal partition. In addition, plotting the rand index allows investigation of the quality of the partitioning. If the rand index differs substantially for the best ranked partitions, it is a sign that $P$ is too small and should be increased. Note, that here, the capacity $Q_{1}$ is obtained by quantifying the 97.5th percentile of observed flows in the resampled MFD ( 4 ) and thus captures the day-scale heterogeneity of the network.

Figure 2.

Example of an abstract grid network. (a) Abstract grid network with pre-defined regions. The back loops that measure a flow three times lower than the gray loops at any given time and (b) similarity of partitions based on the rand index. The rank of the partition is defined by its level of heterogeneity.

In summary, the proposed methodology consists of two parts: (i) the generation of meaningful and network-specific partition outcomes using random walks, and (ii) the estimation of an unbiased MFD and its heterogeneity. In the next section, the methodology will be applied to a real-world case.

Data

Before the proposed methodology is applied to a large-scale loop detector data set from Zurich, Switzerland, the empirical data set will be introduced. The preparation of the traffic data and then the road network graphs are briefly described.

Traffic Data

Loop detectors typically record flow $q_{i} (t)$ and occupancy $o_{i} (t)$ . Unfortunately, the measured occupancy is only a proxy for the link’s density and speed. Fortunately, the occupancy can be transformed into density using the detector and car length ( 38 ). Previous work has validated this transformation for the city of Zurich using FCD ( 3 ). From the roughly 1,500 detectors operated by the city, 830 detectors are located on tertiary, secondary, primary, and trunk roads (OpenStreetMap [OSM] classification). These detectors are the input to the empirical analysis. They record flows and occupancy with a resolution of 3 min during 1 week in October 2015. More details about Zurich’s traffic data, control, and traffic surveillance system can be found elsewhere ( 3 , 6 ).

Road Networks

To identify communities, the focus is on roads with a connecting function and thus excludes all residential and service roads. In the context of OSM, the functional road class attributes of the chosen roads are tertiary, secondary, primary, and trunk roads (the same kind of roads are chosen for the traffic data). A directed graph from the road network is then created ( 39 ). In addition, the network’s connectivity and comprehensiveness is validated, link attributes partially updated, and intersections simplified so that a simple four-way intersection is represented by a single node. Last, street segments are amalgamated at pseudo-nodes, that is, a node with degree two if there is no signalized intersection.

Empirical Partitioning Results

Partitioning Based on Community Detection

For the presented data set 10,000 random partitions were generated. Given the city of Zurich’s size of around 80 km², the number of regions per partition was chosen to range from 5 to 12, respectively, with a minimum region size of 2 km², and the weekday data were resampled 1,000 times at a sample size of 0.5. The minimum number of loops required per cluster is 20. Figure 3 shows the best partitioning outcome, in which each color corresponds to one cluster. It can be seen that the partitioning outcome found has five regions. Interestingly, the partition identifies topographical boundaries, such as the lake of Zurich or the hill range to the north west of the city. Here the algorithm finds the correct topographical borders, without any additional information. Moreover, the five regions follow more or less the boundaries of the control regions that the city has defined for its traffic management strategy. This can be seen as a further confirmation of the algorithm. Figure 3b shows the previously introduced rand index comparing every partition outcome to the best partition shown in Figure 3a. It is shown as a function of the rank of the partition, in which a higher rank represents overall higher heterogeneity. Recall that the rand index measures how similar a partition outcome is, and higher values indicate higher similarity. Therefore, one would expect that comparing the best and one of the worst partitions in relation to heterogeneity yields very different regions, and thus a low rand index. Conversely, if the partition algorithm is robust, it is expected that the best partitions in relation to heterogeneity have a relatively high rand index. Compared with the abstract grid, the curve in Figure 3a exhibits higher variations and seems less smooth. The reasons for this behavior are twofold. First, the complexity and size of Zurich’s network is not comparable to a simple abstract grid, for example, one-way roads, and so forth. Second, the correction method has a non-linear effect on the partitioning. In other words, two partition outcomes, that partition the city almost identically, might result in relatively different MFDs (because of the correction method) and in turn different levels of heterogeneity. Nonetheless, a trend is apparent: with decreasing partition ranks, the difference to the best ranking partition also decreases, confirming thereby the quality of the partitioning algorithm. In addition, the relatively stable decrease observed in the moving average trend (in gray) indicates that 10,000 random partitions are enough to find a quasi-optimal solution.

Figure 3.

The best partitioning for the city of Zurich. The white dots represent the location of the loop detectors. The MFDs are shown for each of the regions of the best partition outcome. (a) Best partitioning for Zurich. Five regions can be identified. The regions are found to respect topographical boundaries, such as the lake of Zurich or the hill range to the north west of the city; (b) Rand index measuring the similarity of the partitions to the best partitioning for Zurich. The rank of the partition is defined by its level of heterogeneity. A moving average is added to the series as a dashed line; and (c) MFDs for the regions of the best partitioning for Zurich. Data from five weekdays, each point represents a 3 min interval.

Figure 3c shows the resulting MFDs for 5 days for each cluster found by the best partitioning for Zurich. All MFDs are well defined and show an uncongested branch, with regions 1, 3, and 5 being the only ones reaching saturation. This is not surprising as regions 1 and 2 represent the right and left side of the lake and include the city center. Region 3, on the other hand, covers the inflow from the highway to the city. In addition, the city’s perimeter control affects these three regions. By extending red times at certain intersections, it aims at reducing congestion in the city center ( 40 ).

Comparison with an Algorithm that Disregards Stationary Detectors’ Biases

In the following, the obtained results are compared with an algorithm that disregards the placement biases from stationary detectors. Based on the methodology given in Ji and Geroliminis ( 17 ), the dissimilarity matrix $W (i, j)$ is defined. It sets the dissimilarity value for a link pair to $\exp (- (d_{i} - d_{j})^{2})$ if the two links i and j are adjacent (i.e., they are connected via an intersection). $d_{i}$ and $d_{j}$ represent the densities on the two links. If the links are not adjacent the dissimilarity value is set to 0. As loop detector measurements are point measurements, instead of line segment measurements, adjacent detectors are identified in this example with the boundaries of Voronoi polygons. The matrix $W (i, j)$ is then clustered using a hierarchical clustering with geographic constraints ( 41 ), which is based on a ward-like hierarchical clustering minimizing the within pseudo-inertia. This is advantageous as it allows relaxing of the spatial constraints and demonstrates certain features in more detail.

It is important to note that in this case $d_{i}$ is the density measured by a loop detector on link i. Given the size of the loop detectors (1–2 m), it is clear that the density recorded is only representative at its location (moreover, loop detectors measure occupancy instead of density). Let us consider the following example to understand the importance of accounting for the position of the loop detector. A loop detector in close proximity to a downstream traffic signal will record much higher density values (in the raw data: occupancies) than a loop detector in the same link positioned much further upstream, where no recurring queues occur. In other words, disregarding the position of the loops within the length of the links may yield biased results. For example, a heavily congested road with a loop detector very far upstream of the traffic light could measure very similar traffic densities as an uncongested road with a loop detector close to the traffic light.

Figure 4a shows the clusters found for an average evening peak hour during the analyzed week, if the spatial constraint is completely relaxed. Thus, the clusters are based only on the dissimilarity matrix W(i,j) for adjacent measurements as used by Ji and Geroliminis ( 17 ). From previous studies on congestion propagation, it would be expected that there are at least some aggregated clusters of congestion and that there is some geographical coherence for the clusters found although no spatial constraints are applied. Here, it is observed that there are no obvious spatial contiguous clusters. This, however, does not imply that the distribution of traffic in reality is really as heterogeneous as shown by the partitioning result. In other words, the clustering emphasizes that the density values of the loop detectors are significantly different from the values of adjacent loop detectors. Therefore, Figure 4a illustrates that it is unsuitable to cluster on the biased density values and strongly emphasizes that it is important to define a partitioning algorithm that corrects for loop detectors placement biases.

Figure 4.

(a) Partitioning based on biased loop detector measurements without geographical constraints. (b) Partitioning based on biased loop detector measurements with geographical constraints.

In Figure 4b, we then cluster $W (i, j)$ disregarding the loop detector placement bias but ensuring geographical coherence with additional spatial constraints. Here, clusters different from the one estimated by the algorithm are found. Given that there is no heterogeneity measure defined for loop detectors with placement biases, the partition from Figure 4b was compared with the partitions obtained from our approach. The heterogeneity index as defined in Equation 6 yields values from 1.19 (best partition found) to 1.5 (worst partition found). The partition from Figure 4b yields a value of 1.29, thus exhibiting a higher heterogeneity than the best partition found by the random-walk algorithm. Note that for the estimation of heterogeneity the placement bias is accounted for in both cases. From the 10,000 partitions generated in the process, 1,852 exhibit a lower heterogeneity than the one in Figure 4b.

Conclusion

In this paper, the authors propose a novel network partitioning approach for MFD estimation, especially for data from stationary sensors in which the estimations of network-level densities are usually biased.

The methodology is a suitable alternative for network partitioning for three main reasons. First, given the biases of stationary detectors, a partitioning based on their data alone would lead to a sub-optimal partitioning. Second, it is reasonably argued that an uneven distribution of traffic is also a reflection of certain features of the road network topology. Third, the authors make use of the fact that the network topology affects the shape of the MFD. Thus, the proposed approach does not replace current approaches on network partitioning, but extends this important field to empirical data from stationary detectors—a data source that is still predominantly used in traffic management and control. The proposed approach identifies homogeneous regions using a two-step procedure. In a first step, possible partitioning outcomes are generated based on community detection in the road networks using random walks. In a second step, MFDs are estimated for every possible partitioning outcome and corrected for potential placement biases. In the end, the partitioning outcome with the lowest average heterogeneity is chosen.

The applicability of the proposed method using an abstract grid network was shown. The authors then demonstrated, using empirical data from Zurich, that the method is capable of finding homogeneous regions in a large city. The results are promising, as they showed how the partitioning reduces heterogeneity. In fact, the partition outcome with the lowest heterogeneity value, as defined by the heterogeneity index, is reliable and not very sensitive to partition settings. The proposed method is flexible and pragmatic to apply, as it only requires a graph representation as an input for the generation of potential regions that are contiguous regions and contain a connected road network by the very design of the algorithm. Moreover, it is the first network partition algorithm that accounts for the biases from stationary sensors. Nonetheless, it is worth mentioning that the spatial distribution of the stationary sensors limits to some extent the MFD’s accuracy. The proposed approach is valuable for networks in which the distribution of the loop detectors positions with respect to the length of the links covers a certain range, that is, some are placed in front of a signal, some in the middle of a link, and others far upstream. If, for example, loop detectors are distributed in a very similar way, for example, all loops are located in front of the traffic signal, there is no need to correct for the bias in the context of a partitioning algorithm. Given that in such case all loop measurements are biased in the same way, we can partition on the biased measures with the existing partitioning. Future research will investigate potential improvements to the method, when using the network’s dual graph and other community detection algorithms, such as Lévy flight. In addition, future research will address a time-dynamic partitioning. For example, for a given time slice and density we could use as a criterion the variance in observed flows. Another approach would be to quantify the MFD shape with a functional form in each analyzed partition to finally select that partitioning outcome where all MFDs are well defined with low heterogeneity ( 5 ).

Footnotes

Acknowledgements

This work was supported by ETH Research Grants ETH-04 15-1 and ETH-27 16-1. This research was also supported by the National Science Foundation Grants #KG12017301. We wish to acknowledge the support by Gian Dönier, Urs Birchmeier and Karl Weberruss from Zurich.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: LA, AL; data collection: LA, AL; analysis and interpretation of results: LA, AL, NZ, MM; draft manuscript preparation: AL, LA, NZ, MM, KWA. All authors reviewed the results and approved the final version of the manuscript.

The Standing Committee on Traffic Flow Theory and Characteristics (AHB45) peer-reviewed this paper (19-02327).

References

Geroliminis

Daganzo

C. F.

Existence of Urban-Scale Macroscopic Fundamental Diagrams: Some Experimental Findings. Transportation Research Part B: Methodological, Vol. 42, 2008, pp. 759–770.

Buisson

Ladier

Exploring the Impact of Homogeneity of Trafﬁc Measurements on the Existence of Macroscopic Fundamental Diagrams. Transportation Research Record: Journal of the Transportation Research Board, 2009. 2124: 127–136.

Ambühl

Loder

Menendez

Axhausen

K. W.

Empirical Macroscopic Fundamental Diagrams: New Insights from Loop Detector and Floating Car Data. Presented at 96th Annual Meeting of the Transportation Research Board, Washington, D.C., 2017.

Ambühl

Loder

Bliemer

M. C. J.

Menendez

Axhausen

K. W.

Introducing a Re-Sampling Methodology for the Estimation of Empirical Macroscopic Fundamental Diagrams. Transportation Research Record: Journal of the Transportation Research Board, 2018. 2672(20): 239–248.

Ambühl

Loder

Bliemer

Menendez

Axhausen

K. W.

A Functional Form for the Macroscopic Fundamental Diagram with a Physical Meaning. Transportation Research Part B: Methodological, 2018, in press. https://doi.org/10.1016/j.trb.2018.10.013.

Loder

Ambühl

Menendez

Axhausen

K. W.

, Empirics of Multi-Modal Trafﬁc Networks – Using the 3D Macroscopic Fundamental Diagram. Transportation Research Part C: Emerging Technologies, Vol. 82, 2017, pp. 88–101.

Daganzo

C. F.

Urban Gridlock: Macroscopic Modeling and Mitigation Approaches. Transportation Research Part B: Methodological, Vol. 41, 2007, pp. 49–62.

Daganzo

C. F.

Geroliminis

An Analytical Approximation for the Macroscopic Fundamental Diagram of Urban Trafﬁc. Transportation Research Part B: Methodological, Vol. 42, 2008, pp. 771–781.

Mariotte

Leclercq

Laval

J. A.

Macroscopic Urban Dynamics: Analytical and Numerical Comparisons of Existing Models. Transportation Research Part B: Methodological, Vol. 101, 2017, pp. 245–267.

10.

Kouvelas

Saeedmanesh

Geroliminis

Enhancing Model-Based Feedback Perimeter Control with Data-Driven Online Adaptive Optimization. Transportation Research Part B: Methodological, Vol. 96, 2017, pp. 26–45.

11.

Haddad

Geroliminis

On the Stability of Trafﬁc Perimeter Control in Two-Region Urban Cities. Transportation Research Part B: Methodological, Vol. 46, 2012, pp. 1159–1176.

12.

Ramezani

Haddad

Geroliminis

Dynamics of Heterogeneity in Urban Networks: Aggregated Trafﬁc Modeling and Hierarchical Control. Transportation Research Part B: Methodological, Vol. 74, 2015, pp. 1–19.

13.

Yang

Zheng

Menendez

Multi-Scale Perimeter Control Approach in a Connected-Vehicle Environment. Transportation Research Part C: Emerging Technologies, Vol. 94, 2018, pp. 32–49.

14.

Mahmassani

H. S.

Saberi

Zockaie

Urban Network Gridlock: Theory, Characteristics, and Dynamics. Transportation Research Part C: Emerging Technologies, Vol. 36, 2013, pp. 480–497.

15.

Ampountolas

Zheng

Geroliminis

Macroscopic Modelling and Robust Control of Bi-Modal Multi-Region Urban Road Networks. Transportation Research Part B: Methodological, Vol. 104, 2017, pp. 616–637.

16.

Geroliminis

Sun

Properties of a Well-Deﬁned Macroscopic Fundamental Diagram for Urban Trafﬁc. Transportation Research Part B: Methodological, Vol. 45, No. 3, 2011, pp. 605–617.

17.

Geroliminis

On the Spatial Partitioning of Urban Transportation Networks. Transportation Research Part B: Methodological, Vol. 46, No. 10, 2012, pp. 1639–1656.

18.

Knoop

V. L.

Hoogendoorn

S. P.

van Lint

The Impact of Trafﬁc Dynamics on Macroscopic Fundamental Diagram. Presented at 92nd Annual Meeting of the Transportation Research Board, Washington, D.C., 2017.

19.

Muhlich

Gayah

V. V.

Menendez

An Examination of MFD Hysteresis Patterns for Hierarchical Urban Street Networks using Micro-Simulation. Transportation Research Record: Journal of the Transportation Research Board, 2015. 2491: 117–126.

20.

Gayah

V. V.

Daganzo

C. F.

Clockwise Hysteresis Loops in the Macroscopic Fundamental Diagram: An Effect of Network Instability. Transportation Research Part B: Methodological, Vol. 45, 2011, pp. 643–655.

21.

Doig

J. C.

Gayah

V. V.

Cassidy

M. J.

Inhomogeneous Flow Patterns in Undersaturated Road Networks Implications for Macroscopic Fundamental Diagram. Transportation Research Record: Journal of the Transportation Research Board, 2013. 2390: 68–75.

22.

Saeedmanesh

Geroliminis

Clustering of Heterogeneous Networks with Directional Flows Based on “Snake” Similarities. Transportation Research Part B: Methodological, Vol. 91, 2016, pp. 250–269.

23.

Luo

Geroliminis

Empirical Observations of Congestion Propagation and Dynamic Partitioning with Probe Data for Large-Scale Systems. Transportation Research Record: Journal of the Transportation Research Board, 2014. 2422: 1–11.

24.

Saeedmanesh

Geroliminis

Dynamic Clustering and Propagation of Congestion in Heterogeneously Congested Urban Trafﬁc Networks. Transportation Research Part B: Methodological, Vol. 105, 2017, pp. 193–211.

25.

Chiu

Y. C.

Chen

A Network Partitioning Algorithmic Approach for Macroscopic Fundamental Diagram-Based Hierarchical Trafﬁc Network Management. IEEE Transactions on Intelligent Transportation Systems, Vol. 19, No. 4, 2018, pp. 1130–1139.

26.

Tsubota

Bhaskar

Chung

Macroscopic Fundamental Diagram for Brisbane, Australia. Transportation Research Record: Journal of the Transportation Research Board, 2014. 2421: 12–21.

27.

Leclercq

Chiabaut

Trinquier

Macroscopic Fundamental Diagrams: A Cross-Comparison of Estimation Methods. Transportation Research Part B: Methodological, Vol. 62, 2014, pp. 1–12.

28.

Rakha

Gayah

V. V.

Deriving Macroscopic Fundamental Diagrams from Probe Data: Issues and Proposed Solutions. Transportation Research Part C: Emerging Technologies, Vol. 66, 2016, pp. 136–149.

29.

Courbon

Leclercq

Cross-Comparison of Macroscopic Fundamental Diagram Estimation Methods. Procedia -Social and Behavioral Sciences, Vol. 20, 2011, pp. 417–426.

30.

Geroliminis

Boyaci

The Effect of Variability of Urban Systems Characteristics in the Network Capacity. Transportation Research Part B: Methodological, Vol. 46, 2012, pp. 1607–1623.

31.

Ortigosa

Menendez

Gayah

V. V.

Analysis of Network Exit Functions for Various Urban Grid Network Conﬁgurations. Transportation Research Record: Journal of the Transportation Research Board, 2015. 2491: 12–21.

32.

Watts

D. J.

Strogatz

S. H.

Collective Dynamics of ‘Small-World’ Networks. Nature, Vol. 393, No. 6684, 1998, pp. 440–442.

33.

Pons

Latapy

Computing Communities in Large Networks using Random Walks. Journal of Graph Algorithms and Applications, Vol. 10, No. 2, 2006, pp. 191–218.

34.

Fortunato

Community Detection in Graphs. Physics Reports, Vol. 486, No. 3–5, 2010, pp. 75–174.

35.

Pons

Latapy

Computing Communities in Large Networks using Random Walks. Proc., Computer and Information Sciences -ISCIS 2005, Springer Berlin Heidelberg, Germany, 2005, pp. 284–293.

36.

Clauset

Newman

M. E.

Moore

Finding Community Structure in Very Large Networks. Physical Review E, Vol. 70, No. 6 Pt 2, 2004, p. 066111.

37.

Newman

M. E.

Girvan

Finding and Evaluating Community Structure in Networks. Physical Review E, Vol. 69, No. 2 Pt 2, 2004, p. 026113.

38.

Coifman

Improved Velocity Estimation using Single Loop Detectors. Transportation Research Part A: Policy and Practice, Vol. 35, 2001, pp. 863–880.

39.

Porta

Crucitti

Latora

The Network Analysis of Urban Streets: A Primal Approach. Environment and Planning B: Planning and Design, Vol. 33, No. 5, 2006, pp. 705–725.

40.

Ambühl

Loder

Menendez

Axhausen

K. W.

A Case Study of Zurich’s Two-Layered Perimeter Control. Proc., 7th Transport Research Arena (TRA 2018), Vienna, Austria, 2018.

41.

Chavent

Kuentz-Simonet

Labenne

Saracco

ClustGeo: An R Package for Herarchical Clustering with Spatial Constraints. Computational Statistics, Vol. 33, No. 4, 2018, pp. 1799–1822. https://doi.org/10.1007/s00180-018-0791-1.