A resource allocation problem to estimate network fundamental diagram in heterogeneous networks: Optimal locating of fixed measurement points and sampling of probe trajectories

Network Fundamental Diagram (NFD) or Macroscopic Fundamental Diagram (MFD) represents dynamics of traffic flow at the network level. It is used to design various network-wide traffic control and pricing strategies to improve mobility and mitigate congestion. NFD is well defined when congestion distribution in the network is homogenous. However, in real world networks traffic is often heterogeneously distributed and initiated from an asymmetric and time-varying origin-destination (OD) demand matrix. In this paper, we formulate a resource allocation problem to find the optimal location of fixed measurement points and optimal sampling of probe trajectories to estimate NFD accounting for limited resources for data collection, network traffic heterogeneity and asymmetry in OD demand in a real-world network. Data from probe trajectories are used to estimate space-mean speed while data from fixed detectors are used to estimate traffic flow. Thus, the proposed model does not require an aggregate penetration rate of probe vehicles to be known a priori, which is one of the main contributions of this study. The proposed model is a mixed integer problem with non-linear constraints known to be NP-hard. A heuristic solution algorithm (Simulated Annealing) is implemented to solve the problem. Using a calibrated simulation-based dynamic traffic assignment model of Chicago downtown network, we present successful application of the proposed model and solution algorithm to estimate NFD. The results demonstrate sensitivity of the NFD estimation accuracy to the available budget, namely number of fixed measurement points and probe trajectories. We show that for a fixed proportion of OD trajectories, the increase in the proportion of fixed detection points increases the accuracy of NFD estimation as expected. However, when the proportion of fixed detection points is set to be constant, the increase in the proportion of OD trajectories does not necessarily improve the estimated NFD. Results hold true when varying demand is used to emulate variation in day-to-day traffic patterns. The robustness of the proposed methodology to the initial solution and trajectory availability for each OD pair is demonstrated in the numerical results section. We also found that a uniform distribution of selected links and ODs for NFD estimation across the network may not necessarily result in an optimal solution. Instead, distribution of links and OD pairs should follow the same distribution of links and OD pairs in the network.