2TD Path-Planner: Towards a More Realistic Path Planning System over Two-Fold Time-Dependent Road Networks [Application Notes]

Chao Chen, Liping Gao, Xuefeng Xie, Liang Feng, Yasha WangIEEE Comput. Intell. Mag 2021 · OpenReview

Abstract

Planning driving routes is a common yet challenging task. Previous solutions that often suggest the shortest or time-dependent fastest paths for drivers are incompatible with the diversity of user requirements. Recent years are witnessing an increasing need for utility gained along the driving path, and more advanced path-planners are developed correspondingly, such as the safest and the most beautiful paths. Similar to the travel time on the edge, the utility score actually changes with time as well. In this paper, targeting a more realistic path planning system, we allow both time cost and utility on the edge to vary from time to time. Over such a two-fold time-dependent road network, we aim to discover the optimal driving path for the given user query. To address this NP-hard problem, we propose an approximated algorithm called 2TD Path-Planner, which mainly consists of three components: edge reachability computing, chromosome encoding, and chromosome decoding.

Introduction

Most modern navigation systems prioritize a single metric: travel time. However, human preferences are far more nuanced. A tourist may seek the most scenic route, while a security patrol might prioritize high-risk areas to maximize crime prevention.

The core challenge lies in the dynamic nature of urban environments. While traffic-induced travel time variance is well-studied, the "utility" of a road (e.g., its beauty or safety) is also time-dependent. A coastal road loses its scenic utility after sunset, and a neighborhood's risk profile fluctuates throughout the night. This creates a "two-fold" time-dependency (2TD) problem. Mathematically, this is a variant of the Arc Orienteering Problem (AOP), which is NP-hard and computationally expensive when both cost and utility are dynamic.

The 2TD Path-Planner Architecture

To solve this, the 2TD Path-Planner employs a heuristic-driven evolutionary algorithm designed for real-time performance. The system architecture is divided into three primary stages that transform a user query into an optimal path.

The 2TD Path-Planner system architecture, illustrating the flow from user query to optimal path via reachability computing and evolutionary encoding.

1. Edge Reachability Computing

To prevent the algorithm from exploring impossible routes, the system pre-calculates "timezones" for utility edges. By classifying edges based on whether they can be reached within the user's time budget, the search space is drastically pruned.

Edges are categorized into three zones:

  • Reachable Timezone: The edge can be traversed, and the destination can still be reached.
  • Unreachable Timezone: The edge is impossible to reach or would prevent reaching the destination within the budget.
  • Critical Timezone: A sensitive window where the exact arrival time determines if the destination remains reachable.
Classification of timezones for an edge, showing how reachable, critical, and unreachable windows are determined based on minimum and average travel times.

2. Chromosome Encoding

The system represents potential paths as "chromosomes"—sequences of high-utility edges. To ensure a diverse and high-quality population of paths, it uses four selection heuristics:

  • Number Priority: Targets the nearest utility edges to maximize the total number of edges visited.
  • Value Priority: Selects edges with the highest average utility scores.
  • Sensitivity Priority: Focuses on edges where utility fluctuates rapidly, capturing high-value windows.
  • Random Priority: Maintains genetic diversity to avoid local optima.

3. Chromosome Decoding

Because the selected utility edges may not be adjacent, the decoding stage "fills the gaps." It uses time-dependent shortest-path algorithms to connect the edges into a continuous, valid route that respects the user's total time budget.

Experimental Evaluation

The researchers evaluated the 2TD Path-Planner using synthetic data and four real-world road networks: San Francisco (scenic utility), New York City (risk utility), and the complex urban layouts of Chengdu and Chongqing.

Key Results

  • Efficiency: The 2TD Path-Planner achieved massive speedups over existing baselines like the Memetic Algorithm (MA). In many scenarios, it provided a response within 10 milliseconds, whereas baselines often took seconds or minutes.
  • Utility Maximization: Across varying departure times and time budgets, the system consistently found paths with higher total utility scores than state-of-the-art alternatives.
  • Robustness: The system proved effective even in Chongqing, a city known for its irregular, mountainous road network, demonstrating its applicability to diverse urban geographies.

Conclusion and Future Work

The 2TD Path-Planner represents a significant step toward realistic navigation by treating utility as a dynamic function. By identifying "unreachable" timezones early, it avoids the combinatorial explosion typical of NP-hard pathfinding. Future work will explore multi-objective optimization—such as finding routes that are simultaneously safe and scenic—and real-world deployment to gather qualitative user feedback on suggested routes.

Summary updated

Abstract

Planning driving routes is a common yet challenging task. Previous solutions that often suggest the shortest or time-dependent fastest paths for drivers are incompatible with the diversity of user requirements. Recent years are witnessing an increasing need of utility gained along the driving path and more advanced pathplanners are developed correspondingly, such as the safest and the most beautiful paths. Similar to the travel time on the edge, the utility score actually changes with the time as well. In this paper, targeting a more realistic path planning system, we allow both time cost and utility on the edge to vary from time to time. Over such two-fold time-dependent road network, we aim to discover the optimal driving path for the given user query. To address this NP-hard problem, we propose an approximated algorithm called 2TD Path-Planner, which mainly consists of three components, i.e., edge reachability computing, chromosome encoding, and chromosome decoding.
BibTeX
@inproceedings{chen2021td,
  author = {Chao Chen and Liping Gao and Xuefeng Xie and Liang Feng and Yasha Wang},
  title = {{2TD Path-Planner: Towards a More Realistic Path Planning System over Two-Fold Time-Dependent Road Networks [Application Notes]}},
  booktitle = {IEEE Comput. Intell. Mag},
  year = {2021},
  url = {https://openreview.net/forum?id=xZpklRRz63},
}
Figure