基于最短路的设备更新问题的数学建模

最短路问题在大学生数学建模竞赛和实际生活中有着广泛的应用.介绍了最短路问题的定义、求解最短路的Dijkstra算法和0-1规划法.最后,给出设备更新问题的最短路数学模型求解过程.     

带负权最短路问题前趋法的改进

针对在带负权的有向网络中求最短路的前趋法的不足,结合动态规划思想从提高算法效率方面对其进行了改进,并提出了一种新算法.新算法通过引入变量记录当前节点到宿节点的最短路权,避免了前趋法中比较多条前趋路时反复计算最短路的冗余运算,同时弥补了动态规划不能直接求解带回路的有向网络最短路的缺陷,是一种计算带负权最短路问题的简便方法.该算法对非负权网络中的最短路问题同样有效.最后仿真结果和算例表明了新算法的有效性.     

无向图中严格第三短路问题的多项式时间算法

给定一个无向图G=（V,E;w;s,t）,其中s,t是2个固定顶点,w：E→R^＋是边的长度函数．最短路是指所有路中长度最小者,次短路是指长度比最短路严格大的所有路中的最小者,严格第三短路是指长度比次短路严格大的所有路中的最小者．对正权重无向图中严格第三短路问题给出一个O（n^4）多项式时间算法．     

在电子表上求解最短路问题的研究

图论是运筹学的一个重要分支,各点间最短路是图论重要内容之一,其直接应用是求解单服务设施布点（网络的中心或重心）及多服务设施布点问题．各点间最短路可采取矩阵算法,但并非简单的矩阵的和、积与逆,不能直接使用电子表函数．本文通过函数的组合,探讨利用Excel求解最短路问题的更为简便的操作方法．     

基于Benders分解的鲁棒最短路算法

为了研究路段行程时间不确定条件下的最短路问题,采用区间数据表示路段行程时间,介绍了鲁棒偏差和鲁棒成本的概念,并据此给出鲁棒最短路的定义,运用鲁棒优化中的min-max准则构建了鲁棒最短路问题的混合整数规划模型。通过固定路径决策变量将鲁棒最短路问题分解为子问题和主问题,同时结合对偶理论给出子问题的对偶模型。在此基础上设计出鲁棒最短路问题的Benders分解算法,采用AMPL编程实现算法并调用CPLEX进行求解。并在一个仿真网络中对本研究方法进行了验证分析。研究结果表明,相较于传统最短路Dijkstra算法,本研究方法求得的鲁棒最短路在不确定网络中具有更强的可靠性,设计的算法迭代效率较高,能迅速缩小迭代范围并找到最优解。     

最短路的蚁群算法收敛性分析

蚁群算法最初出发点是模拟蚂蚁觅食,蚂蚁可以利用局部信息素的变化找到从蚁穴到食物的最短路。对求解最短路问题的蚁群算法的收敛性进行了探索性分析,定理给出了寻找最短路的蚁群算法收敛的充分条件,并通过一个数值例子验证了该结果。     

有宵禁限制的时间最短路

在组合优化过程中,往往需要获得从起点到终点之间的最短路,而其所考虑的目标可能是一个与时间相关的变量,同时,对于网络中的节点往往有宵禁的限制(curfews)。本文给出了时变条件下有软、硬宵禁限制的时间最短路模型,设计了求解时变条件下有宵禁限制的时间最短路的算法,并给出了一个应用实例。     

有宵禁限制的成本最短路问题

在组合优化过程中,往往需要获得从起点到终点之间的最短路,而其所考虑的目标可能是一个与时间相关的变量,同时,对于网络中的节点往往有宵禁的限制(curfews).给出了时变条件下有软、硬宵禁限制的成本最短路模型,设计了求解时变条件下有宵禁限制的成本最短路的算法,并给出了一个应用实例.     

无向图中严格第三短路问题的多项式时间算法

给定一个无向图G=(V,E;w;s,t),其中s,t是2个固定顶点,w:E→R+是边的长度函数.最短路是指所有路中长度最小者,次短路是指长度比最短路严格大的所有路中的最小者,严格第三短路是指长度比次短路严格大的所有路中的最小者.对正权重无向图中严格第三短路问题给出一个O(n4)多项式时间算法.     

打孔机生产效能提高的数学模型

为提高打孔机生产效能,建立优化模型以及类似TSP的最短路模型。就单钻头打孔机的孔群加工问题而言,首先求解刀具转换次数最少的优化方案,用lingo程序求解,得到最少的刀具转化次数为9次;在此基础上解决每种刀具进行打孔作业时的最短路问题（即类似 TSP问题）,应用贪心算法并应用matlab求解,最终得到每个工作阶段钻头最短行进路径,共9个阶段的最短路径,进而得到钻头最短行进时间及行进成本。     

卫星时变网络中基于连接计划的最短路径优化算法

在卫星时变拓扑网络中,针对Dijkstra最短路径算法不能时刻保证路径最优的问题,结合卫星节点运动规律的确定性,研究分析了卫星网络拓扑动态变化的周期性特征,提出了一种基于连接计划(contact plan,CP)的最短路径算法(CP-Dijkstra).在低轨(low earth orbit,LEO)卫星系统中,首先根据不同时刻星间链路的时变连接情况形成动态CP,然后根据CP是否发生改变对信息进行不同的处理:当节点检查到CP未改变,则根据之前计算的最短路径进行转发;反之,则根据当前最新的CP重新计算到达目的节点的最短路径,直至信息成功转发到目的节点,从而确保信息经过的一系列路径序列为最短路径.仿真结果表明,与卫星时变网络中常用的动态虚拟拓扑路由(dynamic virtual topology routing,DVTR)算法相比,CP-Dijkstra算法不仅能够较好地提升网络吞吐量,而且可以有效地降低网络平均时延和丢包率.     

最短路径子图

在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高.     

最短路径扩散机制下实时可靠性网络路由选择方法研究

针对网络通信实时性、可靠性的要求,提出一种最短路径扩散机制下实时可靠性网络路由选择方法,依据链路质量对加入网络的节点构建逻辑路径,形成树状结构。将某节点与其它节点之间的可用物理链路看作辅助路径,得到Mesh形网络拓扑结构。分析了最短路径扩散机制,利用最短路径扩散机制对网络中全部节点构建最短路径信息。介绍了网络交通流和交通引力场模型,考虑节点对交通流的引力作用,将传输路径看作影响引力的指标,通过交通引力场实现网络路由选择。实验结果表明,所提方法在保证网络实时可靠性的同时,可减少能耗,降低数据丢包率,提高网络吞吐量。     

无线传感器网络自适应拥塞控制的路由算法分析

无线传感器网络中节点的覆盖范围有限,因而采用多跳路由传输方式.无线自组网中的多跳路由是由普通节点协作完成的,选择不同的转发节点,会对网络的信息传输产生不同的影响.对不同路由(洪泛路由、最短路径等)算法下的网络自适应拥塞控制进行了分析,研究了不同路由算法下的网络性能和拥塞控制效果.根据节点跳数与缓存占用的关系,提出一种基于节点跳数和缓存占用的性能函数的改进最短路径算法,算法选取使性能函数值最小的节点作为转发节点.最后,通过实验比较了最短路径算法与改进路由算法的网络性能,发现改进路由算法相比最短路径算法,具有较好的网络性能和服务质量.     

带转向延误和限制的最短路径问题及其求解方法

阐述了带转向延误和限制的最短路径问题(SP-Turn)的基本原理,系统介绍了现有的求解方法,包括扩展网络法、对偶网络法和弧标号算法,并提出了一个节点标号算法用于对比.分析指出弧标号、节点标号算法在算法原理上是一致的,对偶网络法是对它们的直观化.同时指出在SP-Turn方法中,扩展邻接表是高效的网络表示形式,在合理选择的前提下,一般SP算法的标号设定、标号修正等标号技术同样适用,最短路径可由节点至弧的形式转换为节点至节点的常规形式.     

模糊随机约束等价形式的有效性

最短路问题是寻找从原节点到其他节点最短的距离,它在交通运输、行程安排、信息传递中有很重要的作用.研究了具有模糊随机弧长的多属性最短路问题,通过比较解原模型与等价模型来解释模糊随机约束等价形式的有效性.     

最短路问题的灵敏度分析与最短路调整

本文讨论的是无负回路的有向网络,在己知网络各节点间最短路的前提下,当网络中的个别节点、权值、弧发生变化时,变化对最短路有无影响,若有,如何利用变化前的最短路得到改变后的最短路,即:利用网络的独特优势,建立最短路问题的灵敏度分析算法.     

城轨站行人流线网络客流分配算法与软件实现

为实现符合城市轨道交通车站行人流线网络特点的行人设施客流分配,首先将分方向实结点时间阻抗与结点客流方向引入最短路径识别,将其嵌入连续平均法,建立了适用于城市轨道交通车站行人流线网络的客流分配算法.然后,利用C#和Matlab语言在AutoCAD环境下开发了相应的客流分配软件,并在此过程中提出了结点客流方向获取方法.算例表明,该算法能够实现考虑分方向实结点时间阻抗的城轨站行人设施客流分配;与TransCAD、VISUM相比,软件符合行人流线网络特点,操作简便.     

一种最短路径分析优化算法的实现

在对地理信息系统中最短路径分析的实现方案和现有各种最短路径分析算法进行分析、研究的基础上,提出了“优化Dijkstra算法”。该方法使Dijkstra算法的搜索方向明显趋向于目标结点,减少了算法中遍历的结点数,从而提高了搜索速度。总结出两个Dijkstra算法的优化途径：对搜索到的临时标记结点按照最短路径值排序;减小结点的搜索范围即减少永久标记结点的数量。     

基于蚁群算法的最短路径搜索方法研究

最短路径问题是在给定的网络图中寻找出一条从起始点到目标点之间的最短路径。蚁群算法是一种用于求解优化问题的新型模拟进化算法,该算法在许多相当困难的优化问题的求解中体现了极强的寻优能力和较好的性质。提出了一种利用蚁群算法来解决网络最短路径问题的新方法,并用Matlab语言编程进行算法的实现和仿真。结果表明,蚁群算法在寻求网络最短路方面的应用是可行的。