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

Ali Zockaie, Meead Saberi, Ramin Saedi

Research output: Research - peer-reviewArticle

Abstract

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.

LanguageEnglish (US)
Pages245-262
Number of pages18
JournalTransportation Research Part C: Emerging Technologies
Volume86
DOIs
StatePublished - Jan 1 2018

Profile

Heterogeneous networks
Resource allocation
Trajectories
Sampling
resources
traffic
demand
Traffic control
Simulated annealing
Availability
Detectors
Costs
traffic control
city center
asymmetry
pricing
heuristics
budget
simulation
methodology

Keywords

  • Heterogeneous networks
  • Macroscopic Fundamental Diagram (MFD)
  • Network Fundamental Diagram (NFD)
  • Probe trajectories

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Automotive Engineering
  • Transportation
  • Computer Science Applications

Cite this

@article{d1bd85faad1840c2b7466b5dccebb619,
title = "A resource allocation problem to estimate network fundamental diagram in heterogeneous networks: Optimal locating of fixed measurement points and sampling of probe trajectories",
abstract = "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.",
keywords = "Heterogeneous networks, Macroscopic Fundamental Diagram (MFD), Network Fundamental Diagram (NFD), Probe trajectories",
author = "Ali Zockaie and Meead Saberi and Ramin Saedi",
year = "2018",
month = "1",
doi = "10.1016/j.trc.2017.11.017",
volume = "86",
pages = "245--262",
journal = "Transportation Research Part C: Emerging Technologies",
issn = "0968-090X",
publisher = "Elsevier Limited",

}

TY - JOUR

T1 - A resource allocation problem to estimate network fundamental diagram in heterogeneous networks

T2 - Transportation Research Part C: Emerging Technologies

AU - Zockaie,Ali

AU - Saberi,Meead

AU - Saedi,Ramin

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Heterogeneous networks

KW - Macroscopic Fundamental Diagram (MFD)

KW - Network Fundamental Diagram (NFD)

KW - Probe trajectories

UR - http://www.scopus.com/inward/record.url?scp=85035140832&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85035140832&partnerID=8YFLogxK

U2 - 10.1016/j.trc.2017.11.017

DO - 10.1016/j.trc.2017.11.017

M3 - Article

VL - 86

SP - 245

EP - 262

JO - Transportation Research Part C: Emerging Technologies

JF - Transportation Research Part C: Emerging Technologies

SN - 0968-090X

ER -