航天测控调度问题的拉格朗日启发式算法

通过分析航天测控调度问题的测控需求,建立了航天测控调度0-1整数规划模型,运用拉格朗日松弛方法对模型中的任务约束和设备约束进行了松弛,运用次梯度优化算法求得了航天测控调度问题上界,同时得到了决策变量对应的拉格朗日权重,可以作为决策变量在最优解中是否被调度的启发式信息,对拉格朗日权重进行分析,提出了求解问题可行解的拉格朗日启发式算法。最后,通过对两个场景的试验分析验证了拉格朗日启发式算法所求可行解的优越性。

增强拉格朗日松弛启发式算法分析

随着优化问题复杂度的不断提高,传统的拉格朗日松弛启发式算法已经无法满足现代人工智能的计算需求。为增强拉格朗日松弛启发式算法,本文首先说明了启发式算法的定义以及特点,其次分析了目前拉格朗日松弛启发式算法分析中存在的算法性能不稳定、求解质量难以保证以及计算时间和空间限制等挑战,最后针对具体挑战,采取了一系列创新措施增强拉格朗日松弛启发式算法的性能,实现了对拉格朗日松弛启发式算法性能的提升,以此为相关人员提供实践参考。

三阶段拉格朗日启发式算法求解带同时取送货的绿色车辆路径问题

针对带同时取送货的绿色车辆路径问题,以最小化带碳排放费用的配送成本为优化目标,建立混合整数规划模型,并提出一种结合数学规划方法与启发式算法的三阶段拉格朗日启发式算法进行求解.第1阶段,利用拉格朗日松弛技术得到该问题的拉格朗日对偶模型;第2阶段,设计一种改进的次梯度算法迭代求解该对偶模型,同时引入修复机制,将每次迭代所得下界对应的解修复为原问题较高质量的可行解,并在下次迭代中利用该可行解更新次梯度方向和步长;第3阶段,设计一种启发式局部搜索算法,对第2阶段得到的可行解进行优化,进一步改进解的质量,以得到原问题的近似最优解.实验表明,所提出算法能够获得问题的一个优质解,同时提供一个紧致下界,用以定量评估解的质量.

考虑高低速列车灵活混行和停站的运行图优化

为了提高不同速度列车对轨道资源的占用效率,在高速铁路列车运行图编制过程中,同步优化了高低速列车的混行数量和停站方案。通过构建分层时空网络来刻画不同速度列车运行过程,选取最小高速列车开行数量和OD停站次数来保证旅客基本的出行要求,利用单列车最大停站次数限制列车停站均衡性,建立基于时空弧变量的线性整数规划模型,实现总列车运行成本最小。在拉格朗日松弛框架下,由于所建模型耦合了不同弧变量于一起,需要松弛大量的耦合约束才能实现模型分解,使得该方法难以产生高质量的下界和原问题可行解。为此,利用变量分离技术,引入列车类型和停站方案2类0-1变量,重构优化模型;运用拉格朗日松弛方法,重构模型能够分解为时空路径子问题、列车类型子问题和停站方案子问题;在子问题求解中,构造附加约束保证列车类型指派的可行性,构建替代停站子问题加速算法求解;基于下界对偶信息,设计了两阶段启发式方法用于求解原问题可行解。以京沪高铁为背景,设置多组不同规模算例,利用上述方法进行求解,结果表明所提方法可以在合理计算时间内有效求解大规模问题,能够获得较紧致下界和近似最优解,并在求解质量上优于传统松弛分解方法,展现出良好的求解性能。

物流网络设计建模与求解算法研究

研究了制造系统中物流网络设计问题,构建了一个带固定费用的容量受限的网络设计模型,提出了一种求解该问题的基于拉格朗日启发式算法的增强型分枝定界方法。通过大量的试验测试,结果表明该算法能有效地解决大型的具有NP-hard特性的网络设计问题。

基于系统可靠性的生产与维护计划联合决策

为准确构建生产系统中批量生产与设备维护之间的关联关系,以并行机系统产能受限批量计划问题为基础,提出并引入基于系统可靠性的预防性维护策略与成组维护策略,建立了以生产与维护总成本最小化为目标的生产计划与预防性维护联合决策模型,从而在保证系统生产效益的前提下优化系统的维护频率、减少系统中生产与维护的总成本。模型的求解采用基于产能约束松弛的拉格朗日松弛算法框架,并设计了基于移动平滑方法的构造启发式算法,以获得问题的可行解并协同优化系统生产和维护计划。数值实验表明,该模型能充分发挥并行机的协调能力,有效避免设备过度维护问题,从而降低生产与维护总成本,所设计的算法具有较好的求解性能。

带投资约束p-中位问题的混合蚁群算法

将投资限制引入经典约束p-中位问题,提出带投资的约束p-中位问题,该问题更适用于交通、物流等领域的设施选址。在深入分析带投资约束p-中位问题的数学模型的基础上,首先提出了适用于该问题求解的局部搜索策略;其次,将局部搜索策略与拉格朗日启发式算法和蚁群算法相结合,设计了求解该问题的拉格朗日混合蚁群算法。实验结果表明,带投资的约束p-中位问题能够根据投资金额规划不同的投资方案;且提出的混合蚁群算法较大程度上提高了蚁群算法和拉格朗日启发式算法的求解精度,具有较好的收敛性。

考虑企业沉没成本的工厂选址问题

研究了企业在规模经济时带建站费用、有容量约束的工厂选址问题.把传统的容量约束适当放松,同时引入了沉没成本,以避免过大的生产规模和过多设备剩余,这样的选址决策不仅满足企业当期的要求,也为其未来的发展预留了空间.同时,建立了该问题的数学规划模型,并对所建模型给出拉格朗日松驰算法,用随机选取的一组数据对算法进行检验,实验结果显示相对误差在4%以内,求解的时间也很短.

公共自行车租赁点选址优化方法研究

租赁点选址和车辆调度是公共自行车系统两个重要决策问题.本文考虑租借行为、调度活动及用户需求在各个时间段内的相互联系,将运营时间划分为多个时间段,以最小化未满足需求为目标函数,构建了整数线性规划模型,从而确定公共自行车系统租赁点位置、桩位配备数量及每个时间段初始时刻租赁点的自行车库存量.模型的复杂性导致精确求解大规模实例时间成本较高,为此设计了遗传算法和拉格朗日启发式算法以提高求解效率.通过算例分析,验证了模型及算法的有效性及可行性.计算结果表明:成本提高能引起用户满意率的增加且边际满意率在递减;当参数改变时,计算性能明显受到影响.

钢卷装炉组合模型及算法仿真研究

分析了宝钢冷轧薄板厂罩式炉退火车间钢卷装炉的工艺特点和约束,建立了多炉型、不确定炉数下的装炉组合多背包模型。该模型考虑了最佳装炉量和最大炉高约束,将装炉数作为一个不确定数量。对于模型的求解,首先利用拉格朗日松弛启发式算法求得装炉数的上界,缩小解的搜索空间,然后构造了一种基于局部基因片段保留算子和反序-杂交遗传算子的新型单亲遗传算法进而求解。生产数据的仿真结果及试运行表明,提出的模型和算法切实可行,应用效果良好。

A novel two-stage Lagrangian decomposition approach for refinery production scheduling with operational transitions in mode switching

To address large scale industrial processes,a novel Lagrangian scheme is proposed to decompose a refinery scheduling problem with operational transitions in mode switching into a production subproblem and a blending and delivery subproblem.To accelerate the convergence of Lagrange multipliers,some auxiliary constraints are added in the blending and delivery subproblem.A speed-up scheme is presented to increase the efficiency for solving the production subproblem.An initialization scheme of Lagrange multipliers and a heuristic algorithm to find feasible solutions are designed.Computational results on three cases with different lengths of time horizons and different numbers of orders show that the proposed Lagrangian scheme is effective and efficient.

三级物流网络选址-路径问题建模与求解算法研究

鉴于固定费用选址问题的一个重要局限是在运输成本的计算中,假设采用整车运输方式,其运输成本与考虑运输路径时的成本不同会影响选址决策.针对一个钢材销售企业的三级物流网络中的两级设施进行选址,采用多站式运输方式计算运输成本,问题为三级物流网络选址-路径问题.采用嵌入拉格朗日启发式算法的分枝定界方法来求解,并对该方法进行了实验测试,测试结果表明该方法是有效的.