大规模图上具有约束的多起点路径规划算法

摘要：

路径规划查询是图数据上的一个基本问题,在众多的领域都有重要的应用价值.通常在实际问题中查询的路径是具有约束的,例如在外卖配送和共享出行问题中路径具有节点约束,其路径需要满足节点之间的先后关系约束.目前对于具有节点约束的路径查询问题,大多数的工作都在研究单起点的节点约束路径查询,但很难拓展到多起点节点约束问题中.因为具有节点约束的多起点路径查询问题是NP-hard的,所以该问题的大多数已有方法是使用贪心增量处理,但对于处理静态规则集拓展性不足.因此,提出了基于子路径的启发式算法和基于约束集拓展的精确算法,并在真实数据集上验证了算法的有效性.实验结果表明,启发式算法能够给出问题的精确解,而启发式算法能快速给出较好的近似解.

关键词：图数据、路径查询、最优化问题、启发式算法

所属期刊栏目：59

分类号：TP311.1(计算技术、计算机技术)

资助基金：国家重点实验室基金A32003

在线出版日期：2023-03-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：283-290