Real-time multiple-objective path search for in-vehicle route guidance systems

Blue, Victor J.; Adler, Jeffrey L.; List, George F. · 1997 · ROSA P / United States. Joint Program Office for Intelligent Transportation Systems

archive: archived pipeline: cataloged verified

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

Summary

This paper addresses the limitations of existing in-vehicle route guidance systems (IVRGS), which typically rely on single-objective path searches (e.g., minimum time or distance) using static, free-flow data. The authors argue that driver route choice is influenced by multiple, often conflicting objectives, such as travel time and convenience. To model this behavior more realistically, the study introduces a bi-objective path search algorithm that optimizes for "trip quality," defined as a weighted trade-off between minimizing travel time and minimizing "trip complexity." Trip complexity is quantified as the sum of turning movement costs, assigned empirically based on turn angles and directions (e.g., left turns incur higher costs than right turns). This metric serves as a surrogate for driver convenience and safety, particularly for those who prefer direct routes or wish to avoid complex maneuvers. The authors develop a multiple-objective shortest path (MOSP) algorithm that identifies nondominated solutions by storing partial paths rather than assigning single labels to nodes. The algorithm uses a generalized cost function, $Q = \alpha T + \gamma(1-\alpha)C$, where $\alpha$ represents the driver’s preference weight for time versus complexity, and $\gamma$ is a scaling factor. To evaluate the algorithm, the researchers conducted simulation experiments on a test network under varying peak demand levels (800 to 1,895 vehicles per hour). The study compared two routing strategies: pretrip routing (PR), where the path is fixed at the start, and dynamic routing (DR), where the path is reevaluated at each node based on real-time conditions. The simulations assumed full market penetration of IVRGS with a homogeneous user class to isolate the effects of the routing strategies. The results demonstrate that dynamic routing significantly outperforms pretrip routing under high congestion conditions. Specifically, DR provided substantial network flow improvements over PR for peak volumes exceeding 1,500 vehicles per hour, as DR could avoid congestion-induced bottlenecks that PR could not. The analysis of trade-off surfaces revealed that at high volumes, prioritizing complexity (low $\alpha$) often resulted in large increases in travel time with minimal gains in complexity reduction, indicating a steep trade-off cost. Conversely, at lower volumes, PR and DR performance was nearly identical. The study found that trip time sensitivity to the trade-off parameter $\alpha$ increased with demand, while complexity remained relatively stable across different demand levels for a given $\alpha$. The significance of this work lies in its demonstration that multiple-objective routing can improve both individual trip quality and overall network performance by accommodating diverse driver preferences. The findings suggest that dynamic rerouting is essential for managing congestion effectively when drivers prioritize non-time objectives. The authors conclude that while the current model uses deterministic complexity costs, future research should incorporate probabilistic distributions for turning costs and examine heterogeneous user populations with varying market penetration rates. This approach provides a framework for developing more responsive and behaviorally accurate IVRGS that balance efficiency with driver comfort and safety.

Key finding

Dynamic routing demonstrated significant advantages over pretrip routing in network performance for all alpha values above a peak volume of 1,500 vehicles per hour.

Methodology

modeling

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. Discovered via bulk_ingest_rosap on 2026-05-23 (6 acquisition events logged).

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

Topics

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

• nav systems