无向正权网络最短路模型的建立和理论分析

路径问题是运筹学的重要分支, 更是图论学科成立的奠基问题.针对无向网络中的路径问题, 首先, 建立了无向正权网络最短路模型, 提出一些能够反映无向网络中节点、边和路线规律性的参数概念, 包括点参数和边参数, 用这些参数代替边的权数描述无向正权网络; 其次, 通过对模型进行理论分析, 推导出与各参数相关的结论, 利用参数揭示了点、边、路线以及无向正权网络之间的关系, 并初步体现了该模型的用途; 第三, 利用该模型求解了与无向正权网络相关的几类基本路径问题; 最后, 通过应用举例, 阐述了该模型的部分应用. 需注意的是, 该模型也适用于带回路的有向正权网络.     

区间阻抗下的鲁棒最短路算法

交通需求一旦发生变化,交通路网中的路段阻抗也会呈现显著的不确定性,而现行的最短路求解方法缺乏鲁棒性。为了增强最短路方法的鲁棒性,引入区间型数据的路网阻抗,同时结合鲁棒离散优化与情景分析法,给出鲁棒成本的定义。建立了区间阻抗下的鲁棒最短路模型,接下来基于模型设计了分支定界算法,并就算法的判定条件给出3个定理,最后对一个大型路网进行了仿真测试。结果表明:相对于现行的最短路方法,该方法求解得到的最短路径具有更强的鲁棒性,且求解结果准确高效。     

无线传感器网络移动Agent路由算法的研究与仿真

提出一种新的基于虚拟连通拓扑子图的优化模型用于无线传感器网络移动Agent路由．建立包含有效节点的虚扭连通拓扑子图，将Agent访问路径分解为采集子路径和返回子路径，提出一种基于GA与离散PSO的混合算法GAPSO用于求解该问题。该算法可大大降低解空间复杂度，提高搜索效率。仿真结果表明随着网络规模增大，该优化模型优势明显，GAPSO表现出比GA更好的性能。     

给定限制期条件下最小风险路径的选取算法

讨论在给定限制期情况下，边的长度（权值）为区间数的赋权图最小风险路径的选取算法，该算法将非线形比例路径问题的求解转化为最短路问题的变权迭代，算例及实际应用取得了令人满意的效果。     

无冲突可重复网极小活标识的配置

首先给出无冲突可重复网的定义,并证明无冲突可重复网是结构活的.然后将无冲突可重复网的极小活标识的配置化为强连通T_图极小活标识的配置.文[2]虽然给出T_图极小活标识的判断方法,但是对于一个比较复杂的T_图的极小活标识的配置是无法实现的.本文通过求解强连通T_图的m-n+1个线性无关的极小S_不变量的支集,找出m-n+1个线性无关的有向回路组,然后给出构造强连通T_图以任一变迁为根的有向生成树,最后给出配置强连通T_图极小活标识的有效算法.     

群组AHP判断矩阵的一种有效集结方法

针对群决策中判断矩阵的集结问题,提出了一种基于m阶简单无向连通图理论的正互反型判断矩阵的集结方法.在给出了该算法的具体步骤的同时,通过算例分析,说明了该方法的实施过程及其有效性.     

用模拟退火算法求解有顺序约束指派问题

首先对有顺序约束指派问题进行分析.接着把这一特殊的指派问题用有向无回路图表示出来,从而使指派问题的求解转化为求解有向无回路图的划分问题.针对划分问题,构建了一种特殊的邻域结构,并设计出基于此邻域结构的模拟退火算法.最后,通过一个实例对算法的关键环节进行演示,通过另一个实例把模拟退火算法同禁忌搜索算法进行比较,结果表明该算法能够有效解决此类问题.     

最短路问题的闭环DNA算法

提出了不等长闭环DNA分子的概念,由此推广了闭环DNA计算模型。给出了固定端点的最短路问题闭环DNA算法,该算法首先对每条弧进行了三组DNA编码,再用有目的的终止技术合成固定端点的所有链,然后通过接入实验和电泳实验得到最短路,并通过检测实验输出所有最短路径。得出了算法的复杂性,为说明算法的有效性给出了一个算例。最后讨论了最短路问题闭环DNA算法在变权网络、自由终点或固定中间点的最短路问题中的应用,并给出了相应的解决方法。由此说明该算法具有广泛的适应性。     

带二次参数赋权的多阶段网络最短路算法

当网络中的权值不是常数而是含参数的函数时,它可以看作是一种动态网络,用传统的算法求解这类网络的最短路径变得十分困难.为此,提出了含二次参数权的多阶段网络最短路问题,并利用Dijkstra算法思想和隐枚举方法给出了求该网络最短路的隐枚举标号算法,最后对该算法的复杂性进行了分析.理论分析与实验结果表明,尽管该算法不是多项式的,但对于一定规模的该类网络还是十分有效的.     

一种新的路径生成式Logit交通分配算法

Logit方法是一种重要的非平衡交通分配方法，但由于需要路径枚举，限制了它在大型路网上的应用。本文提出了一种新的路径生成式Logit交通分配算法。每次迭代中，利用Logit方法在已产生的路径集上进行变通分配，并更新路段交通量度路段运行时间，然后在此基础上利用最短路算法求出新的最短路并更新路径集，如此变替进行．直至不再产生新的最短路，最后完成交通分配。由于不需进行路径枚举，从而使本算法适用于大型路网的交通分配。实际计算表明．该算法是有效和可行的。     

著名的Fan型定理的推广

1984年，Fan给出了著名的Fan定理：若2连通n阶图G的距离是2的任意两点x、y均有max{d(x),d(y))≥n／2，则G是哈密尔顿图。本文证明深化Fan条件的结果：若2连通n阶图G的满足1≤|N(x)∩N(y)|≤α-1的任意两点x、y均有max{d（x)，d(y))≥n／2，则G是哈密尔顿图。而且本文给出的证明方法更简捷。     

异质多自主体系统的一致性

研究由一阶自主体和二阶自主体构成的异质多自主体系统的一致性问题.考察连接拓扑为固定有向图的异质多自主体系统在无时延静态一致性算法下的收敛问题,利用图论和矩阵分析方法得到了系统渐近收敛一致的充要条件;在假设连接拓扑在有向连通图之间动态切换条件下,分别研究领导-跟随连接拓扑和无领导连接拓扑下异质多自主体系统的静态一致性问题,并采用Lyapunov定理和线性矩阵不等式得到了系统在具有时变输入时延的一致性算法作用下渐近收敛一致的时延依赖条件.最后,仿真结果验证了结论的正确性.     

KMG:考虑逆向物流的无人机路径规划策略研究

物流领域无人机派送正成为一种快捷高效的派件方式和应用热点.针对于正向、逆向的物流数据,无人机派送是国内外大型物流企业实施高效物流派送的重要手段.本文提出了一种融合拓展性K-Means++算法和遗传算法的路径动态规划模型(KMG),实现包含逆向物流的无人机调度策略.KMG模型将逆向物流路径融入正向物流路径之中,采用加权聚类算法确定不同属性包裹所需派送无人机的最小数量.在每一簇坐标数据的连通图中,采用遗传算法求解TSP问题,并对可行解进行编码,最终求解出最小欧拉回路.在仿真实验中,KMG模型比独立逆向物流派送的成本减少20.08%,使用拓展性K-Means++聚类计算的时间比传统K-Means算法缩短了298.85%.     

基于多目标演化的模糊认知图学习算法

针对传统模糊认知图学习算法仅优化概念结点间有向弧的权值误差而造成模型拟合准确程度不高的问题,将多目标演化的思想用于模糊认知图学习算法,设计了以有向弧权值误差与误差权重同时最小化为目标的多目标模糊认知图学习模型,降低了学习算法对权值的依赖。为有效求解该多目标优化模型,提出了一种基于坐标变换的多目标演化算法,分析了算法的参数设置方法与计算复杂度。实验结果表明,基于多目标演化的模糊认知图学习算法可以有效降低结点数据误差与模型误差,能够更准确地得出概念结点间的因果关系。     

基于模糊网络环境的一种FSPP算法

讨论了有限支撑的正模糊数表示路径长度的最短路问题,接着基于Harisen的双标准路径问题的多标号法和Dijkstra的最短路算法,提出了模糊网络环境下一种具有有限模糊教的模糊最短路径算法,它以某种扩展原则找到所有非劣路径,这种算法在有圈和无圈的网络上都能使用,因此比常规曩短路径算法更加有效和符合实际.     

用于雷达信号分选的连通k近邻聚类算法

为了能够在密集且复杂多变的信号环境中进行实时有效的信号分选，需要一种具有较低复杂度且能够根据信号环境自动调整参数的聚类方法。在模糊聚类算法的基础上结合k近邻搜索，将λ邻域范围搜索变为λ邻域内k近邻搜索，提出了连通k近邻聚类(connected k-nearest neighbor clustering, CkNNC)算法。相比模糊聚类算法，所提算法时间复杂度降低而空间复杂度稍有增加。为使得该算法能够根据信号环境自动进行参数调整，提出了基于k距离图的阈值参数确定方法。所提算法具有时间复杂度低与阈值参数自动确定的特点，仿真结果表明所提算法与使用Calinski-Harabasz指标确定最佳阈值的低复杂度模糊聚类算法相比，分选效果差距不大、性能相近，而时间复杂度大幅下降。     

数据网格中QoS感知的副本放置方法

数据复制技术广泛用于数据网格,如何合理地放置复制时产生的数据副本来更有效地提高数据访问性能成为一个值得研究的重要问题。本文针对无向连通图表示的数据网格模型,提出了一种满足各用户服务质量(quality of service, QoS)需求的副本放置算法(replica placement algorithm, RPA),通过该QoS感知的副本放置算法能够获得k个副本放置位置,并且使得整个数据网格系统的通信代价最小。最后,文章通过相应的仿真实验证明了该算法的可靠性和有效性。     

需求可拆分车辆路径问题的三阶段禁忌算法

需求可拆分车辆路径问题(SDVRP)是一类有待深入研究的车辆路径问题,其求解方法与需求不可拆分的VRP问题有较大的区别.针对该类问题,本文提供了一种新的求解思路——基于双层规划模型的三阶段禁忌算法.首先,将目标函数设定为大TSP路径成本加上切割增加路径成本,构建了SDVRP的双层规划数学模型;然后,根据双层规划的思路设计了三阶段禁忌启发式算法:先求包括车场和所有顾客的大TSP路径,再对大TSP进行切割和拆分,接着对备选方案进行子路径优化;最后,通过实验仿真,将所提出的三阶段禁忌算法与其他算法进行比较,结果表明了所提出的算法可以比较有效地求得需求可拆分车辆路径问题的优化解,是解决需求可拆分车辆路径问题的有效方法.     

不确定性条件下的多目标多路径选择

不确定性条件下,综合多种性能指标,提供多条合理候选路径的路径选择方法还未得到有效解决.介绍一种利用累积前景理论进行多目标多路径选择的方法.为此,首先分析路段的不确定性属性和出行者的路径选择特性,基于路段广义出行费用定义参考点和值函数,建立多目标路径选择的累积前景理论;然后基于累积前景值定义合理替换路径,建立合理多路径选择模型;将改进的克隆选择算法与节点删除法相结合,设计了多路径选择模型的求解算法;最后,将该法和节点删除法、传统k-最短路算法应用于示范网络,比较分析了本文算法的有效性和快捷性.     

用选边法求最优树

设图G=(V,E)是一个有限的无向连通图,这里V表示图G的顶点集,E表示图G的边集。每条边e_i∈E,还有一定的长度l_i,称l_i为边e_i的权。这种每条边标有权的连通图称为赋权连通图。如果图T是一个不包含有回路的连通图,则称图T是一棵树。如果图T是图G的一个生成子图,而且T又是一棵树。则称T是图G的一棵生成树。一棵生成树T的权W(T)是指图T中各条边权的总和,其中具有最小权的生成树称为最优树。赋权连通图的最优树往往是图论中具有较广泛地实际应用价值的。例如在若干城市之间修公路,铺铁路,或架通信线路等,都需要求出城市之间的最短连通线路,使修建成本降到最低。这种求出若干城市之间最短连通线路就是一个求出赋权连通图最优树的问题。