买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网获悉合肥工业大学申请的专利一种考虑实时路况的城市K条最短路径获取方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN117523890B 。

龙图腾网通过国家知识产权局官网在2026-05-05发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202311582995.2，技术领域涉及：G08G1/0968；该发明授权一种考虑实时路况的城市K条最短路径获取方法是由丁建勋;单云晗;段睿;杨贝诺;陈语;黄军鹏;王予悦;王华;龙建成设计研发完成，并于2023-11-24向国家知识产权局提交的专利申请。

本一种考虑实时路况的城市K条最短路径获取方法在说明书摘要公布了：本发明公开了一种考虑实时路况的城市K条最短路径获取方法，包括：1.由起始时刻路况信息构建城市路网；2.定义参数及初始化；3.搜索当前时间从起点交叉口节点到终点交叉口节点的第k条最短路径；4.搜索当前时间从起点交叉口节点到终点交叉口节点的第k+1条最短路径；5.依据实时路况，获取更新路况后的下一时间从起点交叉口节点到终点交叉口节点的K条最短路径。本发明能在提高计算效率的同时得到更加贴合实际交通状况的K条最优出行路径，从而保障社会交通的稳定高效运行。

本发明授权一种考虑实时路况的城市K条最短路径获取方法在权利要求书中公布了：1.一种考虑实时路况的城市K条最短路径获取方法，其特征在于，是按如下步骤进行： 步骤1：构建城市路网； 获取实时道路网络数据并得到城市路网，表示交叉口节点集合，且，表示第个交叉口节点，，为所述城市路网中的交叉口节点总数，表示交叉口节点之间的路段集合，且，表示第个交叉口节点到第个交叉口节点之间的有向路段，表示交叉口节点之间路段的行车时间权重集合，，为有向路段的行车时间权重，若第个交叉口节点到第个交叉口节点之间存在有向路段，则第个交叉口节点为第个交叉口节点的后继交叉口节点，记为，第个交叉口节点为第个交叉口节点的前驱交叉口节点，记为，且，若第个交叉口节点到第个交叉口节点之间不存在有向路段，则令；令表示第个交叉口节点的前驱交叉口节点集合，令表示第个交叉口节点的后继交叉口节点集合； 步骤2：定义参数及初始化； 设置起点交叉口节点为，终点交叉口节点为，且；令表示从起点交叉口节点到终点交叉口节点的最短路径数量；令表示从起点交叉口节点到第个交叉口节点的可行路径数量，且； 步骤2.1：定义可行路径的相关属性； 令表示从起点交叉口到第个交叉口节点的第条可行路径的行车时间，且； 令表示从起点交叉口经过长度为的可行路径到达第个交叉口节点的前驱交叉口节点后，再从前驱交叉口节点到第个交叉口节点的总行车时间，其中，表示从起点交叉口到前驱交叉口节点的第条可行路径的行车时间，且，表示从起点交叉口节点到交叉口节点的可行路径数量，且，当为起点交叉口节点，即时，令； 令表示时间最小值，且=；其中，表示从起点交叉口到第个交叉口节点的第条可行路径的行车时间； 令表示从起点交叉口到第个交叉口节点的第条可行路径中，所包含的从起点交叉口到第个交叉口节点的前驱交叉口节点的第条可行路径的相关属性； 令表示从起点交叉口节点到第个交叉口节点的所有可行路径的属性标签集合，且中的属性标签数量为，且； 令中的任意第个属性标签表示从起点交叉口节点到第个交叉口节点的第条可行路径的相关属性集合，且； 定义为任意第个交叉口节点的所有属性标签按升序排列后的集合； 令中的任意第个属性标签表示从起点交叉口节点到第个交叉口节点的第条最短路径的相关属性，即；其中，表示从起点交叉口到第个交叉口节点的第条最短路径的行车时间； 表示从起点交叉口经过长度为的路径到达第个交叉口节点的前驱交叉口节点后，再从前驱交叉口节点到第个交叉口节点的总行车时间，表示从起点交叉口到前驱交叉口节点的第条最短路径的行车时间，且，表示从起点交叉口节点到交叉口节点的可行路径数量，且，当为起点交叉口节点，即时，令； 表示时间最小值，且=；其中，表示从起点交叉口到第个交叉口节点的第条最短路径的行车时间； 表示从起点交叉口到第个交叉口节点的第条最短路径中，所包含的从起点交叉口到第个交叉口节点的前驱交叉口节点的第条最短路径的相关属性； 定义为第条最短路径的待搜索标签集合； 定义为单位时间步； 步骤2.2：初始化可行路径的相关属性； 初始化起点交叉口节点的标签集合中的所有标签为，其余任意第个交叉口节点的标签集合中所有标签均初始化为； 将起点交叉口节点的有序标签加入第条最短路径的待搜索标签集合； 定义并初始化计时器为； 步骤3：分层计算单位时间步内的条最短路径； 步骤3.1：计算第条最短路径；初始化； 步骤3.1.1：将待搜索标签集合中时间最小值最小的标签所对应的交叉口节点记为，令表示起点交叉口节点到交叉口节点的第条最短路径的相关属性，即对应的属性标签为，其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间； 表示从起点交叉口经过长度为的路径到达交叉口节点的前驱交叉口节点后，再从前驱交叉口节点到交叉口节点的总行车时间，表示从起点交叉口到前驱交叉口节点的第条最短路径的行车时间，且，表示从起点交叉口节点到交叉口节点的可行路径数量，且，当为起点交叉口节点，即时，令； 表示时间最小值，且=；其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间； 表示从起点交叉口到交叉口节点的第条最短路径中，所包含的从起点交叉口到交叉口节点的前驱交叉口节点的第条最短路径的相关属性； 表示从起点交叉口节点到交叉口节点的可行路径数量，且； 若或，转至步骤3.1.2；否则，转至步骤3.2； 步骤3.1.2：若，则执行步骤3.1.2a；否则，转至步骤3.1.3； 步骤3.1.2a：令，将标签移出，遍历交叉口节点的后继交叉口节点集合中的交叉口节点，对于任意一个交叉口节点且不属于从起点交叉口节点到交叉口节点的第短路中： 令表示起点交叉口节点到交叉口节点的第条最短路径的相关属性，即交叉口节点对应的属性标签为，其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间； 表示从起点交叉口经过长度为的路径到达交叉口节点的前驱交叉口节点后，再从前驱交叉口节点到交叉口节点的总行车时间，表示从起点交叉口到前驱交叉口节点的第条最短路径的行车时间，且，表示从起点交叉口节点到交叉口节点的可行路径数量，且； 表示时间最小值，且=；其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间； 表示从起点交叉口到交叉口节点的第条最短路径中，所包含的从起点交叉口到交叉口节点的前驱交叉口节点的第条最短路径的相关属性集合； 表示从起点交叉口节点到交叉口节点的可行路径数量，且； 若存在，则对，从开始降序遍历，若，则转至步骤3.1.2b，否则，转至步骤3.1.2c； 若存在，则遍历交叉口节点的剩余个有序标签，若存在第个标签满足且，则停止遍历，对，从开始降序遍历，若，则转至步骤3.1.2d，否则，转至步骤3.1.2e； 步骤3.1.2b：令，，并更新时间最小值，将标签加入第条最短路径的待搜索标签集合中，以等待后续步骤继续搜索更新，转至步骤3.1.2c； 步骤3.1.2c：更新前序标签，即令，再令，转至步骤4.1；其中，表示有向路段的行车时间权重； 步骤3.1.2d：令，，并更新时间最小值，将标签加入第条最短路径的待搜索标签集合中，以等待后续步骤继续搜索更新，转至步骤3.1.2e； 步骤3.1.2e：令，，并更新时间最小值，将标签加入第条最短路径的待搜索标签集合中，以等待后续步骤继续搜索更新，转至步骤4.1； 步骤3.1.3：令； 步骤3.1.4：遍历交叉口节点及其后继交叉口节点集合中的交叉口节点，对于任意一个交叉口节点且不属于从起点交叉口节点到交叉口节点的第短路中： 记交叉口节点的前驱交叉口节点集合中的任意一个交叉口节点为； 令表示起点交叉口节点到交叉口节点的第条最短路径的相关属性，即交叉口节点对应的属性标签为，其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间； 表示从起点交叉口经过长度为的路径到达交叉口节点的前驱交叉口节点后，再从前驱交叉口节点到交叉口节点的总行车时间，表示从起点交叉口到前驱交叉口节点的第条最短路径的行车时间，且，表示从起点交叉口节点到交叉口节点的可行路径数量，且； 表示时间最小值，且=；其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间； 表示从起点交叉口到交叉口节点的第条最短路径中，所包含的从起点交叉口到交叉口节点的前驱交叉口节点的第条最短路径的相关属性集合； 表示从起点交叉口节点到交叉口节点的可行路径数量，且； 若不是起点交叉口节点且，则执行步骤3.1.5，否则，返回步骤3.1.4继续遍历； 步骤3.1.5：遍历交叉口节点的所有前驱交叉口节点，记使得最小的交叉口节点为，其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间，表示有向路段的行车时间权重； 令表示起点交叉口节点到交叉口节点的第条最短路径的相关属性，即交叉口节点对应的属性标签为，其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间； 表示从起点交叉口经过长度为的路径到达交叉口节点的前驱交叉口节点后，再从前驱交叉口节点到交叉口节点的总行车时间，表示从起点交叉口到前驱交叉口节点的第条最短路径的行车时间，且，表示从起点交叉口节点到交叉口节点的可行路径数量，且； 表示时间最小值，且=；其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间； 表示从起点交叉口到交叉口节点的第条最短路径中，所包含的从起点交叉口到交叉口节点的前驱交叉口节点的第条最短路径的相关属性集合； 表示从起点交叉口节点到交叉口节点的可行路径数量，且； 令，，转至步骤4.2，其中，表示有向路段的行车时间权重； 步骤3.2：计算第+1条最短路径； 将+1条赋值给，若，则转至步骤6；否则，返回步骤3.1； 步骤4：更新第条最短路径的待搜索标签集合； 步骤4.1：更新交叉口节点的标签及有序标签； 步骤4.1.1：若交叉口节点的标签值且，则更新时间最小值，转至步骤4.1.2；否则，执行步骤4.1.3； 步骤4.1.2：将当前交叉口节点移出集合，若此时集合不为空，转至步骤3.1.2继续遍历；否则，转至步骤3.1.1； 步骤4.1.3：若且，则更新时间最小值，然后将交叉口节点的标签加入，转至步骤4.1.2； 若且，则将标签移出，转至步骤4.1.2； 步骤4.2：更新交叉口节点的标签集合和有序标签集合； 步骤4.2.1：若交叉口节点的标签值且，则更新时间最小值，转至步骤4.2.2；否则，执行步骤4.2.3； 步骤4.2.2：将当前交叉口节点移出集合，若此时集合不为空，转至步骤3.1.4继续遍历；否则，转至步骤3.1.1； 步骤4.2.3：若且，则将交叉口节点的标签加入，转至步骤4.2.2； ，则将标签移出，转至步骤4.2.2； 步骤4.3：更新交叉口节点的标签集合和有序标签集合 步骤4.3.1：若交叉口节点的标签值，则更新时间最小值，转至步骤4.3.2；否则，执行步骤4.3.3； 步骤4.3.2：将当前路段移出所有行车时间权重发生变化的路段集合，若此时集合不为空，转至步骤5.3继续遍历下一个行车时间权重变化路段；否则，转至步骤3.1.1； 步骤4.3.3若且，则将交叉口节点的标签加入，转至步骤4.3.2； 若且，则将标签移出，转至步骤4.3.2； 步骤5：检测实时路况并更新条最短路径； 步骤5.1：判断计时器是否达到，若是，则清空计时器，并执行步骤5.2，否则，继续计时； 步骤5.2：检测路网行车时间权重是否发生变化，若没有发生变化，则返回步骤5.1，否则，记更新后交叉口节点之间路段的行车时间权重集合为，转至步骤5.3； 步骤5.3：对于路段，令表示起点交叉口节点到交叉口节点的第条最短路径的相关属性，即对应的属性标签为，其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间； 表示从起点交叉口经过长度为的路径到达交叉口节点的前驱交叉口节点后，再从前驱交叉口节点到交叉口节点的总行车时间，表示从起点交叉口到前驱交叉口节点的第条最短路径的行车时间，且，表示从起点交叉口节点到交叉口节点的可行路径数量，且，当为起点交叉口节点，即时，令； 表示时间最小值，且=；其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间； 表示从起点交叉口到交叉口节点的第条最短路径中，所包含的从起点交叉口到交叉口节点的前驱交叉口节点的第条最短路径的相关属性； 表示从起点交叉口节点到交叉口节点的可行路径数量，且； 若满足，转至步骤5.3.1，否则，转至步骤5.3.2； 步骤5.3.1：若，令，然后令，转至步骤4.3；否则，转至步骤5.3继续遍历下一个行车时间权重变化路段； 步骤5.3.2：若不是起点交叉口节点且，遍历交叉口节点的所有前驱交叉口节点，记使得最小的交叉口节点为，其中表示从起点交叉口到交叉口节点的第条最短路径的行车时间，表示有向路段更新后的行车时间权重，令，，转至步骤5.3，其中，表示从起点交叉口到交叉口节点的第条最短路径的行车时间，表示有向路段更新后的行车时间权重，表示从起点交叉口节点到交叉口节点的第条最短路径的相关属性；否则，转至步骤5.3继续遍历下一个行车时间权重变化路段； 步骤6：输出当前时间从起点交叉口节点到终点交叉口节点的条最短路径信息； 根据终点交叉口节点的标签集合中的个标签，从终点交叉口节点的第个标签开始，不断通过回溯前驱交叉口节点对应的属性标签，直至回溯到起点交叉口节点的标签，从而得到一条从到的第短路径，且行车时间为，进而得到单位时间步内从到的条最短路径及其行车时间，然后转至步骤5继续搜索路况更新后的条最短路径。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人合肥工业大学，其通讯地址为：230009 安徽省合肥市包河区屯溪路193号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。

以上内容由龙图腾AI智能生成。