下载文档原格式
智能交通系统中的路径规划与优化算法研究一、引言智能交通系统（Intelligent Transportation System, ITS）是利用现代信息通信、感知、控制、计算等先进技术，为交通运输提供智能化服务的一种综合性系统。
其中，路径规划与优化算法在智能交通系统中起着至关重要的作用。
本文将针对智能交通系统中的路径规划与优化算法进行研究，并探讨其在提高交通效率、减少交通拥堵、节能减排等方面所具备的潜力。
二、路径规划算法路径规划算法是指根据交通网络及其相关信息，找到一条或多条满足特定要求的路径的算法。
常见的路径规划算法包括Dijkstra算法、A*算法、Bellman-Ford算法等。
这些算法基于不同的策略，在计算效率和路径质量上存在差异。
其中，A*算法结合了Dijkstra 算法和启发式搜索的思想，能够在保证路径优质性的同时提高计算效率。
三、路径规划算法的优化智能交通系统中的路径规划旨在找到使整体交通系统效率最大化的路径。
然而，在实际应用中，交通网络变动性大、车辆流量分布不均匀等因素都会影响路径规划算法的效果。
因此，对于路径规划算法的优化成为了研究的重点。
1. 预测模型的应用通过分析交通历史数据、车辆轨迹等信息，建立合理的交通预测模型，可以为路径规划算法提供更加准确可靠的输入。
例如，通过预测拥堵情况，路径规划算法可以避开拥堵路段，从而提高整体交通效率。
2. 遗传算法的优化遗传算法是一种模拟自然进化过程的优化算法，通过模拟基因的交叉、变异等操作，寻找最优解。
将遗传算法应用于路径规划中，可以通过不断迭代优化路径方案，从而逐步优化整体交通系统效率。
四、路径优化算法路径优化算法是指根据交通网络的拓扑结构，考虑交通流量等因素，对路径进行进一步优化的算法。
常见的路径优化算法包括流量均衡算法、拥塞控制算法等。
1. 流量均衡算法流量均衡算法旨在通过控制路口的信号灯周期或调整路段的通行能力，使得交通流量在网络中均匀分布，避免拥堵现象的发生。
动态交通分配理论研究综述胡婷1，于雷1，2，赵娜乐1（1.北京交通大学交通运输学院城市交通复杂系统理论与技术教育部重点实验室，北京100044；2.美国德克萨斯南方大学，美国休斯顿 77004）摘要：动态交通分配能反映路网交通流的拥挤性、路径选择的随机性、交通需求的时变性等典型交通流动态特征，比静态交通分配有着明显的优越性。
在简要介绍动态交通分配的重要组成要素的基础上，归纳总结动态交通分配区别于静态交通分配的六个典型特征：因果性、先进先出原则、路段状态方程、路段流出函数、路段特性函数和路段阻抗函数。
从路径选择准则、路径走行时间定义、出行者出行选择假定、动态网络交通流模型研究方法等四个方面对动态交通分配模型的分类进行综述性研究，分析不同模型的优缺点，并总结动态交通分配理论的未来研究方向，可为动态交通分配研究提供一定的参考。
关键词：动态交通分配；交通负荷；动态交通分配模型U491.123 ：A：1002-4786（2010）05-0006-05 DOI：10.3869/j.1002-4786.2010.05.0470 引言交通流分配是交通规划中的一个重要环节。
它将预测得到的OD交通量按照一定的规则分配到已知路网的各条路段上去，从而得到路网中各个路段的交通量和出行费用。
从交通流分配理论发展的整体上看，它经历了由静态交通分配(Static Traffic Assig-nment)到动态交通分配(Dy na-mic Traffic Assignment)两个历史阶段。
静态交通分配理论从提出至今已有五十余年，发展较为成熟。
静态交通分配理论提出的背景主要面对的是在城市交通规划领域的应用，其只需要反映平均的网络交通状态，并不需要详细描述交通流的动态交通特征。
然而，随着社会的发展，城市交通拥堵日益恶化，而解决交通拥堵的关键之一是对交通需求时变性进行刻画的方法掌握。
交通需求的时变性体现在OD 矩阵上则表现出随时间变化的起伏特征。
智能交通知识：智能交通下的动态路权分配技术研究随着智能交通技术的迅猛发展，人们对交通的效率、安全性和环保性提出了更高的要求。
动态路权分配技术作为智能交通技术中的重要一环，将有助于实现更加智能化和高效的交通管理。
本文将就智能交通下的动态路权分配技术进行详细介绍。
一、什么是动态路权分配技术动态路权分配技术即根据实时交通状况，对交通路口或单向道路的不同车辆赋予不同的“权利”或优先级，包括优先通行权、限速或限行等，以达到最佳交通流量和最小化交通堵塞的目的。
相比于静态路权分配技术，动态路权分配技术更加灵活和智能，可以根据不同的交通状况随时进行优化和调整。
二、动态路权分配技术的应用场景1.城市交通拥堵城市交通拥堵是一个普遍存在的问题，特别是在早高峰和晚高峰时段交通拥堵的情况尤为明显。
在这种情况下，可以通过给优先通行的车辆增加权利，例如公共交通、紧急救援等，来缓解交通拥堵。
同时，也可以通过动态限速等方式对交通流量进行控制，以保证交通流畅度。
2.高速公路车流量控制高速公路的车流量大，车速快，车辆密度大，存在一定的安全隐患。
采用动态路权分配技术可以对车辆的速度进行限制、控制车辆间距，从而保证行车安全。
此外，在车流高峰期可以通过路权计算和控制，实现高速公路拥堵的缓解和流量的平衡，提高通行效率。
3.入口处、出口处的优先通行对于入口道路或者出口道路短暂内容纳不下那些等待出入口的车辆时，可以通过增加权利，优先让其通行，从而减少车辆拥堵。
同时，也可以根据不同交通方式对路权进行划分、调整，优先考虑那些对环保有益的交通方式，例如骑行、步行，从而提高绿色交通的比重。
三、动态路权分配技术的实现方法动态路权分配技术的实现需要依赖于实时的交通状况数据的采集和处理。
可采用的数据采集方式包括传感器技术、车载设备等。
在数据采集处理过程中，需要通过智能算法对数据进行分析和处理，从而实现动态路权分配。
具体实现方法包括：1.基于GPS定位和地图信息的算法。
智能交通系统中的路径规划与优化算法研究一、引言智能交通系统（Intelligent Transportation System, ITS）是利用现代信息与通信技术，以及交通运输管理技术等综合应用的系统。
路径规划与优化算法是ITS中的重要研究领域，其目标是通过合理分析交通数据和交通网络的拓扑结构，为用户提供高效率的道路导航系统，减少交通拥堵和碳排放。
二、路径规划算法研究路径规划算法是指根据特定的约束条件和目标，找到从起点到目标点的最佳路径。
常见的路径规划算法包括Dijkstra算法、A*算法和最小带宽优先算法等。
1. Dijkstra算法Dijkstra算法是一种经典的单源最短路径算法，其核心思想是从起点开始，逐步扩展到其他节点，不断更新最短路径。
该算法能够找到两个节点之间的最短路径，但在处理大规模复杂网络时，时间复杂度较高。
2. A*算法A*算法是一种启发式搜索算法，适用于在大规模图中寻找最短路径。
通过启发式函数估算从起点到目标点的距离，从而使搜索过程更加高效。
A*算法在实际应用中表现出较好的效果，并被广泛应用于实时路径规划系统。
3. 最小带宽优先算法最小带宽优先算法是一种解决多播或广播通信的路径优化算法，其目标是使数据包的传输带宽尽可能小。
该算法通过动态调整路径的选择，减少网络中的冲突和重复传输，提高数据传输的效率。
三、路径优化算法研究路径优化算法是指在路径规划的基础上，通过考虑交通拥堵、车辆行驶速度和道路容量等因素，进一步优化路径选择，以达到减少交通耗时和提高交通效率的目的。
常见的路径优化算法包括遗传算法、模拟退火算法和粒子群优化算法等。
1. 遗传算法遗传算法是模拟自然界生物进化过程而提出的一种优化算法。
在路径优化中，遗传算法通过不断迭代和交叉变异，寻找最优路径解。
该算法可以有效处理复杂的路径优化问题，但计算成本较高。
2. 模拟退火算法模拟退火算法是一种优化搜索算法，灵感来源于固体退火过程。
(2005) 西安交通大学对具有排队的多模式动态交通分配问题及其相关应用进行研究。
本文对动态交通分配模型发展进行了介绍和总结，并详细讨论了模型中的路段动态函数、流量传播约束、FIFO等相关特性。
将单一交通模式的点排队路段动态模型扩展到多模式动态路段模型，并且证明了各种模式的路段行程时间函数合乎模式内的FIFO特性，以及在拥挤情况下各模式车辆的速度收敛特性。
将多模式随机动态同时的路径与出发时间选择平衡条件描述为变分不等式问题，提出了两个不同的算法用于求解变分不等式问题：算法一是基于路段的算法，这个算法给出了基于logit的同时的路径与出发时间选择的随机动态网络配载方法，并证明了这个方法的正确性；算法二是基于路径的启发式算法。
仿真试验验证了模型以及两个算法的有效性。
提出了多模式多用户动态交通分配模型，用于评估ATIS对不同模式出行者和交通系统的影响。
将每一模式的出行者分为两类：一类是装配ATIS的出行者，另一类是未装配ATIS的出行者。
由于所能获得的交通信息质量的差异，他们将遵循不同的动态用户平衡条件。
同时，每一种模式出行者在选择路径和出发时间时，不但考虑出行费用和进度延误费用的影响，而且还考虑油耗费用的影响。
将多模式多用户动态用户平衡条件描述为统一的变分不等式问题，利用对角化算法计算相应的平衡流量状态，并通过仿真试验验证了模型与算法的有效性。
使用nested-logit模型模拟ATIS的市场渗透率与服从率，模型的上层模拟了驾驶小汽车出行者的购买行为(市场渗透率)，底层主要描述了装配ATIS设备的小汽车出行者的服从行为(服从率)。
设计了固定点算法计算ATIS的平衡市场渗透率与服从率。
并在简单的路网上进行了仿真研究，结果证明算法与模型是正确和有效的。
提出了组合模式动态交通分配模型，模型中假设有两类出行者：一类是纯模式出行者，他们自己驾驶小汽车完成一次出行。
另一类是组合模式出行者，在其一次出行的第一部分是自己驾驶小汽车完成的，剩余部分是乘公交车完成的。
交通路网优化中的路径规划算法综述交通拥堵是大城市面临的一个重要挑战。
为了缓解交通拥堵问题，提高交通效率，路径规划算法在交通路网优化中起着重要的作用。
本文将综述目前常用的路径规划算法，包括Dijkstra算法、A*算法、Bellman-Ford算法和Floyd-Warshall算法，并分析其优缺点及应用场景。
1. Dijkstra算法Dijkstra算法是一种求解单源最短路径的经典算法。
它的基本思想是从起点开始，逐步扩展搜索范围，直到找到最短路径。
Dijkstra算法通过维护一个优先队列来选择当前距离起点最近的节点进行扩展，直到找到目标节点或搜索完所有节点。
该算法适用于无向图或有向图中有正权边的情况。
Dijkstra算法的时间复杂度为O((V + E) log V)，其中V是节点数，E是边数。
2. A*算法A*算法是一种启发式搜索算法，结合了Dijkstra算法和贪心算法的思想。
它引入了启发函数来指导搜索方向，以减少搜索空间。
在A*算法中，每个节点都有一个估计值，表示该节点到目标节点的预计代价。
算法通过维护一个优先队列来选择当前估计代价最小的节点进行扩展，直到找到目标节点。
A*算法的时间复杂度与Dijkstra算法相同，但在实际应用中通常具有更好的性能。
3. Bellman-Ford算法Bellman-Ford算法是一种求解单源最短路径的动态规划算法。
它通过使用松弛操作来逐步更新节点的最短路径估计值，直到收敛为止。
Bellman-Ford算法适用于解决带有负权边的图中的单源最短路径问题，但要求没有负环路。
该算法的时间复杂度为O(VE)，其中V是节点数，E是边数。
4. Floyd-Warshall算法Floyd-Warshall算法是一种求解全源最短路径的动态规划算法。
它通过使用中间节点来逐步更新节点间的最短路径估计值，直到得到全局最短路径。
Floyd-Warshall算法适用于解决带有负权边的图中的全源最短路径问题，但要求没有负环路。
智能交通系统中的动态路径规划算法研究智能交通系统（Intelligent Transportation System，ITS）是指利用先进的信息技术手段，以提高交通运输系统的效率、安全性和环境可持续性为目标的一种综合性交通管理和服务系统。
在智能交通系统中，动态路径规划算法的研究具有重要的意义。
本文将探讨智能交通系统中动态路径规划算法的研究现状、应用场景和发展趋势。
一、研究现状1. 遗传算法遗传算法是一种模拟自然进化过程的优化算法，可以用于求解动态路径规划问题。
通过遗传算法，可以根据交通流量、道路条件等动态信息来实时更新路径规划结果。
遗传算法能够在多目标和约束条件复杂的情况下，寻找到接近最优解的路径规划方案。
2. 蚁群算法蚁群算法是一种模拟蚂蚁觅食行为的启发式算法，可以应用于动态路径规划问题。
蚁群算法通过模拟蚂蚁在环境中搜索食物的行为，不断更新路径规划方案，并实现全局最优解的搜索。
蚁群算法能够适应交通流量变化、路段拥堵等情况，提供最优路径规划结果。
3. 神经网络算法神经网络算法是一种模拟人类大脑神经元工作方式的方法，可以应用于动态路径规划问题。
通过训练神经网络，可以根据历史交通数据和实时流量信息来预测未来的交通状态，并根据预测结果进行路径规划。
神经网络算法具有很强的适应性和学习能力，能够提供准确的路径规划建议。
二、应用场景1. 高峰交通控制在城市交通管理中，高峰时段的交通流量巨大，易产生拥堵。
动态路径规划算法可以根据实时交通信息，通过优化路线选择和分流策略来缓解交通拥堵。
通过智能交通系统中的动态路径规划算法，可以提供交通参与者准确的行驶路线和时间预测，提高路网的整体通行能力。
2. 突发事件处理突发事件（如交通事故、道路施工等）会对道路交通产生严重影响。
智能交通系统中的动态路径规划算法可以实时获取交通状况信息，并为受影响的交通参与者提供最优的绕行路线。
通过及时响应和调整路径规划，可以减少交通事故和拥堵的发生，提高交通系统的应急响应能力。
智能交通路网路径规划算法的研究与应用随着城市化进程的不断加快，城市道路交通问题日益突出。
而随着信息技术的发展，智能交通系统逐渐成为解决城市交通问题的重要手段之一。
智能交通系统中的路径规划算法，是智能交通系统实现高效、智能交通的核心。
现今的路径规划算法具有超高的精度和计算速度，并且在实际应用中取得了重要的效果。
本文将从算法分类、解决问题、算法评价，以及实际应用等方面综合分析智能交通路网路径规划算法的研究与应用。
一、算法分类根据智能交通路网路径规划算法的分类，可以分为精确算法、近似算法和启发式算法。
精确算法是指完全遍历所有可能路径，比如迪杰斯特拉算法、贝尔曼-福德算法、A*算法等。
在实际应用中，精确算法由于计算量大，计算时间长，只适用于小规模的问题，不适合处理大规模的问题。
近似算法是指通过调整路线策略，使路径得到近似最优解的算法，比如遗传算法、模拟退火算法等。
近似算法的优势在于可以在较短的时间内处理大规模问题，并且精度较高。
启发式算法是指通过启发式函数（heuristic function）指导搜索过程，最终得到一条最优路径的方法，如A*算法、终点到起点（endpoint to start point，ESP）算法等。
由于启发式算法能够有效地缩短计算时间，进而实现实时路径规划，所以在实际应用中得到了较广泛的应用。
二、解决问题在具体的智能交通路网路径规划中，会遇到很多问题，比如旅行商问题、多重背包问题等。
X-bertholo算法是一种比较成熟的解决旅行商问题的算法。
它是一种遗传算法，能有效地解决旅行商问题，并且具有出色的性能。
多重背包问题是一种典型的课程规划问题，VNS算法是一种比较出色的解决方案。
该算法采用了较为简洁的路径表示方式，有效地提高了计算效率，同时保证了精度。
三、算法评价智能交通路网路径规划算法的优劣，应从精度、计算速度、健壮性等方面进行评价。
A*算法是一种应用广泛的启发式算法。
该算法在计算路径的过程中，不获得最短路径。
研究出行时间与路径的交通规划算法一、前言在现代社会，交通运输已经成为人类生活和经济活动的重要基础设施之一。
在城市化程度不断提高的今天，公共交通体系建设和智慧交通运输系统的开发都成为了许多城市的重点之一。
在这些发展的过程中，交通规划算法成为了一个重要的研究领域，其中研究出行时间与路径的算法尤为重要。
本文将详细介绍研究出行时间与路径的交通规划算法。
文章首先介绍了交通规划算法的概念，重点介绍了基于时间的路径规划算法。
随后，文章详细阐述了交通数据的获取方法和处理方式，具体包括传感器采集、GPS定位和卫星遥感等技术。
最后，文章讨论了相应的交通规划算法的实现方式和应用场景。
通过本文的阐述，读者将能够深入了解研究出行时间与路径的交通规划算法。
二、交通规划算法交通规划算法是指通过模型、数据和方法等手段，分析、设计和优化城市交通网络和运输体系的过程。
交通规划算法主要由两个部分组成，其一是交通数据的收集和处理，其二是基于数据的交通规划算法的制定。
交通规划算法可分为两类，其一是基于距离的交通规划，其二是基于时间的交通规划。
基于距离的交通规划简单明了，但不一定能够反映实际情况，例如在高峰时段，常常会出现交通拥堵，导致距离远的路径具有较低的效率。
相对的，基于时间的交通规划可以更加准确的反映城市交通拥堵状况，通过对时间敏感的路段进行规划，能够使出行时间尽可能缩短。
三、基于时间的路径规划算法基于时间的路径规划算法主要是指根据不同的时间段，分析城市交通情况，制定出最短时间的出行路径。
在实际应用中，基于时间的路径规划算法除了需要基于数据分析交通状况外，还需要考虑到用户个性化的需求。
例如，一些用户需要尽可能避免高速公路，一些用户需要将步行时间控制在一定范围内。
基于时间的路径规划算法一般分为两类，其一是基于实时数据的规划算法，其二是基于历史数据的规划算法。
基于实时数据的规划算法在规划路径时，主要基于当前场景的数据，结合预测模型对未来一段时间内的交通情况进行预测，从而制定出最优的路径。
2009年 6月郑州大学学报(工学版)Jun 2009第30卷 第2期Journa l of Zhengzhou U n i ve rs i ty (Eng ineer i ng Sc ience)V o l 30 N o 2收稿日期:2008-11-12;修订日期:2009-01-12 基金项目:国家自然科学基金项目(60804049)作者简介:李曙光(1974-),男,安徽郎溪人,长安大学副教授,博士,主要从事于智能交通系统研究,E m ai:l l x lsg @v i p .si na .co m.文章编号:1671-6833(2009)02-0125-04用于动态交通分配的合理路径集合算法研究李曙光(长安大学电子与控制工程学院,陕西西安710064)摘 要:为了解决在基于路径的动态交通分配问题中,在每一个起点与终点之间的合理路径集合产生问题.首先,介绍了目前常用的路径集合产生方法,如D ial 算法、路段删除算法、路段惩罚算法以及仿真方法等,然后在此基础上提出了可用于动态交通分配问题的合理路径集合产生以及路径合理性判断指标.在一个中型路网中,通过仿真方法确定了本文提出的算法的有效性和正确性,结果表明:以D i a l 算法、路段删除算法和路段惩罚算法为基础的算法给出的结果更加有效,而仿真算法给出的路径集合偏差较大.关键词:合理路径集合;动态交通分配;路径;仿真中图分类号:U 491 文献标识码:A0 引言动态交通分配理论作为智能交通系统的核心理论,近些年有了长足的发展.在求解动态交通分配的算法中,使用基于路径的算法可以对一些基于路径的非自加性花费进行研究,而且可以更灵活性地使用相应的路径选择模型(考虑路径覆盖的路径选择模型如:PS-l o g it 模型等).但是在真实的大规模路网中,通过路径枚举方法将产生大量的路径,而且这其中许多路径具有很高的路径覆盖率.也可以说,在路网中一个OD 对之间真正合适的路径数只占整个枚举路径的一部分,因此怎样获得路网中的合理路径集合是非常重要的[1-7].另外,通过事先算好的合理路径集合,可以在动态交通分配程序运行时不需要使用费时的动态最短路算法,因而可以节约大量的运行时间.笔者对目前的几种路径生成方法进行了对比研究,并在此基础上推荐了可用于动态交通分配问题的合理路径集合产生以及路径合理性判断指标,并在一个中等的路网中对这几种方法进行了对比.1 合理路径产生方法在任一OD 对之间,通过路径生成方法给出合乎出行者旅行选择目的的路径集合.路径生成的相应算法主要包括K 条最短路算法、启发式算法(路段删除方法、路段惩罚方法以及仿真方法),文献[6]对路径产生方法进行了详细的介绍.下面给出产生OD 对之间合理路径集合产生的几个主要算法.1.1 D ial 算法根据D ial 算法中的原理,删除相应的路段,然后在简化的路网中计算出相应的合理路径[5].(1)对于每一个起点r ,计算从起点r 到其它每个节点i 的最小花费,记为C ri .(2)对于每一个终点s ,计算从起点s 到其它每个节点j 的最小花费,记为C js .(3)对于每个路段a =(i ,j ),如果C ri >C rj 或是C is <C js ,则从路网中删除相应的路段.(4)在简化的路网中计算每一OD 对之间的路径集合,可以通过节点数组和路段数组中扩展得到相应的路径数组.1.2 路段删除算法[2](1)首先使用最短路算法计算出在OD 对之间的最短路径;(2)从这个最短路径中删除全部或是部分路段;(3)然后,在剩下的路网中再计算相应的最126郑州大学学报(工学版)2009年短路径;(4)重复上面的过程得到相应的最短路径选择集.缺点:删除全部路段的方法可能把路网中一些重要的连接路段删除,导致删除后的路网缺乏连接性;而一次删除一个路段的方法,可能使路网的变化不大.1.3 路段惩罚算法[3](1)首先使用最短路算法计算出在OD 对之间的最短路径;(2)增加这个最短路径中部分路段的权重;(3)然后,在剩下的路网中再计算相应的最短路径;(4)重复上面的过程得到相应的最短路径选择集.描述:这个算法允许必要的路段依然存在路段上,这样避免了路段删除算法所导致的路网连接性不够的情况.1.4 仿真方法[4]由于旅行者在选择路径的时候可能并不能够得到确定的旅行时间信息,因此他们选择路径更多的是根据带有误差的感觉出行时间.为了能够反映旅行者的这种特性,分析者使用了可以代表旅行者感觉的随机分布中,作随机抽样的方法产生路段出行时间.算法的具体流程表示如下:(1)确定一个随机分布表示旅行者的感觉变化.如路段行程时间用高斯分布表示;(2)从路段出行时间的随机分布中,进行采样,得出相应的路段出行时间数据;(3)使用最短路算法,计算相应的最短路径;(4)重复以上过程.2 合理路径集合的判断上面4个算法的缺点是不能保证在动态交通平衡中的所有路径都包括在产生的路径集合中.然后在路径产生过程中选择合适的参数,获得充分的具有表示性的路径集合.怎样判断上面给出的路径集合是否合理,目前主要使用两种方法:一种是在执行动态交通分配程序之前通过一些判断标准确定合理性(事先判断法),笔者采用文献[6]中使用的路径覆盖率作为判断标准;另一种是在动态交通分配程序执行完后,通过动态最短路算法以检验是否存在丢失的路径(事后判断法).笔者根据这些先前的有效路径集合判断方法,提出了一个综合性的合理路径集合判断方法,其过程如图1所示.首先通过前面给出的路径生成方法生成相应的路径集合,而后确定生成的路径集合是否合理.文献[6]中给出了一个确定路径集合是否合理的判断指标,即是通过观察者选择路径与算法生成路径进行对比,以确定生成路径的合理性.这个指标虽然直观,但是需要大量的出行者调查数据,而且在非常真实的大规模路网中,这样收集数据得到相应的指标值是十分困难的.为了避免这个困难,以路径覆盖率(表示在一个起点与终点之间路径集合中,其中一个路径与其它路径的重合部分的比例)为基础,给出了一个数学上易于计算的指标.这个指标计算的是生成路径集合中的路径覆盖率,如果一条路径覆盖率过高,表示这条路径是不合理的.直观而言,出行者选择出行路径时,选择的出行路径一般会有一定的区分.比如说,有两条重叠很多的路径,出行者可能只会选择其中的一条出行.这里使用简单的PS -Log it 模型[1]中的路径覆盖率计算公式,表示如下:PS rsp =a p t aT p!1 j P rsaj rs ,p (1)式中:P r s 表示OD 对rs 之间的路径集合; aj 表示路径p 包括路段a 是1,否则是0;t a 表示路段a 的自由流行程时间;T p 表示路径p 的自由流行程时间;如果PS rsp ∀ ( 表示预先设定的指标值),则路径p 是合理的;否则,路径p 是不合理的.图1 合理路径集合生成方法F ig .1 T he Reasonab le PathG enerati on M e thod第2期李曙光 用于动态交通分配的合理路径集合算法研究1273 仿真实验通过在S ioux Falls仿真试验路网(图2)进行了仿真试验路网中有24个节点和76个路段,路段参数是随机产生的;使用4个OD对(1,20), (2,13),(4,20),(10,21);4个OD之间的枚举路径分别达到3165,4498,2880,2739.比较上面的路径生成算法以及合理路径集合生产流程的合理性.在路径生成方法中的路段删除算法中,为了保持路网的连接性,在每次迭代中删除一个路段.在路段惩罚方法中,每次迭代增加最新生成的最短路径上的路段权重3%.在路段仿真算法中,假设路段行程时间函数中的参数合乎高斯分布.这3种方法总的迭代次数设为50次.图1中的动态交通分配方法采用文献[5]给出的动态随机同时的出发时间和路径平衡方法.通过上面的算法流程得到在S i o ux Fa lls路网中4个OD对之间的合理路径集合.表1给出了4种算法流程中在OD对之间路径数量(其中包括最后通过动态最短路算法获得的增补路径,以#A∃打头的路径路段序列表示增补的路径).从表1中可以看出:通过前3个算法得到的合理路径集合是类似的,而算法4(路段仿真算法)得到的路径数量多于其它3个方法.而且最后增补的路径数量相比前3个方法要多,这主要是仿真方法得到的初始路径集合是抽样具有高斯分布的随机数得到的,因此初始路径集合并不一定合理,进而导致随后的增补路径集合较多.从表1给出的结果可以认为:通过前3个算法得到的路径集合是比较合理的路径集合.这些路径数量相比于枚举得到的路径数量而言,大大减少.图2 实验路网F ig.2 E xa m ple network表1 在OD对之间路径(路段序列)集合Tab.1 The path set(link Series)b et w een OD pairsOD算法1 算法2 算法3 算法4(1,20)1-4-16-20-18-561-4-16-20-18-561-4-16-20-181-4-16-20-18-561-4-16-22-50-561-4-16-22-49-53-591-4-16-22-50-562-7-37-39-75-65-682-6-10-32-28-45-592-6-10-34-41-45-592-6-10-34-41-45-592-7-36-32-30-53-592-6-10-32-28-46-682-6-10-34-41-46-682-6-10-32-28-45-592-7-36-34-41-46-69-642-6-10-34-41-45-59A-1-4-16-22-50-562-6-10-34-42-72-682-7-36-34-42-73-75-642-6-10-34-41-46-68A-2-7-37-39-75-64A-2-7-37-39-75-642-6-10-34-41-46-68A-1-4-16-22-49-53-59A-2-6-10-34-42-72-68A-2-6-9-13-25-28-46-68A-2-6-9-13-25-30-53-59 A-2-6-9-13-25-30-53-59A-2-6-9-13-25-30-53-59A-2-6-10-34-41-46-68A-2-6-9-13-25-28-45-59A-2-7-37-39-75-64A-2-6-10-34-42-72-68A-1-4-16-22-50-56A-2-6-10-34-41-45-59(2,13)3-2-7-373-2-7-373-2-7-373-2-7-373-2-6-10-33-374-16-22-48-27-33-374-16-22-48-27-33-373-2-6-10-33-37A-4-16-22-48-27-33-374-16-22-18-28-46-70-73-744-16-22-48-28-44-42-73-743-2-6-10-34-42-73-74A-4-16-22-48-28-46-70-73-744-16-20-18-56-63-70-73-744-16-22-48-28-46-70-73-743-2-7-36-32-28-46-59-66-74A-4-16-22-48-27-34-42-73-74A-4-15-11-10-34-42-73-74A-16-20-18-56-63-70-73-744-16-22-48-28-46-70-73-74A-4-15-11-10-34-42-73-744-6-20-18-56-62-66-74A-4-16-20-18-56-62-65-70-73-74A-4-16-20-18-56-63-70-73-74A-4-15-13-25-28-44-42-73-74A-4-15-13-25-28-46-70-73-74A-4-15-13-25-27-34-42-73-74A-4-16-22-48-27-34-42-73-74A-4-16-22-48-27-33-37128郑州大学学报(工学版)2009年续表1OD算法1 算法2 算法3 算法4(4,20)10-34-41-45-5910-34-41-45-5910-34-41-45-598-7-37-39-76-72-6810-34-41-46-6810-34-41-46-6810-34-41-46-689-12-16-22-50-569-12-16-20-18-569-12-16-20-18-5610-34-42-72-6810-34-41-45-599-12-16-22-50-569-13-25-28-46-689-12-16-20-18-5610-33-37-39-76-72-69-61 A-9-13-25-30-53-599-13-25-28-45-599-12-16-22-50-5610-32-30-53-59A-10-34-42-73-75-64A-8-7-37-39-75-649-13-25-30-53-5910-32-28-46-68A-10-34-42-72-68A-9-13-25-30-53-59A-8-7-37-39-75-64A-9-12-162-20-18-56A-10-32-30-53-59A-10-34-42-72-68A-9-13-25-28-45-59A-9-13-25-30-53-59A-10-32-30-53-59A-10-32-30-53-59A-9-13-25-28-45-59A-10-34-41-46-68A-10-34-42-72-68A-8-7-37-39-75-64A-9-13-25-28-46-68(10,21)28-46-6928-46-6928-46-6927-33-37-39-7528-45-59-6228-45-59-6228-46-68-6227-31-8-7-37-39-75 28-46-68-6228-46-70-73-7528-45-59-6228-46-6928-44-42-73-7528-46-68-6228-46-70-73-7528-45-59-63-6928-46-70-73-7530-53-59-6227-33-37-39-7529-50-56-63-6927-34-42-73-75A-27-34-42-73-7529-50-56-6230-53-59-63-69A-27-33-37-39-75A-30-53-59-62A-28-46-70-73-75A-30-53-59-62A-28-45-59-62A-27-34-42-73-754 结论笔者对在动态交通分配中的合理路径生成方法进行了研究.首先介绍了几种常用的合理路径生成方法,如D ial方法、路段删除方法、路段惩罚方法、路段仿真方法等.并给出了一个新的合理路径产生流程以及判断标准.通过在一个中等路网中的仿真研究得到4个OD之间的合理路径集合,结果表明:通过D i a l方法、路段删除方法、路段惩罚方法得到的路径集合是类似的,而且是合理的.参考文献:[1] BEN AK I V E M E,RAMM ING M S.D isc rete cho icem ode l s of trav eler behav ior i n ne t w orks[C]%L ectureN o tes:A dvanced M ethods for P l ann i ng and M anagem ent o f T ransporta ti on N et wo rks.Capr,i Ita ly.25M ay1998.[2] A ZE V EDO J A,S ANTOS M E O.A n A lgor it h m f o rthe rank i ng of shortest pat hs[J].European Journa l o fO pera ti ona l R esearch,1993,69(2):97-106.[3] BARRA T D,AN EZ J.M u lti di m ensi onal path sea rchand assi gn m en t[C]%Proceed i ng s o f the21st PTRCSumm er M eeti ng,1993:307-319.[4] S HEFF I Y,POW ELL W B.Pow e l.l A n a l go rith m f o rthe equ ili br i u m assignment prob l em w it h random li nkti m es[J].N et wo rks,1982,12(2):191-207.[5] L I M Y,HE YDEC K E R B.D yna m i c depart ure ti m e andstochastic use r equ ilibri u m assign m ent[J].T ransportati on R esearch P art B,2005,39(3):97-118.[6] RAMM ING M S.N et work know ledge and route cho ice[D].M assachusetts:M assachuse tts Institute o f T echnology,2002.[7] 田智慧,武 舫,熊 伟.公路地理信息系统中的数据组织与管理[J].郑州大学学报:工学版,2008,29(4):118-121.Reasonable Path Set A lgorit h m for Dyna m ic Traffic A ssign m entLI Shu-guang(Schoo l o f E l ec tron i c&Control Eng i neeri ng,Chang&an U n i versity,X i&an710064,Ch i na)Abst ract:I n or der to obta i n the reasonab le path set bet w een each OD pair for the path-based dyna m ic traffic assignm ent prob le m,the path generation procedure is presented.F irstly,so m e path generation m ethods such as li n k e li m i n ati o n m ethod,li n k penalty m ethod and li n k si m ulati o n m ethod are introduced.Then a reasonable path generation procedure is proposed and t h e reasonab le path index is g i v en.Fina ll y,i n a m ed i u m net w ork, t h e si m ulati o n exa m ple de m onstrates that the d ialm ethod,link eli m ination m ethod,link pena lty m ethod are better t h an the li n k si m u lati o n.K ey w ords:reasonab le path se;t path;dyna m ic traffic assignm ent。
