带时间窗的时间依赖型同时取送货车辆路径问题研究

针对带时间窗的时间依赖型同时取送货车辆路径问题(Time Dependent Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows,TDVRPSPDTW),本文建立以车辆固定成本、驾驶员成本、燃油消耗及碳排放成本之和为优化目标的数学模型;并在传统蚁群算法的基础上,利用节约启发式构造初始解初始化信息素,改进状态转移规则,引入局部搜索策略,提出一种带自适应大邻域搜索的混合蚁群算法(Ant Colony Optimization with Adaptive Large Neighborhood Search,ACO-ALNS)进行求解;最后,分别选取基准问题算例和改编生成TDVRPSPDTW算例进行实验。实验结果表明:本文提出的ACO-ALNS算法可有效解决TDVRPSPDTW的基准问题;相较于模拟退火算法和带局部搜索的蚁群算法,本文算法求解得到的总配送成本最优值平均分别改善7.56%和2.90%;另外,相比于仅考虑碳排放或配送时间的模型,本文所构建的模型综合多种因素,总配送成本平均分别降低4.38%和3.18%,可有效提高物流企业的经济效益。

时间依赖型车辆路径问题的一种改进蚁群算法

时间依赖型车辆路径规划问题(TDVRP),是研究路段行程时间随出发时刻变化的路网环境下的车辆路径优化.传统车辆路径问题(VRP)已被证明是NP-hard问题,因此,考虑交通状况时变特征的TDVRP问题求解更为困难.本文设计了一种TDVRP问题的改进蚁群算法,采用基于最小成本的最邻近法(NNC算法)生成蚁群算法的初始可行解,通过局部搜索操作提高可行解的质量,采用最大--最小蚂蚁系统信息素更新策略.测试结果表明,与最邻近算法和遗传算法相比,改进蚁群算法具有更高的效率,能够得到更优的结果;对于大规模TDVRP问题,改进蚁群算法也表现出良好的性能,即使客户节点数量达到1000,算法的优化时间依然在可接受的范围内.

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

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

基于并行模拟退火算法求解时间依赖型车辆路径问题

为提高传统串行模拟退火算法求解时间依赖型车辆路径问题的效率,提出一种并行模拟退火算法。该算法首先使用前向插入启发式算法生成初始解,在主从式并行模拟退火算法框架下使用4种邻域搜索法对初始解进行优化。采用Figliozzi测试数据库(包含56个测试问题,顾客数均设定为100)对算法性能进行测试,结果表明在不同时间依赖型行驶函数情形下,当使用6个线程时,并行模拟退火算法相对于传统串行模拟退火算法可以得到近似于5倍的加速比,且均能在较快时间内得到比Figliozzi算法更优的解。因此,并行模拟退火算法能有效地求解时间依赖型车辆路径问题,并且可以灵活地扩展解决其他车辆路径问题和组合优化问题。

时间依赖型多时间窗车辆路径问题研究

针对一类考虑城市交通拥堵情况的时间依赖型多时间窗车辆路径问题(time-dependent vehicle routing problem with multiple time windows,TD_VRPMTW),提出一种混合离散灰狼算法(hybrid discrete grey wolf optimizer,HDGWO)进行求解。在HDGWO中,设计了新的灰狼个体更新公式,采用基于客户排列的整数编码方式,使算法可直接在离散问题解空间中执行基于标准灰狼算法个体更新机理的全局搜索;设计了基于问题性质的种群初始化策略,用于生成具有高质量和多样性的初始种群;引入头狼信息交流公式,用于探索头狼形成的优质解空间;构造具有多种局部搜索操作的自适应变邻域局部搜索策略,用于增强算法的局部搜索能力。结果表明:HDGWO可有效求解TD_VRPMTW。

求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法

针对单一机制的自适应大邻域搜索算法存在早熟收敛、易陷入局部最优的问题,提出了一种混合自适应大邻域搜索算法来求解冷链物流时间依赖型车辆路径问题(TDVRP)。首先,根据连续型行驶时间依赖函数来刻画时变车速,采用综合油耗模型来评估实时燃油消耗量,并建立了以总成本最小化为目标的路径优化模型;然后,根据问题的NP-hard性质和时间依赖特性设计了多种破坏和修复解的大邻域搜索算子,并将破坏-修复大邻域搜索算子融入到人工蜂群(ABC)算法之中,以提高算法的全局搜索能力。仿真实验结果表明,与自适应可变邻域搜索精英蚁群(AVNS_EAC)算法、自适应大邻域搜索精英蚁群(ALNS_EAC)算法、自适应大邻域搜索精英遗传(ALNS_EG)算法和自适应大邻域搜索模拟退火(ALNS_SA)算法相比,所提出的自适应大邻域搜索人工蜂群(ALNS_ABC)算法在多组测试数据上的最优适应度值分别平均提高了46.3%、5.3%、36.8%和6%。可见所提算法计算性能更高、稳定性更强,能够为冷链物流企业兼顾经济效益和环境效益提供更为合理的决策依据。

基于订单邻域的成品油二次配送中带时间窗车辆路径规划问题

为了求解一种合适的车辆路径规划方案,在满足加油站配送需求的前提下,使车辆总的配送成本最低,基于订单时间、空间和配送项目属性聚类构建订单邻域系统,将其用于车辆路径规划种群的初始化过程。建立了基于订单邻域系统的成品油配送车辆路径规划问题的数学模型,设计了基于订单邻域系统的改进量子遗传算法对模型进行求解。结合具体算例验证了模型与算法的可行性与有效性。

时间依赖型绿色车辆路径模型及改进蚁群算法

绿色车辆路径规划对物流配送领域的节能减排具有重要的现实意义。针对时间依赖型绿色车辆路径问题(time-dependent green vehicle routing problem,TDGVRP),考虑车辆不同出发时刻对行驶时间的影响,分析车辆时变速度、载重与碳排放率之间的关系,确定基于车辆时变速度和载重的碳排放率度量函数;在此基础上,以车辆油耗和碳排放成本、使用时间成本和固定成本、等待成本与人力成本之和作为目标函数,构建TDGVRP模型,并根据模型特点设计基于路段划分策略的车辆行驶时间计算方法,提出了改进蚁群算法。算例仿真结果表明,构建的模型和提出的算法能合理规划车辆出发时刻,有效规避交通拥堵时间段,降低配送总成本,减少油耗和碳排放。

改进混合粒子群算法求解带时间窗的无人机与车辆协同路径调度问题

为提高物流配送效率,考虑时间窗、无人机换电以及无人机多点连续配送等因素,提出了一种带时间窗的车辆与无人机协同配送问题,并设计一种带局部搜索的混合粒子群算法进行求解。该算法以混合粒子群算法为核心,通过构建高效的编解码策略实现了问题解空间到算法搜索空间的转换。进一步,该算法融合单点插入策略、车辆更换策略、无人机更换策略组成局部搜索策略,以此提高算法寻优能力。实验结果表明:所提模型比纯车辆配送的模型效率更高,节省了31.51%的成本;所提算法优于四种对比算法,优化率最高达到82.08%。

带时间窗的车辆路径问题的混合粒子群优化算法

针对带时间窗的车辆路径问题(Vehicle Routing Problems with Time Windows,VRPTW),提出了一种混合粒子群优化算法(Hybrid Particle Swarm Optimization,HPSO)进行求解。所提出的算法设计了一种高效的编解码策略,以此搭建HPSO算法解空间到VRPTW解空间的桥梁。同时为了提高算法的寻优能力,设计了由单点插入策略以及双点交换策略组成的局部搜索策略。通过solomon-50标准数据集中的九个算例进行仿真实验,实验结果证明了所提出算法的寻优能力和稳定性均优于对比算法,最优解误差相较于对比算法最多降低了38.32%。

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

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

基于GCOA算法的带时间窗车辆路径规划问题研究

GCOA算法是对遗传算法的重大改良,不仅加快了遗传算法的收敛速度,而且从一定程度上避免了遗传算法陷入局部最优,并增大了遗传算法获得最优解的能力。本文首先介绍了GCOA算法,然后通过具体问题的解决对比传统遗传算法与GCOA算法,得出GCOA算法在收敛速度及结果优化两方面的有效性,最后将GCOA算法应用于求解VRPTW问题上,得出最优化结论。

基于时间地理学的带时间窗车辆路径问题建模

为实现火力高效机动分配,针对带时间窗车辆路径问题,引入时间地理学的概念,在二维平面的基础上增加时间作为第三维度,建立描述移动对象时空可达性的优化模型。对导弹防御这类时敏强的作战场景通过时空棱柱进行表达和分析,形成时空路径,进而配置作战资源,协同打击时序,为指挥控制中涉及的机动作战问题提供必要的决策支撑。

考虑多时间窗的多行程车辆路径优化问题研究

提出了考虑多时间窗的多行程车辆路径优化问题,是带时间窗的多行程车辆路径问题的扩展,不仅决策每辆车服务客户的顺序,还需确定为每个客户提供服务的时间窗,同时要求送货服务时间满足选定的时间窗,且车辆每个行程服务的客户需求量之和不超过车辆的最大载重量等约束。以最小化车辆总行驶时间为目标构建了该问题的混合整数规划模型,并设计了迭代局部搜索算法进行求解。在迭代局部搜索算法框架下设计了适用于多时间窗和多行程场景的改进Solomon贪婪插入算法生成初始解,还设计了Or-opt和Relocate局部搜索算子以及随机交换扰动操作。基于初始解或当前最优解,通过交替使用这两种算子进行迭代搜索,更新当前最优解。算例结果表明了提出的模型和算法的有效性,验证了为客户提供多时间窗选项承运人可灵活地规划车辆路径和选择服务时间窗,从而减少车辆使用数量和总行驶时间。

货物可分割的车辆路径规划问题

针对货物可再分这一特征,提出可分割的车辆路径规划问题(DCVRP:Divided Capacity Vehicle Routing Problem)。通过以货物为基本单位进行建模处理,并对出现规模爆炸的问题用全局优化的方式做出解答。对遗传算法做出step by step的策略改进,避免出现“早熟”问题,并对经典遗传算法步骤进行了有效的改进,提升了寻找最优解的概率,降低了整体的路径规划成本。

动态路网下带时间窗车辆路径规划问题研究

为调解动态路网下配送成本与服务质量之间的矛盾,提出一种基于动态路网的VRPTW模型和算法。在VRPTW基础上,引入道路通过系数反映各路段不同时段路况信息,以成本最小为目标建立模型并利用改进遗传算法进行求解。选取Solomon测试数据集对模型及算法进行测试,结果显示,动态路网VRPTW最优解在增加1.93%行驶距离的同时可以提升8.45%的服务满意度。该研究对于激烈市场竞争环境下物流配送企业提升服务质量具有一定的借鉴意义。

基于离散灰狼算法的带软时间窗车辆路径规划问题

针对物流配送中对配送时效的要求,引入单位时间费用随时间变化的软时间窗,建立以车辆配送成本最小为目标的优化模型.应用离散灰狼算法求解该问题.由于标准灰狼算法只能求解连续型数值优化问题,引入交换算子(swap operator,SO)和交换序列(swap sequence,SS),并重新定义灰狼位置更新公式,使得灰狼算法可以求解带软时间窗的车辆路径规划离散问题.为了解决求解效率低和易陷入局部最优的问题,应用局部搜索(partial search,PS)技术优化离散灰狼算法.最后分别使用遗传算法和离散灰狼算法对同一算例求解,做对比实验.结果表明:离散灰狼算法可以有效求解带软时间窗的车辆路径规划问题,且离散灰狼算法在寻优能力和求解稳定性上均强于遗传算法.

面向复杂物流配送场景的车辆路径规划多任务辅助进化算法

在现代社会中,复杂物流配送场景的车辆路径规划问题(Vehicle routing problem,VRP)一般带有时间窗约束且需要提供同时取送货的服务.这种复杂物流配送场景的车辆路径规划问题是NP-难问题.当其规模逐渐增大时,一般的数学规划方法难以求解,通常使用启发式方法在限定时间内求得较优解.然而,传统的启发式方法从原大规模问题直接开始搜索,无法利用先前相关的优化知识,导致收敛速度较慢.因此,提出面向复杂物流配送场景的车辆路径规划多任务辅助进化算法(Multitask-based assisted evolutionary algorithm,MBEA),通过使用迁移优化方法加快算法收敛速度,其主要思想是通过构造多个简单且相似的子任务用于辅助优化原大规模问题.首先从原大规模问题中随机选择一部分客户订单用于构建多个不同的相似优化子任务,然后使用进化多任务(Evolutional multitasking,EMT)方法用于生成原大规模问题和优化子任务的候选解.由于优化子任务相对简单且与原大规模问题相似,其搜索得到的路径特征可以通过任务之间的知识迁移辅助优化原大规模问题,从而加快其求解速度.最后,提出的算法在京东物流公司快递取送货数据集上进行验证,其路径规划效果优于当前最新提出的路径规划算法.

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

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

家电送装一体/送装分离混合模式下的车辆路径问题

结合送装分离模式的灵活性和配送效率,研究家电送装一体和送装分离模式相结合的车辆路径问题,以寻求兼顾客户服务体验和整体送装效率的最优送装路径方案。基于混合整数线性规划方法建立了以送装总成本最小化为目标、带软时间窗的家电送装路径优化模型,并根据模型特点针对性设计了改进的遗传算法进行求解,通过算例验证了所提模型和算法的有效性。最后,结合实例比较了上述混合送装模式相对于送装一体和送装分离模式的优化方案绩效,以期为家电送装路径优化提供辅助决策支持。