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

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

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

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

基于端到端深度强化学习求解有能力约束的车辆路径问题

有能力约束的车辆路径问题(CVRP)是现阶段供应链应用最常见的问题模型,现多采用启发式算法求解。但随着问题规模增大,启发式算法求解速度慢且无法保证解的质量。提出端到端深度强化学习(DRL)网络框架对CVRP进行研究。首先利用边聚合图注意力网络编码器(EGATE)对车辆路径规划问题的图表示进行特征嵌入编码;然后设计多头注意力解码器(MAD)进行解码,并提出多解码策略以增加解的空间多样性;接着利用带回滚基线的基线REINFORCE算法对端到端网络模型进行训练,基线可自适应性更新以提升模型训练效果,并利用奖励函数归一化和Adam优化器对算法进行优化。最后通过对不同规模问题的实验以及与其他算法进行对比,验证了所提出端到端DRL框架的可行性与有效性,经过训练的模型在CVRPLIB公共数据集上的平均求解时间仅需0.189 s即可得到较优解。

车辆路径规划问题及其求解方法研究进展

对车辆路径规划问题(V eh icle R ou ting P rob lem,VRP)领域的研究进行综述,根据目前的研究状况对该问题进行分类;分析该问题的图模型和数学模型两大类模型各自的优缺点;分四大类讨论求解该问题的算法:精确算法(exact a lgorithm),构造启发式算法(constructive heuristic a lgorithm),改进启发式算法(im prov ing heuristic a lgorithm),和亚启发式算法(m eta-heuristic a lgorithm),评述各类算法适用的问题求解阶段以及各自的优缺点;探讨国内在VRP领域的研究成果。在此基础上,对求解该问题的方法进一步的研究方向做了展望。

面向多行程取送货车辆路径问题的混合NSGA-Ⅱ

针对多行程取送货车辆路径问题(VRP)收敛性与多样性相互制约的问题,提出一种融合自适应大邻域搜索(ALNS)算法和自适应邻域选择(ANS)的混合快速非支配排序遗传算法(NSGA-Ⅱ-ALNS-ANS)。首先,考虑初始解对算法收敛速度的影响,提出一种改进的后悔插入法以获得高质量初始解;其次,结合取送货问题特性,设计多组破坏和修复算子,以及多种邻域结构,提高算法的全局搜索能力和局部搜索能力;最后,设计基于随机采样的最佳拟合下降(BFD)算法与高效的可行解评价标准,生成路径分配方案。采用不同规模的标准公开算例进行仿真实验,与模因算法(MA)相比,所提算法的最优解质量提升了27%。实验结果表明,所提算法可快速得到满足多重约束的高质量车辆多行程路径分配方案,并在收敛性与多样性上优于对比算法。

车辆运输路径规划问题研究

为了更好地解决武警车辆运输路径规划问题,提高部队行动的迅速性,在考虑武警车辆运输实际需求的基础上,文中建立了开放式车辆路径模型,增加了诸多约束条件,例如车辆容量限制、时间窗限制等等。同时,论述了节约算法的基本原理,并采用设计改进的节约算法对开放式车辆路径问题进行了求解。通过实际案例的验证,采用改进的节约算法能够得到较满意的解,既能够满足时间限制,又能够节约运输里程和费用。结果表明,此种算法简明、易于理解,且可操作性强。

动态预约模式下车辆路径规划的实用拓展问题研究

车辆路径规划问题(VRP)是一个具有现实意义的著名问题.本文提出了一个新颖且在生活中常见的VRP拓展问题,在该问题中客户有自己的道路网络,这些道路是车辆无法行驶的,而且和正常车辆行驶的道路网络共享几种常见的节点.在这种情况下,VRP的任务就转化为一个依赖于车辆和客户方之间信息共享机制的协同运输问题.我们研究的核心目标是当上述情况发生或要满足某些客户的特殊需求时能为提供服务的公司及客户推荐一个最佳的路径规划.为此我们设计了一个改进型遗传算法,显著地优化了我们的实验结果.实验结果表明,本研究能对这个新颖的VRP拓展问题进行很好地求解.

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

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

车辆路径规划问题的逆向优化方法

在电商物流的“最后一公里”配送中,经验丰富的驾驶员(专家)并不总是基于最短路径成本矩阵进行路径规划.对此,提出一种逆向优化方法,通过学习专家的过往路径决策,得到能够代表专家经验的成本矩阵,并应用于路径规划模型求解,使得专家经验能够融入决策算法中.利用机器学习中的乘性权重更新算法实现对专家经验的学习.随机算例和电商实际算例的实验结果证明了方法的有效性.

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

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

近似动态规划求解随机需求分批配送车辆路径问题

本文针对现实生活中固体废弃物收集等需求随机的分批配送车辆路径问题,建立双层马尔科夫决策模型,使用基于动态分区的全局修正策略和基于部分重优化算法的近似动态规划进行求解。通过算例测试和分析表明模型和算法的有效性。得到以下结论:1)SDVRPSD的最优解中车辆数略高于最小期望车辆数的1.2倍,接近使用进化算法得到的最优解中的车辆数,这两者平均约相差0.6辆。2)与静态分区相比,动态分区以花费较多时间为代价,能显著提升服务范围、降低服务费用,并增加分批配送点数量。3)算法最优解与使用固定路径算法得到的初始解相比,期望服务需求量平均提高约2.6%,期望行驶费用平均降低约1.9%;分批配送点数平均多2.5个。

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

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

车辆运输路径规划问题的几点建议

车辆运输路径的规划是物流配送或者人、物运输过程中的最重要环节，这一环节的好坏将直接的影响对客户需求的响应速度，以及企业运输的成本效益。为了更好地解决车辆运输路径的规划问题，有效地提高车辆运输的迅速性与高效性，可以通过建立合理有效的路径模型等方法进行。本文笔者主要针对车辆运输路径规划的问题进行讨论，并提出相关可行性建议。

不确定需求和旅行时间下的车辆路径问题

针对一类不确定需求和旅行时间下的随机车辆路径问题,建立了一个随机规划模型,提出了一种带有自适应机制的改进遗传算法。该算法引入自适应选择机制,采用了新的交叉算子。选取两种不同规模的随机车辆调度问题,分别采用该算法和基于边重组的改进遗传算法进行求解,并通过对计算结果进行对比分析,分别针对自适应选择机制和新的交叉算子做了讨论。结果表明,所提算法不仅取得了更好的优化结果,而且具有更快的收敛速度。

带时间窗的动态车辆路径问题的局部搜索算法

为有效求解带时间窗的动态车辆路径问题,建立了该问题的数学模型,通过计划周期分片,将动态问题转换为一系列的静态子问题,采用插入法构造初始解,并将重定位法、节点交换法和2-opt*法3种线路间局部搜索方法,以及2-opt法和Or-opt法2种线路内局部搜索方法的不同组合应用于初始解的改进,分析了客户出现时间、地理位置分布与不同客户时间窗范围对线路选择的影响,比较了标准算例的求解结果。结果表明:在线路间进行局部搜索时,重定位法的效果最好,2-opt*法次之,节点交换法的最差;在线路内进行局部搜索时,2-opt法优于Or-opt法;当客户请求出现时间越早,客户比较集中,客户时间窗较宽的情况下,使用的车辆数量较少,整个线路的行驶距离较短,客户延迟时间也较短。

带时间窗的车辆路径问题的改进差分进化算法研究

研究带时间窗口的物流配送车辆路径问题(VRPTW),主要考虑车辆容量、时间窗口、最大距离等约束,且完成配送所需的车辆数目不确定,要求在车辆数目最少的条件下再使总的行驶路径最短.提出了该问题的混合整数规划模型,运用改进差分进化算法求解该问题.算法采用序数编码,设计辅助算子解决变异问题,差分进化的交叉率随进化代数自动更新.应用MATLAB语言编程进行仿真计算,得到了最优解,结果表明该算法是求解带时间窗的车辆路径问题的一种有效方法。

带时窗回程取货的车辆路径问题的算法

车辆路径问题如果考虑回程取货过程就可以在送货的过程中先后完成取货任务,比传统不考虑回程过程的问题更有实用性,基于此对传统问题进行了改进,不限制车辆的取送货顺序,而是设计了相应参数,避免了货物的重新排列·在确定目标时,综合考虑车辆运行成本、人员等待成本及服务成本等因素,实现目标解的真正可行·最后,根据此问题的特点,设计了先通过分枝定界法及遗传算法确定可行路线,再运用整数规划方法求解的算法,并以实例说明了算法的有效性·

具有同时配送和回收需求的车辆路径问题的混合遗传算法

介绍了具有同时配送和回收需求的车辆路径问题(VRPSDP),并对其进行了描述,建立了该问题的数学规划模型。结合2-opt法和等级替换策略等设计了求解VRPSDP的一种混合遗传算法,给出了该算法初始种群的两种生成规则———随机生成和构造初始种群,设计了相应的交叉和变异算子,并详细阐述了违反约束条件的处理方法。通过随机模拟试验以及与其他方法的对比分析表明:该算法可有效缩短车辆行驶距离,而构造初始种群则在一定条件下可显著提高混合遗传算法的收敛速度并改善其运行结果。

带有时间窗的车辆路径问题优化

为提高物流配送质量,在以传统的车辆配送行驶成本最小化为目标的基础上,兼顾顾客的满意度(配送及时性)和车辆数目最小化目标,建立优化的多目标带有时间窗的车辆路径问题(Ve-hicle Routeing Problem with Time Windows,VRPTW)模型.引用国际公认的车辆路径问题库中的数据作为算例,对3个目标函数都进行标幺化处理后,运用遗传算法进行求解,最终得出模型解的运算结果和时间都在理想范围之内,表明新模型是有效可行的.该模型的建立有助于有效地解决带有时间窗的车辆路径问题,不仅能够提高物流工作效率,而且能够为城市交通质量的提高提供保障.

混合蚁群算法在车辆路径问题中的应用

蚁群算法在求解车辆路径问题过程中存在搜索时间长、易于陷入局部最优解的问题。为此,设计并实现一种混合蚁群算法。引入变异算子增强算法的全局搜索能力,采用2-opt法优化阶段最优解的子路径。通过对信息素的挥发因子进行动态调整,从而有效控制信息量的变化速度。实例仿真结果表明,该算法具有较好的求解效率和寻优效果。