大规模路网下中心式实时动态交通诱导路径优化方法

暂无

大规模路网下中心式实时动态交通诱导路径优化方法\n技术领域\n[0001] 本发明属于城市交通诱导领域，涉及大规模路网下城市智能交通诱导系统的中心式实时动态交通诱导路径优化实现方法。\n背景技术\n[0002] 城市交通诱导主要分为分布式诱导方式和中心式诱导方式。现有城市交通诱导大多采用分布式诱导方式，即由安装在车辆中的车载导航装置独立进行最优路径计算，并以该计算结果为依据进行路径引导。由于分布式诱导方式仅考虑车辆各自的出行需求进行路径优化，容易产生交通拥挤转移问题。而中心式诱导方式从整个路网均衡的角度出发，通过计算全路网所有点对之间的最优路径，不但能够引导驾驶员避开拥挤，走最佳行驶路线，而且还可以有效避免分布式诱导方式易造成的拥挤转移问题，可有效缓解城市交通拥挤，是国际公认解决交通拥挤最有效的诱导方式。目前，由于无法攻克大规模路网路径优化这一技术难题，无法在短时间内得到大规模路网下所有点对之间的最优路径，中心式诱导方式还没有真正在大规模路网环境中进行工程实际应用。\n发明内容\n[0003] 本发明提出一种城市智能交通诱导系统的大规模路网下中心式实时动态交通诱导路径优化实现方法，实现智能交通诱导系统对大规模路网中车辆的中心式实时动态交通诱导。通过动态地读取存储在Oracle数据库中实时更新的交通路网拓扑结构和路段路阻数据，中心式诱导路径优化方法基于这些数据，在短时间内完成交通路网中所有点对之间的最优路径优化处理，并将最优路径优化处理结果根据实际需要，通过可变信息板(VMS)、车载终端、广播、手机、PDA或Internet等方式进行发布处理。\n[0004] 本发明的技术方案采用C/S(客户端/服务器)模式实现，由2N+1台计算机、网线N\n和高性能信息交换机和发布诱导路径的终端设备构成，其中，2 台计算机用作服务器(1台设为主节点，其他设为从节点)，1台计算机用作客户端。客户端计算机安装Windows XP操作系统、Oracle数据库、MapX4.5软件及路径优化客户端应用程序，路径优化客户端应用程序由负责动态地从Oracle数据库中读取实时更新的交通路网拓扑结构和路段路阻数据的数据获取模块、负责与服务器主节点计算机进行连接和数据传输的客户端通信接口模块和负责向路网中出行者发布最优路径计算结果的发布模块组成。服务器计算机全部安装Redhad-LinuX 6.0操作系统，服务器主节点还需安装MPI消息传递软件、路径优化服务器计算程序，路径优化服务器计算程序由负责与客户端计算机进行数据传输的服务器通讯接口模块、负责将交通路网进行最优分解便于最优路径求解的网络分解模块、负责全路网所有点对之间最优路径求解计算的最短路径并行计算模块和负责检测最优路径是否完成求解计算的终止检测模块组成。网线和高性能交换机用作搭建局域网，实现客户端计算机和服务器计算机之间的良好通信。\n[0005] 其中，数据获取模块通过将路径优化客户端应用程序与Oracle数据库建立连接，动态读取存储在Oracle数据表中实时更新的交通路网拓扑结构和路段路阻数据，即全路网中所有路段的起点编号、终点编号和路段路阻数据，并赋值给一个N行3列的矩阵三元组，N为路网中路段总数，三元组指路段起点编号、终点编号和路段路阻三个元素。\n[0006] 客户端计算机通过客户端通信接口模块与服务器主节点计算机建立连接，将数据获取模块获取的由交通路网拓扑结构和路段路阻数据构成的N行3列的矩阵三元组上传给服务器主节点，启动路径优化服务器计算程序。\n[0007] 路径优化服务器计算程序根据客户端计算机上传的N行3列的矩阵三元组，首先通过网络分解模块将交通路网分解成几个小区，以便于个处理器的最优路径并行计算求解。\n[0008] 本发明提出一种递阶式的网络分解算法，主要分两步实现：\n[0009] 第一步，利用光谱对分方法，按照服务器启动的处理器数量将交通路网分解为与处理器个数相同的小区；\n[0010] 第二步，根据出行者喜欢尽可能走主要道路的行为特性将每个小区分为主要路网和次要路网，并确定子区，其中，将驾驶员和居民出行常走的道路定位主要道路，主要道路把城市路网划分成若干小区，小区内的道路定位次要道路。\n[0011] 网络分解结束后，最短路径并行计算模块负责完成全路网的最优路径求解计算，各处理器根据网络分解结果，对每个处理器所分派的节点采用双端队列最短路径计算方法，分别求局部最小值，然后各个处理器相互合作求全局最小值，最后再将这一最小值广播出去。其中，在最优路径搜索时按出行者特性首先进行主干道搜索，再对次干道搜索到达目的地。\n[0012] 在各处理器合作求解最优路径过程中，由终止检测模块负责检测最优路径求解是否完成。\n[0013] 本发明提出采用同步过渡自适应终止检测算法，通过对最短路径并行计算模块中各个处理器的队列是否清空及通信网络中是否存在未被处理的消息进行实时地检测，如果所有处理器的队列均已清空，并且在通信网络中没有未被处理的消息，则通知最短路径并行计算模块结束计算。\n[0014] 服务器主节点计算机和服务器从节点计算机完成全路网所有点对之间的路径优化处理之后，通过服务器通信接口模块将路径优化处理结果返回给客户端计算机，客户端接口模块负责接收路径优化处理结果，并通过发布模块根据用户的不同需求将最优路径处理结果发送给不同的终端，如可变信息板(VMS)、车载终端、手机、PDA或Internet。\n[0015] 本发明针对大规模路网路径优化的技术难题，提出的大规模路网下中心式实时动态交通诱导路径优化实现方法，能够在短时间内求解大规模路网下所有点对之间的最优路径，能够满足工程实际应用的需求。\n[0016] 通过采用上述方案，解决了大规模路网下中心式实时动态交通诱导路径优化问题，城市交通诱导中心能够以低成本、高可靠性在短时间内完成大规模路网中所有点对之间的最优路径优化，实现了大规模路网下的中心式实时动态交通诱导，同时该方法的实现，对缓解城市路网交通拥挤具有重要意义，并且将大大降低车载端设备的价格。\n附图说明\n[0017] 图1为本发明装置结构框图；\n[0018] 图2为本发明流程图；\n[0019] 图3为数据获取模块流程图；\n[0020] 图4为客户端通信接口模块流程图；\n[0021] 图5为网络分解模块流程图；\n[0022] 图6为最短路径并行计算模块与终止检测模块图；\n[0023] 图7为服务器通信接口模块图；\n[0024] 图8为发布模块图；\n[0025] 图9为Oracle数据表存储交通路网拓扑结构和路段路阻数据示意图。\n具体实施方式\n[0026] 数据获取模块负责与Oracle数据库建立连接，以一定的时间间隔动态地从Oracle数据表中读取实时更新的交通路网拓扑结构和路段路阻数据，即全路网中所有路段的起点编号、终点编号和路段路阻数据，并赋值给一个N行3列的矩阵三元组，通过客户端通信接口模块，将矩阵三元组数据上传给服务器主节点计算机，服务器主节点计算机通过服务器通讯接口模块接收客户端计算机上传的存储全路网中所有路段的起点编号、终点编号和路段路阻数据的N行3列的矩阵三元组数据，网络分解模块负责根据服务器通讯接口模块接收的矩阵三元组数据按照服务器所启动的处理器数量和出行者特性进行交通路网网络分解，最短路径并行计算模块根据交通路网网络分解结果，在各个处理器上进行最短路径计算，终止检测模块负责对最短路径并行计算模块中各个处理器的队列是否清空及通信网络中是否存在未被处理的消息进行检测，如果所有处理器的队列清空均已清空，并且在通信网络中没有未被处理的消息，通知最短路径并行计算模块结束计算，获取全路网最优路径，并通过服务器通讯接口模块将全路网所有点对之间的最优路径优化结果传送给客户端计算机，客户端通讯接口模块接收服务器通信接口模块传送过来的全路网所有点对之间的最优路径优化结果，再由发布模块根据用户的不同需求将最优路径发送给不同的终端，如可变信息板(VMS)、车载终端、广播、手机、PDA或Internet。\n[0027] 一、路径优化客户端应用程序\n[0028] 1、数据获取模块\n[0029] 路径优化客户端应用程序启动后，数据获取模块与Oracle数据库建立连接，动态地读取存储在Oracle数据表中且实时更新的交通路网拓扑结构和路段路阻数据，即交通路网中所有路段的起点编号和终点编号和路段路阻数据，其中，路段路组包括行程时间、行驶距离、拥挤程度和道路质量等多种满足不同驾驶员偏好的出行费用数据，并赋值给一个N行3列的矩阵三元组，该矩阵三元组由三个元素组成，三元组指路段起点编号、终点编号和路段路阻三个元素，N为路网中路段总数。\n[0030] 存储在Oracle数据表中实时更新的交通路网拓扑结构和路段路阻数据，其来源是初始交通路网拓扑结构数据(即交通路网中各个路段的起点编号和终点编号数据)主要从导航电子地图内置的属性数据库中获取，如果交通路网拓扑结构发生变化(道路增加，如修建新的道路；道路减少，如封闭道路)，则需要根据城市规划部门或交通指挥控制中心等提供的交通路网拓扑结构增量数据包对Oracle数据表中存储的交通路网拓扑结构数据进行实时更新。\n[0031] 路段路阻数据可以是路段的长度、行程时间等，路段的长度数据通常可以从导航电子地图属性数据库中直接获取，路段的行程时间等数据主要是根据城市交通路网中各类检测器(如线圈检测器、视频检测器、浮动车)实时采集的交通数据对路段行程时间进行估计获取，主要包括基于单种检测器数据的行程时间估计和基于多种检测器数据的行程时间融合估计。我们将获取的路段路阻数据存入Oracle数据表，并根据一定的时间间隔(5~15分钟)对这些数据进行实时更新。\n[0032] 2、客户端通信接口模块\n[0033] 客户端通信接口模块通过调用接口函数实现与服务器计算机进行连接及数据传输。\n[0034] 具体实现流程：\n[0035] a、初始化与服务器主节点计算机的连接；\n[0036] b、矩阵三元组数据上传；\n[0037] c、计算任务上传：求全路网所有点对之间的最优路径并要求返回结果；\n[0038] d、计算结果成功返回后，断开连接，进行善后处理。\n[0039] 3、发布模块\n[0040] 路径优化服务器计算程序在完成交通路网全路网所有点对之间的最优路径求解计算之后，将路径优化结果通过服务器通信接口模块调用相应的接口函数返回给客户端计算机，客户端发布模块根据用户的不同需求将最优路径计算结果发送给不同的终端，如可变信息板(VMS)、车载终端、手机、PDA或Internet。\n[0041] 二、路径优化服务器计算程序\n[0042] 1、服务器通信接口模块\n[0043] 服务器通信接口模块负责接收客户端通信接口模块上传的数据，并传送给网络分解模块和最短路径并行计算模块，在路径优化服务器计算程序完成交通路网全路网所有点对之间的最优路径求解计算之后，再将路径优化结果通过服务器通信接口模块返回给客户端计算机。\n[0044] 2、网络分解模块\n[0045] 网络分解模块根据服务器通讯接口模块接收的交通路网拓扑结构和路段路阻数据，对交通路网进行网络分解，网络分解模块包括两个步骤：\n[0046] 第一步，利用光谱对分方法，按照服务器启动的处理器数量将交通路网分解为与处理器个数相同的小区，所述的处理器是指服务器主节点计算机和服务器从节点计算机；\n[0047] 具体实现流程：\n[0048] a、根据交通路网拓扑结构关系构造与路网结点数相同的Laplacian矩阵；\n[0049] b：求解Laplacian矩阵的最小非零特征值对应的第二特征矢，即Fiedler矢，并将Fiedler矢中每个值分别与交通路网中的结点相对应；\n[0050] c：求解Fiedler矢的中值，将大于中值的点赋值为+1，将小于中值的点赋值为-1；\n[0051] d：根据+1和-1将交通路网划分成两部分；\n[0052] e：上述a～d步反复执行，N次循环后，可将交通路网被划分为2N部分，且每个部分的单元数近似相等。\n[0053] 第二步，根据出行者行为特性将每个小区分为主要路网和次要路网，并确定子区。\n这里出行者特性主要是指无论是在市区里或城市之间出行，驾驶员通常喜欢尽可能走主要道路，将驾驶员和居民出行常走的道路定位主要道路，主要道路把城市路网划分成若干小区，小区内的道路定位次要道路。其中驾驶员和居民的出行偏好根据大量居民出行调查和驾驶员问卷调查来获得。\n[0054] 3、最短路径并行计算模块\n[0055] 最短路径并行计算模块根据交通路网网络分解结果，在各个处理器上进行最短路径计算。\n[0056] 具体实现流程：\n[0057] a、给每个处理器分派n＝N/p个节点，并对每个节点进行赋值初始化；\n[0058] b、首先对每个处理器所分派的n个节点分别求局部最小值，然后p个处理器相互合作求全局最小值，最后在将这一最小值广播出去。\n[0059] c、每个处理器根据分配的n个节点，分别独立进行双端队列(Pallottino)的计算操作。路径搜索时，按照节点和道路的重要性进行分列搜索，总是优先搜索重要节点(按被搜索的频率划分重要节点和次要节点)和主要道路(根据网络分解的第二步确定)队列。\n[0060] 4、终止检测模块\n[0061] 终止检测模块负责对最短路径并行计算模块中各个处理器的队列是否清空及通信网络中是否存在未被处理的消息进行实时地检测，如果所有处理器的队列清空均已清空，并且在通信网络中没有未被处理的消息，则通知最短路径并行计算模块结束计算。\n[0062] 三、局域网组建\n[0063] 网线和高性能交换机用作搭建局域网，实现客户端计算机和服务其计算机间良好通信。