Fast algorithm for large-scale time-dependent shortest path problem

大规模瞬态最短路径问题的快速算法

• 批准号: 23700018
• 负责人: ZHAO Liang
• 金额: $ 2.16万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2012
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23700018/
• 关键词: 組み合わせ最適化; ALTアルゴリズム; A*アルゴリズム; 大規模最短路計算; 時間依存最短路問題; Node Early-Fixing

We developed a new time-dependent A* algorithm framework for finding a shortest path in a large-scale time-dependent network. In particular, based on the conventional ALT method that uses landmarks, we developed a fast A* algorithm for finding an optimal solution with dynamical updating of the set of the effective landmarks. This algorithm can be applied to any kind of instances since it does not dependent on the graph structure of the network.

我们开发了一种新的基于时间的a *算法框架，用于在大规模时间相关网络中寻找最短路径。特别地，在传统的使用地标的ALT方法的基础上，我们开发了一种快速的a *算法，通过动态更新有效地标集来寻找最优解。该算法可以应用于任何类型的实例，因为它不依赖于网络的图结构。

项目成果

Node Early-Fixing: A Practical Speedup Technique for A* Algorithms

节点早期修复：A* 算法的实用加速技术

• 发表时间: 2013
• 期刊: GSTF Intl. J. Mathematics, Statistics and Operations Research (JMSOR)
• 作者: Liang Zhao;Mingji Gao
• 通讯作者: Mingji Gao

Approximation algorithms for the L-distance vertex cover problem

L距离顶点覆盖问题的近似算法

• 发表时间: 2012
• 期刊: Proc. Third International Conference on Theoretical and Mathematical Foundations of Computer Science (ICTMF 2012), Bali, Indonesia
• 作者: Qiaoyun Chen;Liang Zhao
• 通讯作者: Liang Zhao

Some practical speed-up techniques for A* algorithms

A*算法的一些实用加速技巧

• 发表时间: 2011
• 作者: Mingji Gao;Liang Zhao
• 通讯作者: Liang Zhao