一种基于匹配交叉求解最大团问题的Memetic算法

针对基于适应值的选择交叉机制在优化具有欺骗性的最大团问题中性能退化的问题,提出一种新的基于匹配交叉的Memetic算法.该算法提出交叉匹配度的概念,用来估计两个体交叉所能获得的最佳适应值.通过匹配度的计算对交叉方向的选择进行控制,保证了交叉操作以较大的概率生成新的优良模式.在40个最大团问题标准算例上的测试结果表明,新算法优于目前在最大团问题求解中性能最好的多阶段动态局部搜索算法.     

求解N-车探险问题的Memetic烟花算法

{{\baselinestretch     

开放式两级车辆路径问题建模与多起始点变邻域下降法求解

针对城市物流中普遍存在的物资开放式两级配送情形,构建了开放式两级车辆路径问题的数学模型,它要求物资必须先由远程的中心仓库配送至转运中心(第一级),再由转运中心配送至客户点(第二级),两级车辆在完成各自的配送任务后,均不必返回出发点,若要返回,则必须按照原路返回。为有效求解该NP难问题,设计了一种多起始点变邻域下降算法。扩展算例的测试结果表明,所设计的算法注重求解质量与求解效率的平衡,可有效求解提出的开放式两级车辆路径问题。     

基于Memetic算法的带时间窗车辆路径问题研究*

提出一种模拟文化进化的Memetic算法求解带时间窗的车辆路径问题。设计了一种实数编码方案,将离散的问题转为连续优化问题。采用邻域搜索帮助具备一定学习能力的个体提高寻优速度;采用禁忌搜索帮助部分个体跳出局部最优点,增强全局寻优性能。实验结果表明,该算法可以更有效地求出优化解,是带时间窗车辆路径问题的一种有效求解算法。     

求解两级定位-路径问题的粒子群算法

为求解配送网络中的两级定位-路径问题,提出一种在粒子更新过程中融入路径重连启发式搜索策略的粒子群算法。其中,根据两级定位-路径问题中解的属性,提出以中转站、路径、边为对象的三个路径重连搜索模块;同时基于搜索模块的不同组合,提出四种路径重连策略。应用不同规模算例测试结果表明,该粒子群算法能有效求解两级定位-路径问题,且路径重连策略一的求解效率较高,策略二求解的稳定性较好,策略三求解时各方面均无突出表现,策略四求解时解的质量较高。     

求解车辆路径问题的改进扰动机制的ILS算法

针对车辆路径问题,提出一种改进的迭代局部搜索(ILS)算法。该算法基于破坏再重建(Ruin and Recreate)的思想,设计了一种新的扰动机制。扰动过程包含破坏和重建两个阶段,即先使用一种兼顾随机性和相关性的破坏方法对解进行破坏,并引入扰动因子控制解的破坏强度,然后再随机选择基本贪婪插入和改进贪婪插入算法完成解的修复。利用国际标准测试案例对常规扰动机制和改进后的扰动机制进行了测试,并与量子进化算法、蜂群算法进行了比较,实验结果表明改进后的ILS算法更加有效。     

用于求解混合车辆路径问题的混合进化算法

文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的。给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点;规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次。MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小。混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法。该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛。在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的。     

求解车辆路径问题的一种混合方法

提出一种求解带软时间窗车辆路径问题的混合算法。采用蚁群系统算法产生阶段最优解,以此作为粒子模板,随机生成粒子群,利用粒子群算法在阶段最优解基础上进一步优化。且在蚁群系统算法中,当容量超过限制后,从剩余的客户里选择需求量最大的作为新的起点继续探索路径,直到所有客户都被访问一遍。实验表明,该混合算法是解决带软时间窗车辆路径问题的一个有效算法。     

车辆路径问题的离散细菌菌落算法

为了丰富解决车辆路径优化问题的方式,提出一种融入了局部搜索的离散型细菌菌落优化算法。首先设计了算法的个体编码方式和进化模式;然后融入局部搜索方式来加速算法寻优的效率;最后将该算法应用于带时间窗的车辆路径问题,并采用solomon数据验证,通过与其他算法进行比较,验证算法的可行性。     

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

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

需求可拆分车辆路径问题的禁忌搜索算法

为解决实际配送运输中的车辆路径问题（Vehicle Routing Problem,VRP）,通过改进传统的数学模型,解除每个客户需求只能由l辆车配送的约束,建立改进的可拆分车辆路径问题（Split Delivery VRP,SDVRP）数学模型,并利用禁忌搜索算法（Taboo Search Algorithm,TSA）进行求解．在TSA的设计中,根据SDVRP模型的特点对初始解、邻域搜索和解的评价等进行特殊处理．算例表明,该模型不仅可以解决VRP模型中不允许配送点需求量超出装载量的限制,而且通过相应配送点需求量的拆分和重新组合,可节省车辆数目、缩短路线长度、提高车辆装载率．     

需求可拆分车辆路径问题的聚类求解算法

针对传统的车辆路径问题通常假设客户的需求不能拆分,即客户的需求由一辆车满足,而实际上通过需求的拆分可使需要的车辆数更少,从而降低配送成本的问题,分析了需求可拆分的车辆路径问题的解的特征,证明了客户需求不宜拆分应满足的条件,设计了符合解的特征的聚类算法,并对其求解.通过实验仿真,将所提出的聚类算法与蚁群算法和禁忌搜索算法进行比较,所得结果表明了所提出的算法可以更有效地求得需求可拆分车辆路径问题的优化解,是解决需求可拆分车辆路径问题的有效方法.     

基于免疫Memetic算法的网络组播路由优化

为了求得代价最小的网络组播路径,提出了一种基于免疫Memetic算法的优化求解方法。算法充分结合免疫全局搜索和局部搜索机制,设计了适合组播路由问题的各种免疫算子,加快了算法的收敛速度。实验结果表明,该算法在无需备选路径集的情况下,可以较快地找到最优路径,并且算法更加简单。     

带时间窗车辆路径问题的文化基因算法

针对物流配送中带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）,建立了数学模型,并设计了求解VRPTW的文化基因算法。种群搜索采用遗传算法的进化模式,局部搜索采用禁忌搜索机制,并结合可行邻域结构避免对不可行解的搜索,以提高搜索效率。与单纯的遗传算法和禁忌搜索算法进行对比实验,表明该算法是求解VRPTW的一种有效方法。     

车辆路径问题的双重进化蜂群算法求解研究

针对传统人工蜂群算法局部搜索的低效性,提出了双重进化人工蜂群算法。在需要两点进行操作的搜索过程中,采用一点随机选取,另一点通过遍历可行解,以其中最优解确定位置的半随机式搜索策略。用该策略改进插入点算子和逆转序列算子,分别在两对以及三对城市间距离之和的解空间维度上交叉搜索,并应用到局部搜索中构成双重进化过程,提高了搜索效率和适应值引导性。实验结果表明,该算法较已有方法提高了收敛速度,优化了目标解,并可通过合理设置终止阈值提高时效性。     

求解需求可拆分车辆路径问题的改进的金字塔演化策略

为了更加合理地求解需求可拆分的车辆路径问题（SDVRP）,克服传统先路径后优化两阶段的求解方法容易陷入局部最优的缺点,以及解决智能优化算法在优化阶段未能将竞争与协作有机地融合为一体的问题,以配送路径最短和配送车辆最少为优化目标,提出了一种改进的金字塔演化策略（IPES）。首先,以金字塔为基础,提出了求解SDVRP的编码、解码方式以及层级间的协作策略;其次,根据遗传算法的随机、“适者生存”的高度并行、自适应等特点,以及金字塔结构各层分工不同,设计了一种适合SDVRP的自适应邻域算子,使得算法能够快速收敛到最优;最后,得到最优解。相较于分段求解算法、聚类算法、粒子群算法、人工蜂群算法、禁忌搜索算法,四个仿真实验的结果表明,在求解各案例的最优路径时,所提IPES的求解精度分别至少提升了0.92%、0.35%、3.07%、9.40%,验证了在求解SDVRP时,IPES具有良好的性能。     

An improved hybrid firefly algorithm for capacitated vehicle routing problem

Firefly algorithm (FA) is a new meta-heuristic which is successfully applied to solve several optimization problems. However, it suffers from a drawback of easily getting stuck at local optima. This paper proposes a new hybrid FA, called CVRP-FA, to solve capacitated vehicle routing problem. In CVRP-FA, FA is integrated with two types of local search and genetic operators to enhance the solution’s quality and accelerate the convergence. The experiments are conducted over 82 benchmark instances. The results demonstrate that CVRP-FA has fast convergence rate and high computational accuracy. It significantly outperforms the other state-of-the-art FA variants in majority of the tested instances.     

多车场满载车辆路径优化算法

针对多车场满载车辆路径问题(MDVRPFL),结合节约法提出了一种依次对车场、配送中心、用户进行循环调整直到最优的迭代算法.该算法具有使总费用随迭代次数逐渐降低的特点,其运算结果能同时得到最优车辆分配方案和车辆行驶路径.最后用该算法对不同规模的算例进行试验.试验结果表明,该算法对多车场车辆路径问题有效适用.