基于网络资源系统专线建设最短路径算法研究

1 引言 随着中国移动传输网络规模日趋庞大,网络资源的精细化管理显得尤为重要.2010年起中国移动全网建设网络综合资源管理系统,覆盖了14个专业200多类资源,实现了对全专业网络资源和信息服务资源的有效管理.系统建设初期,集客业务支撑是系统的一个主要服务方向,在资源管理系统建成前,客户经理在开展业务时不能及时获得客户资源的覆盖情况,有时业务谈妥但最终发现资源无法到达,导致客户丢失.

P2P网络架构的资源搜寻算法设计

结构化对等(P2P,Peer to Peer)架构的资源搜寻算法如Chord、CAN、Pastry等的提出,改变了非结构化P2P架构的泛洪式资源搜寻的方式,降低了P2P资源搜寻信息的流量,从而增强了系统的扩展性。但是以上算法均未考虑到节点间实际物理距离对搜寻路径长度的影响。文章提出一种基于节点能力和节点区域性的结构化搜寻算法,该算法综合了CBT和Grapes的优点并充分考虑到节点的区域性以及节点能力,从而构建了一个短搜寻路径能力集包容的P2P系统。

在MapInfo电子地图中搜寻最短路径的实现

根据MapInfo电子地图的特点,本文介绍了如何从电子地图中提取出交通道路及道路交汇点信息,并将其抽象成图,选择合适的结构进行存储,然后运用Dijkstra最短路径算法求解最短路径,根据求解结果在电子地图上绘制线路图。

基于公交网络的最短路径算法的分析及对比

路径分析是GIS最基本的分析功能,在公交网络方面有着广泛的应用。而最短路径分析是地理信息系统(GIS)中网络分析的一项重要功能.等价于图论中的节点间求解最短路径问题.在GIS应用的各个方面都有着很重要的地位。对于最短路径的研究也一直没有停止。对地理网络进行地理分析和建模.实现最短路径算法已经有大量论文讨论,但是专门针对公交网络的最短路径算法则鲜有研究.本文在总结公交网络特点的基础上,引入了"搜寻"算法来计算公共交通系统的最优路径。最后用一个简化的例子来说明了这种算法的算法流程,对这种算法以及经典的Dijstra算法做了几点比较,无论在空间复杂度还是时间复杂度方面都优于Dijstra算法。

基于城市道路数据库的最短路径搜索

在智能交通的导航/动态路线诱导系统中,最短路径搜寻是其重要功能.根据城市交通路网建设的实际,研究了描述城市交通网络图的城市道路数据库的组织结构.在此数据结构的基础上依靠GIS技术的支持,采集了大量具体道路信息,采用Dijkstra算法实现了快速最短路径搜索.根据城市的交通状况对交通网络图的边值赋予不同的权值可实现最优路径搜寻.给出了在广州市电子地图上搜索的一个实例:一个包含61个交通路口的最短路径搜索结果的搜索时间约为2.2s.

基于最短路径搜索序列编码的多下一跳路由

多下一跳路由较之单下一跳路由有许多天然的优势,通过分析现有多下一跳路由实现机制下的路由算法,提出了基于最短路径搜索序列编码的多下一跳路由。针对SPT(shortest path tree)路由实现机制无法利用等距离邻居节点之间链路的问题,提出了采用Dijkstra算法对网络节点编码赋值的思想。该方法可以对节点进行严格有序的赋值,规范了链路传输方向,有效地避免了环路,提高了网络资源利用率。仿真分析结果表明了该算法的可行性和有效性。

基于Dijkstra算法的多属性资源搜索的一种实现方法

最短路径是经典问题也是应用广泛的问题,在求解最优路径中经常用到Dijkstra算法,但Dijkstra算法是一个抽象的过程,实际应用中仍会有大量的信息可供采用以降低算法的复杂度。在基于交通网络的多属性资源搜索中,本文分别描述了决策偏好信息完全确定和不完全确定下的实现方法。

基于网络图的资源分配问题的算法研究及实现

图论是应用十分广泛的运筹学分支，用网络图来解决资源分配的问题不仅可以简化求解过程而且丰富了求解方法。在深入分析Dikstra算法的基础上，实现了基于网络图的资源分配问题的求解和图形表示，

GIS技术支持下的城市消防资源空间分析与应用

本文探讨了智慧城市理念与城市消防资源调度的关系以及基于GIS技术的城市消防资源空间分析方法。介绍了最短路径算法在城市消防资源调度中的应用,并提出了城市消防资源优化配置的策略和方法。通过这些研究,可以更好理解和应用城市消防资源,提高城市安全水平。

Fall Back^+——一种新的多QoS约束路由算法

FallBack(FB)算法是满足多QoS路径选择的基本算法 ,是Dijkstra算法的一种改进。在FB算法中 ,路径选择是按照算法设计者根据经验排序的多QoS来确定的 ,因此是经验的 ,所做选择的难以保证是最佳路径。另外FB算法主要以满足多QoS路径选择为目的 ,并未考虑网络资源的有效利用。本文对FB算法进一步扩充 ,提出了路径选择的FallBack+算法 ,它不仅满足多QoS约束 ,有效地利用网络通信资源 ,并有高的功效。

基于Agent的服务质量的多路径控制机制

一、引言 当前的因特网只能提供尽力而为(best-effort)的服务,也就是说它只是尽其所能地转发用户报文,不能保证用户数据传输的服务质量,如带宽、延时、延时抖动和报文丢失率等,例如,当网络发生拥塞时,它将不区分不同的用户,一视同仁地丢弃报文,没有用户等级的概念.这种服务模式非常适合于传统的应用,如FTP和电子邮件等.但是,现在出现了大量新型的服务,如IP电话、视频会议、远程教学、远程医疗、视频点播,这些新应用有一个共同的特点--强实时性:要求高带宽、低延时和低延时抖动.换句话说,这些新应用要求网络提供比"尽力而为"更好的传输服务.这样,在因特网上就存在传统的数据应用和多媒体实时应用两种类型的应用,这两种应用对实时性的要求不同,因此,网络需要根据用户的需求提供不同的传输服务,这个问题的解决办法就是在网络中增加服务质量(Quality-of-Service,QoS)机制.QoS问题是一个全方位的问题,它对整个系统都提出了相应的要求,数据发送端和接收端、网络等都要提供对应的机制[1],其中网络中IP层的QoS路由、允许控制、资源预留是一些保证QoS的非常重要的手段和机制[2].

基于Kruskal算法巡检线路的排班

本文主要针对巡检路线的排班问题,我们建立了最少人数模型,最短路径模型,人力资源模型,运用 Kruskal 算法 得出理想的排班时间表以及巡检线路。要使得人力资源消耗量可能少,而且需要把所有的巡检点都要检查一遍,同时还要考 虑每名工人的工作量平衡,由于问题一采用的是三班倒,每班工作 8 小时的制度,中途没有休息以及吃饭的时间。根据这些 条件我们将问题分成了三个部分,首先建立最短路径模型用 0-1 变量以及 Kruskal 算法求出最小生成树,然后得到以 22 号点 为起点以及终点的最短回路路径,在路上总消耗时间为71分钟。巡查线路为:22→23→24→9→25→26→15→12→18→16→1 3→11→10→6→14→8→17→3→5→7→2→1→19→20→21→4→22然后建立最少人数模型,求出最少的巡检人员为4人,然后 根据人数将回路进行划分,得到 4 个区间段,根据人力资源模型,得出巡检时间表。

应急物资配送问题研究

研究了多受灾点的应急物资运送方案的优化问题。首先将各城市路径分布图进行简化,对各节点重新编号,采用Floyd算法求出各城市运送物资到达受灾地所需要的时间,建立了一个多目标应急物资配送模型并进行求解。其次,建立了基于双层规划方法的应急物资配送模型,采用动态优选策略求得全局满意应急方案。最后,为实现整体救灾目标,求得了近似最优解作为应急物资运送方案。