本发明属于交通区域可达性技术领域，具体是一种基于洪泛算法的路网可达范围分析方法。
背景技术：
车辆可达分析是指对特定车辆，综合考虑空间因素和时间因素，寻找在规定时间内该车辆能够到达的交通区域。
车辆可达分析是物流配送与城市智能化交通等研究的热点问题。对于物流公司，其物流服务业务的覆盖范围是衡量其服务能力的重要标准，能否合理选择配送中心，配置配送车辆是实现物流服务全覆盖的关键，而准确的可达性分析则是对相关问题进行最优决策不可或缺的部分；对于城市交通，准确地分析城市内出租车和网约车等车辆的可达性可为城市交通资源的合理分配提供指导，从而有效解决城市交通拥挤以及资源分配不合理等问题。
洪泛算法是指：在网络中，从任何节点通过一个路由器发送的信息包会被发送给与该路由器相连的所有其他节点，是快速散布路由更新信息到整个大型网络的每个节点的一种方法。现有技术中，洪泛算法主要应用于数据通信系统领域，用于实现数据包在主机网络间的传输与交换。但是，洪泛算法在交通领域的应用很少。
目前，现有车辆可达区域计算方法多数基于车辆轨迹，根据车辆查询点和边界点的距离，将交通区域网格化，再基于最短路径进行分析，得到车辆可达区域。另一改进方法引入了不同时间段对可达区域的影响。
但这些方法都是基于车辆查询点与边界点间区域的时空约束进行筛选，并未根据交通区域内不同道路的特点进行准确分析。对于偏远地区的物流配送问题，交通道路状况往往十分复杂，除时间约束外，道路限高限重等问题也会影响运输，所以以上方法的可达性分析适用范围局限，且准确性不足。
技术实现要素：
针对上述问题，本发明提供一种基于洪泛算法的路网可达范围分析方法，根据交通区域内不同道路的特性构建道路网络，将洪泛算法用于交通道路网络中以模拟车辆的行驶过程，对车辆进行较为准确的可达分析。相对于普通的车辆可达分析，本发明考虑了交通区域内道路的复杂性，适用范围广，分析得到的结果准确性明显提高。
所述的基于洪泛算法的路网可达范围分析方法，具体步骤如下：
步骤一、设给定时间为t，针对某选定车辆a，利用车辆a的最大速度v确定交通区域范围，将范围内的道路编号添加到路网集合set_way中。
交通区域范围包含：设给定时间为t，选定的车辆最大速度为v，则所确定的交通区域范围为以车辆位置为圆心，vt为半径所做出的圆。
步骤二、根据车辆a信息对路网集合set_way中的所有道路进行筛选；
根据车辆的高度，宽度和载重筛选区域内道路，依次判断所选交通区域内道路与车辆信息是否匹配，将高度、宽度、载重、车辆种类限制不符合的道路从路网集合set_way中中剔除，剩余满足条件的道路用于道路网络的构建。
筛选后的路网集合set_way＝{wgid1,wgid2,……,wgidm}；wgidm是第m条符合车辆a高度、宽度和载重信息的道路编号。
步骤三、从筛选后的路网集合set_way中依次选择每条道路，将各道路对应的起点与终点编号添加到道路节点集合set_node中；
集合set_node＝{ngid1,ngid2,……,ngidn}；ngidn是从set_way中道路选择的第n个节点编号。
步骤四、将道路节点集合set_node中所有的节点编号构建为路网节点类：
道路节点集合set_node中共n个对象，则生成n个路网节点类node_way，构成路网节点类集合set<node_way>，set<node_way>＝{node_way1,node_way2,……,node_wayp,……,node_wayq,……,node_wayn}；
每个节点类node_way中都包含一个节点编号ngid，一个由多个路网连边类构成的集合set<linked_way>以及一个洪泛时间值flood_time。
节点编号ngid对应集合set_node中的编号；集合set<linked_way>的元素为与该节点相连接的所有路网连边；洪泛时间值flood_time代表上次从该节点进行洪泛时的剩余时间值，默认值为0。
步骤五、根据筛选后的路网集合set_way中的道路编号构建路网连边类；
路网集合set_way中共m个对象，则生成m个路网连边类link_way，构成路网连边类集合set<link_way>＝{link_way1,link_way2,……,link_waym,…,link_waym}；
每个连边类link_way都包含一个道路编号信息wgid，一个通过所需时间信息travel_time，以及一个路网节点类node_target。
道路编号信息wgid对应集合set_way中的编号；travel_time值为保存的通过各道路的时间；node_target中存储的是该道路连边类link_way所指向的路网节点node_way。
步骤六、将n个路网节点类和m个路网连边类进行连接，构建道路网络模型。
连接是指：对集合set<link_way>内每个连边类进行赋值，并添加指向节点node_target，同时将其添加到对应路网节点类的集合set<linked_way>；
具体为：针对连边类link_waym，按照对应道路编号wgidm值，在数据库中获取对应的道路信息；道路信息包括通过时间、终点编号与起点编号；
对连边类link_waym的travel_time赋值为对应道路的通过时间；
根据道路编号wgidm得到的终点编号，在路网节点类集合set<node_way>中找到该终点编号对应的路网节点类node_wayp，作为连边类link_waym对应node_target的值。
同时，根据道路编号wgidm得到的起点编号，在集合set<node_way>中找到该起点编号对应的路网节点类node_wayq，将连边类link_waym添加到路网节点类node_wayq对应的集合set<linked_way>中。
步骤七、采用递归的洪泛算法在道路网络模型中模拟选定车辆a的行驶，得到可达路网列表；
具体为：
步骤701、将模拟车辆a运行的位置与状态构建成包类packet_car并初始化，同时定义可达路网集合set_arrived；
包类packet_car，包含车辆a运行的生命周期和集合set_router；
生命周期初始值为counter；
集合set_router用于记录该包所经过的路网连边信息，由该包所经过的路网连边的编号构成，初始值为空；
可达路网集合set_arrived用于存储车辆a最终经历的路网连边编号，初始值为空。
步骤702、在路网节点类集合set<node_way>中找到距离车辆a最近的路网节点作为源点，记为node_way0，并接收包类packet_car；
设定生命周期值counter为t0。
步骤703、判断t0是否大于0，如果是，进入步骤704；否则，该包已结束，进入步骤708；
步骤704、判断t0是否大于该路网节点内洪泛时间，如果是，进入步骤705；否则，该包为无效包，进入步骤708；
步骤705、判断当前路网节点的连边集合set<linked_way>中否有集合set_router中不存在的连边，如果是，进入步骤706；否则，该路网节点已洪泛完成，进入步骤708；
步骤706、新建一个包packet_new，其时间为t0-tw，向包packet_new的集合set_router中加入该不存在的连边编号；
tw对应为各路网连边的travel_time。
具体加入连边编号的过程为：
判断加入的连边编号是否为1个，如果是，则向包packet_new的集合set_router中加入对应的连边编号即可，否则，当连边编号的数量大于1个时，根据各个时间t0-tw的差值，选择差值最大的时间对应的连边，将该连边编号加入包packet_new的集合set_router中。
步骤707、将包packet_new的集合set_router中加入的连边编号指向的节点node_way1，作为接收包packet_new的下一个路网节点，并将节点node_way1的洪泛时间travel_time更新为t0，返回步骤703，开始新一组的洪泛计算，直至判断t0-tw为0。
步骤708、将集合set_router中的路网连边编号存入初始定义的集合set_arrived中并去重，算法结束；
集合set_router中的路网连边编号即为车辆a的可达路网列表。
步骤八、根据在道路网络模型中得到的可达路网列表为车辆a分配任务，实现精准运输作业。
本发明的优点和积极效果在于：
1)、本发明一种基于洪泛算法的路网可达范围分析方法，充分考虑了车辆周围交通区域内道路的复杂性，根据其道路特点进行筛选，并单独考虑每条路线的通过时间，构造道路网络模型，相比于现有方法更为准确，结果更近似于实际情况。
2)、本发明一种基于洪泛算法的路网可达范围分析方法，采用了洪泛算法，用节点间传递的包模拟车辆的运行，同时针对道路网络的特点进行了一定优化，计算过程具有时间复杂度低的特点。
附图说明
图1是本发明一种基于洪泛算法的路网可达范围分析方法的流程图；
图2是本发明采用递归的洪泛算法计算可达路网列表的方法流程图；
图3是本发明用于解释递归洪泛算法的实施例。
具体实施方式
为了便于本领域普通技术人员理解和实施本发明，下面结合附图对本发明作进一步的详细和深入描述。
本发明提供的基于洪泛算法的车辆路网可达范围分析方法，适用于对特定车辆进行给定时间的可达性分析，最终可计算得出限定时间内车辆所可能到达的交通区域；具体过程为：首先根据输入的车辆信息与时间信息确定交通区域范围，然后根据车辆特性筛选区域内道路，再将所选区域内符合要求路网构建为特定道路网络模型，采用递归的洪泛算法在路网中模拟车辆行驶计算得到可达路网列表，最终根据可达结果为相应运输车辆分配任务，实现精准运输作业。
如图1所示，具体步骤如下：
步骤一、设给定时间为t，针对某选定车辆a，利用车辆a的最大速度v确定交通区域范围，将范围内的道路编号添加到路网集合set_way中。
交通区域范围包含限定时间内车辆a所有可能到达的区域，确定过程如下：
首先，输入车辆a的坐标(lat,lon)，车辆最大速度v和限定时间t；然后，以车辆a坐标(lat,lon)为圆心，vt为半径作圆c，圆c范围即为交通区域范围；将圆c内的道路编号并添加到路网集合set_way中。
所选择的交通区域需要包含限定时间内车辆所有可能到达的区域，从而保证后续分析计算的准确性。同时，此处区域需尽可能得小，以便于在后续分析计算的过程中减少无效计算。故选择圆c为所选区域，该圆c即为保证包含所有可能区域前提下的最小区域。
步骤二、根据车辆a信息对路网集合set_way中的所有道路进行筛选；
车辆a信息包括：高度为height，宽度为width和载重为load，从数据库中依次调取路网集合set_way中每条道路，根据各道路的高度、宽度和载重信息，分别与车辆信息的height,width和load进行对比，将不满足车辆a高度、宽度和载重信息的道路从路网集合set_way中剔除。
筛选后的路网集合set_way＝{wgid1,wgid2,……,wgidm}；wgidm是第m条符合车辆a高度、宽度和载重信息的道路编号。
本步骤筛选的目的为剔除该车辆不可通行的路网。在部分偏远地区的配送问题中，存在着大量道路路况较差、年久失修的情况，将这部分道路剔除后再进行可达性分析对于提高得到结果的准确性十分重要。
步骤三、从筛选后的路网集合set_way中依次选择每条道路，将各道路对应的起点与终点编号添加到道路节点集合set_node中；
集合set_node＝{ngid1,ngid2,……,ngidn}；ngidn是从set_way中道路选择的第n个节点编号。
步骤四、将道路节点集合set_node中所有的节点编号构建为路网节点类：
道路节点集合set_node中共n个对象，则生成n个路网节点类node_way，构成路网节点类集合set<node_way>，set<node_way>＝{node_way1,node_way2,……,node_wayp,……,node_wayq,……,node_wayn}；
每个节点类node_way由区域内不同道路的交点抽象而成，都包含一个节点编号ngid，一个由多个路网连边类构成的集合set<linked_way>以及一个洪泛时间值flood_time。
节点编号ngid对应集合set_node中的编号；集合set<linked_way>代表与该节点连接的道路，集合中的元素为与该节点相连接的所有路网连边的编号；洪泛时间值flood_time代表上次从该节点进行洪泛时的剩余时间值，默认值为0。
步骤五、根据筛选后的路网集合set_way中的道路编号构建路网连边类；
路网集合set_way中共m个对象，则生成m个路网连边类link_way，构成路网连边类集合set<link_way>＝{link_way1,link_way2,……,link_waym,…,link_waym}；
每个连边类link_way由区域内的单条道路抽象而成，都包含一个道路编号信息wgid，一个通过所需时间信息travel_time，以及一个路网节点类node_target。
道路编号信息wgid对应集合set_way中的编号；travel_time值为保存的通过各道路的时间；node_target中代表该连边指向的路网节点，存储的是该道路连边类link_way所指向的路网节点node_way。
步骤六、将n个路网节点类node_way和m个路网连边类link_way进行连接，构建道路网络模型。
连接是指：对集合set<link_way>内每个连边类进行赋值，并添加指向节点node_target；同时将其添加到对应路网节点类的集合set<linked_way>；
具体为：针对连边类link_waym，按照对应道路编号wgidm值，在数据库中获取对应的道路信息；道路信息包括通过时间、终点编号与起点编号；
对连边类link_waym的travel_time赋值为对应道路的通过时间；
根据道路编号wgidm得到的终点编号，在路网节点类集合set<node_way>中找到该终点编号对应的路网节点类node_wayp，作为连边类link_waym对应node_target的值。
同时，根据道路编号wgidm得到的起点编号，在集合set<node_way>中找到该起点编号对应的路网节点类node_wayq，将连边类link_waym添加到路网节点类node_wayq对应的集合set<linked_way>中。
步骤七、采用递归的洪泛算法在道路网络模型中模拟选定车辆a的行驶，得到可达路网列表；
本发明在实施洪泛计算时，提供一个包类packet_car作为于洪泛算法中在网络中传播的介质，模拟的车辆运行时的位置和状态。首先根据车辆信息，在节点中找到距离车辆最近的节点作为源点，建立一个初始时间为输入时间的包，使源点接收该包，开始递归洪泛计算。
如图2所示，具体为：
步骤701、将模拟车辆a运行的位置与状态构建成包类packet_car并初始化，同时定义可达路网集合set_arrived；
包类packet_car，包含车辆a运行的生命周期和集合set_router；
生命周期初始值为counter，用于记录车辆运行中所剩时间。
集合set_router用于记录该包所经过的路网连边信息，由该包所经过的路网连边的编号构成，初始值为空；
可达路网集合set_arrived用于存储车辆a最终经历的可达路网连边编号，初始值为空。
步骤702、在路网节点类集合set<node_way>中找到距离车辆a最近的路网节点作为源点，记为node_way0，并接收包类packet_car；
设定生命周期值counter为t0。
步骤703、判断t0是否大于0，如果是，进入步骤704；否则，该包已结束生命周期，进入步骤708；
步骤704、判断t0是否大于该路网节点内洪泛时间，如果是，进入步骤705；否则，该包为无效包，进入步骤708；
步骤705、判断当前路网节点的连边集合set<linked_way>中否有集合set_router中不存在的连边，如果是，进入步骤706；否则，该路网节点已洪泛完成，进入步骤708；
步骤706、新建一个包packet_new，其时间为t0-tw，向集合set_router中加入该不存在的连边编号并作为包packet_new的路径集合set_router；
tw对应为各路网连边的travel_time。
具体加入连边编号的过程为：
判断加入的连边编号是否为1个，如果是，则向集合set_router中加入对应的连边编号即可，否则，当连边编号的数量大于1个时，根据各个时间t0-tw的差值，选择差值最大的时间对应的连边，将该连边编号加入集合set_router中。
如图3所示，判断节点接收到的包是否具有有效性：即判断包的剩余时间是否大于节点记录的洪泛时间，若为是，则为有效包，进行洪泛，否则为无效包，结束。
从源点o开始进行递归洪泛计算，假设节点b两次接收到包，分别来自源点o与节点a，当节点b接收到来自节点a的包进行洪泛计算时，包的所剩时间要小于来自节点o的包的所剩时间，则其进行洪泛计算的结果必定包含于来自节点o的包的计算结果之中，所以节点b接收到来自节点a的包进行的洪泛计算为无效计算。本发明通过在洪泛计算开始前通过比较包内剩余时间与节点洪泛时间，判断该包是否为无效包，避免无效包的计算。
步骤707、将包packet_new的集合set_router中加入的连边编号指向的节点node_way1，作为接收包packet_new的下一个路网节点，并将节点node_way1的洪泛时间travel_time更新为t0，返回步骤703，进行递归，开始新一组的洪泛计算，直至判断t0-tw为0。
步骤708、将集合set_router中的路网连边编号存入初始定义的集合set_arrived中并去重，算法结束；
集合set_router＝{wgid1,wgid2,……,wgidk}中的路网连边编号即为车辆a的可达路网列表。
当递归传递的洪泛算法全部结束后，代表所有用来模拟车辆运行的包已全部结束生命周期，此时set_arrived中所记录的编号即为在限定时间内特定车辆可以到达的道路编号。将道路编号去除重复并进行排序后输出，车辆可达性分析完成。
步骤八、根据在道路网络模型中得到的可达路网列表为车辆a分配任务，实现精准运输作业。
将特定车辆a可以到达的道路编号结果借助图像化界面进行显示或借入其他装置进行分析，为相应运输车辆分配任务，实现精准运输作业。
本发明根据交通道路特性，建立了特殊的道路网络模型，充分考虑了区域内不同道路的复杂性，根据道路特定进行筛选与构建网络，使得可达性分析结果准确、适用范围广；同时将必要的信息从数据库内提取至模型中，为后续的递归洪泛计算提供了载体。
本发明采用洪泛算法来模拟车辆的运行，现有技术中，洪泛算法主要应用于数据通信系统领域，在交通领域的应用很少。而洪泛算法在网络中进行介质包的递归传递，各个包可以代表运行中的车辆，包的相关参数表示运行的车辆的位置和状态信息。对网络中各个包的传递进行分析，可得到精确的可达性分析结果。
同时，针对车辆问题对洪泛算法进行了优化，对于模拟车辆运行的特殊情况，部分节点接收的包会为无效包，采用普通洪泛算法会存在一定无效计算的情况，会消耗大量的时间。本发明对算法进行优化，增加了对包有效性的判断步骤，避免了该部分的无效计算，减小了算法时间复杂度。
本发明针对特定车辆，考虑了其周边区域内道路的复杂性，进行道路网络构建，运用洪泛算法对车辆可达性进行分析，得到结果并输出。相对现有方法，所得到的可达路网准确性强，方法与装置适用范围广。特别地，对于一些交通情况复杂的区域，本发明提供的方法与装置可以准确地判断道路是否允许车辆通行，从而在进行时空间可达分析前将无法通过的道路进行剔除，这使得结果的准确性大大提高。
1.一种基于洪泛算法的路网可达范围分析方法，其特征在于，具体步骤如下：
步骤一、设给定时间为t，针对某选定车辆a，利用车辆a的最大速度v确定交通区域范围，将范围内的道路编号添加到路网集合set_way中；
步骤二、根据车辆a信息对路网集合set_way中的所有道路进行筛选；
筛选后的路网集合set_way＝{wgid1,wgid2,……,wgidm}；wgidm是第m条符合车辆a高度、宽度和载重信息的道路编号；
步骤三、从筛选后的路网集合set_way中依次选择每条道路，将各道路对应的起点与终点编号添加到道路节点集合set_node中；
集合set_node＝{ngid1,ngid2,……,ngidn}；ngidn是从set_way中道路选择的第n个节点编号；
步骤四、将道路节点集合set_node中所有的节点编号构建为路网节点类：
道路节点集合set_node中共n个对象，则生成n个路网节点类node_way，构成路网节点类集合set<node_way>，set<node_way>＝{node_way1,node_way2,……,node_wayp,……,node_wayq,……,node_wayn}；
每个节点类node_way中都包含一个节点编号ngid，一个由多个路网连边类构成的集合set<linked_way>以及一个洪泛时间值flood_time；
节点编号ngid对应集合set_node中的编号；集合set<linked_way>的元素为与该节点相连接的所有路网连边；洪泛时间值flood_time代表上次从该节点进行洪泛时的剩余时间值，默认值为0；
步骤五、根据筛选后的路网集合set_way中的道路编号构建路网连边类；
路网集合set_way中共m个对象，则生成m个路网连边类link_way，构成路网连边类集合set<link_way>＝{link_way1,link_way2,……,link_waym,…,link_waym}；
每个连边类link_way都包含一个道路编号信息wgid，一个通过所需时间信息travel_time，以及一个路网节点类node_target；
道路编号信息wgid对应集合set_way中的编号；travel_time值为保存的通过各道路的时间；node_target中存储的是该道路连边类link_way所指向的路网节点node_way；
步骤六、将n个路网节点类和m个路网连边类进行连接，构建道路网络模型；
连接是指：对集合set<link_way>内每个连边类进行赋值，并添加指向节点node_target，同时将其添加到对应路网节点类的集合set<linked_way>；
步骤七、采用递归的洪泛算法在道路网络模型中模拟选定车辆a的行驶，得到可达路网列表；
具体为：
步骤701、将模拟车辆a运行的位置与状态构建成包类packet_car并初始化，同时定义可达路网集合set_arrived；
包类packet_car，包含车辆a运行的生命周期和集合set_router；
生命周期初始值为counter；
集合set_router用于记录该包所经过的路网连边信息，由该包所经过的路网连边的编号构成，初始值为空；
可达路网集合set_arrived用于存储车辆a最终经历的路网连边编号，初始值为空；
步骤702、在路网节点类集合set<node_way>中找到距离车辆a最近的路网节点作为源点，记为node_way0，并接收包类packet_car；
设定生命周期值counter为t0；
步骤703、判断t0是否大于0，如果是，进入步骤704；否则，该包已结束，进入步骤708；
步骤704、判断t0是否大于该路网节点内洪泛时间，如果是，进入步骤705；否则，该包为无效包，进入步骤708；
步骤705、判断当前路网节点的连边集合set<linked_way>中否有集合set_router中不存在的连边，如果是，进入步骤706；否则，该路网节点已洪泛完成，进入步骤708；
步骤706、新建一个包packet_new，其时间为t0-tw，向包packet_new的集合set_router中加入该不存在的连边编号；
tw对应为各路网连边的travel_time；
步骤707、将包packet_new的集合set_router中加入的连边编号指向的节点node_way1，作为接收包packet_new的下一个路网节点，并将节点node_way1的洪泛时间travel_time更新为t0，返回步骤703，开始新一组的洪泛计算，直至判断t0-tw为0；
步骤708、将集合set_router中的路网连边编号存入初始定义的集合set_arrived中并去重，算法结束；
集合set_router中的路网连边编号即为车辆a的可达路网列表；
步骤八、根据在道路网络模型中得到的可达路网列表为车辆a分配任务，实现精准运输作业。
2.如权利要求1所述的一种基于洪泛算法的路网可达范围分析方法，其特征在于，所述的步骤一中，交通区域范围包含：设给定时间为t，选定的车辆最大速度为v，则所确定的交通区域范围为以车辆位置为圆心，vt为半径所做出的圆。
3.如权利要求1所述的一种基于洪泛算法的路网可达范围分析方法，其特征在于，所述的步骤二中筛选的具体过程为：
根据车辆的高度，宽度和载重筛选区域内道路，依次判断所选交通区域内道路与车辆信息是否匹配，将高度、宽度、载重、车辆种类限制不符合的道路从路网集合set_way中中剔除，剩余满足条件的道路用于道路网络的构建。
4.如权利要求1所述的一种基于洪泛算法的路网可达范围分析方法，其特征在于，所述的步骤六中连接具体为：针对连边类link_waym，按照对应道路编号wgidm值，在数据库中获取对应的道路信息；道路信息包括通过时间、终点编号与起点编号；
对连边类link_waym的travel_time赋值为对应道路的通过时间；
根据道路编号wgidm得到的终点编号，在路网节点类集合set<node_way>中找到该终点编号对应的路网节点类node_wayp，作为连边类link_waym对应node_target的值；
同时，根据道路编号wgidm得到的起点编号，在集合set<node_way>中找到该起点编号对应的路网节点类node_wayq，将连边类link_waym添加到路网节点类node_wayq对应的集合set<linked_way>中。
5.如权利要求1所述的一种基于洪泛算法的路网可达范围分析方法，其特征在于，所述的步骤706中具体加入连边编号的过程为：
判断加入的连边编号是否为1个，如果是，则向包packet_new的集合set_router中加入对应的连边编号即可，否则，当连边编号的数量大于1个时，根据各个时间t0-tw的差值，选择差值最大的时间对应的连边，将该连边编号加入包packet_new的集合set_router中。
技术总结