基于改进K-means聚类和遗传算法的混合算法求解异构车辆路径问题

由于目前单一车型配送存在资源浪费和效率低下等问题,选取确定数量的不同车型对各客户点进行配送服务往往可以得到更优的配送路径方案。针对这一点,描述了一种异构车辆路径问题,并建立了具有固定车辆数且考虑固定成本、可变成本以及时间窗惩罚成本的混合整数规划模型。同时,提出了一种基于改进K-means聚类和遗传算法的混合算法对模型进行求解。实验仿真先求解不考虑时间窗的问题初步证明混合算法的有效性,再在带时间窗的问题中求解不同规模算例的单一及异构车型结果,以证明异构车型配送更优。最后,对该混合算法的求解结果与其他混合算法的求解结果进行对比分析,证明了混合算法的优越性。研究结果表明:该混合算法求解的异构车型结果优于单一车型,并且比其他混合算法求解的异构车型结果更优,异构车辆配送使用的配送车辆数更少,总成本也更低,该混合算法具有更好的效率和性能。

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

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

考虑碳排放的危险品运输异构车辆路径问题研究

为满足危险品运输异构车辆路径问题(HVRP)的低碳需求,对易爆危险品运输过程中的总风险、总成本和总碳排放量进行最优化处理。首先,在模型构造阶段,改进总成本与总风险的度量方式,包括建立爆炸事故场景下考虑危险品装载量的风险量化模型,并设计一种用于惩罚成本计算的软时间窗函数,该函数可以优先减少装载量较大的车辆在客户处的等待时间;然后,在算法改良阶段从2方面改进非支配排序遗传算法(NSGA-Ⅱ),设计一种带有改良交叉算子的混合交叉方法来提升全局搜索效率,并通过包含2个阶段的变邻域搜索(VNS)算法来提高局部搜索能力;最后,通过算例验证模型和算法的有效性。研究结果表明:相较于原始NSGA-Ⅱ,改进的算法收敛曲线下降更快,使总成本、总风险和总碳排放量3个优化目标的平均值进一步减少3.36%、12.16%和6.96%;在车辆数目有限的车队中,承运人可以通过选择不同的车辆类型对各目标产生不同程度的影响。

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

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

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

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

离散灰狼优化算法求解VRPSPDTW问题

本文针对带时间窗约束的同时送取货车辆路径问题,建立了以总配送距离最小化为目标的数学模型.根据模型的特征,在保留灰狼算法(GWO)搜索机制的基础上,提出了离散灰狼优化算法(DGWO)进行求解.采用多种策略构建种群的初始解,并允许出现不可行解,扩大种群的搜索区域;引入带评分策略的邻域搜索策略,调整每种算子的概率,使算法选择优化效果更好的算子;使用移除-插入机制,对优质解区域进行探索,加速种群的收敛.在仿真实验中对标准数据集进行了测试,将实验结果和p-SA算法、DCS算法、VNS-BSTS算法和SA-ALNS算法进行了对比,实验表明DGWO算法能有效地解决带时间窗约束的同时送取货车辆路径问题.

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

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

基于环境成本与经济成本兼顾视角的GVRPTW-MDHV研究

文章针对绿色物流中多车场多车型带时间窗的车辆路径问题(Green Vehicle Routing Problem with Time Windows for Multi-depot and Heterogeneous Vehicles, GVRPTW-MDHV),考虑实时载重对车辆油耗和碳排放的影响,引入综合排放模型(Comprehensive Modal Emission Model, CMEM)对车辆油耗和碳排放进行度量,最终以车辆油耗成本、碳排放成本、固定发车费用、车辆租用费用、车辆人力成本和时间窗惩罚成本之和最小化为优化目标,构建了GVRPTW-MDHV数学模型,并根据模型特点设计改进差分进化算法。算例仿真结果表明,构建的模型和提出的算法能够为不同车场合理调配不同型号车辆,有助于科学规划车辆路径,有效减少油耗量和碳排放量,降低总配送成本。

基于单车场多车型车辆路径问题的混合求解算法

为降低华北石油局大牛地气田采气过程中的车辆运输成本和车辆碳排放量,建立了单车场多车型车辆路径问题(SHVRP)数学模型,将扫描法、插入法、邻近法、两阶段法、遗传算法和蚁群算法等启发式算法作为求解SHVRP模型的基本算法,在分析算法原理、性能和适用环境等差异的基础上,提出了3种混合算法:混合启发式算法HHA(两阶段法+最远插入法+2-OPT)、混合遗传算法HGA(最邻近法+2-OPT+遗传算法)以及混合蚁群算法HACO(遗传算法+蚁群算法)。进而,列出了HA、HHA、GA、HGA、ACO、HACO等6种算法求解同一算例的10次运行结果的平均值,混合后算法的运行结果对比混合前算法的优势说明了混合算法的优越性。综合总配送成本、总碳排放量、配送车辆数和首次搜索到最优解的迭代数及计算时间等对3种混合算法进行比较,得出HACO最优,HGA次之,HHA最差。最后,将基于混合算法的智能运输方案与大牛地气田现有的基于经验法则的运输模式作对比,进一步说明了所提混合算法的可行性和有效性。

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

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

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

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

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

回顾物流运输中的碳排放和异型车辆路径问题研究状况,阐述带碳排放的异型车辆路径问题(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的有效性.

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

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

关联运输调度问题带遗传算子的自适应蚁群算法

考虑实际生活中商品供应商具有严格的营业时间限制、客户的个性化送货时间预设以及道路路况影响运输成本等因素,建立带多种约束的关联运输调度问题模型。通过聚类算法和节约算法构造初始解,提高求解速度;自适应地改变启发式因子和期望启发式因子,提高算法收敛速度;引入遗传操作算子,自适应改变交叉概率和变异概率,提高算法的全局搜索能力;提取核心路径便于进行后期优化;通过3-opt与车场交换,提高算法的局部搜索能力。基于以上方法构造带遗传算子的自适应蚁群算法,对40客户规模的实例进行仿真,结果表明提出的IVRP优于VRP,该算法在收敛速度和寻优结果两方面略优于自适应遗传算法和自适应蚁群算法,且其稳定性良好。

多车型开放式车辆路线问题的混合启发式算法

多车型开放式车辆路线问题,是物流配送优化中不可缺少的环节。针对标准遗传算法存在收敛速度慢,局部搜索能力差,易早熟的缺点,采用混合启发式算法进行优化求解。采用实数序列编码,使问题变得更简洁;有针对性地构建初始解,提高了解的可行性;用基于排序的选择与最佳保留相结合策略,保证群体的多样性;引入部分算术交叉算子,加强染色体的全局搜索能力;利用模拟退火算法的Boltzmann机制,控制遗传算法的交叉、变异操作,提高了算法的收敛速度和搜索效率。仿真结果表明混合启发式算法在求解质量和计算效率上好于标准遗传算法。

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

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

考虑循环取货装车堆码的一种车辆路径问题研究

研究了某制造企业循环取货物流路径优化问题,根据弱异性小尺寸货物装车堆码特点,在装箱约束处理中通过"砌墙法"的有效简化处理,得到车辆容积和装车长度双容量约束的新型车辆路径问题模型,区别于已有带装箱约束的车辆路径问题.将不同货物作为单独的节点来处理,解决了通常需要需求可拆分路径问题才能解决的、节点需求量大于车辆容量的难题.运用遗传算法求解,松弛双容量的难约束,对该问题实际数据算例求得最终路径-装车结果.从结果解析、"砌墙"误差分析、相关问题比较和应用条件等方面验证了问题模型物流应用的可靠性和可行性.

易腐货物配送中时变车辆路径问题的优化算法

以易腐货物配送中的时变车辆路径问题为研究对象.由于时变车辆路径问题中每条道路上的车辆行驶速度随时间变化,此类问题难以用传统的数学建模方法进行建模及实现优化求解.因此,提出应用计算机建模的方法建立此类时变车辆路径问题的仿真模型.在此基础上,设计并集成遗传算法于计算机仿真模型用于搜索问题的最优解,所提出的自适应性优化算法能够根据来自车辆驾驶员回传的实时数据动态调整后续的最优行驶路线.最后,在多智能体建模与仿真平台上实现了该算法,并以15个顾客的时变车辆路径问题为例验证了算法的有效性.