双机流水车间外包与调度联合优化问题的混合变邻域搜索算法

针对最小化内部完工期与总外包费用的双机流水车间外包与调度联合优化问题,开发了一种混合变邻域搜索算法。在该算法中,采用工件剔除型启发式方法产生初始联合决策解;基于3种新型邻域结构提出了最佳改进式局部搜索规程;引入概率式准则来决定下轮迭代的目标搜索邻域。通过算法校准实验分析,探索出合适的邻域变更次序和温度参数的计算方式。通过与CPLEX软件、隐枚举测试程序对比显示,对于工件数不超过30的算例,校准后所提算法求得最优解的耗用时间更少。通过与遗传算法、模拟退火算法、和声搜索3种对比算法在工件数不少于100的算例上进行对比发现,所提算法经校准后,在求解质量和解的鲁棒性上均具有显著优势。

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

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

基于ALNS-TS算法的半灵活型需求响应公交调度问题

半灵活型需求响应公交模式往往拥有1个基准线路方向与1批确定访问的固定站点,服务车辆可以根据预约请求灵活响应候选的可变站点为其提供服务,当可变站点无请求时则不服务.基于低客流区域内需求响应公交服务所面临载客率低、运营成本高等问题,完善该模式的发车条件,设计差异化票价策略和未预约乘客服务判断的半灵活型需求响应公交服务系统,并建立车辆路径优化模型.为提高算法的搜索空间范围和局部搜索强度,设计了混合自适应大邻域禁忌搜索算法进行模型求解.以中国广州市黄埔区公交站点网络作为案例分析,结果表明,在新策略模式下,去除和未去除未预约乘客的半灵活型需求响应公交的票价收入较传统模式分别提高3.0%和15.5%,响应未预约乘客服务模式的服务人数可以提高7.5%;混合自适应大邻域搜索算法在求解速度和求解质量上均有较好表现,与混合模拟退火算法和遗传算法相比,计算时间分别节约76.9%和97.0%.

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

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

不确定箱重下内河集装箱班轮航线配载决策

与集装箱海运相比内河集装箱班轮运输具有其独特性,同时对于内贸箱而言,货主订舱时箱重信息的不确定性导致其航线配载决策变得更加复杂.本文考虑不确定箱重影响,以最小化航线班轮堆栈占用数量为目标,构建内河集装箱班轮航线配载决策的随机规划模型.为实现求解,基于随机规划理论,采用机会约束描述随机约束,将随机规划模型转化为随机机会约束规划模型,并设计混合邻域搜索算法求解.算法由蒙特卡罗随机模拟、神经元网络训练及邻域搜索启发式3个部分组成.算例研究表明,混合邻域搜索算法的鲁棒性较好,可实现配载计划对不确定因素的有效吸收.

带时间窗偏好的同时配集货且需求可拆分车辆路径问题

针对带时间窗偏好的同时配集货且需求可拆分车辆路径问题,最小化派遣成本、理货成本、时间窗惩罚成本以及油耗成本之和,建立数学模型。设计混合遗传变邻域搜索算法求解问题,在算法中引入时空距离的理念,首先用最近邻插入法和Logistic映射方程生成初始种群;然后利用变邻域搜索算法的深度搜索能力优化算法;提出自适应搜索策略,平衡种群进化所需的广度和深度;设计拆分准则,为各客户设置不同的拆分服务量;提出确定车辆最优出发时间的时差推移法,减少车辆在客户处的等待时间;最后通过多组算例验证本文模型和算法的有效性。

时变温度下考虑装载策略的多温共配优化研究

为了解决考虑外界温度变化、时间窗约束、装载策略的医药冷链多温共配车辆路径问题,建立了时变温度下考虑二维装载约束和多温层的VRPTW模型。考虑时变温度对热量损失的影响,确定制冷成本的度量函数;对于多温层共配,将有多种温层需求的客户点看作多个距离为零的单种温层需求的客户点集合;为提高装卸效率减少热量损失,改进左下角填充算法中装箱位置点的确定方法,混合遗传算法与大邻域搜索算法,根据模型特征在遗传算法中增加移出和重插入操作,设计改进左下角填充-遗传大邻域搜索算法对模型进行求解。最后结合算例,验证该模型和方法的有效性、正确性。