论文标题
快速一对多的多标准最短路径搜索
Fast One-to-Many Multicriteria Shortest Path Search
论文作者
论文摘要
本文介绍了一种新颖的算法组合，旨在最短的一到多个路径搜索。预处理算法通过构建较小的封面图排除了无关的顶点。修改版的多标记标签设定算法在封面图上运行，并采用降低降低技术来进行SWIFTER主导检查。尽管该方法本身保持解决方案的最佳性，但它还能够纳入现有的启发式方法以进行进一步加速。已提出的算法已根据多个相关性的标准组合进行了测试。结果表明，与香草多标记标签相比，在简单的标准组合中，引入的方法至少可以在简单的标准组合中加速6次，而在硬实例上最多可加速6次。图预处理还将查询的内存要求降低了13次。
This paper introduces a novel algorithm combination designed for fast one-to-many multicriteria shortest path search. A preprocessing algorithm excludes irrelevant vertices by building a smaller cover graph. A modified version of multicriteria label-setting algorithm operates on the cover graph and employs a dimensionality reduction technique for swifter domination checks. While the method itself maintains solution optimality, it is able to additionally incorporate existing heuristics for further speedups. The proposed algorithm has been tested on multiple criteria combinations of varying correlation. The results show the introduced approach provides a speedup of at least 6 times on simple criteria combinations and up to 60 times on hard instances compared to vanilla multicriteria label-setting. Graph preprocessing also decreases memory requirements of queries by up to 13 times.
