时变单车路径问题建模及算法设计

讨论了一类时变单车配送路径优化问题。综合考虑车辆行驶速度随时间、路段不同而变化的特点,及车辆为多条路线上的客户提供服务时对车辆路径优化的影响,建立了以配送完成时间最早为优化目标的时变单车配送路径优化模型。在行驶时间满足FIFO规则下,设计了基于Inver-over操作的PSO启发式算法及满足贪婪配送策略下的动态规划精确求解算法,并讨论了增加贪婪补货策略的单车配送路径问题解与原问题解的关系。最后分别用两种算法对算例进行求解,并通过对求解优化结果及计算时间的对比分析验证了IOPSO算法的有效性。     

动态行驶时间取送一体化车辆路径问题

为优化真实路网下的车辆配送路径,采用优化 + 调整的两阶段求解方法. 在优化阶段,根据常发拥堵信息,采用遗传算法求解时变取送一体化车辆路径,安排车辆初始配送路径. 在调整阶段,以路段行驶时间为时间间隔,采用滚动更新策略调整车辆配送路线躲避偶发拥堵. 在针对车辆路径调整问题构建了一系列混合整数规划模型的基础上,设计了2-opt + insertion启发式算法求解模型,并结合Dijkstra算法求解到的客户点间最短行驶路线,将车辆配送路径转化成了真实路网中的车辆配送路线. 数值实验测试结果表明:滚动更新策略中,以路段行驶时间为时间间隔比以客户间行驶时间为时间间隔减少车辆行驶时间0.24～11.95 min;以路段行驶时间为时间间隔比以24 min为时间间隔减少车辆行驶时间0.08～8.06 min,比以6 min为时间间隔减少更新次数10.02～34.59次,因此,固定时间滚动更新策略中的最优时间间隔难以确定,其实用性较差. 2-opt + insertion启发式算法求解速度是遗传算法的4倍.      

不确定环境下的多车型物流配送路径优化

为实现在路段通行时间不确定背景下,配送企业对多种车型车辆的组合优化,使车辆资源利用、配送路径最优.通过建立总成本和配送时间最小的多目标模型、并考虑时间窗约束,设计提出多目标进化遗传算法求解该问题.本算法结合链表思想,同时为解决产生不可行解问题,在解编码时采用多染色体;并在算法中针对子染色体和母染色体分别设计交叉算子,运用擂台赛法则和改进精英保留策略构造非支配解集和加快算法的收敛速度.结果表明:相比单车型,多车型组合优化具有更高的经济效益,且随着不确定参数的变化,运输成本上升,多车型配送满载率受影响较小.     

基于随机时变路网的运输路径选择

针对运输路网中各路段上的行驶时间受交通管理、交通拥挤、天气变化等不确定性因素的影响而呈现出随机时变的特点,引入了路网评审技术中的三时估值法,建立了随机时变路网下以行驶时间最短为目标的路径优化模型,提出了车辆跨时段行驶时路段的时间依赖函数,设计了动态规划标号算法求解。算例求解优化结果的对比分析验证了模型及算法的有效性。     

求解不确定车辆数车辆调度问题的混合算法

针对不确定车辆数的车辆调度问题,建立了使用配送车辆数最少和总行驶距离最短的双目标数学规划模型.在分层序列法思想的框架内,提出一种分两阶段求解的混合算法.基于改进的粒子群算法进行车辆的分配,获得完成任务集所使用的最少车辆数,把粒子群的优化方案转化为禁忌算法的初始解进行路径的优化,以使车队完成给定的配送任务集所花费的成本最少.通过实例求解结果对算法进行了总结分析.     

蚁群算法在西餐连锁店配送路径中应用

西餐连锁店的路径优化是各连锁店食品配送路线的优化,要求满足各连锁店时间窗的约束,可抽象为带时间窗的车辆路径问题（VRPTW）.文中采用启发式算法对VRPTW求解.为正确衡量信息素和期望值浓度在进化的不同阶段对算法的贡献,引入了一种自适应转移策略来提高算法的求解效率,并通过综合考虑全局和局部信息的更新策略——蚁权策略进行信息素更新,加快算法的收敛速度.最后,通过11个经典VRPTW对该算法的性能进行了检验.并以大连市西餐连锁店为研究对象,运用本文所提出的蚁群算法求解大连市西餐连锁店的配送路线.     

带时间窗的多车型车辆路径问题研究

在以往的车辆路径问题研究中,配送中心的货车为同一车型(车辆的最大载重量和最大行驶距离相近),考虑到不同车型的货车配送费用不同,配送中心可根据需求点的需求量和距离来选择较小费用的车辆,以减小配送成本,因此求解一个时间窗的多车型车辆路径问题更具实际意义。基于此问题进行研究,建立相应的数学模型,运用改进的蚁群算法对建立的模型进行求解。最后,通过对不同车型求解结果的对比,证明建模及求解算法的有效性和选用多车型车辆配送的科学性。     

时变交通下生鲜配送电动车辆路径优化方法

依据时变交通路网特点设计基于路段划分策略的行驶时间计算方法,综合考虑客户对生鲜产品最低新鲜度约束,车载限制和电动车电量约束,设计三约束决策因子方法.以配送总成本最小为目标,构建时变交通下电动车城市生鲜配送路径优化模型,根据模型特点设计自适应改进的蚁群算法.实验结果表明,本文方法能够根据客户生鲜新鲜度要求,客户属性和路网特性,合理安排发车时间,科学规划配送路径,有效避免交通拥堵;通过算法对比,本文模型和算法能够明显降低配送成本,提高企业经济效益.     

带时间窗的甩挂运输路径优化问题研究

针对带时间窗的甩挂运输路径优化问题,考虑整车和卡车2种运输方式,以及整车、卡车、混合3种行驶路径,以行驶时间为目标函数构建模型,设计基于A、B策略的两阶段混合启发式算法.算例分析结果表明：针对客户规模在100以内的小规模算例,均可在3s内求得结果,策略B的求解时间少于策略A,而策略A的目标函数优于策略B;当客户规模逐步增至900时,选择策略A可获得更高的求解效率.可见,本文所构建的模型与算法是可行和有效的,对实际配送过程中的车辆指派与路径优化具有一定的参考价值.     

时变交通下生鲜配送电动车辆路径优化方法

依据时变交通路网特点设计基于路段划分策略的行驶时间计算方法,综合考虑客户对生鲜产品最低新鲜度约束,车载限制和电动车电量约束,设计三约束决策因子方法.以配送总成本最小为目标,构建时变交通下电动车城市生鲜配送路径优化模型,根据模型特点设计自适应改进的蚁群算法.实验结果表明,本文方法能够根据客户生鲜新鲜度要求,客户属性和路网特性,合理安排发车时间,科学规划配送路径,有效避免交通拥堵;通过算法对比,本文模型和算法能够明显降低配送成本,提高企业经济效益.     

基于共同配送的农村快递车辆调度问题

为降低农村物流成本,助力"快递下乡"工程的实施,在考虑重量、体积、订单、路径等约束条件下,以总利润最大化为目标构建基于共同配送模式的农村快递车辆调度模型;并提出采用基于随机修复非可行解策略的遗传算法求解该模型,同时在算法中引入多种群机制以提高求解的效率和效果。最后,结合实际算例对模型进行验证;设计不同订单规模的仿真算例对算法性能进行分析。研究结果表明:共同配送策略能从全局优化的角度合理配置区域内物流资源,与独立配送模式相比可降低30%的配送成本。仿真实验表明:相较于标准遗传算法,改进遗传算法能快速地搜索到更优的满意解,可以有效求解共同配送模式下的农村快递车辆调度问题。     

带时间窗的地铁配送网络路径优化问题

为应对人们日益增加的货物需求与货车进城难题,提出整合地铁网和道路交通网,形成以地铁列车和城市配送车辆为载体的地铁配送网络.考虑列车开行时间表、客户服务时间窗、城市配送车辆容量等限制条件,构建带时间窗的地铁配送网络路径优化模型,综合优化地铁列车班次的客户分配、出站点的客户分配及末端配送路径.设计随机变邻域的迭代搜索算法(ILS-RVND)进行求解,以成都市地铁3号线运输货物为例,验证了模型和算法的实用性和有效性.结果表明,地铁配送网络配送成本低,准时性高,配送车辆行驶距离短,能满足比货车单独配送更精准的服务需求.     

考虑交通拥堵及工作量平衡性的一致性车辆路径问题

为研究快递公司在提供一致性配送服务时,交通拥堵以及快递人员工作量平衡性因素对配送路径的影响,在传统车辆路径问题研究的基础上,提出了考虑拥堵和工作量的一致性车辆路径问题,并构建了混合整数规划模型。针对该模型的NP难性质,提出了基于模板路径的两阶段模拟退火算法（template-based simulated annealing heuristic,TSA）。该算法通过构建模板路径求解初始路径方案,再利用模拟退火算法优化路径方案,降低车辆总行驶时间。将该模型和算法应用于3组基准数据（benchmark data set）的数值实验,结果表明:本文模型和算法能有效解决此类问题,交通拥堵使最优配送路径的总行驶时间平均增加18.38%,使快递人员在任意两天到达同一顾客的最早与最晚时刻之差平均增加12.92%;当快递人员配件量的不平衡性平均下降35.82%后,二者仅分别平均增加2.29%和1.68%。      

一致性车辆路径问题下基于模板路径的模拟退火法

根据一致性车辆路径问题的“服务一致性”特征,本文提出了基于模板路径的 模拟退火法（TSA）以更好地求解此问题.该算法求解分为2 个阶段：第1 阶段求解模板路 径,第2 阶段以所得模板路径为参考获得各天车辆具体配送路径方案,2 个阶段均采用模 拟退火法进行优化.借助小、中规模基准数据集,文章对TSA算法进行数值实验,并将实 验结果与ConRTR算法和TTS算法的结果作比较,利用TSA法求解一致性车辆路径问题 得到的配送路径方案和“服务一致性”指标均得到优化.实验结果表明,运用TSA算法规 划车辆配送路径方案,不仅能够降低运营成本,还能提高配送服务质量.     

�������·�������ģ�ͼ����㷨

在物流活动的商品配送运输中，由于受不确定因素的干扰，对配送车辆调度的适时性造成了很大影响，从而增加了配送成本和降低了配送的服务质量。本文考虑客户对配送时间的要求和车辆行驶时间的不确定性，建立了以车辆配送总行驶距离最小化为目标的机会约束规划模型，并构造了求解该模型的单亲遗传算法，通过实例对模型求解，结果表明，该算法是很有效的。     

拉格朗日松弛启发式算法求解时空网络下的弧路径问题

为减少车辆调度成本,优化车辆运输路径,在时空网络中研究路段作业车辆的弧路径问题;考虑道路出行的时变性,利用车辆运行的时间、空间特征,构建时间-空间网络,建立弧路径问题的时空网络流模型;设计了拉格朗日松弛启发式算法,引入拉格朗日乘子松弛耦合约束,构建拉格朗日松弛问题;进一步通过拉格朗日分解,把松弛问题分解为单车最短路问题;用次梯度算法更新乘子,求解拉格朗日对偶问题,并更新原问题最优解的下界;使用启发式算法获得可行解,并更新原问题最优解的上界;用六结点运输网络和Sioux-Falls网络下的算例对算法进行实证分析。计算结果表明:六结点运输网络中6个算例的上下界间隙值等于0或接近0,Sioux-Falls网络中算例2的间隙值为0.02%,其余5个算例的间隙值等于0,均可以得到质量较高的近似最优解;在最复杂的算例(15辆车,70个任务)中,算法在可接受的时间内也得到了间隙值为0的解,找出了最优的车辆路径;随着迭代次数的增加,拉格朗日乘子会逐步收敛到固定值;当车辆容量从50增加到100时,最优解从52下降到42,说明在任务数和车辆数一定时,适当增加车容量可以降低运营成本。可见,与商业求解器相比,拉格朗日松弛启发式算法的间隙值更小,求解质量更高,可以更有效地求解弧路径问题。      

疫情期间社区商超物资配送路径优化研究

在抗击新型冠状病毒肺炎的战役中,采取"商超+社区"创新无接触配送模式对疫情影响下的社区进行物资配送,以保障居民生活物资供应。利用SOM神经网络算法与遗传算法求解车辆路径规划中的特例问题——TSP问题,以湖北省黄石港区社区物资配送路径为例,对两种算法的优化结果进行对比,发现遗传算法比SOM神经网络算法拥有更高的求解精度及效率。结果表明:优化后的路径距离为初始路径距离的37.2%,使用遗传算法可更快地搜寻到最佳的物资配送路径,得到较好的物资配送方案。     

基于拉格朗日分解的电动汽车充电路径优化

针对电动汽车充电路径优化问题,构建简单有效的车辆充电网络,考虑车辆剩余电量和充电站服务能力约束,以车辆行驶总时间最小为优化目标,建立基于多商品流的0-1整数规划模型.在拉格朗日分解框架下,构造所建模型的对偶问题,并利用次梯度算法对其求解.次梯度迭代过程中,对偶问题能够被分解为易处理的最短路径问题和半指派问题.通过应用标号算法求解最短路问题,设计有效的启发式方法求解半指派问题.仿真计算表明,求解算法能够在很短时间内达到非常小的优化间隙,验证了所提方法的可行性.     

带订单选择车辆路径问题的模型与算法

共同配送能够有效提高物流资源利用率,降低物流成本,在此环境下,本文提出了一种带订单选择的车辆路径问题.运输企业可以将运输订单委托给合作企业或者接受合作企业发布的订单,需要同时进行订单选择和车辆路径优化.针对该问题,以最大化企业经济效益为优化目标,建立混合整数规划模型.针对此NP-Hard问题设计了遗传算法进行求解,提出了对该问题染色体编码的一种精确分割算法以得到可行解的结构.本文构造了不同规模的算例,使用Matlab进行数值实验.结果表明,运输企业通过订单的双向委托,能够有效减小车辆行驶距离的同时提高企业的经济效益,为共同配送系统中的个体行为分析提供了理论基础.     

共享单车调度路径优化研究

当前共享单车停放点经常出现供需时空失衡现象,无法满足市民的出行需求,因此,单车投放机构需要进行调度以平衡城市各共享单车投放点的供应量.为保证共享单车的调度效率,需要选择合理的调度路径,针对共享单车的调度路径优化问题开展研究:以调度车辆最少和调度成本最低为目标,构建多车场有时间窗要求的共享单车调度路径优化模型;基于禁忌搜索算法,设计模型的求解算法;以某城市大区内的摩拜单车系统为例进行案例分析.结果表明:利用此模型和算法能有效减少调度成本,提高共享单车的调度效率.