共查询到20条相似文献,搜索用时 10 毫秒
1.
一个关于非对称距离的旅行商问题的迭代算法 总被引:1,自引:0,他引:1
本对非对称距离的旅行商问题,给出了一个迭代算法,并分析了此迭代算法的复杂度为M^nO(N^4),其中,N是问题中旅行商所要经过的城镇数,M是两城镇间的最大距离。最后用实例对此算法进行了验算和说明。 相似文献
2.
旅行推销员问题的算法综述 总被引:31,自引:0,他引:31
马良 《数学的实践与认识》2000,30(2):156-165
本文综述了旅行推销员问题 (TSP)近几十年来的算法研究进展 ,给出了一些主要算法的求解思想及其时间复杂度 相似文献
3.
改进遗传算法求解旅行商问题 总被引:2,自引:0,他引:2
针对采用自然编码的遗传算法在求解旅行商问题(TSP)过程中初始群体设置过于复杂的问题,采用了Grefenstette编码设置初始群体,有效保证了初始群体的随机性和多样性.同时,在遗传算法实施过程中采用了自然编码,吸取边重组交叉算子和简单交叉算子的优点,提出一种新的交叉算子.这种处理解决了Grefenstette编码在遗传算法的交叉和变异过程中只能部分遗传父代的优良特性的问题.对TSP试算结果表明,采用这种遗传算法策略有利于问题的求解.这种实施的策略可以大量用于加工领域和交通领域以及其他规划领域的路径规划中. 相似文献
4.
5.
旅行商问题的基因整合算法 总被引:3,自引:0,他引:3
本文针对旅行商问题提出了基因整合算法。它是通过设置扰动矩阵构造与原商问题等价的近似问题,使用最优罚函数选择回路分枝得到一系列局部最优回路,从中提取频度高的分技——基因进行整合,得到更优的回路。该算法计算量小,对大规模问题计算效果显著。利用该算法对CHN144问题给出了目前最件的结果。 相似文献
6.
本提出一种用凸包收缩来解决旅行推销员问题。首先形成一个凸包初始环路。然后,逐个考察凸包内的点,按照增加值从小到大的顺序依次插入,直至考察完所有的点。从而得到一个包含所有点的环路,即旅行推销员问题的一个满意解。 相似文献
7.
介绍了一种求解旅行商问题的新算法"最小调整法",给出了该算法求解旅行商问题的具体步骤以及有效性证明,对算法的复杂性及近似程度进行了分析.最后通过典型算例进行了检验说明.与经典算法相比,新算法体现了简单易行的特点,对求解旅行商问题具有一定的启发意义. 相似文献
8.
由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了社会的广泛重视,而应急车辆尽快地将应急物资送到受灾点显得尤为重要。针对应急车辆装载物资能力有限和应急车辆不必返回出发点的情形,提出了带有配额的在线Nomadic旅行商问题。分析了该问题在正半轴和一般网络上的下界,针对受灾点仅在正半轴上的情形设计了WTAIB算法,针对受灾点在一般网络上设计了WSB算法,并进一步分析了两个算法的竞争性能。 相似文献
9.
本文将航标部门提出的海上航标巡检问题转换成旅行商问题来研究,提出了一种综合模型及其混合型启发式算法,并就实际问题的特殊要求编制了相应的软件程序,可供决策者参考使用。 相似文献
10.
用列队竞争算法解旅行商问题 总被引:10,自引:1,他引:9
给出了列队竞争算法解组合优化问题的框架和确定变异邻域的两条原则。用列队竞争算法解旅行商问题获得了满意的结果,显示出列队竞争算法良好的全局搜索性能。 相似文献
11.
针对简单遗传算法易陷入局部最优及收敛速度慢的不足,提出一种改进遗传算法-基于启发式策略的搜寻者遗传算法.首先将搜寻者优化算法中的模糊思想和近邻策略相结合改进变异算子,增强种群多样性,避免陷入局部最优;然后针对路径优化问题基于启发式策略设计反转算子,使得路径中不存在交叉边,加快收敛速度;最后将改进遗传算法用于求解旅行商问题.结果表明,改进遗传算法的求解精度和求解效率明显优于基本遗传算法. 相似文献
12.
多旅行商路线的几个问题 总被引:5,自引:1,他引:4
俞文 《数学的实践与认识》1999,(1)
本文对98B题(全国大学生数学建模竞赛)的几个较为深入的问题进行讨论,包括:最小的Hamilton回路与最优旅行商路线的关系,目标函数的处理,最小组数问题。特别,对于98B题第三小题,22组是否为最小组数,我们给出了肯定的结论。 相似文献
13.
14.
15.
16.
非对称距离的旅行商问题的构造算法 总被引:9,自引:1,他引:8
章分析了非对称距离的旅行商问题,讨论了节约算法与最小生成树算法两种启发式方法,并用实例进行了说明,最后对算法的有效性进行了说明。 相似文献
17.
本文研究了一种改进的求解旅行商问题最优路径的免疫遗传算法.结合随机法与贪心法生成初始种群,利用亲和度排序而选取抗体以得到复制群体,引入轮盘赌及克隆选择获取高亲和度抗体,并实施疫苗接种及免疫记忆更新抗体.运用免疫记忆机理的闭环逻辑,证明了该算法生成的城市序列是全局收敛的.数值实验证明该算法是有效的. 相似文献