有宵禁限制的时间最短路

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

一种求解时变条件下双目标最短路的算法

在组合优化过程中,往往需要获得从起点到终点之间的最短路,有时需要同时考虑两个目标,而这些目标可能会随着时间的变化而变化。为此,提出了一种利用标号法获得时变条件下双目标最短路的方法,考虑了不同的出发时间的情况,并对算法的复杂性进行了分析,最后给出了一个应用算例。     

时变网络中零等待时间最短路问题的一个对偶算法

时变最短路问题是最短路问题的一个推广.假设图G=(V,A)是一个有向图且有唯一的源点t,图G中的每条弧(i,j)∈A都附有两个参数:弧的传送时间b(i,j,u)和弧的传送费用c(i,j,u),它们都是在弧的顶点i上的出发时间u的函数.找出从源点到其它各点的最短路,即最小费用的路,并且要求每条最短路的传送时间不能超过给定的时间限制T.假设除源点外,在其它任何顶点都不能等待,b(i,j,u)是满足u b(i,j,u)≥0( (i,j)∈A,u=0,1,…,T)的任意整数,c(i,j,u)是任意的非负整数.给出了该问题的原规划和对偶规划,提出了一个最优性条件和一个对偶算法,并用一个数值例子来阐述算法.     

带硬宵禁限制的动态最短费用路逆问题的讨论

通过构建时间扩张网络，将有宵禁的动态问题转化为一般静态问题，再利用解线性规划逆问题的方法来求解该最短路问题的逆问题。     

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

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

求解Hamming距离下的最短路改进问题的一个近似算法

研究Hamming距离下的最短路改进问题的性质,并给出一个求解Hamming距离下的最短路改进问题的近似算法:按照一定规则得到满足一定条件的树型图,求解相应的0-1整数规划问题.该研究有助于设计求解Hamming距离下的最短路改进问题的有效的近似算法.     

随机网络的最短路问题

研究了随机网络上的最短路问题，并给出了一个启发式算法ESP来寻找期望最短路，以及启发式算法KESP寻找K-期望最短路，最后举出一个实例来证明算法的有效性．     

基于自适应扫描的遥感图像压缩算法

目的 为提高基于上下文算术编码器的效率.方法 首先分析了上下文模型以及上下文量化对信源熵的影响,得到了上下文量化的两个优化准则,并根据准则建立了一种时变的上下文性能模型.结果 给出了一种自适应位平面扫描顺序,改善了上下文条件概率的时变稳定性,提高了编码过程中对上下文条件概率的估计精度.结论 该方法较顺序扫描方式在同码率下有一定的PSNR提高,具有比顺序扫描更优的编码效率.     

不确定离散脉冲系统的保成本控制研究

许多实际系统都可归结为基于脉冲差分方程数学模型所描述的离散脉冲系统,针对此类离散脉冲系统,考虑一类范数有界时变参数不确定性和一个二次型性能指标,研究了其保成本状态反馈控制问题.首先根据李亚普诺夫稳定性理论与鲁棒控制的基本原理,给出了存在保成本控制器的一个充分条件,然后依据范数有界性参数不确定性已有的结论证明了该条件等价于一个线性矩阵不等式的可解性问题,并用这组线性矩阵不等式的可行解给出了保成本控制律的一个参数化表示.     

离散非线性时变系统指数稳定性的充分条件

在相当弱的条件下证明了离散非线性时变系统指数稳定性的一个充分条件,并给出了构造性证明.作为应用,给出了线性时变周期离散系统稳定性的某些简单实用的代数判据.     

基于k-臂分子求解最短路径的DNA计算模型

为有效求解最短路径问题, 避免传统算法计算量大、 求解时间长的问题, 充分发挥DNA(Deoxyribo Nuclec Acid)计算的并行性在求解复杂计算问题的优势, 提出一种基于k-臂分子和粘贴计算求解最短路径问题的DNA计算模型, 阐述了顶点、边及权值的编码方案, 描述了求解最短路径的DNA算法, 经验证, 该模型对求解最短路径问题是有效的。     

分子计算机的诞生与现状

介绍了计算机领域的一项最新成果———分子计算机 .分子计算机利用脱氧核糖核酸 (DNA)来进行计算 .腺嘌呤、鸟嘌呤、胞密啶、胸腺密啶 (核苷酸 )在计算中起了重要的作用 .使用限制内切酶、接合酶、转移酶、外切核酸酶、修饰酶来实现计算所需要的各种操作 .介绍了分子计算机完成的第 1个计算———解哈密顿通路问题的方法 ,用这种方法使NP完全问题在很短的时间内就得到解决     

用最短路径法求关键路线及其SAS的实施

利用网络工程的关键路线为耗期最长的特点，将其按照一定的规则转化成最短路径问题，然后利用求最短路径的SAS程序，顺利地求出网络工程的关键路线。     

基于网络限制的最短路模型

带限制的网络是一类特殊的网络,如具有禁止通行限制信息的交通路网.由于此类网络的最短路径的求解是有后效性的,因此经典的Dijkstra算法等就无法用来解决此类问题.提出了一种路网带限制的交通网络最短路径建模方法.该方法将具有禁行限制的特殊网络转化成一个一般的网络模型,从而可用任一传统高效的算法完成对其最短路径的求解.     

状态离散的确定性多阶段群体满意决策最优的算法

为了解决状态离散的确定性多阶段群体决策问题,将群体满意决策问题的多阶段与图的点集、边集对应起来,应用图论知识建立了多阶段群体决策问题的模型．将多阶段群体满意决策问题转换成一个在多部赋权图中找一条最长路径的问题．依据一条最长路径上的任意两个不相邻的顶点之间是不可以被由不在这一条路径上的两个顶点组成的更长的路所替代这一事实,提出了一种多部赋权图中最长路径的算法．最后给出计算实例．     

仓库拣选路径问题研究综述

近年来,多品种、小批量的生产模式的盛行,给制造业的仓储带来了巨大的挑战,如何提高仓库的拣选效率是一个亟待解决的问题。因此,中外学者针对仓库拣选路径问题提出了多种分类及研究方法。通过查阅相关文献,从两个角度对仓库拣选路径问题进行综述。首先,从拣选作业类型的角度,将研究问题分为单一作业和复合作业,分析仓库拣选路径问题的研究现状及存在的问题;其次,从研究方法的角度,将求解方法分为启发式算法和强化学习,分析近年来二者在仓库拣选路径问题中的应用;最后,对现有文献进行总结,并提出未来仓库拣选路径问题的发展方向。     

基于图论和多目标规划的兵力机动路线优化

研究在最短时间和最大生存概率等两重目标约束下的兵力机动路线优化问题。首先介绍最短路问题的数学模型及D ijkstra算法,然后将求最大生存概率路目标约束转化为求最短路问题,随之建立多目标规划模型,并描述了用STEM算法进行求解的过程。最后用实例验证了模型和算法的可用性。