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

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

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

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

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

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

基于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算法进行对比,实验结果表明,本文所提出的混合大规模领域搜索的改进蜣螂优化算法能找到更好的解,并且寻优能力和稳定性均优于对比算法。

基于改进ALNS算法的离散制造车间物料配送路径优化研究

针对离散制造车间在多品种、小批量生产模式下面临的物料配送复杂性问题,提出了一种有效的路径优化方法。目标是通过创新的算法设计,实现物料配送的成本最小化,从而提高车间物料配送的效率,确保物料的及时供应,提高生产效率。为确保优化方法能够适应实际生产环境的需求,提高模型和实际环境的精确性和匹配性,构建了一个包括车间仓库、多个物料需求工位点、配送车辆及其载荷限制、时间窗要求等因素的离散制造车间配送模型,并考虑了车间内实际环境存在的路径约束,结合相邻工位间的实际距离,通过应用Floyd算法进行预处理,确保能够计算出所有最短路径。针对该数学模型设计相应破坏和修复算子,并运用了改进的自适应大领域搜索(ALNS)算法,通过破坏和修复过程有效地探索解空间,并利用模拟退火策略以避免陷入局部最优解。以某离散制造车间为例进行的实验验证,改进的ALNS算法展现了其在解决物料配送路径优化问题上的有效性和高效率,可以更好的减少配送成本和提高生产效率。

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

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

遗传算法综述

遗传算法是一种自适应全局优化概率搜索算法,在各种科学工程领域得到了广泛的应用,文幸介绍了遗传算法的发展历程、理论研究和应用研究状况。

改进遗传算法求解旅行商问题

针对传统遗传算法求解旅行商问题收敛速度慢且不稳定的问题,提出了一种改进遗传算法(Improved genetic algorithms,IGA)。通过邻域搜索算法对初始化种群进行优化;设计了一种自适应调节的交叉和变异概率;加入了Metropolis准则,以一定概率接受劣解,提高跳出局部最优的能力;加入了逆转操作加强局部搜索能力,加快种群收敛。利用Matlab将IGA和其他五种算法在TSPLIB数据库中进行试验,结果表明,该算法在中小型TSP问题上的收敛速度和求解精度都有一定的优势。

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

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

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

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

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

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

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

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

无人车辅助卡车配送路径优化研究

使用无人车进行物流配送具有降低配送成本、提高配送效率等优点,但无人车对周边智能交通设施和自动驾驶技术要求较高,再加上政策约束,现有L4级无人车只适合简单环境的应用。针对无人车的配送特点,本文研究具有车辆载重限制和无人车配送区域限制的无人车与有人驾驶卡车协同配送路径优化问题,建立了以耗费工作人员时间最少为目标的数学模型。设计自适应聚类领域搜索算法,首先采用k-means聚类算法结合插入操作生成初始解,其次运用自适应领域搜索算法对初始解进行改进,再使用算例证明算法的有效性,最后探讨非限制区客户比例对配送时间的影响,并证明多使用无人车可以减少配送的时间成本。

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

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

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

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

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

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

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

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

考虑充电等待成本的电动汽车路径问题

随着电动汽车规模化发展,配套充电设施的不足严重制约了电动汽车用户的出行计划。为了提高电动汽车出行效率,分析了电动汽车在行驶过程中的充电需求问题,建立考虑时间窗特征及充电等待成本的电动汽车路径规划问题模型。该模型考虑充电站内车辆排队等待时间这个影响因素,采用M/G/1排队系统对等待时间进行模拟,以能源消耗与成本最低为目标,采用自适应大规模邻域搜索算法对路径规划问题进行求解,并以物流电动汽车为例进行仿真验证。结果表明:针对不同的行驶路径,该模型在电能消耗和等待成本等方面具有较好的表现,可为电动汽车充电路径规划选择提供借鉴。

模糊需求下时间依赖型车辆路径优化

针对客户需求模糊且有时间窗约束的时间依赖型车辆路径问题(TDVRP),基于先预优化后重调度的思想构建模型.在预优化阶段,依据可信性理论构建模糊机会约束优化模型处理客户点模糊需求;针对不同时间段道路的交通情况,采用Ichoua速度时间依赖函数表征车辆的行驶速度,并设计自适应大规模邻域搜索算法(ALNS)对其求解.在重调度阶段,应用随机模拟算法模拟客户点的真实需求,采用点重调度策略对预优化方案进行调整.通过改进的Solomon算例实验验证模型和算法的有效性.研究成果可丰富TDVRP问题的相关研究,为现实配送方案的优化决策提供理论依据.

面向多个无人机站点的车辆与无人机联合配送路径问题研究

车辆与无人机联合配送模式在产业界受到青睐,该模式有效地降低了配送成本,但却有极大的调度难度,问题的求解也非常复杂。本文对问题进行明确定义并建立模型,根据问题特性设计了一个自适应大规模邻域搜索(Adaptive Large Neighborhood Search,ALNS)算法,进行了大量的实验的对比和分析。研究结果表明,ALNS算法相比Gurobi在运行时间上有明显优势,结果相同甚至更优;车辆与无人机联合配送模式也较仅卡车配送模式节约了成本。