THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

This paper provides a method of producing a minimum cost spanning tree (MCST) using set operations. It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves the correctness and the complexity of the algorithm. This algorithm uses the FDG (formula to divide elements into groups) to sort (the FDG sorts a sequence of n elements in expected tir O(n)) and uses the method of path compression to find and to unite. Therefore. n produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).

考虑库存成本的蔬果同城配送路径优化研究

疫情防控常态化对我国蔬果冷链市场带来了挑战。文章研究考虑库存成本下蔬果的同城配送路径优化,使得在疫情的情况下,能最大限度节约供应商的配送成本,获得更高效益。配送成本不仅包含运输成本、货损成本和时间惩罚成本,文章还将考虑库存成本,构造满足时间窗约束的节约成本最大为目标的优化模型,并基于节约里程法的思想提出启发式算法。结果表明,优化后的路线能节约总配送成本,从而达到成本节约的目的。

基于共享边的时延约束组播路由算法

为了优化在时延约束下的组播树代价,降低算法计算复杂度,研究了时延受限的Steiner树问题。分析了最短路径启发式(MPH)算法的执行过程,以此为基础提出一个基于共享边的时延约束组播路由算法ESAMPH。该算法在构建组播路由树时能够优先采用包含有较多的最短路径经过的节点,这样后面的组播成员节点到树上的最短路径也有可能经过这些节点,由此实现边的共享,降低了组播树的代价。仿真结果表明,ESAMPH算法在代价、延迟和计算时间之间能获得较好的平衡,综合性能较好。

运费有差异的多品种流交通网络最小费用算法

对运费有差异的多品种流交通网络进行了分析,构建了复合参数和复合指标,借鉴连续最短路算法和FordFulkerson算法,设计了运费有差异的多品种流最小费用算法,并通过算例证明了算法的可行性,为解决实际交通网络的相关问题提供了参考.

基于公共信息模型的配电网网架优化规划

在公共信息模型(CIM)扩展的配电网模型基础上构建了组合式迭代器以实现系统级元件遍历。讨论了实际配电网规划普遍存在的多交叉点的情况,运用改进的基于关键节点最小代价多播路由算法建立配电网规划模型,提出了组合边的概念,以组合边的形式参与边的动态迭代,获得总体费用最小的优化规划结果。以迭代器隔离算法和数据,降低耦合度并增强稳定性和可拓展性。算例表明了文中方法的有效性。

基于加权节点的Steiner树启发式算法

Steiner最小树问题是一个NP完全问题,被广泛应用在通信网络中点到多点的路由选择。为了实现更多链路的共享,减少所求Steiner树的费用,提出了一种基于加权节点求解Steiner树的启发式(NWMPH)算法。该算法构造了非正则点的权值公式,给每一个非正则点赋权值,根据权值对链路的费用进行修正,通过修正费用最短路径依次把所有的正则点连接起来,得到包含所有正则点的最小树。对STEINLIB标准数据集中的部分数据进行计算,结果表明:NWMPH算法与MPH算法所用时间基本相同,得到的Steiner树费用优于MPH算法;NWMPH算法比KBMPH算法所用时间少,得到的Steiner树费用绝大多数优于KBMPH算法。

基于改进GA的分段堆场计划调度方法研究

针对船舶分段堆场在调度过程中周转效率低、调度滞后以及调度成本高等问题,以进出场分段在堆场中的调度为研究对象,考虑船舶分段堆场调度过程中的扰动因素,采用基于事件触发式的重调度方法,结合分段质量和移动距离建立数学模型,以移动分段所需的成本为优化目标,提出利用改进遗传算法来选择分段在堆场中停放位置的较优方案,并构建启发式规则来确定分段最优进、出场路径。利用某船厂实际数据对模型进行验证,表明该方法可得到较优的堆场作业计划,实现堆场资源的高效利用。

时延受限组播路由的最短路径加速算法求解

分析了时延受限的Steiner树问题,总结了在构建组播树过程中的代价和计算复杂度变化规律,并根据实际网络环境,从优化最短路径出发,提出了一种基于优化最短路径的时延受限组播路由算法AOSPMPH。该算法以MPH算法为基础,利用Floyd最短路径优化算法求出节点对之间的最短路径,选择满足时延要求的最小代价路径加入组播树,进而产生一棵满足时延约束的最小代价组播树。仿真结果表明,AOSPMPH不但能正确地构造时延约束组播树,而且其代价和计算复杂度与其他同类算法相比得到了优化。

运费无差异的多品种流交通网络最小费用算法

为了解决交通网络应用中多品种流问题,对运送费用无差异的多品种流交通网络进行分析,在借鉴连续最短路算法和Ford-Fulkerson算法基础上,构造了复合参数和复合指标.基于设定的复合参数、复合指标以及相应的计算规则,构建了多品种流交通网络最小费用流分配算法,通过算例验证了算法的可行性.运费无差异的多品种流交通网络最小费用算法为解决交通运输领域普遍存在的运送费用无差异的多品种流最小费用流问题提供了应用基础.

基于时间与费用双优化的虚拟企业调度算法

基于合理抽象虚拟企业模型和任务模型,建立虚拟企业生产任务计划的数学模型,并提出了一种时间与费用双优化的调度算法.该算法分别针对虚拟企业生产调度的时间与费用2个目标提出启发式优化算法,并以调度优化的结果作为遗传算法的初始染色体,通过对遗传算法运算的重新定义来优化虚拟企业生产计划调度,充分发挥遗传算法良好的全局搜索能力和能有效避免陷入局部极小的优点,提高了算法的全局寻优能力.实验结果表明,启发式优化算法与遗传算法相结合的优化技术能够降低虚拟企业生产费用,使企业具有较好的生产敏捷性.

交通运输网络中两个结点间有流量约束的最小费用最大流算法

对交通运输网络最小费用最大流的分配是在满足容量限制条件和流量守恒条件下,基于总费用最低的原则进行的,但在实际应用中,通常对交通运输网络中两个结点之间的流量有具体的要求和约束限制条件.针对交通运输网络中两个结点之间有流量约束的最小费用最大流问题进行了分析,总结了两个结点之间的流量不能超过限制值、不能低于限制值以及在一定范围内的3种约束条件.基于连续最短路算法中构造伴随增流网络的思路,设计了这3种约束限制条件下的最小费用最大流分配算法.利用这个算法,可以解决交通运输网络中两个结点之间有流量约束的最小费用最大流分配问题.在交通运输领域,两个结点之间有流量约束的最小费用最大流问题普遍存在,这些算法也为解决实际的运输问题提供了应用基础.

有运送路径限制的多品种流交通网络最小费用流算法研究

传统的交通网络最小费用流分配是针对单一品种,但在实际的交通运输应用中,交通网络中往往会出现多品种流的运送情况,而且也有可能对某些品种的运送路径进行限制.首先针对交通网络中的多品种流及其流动现象进行分析,借鉴Ford-Fulkerson算法中构造伴随增流网络的思路,建立了多品种流交通网络图的顺推重构方法,在此基础上,构造了有运送路径限制的多品种流交通网络最小费用流算法.在交通运输领域,多品种流最小费用流问题普遍存在,此算法为解决实际交通网络的相关问题提供了基础.

最小生成树的算法

本文提出了一个利用集合运算生成最小生成树的算法,研究了实现集合运算的数据结构及施加在这个结构上的算法,该算法利用公式分组排序(公式分组排序n个元素序列的期望时间是O(n)),利用路径压缩的方法进行查找、并运算,该算法将有n个顶点e条边的无向连通网络生成最小生成树的期望时间是O(eG(n))(当n≤2^(16)时,G(n)≤3)。

基于最小代价路径的血管中心线提取

为解决传统最小代价路径算法提取血管中心线时存在偏向血管侧壁的问题,提出一种基于点的中心线校正方法。应用最小代价路径算法初步提取中心线,然后根据血管剖面灰阶值呈高斯分布的特点对每个中心点进行校正,再利用三次B样条将离散的中心点拟合为一条连续的中心线。实验结果表明,该算法提取的中心线更靠近血管的中心处,且对噪声具有鲁棒性。此外,将该算法用于起点、终点位置的校正,则提取的中心线对用户定义点的位置不敏感。

最小费用最大流算法实现

综合运用3维数组和深度优先等数据处理方法,结合最大流原理和最短路的Floyd算法,利用VC语言工具编写了C++程序,在直接输入初始状态下就可求出任何一个多络图的最小费用值、最大流值以及其他一些相关数据.

基于最小费用/可靠性比值路的物流配送中心选址问题

费用和可靠性是评判一个物流系统是否优良的两个重要指标.一般要求从配送中心到各配送点的运输费用尽可能低,而可靠性则要求尽可能高.讨论了在时变环境下的物流配送中心选址问题,要求从配送中心到各配送点的费用/可靠性比值之和达到最小.模型中考虑的费用和可靠性都是时间的函数.该问题是NP完备的.且给出了求解该问题最优解的一个拟多项式算法.

A^＊算法估价函数的特性分析

确定估价函数是A*算法中最关键的问题。在对估价函数特性进行分析的基础上,讨论了它的几个一般构造原则,并简要介绍一些试验经验及若干实例。

基于费用最小的列控设备维修优化与仿真

铁路列控设备维修计划的合理优化不仅可以减少维修过程中存在的一些问题,而且可以提高设备的可靠性进而提高整个列控系统的安全性及运输效率。建立了以最小费用为目标函数,可用度和故障风险为约束条件的最小费用模型,并在此基础上设计了设备维修计划优化的启发式求解算法流程;提出基于可靠性分析的铁路列控设备维修计划调整方案,结合某站的实际调研数据开展案例研究;最后基于所建立的模型及求解方法运用蒙特卡洛模拟仿真获得维修计划优化方案,使维修效果和维修投入之间达到一个平衡,从而证明优化模型的有效性与实用性。

一类点权网络的最小费用流问题

以城市路网为背景求最小费用流时不能忽略交叉口的费用和通行能力限制,但由于交叉口延误等费用和通行能力具有方向性,普通最小费用流算法无法直接应用于这类问题.文中以节点权重表示交叉口的延误和通行能力,将城市道路网表示为一个节点具有分方向权重的点权网络,提出了一个改进的最小费用路算法求解这类点权网络中的最小费用流问题.算法计算时间复杂性为O(nmf0).以一个数值算例说明了算法的应用.

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

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