Route estimation based on network flow maximization

Behrisch, Michael; Erdmann, Jakob · 2018 · Crossref

DOI: 10.29007/rjj7

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the static traffic assignment problem, specifically the challenge of estimating vehicle routes in a street network based solely on observed traffic counts. While dynamic traffic assignment is widely studied, the authors focus on finding a list of routes that approximates measured edge flows as closely as possible, treating traffic counts as hard constraints. The motivation is to provide a robust method for microsimulation input that can handle incomplete data, a common issue in real-world scenarios where detector coverage is sparse. The proposed solution, named FlowMax, utilizes network flow maximization techniques. The algorithm operates in two distinct phases. First, it determines an optimal weight function for the network edges that respects flow conservation (Kirchhoff’s law) and maximizes the total flow without exceeding the measured traffic counts on any edge. This is achieved by modeling the street network as a directed graph and applying maximum flow algorithms, such as Ford-Fulkerson, with traffic counts serving as edge capacities. Second, the algorithm constructs specific routes from this weight function. It transforms the weighted graph into an unweighted multigraph and identifies an Euler tour, which is then split into individual routes connecting source and sink vertices. This separation allows for the use of highly optimized flow algorithms and facilitates handling missing data by assigning infinite capacity to edges without measurements. The authors evaluate the algorithm using real-world data from a highway network in Munich (A9, A92, and A99), utilizing traffic counts from 282 induction loop detectors. Performance is measured using the GEH statistic, which balances absolute and relative errors between estimated and measured flows. The study compares FlowMax against an existing tool, dfrouter, under conditions of varying data completeness. Results indicate that FlowMax performs comparably or better when data is complete or when entire cross-sections are missing. However, FlowMax is more sensitive to partial data loss (e.g., missing single-lane detectors) because it treats counts as strict upper bounds, whereas dfrouter uses them for proportional adjustments. Despite this sensitivity, FlowMax demonstrated the ability to achieve good approximation quality (GEH < 5) with only 40% of the input data, significantly outperforming dfrouter in low-data scenarios. The significance of this work lies in providing a provably optimal method for route estimation that requires no origin-destination matrices or dynamic behavioral models. By leveraging network flow theory, the algorithm offers a computationally efficient approach that is robust to missing data, making it suitable for networks with sparse detector coverage. The method is implemented as a prototype in the SUMO simulation software, offering a new tool for traffic simulation calibration and route estimation that separates flow approximation from route construction, allowing for flexible optimization strategies.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• exposure measurement