Self-adaptive large neighborhood search algorithm for parallel machine scheduling problems

A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.

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

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

基于ALNS-TS的大规模维修任务调度优化快速求解算法

大规模维修任务的调度优化在实际生产过程中具有广泛的应用,例如煤层气井维修任务调度优化、修井作业调度和压裂作业调度等。该问题规模庞大且求解困难,是实时调度优化的难点和挑战。合理的大规模维修任务调度对于保障油气田平稳生产和降低成本具有重要意义。为了有效解决这一难题,提出了基于ALNS-TS的优化求解算法,并通过不同规模的案例验证了算法的有效性。实验结果显示,对于代表性的10、50和100个维修任务的案例,求解时间分别为0.03、8.33和74.32 s,都能在分钟级时间内给出合理的调度方案。随着问题规模增加,基于ALNS-TS的算法比传统算法更高效,并能找到目标函数值更低的更优解。

基于ALNS算法的机场客舱清洁人员调度研究

我国机场目前主要采用人工方式调度客舱清洁人员,效率低下,时常发生任务拖期现象。针对客舱清洁人员日常调度问题,考虑客舱清洁任务的服务时间窗、多需求同时服务等约束,以最小化总运营成本为目标包含延误成本和资源转移成本,建立混合整数规划模型。设计了一种结合贪婪算法生成初始解的自适应大规模领域搜索算法,采用多种移除算法和修复算法进行邻域搜索,并利用时间快速更新机制加速求解,用模拟退火算法接受邻域解。数值实验结果与Gurobi优化求解结果比较,表明本文算法在所有实验算例中大部分都优于或等于Gurobi求解结果,并都能在较短的时间内找到较为满意的可行解,从而验证了本文算法的求解质量和求解效率。

基于电子商务竞标结构的分布式作战资源调度

针对现代战争作战任务规划问题,提出一种基于电子商务多轮竞标结构的作战资源调度方法,以异步、分散的方式让多个供应商协调来自多个消费者的任务资源请求。每个任务关联一个时间窗口,有些任务需要不同类的多个资源同步服务。招标由消费者发起,供应商对各资源请求发起投标,消费者根据投标结果中任务的3种状态,采取不同策略,并向供应商发送中标信息以执行任务或启动下一轮竞标。建立供应商和消费者调度问题数学模型,针对供应商资源调度非确定性多项式(nondeterministic polynomial,NP)完全问题特点,提出基于改进节约算法和自适应大邻域搜索算法的两阶段启发式求解方法;消费者模型使用混合整数线性规划来选择成本最低的投标组合,以满足任务需求。算例分析验证了所提方法的有效性。

一种时延能耗感知的在轨边缘计算任务卸载调度方法

全球智能设备的迅速增长引发了对计算资源下沉至边缘的巨大需求,催生了边缘计算范式的出现。同时,计算资源稀缺的偏远地区用户对算力的需求又推动了在轨边缘计算(Orbit Edge Computing,OEC)概念的提出和发展。在OEC场景下,偏远地区用户可以通过星地和星间通信链路将计算任务卸载至部署在低轨卫星上的边缘服务器,以此突破地面计算通信基础设施的限制,为偏远地区的用户提供低时延和高可靠的服务。然而,OEC场景中卫星算力受有限载荷和太阳能转化效率约束,同时还存在低轨卫星绕地导致的高度动态的星地连接造成的可用时隙有限的限制,面临着计算资源稀缺和可用通信时间有限所带来的挑战。因此,需要高质高效的任务卸载决策算法来保证OEC系统的高效运行。然而,目前在OEC场景下任务卸载方法大多在处理任务时无法兼顾计算任务卸载时延与能耗,此外传统方法还缺少对任务多样性的考量。针对上述问题,提出了一种基于自适应大邻域搜索的在轨边缘计算任务卸载方法OEC-ALNS,该方法以任务类型加权的任务处理成本为优化目标,并针对性地提出了基于最小化时延的破坏算子和修复算子来进一步提升搜索效率和卸载调度质量。基于Walker Delta低轨卫星星座和真实计算任务数据的实验结果表明,与传统的OEC-TA(OEC Task Allocation)方法相比,提出的OEC-ALNS方法在多个任务集异构的OEC场景中最多能够减少42.22%的加权任务处理成本和降低42.46%的平均时延。

改进天鹰算法求解时间依赖型车辆路径问题

针对速度时变的时间依赖型车辆路径问题,分析时间依赖型路网的行程时间计算方法,提出了一种改进天鹰优化(improved Aquila optimizer,IAO)算法。设计了一种天鹰位置-顾客序列(Aquila-customer,A-C)编解码方式,结合天鹰狩猎的拓展勘探、缩小勘探范围、扩大开发范围以及缩小开发范围四种搜捕猎物的方式,重新定义其智能寻优行为,引入自适应大规模邻域搜索策略,设计多种邻域破坏算子与修复算子,并在算法中加入劣解接受准则,提出循环启发式扰动机制与精英解扰动机制两种停滞扰动策略。Solomon基准算例对比实验以及基于Figliozzi测试算例与遗传算法、粒子群算法、蚁群算法的仿真对比实验均验证了IAO算法的优化性能,同时实际案例的实验结果充分证明了IAO算法在收敛速度与求解质量上的优越性,表明其具备求解时间依赖型车辆路径问题的应用价值。

多车程多时间窗车辆路径问题研究

针对末端物流中配送车辆多趟次运输、客户对配送服务时间的多样化需求,研究多车程多时间窗车辆路径问题。构造该问题的最小化车辆数量和总运输成本的双目标混合整数规划模型,设计改进的自适应大邻域搜索算法对其求解;构建了基于路径、车程及客户点3个层级上的多种高效的破坏算子和修复算子来扩大解的搜索空间;使用自适应策略选择高效的搜索算子,以及引入模拟退火新解接受准则避免陷入局部最优解来提高搜索效率。通过多种规模算例实验结果分析,验证了改进的自适应大邻域搜索算法的优越性,并分析了考虑多车程的模型对总运输成本的影响。

基于混合启发式算法的快递末端选址路径优化研究

传统快递末端配送模式存在快递网点建设冗余、派送路径重叠等问题,而共同配送模式可有效解决此类问题,因此对共同配送模式下同时收派件且收件需求为不确定情形的快递末端网点选址路径问题进行研究。首先,建立了两阶段数学优化模型,引入随机机会约束来处理收件量不确定的问题。其次,设计基于遗传算法和自适应大邻域搜索算法的混合启发式算法。最后,通过数值实验表明:所设计的混合算法比传统遗传算法具有较快的收敛速度和较好的求解质量;决策者对随机需求下的优化方案风险接受程度过高或过低都会导致成本上升;随客户收派量之比的增加,快递末端配送成本呈先降低后增高的趋势;采用最近网点返回策略可有效降低企业配送成本。

考虑满意度的团购两级混合冷链低碳路径优化

考虑当前社区团购生鲜品冷链运输过程中,因品质衰减导致顾客满意度降低,同时需求井喷造成运力不足的问题,提出一种基于众包模式的两级冷链协同优化配送策略,即由企业冷藏车完成城市仓至中转仓的一级冷链运输,由众包冷藏车完成由中转仓至团长的二级冷链运输,并以包含服务延迟成本、碳排放成本和固定成本的总成本最小,及团长对产品品质满意度最大为优化目标,建立一个带有众包的两级开闭混合冷链低碳路径规划模型。针对模型特点,构造了一种改进的自适应大领域搜索算法(improved adaptive large neighborhood search,IALNS),设计了新的破坏-修复解的策略,并在算子选择阶段加入模拟退火算法(simulated annealing,SA)的思想,以加快收敛速度,提高算法全局搜索能力。通过分别与自适应大领域算法(adaptive large neighborhood search,ALNS)、模拟退火算法、遗传算法(genetic algorithm,GA)、粒子群优化算法(particle swarm optimization,PSO)的算例优化结果对比,证明该算法的有效性。该策略兼顾企业利润和客户需求,对比在不同配送模式下的实验结果,验证了该模型在解决社区团购生鲜品冷链物流问题上有积极意义。

面向突发应急事件的定制公交线网优化研究

为保障突发应急事件下乘客的出行效率与安全,研究一类全新的面向突发应急事件的定制公交线网优化问题,旨在降低乘客出行时间、提高救援效率。首先引入风险系数概念,以描述不同乘客受突发应急事件的影响程度。其次,以所有乘客的出行时间最小化为目标,考虑需求点优先级、车辆容量、车辆到达时间等约束,构建一个混合整数非线性规划模型。同时针对模型特点,设计基于应急服务特点的破坏算子,改进自适应大邻域搜索算法,通过大量仿真算例验证模型与算法的可行性。实验结果表明:求解大规模算例时,改进算法相较于文献中的遗传算法,获取最优解的能力更强,平均节约出行时间1.38%。最后,将常规情境与突发应急事件下的优化方案进行对比,在相同出行需求下,应急定制公交线网优化的总运行时长比常规情况增加9.624 min;高风险需求点接受服务的时间相较于常规情况降低4.5%。与常规情况相比,该模型得到的线网优化方案更能实现乘客安全高效的转移,可为城市应急救援方案提供参考。

考虑可配送时间和柔性时间期限的电动车路径问题

随着低碳绿色、节能环保的经济发展理念越来越受到重视,电动车逐渐成为物流配送的主要运输工具,且物流配送服务的灵活性也越来越受到重视。在传统的车辆路径问题中,通常假设客户需要在指定的时间窗口内接收货物,如果未能按时送达,则会被视为违约,造成客户满意度下降。然而,在实际应用中,大部分客户接受在截止日期后一定时间内延迟接收货物,但这种灵活性通常伴随着额外的成本。针对货物具有可配送时间和柔性时间期限的情况,研究了考虑可配送时间和柔性时间期限的电动车车辆路径问题。构建了以车辆数量、行驶成本和违反时间期限的惩罚成本最小化为目标的混合整数规划模型,设计了改进的自适应大邻域搜索算法对其求解,基于问题特性设计了高效的破坏算子和修复算子以扩大解的搜索空间、运用自适应策略选择高效的搜索算子以及引入模拟退火新解接受策略避免陷入局部最优。通过对随机生成的算例进行计算验证了模型和算法的有效性,并分析了是否考虑柔性时间期限约束及不同的违反时间期限惩罚系数对总成本的影响,本研究为物流配送企业电动车车辆路径规划提供参考依据。

灾后应急救援背景下卡车-无人机协同配送路径规划

无人机因其具有不受道路条件和交通拥堵影响的特点而被应用于物流配送,因此针对灾后道路损毁严重,卡车无法及时配送救援物资的问题,提出利用“卡车-无人机”协同配送的模式进行救援物资的配送。文章对多辆卡车多架无人机灾后协同配送物资的路径规划问题进行了研究,考虑到受灾群众对救援物资的需求紧迫性,受灾群众满意度会随着救援物资送达时间的延长而降低,因此以最大化受灾群众满意度为目标建立了卡车-无人机协同物资配送模型,并使用了自适应大邻域搜索算法对模型进行求解。最后,通过卡车-无人机协同配送和卡车单独配送两种情况下的对比实验验证了无人机在灾后救援物资配送中的有效性。

基于两阶段启发式算法的省电力物资周转库选址-路径优化研究

省电力物资周转库是仓储网络架构的关键节点,文中研究带库存容量限制的周转库选址与考虑时间窗和装载量约束的车辆配送路径优化的组合决策问题,构建以配送总成本最小为目标的选址-路径问题模型,设计两阶段启发式算法进行求解。第一阶段设计聚类-重心-搜索算法,求解带库存容量限制的省周转库选址问题;第二阶段采用自适应大邻域搜索算法,解决考虑时间窗和装载量约束车辆配送路径优化问题。基于S省2022年历史物流数据和已有仓储资源规模,采用两阶段启发式算法确定省电力物资周转库选址和配送路径。结果表明该算法能够有效降低仓储网络的总配送成本。

ALNS算法求解带软时间窗同时取送货的PCVRP问题

考虑电子商务环境下订单种类多、批量小等特点,在现有奖金收集车辆路径问题(PCVRP)模型的基础上加入时间窗约束和同时取送货需求,建立了带软时间窗同时取送货的PCVRP模型。设计了自适应大邻域搜索算法(ALNS)进行求解,采用插入法生成初始解,再用ALNS对初始解进行改进。通过仿真实验将设计的ALSN算法计算结果与使用遗传算法、模拟退火算法、布谷鸟算法、禁忌搜索算法及离散粒子群算法的计算结果进行比较,仿真实验结果验证了模型的合理性及ALNS算法的有效性。实验结果表明所设计的ALNS算法在求解大规模问题方面具有更好的寻优能力。

考虑动态需求的多中心沿途补货冷链物流配送路径优化

为提升冷链物流配送效率、降低物流成本,本文在综合考虑多配送中心、客户动态需求、沿途补货策略的前提下,建立以总配送成本和客户满意度最优为目标的冷链物流配送模型.模型采用主目标法处理客户满意度和成本之间的背反关系,将动态问题按照时间轴依次分解为一系列的静态调度子问题并考虑了5种配送成本.本文提出自适应大邻域搜索算法求解该模型,设计了三种破坏算子和三种修复算子,对小中大三种不同规模的算例进行测算.结果表明该算法在速度、精度和稳定性上表现良好,对求解此类问题有较好的适应性和准确性.与不考虑沿途补货策略的动态配送方案相比,沿途补货策略可使成本降低23.06%、客户满意度提升8.69%.结果表明提出的配送方案可很好地节约企业的配送资源、减少配送成本、增强竞争力.

考虑同时取送和时间窗的车辆路径及求解算法

针对带时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup-delivery and time windows,VRPSPDTW),构建了以车辆使用成本、车辆行驶距离成本总支出最小化的路径优化数学模型,提出自适应头脑风暴算法(adaptive brain storm optimization,ABSO)进行求解。全局搜索阶段,采用多项惩罚方式扩大搜索区域,并使用聚类及三种路径搜索策略进行全局搜索;局部搜索阶段,将六种破坏-修复算子作为备选集合,进而设计自适应动态选择邻域搜索机制,增强局部搜索效能。选取测试数据集和实际案例对算法性能进行测试,实验结果表明针对小规模标准算例,所提算法全部取得了当前已知最优解;对于大规模标准算例,通过与遗传算法、并行模拟退火算法、离散布谷鸟算法对比,所提算法实验计算结果有7.52%~12.03%的提升;对于实际案例,所提算法在收敛速度和寻优能力方面均展示出优越性,充分验证了所提算法对解决VRPSPDTW问题的有效性。

电商RMFS系统订单分配与路径规划联合优化方法

随着电子商务的蓬勃发展,海量客户需求和高频率、多品种、小批量的订单特性为订单拣选业务带来巨大挑战。在物流智能化的趋势下,大量电商企业采用移动机器人拣货系统(Robotic Mobile Fulfillment System,RMFS)进行订单拣选。订单分配和拣选路径规划是影响仓库订单拣选效率的关键决策。为了提高电商RMFS系统拣选效率,降低仓库运营成本,基于电商企业多订单、多货架、多拣选站下的拣选业务场景,以最小化机器人负载距离为目标,构建订单分配与路径规划联合优化模型,设计两阶段的A*算法和自适应大领域搜索算法(Adaptive Large Neighborhood Search,ALNS),在ALNS算法原有框架的基础上提出新的移除和修复算子以适应订单分配问题,并针对30个不同规模算例进行计算分析。计算结果表明,所提出的优化方法收敛快、性能稳定,能够有效缩短机器人行走距离,相比先到先拣选策略最大可缩短47.6%的机器人负载距离。同时,也可在更短时间内获得与CPLEX求解质量相近的解。尤其是当订单数量增长时,相比CPLEX具有突出时间优势,可以实现电商仓储资源的合理调度和配置,从而为电商企业仓储智能化提供有效决策指导。

考虑工人疲劳的双资源柔性作业车间调度优化

针对生产制造过程中的工人疲劳问题,在人机双资源约束柔性作业车间调度问题的基础上,以最小化完工时间为目标,构建混合整数规划模型,保证工人疲劳不超过限定水平.提出改进的自适应大规模邻域搜索算法,以解决工件排序、机器分配、工人指派和工人疲劳等高度复杂的子问题.所提算法使用8种启发式规则生成初始解,引入6类破坏算子和6类修复算子实现对解空间的高效搜索.通过不同规模的算例对比,验证所提算法的有效性.相较于Gurobi求解器、遗传算法、Jaya算法和标准ALNS算法,所提算法具有良好的寻优性能,能够有效解决作业车间调度过程中的工人疲劳问题.

服务差异二级选址路径问题及大邻域搜索算法

在电子商务背景下,物流公司为了实现及时交付并缓解交通拥堵,可按照客户不同的服务需求,将其分为自取型和配送型,进而选择开放自助点或配送点对客户进行服务。自助点和配送点作为二级物流设施,配送中心作为一级物流设施,由此形成了二级选址-路径问题。在配送车数量约束、自助点容量约束等限制下,兼顾客户点物品回收,以总物流成本最小为目标,建立考虑服务差异的二级选址-路径问题模型。设计自适应大邻域搜索算法进行求解,通过Nguyen的2E-LRP算例进行测试,更新了1个算例的全球最优解,其余算例达到或接近最优解,平均Gap值在1.22%以内,验证了算法的有效性及良好的收敛性。实际案例模拟分析验证了模型的有效性和适用性,可以为相关物流企业提供决策依据和参考。