(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111580292.7 (22)申请日 2021.12.2 2 (71)申请人 大连理工大 学人工智能大连研究院 地址 116000 辽宁省大连市高新 技术产业 园区火炬路5 6A-22层2211室 申请人 大连鞍利科技有限公司 (72)发明人 李明楚　曹瀚文　王紫荆　 (74)专利代理 机构 青岛恒昇众力知识产权代理 事务所(普通 合伙) 37332 代理人 苏友娟 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 50/26(2012.01) (54)发明名称 人群分配与疏散路线规划的快速 计算方法 (57)摘要 本发明公开了一种人群分配与疏散路线规 划的快速计算方法， 包括以下步骤： S1： 使用双队 列的方法， 首先用邻接矩阵来表示路网图G(N, E)， 其中N为点的集合， E为边的集合。 本发明采用 双队列的计算方法可以快速找到最短路径， 避免 了很多冗余的计算， 大大提高了计算效率， 通过 使用双队列的数据结构技术来存储每次迭代的 最短路径的结果， 避免每次对所有疏散点计算最 短路径， 从而降低算法时间复杂度， 通过使用疏 散批次时间间隔策略， 克服了上一趟疏散与下一 趟疏散之间的时间间隔， 进而更准确的计算出人 群疏散方案， 更符合实际情况， 也更安全， 既可以 防止不同疏散批次的人群拥挤， 又可以合理有效 的分配人群， 满足使用需求。 权利要求书2页 说明书4页 附图1页 CN 114330855 A 2022.04.12 CN 114330855 A 1.人群分配与疏散路线规划的快速计算方法， 其特 征在于， 包括以下步骤： S1： 使用双队列的方法， 首先用邻接矩阵来表示路网图G(N,E)， 其中N为点的集合， E为 边的集合， 每个点n∈N有两个属性， 每条边e∈E有两个属性； S2： 输入路网图G(N,E)， 输出疏散路径和流量的疏散方案， 包含经过的节点和时间 的疏 散路径集 合， 其中疏散点的集 合为S∈E， 避难点的集 合为D∈E； S3： 设置一个超级疏散点s0,连接s0和所有源节点， 将连接所得的边的最大容量设置为 大约待疏散总人 数， 通行时间设置为0； S4： 对所有疏散点找最短路径， 将所有疏散点的最短路径放在PreQueue中 S5： 比较PreQueue和Queue队首 元素大小 S6： 比较Queue中前两个元 素的大小权　利　要　求　书 1/2 页 2 CN 114330855 A 2while(Q1.Shor testPath <＝Q2.ShortestPath){ Route R(S)＝update(Q1.S)； Q1<ShortestPath,S>＝<R.A rrivalTime,S>； S7： 更新流量 flow＝min(Evacue es[s],Available_Edge_Capacity(e,t) )； Reserve Q1.route； S8： 更新疏散点的待疏散人 数和避难点的人 数 S.evacue es‑＝flow； exitNum+＝fl ow； S9： 输出最短路径和流 量： Output  Route Q1.route and flow。 2.根据权利要求1所述的人群分配与疏散路线规划的快速计算方法， 其特征在于， 所述 S1中， 每个点n∈N中的n为最大节点容量， 最大节点容量和节点(n)的初始人数均为非负整 数。 3.根据权利要求1所述的人群分配与疏散路线规划的快速计算方法， 其特征在于， 所述 S1中， 每条边e∈E中的边e为 最大容量， 其中最大容 量和通行时间(e)均为非负整数。 4.根据权利要求1所述的人群分配与疏散路线规划的快速计算方法， 其特征在于， 所述 S2中， 疏散点的集 合用S表示。 5.根据权利要求1所述的人群分配与疏散路线规划的快速计算方法， 其特征在于， 所述 S2中， 避难点的集 合用D表示。 6.根据权利要求1所述的人群分配与疏散路线规划的快速计算方法， 其特征在于， 所述 S3中， 节点的等待时间定义 为TotalWT， 其计算公式为 总的等待时间是当前边的通行时间和前一条边 的通行时间差的总和， 如果二者的差为正数， 即可直接相加， 如果为负数或者为0， 就按0计 算， 表示不需要等待。权　利　要　求　书 2/2 页 3 CN 114330855 A 3