资源描述：
《基于数字地图的多属性最优路径问题的算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、9一洲给借尾与工思JournalofGeomatics2003Aug.;28(4)文献标识码:1i文童编号1007-3817(2003)04-0009-02中图分类号:P208;TP751.2基于数字地图的多属性最优路径问题的算法研究王建宇许震洪周献中(南京理工大学自动化系，南京市幸陵卫200号210094)摘要以某地理信息系统的数字地图为背景，通过综合数字地图交通道路层的几个属性来设置权值并改善矩形A搜索区域算法，使之适用于地理信息系统下交通道路网的最优路径计算，提高了Dijkstra算法的效率。关扭词D
2、ijkstra算法;教字地图;最优路径;地理信息系统最优路径问题其实是一个很古老的问题。其原型是运筹f:f(e)=f(v,，vs),.f(,)f(",,)学中的最短路径间题，随着自身不断的发展，路径问题从建f(e)=f(*=，，，)，f(,)=f(,,·v,)立在图论仁的抽象网络上的模型的算法研究，逐步向现实生f(e)f(v,，?、)，)(e)=f(v=v)活，}了的实际模型的算法研究进行转变，使得最优路径算法广f(,)二f(v,)，f(e)=f(.?,，a)泛应用于互联网的寻址计算、智能交通系统(ITS)
3、,城市地理具体Dijkstra算法的基本原理和算法参见文献仁门其实信息系统以及军事地理信息系统中Di扭stra算法是一个全方位搜索的过程，节点数越多，相对而言，计算量就越大.道路网是可以建立在二维坐标中的，每个1核心获法节点可由坐标表示.必然每个节点也因此存在某种相对关在运筹学中，最短路径间题最经典的算法就是Dijkstra系实际上，道路本身还有一些属ft特征(等级，宽度等)而算法。Dijksva算法建立在抽象的网络模型上，把路线抽象Dijkstra算法没有充分利用道路网的这此特征，所以直接把为网络中的边，
4、以边的权值来表示相关的参数，算法确定了Dijkstra算法应用于道路网最优路径的计算是不妥的赋权网络中从某点到所有其他结点的具有最小权的路径，2改进Dijkstra算法Dijkstra算法是求解最小权问题的通用算法，它忽略了网络棋型的个体特性因此它的算法复杂度较高。值得注意的是2.I权位的确定Dijikstra算法描述的是算法的实现方法与网络的存储结构地理信息系统中的数字地图数据库提供了各种道路的无关，不同的实现方法决定了不同的时间复杂度现实世界属性的记录，有路段的等级、名称、长度、载重、宽度、质料〔沥的空
5、间地物各式各样，而道路网可以由点一线构成空间网青、水泥)、桥梁等.通过道路的属性，结合用户使用的交通工络，而且可用一个坐标系统来标识空间网络中的各点，网络具的类型，在起始点和终点之间选择一条能够最短时间到达中的线的权值可以表示路段的长度等属性。这种空间网络的路径，这里称为时间最优路径其实要实现真正意义的时可以表示为矢量化的网络模型“，‘可用有序三元组(V,凡间最优路径，需要综合各种动态实时信息(道路拥挤程度是f)表示.其中V是网络模5G的顶点集合，E是边集，而f是否有交通事故等)，计算过程非常复杂tzi所以
6、，这里的时间函数,.f(e)表示边。(eEE)的权值，也就是G中边，对应的最优路径算法是建立在道路信息基础上的为用户行驶路线顶点对(u,v)之间的包括距离在内的相关属性，因此f也可的进行一次静态的优化选择的计算U表示为f(u,v)例如，如图I所示的矢量化网络模型可以要计算时间最优路径，必须先知道用户可能的行驶速用G表示为(不失一般性，假设G位于二维坐标系统中)度根据实际经验(排除人为因素之外)很大程度上道路的状况和车辆的性能决定着车辆的行使速度。比如桑塔纳轿车的一般行驶速度，在高速公路上为100k./h-1
7、20km/h在一级公路上为80km/h--l00km/he所以根据道路的一些属性和车辆的类型，应该可以粗略地估算出车辆行驶速度假设某用户的使用交通工具为T,所需路段的载重为二·，而某段路长度为d道路等级为R+道路载重为W-，该用户的行使速度为V，如果通过该路段的时间为t，则有:V=f(T，二，e,Wm)(1)圈1矢且化网络桩型d/V(2)G=(V.E.f)这里规定只有当二(w二(4A果不考虑特殊情况应以不损V={刃卫。脚，巧，劝，饥全坏道路前提)，才有实际意义，二)W。，则V=。所以形，=(几+Y}),.1
8、,2,3,4.f(T,g).u簇WmV-(3)E={e,,ez.。:，。;，e，。。，，.eafO，切>W、二浏抢佑电与x粗.1(-.1ofGeomatics2003Aug.;28(4)需要说明的是.j(T.g)目前没有具体的数学式可表示.己二(z十ze)-2,L=(，一y升2但是通过对各种不同车辆在不同道路上的速度采样后进行A=过(y，一Y.Y+(1一1)2一’:2统计.建立简单的数据库.通过输人车辆的类IV.
