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

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

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

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

一种基于图神经网络的改进邻域搜索算法

近年来图神经网络与深度强化学习的发展为组合优化问题的求解提供了新的方法。当前此类方法大多未考虑到算法参数学习问题,为解决该问题,基于图注意力网络设计了一种智能优化模型。该模型对大量问题数据进行学习,自动构建邻域搜索算子与序列破坏终止符,并使用强化学习训练模型参数。在标准算例集上测试模型并进行三组不同实验。实验结果表明,该模型学习出的邻域搜索算子具备较强的寻优能力和收敛性,同时显著降低了训练占用显存。该模型能够在较短时间内求解包含数百节点的CVRP问题,并具有一定的扩展潜力。

基于深度强化学习和大邻域搜索的矿山巡检机器人路径规划算法

当前大多数矿山巡检机器人采用激光雷达作为矿山环境探测方法,该方法对于一些小目标物体和反照率小的物体检测不明显,容易造成误检或漏检,从而引发矿山安全事故。为了提高矿山巡检机器人的识别精度,将基于强化学习结合大邻域搜索的路径规划方法引入矿山巡检机器人路径规划工作中,提高矿山巡检机器人对场景的感知能力。首先,提出了基于LSTM的时序性路径规划模型,能够从机器人的RGB相机中提取图像特征,通过深度学习方式进行场景感知。其次,将激光雷达设备采集的信息进行处理,使用大邻域搜索算法找到空间中的多个最优路径,用于后续场景导航。最终通过深度强化学习和大邻域搜索方法实现矿山巡检机器人精准导航,选择最佳的机器人巡检路径。为了验证所提算法性能,在二维和三维空间中进行了场景搭建、导航模拟、模型训练和测试。结果表明:该方法在仿真环境和真实场景中具有较好的路径规划能力。

自适应大邻域搜索求解着色旅行商问题

着色旅行商问题(Colored Traveling Salesman Problem,CTSP)来源于一类多机器人加工实践应用,在现实生活中有着广泛的应用场景。在CTSP中,每个旅行商各自分配一种特定的颜色,每个城市节点携带一个或者多个旅行商的颜色值,这些城市节点只能被带有相同颜色的旅行商访问。针对CTSP这个NP难问题,本文提出了一种高效的自适应大邻域搜索算法来求解CTSP。该算法包括四个重要的组成部分:一个随机贪心的初始解构造方法、四个专门的破坏操作和修复操作、一个高效的局部搜索程序和一个自适应破坏和修复操作选择机制。在文献中三组标准算例集上的实验结果表明,本文提出的自适应大邻域搜索算法能够高效地求解CTSP问题。

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

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

基于最优邻域搜索粒子群的低轨卫星通信任务规划方法

针对低轨卫星通信中的任务规划问题,提出了一种基于最优邻域搜索粒子群优化(Particle Swarm Optimization,PSO)群算法的任务规划方法。引入最优近邻搜索,通过最优粒子间的差分值来促进局部搜索,设计了惯性权值、社会和自我学习因子的优化方式,最终能够高效求解低轨卫星通信星座中多转发器与多任务的组合优化问题,用以应对低轨卫星过境时间限制和链路切换导致的时间段离散问题,并使得算法前期具有更强探索全局最优和后期快速收敛的能力。实验验证结果表明,该方法能够在低轨卫星中的约束条件下,有效提高卫星平均资源占用率(Average Occupancy Percentage,AOP)的同时减少算法收敛的迭代次数,显著降低运行时间开销。

基于遗传-变邻域搜索算法的堆垛机作业调度优化

基于缩短自动化立体仓库中堆垛机完成货物出入任务时间的目的,建立了堆垛机作业调度的作业时间模型,通过修补机制、校正机制和遗传-变邻域搜索算法的优化方法,使得在优化的过程中,确保出入库任务序列的长度相等,并能够复用同一批作业任务中因出库作业产生的空货位。12组作业任务的仿真实验结果表明,相较于变邻域搜索算法,遗传-变邻域搜索算法的收敛速度更快,其中3组作业任务解的质量更高,总耗时和相对耗时的优化率分别为11.57%~21.56%和35.85%~68.89%,且复用空货位可以缩短堆垛机的作业时间。

基于最优邻域搜索改进模拟退火的多雷达优化布站

针对多雷达组网探测系统,首先建立以空域覆盖率为优化目标、以多雷达位置为优化变量的数学模型,将多雷达布站建模为一个离散优化问题,从而筹划形成最优的多雷达部署方案.其次提出一种基于最优邻域搜索的改进模拟退火算法,通过在历史全局最优解的邻域范围内搜索产生新解来提升算法收敛速度;为确保算法的有效性,利用多项复杂性能测试函数对改进算法进行全面的性能分析.最后,在典型的仿真场景中,设定6部雷达、2个高度层的环境条件,对提出的算法进行验证.仿真结果表明,基于最优邻域搜索的改进模拟退火算法在收敛速度上表现优异,且以此为基础得到的多雷达布站方案能够满足任务需求,确保空域覆盖率的最大化.

基于动态五邻域搜索的改进Astar算法路径规划研究

针对传统Astar算法在复杂场景下的路径规划任务中存在路径搜索效率低、路径转折次数多等问题,本文提出一种基于动态五邻域搜索的改进Astar算法。通过改进算法的启发函数,将曼哈顿距离与欧式距离融合得到的距离度量代替传统Astar算法的单一距离度量,引入动态加权机制,并将传统的固定八邻域搜索策略改进为动态五邻域搜索策略。通过剔除最终路径的冗余节点并进行贝塞尔曲线平滑处理,使最终路径更平滑。试验表明,与传统Astar算法相比,采用本文算法的路径搜索时间减少了约69%,路径拓展节点数减少了约66.35%,路径包括节点数减少了约38.8%,路径寻优能力较好。

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

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

分阶段改进大邻域搜索算法求解取送货车辆路径问题

基于带时间窗的取送货路径优化问题的现实需求和大邻域搜索算法的研究发展趋势,依据实际情况构建带时间窗的末端混合取送货路径优化模型。根据模型特性提出一种分阶段求解算法进行求解。在基于随机订单序列的重新构建阶段,引入交叉、翻转、扰动算子以提高全局搜索能力。并在解码路径重新构建阶段,设计了子路径分解算子和交叉算子,破除了局部最优的情况。通过基准实例测试及实验对比分析,证明了该算法能够快速找到有效解,所设计的算子不仅能够跳出局部最优,还能加快收敛速度,进一步证实了所提算法在解决该问题模型方面的有效性和可行性。

一种邻域搜索的人工蜂群算法

提出采用邻域搜索机制来改进人工蜂群算法的解搜索方程,从当前食物源的环形邻域拓扑结构中选择较优的邻居食物源进行开采,平衡算法的勘探与开采能力。此外,为保存侦察蜂的搜索经验,提出采用一般反向学习策略生成被放弃食物源的反向解,提高算法的搜索效率。在20个典型的benchmark函数上验证算法的性能,并与6种知名的改进算法进行对比。实验结果表明:本文算法在收敛速度和解的精度上均有较大优势。

作业车间调度的空闲时间邻域搜索遗传算法

针对最小化最大完工时间的作业车间调度优化问题,提出一种基于空闲时间的邻域搜索遗传算法。通过对不同解码方式的分析,设计了一种基于空闲时间的邻域结构及其邻域搜索方法;分析了同一机器上相邻两工序间的空闲时间,给出最大限度查找关键工序相关机器空闲时间的方法;查找关键工序前后的机器空闲时间,在保证可行解的条件下,移动关键工序到空闲时间位置实现邻域搜索;给出同一台机器上任意两个工序位置相对移动时保证可行解的工序移动条件及证明。将基于机器空闲时间的邻域搜索方法融入遗传算法,采用典型算例进行测试,与文献中不同算法的求解结果进行比较,验证了所提方法的有效性。

实时无功优化调度中的邻域搜索改进遗传算法

为了避免遗传算法的早熟收敛及改善其收敛性能,提出了电力系统最优无功调度和电压控制的一种改进遗传算法。算法中采用了分组整数编码技术和锦标赛选择机制;结合十进制整数编码的特点,提出了邻近变异的操作算子,避免了二进制编码中的海明悬崖(Hammingcliffs);在遗传迭代结束后再引入邻域搜索技术,以极短的时间完成搜索。将此算法应用在海南电网的实时无功优化调度中,结果表明该算法能迅速获得全局优化解,具有很好的全局收敛性能,能满足电力系统无功优化实时调度的要求。

技术站广义动态配流问题的局部邻域搜索算法

为了实现技术站阶段计划的计算机编制,研究了静态配流和列车解编方案调整的协同优化.在综合考虑优先排空和优先发送较近编组去向车流的编组要求、欠轴列车停运要求,以及到发列车时间和车流接续关系的基础上,以静态配流为主线,通过调整欠轴列车编组顺序以及与其相关到达列车的解体顺序构造邻域,设计了局部邻域搜索算法.该算法的主要思路是:每次搜索只考虑最早出发的欠轴列车;构造其邻域时保证不产生新的欠轴列车;通过邻域搜索后,该列欠轴列车如不能满轴就停运.算例表明,与既有方法相比,该算法能求出编组列车数、编组车辆数和中时的更好解.

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

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

基于功率矩和邻域搜索的有源配电网两层重构算法

针对传统的含有分布式电源的配电网重构算法所存在的寻优速度和最终解的质量难以兼顾的问题,提出一种基于功率矩和邻域搜索的配电网两层重构算法。利用功率矩算法对各环路进行第一层重构优化,确定开断支路集,在此基础上采用具有方向的邻域搜索算法进行第二层重构。通过对当前解点的邻域搜索获取更优的解点位置,直至目标函数值不再下降,从而得到最终的重构方案。含有分布式电源的IEEE 33和IEEE 69节点典型测试系统的仿真结果验证了所提算法的有效性。

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

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

基于工序编码和邻域搜索策略的遗传算法优化作业车间调度

针对作业车间调度优化问题,研究对其进行求解的遗传算法的种群初始方法和邻域搜索机制。为提高初始种群的质量,采用主动调度、无延迟调度与启发式规则相结合的启发式方法初始群体;基于关键路径构造邻域结构,将关键工序的邻域搜索移动与基于工序的编码方式相结合,避免不可行解的产生以及染色体的检测修复等工作;对工序块的块首、块内和块尾工序分别定义了不同的邻域移动操作。基于主动解码得到的甘特图,根据工序的开工时间,正向标准化染色体,使染色体中的工序位置顺序与机器上的工序实际加工顺序一致。为扩大工序的邻域移动范围,对甘特图进行右移处理,根据工序的完工时间,反向标准化染色体。对正向和反向得到的两个标准化染色体进行邻域搜索。采用基准算例进行测试,验证了所提算法的有效性。