基于区域目标网格化的多星协同观测方法

通过分析多颗SAR卫星对某一大面积区域目标进行协同观测的约束条件,以给定任务周期内观测收益最大为目标函数,建立约束满足模型。为改善传统的禁忌搜索算法在多星协同观测任务中易收敛于局部最优解的问题,提出一种改进的变邻域禁忌搜索算法。在算法实现的过程中,将区域目标网格化从而动态生成观测模式,并计算各模式对应的观测率。相对于传统的禁忌搜索算法,该变邻域禁忌搜索算法在同等资源下可将观测收益提高8%以上。

基于混合平衡优化器算法的多目标柔性作业车间多重动态调度研究

面对生产过程中出现的多种扰动问题对实际调度过程的影响,构建以紧急订单和机器故障为扰动因素,以最小化最大完工时间、最小化订单拖期惩罚和最小化碳排放为目标的柔性作业车间多重动态调度模型。采用基于事件和周期的混合动态调度策略来应对突发事件,并提出一种改进的平衡优化器算法来求解该模型。该算法通过采用基于精英反向学习的混合种群初始化策略提高初始种群质量;通过采用IPOX交叉、MPX交叉和变异操作,提高算法解集的广泛性和多样性;通过使用基于Metropoils准则的精英选择策略来更新种群,防止种群陷入局部最优;通过双层变邻域搜索提高算法的寻优能力。通过大量拓展算例仿真验证了该算法的有效性、稳定性和优越性。

自动化立体仓库中环形2-RGV系统入库调度模型与求解算法

确定合理的货物运送序列,实现穿梭车(RGV)与堆垛机协同作业是提升自动化立体仓库中环形2-RGV系统搬运效率的重要手段。通过对RGV在环形轨道运作环境下的碰撞情况进行分析,以货物总入库时间最小化为目标,考虑了同一辆RGV运送、两RGV碰撞避免以及RGV与堆垛机协同运作等约束,构建了环形2-RGV系统入库调度问题的混合整数规划模型,设计了可快速求解问题的混合变邻域禁忌搜索(HVNTS)算法。为验证算法的有效性,设计了25组不同规模的算例,并将HVNTS算法的求解结果与CPLEX和禁忌搜索算法的求解结果相比较,算例实验结果表明:货物的平均入库时间分别节省了0.36%和8.67%,且HVNTS算法的求解时间均在3 min内,证明所提算法能快速有效地求解该问题。

基于混合算法的具有硬时间窗口约束的VRPSPD问题

具有硬时间窗口约束下同时收发的车辆路径问题(vehicle routing problem with simultaneous pick-up and delivery with hard time windows,VRPSPD with Hard TW)是将产品配送和废物回收统一进行优化的问题。本文研究了一个中心仓库,多台车辆向具有配送需求和回收需求的客户提供服务,客户存在硬时间窗口要求的车辆运输问题。该问题中,客户的配送需求和回收需求必须同时获得满足,即客户仅允许被访问一次,且需求不可分割,只能由一台车辆提供服务。且客户的硬时间窗口要求必须获得满足。首先将修正后的旅程分割方法应用于硬时间窗口约束下的VRPSPD问题初始解的获得,并利用响应性禁忌搜索算法框架,结合基于多种领域的可变式搜索方法,给出一启发式算法。计算机实验结果表明,该启发式算法在求解VRPSPD with hard TW上是有效的。

随机活动工期下基于总不确定成本的项目前摄性调度与反应性调度集成优化

从成本经济角度研究活动工期随机中断下前摄性调度与反应性调度在应对不确定因素干扰中的集成优化问题,目标是最小化项目计划与实施过程的总成本。构建以总成本最优为目标的前摄性与反应性调度集成优化模型;针对模型特征设计混合变邻域随机禁忌搜索启发式算法,并在ProGen生成的算例上进行全因子测试。结果表明:基于随机属性的混合启发式算法在算例规模较大时可以发挥较好的作用;通过合理设置基准进度中缓冲分配方案,可以通过牺牲部分鲁棒性的方式获得项目总成本的最优。

一个具有仓库容量选择的两阶段设施选址问题的模型及算法

设施选址及其规模选择优化对供应链的长期战略成本和运营成本有着重要影响,是提高企业利润和竞争力的关键决策之一,也是运筹优化领域研究的热点与难点.针对已有的两阶段设施选址问题(two-stage facility location problem,TSFLP)研究中缺乏对设施容量选择的优化,在设施选址问题基础上引入了设施容量选择的优化,同时确定了工厂的位置、仓库的位置和容量、从工厂到仓库的产品流以及客户到仓库的分配,建立了以最小化总成本为目标的混合整数规划模型,并基于模型特点设计了适合求解此问题的拉格朗日松弛(Lagrangean relaxation,LR)方法和混合变邻域禁忌搜索(hybrid variable neighborhood tabu search,HVNTS)算法.基于随机生成的大量具有不同参数的实例,验证了所提出的算法可有效求解大规模的、且需同时优化设施选址及容量选择的问题.

随机环境下基于成本经济的项目调度权衡优化研究

针对随机环境下项目前摄性调度与反应性调度在应对不确定因素过程中起到的不同作用,从成本经济角度出发,研究了如何通过两种调度方法的权衡实现项目计划与执行的最优配合。在此基础上构建了基于成本的前摄反应调度权衡模型,通过对鲁棒性成本与调整成本进行量化分析,实现两种调度方案的最佳权衡。考虑到问题的NP难属性,设计了基于混合变邻域禁忌搜索的随机两点启发式算法,并通过大规模算例测试验证了算法的有效性。结果表明,根据承包商对成本的敏感度,前摄性调度与反应性调度在应对不确定性因素干扰中承担的工作量会随着成本权衡比的变化而发生改变,逐渐从前摄性方法为主过渡到以反应性方法为主。最后,从项目管理角度给出了有价值的管理启示。

一种新型轻小包裹高速分拣系统调度算法

新型轻小包裹高速分拣系统综合应用两种不同类型的机器人(分拣机器人、料箱搬运机器人),首先分拣机器人将包裹先分拣至分拣区域内的周转料箱中,当周转料箱满箱后,料箱搬运机器人将之搬运至装箱区域打包。该系统可以基于分拣需求的变化动态调整分拣系统中机器人数目以及分拣区域面积大小,有利于降低分拣作业设备损耗及系统能耗。本文针对这种新型轻小包裹高速分拣系统调度问题展开研究,首先建立了综合考虑两种机器人、两阶段分拣过程(先分拣到周转料箱,再搬运周转料箱至打包位置)和动态分拣料口(分拣区域内周转料箱放置点不是固定的)的基于最低分拣成本的三维度调度模型;其次针对该调度模型两阶段三维度调度的特点,设计了一种两段三层可行解整数编码,及一种基于编码编辑距离(Levenshtein距离)的计算种群多样性的方法;然后,设计了一种结合两种变邻域算子(交换算子、贪心算子)和禁忌搜索的混合分散搜索算法,对模型进行求解;最后使用改进的MAPF基准测试数据集,对上述模型和算法进行了验证。实验结果表明:本文提出的模型有效,能满足实际使用要求,求解算法的求解精度相较于标准遗传算法、标准分散搜索算法分别提升了10.3%和6.5%,收敛速度相较于标准分散搜索算法提升了15.5%,且数据集规模越大,本算法的收敛速度优势越突出。

基于自适应变邻域搜索算法的一类混合流水车间调度问题

混合流水车间调度是一类典型的生产调度问题,属于NP-难问题。传统的研究通常针对中间存储无限的情况,但是在实际生产中,相邻工序之间的存储一般是有限的。针对中间存储能力有限的混合流水车间调度问题,建立了该问题的混合整数规划模型,并提出了一个自适应变邻域搜索算法。在算法中,针对混合流水车间调度问题的特点,提出了基于工件顺序的编码及解码方法。针对传统邻域类型广域搜索能力不足的问题,提出了基于块删除与插入的大规模邻域搜索,并提出了邻域规模的自适应选择机制。基于随机测试问题的实验结果表明,所提出的自适应变邻域搜索算法具有较好的局域与广域搜索能力。

考虑多急件到达的作业车间重调度研究

为解决大规模急件插单重调度优化问题,以最小化最大完工时间及加权延期成本为目标,构建混合整数规划模型。提出基于新的匹配策略的混合遗传禁忌搜索算法对该问题进行求解,采用基于贪婪规则的启发式算法改进初始解的质量,提出基于自适应的变异算子选择算法,同时引入部分非关键工序交换规则改进N5邻域结构,提高算法的局部搜索能力。实验结果验证了所提算法的有效性和可行性,并表明急件插单时间发生的越早,该算法优越性越突出。

Free-floating bike-sharing green relocation problem considering greenhouse gas emissions

This paper introduces the problem of green bike relocation considering greenhouse gas emissions in free-floating bike-sharing systems(FFBSSs)and establishes a mathematical model of the problem.This model minimizes the total imbalance degree of bikes in the FFBSS and the greenhouse gas emissions generated by relocation in the FFBSS.Before the relocation phase,the FFBSS is divided into multiple relocation areas using a two-layer clustering method to reduce the scale of the relocation problem.In the relocation phase,the relocation route problem is converted into a pickup and delivery vehicle-routing problem.Then,an adaptive variable neighbourhood tabu search algorithm with a three-dimensional tabu list is proposed,which can simultaneously solve the relocation problem and the routing problem.A computational study based on the actual FFBSS used in Shanghai shows that this method can effectively solve the green relocation problem of FFBSSs.