收稿日期:200401
09. 浙江大学学报(工学版)网址:ww w.jou rn https://www.doczj.com/doc/6318689295.html, /eng
基金项目:浙江省自然科学基金资助项目(601119).
作者简介:李威武(1976-),男,湖北通城人,博士,从事智能控制、智能优化技术的研究.
通讯联系人:王慧,教授.E -m ail :hw ang @iipc.z https://www.doczj.com/doc/6318689295.html,
第39卷第6期2005年6月
浙 江 大 学 学 报(工学版)
Jo urnal of Z hejiang Univ ersity (Engineering Science )
Vol.39No.6Jun.2005
智能交通系统中路径诱导算法研究进展
李威武,王 慧,钱积新
(浙江大学工业控制技术国家重点实验室,系统工程研究所,浙江杭州310027)
摘 要:针对智能交通系统的路径诱导问题,提出了按诱导系统的目标是系统路径或单车路径、所依据的信息性质是静态或动态以及路径生成方式是分散型的还是中心型的三种分类方式.详细讨论了路径诱导算法的实时性、动态路径诱导和交通控制与诱导一体化集成这三个在路径诱导系统研究中的关键问题,并分析了它们最新的研究进展.结合分析结果与路径诱导系统的实际应用前景,给出了基于出行者心理特征模型、多目标优化、路段交通量预测、提供更多智能化服务以及基于分布式人工智能框架模型等进一步研究未来路径诱导算法的重要研究方向.关键词:智能交通系统;路径诱导系统;最短路径问题;交通控制;分布式人工智能
中图分类号:T P18;T P491 文献标识码:A 文章编号:1008973X (2005)06081907
New trends in route guidance algorithm research of intelligent transportation system
LI Wei -w u ,Wang Hui ,QIAN Ji -xin
(N ational Laboratory o f Industrial Control T echnology ,I nstitute of S y stems Engineering ,
Zhej iang University ,Hangzhou 310027,China )
A bstract :Fo r solving the route guidance pro blem in intelligent transportatio n sy stem (I TS ),three classifications of ro ute g uidance system s w ere pro posed according to the aim o f route g uidance sy stem ,the character of steady o r dy namic state info rmatio n and the available m ode o f route guidance.The key pro blem s in the three main research fields including alg orithm real time efficiency ,dynamic ro ute guidance algo rithm and integration w ith traffic control sy stem in route g uidance sy stem and their up -to -date study
developments we re analy https://www.doczj.com/doc/6318689295.html, bining analysis results and the possibility o f practical application o f ro ute guidance sy stem ,several impo rtant problems in future research on route guidance alg orithm w ere presented based on traveller psycho logy model ,m ulti -index o ptimization ,traffic flow forecast ,m ore intelligent route guidance service and an algo rithm model of distributed artificial intelligence.Key words :intellig ent transpo rtation sy stem (ITS );route guidance alg orithm ;sho rtest path problem ;traffic control ;distributed artificial intellig ence 路径诱导系统(ro ute guidance system )是智能交通系统的核心组成部分之一.路径诱导系统通过诱导信息来改变出行者的出行行为,降低出行者对未知交通状态的焦虑,合理分配整个交通网络上的交通流,从而减少整个系统总的交通时耗[1].目前的
交通控制系统基本上都是采用开环和被动式控制,这些控制方法不可能得到最优解,而引入路径诱导控制可以实现闭环反馈控制,为交通网络控制提供了新的控制模式并可能实现真正意义上的优化控
制.路径诱导系统的研究对象是由路网、车流和具有
能动行为的出行者组成的复杂系统,因此对其研究也涉及到交通工程、自动控制、人工智能、计算机技术等众多交叉领域[2].目前国内外对交通路径诱导算法的研究主要集中在提高算法的实时性、处理动态路径信息、交通控制系统集成等关键问题上.在给出了按路径诱导系统目标、所依据的信息性质以及路径生成方式进行分类的基础上,本文详细综述和分析了路径诱导算法在实时性、动态路径信息处理以及与交通控制系统集成几个方面的最新进展,并提出了未来路径诱导算法发展的几个重要方向.
1 路径诱导系统的分类方式
路径诱导系统有以下几种主要的分类方式:
1)按诱导系统的目标可分为系统路径诱导和单车路径诱导.系统路径诱导的目标函数是交通网络给定区间内的所有被引导车辆的总出行时间[3],系统路径最优的研究主要是从交通网络系统动态交通分配的角度进行[4],由于系统路径最优诱导的要求十分苛刻,一般只具有评价理论效率的作用.考虑到可操作性,目前路径诱导系统的优化目标一般都是指单个车辆的路径优化,代价函数可为行驶距离、行驶时间、路段拥塞程度或几种指标的加权和等,而行驶时间最短已成为路径诱导研究的典型问题.
2)按路径诱导所依据的信息性质可分为静态路径诱导系统和动态路径诱导系统.静态路径诱导系统所依据的信息为静态的路网信息,如预先存储的路网结构和路段旅行时间.
3)按诱导路径生成方式可分为分散型诱导系统和中心型诱导系统.分散型诱导系统由车载系统计算生成诱导路径,而中心型诱导系统由交通管理中心的计算系统产生诱导路径,并将结果通过通信装置传送给车辆.
图论中普通的最短路径问题(shortest route pro blem,S RP)已有各种成熟的解法,如Dijkstra 算法、A*算法等.然而智能交通系统中的路径诱导由于路网对象的复杂和特殊、求解的实时性要求,以及与交通控制系统相互耦合等特性,远比基本S RP 问题复杂.如何在这些复杂限制条件下求解最优路径或满意路径,正是路径诱导算法研究的核心.
2 路径诱导算法实时性研究
无论路径诱导系统采用中心式还是分散式的计算方式,路径诱导算法都必须解决实时性问题.在分散式计算环境中,车载计算系统的配置一般不会很高,目前的路径诱导产品大多是面向普通应用的移动手持计算平台,如个人数字助理(perso nal digital assistant,PDA).手持计算平台在计算速度上有较为严重的不足,因此较少资源消耗下的快速路径搜索能力显得十分重要.中心式计算环境中,中心计算机的配置一般较高,然而考虑到通信过程中的时间消耗,中心式诱导系统也应当采用实时性好的路径搜索算法.此外中心式诱导系统还可能同时接受很多不同的计算呼叫,因此还必须考虑诱导系统在大负荷情况下的算法实时性问题.
Zhan等人[5,6]研究了实际交通路网条件下的最短路径算法.Dijkstra算法在从单点到所有点、从单点到单点问题上依旧是最快的几种算法之一;然而即使是采用速度最快的双桶数据结构实现,Dijkstra 算法在33M H z处理器和8M RAM的环境下,计算一个节点数为100000的网络最短路径的平均耗时为12s,这对分散式计算环境的诱导方式是很难接受的.
基于这种情况,很多研究者开始采用启发式和分层路径搜索算法来计算最短路径.启发式算法中最有代表性的是A*算法.A*算法使用合适的启发信息来优先搜索那些最有希望的节点,从而降低计算时间.目前对分层路径诱导算法的研究较为丰富.分层算法基于这样的出行者行为,假设出行者大多数愿意选择那些他们比较熟悉、道路等级较高、连通性能较好的次优路径,而不是单纯的距离最短路径.常见的分层算法一般采用底层和顶层两级分层:底层包括路网中所有的道路和交叉口;顶层只包括主干道和主干道形成的交叉口.顶层中的主干道将路网划分为若干个自然网格,各网格内的从道通过进出口节点E点与干道相连,网格的E点在底层和顶层路网上都是可见的.一个典型的两层路网结构如图1所示.图中点O和D分别代表起点和终点,O网格和D网格分别为包含这两个点的顶层网格,E1、E2、E3、E4为O网格的E节点,E5、E6、E6、E8为D网格的E节点.通过分层算法找到的O点到E点之间的路径包含以下三部分内容:
图1 两级分层路网示意图
Fig.1 Illustra tion of tw o-laye r hierar chy
820浙 江 大 学 学 报(工学版)第39卷
1)O网格内一条从O点到O网格E节点的路径;
2)顶层路网中一条从O网格E节点到D网格E节点的路径;
3)D网格中一条从其E节点到D点的路径.
决定以上路径的方式主要有最近E节点方法和最佳节点分层算法[7].最近E节点方法计算速度较快,但准确性较差,较少采用;在最佳节点分层算法中,函数f g(x,y)为底层网格G上从节点x到节点y的最短路径费用,f*(x,y)为节点x到节点y在顶层网格上最短路径费用,N o和N d分别为O网格和D网格的E节点集合.图1中N o={E1,E2,E3, E4},N d={E5,E6,E7,E8}.如果起始节点O和终点D间的最佳分层路径通过E节点E o∈N o和E d ∈N d,则E o和E d通过下式决定:
(E o,E d)=arg min
(i,j)∈N
o ×N
d
{f o(O,i)+
f*(i,j)+f d(j,D)}.
尽管最佳节点分层算法保证了最优解,但是它的计算量较大,大大超过了最近节点算法.
Jagadeesh等人[8]提出一种节点提升分层算法,能够保证算法获得最短路径,而计算量与最近节点算法相近.不过节点提升分层算法是一种基于硬件路由单元的算法,因此仅适合节点数固定如64、128的网络.他们结合分层路径诱导算法和启发式算法,提出一种应用上较成熟的启发式分层算法.该算法首先对路网进行简化处理,删除中间节点并合并主干道的会交点,大大减少了路网的节点数和连接数;然后在节点提升算法中采用启发式估计值代替起始点到各自E节点的最短路径,进一步减少计算量.在主干道层计算最短路径时,以节点到起点和终点的距离之和作为启发值可以进一步减少计算量,从而使启发式分层算法速度得到了很大提升.新加坡城市交通网络的试验显示,启发式分层算法与A*算法相比,最优路径的准确率误差平均为3.31%,速度要快52倍.
为了消除因用户“自私”行为导致的最优路径的振荡,以及充分平衡网络中的负载,一般希望路径诱导系统能对用户推荐多条“最优”路径,这也就是所谓K路最短问题.常见的K路最短算法是由Dijk-stra算法发展起来的二重扫除法,这是一种非确定性多项式时间复杂性的算法,对大型交通网络难以满足实时性的要求.而遗传算法、神经网络等软计算方法的计算时间对网络尺寸不敏感,解决大规模网络中K路最短问题具有一定优势[9,10].虽然神经网络方法和遗传算法涉及到大量的迭代而计算速度较慢,但若是用基于硬件如现场可编程逻辑器件(field-prog ramm able g ate array,FPGA)芯片来实现,则可以非常快.
为了保证中心式诱导系统在大的计算负荷下稳定工作,以及增加系统的响应速度,Huang等人[11]研究了一种半固化的路径诱导方法,即预先计算好各起讫点间的最短路径,并将其存储在中心主机的方法.当中心主机接受到诱导请求时,只要执行一个查表的任务即可,速度得到了极大的提高,即使在诱导请求高峰期,响应速度也不会受大的影响.同时在存储最优路径时,系统并不存储所有的最优路径路段,而只存储最优路径离出发点最近的下一路口的数据,这样不仅使存储开销合理,并且也与路径诱导指令方法一致,即出行者只需知道在下一个交叉口的转向即可.对于大型的路网结构,这种方法对内存的需求和各节点间权值的更新要求较高.Fetterer 等人[12]进一步研究了采用混合存储分层信息的方式来解决这些问题.但从目前的研究结果来看,这类基于固化方法的查表式诱导不适合于分散式的路径诱导系统.
3 动态路径诱导算法研究
动态在线路径诱导是智能交通系统中最为人们所期许的功能之一,动态路径诱导系统一般应具有通过考虑交通网络的变化来提供最小出行时间路径的功能.
由于动态路径网络中的各路径权值均在动态变化,此时理论上的动态路径诱导算法变得异常复杂.如果先进先出(first in first o ut,FIFO)条件满足,可以推广Dijkstra算法来解决动态最短路径问题[13].在不满足FIFO条件时,Chabini[14]提出将时间离散化处理来求解任意点到某终止点的最短路径.Fu等人[15]将路段行驶时间看成连续随机过程,估计在某一时刻特定路径的出行期望时间.在动态路网权值变化的概率分布已知的随机情况下,最短路径问题的解有多种变化情况[16],当路网的权值为时变随机时,最短路径的求解则十分困难,很难求得解析解[17].
在工程实际中,一种简单且应用较多的处理办法是认为各路径路段权值变化是确定性的,最简单的情况下它只与历史行程时间相关.在此前提下,各研究者纷纷提出自己的动态路径诱导模式.
Lam等人[18]提出一种结合历史数据和当前交
821
第6期李威武,等:智能交通系统中路径诱导算法研究进展
通状况的诱导方式,在当前交通流与历史数据没有明显变化时,可按预先计算的离线结果进行诱导,只有在发现当前状况跟历史数据有很大变化时才进行调整.
Sung等人[19]提出一种采用G PS实时数据的路径诱导方法.它基于历史数据和实测数据,采用时间序列的自回归积分滑动平均模型(auto-reg ressive integrated moving average,A RIM A)来预测各路段下一时段的通行时间,并采用修正的Floyd-Washall 算法来计算最短路径.
Gaetani等人[20]将交叉口各时间段的绿信比当成控制变量来控制通过从该交叉口出发的路段的诱导车辆比例,从而达到优化每一辆进入交叉口的车辆的总行驶时间目的.通过对单个交叉口的最优控制来解决全局路网的优化.
Kobay ashi等人[21]根据下游交叉口是否发生拥挤以及是否采用信号灯控制和信号灯的控制参数来估计各路段的平均行使时间,然后采用Dijkstra算法计算最小的平均行使时间路径.
苏永云等人[22]研究了路径权值在优化过程中跨时段动态变化的问题,给出了改进的矩阵算法和改进的A*算法来求解K路最短问题.
Fu[23]将交通网络的最短通行时间归结为一种闭环自适应最短路问题(clo sed-loop adaptive shor-test path routing problem,CASPRP),将路段的通行时间看成时变的随机变量,并且可以在车辆进入该路段时做出准确的预测,其优化的目标函数定义为下一个可供选择的路段,而不是全部路径.这种方法可以让车辆能及时地接受实时信息,并做出适当的行驶路径变化,因此诱导效率高于在出行开始时就决定全部行驶路径的开环自适应诱导.
对于时变的交通网络系统,大部分出行诱导策略都是基于起讫点行驶时间期望最小的路径.然而出行者可能还会希望路径行驶时间期望的变化尽可能小.Sen等人[24]提出了一种综合考虑最小期望和方差的路径选择模型.
当考虑路径权值动态变化时,路径诱导算法的实时性问题将变得更加困难.Ziliaskopoulos[25]在将路段通行时间看成时变函数时提出一种求平均最短路径的顺序算法,并在此基础上提出一种对算法复杂度改进的大规模并行算法.
由于城市交通网络中交通流的高度复杂性和难以预测性,基于精密交通流数学模型的路径诱导算法的实施十分困难,有些研究者开始注意一些对模型要求较低的智能解决方法.
杨兆升等人[1,26]提出一种将交通流比拟成自然流体的神经网络诱导模式,并用遗传算法来优化流体神经网络的参数.这种诱导模式基于以下假设:从出行点出发,径流量最大的通道到达目的点的路径就是对应于交通网络的最短路径.计算表明,这种方法较传统K路最短算法优越,并且成功率较高.
贺国光等人[27]提出一种具有评测和自学习能力的诱导模式,诱导系统包括交通状况数据库、诱导策略评价单元、策略评价数据库、诱导策略学习单元、诱导策略数据库和诱导策略推理机单元.由于该系统采用知识库模型来代替数学模型描述交通状况与诱导策略之间的复杂关系,使诱导系统不断地学习改进自己的诱导策略,从而能更好地描述它们的不确定性关系.
动态路径诱导要比静态诱导复杂得多,这也是当今路径诱导算法研究中最为核心的问题.遗憾的是,目前对于此问题的各种技术路线探讨大部分还停留在假定性较强的理论层次.同时动态路径诱导算法的实时性则更是一个很少有人注意的研究领域.
4 交通控制、诱导的集成研究
交通路径诱导系统的另一个研究热点是诱导系统与交通控制系统的集成研究.交通路径诱导系统和交通信号灯控制系统是城市智能交通管理最重要的两个方面.随着研究日益深入,它们的综合集成愈发显得重要.1)目前路径诱导策略中大多只考虑路段的行驶时间,忽略了交叉口的等待通行时间.而实际上,城域道路系统中交叉口的延误占整个行程时间的很大部分,甚至超过路段行驶时间[28].因此在考虑路径诱导算法时必须包含交叉口延误的影响,而车辆在交叉口的通行延误和信号灯控制策略直接相关.2)当诱导服务的使用者增加到一定的程度,必将改变交通流在路网上的分配,即诱导策略反过来也会影响到信号系统的控制策略.诱导和控制策略的相互耦合增加了对交叉口通行时间估计的难度,也给诱导系统的实施带来新的挑战.
目前路径诱导系统与交通控制系统集成的基本解决方法是将这两个系统放到一个统一的框架中,通过优化两者的目标函数达到同时优化的目的.
H ounsell等人[29]研究了英国的SCOO T(split,cy-cle and offset optim izatio n technique)系统与路径诱导系统的三种不同层次的融合方式,而徐岩宇等人[30]提出一种路径诱导系统和控制系统一体化的结构框架.这些工作都是基于交通再分配的全局最
822浙 江 大 学 学 报(工学版)第39卷
优方案,实施难度较大,并且路径诱导与交通控制的直接整合、同时优化也会导致模型与算法的复杂性增高,可能会对系统效率与可靠性带来不利的影响.
由于路径诱导与交通控制系统直接优化的复杂性,一些研究人员提出首先根据路径诱导系统将合适的交通流分配到路网,再由交通控制系统来适应这些交通流,并形成相应的交通控制方案.莫汉康等人[31]研究了在这种框架下的交通控制子区自动划分问题.马寿风等人[32]提出在诱导系统和控制系统之上建立协调层的集成方法,以简化优化模型和寻优算法.
Jia等人[33]研究了现有I TS体系结构中动态路径诱导和交叉口信号控制的集成模型,在此模型框架下,对交叉口的控制与动态诱导分别建立优化模型,但前提是要求已知网络中各路段的交通流量.
徐丽群等人[34]研究了信号控制对动态路径选择的影响:路段行驶时间越长,交叉口的延误也越长.刘灿齐[35]讨论了路网交叉口不同分流向延误时间下的最短路径算法.
路径诱导系统和信号控制系统的集成研究有很强的应用背景.目前有关研究大多建立在动态交通分配的概念上,而动态交通分配要求的条件很强,其在交通控制中的应用一度遭到专家质疑[36].总之,路径诱导与信号控制的集成研究还处于起步阶段,还有很长的路要走.
5 结论与展望
智能交通系统中的路径诱导系统是一个复杂的系统工程,具有很强的理论和实现上的挑战性.路径诱导算法的实时性、动态路径诱导算法以及路径诱导与交通控制的集成是目前路径诱导算法研究的三个主要方向.然而作为智能交通系统的一个重要子系统,路径诱导系统除了必须具有良好的实时性、动态性和集成性之外,还必须对其他与其实施运营密切相关的众多问题从和谐系统层面加以综合协调考虑,例如出行者的出行偏好、管理层的硬性控制策略,以及环境保护等诸多复杂因素,才能充分发挥诱导系统的实际作用.这些领域目前尚未引起人们的太多注意,研究工作亦相对较少.
纵观路径诱导算法研究进展现状,结合智能交通系统的实际,可以提出值得继续深入研究的几个新方向:
1)结合出行者的心理特征模型建立路径诱导算法.路径诱导是一个对实时性要求相当强的系统,过分追求模型的精确和复杂并没有多大帮助.描述交通网络的模型越复杂,算法的灵敏性就会减弱,最优路径的求解复杂度也越大,计算中的省略误差通常也越大,这些都会降低模型精确带来的优势.如果算法不能满足实时性要求,则无论其效果如何终将无法被用户所接受.实际上出行者一般最关心的是诱导系统的方案是否在心理可承受或满意范围之内,而不是诱导方案是否一定是数学意义上的最佳.建立在出行者出行心理特征模型基础上的诱导方案不仅能减轻建模的负担,而且还会大大降低系统计算时间.因此有效的路径诱导系统在建模过程应当认真考虑使用者的心理状况,如出行者对什么方式的诱导认定有效,出行者对诱导指令的心理接受极限,这是路径诱导系统走向实用的重要步骤.
2)发展基于多目标优化的路径诱导算法.目前路径诱导方案大多是采用距离最短或时间最短等单一的指标,而实际上人们的出行习惯很难归结为单指标优化问题.出行者除了对时间有要求外,还希望在舒适感上得到满足,例如尽量减少转弯的次数,尽量不进入路况较差的道路等;对于司机路径选择行为进行的调查也表明大多数的司机也并不是趋向时间最短的路经,而是那些包含一些其他因素的次优路径,如熟悉程度、道路等级、连接性等,这实际就是一个多目标优化问题.传统的最优路径算法做不到这些,因为他们没有包含所需的路网信息.
3)继续加强对路段交通量预测的研究.路段交通量的预测结果通常是动态路径诱导算法的实现依据.目前的预测手段一般只能预测短时段后的情况,而交通诱导行为往往发生在比较大的空间范围,这样就可能跨越多个预测区段.研究表明交通流特性呈现复杂的混沌特性[37],如何实现对交通量在一个较长时间区域的预测将是非常有挑战性的问题,可以考虑引入递阶变时域滚动优化策略[38].此外基于实时交通状况的切换式路径诱导系统至少要有区别正常的交通波动和异常波动的能力.
4)发展提供更多智能化服务的路径诱导系统.人们对智能交通系统的希望很高,希望智能路径诱导系统能提供很多人性化的服务.Adler等人[39]详细论述了下一代智能诱导体系中能实现的各种智能化服务,例如有特定路径要求的优化导航[40],自动识别司机路径选择习惯等.智能化的路径诱导系统无疑将极大地增加它对人们的吸引力.
5)在分布式人工智能框架体系上建立路径诱导系统.交通网络作为一个典型的对象不确定、随机性强、实时性要求高、同时拓扑结构复杂分散的动态
823
第6期李威武,等:智能交通系统中路径诱导算法研究进展
大系统,对其进行车辆诱导研究必须考虑这些实际特征.基于中央监控或者完全分布式的多智能体的交通诱导体系[41],结构上易于实现系统间的信息共享,有利于信号灯控制和车辆路径诱导的一体化.分布式的结构能很好地缓解诱导系统中运算过于集中很好计算负荷大的问题.同时多智能体心智模型亦非常有利于表达出行者的心理特征,适合于建立出行者的出行心理模型.此外多智能体间的协作协商机制有助于解决多目标优化中的目标冲突问题.因此可以预见,这种构建在分布式人工智能基础之上的路径诱导系统必将越来越引起重视,在智能交通系统中发挥重要作用.
参考文献(References):
[1]杨兆升.城市交通流诱导系统理论与模型[M].北京:
人民交通出版社,2000.
[2]赵亦林,谭国真.车辆定位与导航系统[M].北京:电子
工业出版社,1999.
[3]区海涛,张文渊,张卫东,等.城市交通控制研究的新
发展[J].信息与控制,2000,29(5):441453.
O U H ai-tao,ZH A NG Wen-yuan,ZH A NG Wei-do ng,
et a l.N ew tr end tow ard ur ban traffic contr ol[J].
Informatio n and Control,2000,29(5):441453.
[4]K A U FM A N D E.A mix ed integ er linear pro gr amming
mo del fo r dy namic r oute g uidance[J].Transpo rtation Research B,1998,32(6):431440.
[5]ZH AN F B,N O ON C E.Sho r test pa th A lg orithms:A n
Evaluation using r eal road netw or ks[J].Transpo rtation Science,1998,32(1):6573.
[6]Z H AN F B.T hree sho rtest pa th alg o rithms o n r eal ro ad
ne tw o rks:Date structure and pro cedures[J].Jo urnal of
Geo graphic and Decision Analysis,1997,1(1):6982. [7]CHO U Y,RO M EIJN E,SM I T H R L.Appro ximating
shor te st paths in la rge-scale ne tw o rks with an applicatio n to IT S[J].INF ORMS Journal of Computing,
1998,10(2):163179.
[8]JAG A DEESH G R,S HRIN K T H A N T,Q U EK K H.
H euristic T echniques for A ccelerating H ier archical
Ro uting o n Road Ne two rks[J].IEEE Transactions on Intelligent Transportation Systems,2002,3(4):301
309.
[9]CHA N G W A,RA M A K RISH NA R S.A Genetic
A lg o rithm f or Sho rtest P ath Routing P roblem and the
Sizing o f Po pula tions[J].IEEE Transactions on Evolutionary Computatio n,2002,6(6):566579. [10]A H N C W,RAM AK RISH N A R S,K A NG C G,et
al.Sho r te st pa th routing algo rithm using H opfield
neural netw o rk[J].Electronics Letters,2001,37(19):
11761178.
[11]HU ANG Y W,NING J,RUN DENST EINER E A.A
hierarchical path view mo del for path finding in Intelligent
Transpo rtatio n Sy stems[J].Geo Inform atica,1997,1(2): 125159.
[12]FET T ERER A,SHEKHA R S.A perfo rmance analysis of
hierarchical shortest path algo rithms[A].Proceedings of
Ninth IEEE International C onference on Tools with
Artif icial Intelligence[C].New po r t Beach:IEEE
Compute r Society,1997,8493.
[13]CHSBIN I I.A new sho rt pa ths alg orithm fo r discrete
dy namic netw orks[A].Proceedings of8t h IFAC
symposium on Transport systems[C].Salfor d:Elsevier,
1997:551556.
[14]CHA BINI I.Discre te dy namic sho rtest path pro blems
in tr anspor tation applica tions:Comple xity a nd
alg o rithms with optimal r un time[J].Transportation
Research Records,1998,1645:170175.
[15]F U L P,L RIL ET T R.Expected sho rtest paths in
dy namic and stochastic traffic ne two rks[J].
Transportation Research B,1998,32(7):499516. [16]DEO N,PANG C Y.Shortest path alg orithms:taxo nomy
and annotatio n[J].Networks,1984,14:175323. [17]H A LL R.T he fa stest path thr ough a netw o rk with
rando m time-dependent tr avel time[J].Transportation
Science,1986,20(3):182188.
[18]LA M T N,T O NG C O.A dy namic route g uidance
sy stem based o n historical and cur rent tr affic pa ttern
[A].Proceedings of1992IEEE Intelligent Vehicles
Symposium[C].Detroit:Sag e Publicatio ns,1992: 365369.
[19]SU N G S K,JON G H L.A study on desig n of dy namic
r oute guidance sy stem using fo recasted tr avel time
based o n G PS da ta and modified sho r test path
algo rithm[A].Proceedings of1999IEEE/IEEJ/JSAI
International Conference on Intelligent Transportation
Systems[C].T okyo:IEEE,1999:4448.
[20]GA ET A N I F,M IN CID A RDI R.Dy namic models a nd
optimal contro l methods fo r ro ute g uidance in urban
tr affic ne tw o rks[A].Proceedings of IEEE5th
international co nference on intelligent transportation
systems[C].Sing apo re:I EEE,2002:454459. [21]K OBA YA SH I M A,SH IM IZ U H,YO NEZA W A Y.
Dy namic r oute search alg o rithms of a traffic ne tw o rk
[A].Proceedings of the36th SIC E Annual Conference
International Session Papers[C].T okushima:IEEE,
1997:12111216.
[22]苏永云,晏克非,杨晓光,等.VN S中动态行程时间与
多端动态最短路算法[J].中国公路学报,2001,14
824浙 江 大 学 学 报(工学版)第39卷
(1):97103.
S U Y ong-y un,YA N K e-fei,YA N G Xiao-guang,et
al.S tudy o f the alg orithm o f dy namic tr avel time and
multi-end sho rtest path in V N S[J].China Journal of
Highway and Transport,2001,14(1):97103. [23]F U L P.A n adaptive routing algo rithm fo r in-vehicle
r oute guidance sy stems w ith real-time infor matio n[J].
Transportation Research B,2001,35(8):749765. [24]S EN S,P IL LA I R,JOSH I S,et al.A mean-variance
mo del fo r route g uidance in advanced traveler
info rma tion sy stems[J].Transportation Science,2001,
35(1):3749.
[25]Z ILI ASK OP O U LO S A.A M assively parallel time-
depe ndent least-time-path alg orithm for intelligent
transpo rtation sy stem s applicatio ns[J].C omputer-
Aided Civil and Infrastructure Engineering,2001,16: 337346.
[26]WEN Huimin,YANG Zhaosheng.Study on the shor test
path algo rithm based o n fluid neural netw ork of in-vehicle
traffic flow guidance system[A].Proceedings of the IEEE
International Conference on V ehicle Electronics[C].
Changchung:I EEE,1999,1:110113.
[27]HE G uo-guang,M A Shou-feng.AI-based dy namic
route g uidance stra teg y and its simulatio n[A].
Proceedings of IEEE Intelligent Transportation Systems
Conference[C].Oakland:IEEE,2001:2832.
[28]王炜,徐吉谦,杨涛.城市交通规划理论及其应用
[M].南京:东南大学出版社,1998.
[29]Ho unsell N B,M CDON A L D M,LA M BERT R A.
T he integr atio n of SCOO T and dy namic route guidance
[A].Road Traffic Monitoring[C].L onton:IEEE,
1992:168172.
[30]徐岩宇,冯蔚东,贺国光.V RG S与交通控制系统的一
体化研究[J].公路交通科技,1997,14(3):2428.
X U Yan-yu,F ENG W ei-do ng,H E Guo-g ua ng.S tudy
o n the integ ra tion of VG RS and T CS[J].Jo urnal of
Highway and Transportation Research and Development,
1997,14(3):2428.
[31]莫汉康,彭国雄,云美萍.诱导条件下交通控制子区的
自动划分[J].交通运输工程学报,2002:2(2),6772.
M O Ha n-kang,PENG G uo-Xio ng,YU N M ei-ping.
Automa tic div isio n of traffic contro l sub-area under
co ndition of ro ute g uidance[J].Journal of Traffic and
Transportation Engineering,2002,2(2):6772. [32]M A Sho u-feng,H E Guo-g uang,WA NG Shi-tong.A
hie rarchical co or dination model fo r co ntrol-guidance
integ ra ted sy stem s in I T S[A].Proceedings of IEEE
International Conference on Intelligent Transportation
Systems[C].Sing apo re:I EEE,2002:522527. [33]JIA Lei,OZG U N ER U mit.Integ ratio n o f Dy namic
routing and inte rsection co ntrol in intellig ent
transpo rtatio n sy stem[A].Proceedings of2000IEEE
Intelligent Transportation Systems C onference[C].
Dea rbo rn:I EEE,2000:137142.
[34]徐丽群,杨兆升,贾正锐.信号控制对动态路径选择的
影响研究[J].中国公路学报,2000,13(2):99101.
X U Li-qun,YA NG Z hao-sheng,JIA Zheng-rui.Study
of influence o f sig nal contro l on dy namic r oute g uidance
[J].C hina Journal of Highway and Transport,2000,
13(2):99101.
[35]刘灿齐.车辆在交叉口分流向延误的最短路径及算法
[J].同济大学学报,2002,30(1):5256.
L IU Can-qi,Sho rtest pa th including delay of each f low
at inter sectio n and its alg o rithm[J].Journal of Tongji
University,2002,30(1):5256.
[36]杨清华,贺国光,马寿峰.对动态交通分配的反思[J].
系统工程,2000,18(1):4954.
Y AN G Qing-hua,HE Guo-g uang,M A Shou-feng,
T he opinio n on dy namic T raffic A ssig nment[J].
Systems Engineering,2000,18(1):4954.
[37]李英,刘豹,马寿峰.交通流时间序列中混沌特性判
定的替代数据方法[J].系统工程,2000,18(6):54
58.
L I Ying,LI U Bao,M A Shou-feng.T he identification
of chao s in traffic flow using sur rog ate-da ta technique
[J].Systems Engineering,2000,18(6):5458. [38]宋春跃,李平.递阶变时域滚动优化生产控制策略[J].
浙江大学学报:工学版,2004,38(12):16231628.
SON G Chun-y ue,L I Ping.O ptimal pro ductio n co nt rol
policy based on hierar chical va rying receding-ho rizon
[J].Journal of Zhejiang University:Engineering
Science,2004,38(12):16231628.
[39]AD LER J L,BL U E V J.T o wa rd the desig n o f the
intellige nt traveler info rmatio n sy stem s[J].
Transportation Research C,1998,6(3):157172. [40]K A NO H H,N AK A M U RA N.Ro ute g uida nce with
unspecified staging posts using g enetic algo rithm for
car navig atio n systems[A].Proceedings of IEEE
Intelligent Transportation Systems[C].O akland: IEEE,2000:119124.
[41]ADLER J L,BL UE V J A cooperative multi-agent
transportation management and route guidance system
[J].T ranspo rta tio n Resea rch C,2002,10(5):433
454.
825
第6期李威武,等:智能交通系统中路径诱导算法研究进展
.. .. 多元统计分析及R 语言建模考试试卷 一、简答题（共5小题，每小题6分，共30分） 1. 常用的多元统计分析方法有哪些？ （1）多元正态分布检验 （2）多元方差-协方差分析 （3）聚类分析 （4）判别分析 （5）主成分分析 ______________ 课程类别 必修[ ] 选修[ ] 考试方式 开卷[ ] 闭卷[ ]
（7）对应分析 （8）典型相关性分析 （ 9）定性数据建模分析 （10）路径分析（又称多重回归、联立方程） （11）结构方程模型 （12）联合分析 （13）多变量图表示法 （14）多维标度法 2. 简单相关分析、复相关分析和典型相关分析有何不同？并举例说明之。 简单相关分析：简单相关分析是研究现象之间是否存在某种依存关系，并对具体有依存关系的现象探讨其相关方向以及相关程度，是研究随机变量之间的相关关系的一种统计方法。例如，以X、Y分别记小学生的数学与语文成绩，感兴趣的是二者的关系如何，而不在于由X去预测Y。 复相关分析；研究一个变量 x0与另一组变量 (x1,x2,…，xn)之间的相关程度。例如,职业声望同时受到一系列因素（收入、文化、权力……）的影响，那么这一系列因素的总和与职业声望之间的关系，就是复相关。复相关系数R0.12…n的测定，可先求出 x0对一组变量x1，x2，…，xn的回归直线，再计算x0与用回归直线估计值悯之间的简单直线回归。复相关系数为R0.12…n的取值围为0≤R0.12…n≤1。复相关系数值愈大，变量间的关系愈密切。 典型相关分析就是利用综合变量对之间的相关关系来反映两组指标之间的整体相关性的多元统计分析方法。它的基本原理是：为了从总体上把握两组指标之间的相关关系，分别在两组变量中提取有代表性的两个综合变量U1和V1（分别为两个变量组中各变量的线性组合），利用这两个综合变量之间的相关关系来反映两组指标之间的整体相关性。
习题2-1 求下列函数的渐进表达式： 3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。 解答：3n^2+10n=O(n^2), n^2/10+2^n=O(2^n), 21+1/n=O(1), logn^3=O(logn), 10log3^n=O(n). 习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。 解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2 、20n、n^2/3、logn、2 习题2-4 (1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？ (2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？ (3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？ 解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6 (2)n1^2=64n^2得到n1=8n (3)由于T（n)=常数，因此算法可解任意规模的问题。 习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？ 解答：n'=100n n'^2=100n^2得到n'=10n n'^3=100n^3得到n'=4.64n n'!=100n!得到n' 摘要：主要介绍最短路径问题中的经典算法——迪杰斯特拉(Dijkstra)算法和弗洛伊德（Floyd）算法，以及在实际生活中的运用。 关键字：Dijkstra算法、Floyd算法、赋权图、最优路径、Matlab 目录 摘要 (1) 1引言 (1) 2最短路 (2) 2.1 最短路的定义 (2) 2.2最短路问题常见算法 (2) 3 Dijkstra算法 (2) 3.1Dijkstra算法描述 (2) 3.2 Dijkstra算法举例 (3) 3.3算法的正确性和计算复杂性 (5) 3.3.1贪心选择性质 (5) 3.3.2最优子结构性质 (6) 3.3.3 计算复杂性 (7) 4 Floyd算法 (7) 4.1Floyd算法描述 (8) 4.2 Floyd算法步骤 (11) 4.3 Floyd算法举例 (11) 5 Dijkstra算法和Floyd算法在求最短路的异同 (11) 6 利用计算机程序模拟算法 (11) 7 附录 (11) 8 论文总结 (13) 9 参考文献 (13) 1 引言 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。 2 最短路 2.1 最短路的定义 对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图 的有效算法是由荷兰著名计算机专家E.W.Dijkstra 在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G 中一特定点到其它各顶点的最短路。后来海斯在Dijkstra 算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford 提出了Ford 算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的() 0ij w ≥的情况下选择Dijkstra 算法。 定义1若图G=G(V,E)中各边e 都赋有一个实数W(e),称为边e 的权,则称这种图为赋权图,记为G=G(V,E,W)。 定义2若图G=G(V,E)是赋权图且()0W e ≥,()e E G ∈,假设[i,j] 的权记为()i j W ，,若i 与j 之间没有边相连接，那么()i j =W ∞，。路径P 的定义为路径中各边的长度之和，记W （P ）。图G 的结点u 到结点v 距离记为d(u,v)，则u 、v 间的最短路径可定义为 { ()min P 0d(u,v)=,u v W =∞（），不可达时 。 2.2 最短路问题常见算法 在求解网络图上节点间最短路径的方法中,目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。这两种算法中,网络被抽象为一个图论中定义的有向或无向图,并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径。 Dijkstra 算法是图论中确定最短路的基本方法,也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径,通常采用两种方法。一种方法是每次以一个结点为源点,重复执行Dijkstra 算法n 次。另一种方法是由Floyd 于1962年提出的Floyd 算法,其时间复杂度为 ()3O n ,虽然与重复执行Dijkstra 算法n 次的时间复杂度相同,但其形式上略为简单,且实际运 算效果要好于前者。 3 Dijkstra 算法 3.1 Dijkstra 算法描述 李委明十大速算技巧 ★【速算技巧一：估算法】 “估算法”毫无疑问是资料分析题当中的速算第一法，在所有计算进行之前必须考虑能否先行估算。所谓估算，是在精度要求并不太高的情况下，进行粗略估值的速算方式，一般在选项相差较大，或者在被比较数据相差较大的情况下使用。估算的方式多样，需要各位考生在实战中多加训练与掌握。 进行估算的前提是选项或者待比较的数字相差必须比较大，并且这个差别的大小决定了“估算”时候的精度要求。 ★【速算技巧二：直除法】 李委明提示： “直除法”是指在比较或者计算较复杂分数时，通过“直接相除”的方式得到商的首位（首一位或首两位），从而得出正确答案的速算方式。“直除法”在资料分析的速算当中有非常广泛的用途，并且由于其“方式简单”而具有“极易操作”性。 “直除法”从题型上一般包括两种形式： 一、比较多个分数时，在量级相当的情况下，首位最大/小的数为最大/小数； 二、计算一个分数时，在选项首位不同的情况下，通过计算首位便可选出正确答案。 “直除法”从难度深浅上来讲一般分为三种梯度： 一、简单直接能看出商的首位； 二、通过动手计算能看出商的首位； 三、某些比较复杂的分数，需要计算分数的“倒数”的首位来判定答案。 【例1】中最大的数是（）。 【解析】直接相除：＝30＋，＝30-，＝30-，＝30-， 明显为四个数当中最大的数。 【例2】32409/4103、32895/4701、23955/3413、12894/1831中最小的数是（）。 【解析】 32409/4103、23955/3413、12894/1831都比7大，而32895/4701比7小， 因此四个数当中最小的数是32895/4701。 李委明提示： 即使在使用速算技巧的情况下，少量却有必要的动手计算还是不可避免的。 【例3】6874.32/760.31、3052.18/341.02、4013.98/447.13、2304.83/259.74中最大的数是（）。 【解析】 在本节及以后的计算当中由于涉及到大量的估算，因此我们用a+表示一个比a大的数，用a-表示一个比a小的数。只有6874.32/760.31比9大，所以四个数当中最大的数是6874.32/760.31。 【例4】5794.1/27591.43、3482.2/15130.87、4988.7/20788.33、6881.3/26458.46中最大的数是（）。【解析】本题直接用“直除法”很难直接看出结果，我们考虑这四个数的倒数： 27591.43/5794.1、15130.87/3482.2、20788.33/4988.7、26458.46/6881.3， 利用直除法，它们的首位分别为“4”、“4”、“4”、“3”， 所以四个倒数当中26458.46/6881.3最小，因此原来四个数当中6881.3/26458.46最大。 【例5】阅读下面饼状图，请问该季度第一车间比第二车间多生产多少？（） A.38.5％ B.42.8% C.50.1% D.63.4% 【解析】5632-3945/3945=1687/3945=0.4＋=40%+，所以选B。 壹 汽车整车振动诊断和校正<经验交流> 整车振动可分为轮胎和车轮振动、起步颤动、排气呼啸声、发动机点火振动、传动系振动等。诊断整车振动的基本步骤是识别振动原因，查找再现条件，确定消除方法。 一、振动的检查及分类 1、轮胎和车轮的检查 在新生产的车型上，轮胎侧部都模塑有轮胎性能条件（TPC）额定值，如图1所示。TPC的额定值为一组4位数字，靠近轮胎尺寸，前边有字母TPCSPKC。替换轮胎应该具有相同的TPC额定值。 检查轮胎和车轮的一些特征可以发现振动的原因。轮胎不正常磨损（如图示2示）、胎壁凸起、不合理的充气、弯曲的轮圈法兰都可能引起整车振动。轮胎和车轮的径向跳动规格如表1所示。 2、路试检查程序 路试的目的在于再现振动现象并找出改变和消除振动的条件。更重要的是，路试可以确定振动是否与发动机转速和车速有关。为了迅速、准确地完成路试，在车辆上安装上发动机转速表（如扫描工具）和小型电子振动分析仪（EV A）。将EV A传感器放在用户可以感受振动的地方。路试检查包括轮胎和车轮检查、缓慢加速测试、空档滑行减速测试、挂低档测试、空档升速测试、制动器转矩测试、转向机械输入测试和静止起步加速测试（起步颤动）。 （1）缓慢加速测试：缓慢加速测试的步骤是： 1）在平整的水平路面上，缓慢加速至公路行驶速度。 2）查找与用户描述相符的故障。 3）在出现振动时，观察车速、发动机转速，如果有可能观察振动频率。 （2）空档滑行测试：空档滑行测试的步骤是： 1）在平整的水平路面上，将速度提高到略高于振动出现的速度 2）将车辆挂上空档并滑行，体验振动速段。 3）观察挂空档时是否有振动。 如果挂空档时仍有振动，则振动肯定对车速十分敏感。此时，发动机、变速器挠性板、变矩器作为振源的可能已经排除，可按照症状或振动频率集中维修轮胎和车轮总成或变速器输入轴。 （3）挂低档测试：挂低档测试的步骤是： 1）在平整的水平路面上，将速度提高到略高于振动出现的速度。 2）减速并安全减低一档。 3）提高发动机转速到减速前时的转速。 如果在相同的发动机转速下振动再次出现，则发动机、变速器挠性板、变矩器便是最可能的振源。每次减一档并在空档重复本测试，对确认测试结果。 （4）空档高速测试：本测试是为识别与发动机车速相关的振动而设计的。当用户投诉车辆在怠速情况下发生振动时，可行进行该项测试，或者在挂低档测试后进行该项测试。如果用户抱怨的振动仅与车速有关，本测试不一定适用。测试时缓慢提高发动机转速，同时观察是 华南农业大学期末试卷（A 卷） 2006学年第2学期 考试科目：多元统计分析 考试类型：（闭卷） 考试时间：120 分钟 学号 姓名 年级专业 题号 一 二 三 四 五 六 七 八 总分 得分 评阅人 一、填空题（5×6=30） 22121212121~(,),(,),(,),, 1X N X x x x x x x ρμμμμσρ ?? ∑==∑= ???+-1、设其中则Cov(,)=____. 10 31 2~(,),1,,10,()()_________i i i i X N i W X X μμμ=' ∑=--∑、设则=服从。 ()1 2 34 433,4 92,32 16___________________ X x x x R -?? ?'==-- ? ?-? ? =∑、设随机向量且协方差矩阵则它的相关矩阵 4、 __________， __________， ________________。 215,1, ,16(,),(,) 15[4()][4()]~___________i p p X i N X A N T X A X μμμμ-=∑∑'=--、设是来自多元正态总体和分别为正态总体的样本均值和样本离差矩阵,则。 (), 123设X=x x x 的相关系数矩阵通过因子分析分解为 211X h = 的共性方差111 X σ = 的方差21X g =1公因子f 对的贡献121330.93400.1280.9340.4170.83511 00.4170.8940.02700.8940.44730.8350.4470.1032013 R ? ? - ????? ? -?? ? ? ?=-=-+ ? ? ? ??? ? ? ????? ? ??? 第17卷第2期 湖南城市学院学报（自然科学版）V ol.17 No.2 2008年6月 Journal of Hunan City University （Natural Science） Jun. 2008 公交最优路径选择的数学模型及算法 雷一鸣 （广东工业大学华立学院，广州 511325） 摘要：在公交出行查询系统中，最关键的部分是寻找两站点间乘车的出行最优路径问题．建立了以最小换乘次数为第一目标，最小途经站点为第二目标的公交出行最优路径模型．同时，设计了一种算法以确定最优公交线路序列，分析了线路相交的几种情况，给出了换乘点选择方法． 关键词：最优路径；换乘次数；公交网络 中图分类号：O232文献标识码：A文章编号：1672–7304(2008)02–0050–03 公交最优路径问题一直是应用数学、运筹学、计算机科学等学科的一个研究热点．对公交最优路径问题的理论研究主要包括公交网络的数学描述和设计最优路径算法．在公交网络描述方面，Anez等用对偶图描述能够涵盖公交线路的交通网络，Choi等讨论了利用GIS技术从街道的地理数据产生公交线路和站点的问题；在设计最优算法方面，常用的算法[1]有Dijkstra算法、Floyd 算法、Moore-pape算法等．Moore-pape算法计算速度较快，适用于大型网络，但它无法进行“一对一”的计算．Floyd算法虽然可以快速地进行“多对多”的计算，但它不能应用于大型网络，而Dijkstra算法是目前公认的最好的算法，但它数据结构复杂、算法时间长，不适合公交线路的查询．本文首先对公交网络进行了数学描述，考虑到公交乘客出行时所面临的各种重要因素，包括换乘次数、途径站点、出行耗时和出行费用等，选择以换乘次数最少作为最优路径算法的第一约束目标，而出行耗时虽难以准确测算但它与途径站点数相关，所以选择易于量化的途经站点数最少作为第二约束目标，建立公交乘车数学模型，设计相应的算法，并利用有关实验数据验证了它的有效性和可行性． 1 模型的建立及其算法 1.1 模型假设及符号规定 为了更好地建立数学模型，首先对公交网络及出行者作出以下假设[2]： 1)不考虑高峰期、道路交通堵塞等外界因素对乘车耗时的影响． 2)假设出行者熟悉公交站点及附近地理位置，并且知道可乘的各种公汽和地铁以及到达目的地有哪几种不同选择的机会．在公交线路网中， 不同的公交线路在行程上一定会有重叠，也就是说不同的线路上一定会有同名站点．在进行网络分析时，把空间上相近的异线同名站点合理抽象成一个节点． 3)假设出行者对公汽和地铁的偏好程度不一样．在不换乘的情况下，宁愿乘地铁，以求舒适；在路途较近的情况下，宁愿坐公汽而放弃乘地铁．出行者可根据自己的偏好结合自己的出行需求（换乘次数、最短路程、费用等），可在各种出行方案中选出满足自己出行需求的乘车方案．设() L I为经过点A或其附近的公交线路集，其中1,2,..., I m =；() S J为经过点B或其附近的公交线路集，其中,,..., J12n =；(,) E I U为线路 ) (I L上的站点，其中,,..., U12p =；(,) F J V为线路) (J S上的站点，其中,,..., V12q =；() X K为经过站点) ,(U I E的线路，其中,,..., K12w =；() Y O 为经过站点) , (V J F的线路，其中,,..., O12v =；(,) d E F M ≤表示从站点E步行到站点F之间的距离不超过乘客换车时步行的最大心理承受值M，其中M表示乘客在换车时步行的最大心理承受值．通常，M与公交站点间的平均距离呈线性正相关． Ai Z表示站点A的下行第i个站点； Bj Z表示站点B的上行第j个站点；另外，公交的可行线 路的集合可表示为：{| i i TR TR TR == 0112,1 ,,,,,, i i i i d a p a p a ? < ,} id d p a>，其中，{} 01,1 ,,,, i i d d a a a a ? 为站点集合，{} 12,1 ,,,, i i i d d p p p p ? 为公交车次的集合， i TR 收稿日期：2008-03-10 作者简介：雷一鸣(1972-)，男，湖南临武人，助教，硕士，主要从事数学模型及经济信息管理研究． ★【速算技巧一：估算法】 “估算法”毫无疑问是资料分析题当中的速算第一法，在所有计算进行之前必须考虑能否先行估算。所谓估算，是在精度要求并不太高的情况下，进行粗略估值的速算方式，一般在选项相差较大，或者在被比较数据相差较大的情况下使用。估算的方式多样，需要各位考生在实战中多加训练与掌握。 进行估算的前提是选项或者待比较的数字相差必须比较大，并且这个差别的大小决定了“估算”时候的精度要求。 ★【速算技巧二：直除法】 李委明提示： “直除法”是指在比较或者计算较复杂分数时，通过“直接相除”的方式得到商的首位（首一位或首两位），从而得出正确答案的速算方式。“直除法”在资料分析的速算当中有非常广泛的用途，并且由于其“方式简单”而具有“极易操作”性。 “直除法”从题型上一般包括两种形式： 一、比较多个分数时，在量级相当的情况下，首位最大/小的数为最大/小数； 二、计算一个分数时，在选项首位不同的情况下，通过计算首位便可选出正确答案。 “直除法”从难度深浅上来讲一般分为三种梯度： 一、简单直接能看出商的首位； 二、通过动手计算能看出商的首位； 三、某些比较复杂的分数，需要计算分数的“倒数”的首位来判定答案。 【例1】56 .10134.489294.13343.559310.7454.813222.0349.738、、、中最大的数是（ ）。 【解析】直接相除： 30.2294.837＝30＋，10.7454.8132＝30-，94.13343.5593＝30-，56.10134.4892＝30-， 明显3 0.2294.837为四个数当中最大的数。 【例2】32409/4103、32895/4701、23955/3413、12894/1831中最小的数是（ ）。 【解析】 32409/4103、23955/3413、12894/1831都比7大，而32895/4701比7小， 因此四个数当中最小的数是32895/4701。 李委明提示： 即使在使用速算技巧的情况下，少量却有必要的动手计算还是不可避免的。 【例3】6874.32/760.31、3052.18/341.02、4013.98/447.13、2304.83/259.74中最大的数是（ ）。 1在本节及以后的计算当中由于涉及到大量的估算，因此我们用a+表示一个比a 大的数， 附件1 汽车发动机振动噪声测试系统 1用途及基本要求： 该设备主要用于教学和科研中的振动和噪声测量，要求能够测量试验对象的振动噪声特性（频率、阶次、声强等），能对试验数据进行综合分析。该产品的生产厂应具有多年振动噪声行业从业经验，有较高的知名度和影响力。系统软件和硬件应该为成熟的模块化设计，同时具有很强的扩展能力，能保证将来软件和硬件同时升级。 2设备技术要求及参数 2.1设备系统配置 2.1.1数据采集系统一套； 2.1.2数据测试分析软件一套； 2.1.3传声器 2个； 2.1.4加速度计 2个； 2.1.5声强探头 1套； 2.1.6声级校准器 1个； 2.1.7笔记本电脑一台 2.2数据采集、控制系统技术要求 2.2.1主机箱一个；供电采用9～36V直流和 200～240V交流； 2.2.2便携式采集前端，适用于实验室及现场环境； 2.2.3整机消耗功率<150W； 2.2.4工作环境温度：-10?C ～50?C； 2.2.5中文或英文WindowsXP下运行，操作主机采用笔记本电脑； 2.2.6输入通道数：4个以上，其中2个200V极化电压输入通道、不少一个转速输入通道； 2.2.7输入通道拥有Dyn-X技术，动态围160dB； 2.2.8每通道最高采样频率：≥65.5kHz，最大分析带宽：≥25.6kHz； 2.2.9系统留有扩充板插槽，根据需要可以进一步扩充；数据采集前端可同时连接多种形式传感器,包括加速度计、转速探头、传声器、声强探头等； 2.2.10系统具有堆叠和分拆能力，多个小系统可组成多通道大系统进行测量。大系统可分拆成多个小系统独立运行； 2.2.11采集前端的数据传输具备二种方式之一：①通过10/100M自适应以太网传输至PC； ②通过无线通讯以太网技术传输至PC，通信距离在100米以上。使测量过程更为灵活方便，方便硬件通道和计算机系统扩展升级； 一、填空题： 1、多元统计分析是运用数理统计方法来研究解决多指标问题的理论和方法. 2、回归参数显著性检验是检验解释变量对被解释变量的影响是否著. 3、聚类分析就是分析如何对样品（或变量）进行量化分类的问题。通常聚类分析分为 Q型聚类和 R型聚类。 4、相应分析的主要目的是寻求列联表行因素A 和列因素B 的基本分析特征和它们的最优联立表示。 5、因子分析把每个原始变量分解为两部分因素：一部分为公共因子，另一部分为特殊因子。 6、若 () (,), P x N αμα ∑=1,2,3….n且相互独立，则样本均值向量x服从的分布 为_x~N(μ，Σ/n)_。 二、简答 1、简述典型变量与典型相关系数的概念，并说明典型相关分析的基本思想。 在每组变量中找出变量的线性组合，使得两组的线性组合之间具有最大的相关系数。选取和最初挑选的这对线性组合不相关的线性组合，使其配对，并选取相关系数最大的一对，如此下去直到两组之间的相关性被提取完毕为止。被选出的线性组合配对称为典型变量，它们的相关系数称为典型相关系数。 2、简述相应分析的基本思想。 相应分析，是指对两个定性变量的多种水平进行分析。设有两组因素A和B，其中因素A包含r个水平，因素B包含c个水平。对这两组因素作随机抽样调查，得到一个rc的二维列联表，记为。要寻求列联表列因素A和行因素B的基本分析特征和最优列联表示。相应分析即是通过列联表的转换，使得因素A 和因素B 具有对等性，从而用相同的因子轴同时描述两个因素各个水平的情况。把两个因素的各个水平的状况同时反映到具有相同坐标轴的因子平面上，从而得到因素A 、B 的联系。 3、简述费希尔判别法的基本思想。 从k 个总体中抽取具有p 个指标的样品观测数据，借助方差分析的思想构造一个线性判别函数 系数： 确定的原则是使得总体之间区别最大，而使每个总体内部的离差最小。将新样品的p 个指标值代入线性判别函数式中求出 值，然后根据判别一定的规则，就可以判别新的样品属于哪个总体。 5、简述多元统计分析中协差阵检验的步骤 第一，提出待检验的假设 和H1； 第二，给出检验的统计量及其服从的分布； 第三，给定检验水平，查统计量的分布表，确定相应的临界值，从而得到否定域； 第四，根据样本观测值计算出统计量的值，看是否落入否定域中，以便对待判假设做出决策（拒绝或接受）。 协差阵的检验 检验0=ΣΣ 0p H =ΣI ： /2 /21exp 2np n e tr n λ???? =-?? ? ???? S S 00p H =≠ΣΣI ： /2 /2**1exp 2np n e tr n λ???? =-?? ? ???? S S 摘要 供货小车的路径优化是企业降低成本,提高经济效益的有效手段,供货小车路径优化问题可以看成是一类车辆路径优化问题。 本文对供货小车路径优化问题进行研究，提出了一种解决带单行道约束的车辆路径优化问题的方法。首先，建立了供货小车路径优化问题的数学模型，介绍了图论中最短路径的算法—Floyd算法，并考虑单行道的约束，利用该算法求得任意两点间最短距离以及到达路径，从而将问题转化为TSP问题，利用遗传算法得到带单行道约束下的优化送货路线，并且以柳州市某区域道路为实验，然后仿真，结果表明该方法能得到较好的优化效果。最后对基本遗传算法采用优先策略进行改进，再对同一个供货小车路径网进行实验仿真，分析仿真结果，表明改进遗传算法比基本遗传算法能比较快地得到令人满意的优化效果。 关键字:路径优化遗传算法 Floyd算法 Abstract The Path Optimization of Goods Supply Car is the effective way to reduce business costs and enhance economic efficiency.The problem of the Path Optimization of Goods Supply Car can be seen as Vehicle routing proble. This paper presents a solution to Vehicle routing proble with Single direction road by Researching the Way of Path Optimization of Goods Supply Car. First, This paper Establish the mathematics model of Vehicle routing proble and introduced the shortest path algorithm-Floyd algorithm, then taking the Single direction road into account at the same time. Seeking the shortest distance between any two points and landing path by this algorithm,then turn this problem in to TSP. Solving this problem can get the Optimize delivery routes which with Single direction road by GA,then take some district in the state City of LiuZhou road as an example start experiment.The Imitate the true result showed that this method can be better optimize results. Finally improving the basic GA with a priority strategy,then proceed to imitate the true experiment to the same Path diagram. The result expresses the improvement the heredity calculate way ratio the basic heredity calculate way can get quickly give satisfaction of excellent turn the result. Keyword: Path Optimization genetic algorithm Floyd algorithm 《多元统计分析》课程试卷答案 A 卷 2009年秋季学期 开课学院：理 考试方式：√闭卷、开卷、一纸开卷、其它 考试时间：120 分钟 班级 姓名 学号 散卷作废。 一、（15分）设()∑????? ??=,~3321μN x x x X ，其中????? ??-=132μ，??? ? ? ??=∑221231111， 1．求32123x x x +-的分布； 2. 求二维向量???? ??=21a a a ，使3x 与??? ? ??'-213x x a x 相互独立。 解：1.32123x x x +-()CX x x x ???? ? ? ??-=321123，则()C C C N CX '∑,~μ。（2分） 其中：μC ()13132123=????? ??--=，()9123221231111123=??? ? ? ??-????? ??-='∑C C 。（4分） 所以32123x x x +-()9,13~N （1分） 2. ????? ?????? ??'-213 3x x a x x =AX x x x a a ????? ? ?????? ??--3212 1110 ，则()A A A N AX '∑,~2μ。（1分） 其中： 订 线 装 μA ???? ??++-=???? ? ??-???? ??--=132113********* a a a a ，（1分） ??? ? ??+--+++--+--='???? ??--???? ? ?????? ??--='∑242232222211002212311111100 2121222121212121 a a a a a a a a a a a a a a A A （2分） 要使3x 与???? ??'-213x x a x 相互独立，必须02221=+--a a ，即2221=+a a 。 因为2221=+a a 时24223212122 21 +--++a a a a a a 0>。所以使3x 与??? ? ??'-213x x a x 相互独立，只要 ???? ??=21a a a 中的21,a a 满足2221=+a a 。 （4分） 二、（14分）设一个容量为n=3的随机样本取自二维正态总体，其数据矩阵为 ??? ? ? ??=3861096X ，给定显著性水平05.0=α， 1. 求均值向量μ和协方差矩阵∑的无偏估计 2. 试检验,38:H 0???? ??=μ .38:H 1??? ? ??≠μ （已知F 分布的上α分位数为19)2,2(F ,5.199)1,2(F ,51.18)2,1(F 0.050.050.05===） 解：1、??? ? ??==∑=68X n 1X n 1i i （3分） ???? ??--='--=∑=9334)X X ()X X (1-n 1S i n 1i i （3分） 2、,38:H 0???? ??=μ .38:H 1??? ? ??≠μ…（1分） 解决方案一： Dijkstra算法（单源最短路径） 单源最短路径问题，即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前，必须弄清楚最短路径的最优子结构性质。 一.最短路径的最优子结构性质 该性质描述为：如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。 假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，则有 P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j) 机器人的路径规划---蚁群算法 1.蚁群算法 众所周知，蚁群算法是优化领域中新出现并逐渐引起重视的一种仿生进化算法它是群体智能的典型实现，是一种基于种群寻优的启发式搜索算法。自从M．Dorigo等意大利学者在1991年首先提出蚁群算法(Ant Colony System，ACS)以来，这种新型的分布式智能模拟算法已逐渐引起人们的注意并得到广泛的使用。 蚁群算法的特点主要表现在以下五个方面： (1)蚂蚁群体行为表现出正反馈过程。蚁群在寻优的过程中会释放一定量的信息素，蚁群的规模越大，释放的信息素的量也就越大，而寻优路径上存在的信息素浓度越高，就会吸引更多的蚂蚁，形成一种正反馈机制，然后通过反馈机制的调整，可对系统中的较优解起到一个自增强的作用，从而使问题的解向着全局最优的方向演变，最终能有效地获得全局相对较优解。 (2)蚁群算法是一种本质并行的算法。个体之间不断进行信息交流和传递．有利于最优解的发现，并在很大程度上减少了陷于局部最优的可能。 (3)蚁群算法易于和其他方法结合。蚁族算法通过和其他算法的结合，能够扬长避短，提高算法的性能。 (4) 蚁群算法提供的解具有全局性的特点。一群算法是一种群只能算法，每只蚂蚁巡游的过程相对独立，他们会在自己的活动空间进行搜索，蚂蚁在寻优过程中通过释放信息素，相互影响，互相通信，保证了解的全局性。 (5) 蚁群算法具有鲁棒性。蚁族算法的数学模型易于理解，可以广泛使用在很多复杂的优化问题中，蚁族算法区别于传统优化算法的一个特点在于该算法不依赖于初始点的选择，受初始点的影响相对较小，并且在整个算法过程中会自适应的调整寻优路径。 由此可见，在机器人寻找最优路径的过程中，采用蚁群算法实现路径的规划问题，可以高效，准确的找到最优的路径。 2.移动机器人的路径规划 2.1环境信息处理 假设机器人运行环境为边长分别为x和Y的矩形区域，在矩形区域内分布有n 资料分析速算技巧 “差分法”是在比较两个分数大小时，用“直除法”或者“化同法”等其他速算方式难以解决时可以采取的一种速算方式。 适用形式： 两个分数作比较时，若其中一个分数的分子与分母都比另外一个分数的分子与分母分别仅仅大一点，这时候使用“直除法”、“化同法”经常很难比较出大小关系，而使用“差分法”却可以很好地解决这样的问题。 基础定义： 在满足“适用形式”的两个分数中，我们定义分子与分母都比较大的分数叫“大分数”，分子与分母都比较小的分数叫“小分数”，而这两个分数的分子、分母分别做差得到的新的分数我们定义为“差分数”。例如：324/53.1与313/51.7比较大小，其中324/53.1就是“大分数”，313/51.7就是“小分数”，而324-313/53.1-51.7=11/1.4就是“差分数”。 “差分法”使用基本准则—— “差分数”代替“大分数”与“小分数”作比较： 1、若差分数比小分数大，则大分数比小分数大； 2、若差分数比小分数小，则大分数比小分数小； 3、若差分数与小分数相等，则大分数与小分数相等。 比如上文中就是“11/1.4代替324/53.1与313/51.7作比较”，因为11/1.4＞313/51.7（可以通过“直除法”或者“化同法”简单得到），所以324/53.1＞313/51.7。 特别注意： 一、“差分法”本身是一种“精算法”而非“估算法”，得出来的大小关系是精确的关系而非粗略的关系； 二、“差分法”与“化同法”经常联系在一起使用，“化同法紧接差分法”与“差分法紧接化同法”是资料分析速算当中经常遇到的两种情形。 三、“差分法”得到“差分数”与“小分数”做比较的时候，还经常需要用到“直除法”。 四、如果两个分数相隔非常近，我们甚至需要反复运用两次“差分法”，这种情况相对比较复杂，但如果运用熟练，同样可以大幅度简化计算。 【例1】比较7/4和9/5的大小 【解析】运用“差分法”来比较这两个分数的大小关系： 大分数小分数 9/5 7/4 9－7/5－1=2/1(差分数) 根据：差分数=2/1＞7/4=小分数 因此：大分数=9/5＞7/4=小分数 李委明提示： 使用“差分法”的时候，牢记将“差分数”写在“大分数”的一侧，因为它代替的是“大分数”，然后再跟“小分数”做比较。 汽车的振动测试技术-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII 汽车的振动测试技术 汽车供应商们采用先进的振动测试技术来保证汽车在行驶中的安静和平稳。汽车上的零件和组装件必须经受振动可控测试技术的检验。 汽车内部从仪表板到桌椅，从安全气囊传感器到引擎注油泵，诸多零部件都要经过精确振动模式和幅度的测试。 在有些情况下，要用振动测试法验证汽车的各种装置在一般路面条件下不会损坏。在另一些情况下，通过振动测试来识别机械发出的烦人的噪声。 在振动控制的工业中，开发成功的数字信号处理技术有可能在实验室和生产线上制造成更加贴近真实的振动环境。今天，振动测试除了使用随机波、正弦波和冲击波的传统方法，又增加了更加复杂的方法，比如随机波上加正弦波和波形复制。 正如名称所示，随机正弦波是把随机振动与正弦波结合起来形成复杂的振动形式；波形复制振动模仿出真实的汽车振动环境。随机正弦波振动把多个正弦波与具有宽频带的噪声结合在一起。正弦波振动可以是固定的或者是扫描式的谐波或非谐波振动，而且在整个频带内的振动幅度是可变的。就模仿在路面变化行驶中的随机振动的汽车来说，其引擎转速增加或减少时，随机正弦波振动是很好的测试方法。 实际应用 采用随机正弦波振动和波形复制方法对汽车进行测试，可真实地再现汽车行驶中的实际环境，用作设计验证和质量控制。 ?仪表板 许多汽车制造厂对仪表板组件进行振动测试以检查其发出的咯吱声和卡嗒声。这一项是新车购买者可能最不满意的地方，在保证金中占很大份额。 为了测试建造了专用振动台，它不使用风扇，为的是造成清静的环境来验证振动中的仪表板是否有咯吱声和卡嗒声。因为没有通风散热，只能在温升超过工作温度时做短时间的振动测试，然后测试要暂停一会儿让设备冷却下来。 除振动台外，所有能发出噪声的仪器设备，包括振动台的控制器都应放在测试室的列边。遥控面板和显示器要悬挂在测试装置的上面，便于工作人员能听见噪声并控制测试过程。 用于检验咯吱声和卡嗒声的振动模式，由随机波、扫描正弦波和代表负荷的多段波形所构成。其振动幅度要控制在汽车正常行驶中的额定实验值内。为了避免振动过于猛烈。要维修部件并做好紧固工作。 在振动测试中，操作人员起着关键性的作用，例如施加扫描式正弦波来重复加速引擎的振动模式，此时可能要加上几次扫频来发现异常的噪声。由于咯吱声和卡嗒声难于发现起因，操作者必须停止对仪表板做下一步的操作，并且用于动方式来控制振动频率和振幅，检查产生噪音的真正原因。这样才能找到产生噪声的机理，许多设备生产厂也采用这种方法作为质量控制的手段。最短路径学年论文
李委明十大速算技巧(完美修正版)
汽车整车振动诊断
多元统计分析试题及答案
公交最优路径选择的数学模型及算法_雷一鸣
李委明十大速算技巧(完整版)
汽车发动机振动噪声测试实用标准系统
应用多元统计分析试题及答案
路径优化的算法
秋季多元统计分析考试答案
最优路径算法
蚁群算法最优路径
行测——资料分析速算技巧(附例题)
汽车的振动测试技术
相关主题
文本预览