超启发式遗传算法求解带软时间窗的车辆路径问题

针对车辆路径问题中传统软时间窗惩罚函数过于线性的问题,考虑客户容忍水平,提出一种折线型软时间窗,并构造出相应的惩罚函数。在此基础上,以运输配送总成本最小为目标,构造出一种带折线型软时间窗的车辆路径问题通用数学模型。同时,提出一种具有一定通用性的超启发式遗传算法,该算法以遗传算法作为上层搜索算法,以3种启发式算法——CW节约法、MJ插入法和Kilby插入法作为底层搜索规则,并通过预排序、局部搜索和全局优化来优化算法。最后,通过Solomon标准题库中的R101算例分析并验证了所提算法的可行性和有效性。

求解带软时间窗的车辆路径问题的改进遗传算法

带软时间窗的车辆路径问题 (VRPSTW)是在基本的车辆路径问题 (VRP)上增加了时间窗约束条件的一种变化形式 ,是一个典型的 NP-难问题。通过引用一种新的编码方法、交叉和变异概率的自适应机制 ,构造一个改进的遗传算法来求解 VRPSTW,并将求解结果与其他遗传算法比较。比较结果显示 。

基于改进蚁群算法求解带软时间窗的车辆路径问题

针对带软时间窗的车辆路径问题(VRPSTW),建立以配送成本为优化目标的混合整数规划模型,提出一种改进蚁群算法(IACO)求解该问题。在传统蚁群算法(ACO)的基础上,改进蚂蚁状态转移概率公式,通过自适应调整信息素挥发系数改进信息素更新策略,设计插入算子和交换算子嵌入变邻域局部搜索,并设置开始和退出局部搜索的条件,更新当前局部最优解。选取Solomon标准测试集里3类不同规模的算例,测试算法改进效果,以客户规模为100的C类算例验证所提算法求解较大规模算例的可行性,并与传统蚁群算法以及其他文献中的算例结果进行对比。实验结果表明,改进蚁群算法的寻优能力高于其他算法,求解得到的最优配送方案能够实现更低的车辆配送成本,从而验证了改进蚁群算法的有效性。

蜂群优化算法在带软时间窗的车辆路径问题中的应用

本文给出了带软时间窗的车辆路径问题的一种新的算法,蜂群算法。通过计算若干benchm ark问题,并将结果与硬时间窗的目前最好解及蚁群算法的相应解作比较与分析,验证了算法的有效性。蜂群算法是刚刚起步的智能优化算法,目前国内外关于蜂群算法的文献较少,研究范围较窄,故本文不仅是拓宽蜂群算法应用范围的有效尝试,同时也给本身求解方法不多的软时间窗车辆路径问题提供了一种新解决方法。

混合蚁群算法求解带软时间窗的车辆路径问题

针对车辆路径问题中传统硬时间窗过于刚性的问题,将软时间窗引入模型约束,建立基于总配送费用最小化的优化模型.同时,考虑到蚁群算法在求解该类问题上的不足,提出萤火虫算法与蚁群算法混合来突破原有算法的瓶颈.将萤火虫个体间的寻优过程引入蚁群算法,以指导蚂蚁搜索额外解空间,以此改善每代可行解的多样性,从而在蚂蚁信息素更新过程中进行扰动,提高算法求解质量.数值实验表明,相较于传统蚁群算法,混合算法在求解的精确性与稳健性上具有显著优势,验证了算法的可行性与有效性.

混合乌鸦算法求解带软时间窗的车辆路径问题

为求解带软时间窗的车辆路径问题,提出一种混合乌鸦搜索算法(hybrid crow search algorithm, HCSA)。设计最小惩罚成本与最小距离成本两种种群初始化规则,根据乌鸦在搜寻食物时的确定性搜索与随机性搜索两种智能搜索行为,将固定感知概率改进为可自适应调整的动态参数,引入自适应大规模邻域搜索策略,设计多种确定性与随机性邻域搜索算子。与已有文献算例结果及Solomon测试数据库进行对比,其结果表明,HCSA的优化质量优于其它文献算法,可有效求解带软时间窗的车辆路径问题。

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

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

一种改进的种群增量学习算法求解带软时间窗的车辆路径优化问题

针对求解带软时间窗车辆路径问题(Vehicle routing problem with soft time windows,VRPSTW),提出一种改进的种群增量学习算法(Improved population-based incremental learning algorithm,IPBIL)优化运输总成本。提出一种新型的3维种群增量学习模型引导算法执行全局搜索,发现解空间中的优质解区域;设计一种基于客户间距离和惩罚成本相关度的交换操作进一步提高解的质量;提出一种关于时间窗问题性质的插入和逆转操作,对优质解区域进行细致搜索。最后,通过仿真实验和算法比较,验证了该文所提出的IPBIL的有效性。

改进混合粒子群算法求解带时间窗的无人机与车辆协同路径调度问题

为提高物流配送效率,考虑时间窗、无人机换电以及无人机多点连续配送等因素,提出了一种带时间窗的车辆与无人机协同配送问题,并设计一种带局部搜索的混合粒子群算法进行求解。该算法以混合粒子群算法为核心,通过构建高效的编解码策略实现了问题解空间到算法搜索空间的转换。进一步,该算法融合单点插入策略、车辆更换策略、无人机更换策略组成局部搜索策略,以此提高算法寻优能力。实验结果表明:所提模型比纯车辆配送的模型效率更高,节省了31.51%的成本;所提算法优于四种对比算法,优化率最高达到82.08%。

多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法

针对多车场带时间窗车辆路径问题(MDVRPTW),提出一种改良自适应大邻域搜索算法(IALNS)。首先,在构造初始解阶段改进一种路径分割算法;其次,在优化阶段利用设计的移除和修复启发式算子相互竞争择优选取算子,为各算子引入评分机制,采用轮盘赌方式选取启发式算子;同时,将迭代周期分段,动态调整各周期内的算子权重信息,有效避免算法陷入局部最优;最后,采取模拟退火机制作为解的接受准则。在Cordeau规范算例上进行实验,确定IALNS的相关参数,将所提算法求解结果与该领域其他代表性研究成果对比。实验结果表明,所提算法与变邻域搜索(VNS)算法的求解误差不超过0.8%,在某些算例上甚至更优;与多相位改进的蛙跳算法相比,算法的平均耗时减少12.8%,所提算法在绝大多数算例上运行时间更短。因此,验证了所提算法是求解MDVRPTW的有效算法。

带时间窗的车辆路径问题的混合粒子群优化算法

针对带时间窗的车辆路径问题(Vehicle Routing Problems with Time Windows,VRPTW),提出了一种混合粒子群优化算法(Hybrid Particle Swarm Optimization,HPSO)进行求解。所提出的算法设计了一种高效的编解码策略,以此搭建HPSO算法解空间到VRPTW解空间的桥梁。同时为了提高算法的寻优能力,设计了由单点插入策略以及双点交换策略组成的局部搜索策略。通过solomon-50标准数据集中的九个算例进行仿真实验,实验结果证明了所提出算法的寻优能力和稳定性均优于对比算法,最优解误差相较于对比算法最多降低了38.32%。

求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析

针对伊藤算法在求解离散组合优化问题时效率较低、收敛性较差等缺陷,本文提出的改进伊藤算法引入了协同扩散过程的漂移系数,采用局部搜索能力强的爬山法确定波动系数,将漂移和波动同步进行,当找到可行解之后再进行一定程度的波动.为了验证算法的有效性,将改进后的伊藤算法用于求解带软时间窗的车辆路径问题.仿真结果表明,改进后的算法效率更高,收敛速度更快,算法稳定性和健壮性也更好.此外,本文还根据马尔科夫链移向吸引元的性质及其各状态之间的转换关系,探讨了构造伊藤随机微分方程的马尔科夫链近似模拟算法及其收敛性证明.

带软时间窗物流配送车辆路径问题的并行遗传算法

针对一般遗传算法在求解有时间窗车辆路径问题时初始种群的单一性,提出一种新的算法。该算法对不同的种群用不同的初始化方法——随机初始化法和构造初始化法,这种算法改变了过去那种种群内部的平衡。并将该算法所得结果与其他算法进行比较,表明该算法的合理性。

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

考虑软时间窗下的车辆路径问题,客户点常伴有同时取送货的双重需求。针对此类问题,通过对软时间窗、车辆在途前后时间关系及二者融合问题进行刻画,同时将车辆行驶距离、车辆使用数、违反软时间窗总时间、客户满意度等纳入综合考量,构建相应混合整数非线性规划(mixed integer nonlinear programming,MINLP)模型。设计相应多目标优化求解算法,运用理想点法对目标函数进行转化,将多目标优化问题转化为单目标优化问题。结合相应算例集,运用LINGO 17.0全局求解程序求得每组算例的全局最优解。结果表明,针对带软时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pick-up and delivery and soft time windows,VRPSPDSTW),所建模型及算法是有效且可行的。

求解带软时间窗的开放式车辆路径问题的遗传算法

通过应用交叉、变异概率的自适应机制和交叉算子A等技术,构造了一个求解带软时间窗的开放式车辆路径问题的遗传算法。用标准测试算例对算法进行测试,并将运算结果与文献中相关算法的运算结果相比较。结果表明,该算法具有较好的性能。

求解带软时间窗车辆路径问题的融合算法

设计了遗传算法与变异蚂蚁算法的一个融合算法,该算法采用优良基因保护策略,引入蚂蚁寻径变异机制,并改进了信息素的更新方式,提高了寻径速度以及寻径的全局性。经过对比实验,验证了本融合算法可以有效而快速地获得问题模型的最优解或近似最优解。

带软时间窗的两阶段连锁门店配送车辆路径问题研究

针对连锁企业配送路径优化决策问题,利用分解法进行两阶段分析,建立数学模型,并引入时间窗约束。应用最小包络聚类分析方法确定供应商与配送中心的最佳位置与数量,运用禁忌搜索算法求解配送中心到门店的最佳配送路径,算例测试验证了该方法的有效性与研究的实用价值。

基于第三方带软时间窗约束的车辆路径问题研究

在分析电商企业的"自建物流+第三方物流"配送模式的基础上,对自建物流成本和第三方物流成本分别展开研究,并在自建物流成本中设计了软时间窗惩罚函数。建立了基于第三方带软时间窗约束的车辆路径模型,设计了基于自然数序列的改进遗传算法对模型进行求解,改进交叉与变异操作来保护优秀基因,提出了种群扩张机制。最后,算例结果表明模型可以有效减少物流配送成本,提高配送效率,改进遗传算法还在提高计算时间方面有显著的成效。

带软时间窗车辆路径问题及禁忌搜索算法

考虑不同容量和运输成本的多车型车辆,建立容量限制和软时间约束,并以最小化车辆在路段上的运输量和该路段的长度乘积为目标的数学模型,给出求解该问题的禁忌搜索算法。在算法中考虑使用车辆最少的插入算法生成初始解。最后,通过仿真算例,检验模型和算法的有效性。

基于时间地理学的带时间窗车辆路径问题建模

为实现火力高效机动分配,针对带时间窗车辆路径问题,引入时间地理学的概念,在二维平面的基础上增加时间作为第三维度,建立描述移动对象时空可达性的优化模型。对导弹防御这类时敏强的作战场景通过时空棱柱进行表达和分析,形成时空路径,进而配置作战资源,协同打击时序,为指挥控制中涉及的机动作战问题提供必要的决策支撑。