求解软时间窗车辆路径问题的一种新方法

车辆路径问题属于组合优化领域中的NP–Hard问题.针对带软时间窗的车辆路径问题,提出了一种区域划分—路径优化的数学模型.首先结合最小支撑树算法能产生全局最优解的优点,将客户划分为若干个子区域.然后再结合贪婪算法简单迅速的特点,对每个子区域中的路径进行优化.实验结果表明,该算法收敛速度快、搜索成功率高.     

约束最小支撑树问题

主要研究两类约束最小支撑树问题,即点约束和边约束最小支撑树问题.点约束最小支撑树问题主要研究了点v不是叶子和点v是叶子两个具体约束问题,边约束最小支撑树问题的约束条件分别为包含给定边e0和不包含给定边e0,对上述问题分别给出了一些基本定理和算法.     

改进的生成树算法求解旅行商问题

给出了一种基于最小生成树的TSP求解算法,该算法结合贪心算法和匹配算法,把传统近似算法的局部最优转化为全局最优,避免了最邻近算法中最后几步产生的较大的误差.文章最后分析了算法的复杂性,实验数据表明该算法有较高的有效性.     

最小支撑树的三种算法

最小生成树问题是网络优化中一个常见的问题,本文介绍了避圈法（kruskal）和破圈法等求解方法。     

最小支撑树的新算法

从树的等价定义出发,叙述并证明了一种不必考虑圈的求最小支撑树的算法.     

交通网络k-短路径与最小支撑树问题

为了给交通管理部门提供多个路径诱导信息,基于经典的最短路径算法——Dijkstra算法,研究了赋权交通网络的k-短路径问题。k-短路径问题是在网络G中求出给定起讫点对之间的k条路径P1,P2,…,Pk,满足W(P1)≤W(P2)≤…≤W(Pk),其中W(*)表示路径*的权值。在网络G的基础上,通过对G的点、边重新划分以及对边上的权值重新赋值,构造出了1个新的网络G′并讨论了它的几个性质。从而将G的k-短路径问题转换为求解G′的最小支撑树问题,进一步,最小支撑树问题又等价于求G′中一条边的权值。研究结果表明:由于最小支撑树问题具有多项式算法,得到关于k-短路径问题的多项式算法,其时间复杂性为O(k(m+nlg(n))),m和n为G的边数和顶点数。最后通过算例给出了算法的具体执行过程,同时验证了其可行性。     

基于客户满意度的车辆路径问题的混合蝙蝠算法

车辆路径问题对现实有着良好的指导意义,自提出以来便吸引了企业界和学术界的广泛关注。然而,传统车辆路径问题仅仅将车辆行驶里程最短作为目标,忽视良好的客户体验对于企业的重要性。考虑客户满意度这一目标,建立以客户满意度和车辆行驶里程最短为目标的多目标优化模型,根据车辆路径问题的具体特征,改变基本蝙蝠算法的编码方式。为克服基本蝙蝠算法求解精度低、易陷入局部最优的缺陷,加入贪婪随机自适应启发式算法提高求解精度,引入病毒进化机制以增强蝙蝠算法跳出局部最优的能力。算例分析表明:病毒进化混合蝙蝠算法相比于基本蝙蝠算法,在求解精度上有较大幅度提高,是一种有效求解车辆路径问题的方法。     

最小支撑树的一种删除大权边算法及应用

最小支撑树的一种删除大权边算法是在Kruskal算法、Prim算法和破圈法的基础上,提出的另一种算法。介绍了删除大权边算法的基本概念和性质,列举了删除大权边算法的计算实例,叙述了删除大权边算法的及其应用。     

求解运筹学最小支撑树模型的一种新算法

为了简化对运筹学中最小支撑树模型编写简单计算机程序来实现求解,设计了一种新的简便算法----"节点列表判定法"。该算法是用节点来表述网络图的边,并从节点列表中找到了构成圈的特征结构,以此作为判定条件来确定网络图是否有圈存在。在最小支撑树模型的求解过程中,选择网络图中权数最小的边为支撑树的边。每选择一条边就判定一次,若判定有圈存在则放弃最后选择的边,反复选择边并判断,直到所有已选择的边都不构成圈且总边数等于点数-1,那么新确定的支撑树就是一个最小支撑树。这种新的算法已经Excel-BVA编制求解程序验证了其正确性、实用性和快捷性。     

多集散点车辆路径优化的混合算法

为使多集散点车辆路径优化结果全局最优,以订单为基准建立多集散点车辆路径优化模型.采用粒子群算法与改进蚁群算法组成的混合优化算法求解模型.由粒子群算法的粒子位置向量得到每辆车所需运送的订单号,用蚁群算法优化单车路径,根据优化的总路径评价和筛选粒子,直到满足终止条件.该模型和混合算法是所有车辆对所有订单节点的路径优化,突破了多仓库问题直接或间接转化为多个单仓库车辆路径优化问题中的局部节点求解的限制.实例求解结果表明,用该混合算法优化的车辆总路径长度小于用蚁群算法求得的结果.     

求解旅行商问题的混合量子算法

提出了求解旅行商问题的混合量子算法(HQA).HQA以量子计算为基础,设计了移位解码,解决了构造路径难的问题.并采用微粒群算法的进化模式和跟踪保优模式,构造了动态惯性权重使量子角更新、更有效,增加了局部优化进行精细搜索.对多个算例的测试结果表明,HQA具备了求解旅行商问题的能力.     

求解最小比率旅行商问题的大洪水算法

基于大洪水算法寻优思想,给出一种采用两城市互换策略进行邻域搜索的大洪水算法,以快速求解对称型最小比率旅行商问题.算法在Delphi7环境下编程实现,经大量数据测试和验证,大洪水算法是一种简单有效的算法,在运行效率上明显优于其他算法.     

基于最小生成树算法求解图的单源最短路径的研究

对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论.     

基于最小生成树算法求解图的单源最短路径的研究

对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论.     

附有条件的最小支撑树算法

传统最小生成树算法不能解决:度约束条件下的最小支撑树问题;动态网络的最小支撑树问题;边约束条件下的最小支撑树问题。遗传算法可以求解度约束条件下的最小支撑树问题,但存在效率低、编码复杂等缺陷。归纳了3类附有条件的最小支撑树数学模型,在最小支撑树传统算法基础上,提出了3类附有条件的最小支撑树算法。算法测试和比较表明:附有条件的最小支撑树算法是完全可行和有效的。     

一种求解多目标车辆路径问题的改进免疫算法

免疫算法是模拟生物免疫系统功能的一种智能优化算法,它具有良好的全局搜索能力.文章设计了一种具有动态自适应性的免疫算法,在算法中引入年龄结构模型,采用一种基于rank排名方法的抗体浓度抑制思想,并利用变异算子更新抗体群,保证了进化过程中解的多样性,提高了搜索效率.将改进的免疫算法用于求解多目标车辆路径问题,实验表明,算法...     

多车场车辆路径问题及混合遗传算法

在多车场车辆路径问题中,综合考虑车辆的行驶路程和使用车辆的数量能有效降低配送成本,考虑了这两方面的因素建立了相应的数学模型,运用混合遗传算法进行了求解,并通过实例证明了模型和算法的有效性。     

求一般图的最小顶点覆盖集问题的混合贪婪算法

现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大.根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法.该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为O(|V|2),执行效果较好,性能近似比不大于4/3,接近已知的可能的近似比下界1.166 6,低于2005年认为最低的近似比1.361,是图的最小顶点覆盖问题算法的一个较好的补充.     

求解车辆路径问题的改进蚁群算法

为解决基本蚁群算法的过早收敛的缺陷,提出一种将遗传算法和蚁群算法融合的改进的蚁群算法.即使用蚁群算法求解出完成所有配送任务的车辆行驶路径,并将其作为局部最优解;然后,使用遗传算法的交叉变异算子对第一步搜索出来的局部最优解进行优化,筛选出全局更优解.仿真实验证明:改进后的蚁群算法与现有的求解车辆路径优化问题的蚁群算法相比,具有更快的运行速度,找到最优解的概率更高,且避免了基本蚁群算法的过早收敛.     

基于离散海鸥算法求解循环取货车辆路径问题

针对如何降低循环取货车辆路径问题(VRP:Vehicle Routing Problem)中的运输成本,提出一种离散海鸥算法。首先,在海鸥迁移过程中,采用insert、 reverse操作更新海鸥位置加快算法寻优速度;其次,在海鸥攻击过程中,采用swap、 3-opt操作更新海鸥位置提升算法局部搜索能力;最后,结合模拟退火算法避免算法在运行过程中陷入局部最优,重新定义了在离散的车辆路径问题下的更新策略。以总成本最低为目标函数,构建相应的数学模型。实验结果表明,该算法具有高效解决循环取货车辆路径问题的能力,寻优效果及求解质量均高于标准海鸥优化算法、粒子群算法、模拟退火算法、灰狼优化算法、鲸鱼算法和飞蛾扑火算法。