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

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

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

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

基于自适应大规模邻域搜索算法的多等级引航员排班问题

引航服务不仅是保障船舶和港口安全的必要手段,也直接影响船舶进出泊位的效率。本文聚焦引航服务日常运作管理中面临的引航员调度排班问题,考虑引航员等级、服务时间窗、航道宽度等现实因素,以服务延迟成本、引航员出工成本、引航员交通成本、单次服务成本和当日未服务惩罚成本的总加权成本最小为目标构建了一个混合整数规划模型。结合问题特征,本文选择采用自适应大邻域搜索算法对模型进行求解,并针对模型特点设计多种破坏算子和修复算子进一步提高算法的运行速度与精度。最后,本文通过一系列数值试验验证了算法的高效性和准确性,并通过参数进行敏感性分析给出相应的管理启示,为港口企业运营决策提供参考和建议,从而提高引航服务水平。

考虑载重成本与时间窗的集送货问题的自适应大邻域搜索算法

物流配送需求的快速增长使得集送货问题的应用越来越广泛。针对配送过程中货物载重影响运输成本的情况,研究考虑载重成本的有时间窗的集送货问题。构建该问题的最小化车辆数量和总运输成本的双目标混合整数规划模型,在该模型中,运输成本为车辆载重量与车辆行驶距离的函数。设计两阶段自适应大邻域搜索算法对其求解,通过设计基于模型特点的多种高效的破坏算子和修复算子,引入模拟退火接受准则避免陷入局部最优解来提高算法性能。测试不同规模及特点的标杆算例,结果表明,所提出的两阶段自适应大邻域搜索算法能够高效求解小规模、中等规模和大规模算例,并分析了货物载重以及不同运量系数对运输成本的影响,为物流企业的集送货车辆路径优化提供参考。

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

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

基于大邻域搜索算法的不正常航班恢复策略

航班由于恶劣的天气、机组人员和飞机维修等原因导致延误或取消时,如果不能妥善处理,将会影响到旅客旅行,并可能损害航空公司的盈亏绩效和声誉,对此,航空公司需要制定应急计划以应对航班故障、维持竞争力和满足旅客需求。文章针对不正常航班的恢复问题建立了最小成本的数学模型,采用大规模邻域搜索的启发式算法求解,并针对国内某航空公司的航班数据进行仿真实验。实验结果表明,采用启发式算法对不正常航班进行一系列的恢复之后不仅可以降低恢复成本,还可以减少对于旅客出行带来的各种不便问题。

变邻域搜索算法综述

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

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

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

求解单行布局问题的一种变邻域搜索算法

设施布局问题对于企业内部的物流合理化起着重要作用,单行布局问题作为设施布局问题的一个典型特例,属NP-hard问题,常规方法难以精确求解。针对单行布局问题的复杂性,提出了一种改进的变邻域搜索算法进行求解。首先构建单行布局问题的数学模型,然后分析模型并构造一种有效的初始解;针对问题特征,设计了4种邻域结构,该邻域结构采用了从简单到复杂的推进搜索机制;改进了局部搜索算法并对邻域结构进行搜索;最后进行了实例验证,并与多种经典算法进行了对比,结果表明,所提变邻域搜索算法可在短时间内得到单行布局问题高质量的近优解。

多对多板坯倒垛问题的一种邻域搜索算法

为解决热轧生产计划中出现的板坯倒垛问题,建立了基于轧制位置与库内板坯多对多对应关系的问题模型,提出了一种新的邻域搜索算法。该算法考虑到轧制计划中的板坯规格组在库内垛位中连续堆放的特点,引入了Sequence邻域概念,使算法能够更好地利用问题的特征,并通过两阶段的寻优替换对问题进行求解。实验结果表明了所提模型和算法的可行性和有效性。

基于变邻域搜索算法的物流配送系统集成优化研究

本文针对物流配送系统集成优化问题,考虑取货和送货两种业务的配送情形下仓库和车辆的容量上限约束,构建包括仓库的开放成本、配送成本以及容量溢出成本的非线性混合整数优化模型,设计变邻域搜索启发式算法对模型进行求解。算法通过泰森多边形确定位置上的初始订单分配,再通过扫描半径及消费者数据结构标识实现邻域搜索,改进算法对解决方案进行迭代更新,完成优化求解。最后通过对辽宁宅急送取/送一体化物流配送案例进行数值分析,验证算法可行性和有效性。

解决无等待流水线调度问题的变邻域搜索算法

提出了解决无等待流水线调度问题的变邻域搜索调度算法。采用基于自然数编码的工件序列表达问题的解,采用多重Insert移动邻域和多重Swap移动邻域作为变邻域搜索的两种邻域结构。多重移动有利于算法向包含较优解的区域搜索,因而有较高的求解质量和效率。仿真实验证明了变邻域搜索算法的有效性。

基于自适应大规模邻域搜索算法的带时间窗的车辆路径问题

引入自适应大规模邻域搜索算法进行带时间窗的车辆路径问题的求解,通过移除和插入规则,分别在客户层级和路线层级上,不断地摧毁和重建解决方案,并通过局部优化策略来提高解的质量,最终得到最优的解决方案。结果表明,相较于传统的启发式算法,该算法求解此类问题的速度更快、结果更好。

用进化变邻域搜索算法求解闭合供应链选址问题

针对逆向物流依赖于物流网络的合理规划与设计,提出选址问题,通过分析闭合供应链规划设计中的选址定位,建立了相应的数学模型。模型中正向物流和逆向物流共享运输网络,把需求量作为随机变量处理,以供应链的总运营成本作为优化目标,为解决闭合供应链选址这个NP难题,提出了一种基于进化策略的变邻域搜索算法。通过设计基于多个算例的仿真试验表明:所建立数学模型和所提出算法是有效的。

自适应大邻域搜索算法在无人机物流路径规划问题中的应用

近年来无人机在物流运输领域发展十分迅速,这其中一个重要原因是无人机可以应对各种复杂的交通环境如城市的交通拥堵和乡村偏远地区的较差路况.而路径规划则是其在实际应用过程当中的一个重要环节,本文针对于此设计了一种自适应大邻域搜索算法来解决该问题.该算法通过引入自适应的机制来对传统的邻域搜索进行改善,使其能具有找到更好的解的潜力.在一些经典数据集上的仿真实验显示,本文提出的算法具有较强的鲁棒性和稳定性.另外通过该算法和其他元启发式算法的对比实验验证了本算法能够有效地减少使用无人机进行物流配送的费用.

求解拆卸线平衡问题的一种变邻域搜索算法

针对拆卸线平衡问题特点,建立以最小化工作站数、平滑指数、危害指数和需求指数为优化目标的多目标数学模型,进而提出一种改进的变邻域搜索算法求解该问题。所提算法采用了一种启发式方法产生初始解,并构造了3种邻域结构,扩大算法搜索范围。采用初始解集进行局部搜索,搜索过程使用一步改进策略,并引入禁忌表方法,提高算法全局寻优能力。通过对大量不同规模测试问题进行算法实验,并与现有方法对比,结果表明,所提变邻域搜索算法在求解效率与求解质量上具有优越性。

开放式带时间窗车辆路径问题及变邻域搜索算法

针对配送服务中开放式带时间窗车辆路径问题,构建了最小化车辆行驶成本的集分割模型,并提出变邻域搜索算法进行求解。该算法包括抖动和邻域搜索两个阶段,其中,抖动阶段通过当前解与种群历史最优、与个体历史最优之间的路径重连来实现,邻域搜索阶段通过同一条路径内以及不同路径间的交换、插入、2-opt三个操作算子来实现。通过与已有文献进行对比,结果表明该算法在求解开放式带时间窗车辆路径问题时,能得到更高质量的解,而且算法的收敛性和稳定性均较好。由此验证了该算法的可行性和有效性。

改进的引导式邻域搜索算法求解周期性车辆路径问题

在引导式邻域搜索算法静态惩罚策略的基础上,提出动态惩罚策略,设计改进的引导式邻域搜索算法,将其用于求解周期性车辆路径问题,采用标准算例进行数据实验,对动态与静态的惩罚策略进行对比.结果表明,采用改进的引导式邻域搜索算法求解周期性车辆路径问题可行有效.

求解UCARPP问题的变邻域搜索算法

针对无向网络中带有收益值有容限的弧路径问题,提出一种变邻域搜索算法。生成需求边的有序列,以相同概率初始化每条边的方向,采用分割算法构造初始解,运用6种邻域结构进行广域搜索,使用局部搜索算法改进解,利用旋轮法选择邻域结构。实验结果表明,该算法能提高效率,避免早期陷入局部最优,稳定性较好。

求解考虑顺序相关调整时间的双边装配线平衡问题的变邻域搜索算法

为有效解决带有顺序相关调整时间的双边装配线平衡问题,提出了一种简单高效的变邻域搜索算法。该算法通过将优先关系约束融入到交换、插入、交叉、变异等算子中,分别得到4个不同的邻域结构来保证搜索过程中解的可行性,避免过多重复邻域解的生成。4个邻域结构的搜索空间依次变大,以增强算法搜索能力。同时,结合装配线的特点,提出基于作业序列的编码和解码方式,在解码过程中,优先选择空闲时间较多的边,引入启发式目标加快算法收敛。分配结束后,对装配线末端的工作站组进行局部调整。通过将该算法先后用于求解无/有顺序相关调整时间的双边装配线平衡第一类问题,并与已有的算法进行对比,验证了所提的变邻域搜索算法的优越性和有效性。