英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
基于最短路径算法的智能路径引导系统设计
摘要：随着城市化进程的加快和汽车工业的发展，许多大都市的交通拥堵已逐渐严重。 因此，许多国家利用智能交通系统(ITS)控制交通，诱导车辆流动，从而减轻道路拥堵，提高交通效率，它是一种重要而作用广泛的方法。智能路线引导系统（IRGS）作为智能交通的一个重要组成部分，它不仅调节各个十字路口的交通流量来充分利用不够的道路基础设施，而且减少了运行距离和平均等待时间，使每个司机达到区域交通平衡。本文探讨了一种IRGS设计，并提出一种解决交通诱导任务分解和路径选择问题的方法。仿真实验结果表明，采用最短路径算法的IRGS可以获得更好的网络性能，提高交通控制系统的效率。该研究为实际应用系统的开发提供了理论和方法指导。
关键词：智能路线引导系统；动态交通分配；任务分解；最短路径算法
1.介绍
随着全球城市化趋势的加剧，越来越多的人涌入城市。这种情况导致社会各方面的严重困难。对交通管理来说，其后果是很明显的：在北京2007年和2012年机动车数量增加了66.7%（312万-520万），这极大地影响了生活质量。城市里大量的车辆不仅降低了交通质量和效率，而且增加了时间和金钱成本，造成更严重的交通事故、交通堵塞和环境污染。此外，交通现象还引发了许多社会问题，如压力、空气污染、油耗过大，浪费时间等。交通问题已成为制约许多大城市发展的主要瓶颈。
交通问题是由于有限的供给和不断增长的运输需求所导致的[2]。早期的公路网扩张被认为是有效解决道路交通管制问题。但是，有限自然资源和昂贵的劳动力消耗使它不是最终解决问题的方法。智能化管理交通系统与驾驶员交通道路知识状态可以减少交通拥挤的诅咒。所以于20世纪90年代提出的“智能交通系统”（ITS），为我们研究这一问题提供了新的视角。智能交通系统突破传统的交通信号控制器和静态交通诱导，使大城市的交通控制更加智能化。道路交通流的优化将带来在日常生活中可观的多方面的收获。ITS的目标是通过使用各种技术来拯救生命，时间和金钱，以此优化交通系统，使之更有效率更加安全[3]。除了明显的经济效益外，更有效的交通管理导致环境问题的改善和通过减少车辆流通时间提高驾驶员和乘客的生活水平。这个智能交通系统为21世纪城市交通问题提供解决方案的潜力已经在几个分段应用中得到了证明。根据美国智能交通协会所说[4]， ITS包含广泛的基于无线通信的信息、控制和电子技术，这些技术嵌入到系统的基础设施和车辆中，以缓解拥堵、提高安全性和生产力。
本文提出了一种智能路径诱导系统IRGS，通过对动态交通信息的处理和分析，进行道路交通实时预测，提供高效、准确的智能交通服务和及时规划最佳行车路线。导航任务越简单，就能达到更好的目标。本文建立了一个简化的城市多环路系统模型，介绍了交通诱导任务分解的原理并应用最短路径算法选择最优方案。 仿真结果表明，与现有的一些方法相比，IRGS在交通管理方面具有一定的优势。
为了帮助您更好地了解我们的学习，我们概述本文的贡献如下：
- 我们提出了一个IRGS的设计，并将其分为四个部分不同的子系统，它们是道路网络数据收集子系统、车载终端子系统、交通管理数据通信子系统、进路优化子系统。并详细介绍各子系统的结构和功能。
- 我们回顾了建立在在动态交通分配的基础上的经典的路径引导系统方法，并指出这些方法的不足之处。 然后，我们提出了一种解决交通引导和路径选择问题的任务分解的方法。
- 我们使用VISSIM对IRGS的性能进行了仿真评估。仿真结果表明，与动态交通场景下的静态集中式路径诱导相比，该方法具有较好的近似性（达到了预期的理论结果）、改进的测度增益和全局交通优化。
论文的其余部分安排如下。第二部分介绍了该系统的体系结构及其四个子系统的详细信息。第三部分对提出的模型和算法进行了说明。第四部分利用VISSIM软件对系统进行性能评估。最后，在第五部分进行总结，它提出了项目的结论、商业化和对拟议系统的未来范围。
2.IRGS的框架
交通灯控制和车辆引导是智能交通的两个基本组成部分。交通灯是一种强有力的强制和被动控制和诱导交通流的工具，而车辆诱导在主动和主动地引导和调节交通流方面有着重要的作用，特别是在交通堵塞的情况下。IRGS不仅要调节各交叉口的交通流量，充分利用道路基础设施不足的情况，而且要减少每一个驾驶员的行驶距离和平均等待时间，以达到区域交通平衡。从交通管理者的角度出发，利用海量传感器采集的实时交通数据，系统可以根据出行者的位置、目的地和偏好提供多种个性化服务。同时，从用户的角度出发，在收到导航信息后，旅行者可以相应地避开拥堵的道路，选择最优的路线，从而达到区域平衡。从某种程度上说，交通诱导是一种针对特定目的对交通流的直接、积极的调节。要实施这一制度，需要做以下工作：
- 收集区域路网过去和现在的车辆信息（如交通密度、车速、平均交叉口延误等）。这些真实的数据可以通过在交通路口手动计数或使用诸如线圈感应器、闭路电视摄像机等探头来获得。
- 利用过去和现在的交通信息，建立短期城市道路交通流量预测模型，并生成道路权重函数，用以度量被检测道路的拥挤度。
- 在探测车上安装嵌入式OBU（车载单元）检测交通状况，并采用无线通信作为传输模块与交通数据通信中心交换信息。所有这些车载单元使得探测车成为交通信息的来源。
- 为不同种类的车辆分配不同的优先级，避免将所有用户引导到同一条最短路径，并考虑每条道路的交通负荷和用户终端的始发目的地信息，确定优化的路径。
- 通过各种媒体向公众实时提供车速、行驶时间、事故及施工区域等信息。用户终端接收到路径引导信息后，提供短信、语音服务、动态地图等多模式引导信息。
综合考虑，该系统必须包含交通信息检测、信息交换和数据库管理、任务分解和路径选择、导航信息广播等互联子模块。可移植性强、传输可靠、响应速度快是大型交通诱导系统的主要特点。该系统的运行对信息传输和数据库维护的安全性提出了更高的要求。这些都使IRGS成为一个开放的、可扩展的、兼容性强、传输可靠、响应速度快的分布式系统。智能路径诱导系统的四个子系统是：路网数据采集子系统、车载终端子系统、交通诱导数据通信子系统和路径优化子系统。ITGS的结构和功能如图1所示。
图1 ITGS的结构和功能
2.1公路网数据收集系统
质量登记车辆传感器包括IRGS的数据采集子系统[6]。许多基于不同车辆力学的交通数据传感器在交通领域的实际应用效果良好。这些设备可以从不同厂家购买，而且它们测量技术先进。由于不同传感器采集的交通数据格式不同，在设计该子系统时必须考虑独立的冗余性和灵活的可扩展性。
但在实际应用中，传感器分布在远离交通数据中心的地方，通信信道数量有限。因此，我们需要使用局部决策规则处理局部传感器的观测数据。为了提高路径引导的性能，需要将原始数据发送到各个传感器内部的融合模块，然后将来自不同传感器的决策发送到路径优化子系统进行最终决策[7]。
2.2车载终端子系统
传统的车载终端系统通常提供基于GPS（全球定位服务）和GIS（地理信息系统）的车辆定位服务，并根据驾驶员的偏好生成最优的路径。然而，在实际应用中，大多数系统很少支持司机的决策，甚至相反会引起司机的投诉。这是他们在交通状况发生变化时缺乏灵活性和智能性的原因，这使得他们表现得不如之前预测的那么好。
目前已有很多基于静态地图的商业交通诱导终端。然而，他们的表现远远不能令人满意。首先，在一些大城市的交通高峰期，大多数街道都存在交通拥挤，交通诱导策略很难找到所谓的最优路径。然后，如果你陷入交通堵塞，他们很难给你任何有价值的建议，因为指导策略是固定的，这是他们效率低下的主要原因。而且，这些静态的交通诱导终端对驾驶员没有约束，有些驾驶员会按照自己的路径而不是推荐的路径行驶，这使得交通诱导系统根本无法工作。
鉴于移动终端用户众多，应用范围广泛，我们对其可移植性、适应性和独立性提出了基本要求。嵌入式车载单元和微型传感器的用户终端不仅具有导航查询的基本功能，还可以采集周围的交通信息并将其传输到交通信息中心。车载终端在全网无线通信的支持下，丰富了交通数据的来源，可用于交通流预测和路径选择。车辆终端通过其无线传输模块接收交通状况和诱导信息。
2.3交通引导数据通信子系统
GPS、GIS、计算技术和通信网络的集成，使交通诱导系统能够实时采集和处理交通信息，从而提高交通信息质量[9]。数据通信子系统负责信息中心、车辆传感器和用户终端之间的信息交互。因此，该子系统是实现IRGS功能方面的核心。一方面，由车辆传感器和用户终端采集的交通数据通过无线通信网络发送到路由决策模块。另一方面，通过网络将短时间的交通状况和优化子系统的引导路径反馈信息广播给驾驶员，缓解了交通拥挤。网络上可靠而频繁的数据传输保证了IRGS的性能和实时性。无线网络的总处理能力必须足够强，以防出现任何可能的扩展和异常。
无线传输方式在交通领域的主要功能是实现准确、实时的信息交换和大容量的网络容量。由于车辆在路网中高速行驶，其行为很难预测。考虑到这些特点以及交通诱导系统对通信的广域接入和双向传输的需要，并不是所有主要的无线通信技术都适合于交通数据的实时传输[10]。 网络的建立需要做大量的工作，以满足大范围交通信息在容量和传输速率上的大规模传输的需要。
2.4路径优化子系统
路径优化子系统是IRGS的基本组成部分，它处理车辆传感器和探测车采集的实时信息，为最终用户输出最优的路由方案。面对数以百万计的导航查询，该子系统能够分析和处理交通数据，预测短时交通流，并在每个规定的时间间隔内为驾驶员生成优化的路线。交通分配建模和诱导算法是该子系统实现的难点，它直接影响到整个路网的性能和效率。近30年来，许多学者在这一领域进行了大量的研究，为进一步的研究奠定了理论基础。
求解算法的唯一性和收敛性不仅从理论上说是重要的，而且从它们作为策略分配工具对模型的相关性和可靠性的潜在影响来看也是重要的[11]。此外，这种由车对车和车对基础设施通信所支持的我们设想的智能交通诱导算法，允许智能交通管理。
3.导航方案
在这一部分中，我们主要描述了不同车辆的导航任务分解原理和每个分布式路径选择的最短路径算法。装有用户终端的车辆向交通信息中心发送交通数据及其引导请求，路径优化子系统向公众广播交通状况并响应其请求。
3.1提出问题
尽管交通流行为与气体等可压缩连续流体介质有一些相似之处，但它们之间的差异是明显的。呼叫传输模型（CMT）是一种收敛于水岩模型的数值逼近方法，它以显式的方式复制运动波、皇后层的形成和耗散。这种能力使其成为一个适合于动态交通建模的平台。如何改进CTM或建立一种新的智能交通管理模式是难点所在。
除了交通量的测量外，未来交通量的预测对于准确确定道路权重也非常重要。Claudio Meneguzzer提出了交通信号控制与路径引导联合问题（CTSCRG）的环形结构、实用性和定义[12]，与一般的分配模型相比，CTSCRG模型能提供更高的网络流量预测精度，提高了道路诱导系统向驾驶员提供实时交通信息的质量。设计这种模型的主要挑战在于克服部署障碍，保持路由层的可扩展性和效率。新兴的路径引导服务的用户数量呈指数增长，这样就不可能把整个制导要求看作一个控制对象。因此，采用合适的任务分解策略对交通诱导具有重要意义。
只考虑用户满意度的路由引导算法试图确保用户能在最短时间内到达目的地。但是由于这些算法将所有用户引入同一条最短路径而导致最短路径拥挤，无法平衡流量负载。我们设计的方法考虑了各路段的交通负荷，对均衡交通密度、减少交通拥挤有较好的效果。同时考虑交通负荷和用户满意度是很有必要的，特别是在道路密度较高的情况下，这个问题必须要考虑[13]。
3.2导航任务分解
我们的城市交通引导道路优化问题需要对所考虑的对象：道路网络进行精确的定义。它实际上是一种特殊的图形，而路径引导是一种搜索图的算法，其目的是寻找最短路径。同时，我们还定义了驱动成本，它表示某条道路的实时道路密度。
定义（道路网）：道路网是一个加权有向多重图G=（V，E），其中V是表示显著道路元素的顶点集：交叉点、端点，E是表示顶点之间道路段的一组弧（有向边）。我们使用一组邻接表来表示图G。邻接表可以容易地适于表示加权图，也就是说，其每一条边具有相关联的权重的图，通常由权重函数w:E→R给出。例如，设G=（V，E）为带权函数的加权图。边（u，v）isin;E的权重w（u，v）与顶点v一起简单地存储在u的邻接列表中。
在接收到用户终端的位置和目的地信息后，路径优化子系统将其视为一对起点-目的地（OD）。并对车辆传感器和探测车采集的信息进行处理，得到道路权重w（u，v），根据不同的交通状况而变化。城市交通状况自适应识别方法具有良好的效果，具有较高的精确性和坚固性[14]。我们可以为不同种类的车辆分配不同的优先级，以避免将所有用户引入同一条最短路径。假设急救车、消防桥、警车的优先级高于轿车，高于货车。为了应对日益增长的交通诱导请求，我们采用了一种分布式的交通诱导机制。下面详细介绍了该方法中制导任务分解的过程。
第一步。整个交通诱导任务G可以根据不同的OD对划分为不同的子任务集，如G=（G1，G2hellip;Gn）。子任务可以是同一OD对车辆的交通诱导或单个车辆的路线选择。
第二步。给定同一OD路径引导子任务Gi的组件，需要考虑以下两种情况。
（1）如果子任务Gi包含不同优先级的车辆，则Gi必须按照优先级从高到低的顺序完成。高优先级车辆的路径引导完成后，需要更新对未来道路重量的预测。
（2）如果子任务Gi包含单一优先级的车
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[239304]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
