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

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

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

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

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

为了给物流企业在车辆配送方案制定上提供决策支持,针对电动物流车与燃油物流车混合配送的模式,研究了带时间窗的动态需求车辆路径问题,建立了以配送总成本最小化为目标的两阶段整数规划模型。针对模型特点,设计了改进的自适应大规模邻域搜索(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较对比算法能够更好地平衡全局搜索和局部搜索.此外.灵敏度分析实验表明,无人机载重能力和无人机续航能力是影响包裹配送时间的两个关键因素.

基于改进蚁群算法的外卖配送路径规划研究

从外卖配送员角度出发提出一种改进蚁群算法(Improved Ant Colony Optimization,IACO),在此基础上进行外卖配送路径规划研究.首先通过蚁群算法(Ant Colony Optimization,ACO)求解得到初始规划路径,然后通过大规模邻域搜索算法(Large Neighborhood Search,LNS)优化初始规划路径,通过将ACO和LNS算法结合,提高求解质量.为了验证方法的有效性,对外卖配送过程进行仿真,并且选用不同订单数量场景进行对照分析.根据最优配送方案路线图和目标罚函数的最优值可以得出,IACO算法是有效的,且可以提高外卖配送员外卖配送的效率.IACO算法不但能够提升配送的智能化水平,还从外卖配送员的角度提出一种更为人性化的配送方法,支持网络互联外卖平台派送系统的可持续化发展.

基于投影残差量化哈希的近似最近邻搜索

针对投影哈希中投影误差较大,二进制编码时原始信息丢失严重等问题,提出一种近似最近邻搜索方法。该方法通过多阶段量化策略减少编码过程中的投影及量化误差。在每阶段训练时,对前一阶段的量化残差采用投影、按维度训练码书及量化、反投影等运算生成各阶段的子量化器。子量化器按投影后数据的维度提供多个哈希函数,最终的哈希函数由各阶段哈希函数共同构成。在最近邻搜索时,给二进制编码加上权重以便对搜索结果进行重排,提高搜索精度。实验结果表明,基于投影残差量化哈希的近似最近邻的搜索性能优于当前主流的哈希方法。

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

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

基于CAA的船舶工艺仿真环境搭建与LNS-SATSP排产优化

为解决在DELMIA原生环境下手动操作较多、工作效率低问题,提出一种基于CAA的船舶工艺仿真环境搭建与LNS-SATSP排产相结合的方法。通过CAA实现自动构建流程库与PPR树有效降低仿真环境搭建时间,并结合基于大规模邻域搜索的三次模拟退火算法(LNS-SATSP)进行排产分析,规划产品加工路线并自动优化仿真环境。以船舶肋骨段加工为例,引入自动建模,通过改进排产算法使平均加工时间缩短7.04%,并对优化后仿真环境搭建流程进行验证。

考虑众包场景的电动车动态需求车辆路径问题

针对企业自有车辆和社会车辆共同取送货的场景,以及国家节能环保的政策背景,考虑分时电价、部分充电、软时间窗、以及动态需求等因素,以最小化配送总成本为目标,建立考虑众包场景的电动车动态需求车辆路径问题(EDDVRP-CD)的两阶段整数规划模型。考虑动态需求的时效性,设计了启发式算法——改进的禁忌自适应大规模邻域搜索算法(IALNS-TS),增加了新的删除算子和修复算子,同时提出了加速策略。分别与两种算法——自适应大规模邻域搜索算法(ALNS)以及禁忌搜索算法(TS)进行对比,通过大量算例验证了IALNS-TS算法能够快速响应动态需求,并有效降低总配送费用。

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

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

校车路径问题的改进迭代局部搜索算法

针对考虑站点服务时间、学生最大乘车时间约束的校车路径问题(SBRP),提出一种改进迭代局部搜索(ILS)算法以提升求解质量。该算法使用大规模邻域搜索(LNS)算法作为扰动算子;在解的破坏过程中,设计一组解的破坏因子并赋予一定的选择概率,每隔若干次迭代后根据解的质量自适应更改破坏因子的选择概率,进而调整解的破坏程度。为提升ILS解的多样性,算法采用了基于偏差系数的邻域解接受准则。在国际基准测试案例上进行了测试,测试结果表明在ILS算法中使用自适应调整破坏程度的LNS扰动比常规扰动和其他破坏扰动的求解质量有大幅提升;与蚁群算法的比较结果进一步验证了改进算法的有效性。

基于ALNS改进的蜣螂优化算法求解带时间窗的车路径问题

针对带时间窗的车辆路径问题(Vehicle Routing Problems with Time Windows, VRPTW),提出一种混合大规模领域搜索的改进蜣螂优化算法(Improved Dung Beetle Optimization of ALNS, ALSN-IDBO)进行求解。本文主要的改进点为:1) 设计新的编码解码方式实现连续蜣螂位置向量向离散客户序列的转化;2) 对于蜣螂优化算法的初始化采用随机、贪婪、最邻近而策略;3) 在ALNS中设计了3个移除算子和3个重插算子;4) 在传统的DBO中针对繁育的蜣螂和小蜣螂分别改进为螺旋搜索策略和三角游走策略。通过在标准Solomon数据集的部分算例进行实验,将本文算法与GA、DBO、ALNS算法进行对比,实验结果表明,本文所提出的混合大规模领域搜索的改进蜣螂优化算法能找到更好的解,并且寻优能力和稳定性均优于对比算法。

两级选址-路径问题的大规模邻域搜索模拟退火算法

针对目前越来越普遍的多级配送模式,建立以总成本最小为目标函数的两级选址-路径问题模型,并提出了大规模邻域搜索模拟退火算法进行求解.在模拟退火算法框架中,嵌入大规模邻域搜索过程,包含破坏、重组和局部搜索方法,从而进一步提高算法在解空间中构建邻域的范围.采用两级选址-路径问题标准算例对算法求解效果进行验证,并与标准模拟退火算法和国际已知最优解进行对比.结果显示,所建模型和算法正确有效,并且在求解大规模问题时算法能够取得相对更好的优化结果.

考虑新冠疫情扩散规律的医疗物资动态配送优化

为了满足新冠疫情防控的应急性需要,基于传染病扩散模型提出了一种物资配送方案周期滚动优化模型。该模型结合医疗物资外源补给和点对点运输的特点,考虑疫区医疗物资数量和物资配送时间对新冠疫情扩散的影响,以最小化感染人数和使用车辆数为目标,联合决策配送中心物资补给数量、疫区物资配送时间及配送量。根据所提出的多目标模型的特征,提出了两阶段优化方法,分别采用同步扰动随机逼近算法与大规模邻域搜索算法对模型进行求解,并结合具体算例将所提方法与其他配送策略进行了比较分析。结果表明,相较于其他策略,所提优化模型可有效减少13.9%~40.0%的感染病例和17.6%~30.0%的调度车辆,优化后的周期滚动决策方法,在节省人力物力的同时,有效避免了配送中心出现“爆仓”现象,为后续研究和实践提供参考。

基于自适应大邻域搜索算法的无人机-卡车-代收点协同配送

针对农村地区物流配送成本高、效率低等问题,对无人机-卡车-代收点的协同配送进行了研究,以助力“乡村振兴”战略。充分考虑农村道路条件、农户地理分布等特征,构建了面向农村的无人机-卡车-代收点协同配送整数规划模型,同时对无人机路径、卡车路径、代收点选址及分配、无人机发射点及回收点等进行决策。针对问题特点设计了初始解生成策略及改进的自适应大规模邻域搜索算法。此外,通过敏感性实验分析代收点服务范围和无人机飞行能力对配送系统的影响。最后,通过与精确算法求解器Gurobi、自适应大规模邻域搜索算法和两阶段构造搜索算法进行对比,验证了所设计算法的有效性。

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

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

基于混合算法的多机器人协作任务均衡规划研究

针对机器人完成任务不均衡问题展开分析,提出了基于混合算法的规划算法,包括适应度值分类的K-means聚类实现任务分配、黏菌算法提高整体搜索效率、头脑风暴算法机器人内进行局部更新操作和机器人间进行全局更新操作完成重规划操作、交叉操作和大规模邻域搜索操作用以更新个体.实验结果表明:基于混合算法的任务均衡规划方法能够均衡规划多机器人任务,优化任务规划结果,提升任务的完成效率.

混合乌鸦算法求解带软时间窗的车辆路径问题

为求解带软时间窗的车辆路径问题,提出一种混合乌鸦搜索算法(hybrid crow search algorithm, HCSA)。设计最小惩罚成本与最小距离成本两种种群初始化规则,根据乌鸦在搜寻食物时的确定性搜索与随机性搜索两种智能搜索行为,将固定感知概率改进为可自适应调整的动态参数,引入自适应大规模邻域搜索策略,设计多种确定性与随机性邻域搜索算子。与已有文献算例结果及Solomon测试数据库进行对比,其结果表明,HCSA的优化质量优于其它文献算法,可有效求解带软时间窗的车辆路径问题。