混合遗传变邻域搜索算法求解柔性车间调度问题

针对考虑生产成本的柔性作业车间调度问题(flow job shop scheduling problem, FJSP),以完工时间与加工成本为优化指标,提出一种求解FJSP的混合遗传变邻域搜索算法。根据个体适应度对种群分割,结合自适应交叉概率改进子代种群产生方式;设计两种邻域结构增强算法的局部搜索能力;提出一种基于动态交叉变异概率的优化算法流程提高求解效率。运用提出的算法求解基准实例与实际问题测试,验证了算法的有效性。

改进遗传算法搜索动态订单下车辆路径最优问题

滚动周期策略是当前学者利用优化算法解决动态车辆路径规划(dynamic vehicle routing planning,DVRP)问题的主要研究策略。预优化算法是基于遗传算法(genetic algorithm,GA)进行改进。GA易早熟和易陷入局部最优的特点,使解的质量往往不能达到最好。针对此问题,在GA算法上提出了贪婪重构策略进行改进。贪婪重构遗传算法(greedy reconstruction genetic algorithm,GRGA)随机剔除每条路径固定数量的客户点,利用贪婪重构策略依次将剔除点插入到各个路径,保留成本最低的解,摒弃了完全随机的策略原则,使解可以跳出局部最优。在每次迭代之后利用变邻域下降搜索算法(variable neighborhood descent,VND)进行深度搜索,完成一次迭代。最后进行三组测试,第一组是在统一平台上采用Solomon数据集测试算法效果,第二组是把预优化改进算法与对比算法得到的数据分别进行保存,利用控制变量法在动态调度周期使用一种动态调度优化算法,分别对每个预优化算法形成的初始路径进行调度,测试改进算法的有效性,第三组是采用实际案例测试预优化算法的效果。

基于改进粒子群算法的木材板材下料方法

木材板材在家具行业应用广泛,以绿色环保、节约能源为目的的木材板材优化下料已经成为研究的热点。木材板材下料优化问题属于二维矩形下料问题,是一种具有高度计算复杂性的问题。本研究主要针对单规格木材板材进行矩形零件下料问题,在木材板材长和宽都大于零件长和宽的情况下,通过建立二维下料的数学模型,采用标准粒子群算法、变邻域搜索算法、粒子群混合变邻域搜索算法分别进行求解,并以某企业的下料实例进行分析计算。首先,利用标准粒子群算法求解单规格板材下料问题;其次,利用变邻域搜索算法求解单规格板材下料问题。在获得局部最优解的基础上改变其邻域结构再进行局部搜索,找到另一个局部最优解,如此不断迭代,直到满足算法的终止条件,获得全局最优解;最后,利用粒子群变邻域搜索混合算法求解单规格板材下料问题。针对粒子群算法局部搜索能力较差、容易过早收敛的问题和具有较好包容性的特点,将变邻域搜索的思想融入粒子群算法中,使结果更加趋向全局最优。结果表明:粒子群变邻域搜索混合算法相比粒子群算法和变邻域算法效率都有显著提升,能显著提高该木材板材的利用率,增加企业经济效益。

混合白鲸优化算法求解柔性作业车间调度问题

针对柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP),提出一种混合白鲸优化算法(hybrid beluga whale optimization,HBWO)对其求解,旨在最小最大化完工时间。采用既定策略改进标准白鲸优化算法(beluga whale optimization,BWO),加快其收敛速度;基于机器选择和工序排序问题设计双层编码方案,解决FJSP离散化问题;采用主动编码及种群初始化策略,提高求解质量;基于工序的开始和结束时间确定关键路径和关键块,注重各工序时间维度;引入贪心思想至基于关键路径的混合变邻域搜索策略中,加大勘测搜索空间及减少无效搜索;此外,引入遗传算子防止算法陷入局部最优;通过35个标准算例的仿真实验与分析,证明了算法在求解FJSP问题中具有有效性。

基于改进遗传算法的舾装件托盘多载具协同拣选方法

为提升舾装件托盘的拣选效率,建立拣选过程的数学模型,提出一种基于改进遗传算法(Improved Genetic Algorithm, IGA)的舾装件托盘多载具协同拣选方法。针对遗传算法(Genetic Algorithm, GA)流程与实际拣选过程的差异,改进GA的初始化过程和染色体交叉方式,并对变异过程进行更贴近实际生产的修改。针对GA难以得到全局最优解的问题,采用变邻域搜索(Variable Neighborhood Search, VNS)策略降低陷入局部最优解的可能性。采用实例计算验证该算法的有效性,可优化传统舾装件托盘拣选方法。

果蔬采后分级和预冷车辆协同调度模型与算法

新兴的移动式分级、预冷技术应用于果蔬田间采后处理,有助于降低采后损耗,也催生了采后“最先一公里”冷链物流环节协同运作优化问题。以采后分级、预冷环节为例,综合考虑果蔬最佳预冷时间、先分级后预冷的服务顺序等特有协同情景,构建了移动式分级预冷资源协同调度优化模型。与现有模型不同,本研究考虑延迟预冷对果蔬新鲜度的特殊影响,设计了延迟预冷成本函数,在保障产品质量的同时最小化服务运作成本。设计混合遗传算法对模型进行求解,该算法融合了遗传算法与邻域搜索算法,增强混合算法的局部和全局搜索能力。其中,结合问题的双需求特点及关键协同约束,设计了基于双序列的解的表达方式、基于最佳插入策略的交叉算子以及基于三阶段邻域搜索的变异操作,以提高算法的收敛速度与求解质量。通过与标准遗传算法和变邻域搜索算法对比,验证了本文算法在求解大规模算例时可以更快收敛到更高质量的解。基于陕西省洛川县水蜜桃产业的分级预冷数据证明了模型的合理性。本研究有助于把协同运作优化思想引入果蔬采后“最先一公里”冷链物流环节,为降低我国果蔬采后损耗提供创新性解决思路。

考虑站点换乘的地铁多车站接运公交线路优化

为了实现公交与地铁的有效接驳,提高公交系统接运效率,开展接运公交线路优化研究.考虑多个地铁站与公交站间客流的起点-终点(OD)需求与换乘特性,建立双层规划模型.上层模型的目标函数旨在使公交运营成本及乘客出行成本之和最小化,约束条件考虑线路的完整性、路径的合理性;下层模型为客流分配模型,以线路容量、站点换乘构建约束条件.引入精英保留策略,将邻域搜索算法与遗传算法组合,设计模型求解算法.案例分析结果表明,所设计算法的最小误差为1.6%,算法效率显著提升;与原公交线网相比,优化后公交载客量提升29%,人均出行成本降低13%.实验结果表明,所建模型基于系统最优原则,能够对多个地铁站周边的公交站进行统筹优化;优化方案在提升载客率、降低人均出行成本与提高公交系统接运效率方面优势明显.

利用强化学习的改进遗传算法求解柔性作业车间调度问题

针对传统遗传算法在解决柔性作业车间调度问题时易陷入局部最优解、参数不能智能调整、局部搜索能力差的问题,建立以最大完工时间最小为目标的柔性作业车间调度模型,并提出一种基于强化学习的改进遗传算法(reinforcement learning improved genetic algorithm,RLIGA)求解该模型。首先,在遗传算法迭代过程中,利用强化学习动态调整关键参数。其次,引入基于工序编码距离的离散莱维飞行机制,改进求解空间。最后,引入变邻域搜索机制,提升算法的局部开发能力。使用PyCharm运行Brandimarte算例,验证算法的求解性能,实验证明所提算法求解效率较高,跳出局部最优能力更强,求解结果更好。

有禁飞区的时间依赖型车辆与无人机协同配送路径优化

本文针对有禁飞区的时间依赖型车辆与无人机协同配送路径问题,综合考虑分时段禁飞的无人机禁飞区域、车辆行驶速度连续变化、车辆及无人机能耗等因素,以车辆派遣成本、车辆能耗成本、无人机能耗成本之和最小为目标建立优化模型.根据问题特征,设计遗传变邻域搜索算法对其进行求解.针对遗传算法易早熟、局部搜索能力较差等缺陷,将变邻域搜索算法与其结合以增强算法的局部搜索能力,引入自适应邻域搜索次数以增强对种群的搜索深度,采用精英保留策略不断改进最优解.通过多组算例验证了算法的有效性,并分析了配送模式、禁飞区数量、车辆行驶速度变化对配送方案的影响,结果表明禁飞区及车辆速度等因素在很大程度上影响物流配送成本.研究成果不仅丰富了车辆与无人机协同配送的场景,拓展了VRP问题的研究,也为物流企业制定配送方案提供了依据.

考虑设备预防性维护的开放车间调度问题

依据实际生产车间的运行情况,建立了带设备预防性维护的开放车间调度模型,并设计一种混合遗传禁忌搜索算法来求解该问题。根据问题的特点,设计了混合算法的遗传编码、解码、改进交叉和变异等操作,以及禁忌搜索算法的邻域结构,使算法在集中搜索与分散搜索中达到平衡。所提算法在开放车间调度Taillard基准实例和带预防性维护的开放车间调度案例中的应用验证了其高效性和有效性。

丘陵山地环形单轨运输系统静态调度优化方法

为了提高环形单轨运输系统完成静态任务的作业效率,该研究以丘陵山地为应用场景,针对任务点与运输车的匹配与调度需求问题,综合考虑最大程度满载的因素,建立了具有任务点“拼车”组合处理和运输车任务分配两个阶段的数学模型。提出基于相邻位置、任务量和随机序列不同优先级的3种启发式规则算法解决以运输车上货次数最少为目标的“拼车”组合问题,采用基于变邻域搜索的遗传算法解决以运输车堵塞次数最少为目标的运输车任务分配问题。通过模拟3种任务批量的运输情形,验证优化算法的性能,结果表明:基于任务量在3种启发式规则算法中求解速度最快,在80%的试验中获得的可行解最优,选择基于任务量和与之性能接近的基于随机序列的结果分别作为运输车任务分配问题的初始解,基于任务量更有利于第二阶段运输车任务分配问题的求解,得到的分配方案堵塞次数更少。基于变邻域搜索的遗传算法能显著提高标准遗传算法的求解质量,使堵塞次数降低了33.3%~100%,在大规模运输问题的求解中比变邻域搜索算法表现出更高的稳定性,最少堵塞次数出现的概率分别提高了10%和40%,有效性也优于整体匹配规则、随机重启爬山等其他类型的算法。该研究实现了对环形单轨运输系统静态调度的有效优化,所提出的算法有助于减少停车次数,节约工作时间,提高运输效率。

混合麻雀算法求解带准备时间的分布式柔性作业车间调度问题

分布式制造模式因多工厂/车间协同生产而使其制造环境存在多样性和多变性。研究了考虑零件加工前的动态准备时间的分布式柔性作业车间调度问题(Distributed Flexible Job Shop Scheduling Problem, DFJSP)。针对缸体零件加工阶段存在多工位零件装夹定位、拆卸和换刀等动态准备时间的实际生产情况,建立了以完工时间、碳排放和订单拖期为目标的DFJSP模型;提出了一种混合麻雀算法(Hybrid Sparrow Search Algorithm, HSSA)对上述模型进行求解。HSSA算法根据模型特点,采用了三层编码方式和多种群初始化策略,设计了一种三层变邻域搜索结构,引入了POX、PMX交叉算子和高斯变异算子来完成交叉、变异操作,同时设计了一种基于支配关系的精英选择策略。通过仿真及与其他算法的对比分析,验证了HSSA算法的优越性和可靠性。

基于混合遗传算法的城市固体废弃物运输路径优化研究

针对城市固体废弃物运输成本不确定的特点,文章在车辆路径问题的基础上对带时间窗的城市固体废弃物运输问题进行研究。考虑到遗传算法存在局部搜索能力不足的缺陷,在遗传算法的基础上结合变邻域搜索算法的思想提出了混合遗传算法。(1)采用三种邻域搜索算子用于改进遗传算法的变异算子;(2)采用模拟退火算法中的Metropolis判别法则来更新邻域搜索最优解;(3)采用自适应交叉变异概率和最优个体保留策略提高算法的运算效率。采用Solomen算例中的7个标准例题对算法性能进行测试,实验结果表明,混合遗传算法能够求得质量更高的解。最后通过算例来验证该模型的可行性,在满足时间窗和载重约束下缩短行驶距离。

考虑需求可拆分的共享单车调度优化研究

研究考虑需求可拆分的共享单车调度优化问题为可拆分单商品取送货TSP问题,考虑一辆调度车,允许调度车多次访问各站点,每次满足站点的部分需求,即允许对站点的需求进行拆分。首先,考虑到调度车容量限制,统筹安排调度车行驶路径和调度车在每个站点的取车量、送车量,使得企业的运营成本达到最优。其次,提出了一种改进的变邻域搜索算法求解上述问题,使算法在陷入局部最优解时改变邻域结构,扩大搜索范围,以此提升算法跳出局部最优解的能力,加快收敛速度。最后,用数值实验验证了算法的有效性。研究结论拓展了可拆分单商品取送货问题的相关理论,并为共享单车企业的实际运营提供决策支持。

基于改进多目标水母算法的低碳柔性作业车间调度方法

针对柔性作业车间调度问题中多个目标之间相互冲突、难以求解的问题,设计了一种基于Pareto和改进多目标水母搜索算法的柔性作业车间调度方法。首先,建立了以最小化最大完工时间、最小能耗以及最小机器总负荷为优化目标的车间调度模型;其次,使用了一种基于完工时间和机器负荷均匀分布的初始化方式,有效地提升了初始种群的质量;考虑到连续水母算法在求解离散问题时存在效率低等问题,设计了离散水母算法,提出了基于Pareto等级的被动运动方式,进一步提高了搜索效率,引入了学习的概念引导种群向Pareto前沿移动;最后,为了验证多目标改进水母算法在求解柔性作业车间调度的有效性,与NSGAII算法进行了仿真实验对比。实验结果表明:利用该算法求解MK06算例完工时间为76、机器负荷为424、能耗为565.8支配的NSGAII的结果,解的质量整体较高。研究结果表明:采用均匀分布初始化方式以及学习型引导的离散化水母算法,其初始种群分布均匀、收敛速度快、解的质量高,具有较强的寻优能力,能够有效地处理多目标柔性作业车间调度问题。

混合时间窗下多中心混合车队车辆路径优化

针对混合时间窗下多中心混合车队车辆路径优化问题,综合考虑多中心联合配送、客户混合时间窗、配送中心运力平衡和车辆装载量对油耗的影响,构建以车辆派遣成本、油耗成本、电动车能耗成本和时间窗惩罚成本之和最小化为目标的优化模型。设计遗传—大邻域混合算法求解模型,该算法采用聚类法生成初始解,基于运力平衡的返回策略设计交叉和变异算子,并引入变邻域搜索结构和大邻域搜索算法的移除与插入算子进行搜索优化。通过对比和分析多组算例验证了算法的有效性,并分析了运力平衡策略和混合时间窗对制定配送方案的影响。研究成果可丰富车辆路径问题的相关研究,为物流企业优化决策配送方案提供了理论依据。

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

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

基于遗传变邻域搜索算法的农机跨区调度优化研究

智慧农业的快速发展促使多区域互联农机的调度追求更高的实时性,为更合理配置农机资源,农机跨区作业已成为完成“三夏”机收任务的主要服务模式。基于小麦收获机跨区作业真实场景,研究了带时间窗的多库、多机型的农机跨区调度问题,同时考虑经济成本和环境成本,建立以最小调度成本为目标的跨区调度模型。根据问题特征,设计遗传变邻域搜索算法(Genetic algorithm variable neighborhood search,GAVNS),该方法通过交叉、随机扰动、自适应邻域选择等操作,使解的搜索更加高效和灵活。对我国黄淮海平原72个小麦生产区县的作业需求进行计算与分析:不同算法相比,本文设计的算法得到最优解的迭代次数更低、收敛速度更快,求得的目标函数值较遗传算法、变邻域搜索算法分别降低16.41%、11.15%;对比不同调度模式,开放路径模式更有利于提升跨区调度服务效率,较闭合路径模式,调度成本降低17.76%。

考虑机器故障的柔性作业车间动态调度

针对生产过程中不确定性机器故障使初始调度方案可执行性降低的问题,提出了一种考虑机器故障概率的柔性作业车间重调度方法。采用事件和基于故障概率的周期混合驱动策略,综合使用多种重调度方式,引入最大完工时间偏差、工序开始时间累积偏差、工序机器变动量作为评价指标,借助结合变邻域搜索的改进遗传算法对调度方案进行求解。通过对处理后的柔性作业车间案例仿真分析,结果表明,相比于单一重调度方式该方法最优重调度方案在性能评价指标上有显著提升,验证了所提出重调度方法应对不同情况下机器故障扰动的优越性。

基于超网络的集成工艺决策与调度问题研究

针对多工艺产品的加工路线决策与车间调度方案不能同步制定的问题,在制造车间数字化背景下,提出集成车间不同要素信息的特征—工序—机器—工人的超网络结构,建立基于超网络的加工路线决策与车间调度模型,设计一种集成工艺决策与车间调度的两阶段混合遗传算法求解模型。在工艺决策阶段,设计特征—工序双层矩阵编码染色体保持加工路线的多样性,并在遗传算法的执行过程中使用变邻域搜索方法增强算法的局部搜索能力;在车间调度阶段,采用NSGA-Ⅱ算法优化调度模型,将得到的调度方案多目标值返回至工艺决策阶段用于加工路线的适应度评价。最后通过仿真实验验证了该算法的可行性与有效性。