一种求解CVRP的动态图转换模型

带容量的车辆路径问题是组合最优化问题中的经典问题,多年以来一直被反复研究。最近,Transformer已经成为解决车辆路径问题的主流深度学习架构。然而,由于一个实例在模型不同构造步骤中会发生改变,相应的节点特征也需要更新,传统位置编码方法不适用于提取动态优化问题的位置信息。因此,现有方法在提高学习效率方面效果较差。以最小化路径长度为目标,提出一种动态图转换模型(DGTM)和动态位置编码(DPE)方法,并使用一种双重损失REINFORCE算法训练DGTM模型。此外,强化学习、图神经网络和Transformer架构相结合,提高了模型的训练效率,增强了神经网络对带约束路径问题信息的表征能力。实验结果表明,DGTM模型在此问题上的优化效果超越了目前基于深度强化学习的方法和部分传统算法,整体性能优于专业求解器的,且具有较好的泛化性能,为求解图上组合最优化问题提供了一种有效方法。

一种新的免疫克隆算法在CVRP问题中的应用

基于克隆选择学说,通过引入克隆算子提出一种新的免疫克隆算法,并将其用于求解CVRP问题.该算法采用了克隆增殖、高频变异和克隆选择算子的操作,增加了种群中优秀个体获得克隆增殖实现亲和度成熟的机会,提高抗体群分布的多样性,在深度搜索和广度寻优之间取得了平衡.仿真结果表明,该算法具有良好的全局收敛性和较快的收敛速度,能有效解决CVRP问题.

面向不同目标偏好的CVRP多目标模型及其求解方法

为了更有效地求解车辆路径问题、全方位地评估物流运输成本,提出了面向不同目标偏好的车载能力约束车辆路径问题的多目标优化模型(MOCVRPFDTP),其包括三种不同的偏好结构:装载与CVRP联合优化、绝对最小车辆数偏好及路径优化偏好。为了求解该模型,设计了算法架构及具体算法。在实验中,该模型及其求解方法对CVRP国际标准算例VRPLIB的测试结果显示了令人满意的性能,并且它更适用于实际CVRP问题的求解。

蚂蚁优化算法在解决CVRP中的应用

针对基本蚁群算法收敛性差,易于停滞的缺陷,通过引入信息素窗口限制信息素的最大最小值,只对迭代最好解进行信息素更新,判断汇聚情况进行信息素重新初始化,在每次迭代中加入局部搜索优化,在选择概率中加入与问题相关的参数等措施对蚁群进行优化,提高蚁群算法的收敛性,避免了算法的停滞现象。

求解CVRP的改进蚁群系统算法

针对基本蚁群算法在求解CVRP时收敛速度慢、求解质量不高的缺点,提出了一种改进的蚁群系统算法求解CVRP,该算法引入基于DT策略的候选列表,以提高构建路径的质量,在每次迭代中加入GIIM算子,增强局部搜索能力。实验结果表明,改进的蚁群系统算法在收敛能力和收敛速度方面都较基本蚁群算法更有优势。

数字经销平台统采共配双层拍卖机制设计

针对当前都市圈经销商因“孤立式发展、分散化建网”而导致无法满足碎片化订单、多渠道履约及高频高效配送要求等痛点,提出了一种数字经销平台统采共配双层拍卖机制。在上层机制中,考虑一家数字经销平台(卖者)与多家经销商(买者),以社会福利最大化为目标,构建了单边组合Vickery-Clarke-Groves(O-VCG)拍卖机制,实现了多物品多单元环境下的供需匹配。在下层机制中,考虑一家经销商(卖者)与多家承运商(买者),基于O-VCG拍卖机制的思想,实现了从城市集拼仓到门店、从门店到客户的两级城配运输服务采购。特别地,下层机制采用多轮O-VCG竞拍以满足多家经销商的运输需求。所提出的O-VCG拍卖机制可以实现激励相容、个体理性和配置效率。经销商构建基于需求预测及控制合理库存的上层拍卖投标策略。构建两级基于车容的城配车辆路径问题(Two-Echelon Capacity-Based Vehicle Routing Problem,2E-CVRP)近似优化算法,用于求解下层拍卖机制中基于库存限制的竞价生成问题(Bid Generation Problem,BGP)。针对双层拍卖中的胜者确定问题(Winner Determination Problem,WDP),提出有效的WDP算法。最后,基于全球最大的医药流通集团的真实数据进行数值仿真实验,结果表明:数字经销平台统采共配的双层拍卖机制可以高效分配货权及运单,合理确定批发价及城配运价,提高社会总效益,降低两级城配运输成本。

带容量约束的多车调度暂态混沌神经网络算法

带容量约束的多车调度问题是典型的NP-hard问题,利用模糊C均值聚类算法的相似性分类原理及混沌神经网络的全局搜索能力和高搜索效率,提出了一种快速且易于实现的新的混合启发式算法.该算法分为用模糊C均值聚类算法将所有客户按车容量要求装车和用暂态混沌神经网络方法对每条路线排序两个阶段.实例计算以及与其他算法比较表明,该算法是一种求解多车调度问题的可行且高效的方法.

公司班车的协同车辆路径问题

考虑员工上下班时间及早晚高峰期影响班车行驶速度等因素,建立协同车辆路径问题的数学模型。针对蚁群优化算法的缺点,结合具有快速全局搜索能力的遗传算法,并自适应地改变信息素挥发因子,采用混沌搜索产生初始种群可以加速染色体向最优解收敛,平滑机制有助于对搜索空间进行更有效的搜索,构成混合自适应蚁群优化算法。应用该算法和蚁群优化算法对该模型求解,实验证明了构造算法在收敛速度和寻优结果两方面都优于蚁群优化算法。

带运力限制车辆路径问题的简易蚁群算法实现

以求解旅行商问题的蚁群算法为基础,根据带运力限制车辆路径问题的实际应用条件,提出一种较为简易的求解带运力限制车辆路径问题的蚁群算法,并对其中的信息素更新策略进行了分析,对蚁群中的精英蚂蚁(搜索出最优解的蚂蚁个体)所经过路径的信息素进行加强,提高了算法的全局收敛性能和收敛速度,允许蚂蚁在搜索的最初阶段有较大的自由以扩大最优解的寻找空间,提出改进蚁群算法.实验结果表明,该方法能在较短的时间内达到已知最优解的1.5%误差范围.

核中心驱动混合蛙跳算法及其应用

针对混合蛙跳算法(SFLA)青蛙个体当前位置提供的惯性以及跳跃步长引起的进化速度慢,易陷入局部收敛的缺陷,将青蛙个体跳跃进化行为定义为量子力学行为,提出一种核中心驱动混合蛙跳算法(NCSFLA)。在全局寻优中,以原子核为中心的同心圆作为电子轨道构成青蛙族群;在局部寻优中,分别以跃迁步长为半径向局部最优个体跳跃,以驱动步长为半径向全局最优个体跳跃,随机产生不重复的青蛙个体分量等三种不同的局部搜索策略对族群内最差个体进行更新。以电子轨道中心即局部最优个体为跃迁的惯性指导,使得族群内的收敛更加有利于寻找局部最优解,提升搜索能力;如果陷入局部最优,则以原子核中心即全局最优个体为驱动的惯性指导,使得青蛙个体尽可能聚集在原子核中心周围,从而加快收敛速度。将该算法应用于解决容量限制车辆路径问题(CVRP),提出一种核中心驱动混合蛙跳算法的容量限制车辆路径优化算法(NCSFLA-CVRP)。实验结果显示,在单峰值、多峰值函数以及复合函数等20个测试函数上,改进后的核中心驱动混合蛙跳算法相比其他五种算法具有收敛速度快、精度高的特点。Solomon算例标准测试数据测试结果表明该方法可有效提高容量限制车辆路径的优化性能。

农村公交协同车辆路径问题的研究

针对考虑农村人口出行频次的季节偏好性、早晚高峰期班次多、乘客乘车的最长忍受时间、司机连续驾驶时间限制、车辆可以停在其他车场、车场与车场之间的车辆可以共享等因素的农村公交的协同车辆路径问题,建立车辆租赁模式的单车型开放式协同车辆路径问题的数学模型。结合节约算法、扫描算法和遗传算法,构造混合蚁群算法对实例进行仿真。首先通过扫描算法对站点进行分组,然后应用节约算法对单个旅行商问题(traveling salesman problem,TSP)求解得到可行解,最后应用混合蚁群算法对可行解进一步优化。结果表明该算法在收敛速度和寻优能力两方面都优于遗传算法。

改进遗传算法下的无水港集货路径优化研究

在出口电商企业向内地无水港进行货物集中时,考虑其交通运输过程中遇到的效率低、成本高等问题,提出了一种切实可行的解决办法,即通过车辆共享的形式,既降低了发货商的成本,也使得无水港的管理更加便捷。在对传统的集货运输模式改进后,建立以最小化所有货车总运输路程的数学模型,先使用扫描法对发货点进行分组,后使用改进的遗传算法(IGA)进行路径优化。针对不同数量的发货点以及集货车辆规模,使用IGA对模型求解并与传统遗传算法(GA)以及粒子群算法(PSO)所得结果对比。经MATLAB对小规模实验进行算例分析,得到改进后的车辆需求总数为3辆,配送总成本为5485.67元,与另外两种传统运输方式对比,证明了所述方法的优越性。

针对CVRP的2-OPT算法的时间复杂度均值分析

分析了需求不可分割带能力约束的车辆路径问题(CVRP)的 2 - OPT算法计算时间的平均复杂度。利用需求分布独立于客户的空间分布的特点 ,将车辆路径问题 (VRP)转化为多旅行商 (MTSP)问题 ,并通过分析 MTSP进行 2 -OPT操作的可行性条件 ,建立起该算法运行所需的迭代次数的分布函数 ,进而求得平均运算时间复杂度的上界。该文为有效评价针对 VRP的 2 - OPT算法 ,提供了理论依据 ,并为VRP领域的启发式算法的复杂度分析 ,提供了一种新思路。

带容量约束车辆路由问题的改进蚁群算法

提出一种带容量约束车辆路由问题(CVRPs)的改进蚁群算法.该算法使用一种新的蚂蚁位置初始化方式,增加了蚂蚁走出最优路径的可能性.在搜索过程中,以客户之间路径的节省量作为启发式信息.信息素更新采用一种动态更新的方法,能够根据当前车辆所构建路径的情况对信息素进行更新,避免算法陷入停滞状态.局部搜索除使用2-opt方法外,针对不同车辆访问的客户,还增加了交换搜索和插入搜索以扩大搜索范围.仿真实验验证了所提出算法的有效性.