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

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

改进的自适应大规模邻域搜索算法求解动态需求的混合车辆路径问题

为了给物流企业在车辆配送方案制定上提供决策支持,针对电动物流车与燃油物流车混合配送的模式,研究了带时间窗的动态需求车辆路径问题,建立了以配送总成本最小化为目标的两阶段整数规划模型。针对模型特点,设计了改进的自适应大规模邻域搜索(improved adaptive large neighborhood search,IALNS)算法,提出新的删除、修复算子及动态阶段加速策略,分别针对大规模的静态算例与动态算例进行算法性能测试。结果表明,与无改进策略的IALNS(IALNS-ND)相比,静态问题中在相同的求解时间内75%的算例(12个算例中9个)IALNS得到的最小值和平均值优于IALNS-ND,动态问题中95%(60个算例中57个算例)的算例可以得到成本和时间均优于IALNS-ND的解;与三种算法——自适应大规模邻域搜索算法(ALNS)、大规模邻域搜索算法(LNS)以及变邻域搜索算法(VNS)相比,静态问题中所有算例IALNS获得的总成本的最小值和平均值均优于三个对比算法,动态问题中58%(60个算例中35个算例)的算例IALNS能够以少于三个对比算法1.5倍甚至10倍的时间获得更优的解。同时随着问题动态度的提高,IALNS的速度更快,质量更好,证明了该算法在求解时效性要求高的动态需求车辆路径问题的优越性。

基于自适应大规模邻域搜索算法的两级车辆路径问题

两级车辆路径问题(2E-VRP)是在现代物流产业高速发展和运输网络的多极化背景下提出的,其中两级路径指的是从生产中心到中转站(一级),再从中转站到客户(二级),该问题的目标是使整个运输网络的路径最短,从而达到节约费用、节能减排的目的。对于这一问题,文章首先用经典节约算法构造了模型的初始解,然后通过自适应大规模邻域搜索算法对初始解进行改进,实验结果表明,该算法能够取得高质量的解,而且计算速度快,稳定性好。

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

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

多结构型任务驱动的上门服务调度优化模型与自适应大规模邻域搜索算法

研究一类特殊的上门服务调度问题,该问题具有一般上门服务调度问题的要求,即要求可能具备不同技能水平的服务人员从同一站点出发,按路径执行被分配的任务后返回站点.被分配的任务在已有研究中对应图内点,而现实中的上门服务任务还可能具备内部结构(称为多结构型的任务),因此,在这类问题中路径的生成过程无法由任务序列本身确定,需要考虑任务指派和含出入点选取的路径规划的协同优化.通过分析此类问题特征,建立以总拖期最小化为目标的混合整数规划模型.通过分析模型的解的层次性特点,提出基于自适应大规模邻域搜索框架的启发式算法.通过多种规模对比实验发现,所提出算法适用于大规模问题和即时性要求,即在小规模算例下平均求解结果与精确解接近;在中、大规模算例下平均求解结果相较于一般贪婪算法产生显著优化.因此,所提出模型和算法可为多结构型任务驱动的上门服务调度提供参考.

基于自适应大规模邻域搜索算法的多车辆与多无人机协同配送方法

针对物流配送需求大、“最后一公里”交付困难等问题,提出带有动态能耗约束的多车辆与多无人机协同配送问题,并以最小化配送时间为目标建立混合整数规划模型(MIP).为解决该问题,设计K-means聚类和最近邻协同的初始解生成算法,并提出基于问题领域知识的自适应大规模邻域搜索算法(adaptive large neighborhood search,ALNS).在不同规模算例上的实验结果表明,所提出的算法相比于模拟退火算法、变邻域搜索算法和遗传算法在求解质量和求解效率方面都具有一定的优势,求解质量分别平均提升23.8%、23.3%和5.7%,表明ALNS较对比算法能够更好地平衡全局搜索和局部搜索.此外.灵敏度分析实验表明,无人机载重能力和无人机续航能力是影响包裹配送时间的两个关键因素.

基于自适应变邻域搜索的大规模电动车辆路径优化

针对变邻域搜索后期出现的在某些邻域内长时间无法找到更优的可行解的情况,提出了一种基于邻域选择概率自适应的变邻域搜索算法。该算法能够自适应调整在某个邻域进行搜索的概率,进而提高优化效率。对城市配送中的大规模电动车辆路径问题进行了建模分析,根据客户的地理位置、时间窗等信息设计了高效的初始解生成算法。使用片段交换、2-opt、Relocation等邻域算子进行自适应变邻域搜索。最后使用不同规模的实际数据对算法进行仿真验证,相比于传统的变邻域搜索算法,本文算法能更有效地跳出局部最优解,降低物流成本。

大规模邻域搜索算法求解时变车辆调度问题

对时变网络车辆调度问题提出一种满足先入先出准则的时变处理方法,并建立相应的数学模型,提出一种基于大规模邻域搜索技术的智能优化算法进行求解,算法顶层采用动态规划算法搜索环状交换邻域以得到每辆车的最佳服务顾客集合;底层设计动态搜索算法用以安排每辆车的最佳服务路线.在此基础上提出顶层加入虚拟顾客和底层嵌入insert两类改进策略.通过实验仿真比较,验证了所提算法的有效性.

基于差分进化邻域自适应的大规模多目标算法

对于大规模决策变量给求解大规模多目标优化问题带来的难以收敛及解集分布不均匀问题,通过分析变量特征将其分类再分别优化是当前较为有效的求解方法,但存在变量分类不够准确、变量处理不够有针对性等不足。对此,提出一种基于差分进化邻域自适应策略的大规模多目标优化算法。首先,通过分析扰动解的支配关系将混合变量分为多样性变量和收敛性变量,使变量分类更为准确。其次,通过对收敛性变量主成分分析降噪,降低计算成本,并设计种群的交替进化策略及差分进化的邻域自适应更新操作以提升种群进化过程中的收敛性。实验结果表明,所提算法在收敛速度和解集的分布均匀性上表现出良好的性能。

多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法

针对多车场带时间窗车辆路径问题(MDVRPTW),提出一种改良自适应大邻域搜索算法(IALNS)。首先,在构造初始解阶段改进一种路径分割算法;其次,在优化阶段利用设计的移除和修复启发式算子相互竞争择优选取算子,为各算子引入评分机制,采用轮盘赌方式选取启发式算子;同时,将迭代周期分段,动态调整各周期内的算子权重信息,有效避免算法陷入局部最优;最后,采取模拟退火机制作为解的接受准则。在Cordeau规范算例上进行实验,确定IALNS的相关参数,将所提算法求解结果与该领域其他代表性研究成果对比。实验结果表明,所提算法与变邻域搜索(VNS)算法的求解误差不超过0.8%,在某些算例上甚至更优;与多相位改进的蛙跳算法相比,算法的平均耗时减少12.8%,所提算法在绝大多数算例上运行时间更短。因此,验证了所提算法是求解MDVRPTW的有效算法。

分块自适应加权改进大规模模糊聚类

为解决传统模糊C均值聚类(Fuzzy C-means,FCM)算法在处理大规模数据集时遇到的时间复杂和内存不足等瓶颈,提出基于大数据集抽样分块的多视角自适应模糊聚类算法,算法通过邻域正则约束提高传统FCM算法的抗噪性,通过低秩与熵加权约束提高多视角一致性,以提高算法对多样化数据聚类的适应性,最后通过Canopy算法初始聚类中心提取、数据抽样分块和自适应加权优化算法对大规模数据聚类的适应性。实验结果表明,算法在继承传统多视角FCM算法良好聚类性能基础上,减少了计算复杂度,提高了聚类准确率,适于大规模数据集聚类。

自适应变邻域混沌搜索微粒群算法

针对局部地形复杂、振荡强烈的函数优化精度难以提高的问题,提出一种自动调整邻域搜索范围和方向的自适应变邻域混沌搜索微粒群算法(AVNC-PSO)。优化初期首先由基本PSO算法进行粗调,当种群收敛于局部最优时,选择飞行停滞且聚集程度高的粒子向不同方向的邻域内进行混沌搜索,搜索方向和粒子偏移量根据粒子与收敛中心的距离和混沌变量的值共同确定。数值仿真表明,该算法能够使局部搜索更精确,有效改善基本PSO算法优化精度不高的弱点。

求解TSP问题的自适应邻域搜索法及其扩展

TSP问题是测试组合优化领域算法性能的经典平台。提出了一种求解TSP问题的自适应邻域搜索算法,该算法通过为每个城市设定邻域来降低TSP问题的复杂度,并结合满意度和活跃度来构建一种自适应邻域搜索算子,使得其在局部优化的速度和收敛性方面取得了良好的效果。最后在该算法中融入遗传算法思想,将局部优化的高效性和遗传算法的鲁棒性有机结合起来构建成一种综合性能更好的混合优化算法。对eil75、CHN144和TSPLIB中的部分实例的仿真结果表明该算法在寻优度、收敛速度和稳定性等方面都优于目前一些比较常用的算法。

切割路径优化问题的自适应大邻域搜索退火算法

针对定义为广义旅行商问题(GTSP)的激光切割工艺路径优化问题,提出了一种自适应大邻域搜索算法(ALNS)与改进模拟退火算法相结合的混合算法。该算法提出一种融合最近、最远和随机插入操作的统一插入操作和统一最坏删除操作,通过在算法中反复进行删除和插入操作来优化自适应大邻域搜索算法,再运用改进模拟退火算法接受最优解,求得满足工艺约束的最短切割路径。通过GTSP-Lib数据库中的算例和实际切割案例对算法进行验证。结果表明,提出的算法在准确性上与最优算法的误差只有0.31%,但计算速度提高了12%,证明了该算法在求解小规模切割路径问题上有很强的适用性。

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

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

大规模MIMO系统中全局LAS检测算法

在大规模多输入多输出(Multiple Input Multiple Output,MIMO)系统中,现有的非线性检测算法中似然上升搜索(Likelihood Ascend Search,LAS)算法的复杂度较低,但是算法容易陷入局部极值,导致算法性能较差。文中提出一种全局最优的模拟退火-似然上升搜索(Simulated Annealing-Likelihood Ascend Search,SA-LAS)算法,该算法引入模拟退火算法中的概率因素,以一定概率接收相对更差的解,从而改进算法的局限性。同时还利用加权-对称连续超松弛(Weighted Symmetric Successive Over Relaxation,WSSOR)迭代处理复杂的矩阵求逆运算,降低初始解的求解复杂度;另外,设置多个邻域候选集并行搜索加快搜索的速度;最后设置双阈值控制迭代终止时间,以此降低算法复杂度。理论分析了该算法的复杂度,并通过仿真对不同检测算法的误码率性能和收敛速度进行了研究,结果表明:在复杂度阶数不增加的情况下,文中提出的SA-LAS检测算法的误码率性能明显优于现有的LAS检测算法。

自适应大邻域搜索的人工蜂群算法求解带容量约束车辆路径问题

为解决带容量约束的车辆路径问题(CVRP)求解时收敛能力与探索能力不足、耗时长等问题,提出一种基于大邻域搜索的人工蜂群优化算法。设计了5个移除算子和2个插入算子,采用算子区别应用机制、仔细侦查蜂机制、更新策略宽松机制优化算法。所提算法能够快速搜索到可接受解,在实验数据集上能收敛到大部分已知最优解,并更新了4个已知最优精准解。实验结果表明,3种优化策略均能有效提升算法效率,算法具有较好的综合性能。

求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法

针对单一机制的自适应大邻域搜索算法存在早熟收敛、易陷入局部最优的问题,提出了一种混合自适应大邻域搜索算法来求解冷链物流时间依赖型车辆路径问题(TDVRP)。首先,根据连续型行驶时间依赖函数来刻画时变车速,采用综合油耗模型来评估实时燃油消耗量,并建立了以总成本最小化为目标的路径优化模型;然后,根据问题的NP-hard性质和时间依赖特性设计了多种破坏和修复解的大邻域搜索算子,并将破坏-修复大邻域搜索算子融入到人工蜂群(ABC)算法之中,以提高算法的全局搜索能力。仿真实验结果表明,与自适应可变邻域搜索精英蚁群(AVNS_EAC)算法、自适应大邻域搜索精英蚁群(ALNS_EAC)算法、自适应大邻域搜索精英遗传(ALNS_EG)算法和自适应大邻域搜索模拟退火(ALNS_SA)算法相比,所提出的自适应大邻域搜索人工蜂群(ALNS_ABC)算法在多组测试数据上的最优适应度值分别平均提高了46.3%、5.3%、36.8%和6%。可见所提算法计算性能更高、稳定性更强,能够为冷链物流企业兼顾经济效益和环境效益提供更为合理的决策依据。

融合分解和自适应邻域的多目标离散组合优化算法

为了高效获取现实中大规模多目标优化问题解决方案,实现收敛性、多样性和均匀性的平衡逐渐发展为多目标优化的重要目标之一。针对复杂多目标离散组合优化问题,提出了融合分解和自适应邻域的多目标离散组合优化算法(MOALNS)。该算法在问题分解的基础上为各子问题的寻优进程引入大邻域搜索策略与自适应调整机制,形成一套新型的收敛指导准则突破寻优阻力,进而使各子问题在搜索多维解空间的过程中达到全局搜索与局部搜索的平衡。同时,提出为各子问题配置独立算子积分库可有效地调整各子问题的寻优方向,解决由于目标权重不同而造成的求解方向偏差问题,以此实现更为高效、稳定的多目标优化进程。数值实验表明,提出的新型多目标离散组合优化算法在多组标准测试算例与真实案例中均展现出了在收敛性、多样性、均匀性和延展性等方面的良好性能,相较于其他经典多目标优化算法而言更具优势。

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

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