飞行员全动模拟机复训问题求解

针对无训练资源约束的飞行员全动模拟机复训问题,构建双目标整数规划模型对问题进行刻画,通过构造网络流、二部图和加权路等一系列网络规划模型,将原问题转化为最小费用最大流和最长路求解问题,并设计多项式启发式算法对问题进行求解,证明所得解为原问题的非劣解. 最后,实证说明了模型和算法的有效性.     

一种QOS驱动的仿真服务组合优化方法

鉴于Web环境的不确定性和动态性,经过功能性匹配选中的仿真服务必须进一步在非功能性属性,即服务质量上满足用户的需求.为此,首先对仿真服务组合问题进行了定义,建立了组合服务的QoS模型;进而,将Q-SSC优化问题建模为一个带约束的单目标组合优化问题,并实现了求解该问题的启发式算法SOOCH,该算法具有较好的时间性能,而且获得的解与最优解的近似程度能够达到90%以上.     

一种优化多目标的交互式路由算法

Qos路由的基本任务是寻找一条满足多个约束条件同时优化多个网络参数的路径。研究多约束条件下的多个线性目标优化的Qos路由问题。选取带宽作为约束条件，线性函数(时延和耗费徘为优化目标，建立了Qos路由选择的多目标缉陛整数规划模型。通过将多目标优化问题转化为线性单目标优化问题，证明了新问题的最优解是原问题的有效解，给出一种求解模型的交互式算法。该算法引入目标函数参考点概念，逐步调整目标函数参考点，压缩目标函数搜索空间来满足决策者和实时网络资源要求，并最终得到满意解。仿真实例表明了算法的可行性和可操作性。     

允许缺货和转包的受限批量模型的多项式算法

有效组织带转包的采购计划对企业提高竞争力和参与全球产业分工有重要意义.研究了一个新的非减库存能力约束下的允许缺货和转包的企业采购计划模型,提出了一个基于动态规划的多项式算法.引入子计划概念,将问题归结为有效计算子计划;依据最优解的性质设计了求解子计划的多项式算法;再通过动态规划算法以多项式时间枚举所有可能子计划组合,得到问题的最优解.数值试验显示了该算法的有效性及高效性.     

导引式局部搜索在一类过度约束VRP中的应用

针对一类带时间窗口和容量约束的车辆路线问题(VRP),给出了在过度约束即不存在满足所有约束的可行解的情况下,能够最小化约束违反成本的一种新颖的导引式局部搜索(GLS)算法。该算法通过不断动态修改原问题的目标函数,既保留了局部搜索算法的高效率,又有效克服了局部极小解的局限性,因而能够较快地返回一个满意解。求解示例表明,该算法在求解此类问题时,性能要优于常用的禁忌搜索算法。     

考虑资金借贷与资金约束的单产品批量问题

考虑资金借贷与资金约束对企业生产计划的影响,企业在各阶段的资金量必须大于等于零以避免破产,并且企业的现有资金量必须大于等于该阶段的总生产成本时才能生产一定数量的产品,否则需要借贷资金,或者减少生产量.以企业的期末收益最大作为决策目标,构建包含初始借贷资金与资金约束的单产品批量问题模型.通过对问题数学性质的分析,将原问题转换为最长路径问题,提出一个多项式时间的递推算法,并用一个启发式方法对结果调整使其更接近最优解.当各阶段单位可变生产成本相等时,算法可以在多项式时间内得到最优解;当各阶段单位生产成本不相等时,该算法得到可行解,数值实验显示其与最优解的误差较小;当问题规模较大时,本文算法与CPLEX 12.6.2相比具有计算效率优势.     

混合变邻域搜索算法求解大规模电动车辆路径优化问题

基于真实的物流场景,研究了带时间窗的多车型和多循环电动车辆路径问题.建立了一个基于路径的混合整数线性规划模型,可精确求解小规模算例.提出了将变邻域搜索算法和标签算法相结合的混合启发式算法,用以求解大规模情形.该算法提出了一种带随机因子的启发式算法构造初始解,并对时间窗和里程约束进行了松弛,使用邻域算子进行变邻域搜索,使...     

线性一二次双层规划问题

本文利用对偶理论和Kuhn-Tucker条件来研究线性一二次双层规划问题, 给出一些二层规划解的最优性条件和一个求解二层规划解的算法。这些最优性条件丰富了非线性多层规划的理论, 而其求解算法为求解实际问题提供了有力的工具。一些数值试验结果将在本文未给出, 这些结果表明算法对于小规模问题的求解是相当有效的。     

一种高效的实时交通信号灯控制算法

针对交通信号灯实时控制问题,设计了一种以最小化车辆等待时间为目标的数学模型,并给出了一种能求解该模型最优解的启发式搜索算法.仿真结果显示启发式搜索算法存在求解时间长,求解效率不稳定等问题.因此在原算法基础上加入了多阶段决策优化方法,并且在各个阶段中采用了限时搜索,使得算法能在固定时间内得到结果,保证了算法的稳定性和实时性.通过实际数据仿真显示,优化后的算法对比固定周期算法减少了车辆的等待时间;对比原始的启发式搜索算法,提高了求解效率,满足了实时控制的要求.     

求解模糊目标／资源问题的拟人化算法

介绍一种求解具有模糊资源约束线性规则问题的拟人化算法,它将模糊控制算法嵌在遗传算法之中可以解出一个模糊优解,取代了以往利用单纯形法求解模糊线性规划得到的唯一最优解,通过例子,可以看出该算法能得到一个满意度很高的解．     

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

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

Genetic algorithm for pareto optimum-based route selection

A quality of service (QoS) or constraint-based routing selection needs to find a path subject to multiple constraints through a network. The problem of finding such a path is known as the multi-constrained path(MCP) problem, and has been proven to be NP-complete that cannot be exactly solved in a polynomial time. The NPC problem is converted into a multiobjective optimization problem with constraints to be solved with a genetic algorithm. Based on the Pareto optimum, a constrained routing computation method is proposed to generate a set of nondominated optimal routes with the genetic algorithm mechanism. The convergence and time complexity of the novel algorithm is analyzed. Experimental results show that multiobjective evolution is highly responsive and competent for the Pareto optimum-based route selection. When this method is applied to a MPLS and metropolitan-area network, it will be capable of optimizing the transmission performance.     

Multiple constraints-based QoS multicast routing: model and algorithms

1.INTRODUCTION Multicastserviceshavebeenusedbyvariouscontinu ousmediaapplications.Forexample,themulticast backbone(Mbone)oftheInternethasbeenusedto transportrealtimeaudio/videofornews,entertain ment,videoconferencing,anddistancelearning.The provisionofQoSguaranteesisofutmostimportance forthedevelopmentofthemulticastservices.Multi castroutinghascontinuedtobeaveryimportantre searchissueintheareasofnetworksanddistributed systems[1～4].Itattractstheinterestsofmanypeo ple. Afrequently…     

基于遗传算法与模糊选择的多播路由优化

遗传算法在优化计算特别是在多播路由问题中得到了广泛应用,但在进行大规模优化时,遗传算法存在着爬山能力差以及不成熟收敛等缺点。为此,提出基于启发式遗传算法和模糊选择机制的新型多播树计算方法,本算法采用树型结构编码和高效的遗传操作,同时优化时延、丢包率和带宽利用率等多个参数。仿真实验表明,这种算法用于多播路由多目标优化问题时,可以克服采用遗传算法进行多目标优化的缺陷。     

求QoS路由的整数线性规划方法

QoS路由的任务是在网络中寻找一条满足多个约束条件的路径使网络资源的利用达到最优. 该问题是一个NP-完全问题. 提出了一种新的基于整数线性规划模型选择路由的方法. 思路是将复杂约束引入到目标函数作为罚项, 得到一个松弛整数线性规划问题. 因为约束系数矩阵是全幺模矩阵, 松弛问题可以通过线性规划很快地求解. 拉格朗日乘子的调整用罚函数的方法很容易计算. 数值实验表明提出的方法是有效的.     

基于SDN的卫星网络多QoS目标优化路由算法

针对传统卫星网络中业务类型多样化导致的网络配置复杂和业务服务质量(quality of service, QoS)无法得到有效保障的问题,研究了基于软件定义网络(software-defined networking, SDN)的卫星网络架构,提出了一种能够满足多种QoS需求的自适应路由算法。首先,建立了软件定义卫星网络多约束条件路由选择优化模型；然后，使用拉格朗日松弛法对模型进行松弛处理；最后，使用梯度法进行迭代求解,搜索出满足带宽、时延、丢包率等多种QoS的最优路径。研究结果表明,该优化算法在QoS满意度方面相比近地轨道卫星路由算法提高了64%,在时延满意度和丢包率满意度方面相比软件定义路由算法提高了28%。     

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

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

Algorithm for multi-constrained path selection based on experimental analysis

1. INTRODUCTION It is a challenging problem to provide quality-of-servi- ce (QoS) guarantees in next generation high-speed network, and the QoS routing is one of the key issues of the problem. The problem of routing optimization for different QoS requirements has attracted more and more attention and has becomes a hot issue in this field[1~6]. The QoSR problem deals with the metric parameters including bandwidth, delay, delay jitter, loss probability, reliability and hop count. Based o…     

A Heuristic Algorithm for QoS Multicast Routing

In recent years, QoS multicast routing has continued to be a very important research topic in the areas of networks. This paper presents a heuristic algorithm for the QoS multicast routing (HAQMR). This heuristic algorithm deals with delay and bandwidth constraints and has low cost. The HAQMR attempts to significantly reduce the overhead for constructing a multicast tree, the proof for correctness of the HAQMR is given, and the performance of the HAQMR is evaluated by simulations. The study shows that HAQMR provides an available approach to QoS multicast routing.     

一种基于改进蚁群算法的多点路由算法

蚁群算法是一种新型的随机优化算法,蚁群算法与其它随机优化算法同样存在收敛速度慢易于限于局部最小点等缺陷.提出一种改进的蚁群算法,并将其与启发式方法相结合以解决多点路由问题.仿真证明,基于改进蚁群算法的多点路由算法模型可以稳定地获得优于现有启发式算法的解,是一种有效的多点路由算法,同时该算法也适用于并行执行和应用.