2023，59（6）图作为一种重要的数据模型，常常用来刻画真实世界中两个实体之间的关系。图数据管理中，最短路径规划是一类基本且重要的研究问题，其在现实世界中具有广泛的应用，例如：在道路交通网中，最短路径规划可为用户提供起点和终点之间的最优路径；在社交网络网络中，最短路径规划反映了两个指定用户之间发生最直接联系的方式。现实应用中的路径规划往往并非简单的，而是具有约束的。例如，在交通网络图中，用户需要从甲地到达乙地，且要求在到达乙地的过程中经过v1,v2,⋯,vn地，大规模图上具有约束的多起点路径规划算法普林发1，2，3，杨雅君1，2，3，王鑫21.人民网传播内容认知国家重点实验室，北京1007332.天津大学智能与计算学部，天津3003503.天津大学国际工程师学院，天津300350摘要：路径规划查询是图数据上的一个基本问题，在众多的领域都有重要的应用价值。通常在实际问题中查询的路径是具有约束的，例如在外卖配送和共享出行问题中路径具有节点约束，其路径需要满足节点之间的先后关系约束。目前对于具有节点约束的路径查询问题，大多数的工作都在研究单起点的节点约束路径查询，但很难拓展到多起点节点约束问题中。因为具有节点约束的多起点路径查询问题是NP-hard的，所以该问题的大多数已有方法是使用贪心增量处理，但对于处理静态规则集拓展性不足。因此，提出了基于子路径的启发式算法和基于约束集拓展的精确算法，并在真实数据集上验证了算法的有效性。实验结果表明，启发式算法能够给出问题的精确解，而启发式算法能快速给出较好的近似解。关键词：图数据；路径查询；最优化问题；启发式算法文献标志码：A中图分类号：TP311.1doi：10.3778/j.issn.1002-8331.2109-0496ConstrainedMulti-StartPathPlanningAlgorithmonLarge-ScaleGraphsPULinfa1，2，3,YANGYajun1，2，3,WANGXin21.StateKeyLaboratoryofCommunicationContentCognition,Beijing100733,China2.CollegeofIntelligenceandComputing,TianjinUniversity,Tianjin300350,China3.TianjinInternationalEngineeringInstitute,TianjinUniversity,Tianjin300350,ChinaAbstract：Pathplanningqueryisabasicproblemongraphdata,whichhasimportantapplicationvalueinmanyfields.Usually,thepathqueriedinactualproblemsisconstrained.Forexample,intheproblemsoffooddeliveryandsharedtravel,thepathhasnodeconstraints,andthepathneedstomeettheconstraintsofthesequencerela...
