考虑路段充电和时间窗的电动车取送货问题

考虑路段充电和时间窗的电动车取送货问题,以最小化车辆总旅行距离为目标,结合车辆容量约束、时间窗约束和电量约束等限制,决策一组最优的车辆线路。该问题公式化为一个混合整数线性规划模型,提出一种变邻域搜索算法求解该问题。数值算例用于验证模型的性质和算法的性能。结果表明:在小规模算例中,提出的算法只比商业求解器CPLEX差0.08%;但在大规模算例中,算法能求出高质量的可行解而CPLEX在规定时间内无法得到可行解。

模糊需求下绿色同时取送货问题与算法研究

研究绿色同时取送货车辆调度问题,提出改进的遗传禁忌搜索算法(Genetic Algorithm with Tabu Search,GA-TS)求解该问题。模型中,以服务成本、油耗成本和碳排放成本构成的总成本最小为目标,采用了综合模型计算油耗和碳排放成本,引入三角模糊数来描述客户需求的不确定性,并考虑同时取送货需求。在改进的GA-TS算法中,将惩罚因子引入适应度函数,采用结合精英策略的选择算子,提出结合禁忌搜索算法的变异算子。在案例分析中,采用田口分析法获取合理的参数设置,通过案例结果分析和算法对比分析验证模型和算法的有效性和先进性。

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

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

带时间窗取送货问题的混合算法

为解决带时间窗的取送货问题,建立了集合划分模型,设计列生成算法与启发式规则相结合的CGA混合算法进行求解.首先,放松约束构建主问题及受限主问题,运用单纯形法与分支定界进行求解;其次,建立时空网络以构建子问题,基于修正的Dijkstra's算法,设计包含算法A、B1、B2的求解算法;最后,通过启发式算法解决节点重复覆盖问题.为验证算法有效性,进一步构建了OPT近似最优解算法;并基于CGA提出三种求解策略C1、C2、C3,做单因素方差分析,采用算例分析算法的性能.实验结果表明,对于客户点数量小于30的小规模算例,CGA与OPT所得结果相近,但CGA求解效率更显著;针对客户点数量为600的大规模算例,CGA至多在20分钟内求得结果,可见本文算法的精度和效率较高.而针对不同类型及规模的客户点的单因素方差分析结果显示,C1、C2、C3在"平均行驶距离成本"、"平均车辆数"、"平均求解时间"三个维度上差异性显著,经营者可根据实际需求进行策略选择.

具有时间窗的取送货问题建模和大邻域搜索算法

针对新型物流业态中出现的路径优化问题,建立了一类具有不同起点和不同终点的带时间窗取送货问题模型.根据模型特点,设计了一类大邻域搜索算法对大规模问题进行求解.该算法引入了匹配度的概念和时差插入法,以提高搜索效率.通过设计一类与精确求解工具进行比较的方案,验证了算法的有效性.

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

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

分阶段改进大邻域搜索算法求解取送货车辆路径问题

基于带时间窗的取送货路径优化问题的现实需求和大邻域搜索算法的研究发展趋势,依据实际情况构建带时间窗的末端混合取送货路径优化模型。根据模型特性提出一种分阶段求解算法进行求解。在基于随机订单序列的重新构建阶段,引入交叉、翻转、扰动算子以提高全局搜索能力。并在解码路径重新构建阶段,设计了子路径分解算子和交叉算子,破除了局部最优的情况。通过基准实例测试及实验对比分析,证明了该算法能够快速找到有效解,所设计的算子不仅能够跳出局部最优,还能加快收敛速度,进一步证实了所提算法在解决该问题模型方面的有效性和可行性。

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

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

“卡车+无人机”模式下带时间窗的取送货车辆路径问题

无人机由于成本低、速度快、直线飞行等优势被越来越多地用于物流配送。考虑到无人机的载货量小、续航能力有限等因素,针对“卡车+无人机”模式下的带时间窗的取送货车辆路径问题进行优化,建立了以最小化运输成本为目标的混合整数规划模型。设计了自适应大邻域搜索算法对其求解。在该算法中,通过设计基于模型特点的多种高效的破坏算子和修复算子、引入模拟退火接受准则避免陷入局部最优解来提高算法性能。通过算例求解验证了模型和算法的有效性,分析了卡车与无人机联合配送模式对路径成本的影响,为“卡车+无人机”模式的路径规划提供决策依据。

基于狼群算法的同时取送货模糊绿色车辆路径问题

文章提出了带模糊需求的同时取送货绿色车辆路径问题,并将碳排放作为优化目标,建立了相应的模糊规划模型。然后给出了解决问题的狼群算法,定义了人工狼的游走行为、召唤行为、围攻行为。最后通过仿真实验,验证了该算法的有效性,并将其与其他算法进行了对比,分析了决策者主观偏好值的变化对目标值的影响。

求解带时间窗取送货问题的遗传算法

首先介绍基于时差的插入法,进而设计求解带时间窗取送货问题的遗传算法.与传统求解该问题的遗传算法相比,本算法有以下特点:一是设计了基于时差插入法的交叉算子、R1变异算子与R2变异算子;二是采用非代际搜索策略.应用56个标准测试算例测试显示,其求解质量比已有文献报道的同类算法高.

取送货路径优化问题的候鸟群自适应变邻域搜索算法

具有时间、车容量和后进先出约束的多车辆取送货路径优化问题在现实中具有广泛的应用,针对现实问题中规模性和模型的复杂性使其在短时间内无法精确求解的问题,提出了候鸟群自适应变邻域搜索算法(MBO_AVNS)。以三种贪婪插入算法构建初始种群,确保种群的多样性和初始解的质量,对传统候鸟优化算法的邻域搜索算法进行改进,加强了算法的局部搜索能力。通过真实数据进行实验分析表明,与模拟退火算法(SA)和一般自适应变邻域搜索算法相比,MBO_AVNS算法在求解具有时间和后进先出约束的取送货路径问题上更具有优越性。

带时间窗的同时取送货车辆路径问题求解算法

为了整合物流配送过程的退货与送货服务,依据实际情况建立带时间窗的同时取送货车辆路径规划模型,设计一种基于K-means聚类处理的Q-Leaning自启发式蚁群算法解决此类问题。根据配送服务的特性,在基本的K-means算法上作相应的改进,同时提高蚁群算法的局部搜索能力,完成两算法的合理衔接。选用相关文献数据和标准算例进行实验,验证所提算法具有较好的性能,可以解决所描述的此类问题。

模糊需求下低碳取送货车辆调度问题与算法

针对物流配送过程中的高碳排放问题,从低碳视角出发,构建考虑模糊需求的低碳取送货车辆调度(LCVRPPD)模型,并提出一种基于2-OPT的差分算法对问题进行求解。该算法中,采用自然数编码方式并设置三种不同的适应度函数;随后,引入2-OPT算法取代差分算法原有的变异机制,并结合二项交叉算子和贪婪选择算子,从而提高改进算法的收敛速度。案例分析中,通过田口法确定改进算法参数的合理取值,通过SPSS分析揭示了在运输成本最小、碳排放量最小和总成本最小的三种不同目标模型中,以总成本最小为目标函数的模型的解的效果最好。针对不同顾客规模的算例,改进算法与基本差分算法相比,总成本可以降低1.8%~3.0%,碳排放量可以降低0.7%~3.5%;与遗传算法相比,总成本可以降低1.9%~16.47%,碳排放量可以降低1.2%~4.3%;与粒子群优化算法相比的优化效果更加明显,总成本可以降低4.0%~22.5%,碳排放量可以降低1.56%~7.88%,验证了算法的有效性及先进性。综上,所提出的模型和算法可以为低碳取送货车辆调度问题提供参考。

基于实时信息的取送货动态车辆路径问题研究

为适应点对点、实时城市配送对动态响应和快速决策提出的新要求,研究了多种实时信息作用和影响下的取送货动态车辆路径问题.采用将动态问题转化为一系列静态问题的建模方法,建立了基于实时信息的取送货动态车辆路径模型;设计了动态算法框架,运用构造算法获得初始可行解,运用禁忌搜索算法改善初始可行解质量.实验表明,本文的模型和算法能有效解决基于实时信息的取送货动态车辆路径问题,将初始可行解的质量(实时物流配送成本)改善了34%.

多商品分批次取送货的模糊需求车辆路径问题

为解决连锁企业库存不平衡问题,本文研究了考虑多商品多批次取送货的模糊需求车辆路径问题。该问题综合考虑了多货混装、多次访问、供需未匹配、客户需求不唯一以及需求不确定等因素。本文以运营成本最小为目标,构建MCVRPSPDFD数学模型,模型利用可信测度理论应对决策环境中的不确定因素,通过改进的禁忌搜索算法进行求解。为适应模型需求和提升运算效率,算法设计了合理的初始种群形成过程及编码解码方式,并通过参数测试选取合适的参数。算例结果显示,本文成果能有效解决连锁企业库存不平衡问题,决策者偏好值的变动会对运营成本产生影响。

同时取送货车辆路径问题的改进人工鱼群算法

该文在建立同时送取货车辆路径问题数学模型基础上,针对车辆负载波动性的特点,构造相应的人工鱼群算法的四元个体模型;利用动态设置视野范围、邻域搜索方法改进人工鱼群算法的觅食和追尾操作行为,仿真算例证明改进人工鱼群算法能快速收敛得到较优解,具有较强工程应用价值。

同时取送货车辆路径问题的改进粒子群优化算法

同时取送货车辆路径问题(VRPSDP)是指车辆在服务过程中,对顾客同时进行取货和送货服务,针对这类问题,提出一种改进的粒子群优化算法。通过惯性权重的更新和路径链接更新策略有效地扩大算法的搜索空间,从而改进了算法的性能。另外,采用邻域搜索扩大策略(ENS)加快了算法的搜索速度。最后,应用所提出的改进的粒子群优化算法求解了两类同时取送货的车辆路径问题的算例。结果表明,该算法与经典的求解结果相比较,取得了比较好的计算结果,表明该算法是求解同时取送货车辆路径问题的有效工具。

多目标同时取送货车辆路径问题的改进蚁群算法

为使同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup and delivery, VRPSPD)的运输成本和各路径间最大长度差最小化,建立同时考虑车辆容量和距离约束的VRPSPD双目标模型,通过软件测试验证了模型准确性.针对问题的特点构造一个嵌入禁忌表、且具有贪婪转移准则的多目标蚁群算法,对蚂蚁产生的解执行多目标迭代局部搜索程序,以在多个邻域上优化该解或产生新的Pareto解.采用响应曲面法拟合算法参数对目标值影响的数学关系,确定最优参数组合.用该算法求得文献中12组Solomon算例的Pareto解集,并以绝对偏向最小化总成本的解与文献中仅最小化总成本的几种算法的计算结果进行比较,结果表明算法可求得权衡各目标且使单一目标近似最优的Pareto解.

超启发式分布估计算法求解带软时间窗的同时取送货车辆路径问题

本文针对带软时间窗的同时取送货车辆路径问题(VRPSPDSTW),以最小化车辆行驶总里程和最大化服务准时率为优化目标,提出一种超启发式分布估计算法(HHEDA)进行求解.全局搜索阶段,首先,提出3种启发式规则生成初始个体,以确保初始种群的质量和分散性;其次,根据问题特点,构造3个概率矩阵分别学习和积累优质解的排序信息、客户间的距离信息和捆绑信息,并通过采样概率矩阵生成新个体,以增强算法全局搜索发现解空间中优质区域的能力.局部搜索阶段,将11种邻域操作组成备选集合,进而设计学习型超启发式局部搜索(LHHLS),用于动态选择备选集合中的部分邻域操作构成多种新的有效启发式算法,以执行对解空间中优质区域的深入搜索.最后,仿真实验和算法比较验证了HHEDA的有效性.