💻 computer science

A Path Fitting Accuracy Improvement and Evaluation Method Based on Minimum Toll and Multi-dimensional Anomaly Detection Engine

This paper proposes a two-stage path fitting framework that integrates a "minimum toll" principle with a multi-dimensional anomaly detection engine to address gantry data issues in expressway tolling, achieving a 2.1% accuracy improvement and a 70% reduction in billing deviations while introducing a novel dual-indicator evaluation model to ensure result reliability.

Original authors: Jian Li, Yunfang Zhao, Ke Zhang, Xin Gao, Lexiang Mei, Xiaoyu Guo

Published 2026-07-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jian Li, Yunfang Zhao, Ke Zhang, Xin Gao, Lexiang Mei, Xiaoyu Guo

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a massive, real-life video game of "connect the dots," but the dots are toll booths on a highway, and the lines are the roads between them. In the world of intelligent transportation, this is the daily reality of figuring out exactly where a car has been. When you drive on a modern expressway, you don't pay a flat fee; you pay based on the specific path you took, calculated by a digital system that listens to your car's electronic tag as it passes under thousands of overhead "gantries" (those big metal arches with cameras and sensors). The goal is simple: if you drive from Point A to Point B, the computer should know your exact route and charge you the fair price.

However, the real world is messy. Sometimes a sensor glitches, a signal gets lost in a tunnel, or the weather interferes, causing the computer to miss a few "dots" in your journey. When the computer tries to guess the missing parts of your trip, it has to make a choice. If it guesses wrong, you might get a bill for a route you never took, or worse, you might get charged more than you should have. This is the problem of "path fitting": taking a broken, incomplete list of toll stops and reconstructing the true story of the drive. It's a high-stakes puzzle where accuracy means fairness, and a wrong guess can lead to angry drivers and confused billing departments.

The Paper's Mission: Fixing the Highway Puzzle

This paper tackles that messy puzzle with a clever, two-step strategy designed to make highway billing fairer and more accurate. The authors, working from China's Road Network Monitoring and Emergency Response Center, realized that previous methods were like trying to solve a maze by just picking the shortest path on a map. But in the real world of tolls, the "shortest" path isn't always the one a driver took, and the "cheapest" path isn't always the one the system should guess.

The researchers propose a new "two-stage" framework that acts like a smart detective.

Stage 1: The "Just Get It Connected" Phase
First, the system does a quick sweep to make sure the dots are connected. If the computer sees a gap between two toll booths where the car should have passed, it fills in the blanks using a basic map of the road network. Think of this as drawing a straight line between two points just to make sure the story makes sense physically. This stage ensures the car didn't magically teleport; it just gets a "good enough" route to start with.

Stage 2: The "Business Logic" Detective
This is where the magic happens. The authors introduce a "Multi-dimensional Anomaly Detection Engine." Imagine this engine as a super-vigilant traffic cop that looks at the "good enough" route and asks, "Wait a minute, does this actually make sense?"

The engine checks for six specific types of "silly mistakes" that happen in real life:

Head/Tail Noise: Sometimes a car gets picked up by a toll booth meant for the other direction right at the entrance or exit. The engine spots this and deletes the ghost signal.
Mid-Journey Noise: A car might accidentally trigger a ramp sensor it didn't take. The engine checks if the path makes sense and removes the extra stop.
Knots: Sometimes the timestamps get mixed up (like a video playing in the wrong order). The engine unties the knot and puts the stops in the right sequence.
Overspeeding: If the computer's guess requires the car to drive at 300 km/h to make the time work, the engine knows that's impossible and rejects that path.
Illegal U-Turns: If the data suggests a car drove halfway down a highway, did a U-turn in the middle of the road, and came back, the engine flags this as an illegal maneuver and fixes the path to the actual road layout.
Secondary Trips: If a car stops for a long time (like a 3-hour lunch break) and the data looks like one long trip, the engine splits it into two separate trips.

Once the engine cleans up the noise, the system applies a golden rule: Minimum Toll. Instead of guessing the shortest distance, it calculates the path that would result in the lowest possible fee for the driver, assuming the driver took the most logical route. This ensures that if there are multiple ways to fill in the gaps, the system picks the one that is cheapest for the user, which is the fair business standard.

The "Trust Score"
The paper also introduces a new way to measure how sure the computer is about its answer. They created a "Dual-Indicator Quality Evaluation Model." Think of this as a "Confidence Meter."

Confidence: How sure is the system that this is the right path?
Raw En-Route Ratio: How much of the path was actually seen by sensors versus guessed?

The authors found that these scores are incredibly useful. They discovered a strong link (a Pearson coefficient of -0.87) between the confidence score and the actual error: if the confidence meter is low, the bill is likely wrong. If the meter is high, the bill is almost certainly correct. This gives toll operators a way to say, "We are 95% sure this is your route," which helps settle disputes quickly.

What They Found
The team tested their new system using over 5 million real travel records from 2025. The results were impressive. Compared to the old "shortest path" method, their new two-stage framework improved the accuracy of guessing the right path by 24.5 percentage points (reaching a total accuracy of 96.8%). When compared to their own "baseline" method (which only handles the first stage), the improvement was 2.1 percentage points. More importantly, it slashed the "billing deviation rate" (the number of times the bill was wrong by more than 1 yuan) by nearly 70%, dropping it from 18.5% down to just 2.1%.

The system is also fast, taking about 12 milliseconds to process a trip (with the baseline stage taking 8ms and the traditional method taking 15ms), which is quick enough for real-time billing at the exit gate.

What They Didn't Do (Yet)
The paper is very clear about its limits. This solution was tested primarily on passenger cars. The authors note that trucks have different rules (like different toll rates for weight or bridge fees), so the system would need to be tweaked to handle those heavy vehicles. They also mention that while they used historical data to build their models, they haven't yet integrated real-time traffic jams into the equation, which could be a future upgrade.

The Bottom Line
This paper doesn't just suggest a better way to guess; it provides a tested, two-step engine that cleans up messy data, applies the "cheapest fair path" rule, and tells you how much you can trust the result. By turning a chaotic stream of sensor data into a clean, fair, and explainable bill, the authors have built a bridge between complex math and the everyday driver who just wants to know they aren't being overcharged.

Technical Summary: A Path Fitting Accuracy Improvement and Evaluation Method Based on Minimum Toll and Multi-dimensional Anomaly Detection Engine

1. Problem Statement

The widespread adoption of national expressway "one network" operations, Electronic Toll Collection (ETC), and free-flow tolling has shifted billing from rough shortest-path estimations to precise billing based on actual driving trajectories. However, the core challenge lies in reconstructing these complete trajectories (path fitting) from sparse toll gantry transaction sequences.

Current systems face significant hurdles due to data quality issues inherent in real-world environments, including:

Data Anomalies: Missing records, duplicate transactions, timestamp disorder, and signal interference caused by equipment failures or severe weather.
Business Rule Misalignment: Traditional path-fitting algorithms often optimize for "shortest distance" or "fewest gantries," which contradicts the fundamental business principle of expressway tolling: charging the user the minimum feasible fee for their actual travel path.
Lack of Evaluation Standards: Existing methods often produce "black box" results without quantitative indicators for the reliability or confidence of the fitted path, leading to disputes over "same road, different tolls" and a lack of explainability for operators.

2. Methodology

The paper proposes an innovative two-stage path fitting framework coupled with a dual-indicator quality evaluation model. The process is divided into offline preprocessing and online fitting.

A. Offline Preprocessing

Graph Construction: A whole-network directed graph is constructed where toll gantries are nodes and connectivity relations are edges.
Minimum Toll Matrix: A "whole-network minimum toll matrix" is precomputed using an improved Dijkstra algorithm. This allows for $O(1)$ instant queries of the minimum accumulated toll between any two nodes, reducing online search complexity.

B. Online Fitting Stage I: Baseline Fitting (Connectivity Guarantee)
The goal is to generate a spatially continuous and temporally reasonable path ( $P_{baseline}$ ) despite data gaps.

Sequence Cleaning: The raw sequence undergoes parallel cleaning for duplicate records, reverse transactions (using hop-count logic), and spatio-temporal anomalies (using speed thresholds).
Path Filling: For breakpoints, the system uses a hybrid strategy: Depth-First Search (DFS) for short gaps ( $n \leq 17$ ) and the A* algorithm for longer gaps to ensure connectivity.

C. Online Fitting Stage II: Optimized Fitting (Business Rule Optimization)
This stage refines $P_{baseline}$ by integrating business rules and a Parallelized Multi-dimensional Anomaly Detection Engine. Six specific anomaly types are modeled mathematically and detected in parallel:

Head/Tail Noise Points: Filtering reverse gantry captures near entrance/exit stations using speed and connectivity logic.
Mid-Journey Noise Points: Identifying hub ramp misidentifications by comparing hop counts between predecessor, suspect, and successor nodes.
Knotted Path Correction: Correcting timestamp inversions caused by clock errors by reordering nodes based on physical connectivity.
Overspeed Path Verification: Detecting noise points where calculated speeds between nodes exceed physical limits.
Illegal U-turn Identification: Detecting illegal U-turns by checking if start/end points are on the same road section but in opposite directions, combined with overspeed verification.
Secondary Trip Identification: Splitting mixed trips caused by long time intervals where the calculated average speed is unrealistically low.

D. Final Path Generation
After deep cleaning, the system queries the precomputed minimum toll matrix to generate candidate paths sorted by cost. It selects the first candidate path that satisfies physical speed constraints ( $V_{req} \leq V_{limit}$ ), ensuring the "minimum toll" principle is met without violating physics. Timestamps for filled nodes are reconstructed via linear interpolation based on mileage.

E. Dual-Indicator Quality Evaluation Model
To address the lack of reliability metrics, the paper introduces two quantitative indicators:

Confidence: Measures the certainty of the path selection based on the proportion of original data and uniquely determined nodes versus ambiguous paths.
Raw En-Route Ratio: Characterizes the dependence of the result on the original observed data versus speculative filling.
The average of these two indicators provides a "Reliability" score.

3. Key Contributions

The paper claims four primary contributions:

Two-Stage Methodology: A decoupled approach separating "connectivity guarantee" (Stage I) from "business rule optimization" (Stage II), ensuring the transition from geometric feasibility to business optimality (minimum toll).
Parallelized Anomaly Detection Engine: The first mathematical modeling and parallel detection of six complex, coupled anomaly types specific to expressway tolling, significantly improving robustness.
Dual-Indicator Evaluation Model: The introduction of computable "Confidence" and "Raw En-Route Ratio" metrics, providing the first quantitative basis for the reliability and interpretability of path fitting results.
Comprehensive Verification: Validation using massive real-world ETC transaction data, demonstrating significant improvements in accuracy and billing fairness.

4. Experimental Results

Experiments were conducted using over 5 million cross-province travel records from 2025, with a manually labeled test set of 1,000 records containing missing gantries. The proposed method ("Ours") was compared against the Shortest Path (SP) method and the Baseline (BL) method (Stage I only).

Fitting Accuracy: The proposed method achieved 96.8% accuracy, a 24.5 percentage point improvement over SP and a 12.1 percentage point improvement over BL.
Billing Deviation Rate: The rate of records where the toll difference exceeded 1 yuan dropped from 18.5% (SP) and 8.2% (BL) to 2.1% (Ours), representing a nearly 70% reduction compared to traditional methods.
Processing Efficiency: The average processing time was 12 ms, which is slightly higher than BL (8 ms) but well within real-time billing requirements and faster than SP (15 ms).
Evaluation Model Validity: The "Confidence" indicator showed a strong negative correlation (Pearson coefficient = -0.87) with actual fitting errors, confirming that lower confidence scores reliably predict higher error rates.
Multi-dimensional Performance: A five-dimensional radar chart (Accuracy, Stability, Anti-interference, Efficiency, Interpretability) showed the proposed method outperforming others in all categories, particularly in "Anti-interference" (95/100) and "Interpretability" (88/100).

5. Significance and Claims

The paper asserts that this framework provides a reliable theoretical and practical solution for realizing accurate and fair expressway network tolling. By systematically embedding the "minimum toll" business principle into the algorithmic core and introducing a parallelized anomaly detection engine, the method resolves the disconnect between technical optimization and business objectives.

Furthermore, the introduction of the dual-indicator evaluation model addresses the "black box" nature of previous systems, offering operators a transparent, quantitative basis for adjudicating tolling disputes. The authors conclude that this work has significant application value for building accurate, fair, and transparent tolling systems, with future work planned to extend the framework to truck billing and integrate real-time traffic status.