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

为了给物流企业在车辆配送方案制定上提供决策支持,针对电动物流车与燃油物流车混合配送的模式,研究了带时间窗的动态需求车辆路径问题,建立了以配送总成本最小化为目标的两阶段整数规划模型。针对模型特点,设计了改进的自适应大规模邻域搜索(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的速度更快,质量更好,证明了该算法在求解时效性要求高的动态需求车辆路径问题的优越性。

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

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

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

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

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

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

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

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

基于改进灰狼优化算法的柔性作业车间分批调度问题研究

针对以最小化最大完工时间为目标的柔性作业车间分批调度问题(Flexible Job shop Batch Scheduling Problem,FJBSP),提出了一种改进灰狼优化(Improved Grey Wolf Optimization,IGWO)算法,优化对象为工件的分批方案。首次将流体模型应用于FJBSP的求解,提出了一种基于流体模型的解码方法,用于获得更好的子批调度方案;然后改进了狼群的等级制度,避免了算法过早收敛;其次设计了一种全新的适应可变长编码的交叉方法,深入交流2个个体之间的分批信息,增强了算法的搜索能力和稳定性;再次,提出了能够动态更新个体游走率的自适应灰狼游走策略,兼顾了算法的搜索质量和收敛速度;此外,对领头狼使用自适应邻域搜索动态调整每种工件选择各邻域的概率,提高算法的局部搜索能力;最后,设计了9个算例和3组实验,验证了所提出的IGWO算法的有效性和优越性。

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

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

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

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

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

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

基于跨邻域搜索的连续域蚁群优化算法

针对连续域蚁群算法寻优能力差、容易产生局部最优的问题,提出了一种基于跨邻域搜索的改进蚁群算法。首先,通过自适应种群划分方式计算可行解和不可行解群体;然后,针对不可行解群体利用自主选择学习算子选择对象进行学习,目的是不断扩大种群规模,避免算法陷入局部极值点,继而对可行解群体采取全局跨邻域搜索的方式,引导蚂蚁向全局最优解靠近,加快收敛速度;最后,基于全局最优解采用局部跨邻域的方式引导蚂蚁在小范围内进行细致搜索,提高收敛精度。通过与其他连续域蚁群优化算法针对CEC2017测试函数在低维和高维情况下的实验对比,证明本文算法具有较好的寻优能力和稳定性,能有效避免陷入局部最优。

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

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

考虑时变路网的多行程电动车辆路径问题研究

为了降低城市物流的电动车配送成本,考虑道路交通网络的时变性对电动车多行程配送活动进行研究。首先,以固定成本、充电成本和时间惩罚成本之和最小化为优化目标,构建时变路网下的多行程电动车辆路径问题模型;其次,利用自适应大规模邻域搜索算法对实际案例进行求解;最后,分别对出发时刻、路网时变性、充电策略和电价进行分析。结果表明:路网时变性在不同时刻下对成本和配送用时的影响不同,不同出发时刻有着不同的最优路线规划;电价的小范围波动对配送活动的影响很小;充电策略的选择对配送用时和成本的影响显著。

考虑众包物流的大型生鲜商超配送策略研究

针对冷链运输导致大型生鲜商超配送成本高的问题,本文提出了一种采用众包车和自备物流协同配送的模式。考虑企业调用社会车辆并结合自有冷链运输实施众包协同配送,将商品分为冷冻、冷藏、常温三类,构建了带容量和软时间窗限制的多车型车辆路径问题(HFCVRPSTW)模型。该模型涉及冷藏车行驶成本、固定成本、众包车补偿成本、冷藏商品包装成本和损失成本以及时间成本等多个参数。通过设计初始解、采用自循环的衰减破坏策略以及引入新算子的改进自适应大规模邻域搜索(ALNS)算法对模型求解。采用Solomon数据集的拓展算例验证了模型的合理性和算法的优越性。研究得到以下结论:(1)通过对不同类商品的数量比例以及众包车数量进行灵敏度分析发现,众包协同配送的总成本对物流货物中各类商品的配比不敏感,但众包车数量的增加会更有效地降低总成本;(2)对比不同客户分布的算例研究得出,客户点的分布对众包协同配送降低总成本的效果具有显著影响,当客户处于随机分布与混合分布状态时,企业应优先选择众包协同配送,当客户呈聚集分布且众包车数量较少时,企业应优先选择自营配送。

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

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

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

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

基于配送员等级的多目标众包配送路径优化研究

目前,众包平台已经到了平稳发展阶段,该阶段平台的重点已经转为如何降低总成本和提高顾客满意度。该文将众包配送员等级与最大承单量、配送时间及额外成本支出挂钩,并考虑了跑腿订单,针对取送交叉的路径优化问题,构建总成本最低和顾客满意度最高的多目标函数,同时设计多种移除修复算子,利用自适应大邻域搜索算法求解。最后通过M平台的实际数据设计了的数值仿真试验,同时与改进的遗传算法进行对比,验证了该算法解决该模型的有效性。

考虑真实场景动态事件的动态取送货问题

实时城市配送决策高度依赖于环境的变化,须及时处理配送系统中由各种动态事件带来的需求和环境变化.综合考虑新请求逐渐出现、旧请求修改或取消、交通拥堵状况和车辆抛锚4种动态事件对车辆路径规划和配送服务的影响,重新建立考虑实时场景多项动态事件的取送货(DPDP-MDE)动态车辆路径规划模型.设计动态算法框架求解该模型,给出调度时域内静态子问题执行规则和计算规则;针对具体静态子问题,采用构造型启发式算法生成初始可行解,分别采用禁忌搜索算法和自适应大规模邻域搜索算法2种智能优化算法,改善初始可行解质量;在更新路径规划方案时,运用未固定动态插入法,解决处于规划中的未固定请求和新请求同步处理问题.数值实验表明,所提出的模型及设计的动态算法框架能有效解决带时间窗的动态取送货问题(DPDP-TW).

混合优化算法求解同时送取货车辆路径问题

为了给各物流企业在车辆配送路径规划方面提供合理有效的决策支持,针对单配送中心的配送模式,研究带时间窗约束的同时送取货车辆路径问题(VRPSDPTW),建立以总配送成本最小化为目标的数学模型。根据模型的特征,提出基于模拟退火(SA)与自适应大规模邻域搜索(ALNS)相结合的混合优化算法(SA-ALNS)。采用基于时间与距离加权的插入启发式算法构造问题的初始解;引入多种删除、插入算子,以自适应选择策略进行路径优化,并通过反馈机制,逐渐调整各操作算子被选择的概率,使算法更倾向于选择寻优效果较好的算子;使用模拟退火机制的Metropolis准则控制解的更新。仿真实验中测试了56个大规模算例,对比了p-SA算法、DCS算法和VNS-BSTS等其他智能优化算法并进行统计分析,结果证明该算法在求解带时间窗约束的同时送取货车辆路径问题的可行性和优越性,研究成果极大丰富了车辆路径问题(VRP)的相关研究。

随机需求订单可拆分的多目标车辆路径问题

考虑现实中需求随机,司机的工作量和收入可能受线路长度影响,研究基于需求随机订单可拆分的多目标车辆路径问题,添加司机工作线路长度均衡为目标,这种考虑需求随机和线路均衡的双目标模型比原来的单目标模型更具有现实应用意义。此外订单可拆分可提高车辆装载率,降低配送费用。基于以上考虑,本文构造考虑随机需求订单可拆分的双目标车辆路径问题模型,提出订单拆分车辆配对服务策略。针对本文研究问题特点,设计大规模邻域自适应搜索算法进行仿真实验,并通过修订的Solomon算例验证模型和算法的有效性。

道路养护中的带随机时间变量的弧路径规划问题

研究高速路网日常维护中的养护车辆路径优化问题,考虑车辆养护服务时间和移动时间的不确定性,通过科学的规划手段和精确有效的决策方法,可以减少以前依赖人工决策导致的资源浪费。将问题定义为一个带随机时间变量的限容量弧路径规划问题,分别使用机会约束规划模型和带修正的随机规划模型进行描述。针对问题的随机性,提出自适应大规模邻域搜索算法,在优化过程中根据各个删除策略和插入策略对解的表现对其进行评分,根据轮盘赌原则自适应地选择删除策略和插入策略。与分支切割算法进行比较,解的差距只有1.45%~3.15%,但计算时间有显著提升,证明了自适应大规模邻域搜索算法的有效性,能够适用于中大规模问题。通过真实路网算例,显示了带修正的随机规划模型在特定情况下相对于机会约束规划模型的优越性。还对置信水平α和变异系数CV这2个重要变量进行了敏感性分析,显示了其对解的影响程度。