交通运输系统工程与信息 ›› 2026, Vol. 26 ›› Issue (2): 280-288.DOI: 10.16097/j.cnki.1009-6744.2026.02.026

• 系统工程理论与方法 • 上一篇    下一篇

兼顾准时性的动态不确定道路网络可靠路径优化模型

王子吉安,黄爱玲* ,杨柳   

  1. 北京交通大学,交通运输学院,北京100044
  • 收稿日期:2025-11-24 修回日期:2026-01-11 接受日期:2026-01-15 出版日期:2026-04-25 发布日期:2026-04-21
  • 作者简介:王子吉安(1996—),男,北京人,博士生。
  • 基金资助:
    中央高校基本科研业务费专项资金 (2025JBZX038); 国家自然科学基金面上项目 (52472336)。

Reliable Route Optimization Model for Dynamic and Uncertain Road Networks Considering Punctuality

WANG Ziji'an, HUANG Ailing*, YANG Liu   

  1. School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China
  • Received:2025-11-24 Revised:2026-01-11 Accepted:2026-01-15 Online:2026-04-25 Published:2026-04-21
  • Supported by:
    The Fundamental Research Funds for the Central Universities (2025JBZX038); National Natural Science Foundation of China (52472336)。

摘要: 道路网络的动态性与不确定性,使得路径规划方案难以兼顾准时性与最优性,同时增加了大规模路网中问题求解的复杂度。为此,本文提出一种兼顾准时率要求的动态不确定路网可靠路径优化模型,在满足准时率需求的同时尽可能缩短行程时间。基于鲁棒优化范式,构建了时间依赖与不确定性下的可调节鲁棒最短路模型,可适应不同准时率需求下的可靠路径求解。为支持用户直观地依据准时率偏好生成出行方案,本文设计了相应的生成算法,通过融合区间搜索与蒙特卡洛方法,建立调节因子与准时率之间的显式关联,从而无需用户直接设定调节因子。在可靠路径求解环节,结合时间依赖Dijkstra算法设计了高效的子算法,降低求解复杂度。在多个真实城市路网中进行模型与算法的性能验证。实验结果表明,所提出的生成算法能够输出符合用户准时率预期的出行方案;在保证100%准时率时,相比鲁棒优化模型,行程时间减少了10.6%。同时,可靠路径求解子算法较为高效,在大规模路网中可达毫秒至秒级,能够支持在线或离线环境下的大规模路径规划任务。

关键词: 城市交通, 可靠路径优化, 鲁棒优化, 道路网络, 动态不确定性

Abstract: The dynamic and uncertain nature of road networks poses significant challenges for path planning schemes to simultaneously achieve punctuality and optimality, while also escalating the computational complexity when solving such problems in large-scale networks. To tackle this issue, this paper proposes a reliable route optimization model for dynamic and uncertain road networks that incorporates punctuality requirements, striving to minimize travel time while fulfilling specified on time arrival rates. Based on the robust optimization paradigm, an adjustable robust shortest path model is developed for time dependent and uncertain networks, which considers the adaptability to various punctuality demands for reliable route identification. A corresponding plan generation algorithm is designed to empower users to intuitively generate travel plans according to their punctuality preferences. By integrating interval search with Monte Carlo simulation, this algorithm establishes an explicit mapping between an adjustment parameter and the punctuality rate, thereby eliminating the need for users to set the parameter directly. For the reliable route solving subroutine, an efficient sub-algorithm incorporating the time-dependent Dijkstra method is developed to reduce computational complexity. The model and algorithms are validated through performance tests on multiple real-world urban road networks. Experimental results demonstrate that the proposed generation algorithm can output travel plans that align with users' punctuality expectations. When guaranteeing a 100% punctuality rate, the travel time is reduced by 10.6% compared to conventional robust optimization models. Moreover, the reliable route solving sub-algorithm proves to be highly efficient, achieving computation times ranging from milliseconds to seconds on large-scale networks, which enables its support for both online and offline large-scale route planning tasks.

Key words: urban transportation, reliable route optimization, robust optimization, road network, dynamic uncertainty

中图分类号: