Simplifying the nonlinear continuous time-cost tradeoff problem

Equivalent simplification is an effective method for solving large-scale complex problems. In this paper, the authors simplify a classic project scheduling problem, which is the nonlinear continuous time-cost tradeoff problem (TCTP). Simplifying TCTP is a simple path problem in a critical path method (CPM) network. The authors transform TCTP into a simple activity float problem and design a complex polynomial algorithm for its solution. First, the authors discover relationships between activity floats and path lengths by studying activity floats from the perspective of path instead of time. Second, the authors perform simplification and improve the efficiency and accuracy of the solution by deleting redundant activities and narrowing the duration intervals of non-redundant activities. Finally, the authors compare our method with current methods. The relationships between activity floats and path lengths provide new approaches for other path and correlative project problems.     

最短路树的计数、产生和优化问题

首先给出了在非负网络中构造最短路网络的算法，然后将树形图的计数算法到最短路网络中，设计出了最短路树计数问题的算法，将Gabow算法应用到最短路网络中，设计出了产生全部最短路树的算法，最后研究了最短路树的优化问题。     

最短路问题的闭环DNA算法

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

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

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

不确定情形下通信网络最短路径关键点问题

在通信网络中，因突发事件造成通信路由节点毁坏或者中断的现象时有发生，传输的数据包不得不从中断处沿着最短的替代路径行进到数据包的接收节点，在这种情形下，哪个路由节点中断使得数据包实际行进的总路程最长呢？从通信网络管理的角度来看这是一个非常重要的问题。对该问题．以前的文献都是从确定情形（事先具有节点中断的完全信息）下进行研究的，本文从不确定情形（只有数据包行进到中断节点的邻接点时才获得该节点中断的信息）的角度重新考虑这个问题。本文首先定义了不确定情形下的最短路径关键点概念，给出了计算不确定情形下最短路径关键点的算法及其时间复杂性分析。结合实际通信网络的算例分析，比较了确定情形下最短路径关键点和不确定情形下最短路径关键点问题，指出了不确定情形下最短路径关键点问题更具有实际意义。     

基于路径QoS加权分解的工作流调度算法

采用有向无环图DAG(Directed Acyclic Graph)描述的工作流在QoS约束下的调度问题是一类典型的NP难问题。分析了DAG工作流调度问题的调度目标,提出了一种基于路径QoS加权分解的工作流调度算法,通过将工作流的全局QoS约束分解为单个任务的局部QoS约束,将整个工作流的全局优化问题转化为单个任务的局部优化问题,降低了问题的复杂度。在对整个DAG工作流的QoS约束进行分解时,算法对工作流的每条路径的QoS约束进行分解,并以任务可选能力服务间的单位QoS增益之和作为权值,将单条路径的QoS约束分解到组成路径的每个任务。仿真结果表明,与其他基于QoS分解的DTL、DBL等算法相比,该算法具有更高的调度效率,能够找到更好的调度方案。     

不完全信息下交通网络最短路径关键边问题

因各种突发事件（交通事故、自然灾害等）造成道路中断的现象普遍存在，车辆在行驶的过程中并不具有道路中断的完全信息，只有行进到中断处时才获得道路中断的信息。本文就不完全信息（道路中断信息）下的变通网络最短路径关键边问题进行研究，首先定义了不完全信息下最短路径关键边的概念．其次给出了求解不完全信息下最短路径关键边的有效算法厦其时间复杂性分析，然后结合城市道路网络给出了实际算例，比较分析了最短路径关键边、最长绕行路关键边和不完全信息下的最短路径关键边问题，指出了不完全信息下的最短路径关键边问题更具有实际意义。     

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

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

基于改进蚁群算法的建筑火灾疏散路径规划研究

针对综合建筑火灾中人员疏散路径动态规划问题,以待疏散人员所需逃生时间最短为目标,考虑火灾产物和人群密度对人员逃生速度的影响,构建基于改进蚁群算法的人员疏散路径规划模型。建立由障碍物顶点栅格构成的疏散网络数据模型,改进蚁群算法的启发函数、死锁处理策略,引入烟花算法中的爆炸算子优化蚂蚁路径,以某综合建筑为例进行仿真实验。结果表明：该模型不仅能够避免疏散路径经过危险区域,还可根据建筑环境状况和人员分布情况实时调整疏散路径,提高了人员疏散路径安全性。     

最短路网络及应用

首先提出了最短路网络的概念 ,然后给出了一个时间复杂性为 首先提出了最短路网络的概念 ,然后给出了一个时间复杂性为 0 ( n2 )的构造最短路网络的算法 .最后研究了最短路网络在最小成本最短路 ,最短路计数和最短路树中的应用     

基于分段贝塞尔曲线的多导弹协同航迹规划

针对多导弹在保证自身生存能力的前提下对目标进行协同打击的问题,提出一种能够使多导弹回避威胁区、避免弹间碰撞、从指定的方向同时攻击目标的协同航迹规划方法。建立导弹的三次贝塞尔曲线航迹模型,考虑导弹的初始发射角、末端攻击角、过载等多种约束,以表示贝塞尔曲线控制点位置的量作为设计变量,以分段航迹最短为性能指标函数,通过优化得到最优分段航迹。根据战场的威胁区的位置和大小,设计了航迹节点选取规则,并与分段航迹优化方法相结合得到了满足威胁回避要求、过载及攻击角度约束的航迹。在各导弹速度相同的前提下,选定最长航迹对应时间为理想攻击时间,其余航迹按比例扩展以与最长航迹的长度相等,从而实现攻击时间的一致。对协同航迹时空安全性进行检测并提出了对不安全航迹的调整方法。仿真结果表明了本算法的有效性。     

多分配快递轴辐网络的枢纽选址与分配优化方法

快递网络枢纽选址与分配方案的优劣直接关系到快递网络的运营成本和服务水平, 是快递企业运作的基础. 本文详细分析了多分配快递轴辐网络的节点及连接关系、径路特征与形式等网络设计要素, 并分析了快递网络设计中的相关费用和运输时间预算; 在运输时间预算约束下, 以分拣费用、运输费用、中转费用之和为目标函数, 建立了多分配轴辐式快递网络枢纽选址与分配优化模型, 并设计了基于条件最短路的模拟退火求解算法, 最后通过算例验证了模型和算法的有效性.     

AN AUTOMATED REFERENCE POINT-LIKE APPROACH FOR MULTICRITERIA SHORTEST PATH PROBLEMS

1. Introduction Nowadays the exponential and convergent development of informatics and telecommunications, including Internet, makes that, in many communication networks, important decisions of technical nature have to be made in short time periods or even in real-time. This is particularly relevant in the context of routing models involving the calculation and selection of routes (corresponding to loopless paths) for node to node traffic flows, which seek to optimize certain metric(s) while s…     

论k阶最长路

论ｋ阶最长路秦裕瑗（武汉钢铁学院管理工程系４３００８１）ＯｎＬｏｎｇｅｓｔＰａｔｈｓｏｆｔｈｅｋ－ｔｈＯｒｄｅｒＱｉｎＹｕｙｕａｎ（ＷｕｈａｎＩｒｏｎａｎｄＳｔｅｅｌＵｎｉｖｅｒｓｉｔｙ４３００８１）ＡｂｓｔｒａｃｔＴｈｅ［１］ｇｉｖｅｓａｎａｌｇｏ...     

面向异构分布式计算环境的并行任务调度优化方法

分布式计算环境中并行作业的任务调度策略直接影响应用程序的执行时间,寻找一种使任务执行时间最短的调度方案已被证明是NP(non deterministic polynomial)完全问题。首先给出了异构分布式计算系统的形式化描述,建立了静态任务调度问题的理论体系,通过分析总结最长动态关键路径(longest dynamic critical path,LDCP)算法的核心思想及存在的不足,提出一种运用结点信息流量减少CPU空闲时间碎片的并行任务调度优化算法,其时间复杂度为O(M×N3)。实验表明改进后的算法在调度长度、加速比及计算效率3个指标上均优于LDCP算法和分层结点排序算法(sorted nodes in leveled directed acyclic graph division,SNLDD),其中,与LDCP、SNLDD相比,调度长度平均缩短19.03%、8.02%,加速比平均提升18.42%、7.96%,计算效率平均提高10.17%、3.72%,进一步提高了并行系统的资源利用率。     

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

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

基于层次分解策略无人机编队避障方法

针对危险模式下无人机编队问题,提出基于层次分解策略的编队避障方法.通过构建Voronoi图,利用K路径算法为各无人机找到多条备选航路;然后建立协同函数,为各无人机规划出既能满足时间协同要求,又能满足整体代价最优(次优)的障碍物规避航迹.并设计了无人机编队的通行规则,解决了无人机在避障飞行过程中有可能产生的碰撞冲突问题.仿真结果验证了算法的有效性.     

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

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

随机服务时间下的家庭护理人员调度问题研究

研究了家庭护理中的医疗服务人员调度问题,考虑了随机的客户服务时间和最迟开始服务时间约束.建立了带补偿的随机规划模型,得到了客户期望迟到惩罚成本的近似计算表达式,并分析了期望惩罚成本的性质.根据问题的特点,基于列生成算法思想建立问题的集分割最优化主问题模型和生成新列的最短路子问题模型,并设计标签算法对子问题加以求解.将列生成算法嵌入到分枝定界过程中形成分枝定价算法得到问题整数可行解.通过数值实验,验证了所提出客户期望迟到惩罚成本近似表达式和分枝定价算法的有效性.     

低轨预警星座通信网络的路由算法

路由技术是低轨预警星座通信网络需解决的关键技术之一。设计了低轨预警星座通信网络的拓扑结构。提出了多约束最优路由模型,该模型将链路的时延、切换率和可用带宽转化为传输费用,表示了时延和跳数受限的最小费用路由问题。给出了求多约束最优路由问题的最优解算法,此算法通过缩小可行路径的搜索空间降低计算复杂性。仿真结果表明,该路由算法的复杂性和切换性能优于同类算法,适合于星上在线路由计算。