Finding a Noncrossing Steiner Forest in Plane Graphs Under a 2-Face Condition

Let G = (V,E) be a plane graph with nonnegative edge weights, and let be a family of k vertex sets , called nets. Then a noncrossing Steiner forest for in G is a set of k trees in G such that each tree connects all vertices, called terminals, in net N _i, any two trees in do not cross each other, and the sum of edge weights of all trees is minimum. In this paper we give an algorithm to find a noncrossing Steiner forest in a plane graph G for the case where all terminals in nets lie on any two of the face boundaries of G. The algorithm takes time if G has n vertices and each net contains a bounded number of terminals.     

Optimal Augmentation of a 2-Vertex-Connected Multigraph to a k-Edge-Connected and 3-Vertex-Connected Multigraph

Given an undirected multigraph G = (V, E) and two positive integers and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an -edge-connected and k-vertex-connected multigraph. In this paper, we show that the problem can be solved in Õ(mn²) time for any fixed and k = 3 if an input multigraph G is 2-vertex-connected, where n = |V| and m is the number of pairs of adjacent vertices in G.     

并行工程产品开发过程定量化建模与计划制订

由于现有的一些并行工程定量化模型中修改设计微循环的细节特征描述得还不够充分 ,本文提出了一种新的基于产品 -工艺设计活动对网络的定量化模型来描述并行工程产品开发过程 ,并且给出了产品 -工艺设计活动对平均持续时间与产品或工艺设计活动资源占用率的计算方法 .在此基础上 ,将并行工程产品开发过程的计划制订问题建模成一个有资源约束的项目调度问题 .与其它此类问题不同的是 ,在本文中 ,分配给产品开发项目的各类资源的数量不是事先给定的 ,而是与最优产品开发计划一起获得的 ,所以这是一个资源分配与计划制订的集成优化问题 .本文提出了一种新的基于分枝定界的算法来解决此问题并引入一个启发式规则来提高算法的搜索效率     

考虑实时预倒箱的出口箱堆场多场桥调度优化

在出口集装箱堆场的实际作业过程中,倒箱是制约场桥作业效率的瓶颈之一。为提高出口箱堆场的作业效能,减少船舶装船作业时间,采用实时预倒来降低倒箱的影响,研究出口箱堆场多场桥调度优化问题。考虑待提箱作业次序固定、场桥间保持安全距离及不可跨越的现实约束,兼顾内集卡的等待上限,侧重场桥作业过程中的实时预倒箱,构建了以带惩罚因子的内集卡总等待时间最少为目标的混合整数线性规划模型。基于问题自身的特点设计了混合和声模拟退火算法,得出了各场桥的行走路径与实时预倒箱方案。在算例实验中,通过与不考虑实时预倒箱的方案、FCFS方案以及下界进行对比,验证了考虑实时预倒箱的场桥调度模型及算法的有效性,为集装箱码头出口箱堆场的场桥调度提供参考。     

基于随机p-鲁棒优化的国家血液战略储备库选址-库存模型

以往的救灾实践对建立国家血液战略储备体系提出了迫切要求。国家血液战略储备库的建设问题亟待解决。由于血液产品特性以及应急血液保障特性的存在,使得国家血液战略储备库的选址决策具有一定的复杂性。本文将问题定位为选址-库存问题。首先,以应急条件下血液保障及时度最高为目标,构建了一个不确定环境下考虑多情景、多血型、多阶段、带提前期、有容量限制、日常随机需求、有预算约束及协同定位的国家血液战略储备库选址-库存模型。同时,为了规避应急条件下的不确定风险,进一步构建了国家血液战略储备库选址-库存问题的随机p-鲁棒优化模型。该模型为离散非线性混合整数规划模型,难以快速精确求解。故基于模型性质,设计了相应的遗传算法。最后,设计了两组算例验证模型与算法的有效性。其中,第1组算例基于我国大陆地区31个省级血液中心与省级行政区的数据,并根据不同预算值给出6个算例,得到了国家血液战略储备库的选址-库存决策方案。第2组算例为6个不同规模的模拟算例,用来测试不同规模下的算法性能。算例结果表明：遗传算法的性能更好;鲁棒解与确定性模型最优值相差不大（最大差距≤1.08%）,可降低不确定性导致的风险。实践中,可对本文所建模型稍作改进,应用于具有类似特征的易腐品（药品、粮食等）应急物资储备库选址-库存决策。     

震后伤员救援车辆两阶段规划模型及算法研究

不确定情景下的应急物资配送和车辆路径优化问题是目前国内研究的一大热点,其中 震后伤员运送车辆调度及路径优化问题随着近几年地震等自然灾害的频繁发生也逐渐引起人 们的重视． 本文采用聚合优化算法对灾区进行应急救援区域划分,建立了以总救援时间最短和 相对综合救援权重值最大为目标的救援车辆两阶段数学规划模型,设计了带三角函数变异的 离散型萤火虫优化算法进行求解,并与常规算法求解结果做了对比分析． 通过算例进行模拟实 验表明,所提出的模型和算法可以有效解决地震情景下的伤员救援车辆调度问题,且改进算法 的全局搜索性能更优．     

考虑最坏中断损失下的P-中位设施选址问题的模型与算法研究

蓄意突袭以及恐怖袭击会造成设施服务的突然中断成为网络系统的主要危害之一,因此网络设施选址决策应该同时考虑正常和紧急状态下系统的运作成本.本文研究考虑最坏中断损失下的网络设施选址问题,建立了该问题的双层规划模型,上层规划涉及设施选址决策,下层规划研究确定设施位置后,设施中断产生最大损失的问题.本文运用基于拉格朗日松弛的混合遗传算法来求解该双层规划问题.将European150数据集作为研究对象,对比研究了本文研究问题与传统的P-中位选址问题的结果,分析不同选址策略下网络系统的效率被中断影响的程度是不同的.最后通过改变一些关键参数,比如常规运作权重、设施数量、中断设施数量,对相关结果进行了分析.     

模糊环境下考虑缺货和延期支付的Stackelberg均衡策略

在具有价格弹性需求的两层供应链系统中,考虑到价格弹性指数的模糊性和供应链延期支付策略,建立了含缺货的制造商-零售商协调模型.运用符号距离反模糊化方法将其转化为确定模型.基于遗传算法,设计了其求解方法,获得了制造商最优信用期和零售商最优零售价.数值结果表明:模糊环境下的延期支付策略降低了产品的市场零售价,同时增加了供应链中各成员的利润,因此实现了供应链协调.进一步分析显示当模糊价格弹性指数的上(下)界变化反映出的不确定性减弱时,制造商提供更长的信用期,且制造商和零售商的利润均增加(减少).     

基于求解TSP问题的双向扩展差额算法

旅行商(TSP)问题是典型的组合优化中的NP-hard难题.本文在最近城市搜索法和两端延伸最近城市搜索法基础上提出了双向扩展差额求解算法,并分析了算法的复杂度.采用以上三种算法求解了TSPLIB标准库中多个算例,比较结果表明本算法能够更快的找到更优的方案,具有更好的综合性能.     

多项目人力资源调度实证研究

针对某公寓大修项目,建立有关人力资源约束下的多项目进度管理问题混合整数规划模型。其中考虑了多种约束,如项目对人员能力、水平的不同要求,而人员又具有多种能力及水平;目标为满足约束的条件下总成本最小化,其中包含按时间计费的工资,和福利等的固定费用。为了简化计算,采用列生成法把复杂的多项目模型分解为一个主问题和多个子问题并协调主问题和子问题求解。同时由于子问题的复杂性难以精确求解,采用启发式算法求解:首先由基于优先原则的启发式方法给出问题的初始解,再由遗传算法寻优。最后通过该实际案例的应用,表明此方法能够快速有效的解决实际问题,给决策者提供信息,帮助指导实践。