基于改进蚁群算法的有时间窗约束的车辆路径问题研究

基于改进蚁群算法的有时间窗约束的车辆路径问题研究作者：刘市委学位授予单位：长春理工大学相似文献(10条)1.学位论文肇勇改进蚁群算法的理论及方法研究2004本文总结了国内外蚁群算法的研究成果,并提出了新的改进蚁群算法.蚁群算法在组合优化问题的成功应用,使得人们开始将焦点又集中在其在连续优化问题上的应用.目前国内外对于蚁群算法在连续优化问题的应用研究成果还很少,但初步研究已显示出蚁群算法较好的性能.多极值全局优化问题是本文研究的重点,通过使用一种新的蚁群算法—基于网格法的蚁群算法进行多个算例的测试,证明了该算法的性能较好.可以预见随着蚁群算法理论的不断完善,蚁群算法将越来越成功地用于连续优化问题.本文的主要研究内容及成果如下:(1)对全局优化方法的基本框架和研究进展进行了系统的综述,分别从全局优化问题的特点,全局优化方法的构造原理和分类,以及现有全局优化方法的不足等几个方面进行了系统的阐述.(2)针对近几年来发展较快的启发式搜索算法的理论和方法进行了系统的研究.详细研究了启发式搜索算法的产生、构造方法、基本类型等几个方面.并概述了几种元启发式算法:蚁群算法、模拟退火法、遗传算法、禁忌搜索法、混沌优化算法等.(3)详细系统的研究了蚁群算法的发展现状,对于各种改进蚁群算法的特点进行了分析和对比,在此基础之上提出了新的改进蚁群算法,并经过程序调试,其结果显示新的改进蚁群算法的有较好的性能.在研究用于组合优化问题的蚁群算法的基础上,详细地阐述了一种用于连续优化问题的蚁群算法—基于网格的改进蚁群算法,通过测试多个算例发现该方法能够较好地解决一些多极值函数的优化问题.(4)对广义邻域搜索算法及其统一结构进行了详细的阐述和分析,并提出了一种新的混合优化算法-ACOSA,即基于蚁群算法和模拟退火法的混合算法.对于ACOSA混合算法的结构和性能进行了分析,经过测试证明ACOSA混合算法优于单纯蚁群算法和模拟退火法等元启发式算法.2.会议论文师凯.蔡延光.邹谷山.王涛运输调度问题的蚁群算法研究2004蚁群算法是一种用于求解复杂组合优化的较新的启发式算法.本文简述了蚁群算法的基本原理及算法模型,通过分析研究现状指出了蚁群算法在实际应用中的局限性,最后给出解决一般运输调度问题的蚁群算法,并分析了其今后的发展方向.3.学位论文于沛欣一种混合蚁群算法在JSP问题中的应用研究2008随着市场竞争的日趋激烈，每个企业都在寻求更好的生产与运作管理方案，以提高企业的生产、经营和管理效率，从而提高企业的核心竞争优势。生产与运作管理的核心是车间调度问题能否高效地获得优化解，研究车间调度问题具有很大的理论意义和现实价值。车间调度问题是解决如何按时间的先后分配资源来完成不同的生产任务，使预定目标最优化的问题。作业车间调度-(JSP)问题是许多实际车间调度问题的简化模型，是一个典型的NP一难问题。该问题具有约束性、非线性、不确定性、大规模性等复杂性，已被证明在多项式时间内得不到最优值。近年来，对于Job-shop调度问题求解方式主要有启发式算法和元启发式算法，但各有其不足之处：元启发式方法的运行时间长，可获得较好的解，但其解不稳定；启发式方法可在较短的时间内得到鲁棒性较强的解，但是极少获得较优的解。为了更好地解决作业车间调度问题，将一些解决此类问题较好的算法组合起来。蚁群算法是通过信息素的累积和更新收敛于最优路径上，具有分布式并行全局搜索能力，但初期信息素匾乏，求解速度慢。禁忌搜索法(TabuSearch)是一种通过邻域搜索以获取最优解的方法，能有效地加快解的收敛速度。本文根据蚁群算法的特点，对蚁群算法进行改进，并将禁忌搜索算法熔入到蚁群算法中，以改善蚁群算法的收敛速度。算法动态融合的思想是首先应用改进的蚁群算法找到JSP问题的可行解，然后应用禁忌搜索在可行解的邻域找到更优的解。最后，本文对JSP问题应用实验仿真计算。结果表明，改进的蚁群算法与禁忌搜索结合后的混合蚁群算法的收敛速度更高，具有更好的全局收敛性能，能在更少的迭代次数达到全局最优解，具有更高的收敛速度。4.期刊论文王雪峰.孙小明.郑柯威.杨芳.WANGXue-feng.SUNXiao-ming.ZHENKe-wei.YANGFang定位-车辆路径问题的两阶段混合启发式算法-上海交通大学学报2006,40(9)定位-车辆路径问题(LRP)集成了设施定位分配和车辆路径决策,属于NP-hard难题.为有效求解实际大规模的具有设施容量约束和车辆容量约束的LRP问题,设计了基于禁忌搜索及双种群蚁群算法的两阶段混合启发式算法.算法第1阶段采用禁忌搜索算法确定设施定位及客户分配,算法第2阶段采用双种群蚁群算法优化车辆路径,蚁群间的通信与协调通过信息素共享来实现.通过仿真试验并与其他启发式算法进行对比,结果表明,该算法是可行和有效的.5.学位论文曾艳蚁群算法在组合优化中的应用2006组合优化中的许多问题是NP-完全问题，也是科学和工程计算中重要和基本的问题，这类问题的求解一直是算法研究领域的热点问题。对于NP-完全的组合优化问题，至今尚无很好的解析算法，一般采用启发式算法来解决。蚁群算法作为一种新的启发式算法，它具有正反馈、分布式计算以及结构性的贪心启发等特点，使其能够成功地解决许多NP-完全的组合优化问题。本文在详细介绍蚁群算法原理的基础上，对蚁群算法在组合优化问题中的应用进行分析和研究，主要将蚁群算法应用于求解最大团和最大割两个经典的NP-完全组合优化问题，本文主要做了以下工作：1、在研究已有的最大团问题的蚁群算法以及对蚁群算法深入分析的基础上，根据最大团问题的特点，提出了最大团问题的新型蚁群算法，通过大量的仿真试验证明，算法的性能明显提高了。2、以最大团问题为例，对蚁群算法的参数进行了深入研究，并提出了使用动态局部启发信息的改进策略。仿真试验证明，该方案使算法的性能得到一定的提高。3、在研究了组合优化问题基础上，提出了最大割问题的蚁群算法方案。大量的仿真试验证明，该方案能较成功地解决最大割问题。6.期刊论文刘乃文.刘方爱.LIUNai-wen.LIUFang-ai蚁群算法用于TSP的并行策略及模型-计算机应用研究2007,24(12)蚁群算法是一种元启发式算法,其经典应用是解决旅行商问题.该算法有着先天的并行特性.介绍了该算法的两种并行实现策略,给出了蚁群算法的并行实现模型,分析了该算法并行实现需要解决的问题.7.会议论文施寒潇基于改进型蚁群算法求解0/1背包问题为了使用蚁群算法来解决经典的0/1背包问题,本文比较了旅行商问题和0/1背包问题的不同之处.在原有的蚁群优化模型的基础上扩展了它的应用范围,用来解决0/1背包问题,同时相应的一些参数也得到了优化.实验结果显示了蚁群算法的健壮性和作为启发式算法在解决组合优化难题时的潜力.8.学位论文陈星宇蚁群算法理论及其应用研究2008蚁群算法是一种新型求解复杂优化问题的启发式算法。该方法通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。由于蚁群具有稳健性、全局性、普遍性、分布式计算等优点，理论研究不断深入，应用领域不断扩大。理论方面主要研究算法的模型，分析其收敛性和收敛速度以及控制参数对算法性能的影响等。而应用研究也分为两类：解决组合优化问题以及用于具体应用领域。相对于理论部分，对蚁群算法的应用部分的研究则开辟了相当广阔的领域，也取得了很大的成功。本文在理论上对蚁群算法本身的理论部分进行研究，提出了几点有效的改进策略，对蚁群算法加以改进。在应用方面选取TSP问题作为典型的组合优化问题，用改进的蚁群算法求解之。最后，将算法运用于实际的物流管理中的配送路径优化问题。仿真结果表明，本改进算法在理论和实际中都是非常有效的。论文的主要工作和创新如下：在混合算法-最大最小蚂蚁算法和3-opt局部搜索算法的基础上，提出了一种改进的混合蚂蚁算法。在集中讨论了蚁群算法的数学模型基础上，并对蚁群算法提出了几点改进策略，使得本算法能比其他改进蚁群算法具有更多优越性。算法前期使用局部搜索的解初始化信息素矩阵，加快收敛速度，后期依Metropolis接受准则概率接受局部优化解，有效地避免陷入局部最优，自适应的信息素调节机制使算法更加灵活，而K近邻候选集则使之适应大规模问题求解。将改进算法应用于经典的组合优化问题TSP(TravelingSalesmanProblem)问题。TSP问题是一个是一类典型的NP难问题，经常被用来验证算法的效率。在交通运输、网络等方面有着广泛的应用背景。由于TSP问题与最短路径有很多相似之处，它也是路径优化问题的研究基础。理论分析和TSPLIB中部分实例仿真结果表明，此算法求解TSP问题能比其他改进蚁群算法具有更多优越性。将改进算法应用于物流运输管理中，设计了物流配送路径优化问题的数学模型和用于优化物流配送路径的混合蚁群算法，并用实验证明了该算法对于合理生成物流配送路径有着很好的作用，通常都能够找到最优的路径。9.期刊论文陈宝文.宋申民.陈兴林.CHENBao-wen.SONGShen-min.CHENXing-lin随机需求车辆路径问题及其启发式算法-计算机工程与设计2007,28(1)在对随机需求信息条件下的车辆路径问题进行策略分析基础上,提出解决此类问题的改进蚁群算法.分析对比不同策略下用蚁群算法优化的结果.其中给出机会约束下决策者的风险喜好对最终目标的影响.通过模拟实际随机需求的方法评价先验路径的优劣.与其它计算方法在同等条件下的比较证明所设计算法的优越性.同时得出对于不同统计特性的随机需求策略的选择方式.10.学位论文陈晔应用蚁群算法解决约束P-中位问题2005约束p—中位问题(Capacitatedp—medianproblem,CPMP)作为设备选址问题(Facilitylocationproblem,FLP)的一个特殊分支,有着广泛的应用背景,在选址理论和聚类理论中人们对其进行了深入地研究。已知CPMP是一类NP—hard组合优化问题,因此已有多种启发式算法用于求解该类问题。蚁群算法(Antcolonyalgorithm,ACO)由于其良好的优化性能,已成为智能仿生算法领域中最具影响力的算法之一。它的主要优点是:利用蚁群间的信息交互,来逐步优化对问题状态的信息素表示,进而指导蚁群搜索问题的最优解。本论文旨在研究如何有效地将ACO用于求解CPMP,以及如何解决与算法执行相关的一系列重要问题,以获得最好的优化性能。本文的主要工作包括:1.针对CPMP的特点,提出了一种新的求解该问题的启发式算法—中位学习算法(Medianlearningalgorithm,MLA)。本文链接：授权使用：上海海事大学(wflshyxy)，授权号：6850376e-c8b0-4a5e-b193-9e06004c0aaa下载时间：2010年10月5日