多舱共配绿色车辆路径问题的改进变邻域搜索算法

针对社区团购前置仓配送场景中“多中心、高时效、多品类、高排放”难题,本文提出多车场带时间窗的绿色多舱车车辆路径问题(MDMCG-VRPTW),构建混合整数线性规划模型,并设计改进的变邻域搜索算法(IVNS)实现求解.采用两阶段混合算法构造高质量初始解.提出均衡抖动策略以充分探索解空间,引入粒度机制以提升局部搜索阶段的寻优效率.标准算例测试结果验证了两阶段初始解构造算法和IVNS算法的有效性.仿真实验结果表明,模型与算法能够有效求解MDMCGVRPTW,且改进策略提高了算法的求解效率和全局搜索能力.最后,基于对配送策略和时效性的敏感性分析,为相关配送企业降本增效提供更多决策依据.

基于变邻域人工蜂群算法的航空不规则零件下料优化研究

针对航空不规则零件规格种类多样,毛坯数量庞大,原坯料利用率低等实际生产中的问题。为了解决上述问题,提出基于变邻域人工蜂群不规则零件下料优化算法及算法流程,构建双坐标系下料模型,设计交换策略、顺序策略及逆序策略进行变邻域搜索,采用SCO、DCO、HO、WO、AO解码方式进行图样解码。最后,将变邻域人工蜂群算法与原始人工蜂群算法进行仿真分析,仿真实验结果表明:变邻域人工蜂群算法能够有效可靠地提高原坯料利用率及排样效率。

求解最小双连通支配集问题的变邻域禁忌搜索算法

针对经典NP难优化问题——最小双连通支配集问题,提出了一种元启发式求解算法——变邻域禁忌搜索算法。算法将原优化问题的求解转换为一系列判定问题——k双连通支配集问题的求解,使用两种邻域结构更加有效地覆盖解空间,同时使用扰动及禁忌机制帮助算法跳出局部最优陷阱。通过与现有文献中的精确算法、启发式算法在国际文献公开的38个双连通图算例上的实验对比,结果表明变邻域禁忌搜索算法能够有效求解最小双连通支配集问题,可求得所有公开算例的最优解,并且在稠密图中计算效率明显优先于其他算法。

边缘匹配度算法与变邻域搜索结合的矩形件下料算法

研究了广泛存在于生产制造中的二维矩形件下料问题,提出一种边缘匹配度算法和变邻域搜索算法相结合的混合算法进行求解。首先,分析了一般最低水平线相关算法的缺陷,提出了一种边缘匹配度评价函数。下料时其可以对所有剩余的矩形件进行评价,从中选出与当前布局边缘重合最大的矩形件进行排放。其次,由于下料问题存在上位效应,提出一种与其相匹配的邻域结构,得到了一种适应下料问题的变邻域搜索算法,边缘匹配度算法通过与变邻域搜索算法结合来加强其搜索能力。最后,通过对已有文献的多个案例进行试验。实例证明提出的算法可以得到较好的排样结果,相较于其它算法提高了板材利用率1.16%~12.03%,具有较高的实用性。

基于变邻域模拟退火算法的储位分配研究

为提高“货到人”拣选系统的订单拣选效率,降低订单拣选过程中的成本,提升订单服务水平,研究基于变邻域模拟退火算法的储位分配问题。基于自动化无人仓库中AGV在服务过程中搬运整个货架的特点,以货架上商品之间关联度之和最大为目标,建立混合整数规划模型,设计求解模型的变邻域模拟退火算法,有机利用变邻域搜索与模拟退火算法两者的优点,利用计算机进行3种规模算例的实验。结果显示,所提算法相较于随机分配策略在3种规模算例中都可以使目标函数值提升60%左右,并且在时间上较为快速,证明与随机分配策略相比,所提算法具有很大优越性,可以较大提升订单拣选速度。

基于改进变邻域搜索算法的多批次协同任务规划

目的对多批次协同任务进行分析与建模,并研究任务规划的求解算法。方法以车载装备多批次协同执行任务为例,综合考虑时间协同、任务区域协同和补给区域协同约束,以暴露时间最短为目标函数建立模型,并提出一种改进变邻域搜索算法进行求解,该方法根据邻域的优化能力自动调整迭代时选择该邻域的概率。结果仿真结果表明,改进策略在不降低最优解质量的情况下,能够避免标准变邻域搜索算法后期易出现某些邻域长时间无法寻找到最优解的情况,有效提高了算法的效率。结论变邻域搜索算法可以解决多批次任务规划问题,改进后的算法减少了后期对优化能力不强的邻域的搜索次数,有效提升了算法效率。

学习型变邻域搜索算法求解运输-装配协同优化问题

针对运输-装配协同优化问题,建立其整数规划模型,提出一种融合分解策略的学习型变邻域搜索算法(learning variable neighborhood search with decomposition strategy,LVNS_DS)对其求解。为降低问题的求解难度,设计一种分解策略将原问题分解为路径规划问题和装配线平衡问题;应用LVNS算法对2个子问题进行求解;通过合并子问题解可得原问题的完整解。相比常规VNS算法,LVNS算法依据邻域动作概率值来转换邻域结构,依据邻域动作产生的贡献来动态地更新其概率值,LVNS算法能以较大的概率值选择适于当前搜索阶段的邻域动作,从而易于找到子问题的优质解。通过不同规模算例的仿真实验,验证了运输-装配协同优化的有效性和LVNS_DS算法的有效性。

硬时间窗VRP的混合变邻域禁忌搜索算法

为了寻求带硬时间窗的车辆路径优化问题的高质量近似解,针对现有数学模型对时间窗约束考虑不充分,建立了最小化车辆数和总行驶距离的双目标非线性优化模型,提出了一种混合变邻域禁忌搜索求解算法。一方面,采用改进的节约算法生成初始解,设计了3种删除算子和一种插入算子对初始解进行扰动优化,为后续禁忌搜索提供优良的初始解;另一方面,基于4种邻域构造算子进行禁忌迭代搜索,利用禁忌搜索的灵活存储结构、避免迂回搜索的禁忌准则和增强多样性搜索的特赦准则有效摆脱局部最优解,最终实现全局优化。在56个Solomon和18个Homberger基准算例上的实验结果表明,该算法的求解质量优于文献中两种同类型搜索算法,具有良好的收敛性和稳定性,且在42个基准实例上获得了比当前已知最好解更低的车辆总行驶距离。

基于变邻域人工蜂群算法的三维矩形箱体下料优化研究

相比一维、二维下料问题,三维空间下料优化问题存在零件规格种类多样、数量庞大、尺寸约束及工艺约束等多重因素限制,导致原材料利用率偏低的现象。为此,文中以三维矩形箱体为研究对象,建立了三维空间下料模型,基于变邻域人工蜂群三维矩形箱体下料算法及算法流程,设计了4种三维变邻域搜索策略:邻域交换、邻域顺序、邻域逆序及邻域正交,提出了5种三维解码方式:SCO,BCO,HO,WO和LO。试验结果表明:变邻域人工蜂群算法较人工蜂群算法在三维矩形箱体排样中有效提高了原坯料利用率及排样效率,排样方案更优、算法迭代时间更短、更加贴合生产实际,对解决制造业在三维空间下料效率与成本方面所面临的问题,具有很好的借鉴意义。

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

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

基于两阶段变邻域算法的载重关联低碳配送路径优化

为了降低物流配送过程中花费的综合成本,考虑车辆载重和车辆行驶距离对碳排放的影响,提出一种综合成本最小化的低碳配送车辆路径优化问题模型,并设计一种两阶段变邻域算法——TSVNS进行求解。算法的预优化阶段采用局部搜索策略,考虑车辆载重约束求解得到预配送路径,再优化阶段设计一种改进的变邻域搜索算法,对预配送路径再次进行优化,求解得到最优配送路径。最后通过对实际算例的计算分析,验证了模型和算法的有效性,计算结果显示,该算法能有效降低配送过程中的综合成本和碳排放,且相较于已有算法具有明显优势。

基于混合变邻域遗传算法的柔性车间调度研究

针对柔性作业车间调度的问题,以最大完工时间为目标建立数学模型,提出一种混合变邻域遗传算法。采用三种初始化方法保证初始解的质量,用遗传算法进行初步搜索,将搜索的结果通过迭代贪婪策略进一步搜索,以提高解的质量,再对关键路径进行邻域搜索,设计“跨机器工序搜索邻域”、“同机器工序搜索邻域”、“次优工序搜索邻域”三种邻域结构,加强局部搜索能力。引入迭代贪婪策略和改进的邻域结构可显著提高算法的稳定性与迭代速度。通过对国际通用的柔性作业车间调度基准算例进行测试,实验结果表明所提改进算法能够有效求解柔性作业车间调度问题。

取送货路径优化问题的候鸟群自适应变邻域搜索算法

具有时间、车容量和后进先出约束的多车辆取送货路径优化问题在现实中具有广泛的应用,针对现实问题中规模性和模型的复杂性使其在短时间内无法精确求解的问题,提出了候鸟群自适应变邻域搜索算法(MBO_AVNS)。以三种贪婪插入算法构建初始种群,确保种群的多样性和初始解的质量,对传统候鸟优化算法的邻域搜索算法进行改进,加强了算法的局部搜索能力。通过真实数据进行实验分析表明,与模拟退火算法(SA)和一般自适应变邻域搜索算法相比,MBO_AVNS算法在求解具有时间和后进先出约束的取送货路径问题上更具有优越性。

基于改进变邻域搜索的多隔室车辆路径优化算法

为了研究多隔室车辆路径优化问题,建立最小化配送距离数学模型,提出一种改进变邻域搜索算法进行求解。基于变邻域搜索算法框架,设计了多起点寻优机制,运用扫描法构造初始解,设计了Shaking过程与全局扰动过程进行邻域解空间探索,提出还原及再分配策略探寻解空间中不可行区域,结合贪婪算法和多种混合算子设计了Local Search过程的子路径内及子路径间搜索优化机制以展开局部搜索,应用最大迭代次数停止准则结束循环并保留最优解。通过改编算例的实验及对比分析表明,针对多隔室车辆路径优化问题特点设计的改进变邻域搜索算法能够在合适的时间内规划出更合理的配送路径,获得更稳定的高质量解,达到更明显的优化效果。

基于粒子群优化和变邻域搜索的混合调度算法

提出了用于解决作业车间调度问题的离散版粒子群算法。该算法采用基于工序的编码和新的位置更新策略,使具有连续本质的粒子群算法直接适用于调度问题。同时,针对粒子群算法容易陷入局部最优的缺陷,利用粒子群算法和变邻域搜索算法的互补性能,设计了粒子群-变邻域搜索算法、改进的粒子群算法、粒子群-变邻域搜索交替算法和粒子群-变邻域搜索协同算法4种混合调度算法。仿真结果表明,混合算法能够有效地、高质量地解决作业车间调度问题。

随机需求车辆路径问题及混合变邻域分散搜索算法求解

随机需求车辆路径问题(capacitated vehicle routing problem with stochastic demand,CVRPSD)是对带容量约束车辆路径问题(capacitated vehicle routing problem,CVRP)的扩展,需求不确定的特点使其较CVRP更复杂,对求解方法要求更高.基于先预优化后重调度思想,提出两阶段的混合变邻域分散搜索算法(variable neighborhood scatter search,VNSS)对该问题进行求解:预优化阶段构建随机机会约束规划模型,对客户点随机需求作机会约束确定型等价处理,生成最优预优化方案;重调度阶段采用新的点重优化策略进行线路调整,降低因失败点而产生的额外成本,减少对人工和车辆的占用.算例验证表明,随机机会约束模型和两阶段变邻域分散搜索算法在求解CVRPSD时较为有效,点重优化策略调整效果较佳.

变邻域搜索算法综述

变邻域搜索算法(Variable Neighborhood Search,VNS)作为一种新的元启发式算法,已初步成功地用于解决优化问题,尤其是对于大规模组合优化问题效果良好。对VNS的扩展研究层出不穷,并将其成功地应用到旅行商问题、车辆路径问题、调度、图着色等问题中。简述了经典的元启发式算法,并依次论述了优化问题,VNS算法起源,VNS算法原理,VNS算法分析,扩展的VNS分析,VNS在初始解构造、邻域结构构造、局部搜索和停止准则几个方面的改进方法,针对不同版本的VNS归纳了其在各种优化问题应用情况。基于对改进的VNS的分类,从算法自身研究角度和实际应用角度提出了未来研究方向。

改进变邻域搜索算法求解动态车辆路径问题

针对动态车辆路径问题DVRP(Dynamic Vehicle Routing Problem)的优化问题,提出一种改进算法。该算法在分析路径寻优问题的局部特性的基础上,利用变邻域搜索算法VNS(Variable Neighbourhood Search)对路径空间进行"局部探索",结合变异机制对路径空间进行"全局开采",最后根据近邻优先原则将动态路径片段安插到适宜的路径中。实验结果验证了算法的有效性。

同时配集货定位—路线问题的变邻域分散搜索算法

针对同时配集货的定位—路线问题,建立了三维指数混合整数规划模型,并设计了变邻域分散搜索求解算法,即在基本分散搜索算法的基础上保留参考集更新和组合策略的全局搜索能力。针对组合后的解可能是不可行解的问题,利用插入法将其改进为可行解,再运用变邻域搜索进行局部开发以提高可行解质量。为保证算法的多样性以进一步扩大搜索空间,初始种群采用两阶段混合多随机法构造。通过采用Lingo求解简单算例验证了模型的正确性,采用设计的变邻域分散搜索算法仿真已有算例并与其他算法比较,证明了该算法的有效性。

接运公交网络设计的多目标优化模型及遗传变邻域搜索求解算法

为了使接运公交网络更好地为轨道交通车站集散客流服务,将其作为研究对象,提出了接运公交网络的优化方法.考虑接运公交网络服务的需求量与接运公交供给密切相关、接运公交发车时刻与轨道交通车辆到站时刻构成有序衔接,以接运公交服务的乘客量最大化、接运乘客平均成本最小化、运营成本最小化为优化目标,构建了接运公交网络的多目标优化模型.为求解模型,设计了利用产生式方法获得Pareto解集的遗传-变邻域搜索算法.将设计的遗传-变邻域搜索算法与遗传算法、精确算法分别进行比较,通过算例验证了模型与算法的有效性.