求解多车场累积时间车辆路径问题的Memetic算法

在应急救援车辆路径优化问题中,为了及时救援,缩短所有受灾点的总等待时间,提出了多车辆车场累积时间车辆路径问题。它是多个车场通过多个运输车队,使所有受灾点等待时间总和最短的运输问题。针对该NP难问题提出了一种Memetic算法求解。先用改进的最优切割算法MDVRP-Split将受灾点分配至各车场,通过选择、交叉及局部搜索得到最优路径。标准算例的测试结果表明,提出的算法注重了求解质量与求解效率的平衡。

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

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

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

针对带时间窗的时间依赖型同时取送货车辆路径问题(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%,可有效提高物流企业的经济效益。

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

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

改进最近邻算法求解多车场车辆路径问题

论文提出了一种改进最近邻算法用于求解多车场车辆路径问题(multi-depot vehicle routing problem,MDVRP)。为了求解问题解空间得到有效控制,融合最近邻算法与K-means算法的优势对客户进行较为合理的车场分配,将多车场车辆路径问题分解成多个单车场车辆路径子问题。在子问题的求解阶段,提出一种编解码规则,基于车辆装载量利用率得到提高,减少车场车辆路径长度,设计了全局优化策略,基于车辆内部客户访问顺序及车辆间客户改变导致路径长度变化,设计了局部优化策略,提出了随车辆服务客户数变化而变化的搜索策略,提高了算法的运行效率。在不同规模的问题和仿真实验上验证了所提算法的有效性。

带软时间窗约束的多车场车辆路径问题及其禁忌搜索算法研究

带软时间窗约束的多车场车辆路径问题在基础上增加了“多车场”与“时间窗”约束条件。本文建立了相应问题的数学模型,在此基础上设计了求解该模型的禁忌搜索算法,将多配车场中心车辆调度问题看作一个复杂的组合优化问题来进行研究。通过实验得出比较优的结果,证明了提出的算法是有效可行的,禁忌搜索算法搜索速度和寻优能力具有优越性。

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

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

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

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

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

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

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

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

多车场异构车型绿色路径规划问题研究

为拓展多车场车辆路径类问题(MDVRP)的求解方式及途径,引入了油耗和碳排放量的近似计算方法,建立了带时间窗的多车场多车型绿色车辆路径问题模型(GMDHF-VRPTW)。将物流配送和碳排放总成本最小化作为优化目标,设计改进的禁忌搜索算法(ITS)求解该模型。为验证提出模型的有效性和可行性,采用Solomon测试数据集,分别从最优目标值、求解时间等方面与经典的禁忌算法进行对比,实验结果表明ITS方法有显著的优势。此外,为降低问题求解的复杂度,结合K-means聚类算法,将多车场转化为单车场,通过判断满足需求的最小车辆数进行建模并提出了基于Gurobi求解器的聚类过滤算法(CF),在求解同规模多车场多车型路径问题进行了探索,结果表明CF颇具优势,能够为企业实际的低碳物流运输提供决策支持和方法指导。

多中心半开放式同时送取货的车辆路径问题研究

研究了带软时间窗约束的多配送中心半开放式同时送取货的车辆路径问题,所有客户点均存在送取两种需求,并采用同一辆车同时提供送取服务.车辆服务完路线上所有客户点后,不一定返回起始配送中心,可就近返回任意配送中心.在此条件下,构建了以车辆运输成本、车辆租赁成本、时间窗惩罚成本等总和最小为目标的优化模型.根据问题特征,设计了自适应精英遗传算法对该问题进行求解,引入自适应机制,根据个体的适应度动态地调节交叉和变异概率,采用精英保留策略将优秀个体进行遗传保留,不仅增强了算法的全局优化能力,还均衡了算法的局部搜索能力.通过案例仿真,验证了模型和算法的可行性和有效性.研究成果丰富了车辆路径问题的相关研究,为物流企业提供了一种决策参考.

基于改进蚁群算法求解带软时间窗的车辆路径问题

针对带软时间窗的车辆路径问题(VRPSTW),建立以配送成本为优化目标的混合整数规划模型,提出一种改进蚁群算法(IACO)求解该问题。在传统蚁群算法(ACO)的基础上,改进蚂蚁状态转移概率公式,通过自适应调整信息素挥发系数改进信息素更新策略,设计插入算子和交换算子嵌入变邻域局部搜索,并设置开始和退出局部搜索的条件,更新当前局部最优解。选取Solomon标准测试集里3类不同规模的算例,测试算法改进效果,以客户规模为100的C类算例验证所提算法求解较大规模算例的可行性,并与传统蚁群算法以及其他文献中的算例结果进行对比。实验结果表明,改进蚁群算法的寻优能力高于其他算法,求解得到的最优配送方案能够实现更低的车辆配送成本,从而验证了改进蚁群算法的有效性。

考虑软时间窗的同时送取货随机旅行时间车辆路径问题

考虑车辆总旅行时间约束和车辆载重限制以及客户对服务时间窗的要求,研究带有软时间窗的同时送取货随机旅行时间车辆路径问题(STT‒VRPSPD),建立机会约束规划模型。将禁忌搜索算法与分散搜索算法相结合,构建混合分散禁忌搜索(HSTS)算法,并采用C‒W节约算法生成初始解。基于经典的Dethloff算例和Solomon时间窗生成方法,分别生成包括50个客户、200个客户各20组算例,算例测试结果验证了混合分散禁忌搜索算法的有效性。

改进蚁群算法优化车辆路径问题的研究

研究采用改进的蚁群算法优化带约束的车辆路径的问题。考虑的约束条件包括路径约束、时间窗约束和容量约束。主要目的是提出一种改进的蚁群算法进行车辆路径优化,构建配送车辆行驶路线,实现配送路线总成本的最小化。从三方面对蚁群算法进行了改进:对参与条件转移概率的候选节点列表进行预处理减少路线构建过程计算的时间复杂度;提出插入式节约算法用于改进蚁群初始配送路线提高寻优精度;基于蚁群系统对信息素更新策略进行改进,加快算法收敛速度。基于Solomon基准数据集,与近年来已取得的研究成果展开对比实验,证明提出的改进算法在提高求解精度和搜索效率方面的有效性,在优化带约束条件的车辆路径问题时的实用性,拓展了蚁群算法的应用领域。

学习型离散排超联赛算法求解带时间窗的绿色多车型两级车辆路径问题

针对现实中广泛存在的带时间窗的绿色多车型两级车辆路径问题(G2E-HVRP-TW),本文提出一种结合加权K-means算法(WKA)的学习型离散排超联赛算法(LDVPLA)进行求解.首先,根据该问题规模大、约束多的特点,采用WKA将原问题G2E-HVRP-TW分解为一个绿色多车型车辆路径子问题(GHVRP)和一组带时间窗的GHVRP(GHVRP-TW),从而实现两级问题间的部分解耦,以合理缩小搜索空间.然后,利用LDVPLA求解分解后的一系列子问题,并将各子问题的解合并后得到原问题的解. LDVPLA在竞赛阶段将标准排超联赛算法(VPLA)中实数个体更新操作替换为一系列排序操作,使其能够直接在问题离散解空间内执行基于VPLA机制的搜索,可提高搜索效率;在学习阶段构建三维概率矩阵模型合理学习并积累优质解信息,有利于驱动算法较快到达解空间中的优质解区域执行搜索;在淘汰阶段设计一种重启策略,可避免算法过早陷入局部最优.最后,通过在不同规模算例上的仿真实验和算法对比,验证了所提算法的有效性.

深度强化学习Memetic算法求解取送货车辆路径问题

带时间窗约束的同时取送货车辆路径问题(VRPSPDTW)是NP难问题,属于约束较复杂的车辆路径问题,在现代物流中有广泛应用。提出深度强化学习Memetic算法求解该问题,将Memetic算法求解VRPSPDTW问题中的大邻域搜索过程建模成马尔可夫决策过程,构建编码器-解码器架构的深度神经网络模型完成大邻域搜索中的移除操作。编码器对当前解中各结点的个体特征和位置特征进行信息交互,解码器输出需要移除的结点,设计了非自回归和自回归两种网络结构,采用强化学习算法训练神经网络模型。设计了混合策略,将人工设计的启发式策略与深度强化学习到的策略相结合,以提高寻优能力。实验结果显示提出的算法具有更强的跳出局部最优的能力,能在有效的时间内获得比对比算法更优的解,特别是在大规模问题上。最后,对提出算法的新组件进行了消融实验,证明了算法的有效性。

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

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

带时间窗的危险货物车辆路径问题2阶段优化

为有效降低危险货物道路运输的风险和成本,针对带时间窗的危险货物车辆路径问题(HMVRPTW),设计2阶段优化方法。首先,根据特征将该问题分解为双目标最短路径问题和带时间窗双目标车辆路径问题(VRP),分别建立数学模型并设计2阶段方法求解,第1阶段采用脉冲算法初筛路径,第2阶段设计针对带时间窗双目标VRP蚁群算法;然后,以9个节点和17条边的测试为例,说明求解过程;最后,以兰州市主城区16个加油站油品配送为例,采用该方法分配运输车辆,计算平均用时为2438 s,可获得Pareto最优解,而采用多目标遗传算法平均用时为41.05 s。结果表明:所提方法通过初筛路径能够简化问题规模,充分考虑危险货物运输风险变化及时间窗因素,引导蚂蚁在指定搜索空间中寻优,在效率方面较多目标遗传算法具有明显优势。

有时间窗约束的多车场车辆路径问题的改进遗传算法

在给出有时间窗约束的多车场车辆路径问题(MDVRPTW)的数学模型基础上,引入一种新的编码方式,并对RC交叉算子进行修正,构造出一种改进的遗传算法,实验证明能够有效地解决MDVRPTW的优化问题。