基于业务量工程带宽和时延约束的QoS路由算法

研究IP网络中带宽约束和时延约束条件下的路径选择问题,提出基于业务量工程的带宽约束和时延约束的服务质量路由算法．通过计算机仿真,比较SPF,SDPF和SEDPF三种算法在相同的物理网络拓扑结构、不同的链路带宽资源下的性能．结果表明,在链路带宽不均衡情况下SEDPF算法具有优势。     

基于拉格朗日松弛的水灾逃生路径规划

研究了假设路段通行时间为随机变量的交通网络约束最短路径问题.建立0-1整数规划模型,求出最小期望通行时间路径.除流量平衡和路段通行能力约束外,还引入了唯一通路选择约束以保证最终只能生成最优路径.然后,提出了拉格朗日松弛法对难约束进行松弛处理,并将松弛模型分解成两个子问题.结合次梯度算法、标号修正算法和k-最短路径算法设计了一个算法框架,以最小化上下界的差距寻找近似最优解,用改进的算法框架进行求解.最后将该框架应用于龙岩市新罗区进行了计算试验.结果表明,该算法能够找到相对间隙较小的高质量解,验证了该方法的有效性.     

交通网络最优安全路径选择模型与算法

针对交通网络任意路段均可能发生中断的最小损失路径选择问题,提出交通网络最优安全路径选择模型,并设计了2种不同网络结构下最优安全路径选择算法.首先用模型计算任意一条路径上每条边中断后产生的从起点到终点最短替代路径长度的最大值,然后选择一条最短替代路径长度最大值最小且自身长度最小的路径.在网络中,当最短路径删除后该网络依然连通时,最优安全路径问题转化为最短路径问题,其计算复杂度为O(n2);当最短路径删除后该网络不再连通时,最优安全路径问题转化为最小最大问题,其计算复杂度为O(mn),且仅与网络中节点和边的数量有关.最后,结合交通网络的实际情况对最优安全路径进行了算例分析.     

广义半无限极大极小规划的一个新的最优性条件

由于广义半无限极大极小问题的极大函数的约束集合随x的变化而变化,增加了对该问题的理论分析和求解难度.为了克服这种情况,许多研究者考虑通过转化消除约束集合中的约束f(x,y)≤0.本文是通过一类由1范数定义的精确罚,将广义的半无限极大极小规划中的约束条件消除,使该问题转化为半无限极小极大极小规划.在不需要假设集合的条件下证明,当罚参数充分大时,半无限极小极大极小规划与广义半无限极大极小问题具有相同的最优值,相同的局部最优解以及相同的全局最优解.利用这种等价性,进一步给出了广义半无限极大极小问题的一个最优性条件.最后,对本文中建立的最优性条件与其它文献中的最优性条件之间的关系进行了讨论.     

机组最优负荷分配的动态规划网络方法

本文在文的基础上,将考虑机组出力上下限约束和功率平衡约束的机组最优负荷分配问题离散为一个等效网络,分析了该网络在约束条件下各顶点及各边的构成规律.从而把给定机组组合时的最优负荷分配的求解转化为最短路径的动态规划法对该等效网络的求解.     

动态流量多约束优化路径算法

基于多重上联链路网络,建立一个考虑多服务质量(QoS)度量约束限制的网络路径寻优调度模型,并针对时延和剩余带宽提出动态流量多约束优化路径算法(MOPA).基于MOPA和最短路径约束,给出了具有一个多重上联链路的确定性网络拓扑中实现优化流量费用的工程方法.通过分析网络资源现状及目标作用的重要程度,以主次目标形式考虑,建立目标之间的关联,简化多目标之间关系,使用迭代方法求解非线性约束条件下的流量和代价的优化解,动态选择最优路径使流量费用比最优化并实现工程应用.实验表明,该算法适用于多链路网络各种负载下的流量优化.     

基于改进蚁群算法的智能物流配送路径优化方法

针对交通日益拥堵情况下的物流配送路径的优化选择问题,提出了一种基于改进蚁群算法的智能物流配送路径优化方法.首先,对传统基于单一路径最短优化的思路进行了扩展,提出了基于多约束条件的最优路径质量评价函数,并推导分析了不同约束情况下的最优路径模型;然后,基于多约束条件对传统蚁群算法状态转移启发函数和信息素进行了改进,较好地改善了算法的动态优化性能.计算机仿真结果表明,本文方法很好地提升了复杂路况下最优路径的寻优精度和收敛速度,具有较好的应用前景.     

处理带约束的多目标优化进化算法

针对当前对求解多目标优化的遗传算法中主要考虑如何处理相互冲突的多个目标间的优化,而很少考虑对约束条件的处理的问题,提出一种求解带约束的多目标优化遗传算法,利用邻域比较与存档操作遗传算法处理多个相互冲突的目标之间的优化、利用不可行度选择操作处理约束条件和选用约束主导原理指导进化过程选择操作; 面向多目标约束优化算法,列举了2个难点典型问题进行仿真计算研究,仿真结果表明该算法能较大概率地获得多目标约束优化问题的可行Pareto最优解.     

约束优化问题的内点正则牛顿法

研究了求解具有不等式约束最优化问题的内点正则Newton法.其基本思想是把求解约束优化问题的内点法和求解无约束优化问题的正则Newton法结合起来,建立起求解具有不等式约束最优化问题的内点正则Newton法.对于具有有界最优解集的凸约束最优化问题,任取一可行解作为初始点,内点正则Newton法所产生的点列均收敛到最优解...     

一种新的求解约束优化问题的遗传算法

科学和工程领域中的许多问题最终可以归结为求解一个带有约束条件的函数优化问题,本文针对此类约束优化问题提出了一种新方法,它把约束优化问题转化为双目标优化问题,并利用遗传算法从多点出发寻找最优解的特性,设计新的交叉、变异和选择算子,使得算法迅速找到问题的最优解。数据实验结果表明该算法对约束优化问题的求解是有效的。     

带有二次约束的一般二次规划问题的松弛分枝定界方法

考虑带有二次约束的一般二次规划问题的求解，当约束条件为非凸二次函数时，对原问题中的某个二次约束进行凸二次松驰，或在原问题的约束条件中增加一个球约束，使得原问题的可行域包含在松驰二次规划问题的可行域内。采用椭球剖分策略剖分可行域为小 椭球，用投影次梯度算法解松驰二次规划问题的拉格朗日对偶问题，从而获得原问题的一个下界。原问题最优值的一个上界可从迭代过程中的可行点得到，并在迭代过程中得到调整。该算法或在原问题最优值的一个上下界相同时终止，得到原问题的整体最优解；或产生一无限序列，其任一聚点都是原问题的整体最优解。     

城市交通网络路径寻优模型及其求解

路径寻优问题是交通网络优化中的基本问题.由于现实交通网络中的交叉口存在不同程度的转向延误,使得一般的最短路模型与算法并不适合城市交通路网,针对这类问题,设计带交叉口转向延误的交通网络路径寻优模型,并根据模型解的特征,将路径寻优模型转化为只含有0,1变量约束的非线性规划问题,随后采用基于增广Lagrangian法的遗传算法来求解该模型.仿真结果表明该模型和算法是有效的.     

非线性优化中关于鞍点及对偶问题的研究

讨论了非线性优化中Lagrange函数的鞍点与原问题和对偶问题的最优解之间的关系,并对对偶理论中的一些性质给予详细证明.对于凸规划在一定约束规格下鞍点总是存在的,可以通过求解鞍点问题来求最优解.最后给出在不等式约束条件下求鞍点的一个迭代方法.     

高速公路通道路网交通诱导决策模型

为解决灾变事件发生时一条最优路径和多条可绕行路径的决策问题,应用图论及最优化理论相关方法构建模型.以通道路网为研究对象、实时安全可靠度为基本约束条件,采用图论相关方法研究了诱导起终点间通路求解方法.应用最优化理论建立运营安全最优路径决策模型,并采用Dijkstra算法求解最优路径.在解决最优路径的基础上,引入重复度的概念及相应算法,研究其他可绕行路径的决策模型.针对高速公路通道路网,构建了灾变事件下的交通诱导决策模型,解决综合考虑安全、行程时间和通行需求的路径决策.结果表明,图论方法能求解任意起终点间的所有通路,Dijkstra算法能求解最优路径,应用重复度算法可寻求其他可绕行路径以满足灾变事件下的绕行需求.     

面向鲁棒性的高速铁路网络列车运行调整计划优化模型

针对高速铁路路网中出现区间封锁事件,考虑事件持续时间的不确定性,以列车运行时间和安全间隔时间为约束条件,引入路径选择唯一性约束保证列车运行调整计划的鲁棒性,以所有列车晚点时间之和的期望值最小为目标函数,建立高速铁路列车运行调整计划优化整数规划模型.设计基于优先级规则的启发式算法,求解原模型的可行解.运用拉格朗日松弛算法和最短路径算法求解该模型的松弛模型,得到原模型最优解的下界.根据可行解与最优解下界之间的距离,可以定量地衡量可行解的质量.结果表明,相较于CPLEX数学求解软件,算法求解效率较高;模型与算法能够有效生成鲁棒的列车运行调整计划,为调度员提供必要辅助决策信息.     

基于双群体的非线性约束规划进化算法

在求解非线性约束规划问题中,对其约束条件的处理是一个难点问题.本文提出了一个非线性约束规划的双群体进化算法,与以往存在的约束优化算法不同之处在于:定义个体对约束条件的函数值作为约束违犯度对群体中的个体进行度量,目标函数值作为最优解的度量.首先考虑了标准的约束规划问题,简单介绍了约束优化问题中约束条件的处理方法,给出了与这些方法不同的处理方法.针对约束违犯度,定义了两个群体,即可行群体与不可行群体.然后给出了双群体进化算法详细步骤,用5个Benchmark函数测试了此算法,并通过与其它已知算法对此5个函数的计算结果的比较,验证了算法的可行性和有效性.     

交通分配起点算法的实证研究

以交通网络为对象,研究求解均衡网络模型的起点算法原理及其实际应用.起点算法是一种基于路径树的交通网络流量分配方法,它按照交通分布起点把交通分配问题分解成若干个子过程.若干个子过程在网络空间的叠加,形成交通网络流量.在每个子过程中,在具有同一起点的若干起终点对之间,所有路径满足Wardrop原则.在比较不同收敛标准的基础上,提出最大-最小路径费用差作为起点算法的收敛准则.选用国内外不同规模的5个城市交通网络数据,对起点算法进行测试,结果表明,起点算法具有很好的稳定性,能够满足任何给定的精度要求.采用最大-最小路径费用差作为起点算法的收敛标准,能够真实反映起点算法的卓越性能,精确表现交通网络均衡原则.     

剩余最短路径算法应用于起迄点交通调查统计

从研究旅行者的出行行为特征出发，并结合道路网拓扑关系，提出一种全新的剩余最短路径算法，用于起迄点交通量调查统计．对于每个起迄点对，先找到连接这个起迄点对的最短路径，再把这个路径上调查到的交通量从路段上转移到该起迄点对上．再寻找剩余的下一个最短路径，也把相应的路径调查交通量从路段上转移到起迄点对上．这样重复下去，直到该起迄点对的交通量全部从调查路段上转移至起迄点对．该方法可以有效解决交通出行被重复统计和被遗漏的情况，还可以为今后的起迄点调查提供更合理的测点．     

有流量附加约束动态交通网络平衡的变分不等式表示

为了研究有流量附加约束的动态交通网络平衡问题,将附加约束等价地当作路径的新增阻抗,得到了基于有流量附加约束条件下的Wardrop用户平衡的变分不等式表示,并提供了计算这种平衡配流的另一种方法。该方法由于考虑了路径容量约束,使得这种变分不等式表示更接近现实中有路径流量限制的情形。     

一种基于Minmax算法的混合MIMIC算法

将Minmax算法与MIMIC算法相结合,提出一种基于Minmax算法的混合MIMIC算法.该算法不再利用传统的约束保持法和可行规则法处理约束条件,而是结合Minmax算法的思想将约束问题转化为无约束问题,并利用MIMIC算法对无约束问题求解.数值试验结果表明:该算法能收敛到满足约束条件的全局最优解,并且具有很强的全局搜索能力,为解决非线性约束优化问题提供了一种新的有效途径.