异构车队多中心交付的低碳车辆路径问题与算法

针对前置仓配送模式面临的“一地多仓、末端交叉、高成本、高排放”难题,提出异构车队多中心横向协同配送模型。通过引入考虑速度、时间、距离、载重和发动机等因素的异构车队综合碳排放函数,将碳排放成本、司机成本和派车成本通过线性加权方式转换为目标函数;设计含特殊头部结构和染色体编码机制的改进遗传算法,引入交叉算子和动态权重调整机制以实现解空间的高效搜索。研究结果表明:相比传统前置仓横向转移补货调度,异构车队多中心横向协同补货调度在总成本方面减少39.1%,CO_(2)排放量减少12.5%,车辆使用数节约27.2%;随着协同客户占总客户的比例增加,总成本进一步减少;相较碳排放成本、派车成本,司机成本在总成本中占较大比例,需引起物流企业重视。

一类特殊车辆路径问题(VRP)

描述了一类特殊的车辆路径问题 (VRP) -混合车队车辆路径问题·在分析问题特性的基础上 ,通过引入“车队模式”定义 ,提出了求解框架 ,设计了基于遗传算法和禁忌搜索启发式的混合算法·针对其中的混合车队车辆路径问题 ,所设计混合算法 ,利用了GA搜索全局性好 ,TS局部爬山能力强的特点·提出的车队、任务分段组合编码和解码规则充分考虑了混合车队车辆路径问题的特点·实例计算结果表明了框架。

多车型集配货一体化车辆路径问题研究

针对客户存在收货和发货双重需求的物流配送问题,讨论具有多种车型的集配货一体化车辆路径问题。在综合考虑各车型的固定成本和可变配送成本的前提下,以总成本最小为目标,以尽可能提高车辆满载率、减少出行次数为思路,构建多车型集配货一体化车辆路径优化模型。基于最小插入费用法设计初始可行解生成算法,通过引入基于概率的多算子邻域操作、最优解记忆装置、多准则终止原则对模拟退火算法进行改进,给出求解思路。设计算例并对多车型单/双向集配货模型的求解结果进行比较,以验证模型的实用性和算法的有效性。研究结果表明:使用改进后的模拟退火算法对构建的多车型集配货一体化车辆路径问题模型求解更直接简便,对多车型集配货一体化车辆路径优化后能有效降低配送成本。

带有异质固定车队的能力约束弧路径问题

研究了带有异质固定车队的能力约束弧路径问题(CARP).为了在可接受时间里求得较理想的解,提出了基于Route-First,Cluster-Second思想的两阶段启发式算法,并使用局域搜索(LS)和加强的局域搜索(ELS)进行改善.基于标准CARP算例生成了HFFCARP测试数据,算法结果表明了LS和ELS的有效性,且ELS具有更好的效果.

带碳排放约束的异型车辆路径问题及其禁忌搜索算法

回顾物流运输中的碳排放和异型车辆路径问题研究状况,阐述带碳排放的异型车辆路径问题(HVRPCE),并建立HVRPCE问题的数学模型。应用基于最佳插入和交换的混合邻域禁忌搜索算法求解HVRPCE问题,对Taillard标准算例给予碳排放约束以进行HVRPCE测试,其中异型车辆的碳排放系数根据其燃料消耗确定。采用小型车优先的策略来产生初始解,并提出一种混合邻域结构。与文献中已有的结果相比较,结果显示:混合邻域禁忌搜索算法能使得HVRPCE问题在车辆行驶成本和碳排放两方面有较大的下降,而企业不仅能在低碳物流方面成功,还能增加效益。

结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题

针对带时间窗的低能耗多车场多车型车辆路径问题(Low-energy-consumption multi-depots heterogeneousfleet vehicle routing problem with time windows,LMHFVPR_TW),提出一种结合聚类分解策略的增强蚁群算法(Enhanced ant colony optimization based on clustering decomposition,EACO_CD)进行求解.首先,由于该问题具有强约束、大规模和NP-Hard等复杂性,为有效控制问题的求解规模并合理引导算法在优质解区域搜索,根据问题特点设计两种基于K-means的聚类策略,将LMHFVPR_TW合理分解为一系列带时间窗的低能耗单车场单车型车辆路径子问题(Low-energy-consumption vehicle routing problem with time windows,LVRP_TW);其次,本文提出一种增强蚁群算法(Enhanced ant colony optimization,EACO)求解分解后的各子问题(LVRP_TW),进而获得原问题的解.EACO不仅引入信息素挥发系数控制因子进一步动态调节信息素挥发系数,从而有效控制信息素的挥发以提高算法的全局搜索能力,而且设计基于4种变邻域操作的两阶段变邻域局部搜索(Two-stage variable neighborhood search,TVNS)来增强算法的局部搜索能力.最后,在不同规模问题上的仿真和对比实验验证了所提EACO_CD的有效性.

车辆数限制的多车型校车路径问题模型及算法研究

为适应校车路径规划中校车有多种车型且每种车型数量受限的需求,建立车辆数限制的多车型校车路径问题(HFSBRP)的数学模型,并提出一种迭代局部搜索算法进行求解。该算法借助邻域随机选择的变邻域下降搜索(VND)算法完成局部提升。局部提升过程中,首先调整车型,然后再混合使用缩减路径数和提高车辆利用率的邻域解接受策略以提高算法的寻优能力,为保证解的多样性,允许接受一定偏差范围内的邻域解。此外,为避免算法过早陷入局部最优,设计了多点交换和移动的扰动规则。基于国际基准测试案例进行模型验证和算法测试,实验结果表明了模型的正确性和算法的有效性。

基于标签算法的异车型混合集送多属性车辆路径问题研究

文章对异车型混合集送的辆路径问题(Vehicle Routing Problem with heterogeneous fleet,backhaul and mixed-load,VRPHBM)进行研究,提出了一种基于多属性标签的蚁群系统算法(Multi-Label based Ant Colony System简称MLACS)。该算法利用面向对象理念,分别对客户、车辆及其行驶路径构建多属性标签,再通过蚁群算法的搜索规则对客户和车辆标签进行匹配,从而得出满意的车辆行驶路径。通过Solomon标准及其扩展算例和实际案例的验证表明,MLACS具有快速、灵活和稳定等特点,能够很好地解决VRPTW、VRPHBM以及多限制条件的实际应用问题。与本文列出的研究同类型问题文献的其他几种算法相比,MLACS算法在运算时间以及计算结果上明显具有优势,是求解该类问题的有效算法。

煤矿物资多车型配送的改进遗传算法求解

首先根据郑州煤电物资供销有限公司的实际情况建立单车场多车型车辆路径问题的模型,在此模型的基础上,用本文提出的改进遗传算法(IGA)对其求解,最后通过和传统的启发式算法(CHA)、扫描法(SA)的求解从配送费用、配送车辆数和运算时间上进行了综合比较,得出IGA算法求得的总运输费用最低,SA算法次之,CHA算法最高;但从所需参与配送的车辆数目来看,CHA求得的最好解所需的车辆数最少,其次是SA,IGA最多;在平均计算时间上,CHA的优势最明显,仅为SA的,IGA的。

基于密度聚类构建物流配送问题的毁灭移除算法

研究多车型大规模物流配送问题,针对企业配送门店规模大且聚集的特点,在自适应大规模邻域搜索(ALNS)框架下提出一种新的邻域映射方式:基于密度聚类的毁灭移除算法。ALNS包含毁灭与重建两个阶段,通过不断对当前解进行破坏和重建得到更好解。在毁灭阶段,随机选择一条路线进行密度聚类得到簇集合,然后按簇对路线上的门店进行移除;重建阶段随机选择贪婪插入法或Regret-2插入法将移除的门店插入到合适的路线上得到新配送方案。通过国际基准测试案例验证了所提算法的有效性,与已有算法对比,基于密度聚类的毁灭移除算法的ALNS算法求解结果比案例已知最优解平均误差更低,求解质量更优;应用于实际场景中,该算法能在有限时间内求得较好的配送方案。

带时间窗的混和车辆路径问题的优化算法研究

文章针对带时间窗约束的混合车辆路径问题的特点,建立了带时间窗的混合车辆路径问题的数学模型,并设计了变邻域禁忌搜索算法对该问题进行求解。通过标准算例测试及与现有文献计算结果的比较,验证了该算法的有效性。

基于改进禁忌搜索算法的车辆路径问题模型

为了解决传统禁忌搜索算法程序复杂、独立性低下等问题,在考虑带有时间窗的车辆路径问题的基础上,提出了带有时间窗和异构车队的车辆路径问题。为了更好地解决带有时间窗和异构车队的车辆路径问题,建立了带有时间窗和异构车队的车辆路径问题的模型,此模型同时考虑了时间窗、异构车队以及车辆数量限制的多重属性,提出一种改进的禁忌搜索算法来解决这一问题,改进的禁忌搜索算法其实质是在原有禁忌搜索算法的基础上加入了保留表,等级成本结构原则和车辆排序准则对其进行了创新。通过在原有算法中加入保留表,并使用等级成本结构的原则,提出了一种新的解决车辆路径问题的算法,这种改进的禁忌搜索算法解决了传统禁忌搜索算法的弊端,不仅可以使用户点在路径上紧密排列,同时还能达到优化运输路线的目的。最后为了演算改进的禁忌搜索算法的有效性,使用具体的案例数据对改进的禁忌搜索算法进行了演算,演算结果证明了这种创新算法在解决带有时间窗和异构车队的车辆路径问题上是有效的。

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

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

基于混合蚁群算法的异质车队低碳VRP研究

针对货运车辆在配送调度过程中产生大量碳排放的问题,建立模型将多种影响碳排放量的因素协同优化。模型中考虑了不同载重量的异质车队,两个节点之间有多条道路的柔性路径,以及车辆重量随卸货而减少的动态负载等因素,以碳排放量、行驶时间和行驶路程为优化目标,并加入了节点需求时间窗、根据速度变化划分路段、交接和卸货时间的约束。提出了一种混合蚁群算法,利用蚁群算法信息素强度更新方式保持群体记忆性,利用粒子群算法的快速收敛特性增加计算效率。通过随机数值算例的仿真优化与对比分析,验证了算法和模型的有效性。

混合变邻域搜索算法求解大规模电动车辆路径优化问题

基于真实的物流场景,研究了带时间窗的多车型和多循环电动车辆路径问题。建立了一个基于路径的混合整数线性规划模型,可精确求解小规模算例。提出了将变邻域搜索算法和标签算法相结合的混合启发式算法,用以求解大规模情形。该算法提出了一种带随机因子的启发式算法构造初始解,并对时间窗和里程约束进行了松弛,使用邻域算子进行变邻域搜索,使用标签算法精确求解了固定商户配送顺序下的路径最优充电决策问题。测试结果表明:混合变邻域搜索算法可在极短时间内找到最优解,能大幅度降低物流成本。

线性充电策略下多车型电动车辆路径模型研究

针对现实物流配送场景下使用多种具有不同载重、不同续航里程和不同购置成本的电动车队进行物流配送的问题,研究了线性可变充电策略下的多车型电动车辆路径问题。提出了基于路径的混合整数线性模型。列举了任意非充电节点之间所有车型访问的路径,通过负载约束、时间窗约束剔除不可行的路径,通过占优准则剔除被占优的路径。与传统的基于充电站副本的模型相比,该模型不再需要设置充电站副本个数。通过对该模型在不同规模下的公共算例进行仿真实验,结果表明,该模型在求解质量与求解速度方面优于其他模型,验证了模型的有效性。

集货需求模糊的异型车同时配集货路径优化

针对集货需求模糊的异型车同时配集货车辆路径问题(HFVRPSDDFP),基于先预优化再重优化的思路构建模型.预优化阶段根据可信度理论和车型选取方法为客户点分配车辆,生成配送方案.重优化阶段利用随机模拟算法(SSA)确定客户集货需求,对服务失败的客户点,制定服务策略,将模糊问题转化为确定型的异型车辆路径问题(HFVRP),并规划路径.设计遗传变邻域算法,通过测试确定邻域结构构造,将自适应搜索策略应用到邻域搜索过程中,保证迭代前期收敛速度和后期全局搜索能力.通过算例验证了本文模型及算法的有效性.

绿色VRP的增强拉格朗日松弛启发式算法

针对绿色多车型车辆路径问题(GHFVRP),建立了以最小化车辆固定成本、行驶成本及碳排放成本之和为优化目标的混合整数规划模型(MIP),并提出一种增强拉格朗日松弛启发式算法(ELRHA)进行求解。首先,通过松弛难约束构造对偶问题,并分解为两个子问题,再采用次梯度法更新拉格朗日乘子,求解两个子问题获得原问题的下界;其次,设计一种两阶段启发式算法对下界进行修复及优化,以获得较好可行解并更新问题上界;最后进行仿真实验,实验结果表明:在相同实验环境下对17个算例进行20次测试,ELRHA平均求解间隙为4.49%,相较Gurobi提升3.28%,同时与其它算法对比进一步验证了ELRHA能求解问题高质量上界。可见,ELRHA能有效求解GHFVRP。

基于城市道路限行的多能源多车型车辆路径优化

针对日益严峻的城市汽车尾气污染问题和日趋严格的城市限行措施,本文首次将城市分区域、分车型等限行因素引入到车辆路径问题,并以碳排放、运输等费用总成本最小为目标,构建了基于城市道路限行的多能源多车型混合车辆路径优化模型.针对模型的NP难特性,本文提出了一种变邻域搜索算法(VNS-TR)求解该模型.最后,通过算例和基准测试集验证了模型及算法的有效性.

基于两阶段算法的需求可拆分多车型车辆路径问题

需求可拆分车辆路径问题(SDVRP)属于车辆路径问题(VRP)的变种问题,SDVRP模型松弛了客户服务次数和允许客户需求超过车辆装载能力,能提高车辆装载率和降低车辆成本。SDVRP模型都基于相同车型的假设,这不符合实际物流配送中使用不同车型的情况;且较少分析客户需求拆分阈值对问题解的影响;此外,SDVRP研究较少应用新型仿生搜索算法。因此,本文以多车型和需求拆分阈值为新约束,建立需求可拆分的多车型车辆路径问题(SDHFVRP)混合整数规划模型;提出以路径优化和路径改进相结合的两阶段算法(TPA)。最后以华北分公司大牛地气田物流系统中的污水回收路径规划为例,重新规划了大牛地气田污水回收的车辆行驶路线,并与大牛地实际回收方案对比,模拟结果有效地减少了车辆使用数目和运输成本。