改进遗传算法求解TSP问题

1

作者 朱建军 王志宾 《吉林化工学院学报》 2025年第2期11-17,共7页

针对传统遗传算法求解旅行商问题时初始解质量差、容易陷入局部最优、求解精度低等问题,提出了一种改进遗传算法。首先,将贪婪算法与精英选择结合,提高种群中初始解的质量;其次,设计自适应交叉和变异概率的步骤,结合Metropolis准则来防... 针对传统遗传算法求解旅行商问题时初始解质量差、容易陷入局部最优、求解精度低等问题,提出了一种改进遗传算法。首先,将贪婪算法与精英选择结合,提高种群中初始解的质量;其次,设计自适应交叉和变异概率的步骤,结合Metropolis准则来防止遗传算法陷入局部最优;最后,加入贪婪双向三交叉和2-opt搜索算法,提高求解精度。实验结果表明,改进遗传算法最优解的偏差率均小于1.88%,均值的偏差率均小于2.27%。 展开更多

关键词 旅行商问题 遗传算法 贪婪双向三交叉 自适应 2-opt算子

在线阅读 下载PDF 职称材料

考虑碳排放和客户满意度的医药冷链物流配送路径优化

2

作者 邓梦杰 李义华 +1 位作者 徐贝 吴露青 《铁道科学与工程学报》 北大核心 2025年第5期2100-2113,共14页

“双碳”背景下,降碳减排是国民经济高质量发展的现实需要。医药产品时效性强、单位价值高、易腐坏变质,需全程冷链,因此碳排放相对较高。本文旨在对医药冷链物流配送路径进行优化,利用减少行驶时间、降低药品货损、确保药品质量,在不... “双碳”背景下,降碳减排是国民经济高质量发展的现实需要。医药产品时效性强、单位价值高、易腐坏变质,需全程冷链,因此碳排放相对较高。本文旨在对医药冷链物流配送路径进行优化,利用减少行驶时间、降低药品货损、确保药品质量,在不直接改变客户满意度函数的情况下间接提升客户满意度,从而实现医药冷链物流车辆配送过程中碳排放量最小化和客户满意度最大化目标。首先构建了考虑客户满意度最大化和包括固定成本、燃油成本、碳排放成本、货物损耗成本和时间窗惩罚成本5项成本在内的综合成本最小化的双目标优化模型,并且在构建客户满意度函数时主要关注了时间因素;其次,设计了一种改进蚁群算法和局部搜索算法2-opt相结合的混合蚁群算法对模型进行求解;再次,结合实际构造算例,并采用基本蚁群算法、改进蚁群算法和混合蚁群算法分别对其进行求解,旨在验证混合蚁群算法的有效性;最后,求解结果显示,混合蚁群算法在降低综合成本方面优于基本蚁群算法和改进蚁群算法,在客户满意度方面则与基本蚁群算法表现相当,但稍优于改进蚁群算法。本研究验证了混合蚁群算法在降低配送成本、减少碳排放量以及提高客户满意度等方面的有效性,同时为医药冷链物流配送优化提供了一种有效解决方案,并且为路径优化模型构建提供了有益参考。 展开更多

关键词 车辆配送路径优化 医药冷链物流 两元素优化 混合蚁群算法 双目标优化

在线阅读 下载PDF 职称材料

车辆路径问题的模拟退火算法 被引量：42

3

作者 胡大伟 朱志强 胡勇 《中国公路学报》 EI CAS CSCD 北大核心 2006年第4期123-126,共4页

在构造车辆路径问题(Vehicle Routing Problem,VRP)数学模型后,采用路径间调整和路径内优化方法,结合模拟退火算法策略对该问题进行求解。重点阐述了VRP模拟退火算法的设计思路,详细分析和编制了求解程序框图,并实现了计算机求解。仿真... 在构造车辆路径问题(Vehicle Routing Problem,VRP)数学模型后,采用路径间调整和路径内优化方法,结合模拟退火算法策略对该问题进行求解。重点阐述了VRP模拟退火算法的设计思路,详细分析和编制了求解程序框图,并实现了计算机求解。仿真测试结果表明:采用模拟退火算法求解VRP效果显著,计算速度较快,与有关算法对比显示了较强的实用性和可操作性,为解决大规模VRP提供了一种有效算法。 展开更多

关键词 物流 车辆路径问题 模拟退火算法 2-opt法 插入法

在线阅读 下载PDF 职称材料

求解车辆路径问题的混合遗传算法 被引量：33

4

作者 姜昌华 戴树贵 胡幼华 《计算机集成制造系统》 EI CSCD 北大核心 2007年第10期2047-2052,共6页

针对物流配送中具有容量限制的车辆路径问题,设计了一种结合2-OPT子路径优化的混合遗传算法。在该算法中,提出了一种新的双层染色体编码方案。该染色体编码方案能确保子路径为满足车辆容量约束的可行路径,并且该编码方案只需根据客户编... 针对物流配送中具有容量限制的车辆路径问题,设计了一种结合2-OPT子路径优化的混合遗传算法。在该算法中,提出了一种新的双层染色体编码方案。该染色体编码方案能确保子路径为满足车辆容量约束的可行路径,并且该编码方案只需根据客户编号生成染色体,无需预先知道有容量限制的车辆路径问题所需的最小车辆数,更适于求解实际中的车辆路径优化问题。采用2-OPT算法作为遗传算法的变异算子以优化子路径,从而提高算法的收敛速度。基于典型基准测试实例的计算结果表明,该算法是求解有容量限制的车辆路径问题的有效方法。 展开更多

关键词 物流配送 车辆路径问题 混合遗传算法 双层染色体 2-OPT子路径优化

在线阅读 下载PDF 职称材料

基于干扰管理的车辆故障救援模型 被引量：10

5

作者 蒋丽 丁斌 臧晓宁 《系统工程》 CSSCI CSCD 北大核心 2010年第6期111-116,共6页

针对物流配送过程中的车辆故障问题,制定救援车辆要到故障车辆处装货的邻近救援策略。以总配送距离最短、受扰车辆数最少和总配送延迟最小为目标,构建车辆故障邻近救援模型。设计遗传算法和2-opt算法结合的混合遗传算法求解模型,得出车... 针对物流配送过程中的车辆故障问题,制定救援车辆要到故障车辆处装货的邻近救援策略。以总配送距离最短、受扰车辆数最少和总配送延迟最小为目标,构建车辆故障邻近救援模型。设计遗传算法和2-opt算法结合的混合遗传算法求解模型,得出车辆发生故障以后对系统负作用最小的调整方案。最后,通过仿真算例对比分析该邻近救援策略和车辆增派策略。 展开更多

关键词 干扰管理 车辆故障 车辆路径问题 遗传算法 2-opt算法

原文传递

一种基于遗传算法的TSP问题多策略优化求解方法 被引量：17

6

作者 孙文彬 王江 《地理与地理信息科学》 CSCD 北大核心 2016年第4期1-4,共4页

针对遗传算法求解TSP问题解质量不高的缺陷,该文提出并设计了一种基于遗传算法的多策略优化求解方法。首先,应用最邻近法构建TSP的初始解;接着将路径长度作为适应度评价指标,构建基于遗传算法的TSP初始解优化方法,并根据试验结果确定适... 针对遗传算法求解TSP问题解质量不高的缺陷,该文提出并设计了一种基于遗传算法的多策略优化求解方法。首先,应用最邻近法构建TSP的初始解;接着将路径长度作为适应度评价指标,构建基于遗传算法的TSP初始解优化方法,并根据试验结果确定适合的遗传算法参数;然后,针对遗传算法易陷入局部最优的缺陷,借助去交叉和小角操作进一步优化TSP解路径;在此基础上,将遗传算法进行并行化处理,通过增加遗传算法的多样性提高TSP解质量。最后,应用标准测试集(TSPLIB)进行试验,结果表明:该算法能有效提高TSP解的质量,经并行遗传算法、去交叉和小角优化后各测试数据集TSP解误差率平均下降了22.57%;解的误差率均在7.94%以内,质量明显优于最邻近法、插入法、2-Opt优化等传统方法;在节点数多的测试数据集中算法也获得了良好加速性能,8进程时算法加速比达2.51。 展开更多

关键词 TSP问题 遗传算法 优化策略 2-Opt

在线阅读 下载PDF 职称材料

旅行商问题研究及混合粒子群算法求解 被引量：5

7

作者 孙聪 赵新超 《计算机工程与应用》 CSCD 北大核心 2009年第25期38-40,57,共4页

定性地分析了基本粒子群算法,结合遗传算法思想,构造了3种杂交和4种变异运算法则,从而得到了12种混合粒子群算法,并采用14城市算例对其检验和分析。为进一步验证混合算法的性能,根据分析结果挑选了几种较优的混合算法用以解决中国34城市... 定性地分析了基本粒子群算法,结合遗传算法思想,构造了3种杂交和4种变异运算法则,从而得到了12种混合粒子群算法,并采用14城市算例对其检验和分析。为进一步验证混合算法的性能,根据分析结果挑选了几种较优的混合算法用以解决中国34城市(CTSP)问题和kroC100问题,其中CTSP问题很快达到最优解,对kroC100问题该文提供的算法获得了一个比现有已知结果更好的结果。 展开更多

关键词 旅行商问题 粒子群算法 2-opt 3-opt 遗传算法

在线阅读 下载PDF 职称材料

帝国竞争算法求解CVRP 被引量：11

8

作者 蔡延光 王世豪 +2 位作者 戚远航 王福杰 林卓胜 《计算机应用研究》 CSCD 北大核心 2021年第3期782-786,共5页

针对带容量约束的车辆路径问题(CVRP),提出了一种带分裂机制的帝国竞争算法进行求解。首先,结合CVRP的特性,采用基于贪婪准则的编解码策略实现算法空间到解空间的转换。其次,提出帝国分裂策略来增强算法的全局搜索能力,并结合2-Opt提高... 针对带容量约束的车辆路径问题(CVRP),提出了一种带分裂机制的帝国竞争算法进行求解。首先,结合CVRP的特性,采用基于贪婪准则的编解码策略实现算法空间到解空间的转换。其次,提出帝国分裂策略来增强算法的全局搜索能力,并结合2-Opt提高算法的局部搜索能力。最后,通过25个基准算例的仿真实验表明:所提算法能有效求解CVRP,所有算例的优化误差不超过1.0%;与已有的帝国竞争算法、粒子群算法、遗传算法、布谷鸟搜索算法相比,所提算法的求解效率更高。 展开更多

关键词 车辆路径问题 帝国竞争算法 粒子群算法 遗传算法 2-Opt

在线阅读 下载PDF 职称材料

新型模拟退火遗传算法在路径优化的应用 被引量：18

9

作者 李朝迁 裴建朝 《组合机床与自动化加工技术》 北大核心 2022年第3期52-55,共4页

针对路径优化中,遗传算法(GA)初始解质量低,变异能力差,以及易陷入局部最优解等问题,提出了一种新型模拟退火遗传算法。首先,采用混合策略生成初始解,将模拟退火算法引入遗传算法的变异算子,使用2-opt算子和单点最优插入算子增强局部搜... 针对路径优化中,遗传算法(GA)初始解质量低,变异能力差,以及易陷入局部最优解等问题,提出了一种新型模拟退火遗传算法。首先,采用混合策略生成初始解,将模拟退火算法引入遗传算法的变异算子,使用2-opt算子和单点最优插入算子增强局部搜索能力,使算法能够更加有效地避免陷入局部最优;其次,提出改进的锦标赛算法,对交叉、变异前后种群个体进行一一对比,选择较优个体进入下一代,目的是为了避免传统锦标赛法破坏种群多样性,同时改进方法可以在增强变异能力的情况下,维持种群稳定性;最后,用TSP问题实例进行试验。结果表明,所提算法在Dantzig42和Pr107实例的优化结果优于国际网站TSPLIB给出的最优结果。 展开更多

关键词 路径优化 改进遗传算法 模拟退火算法 2-opt算子

在线阅读 下载PDF 职称材料

基于改进蚁群算法的CVRP问题研究 被引量：3

10

作者 程亮 干宏程 刘勇 《重庆工商大学学报（自然科学版）》 2021年第5期81-86,共6页

车辆路径优化问题归属于NP-hard问题;针对基本蚁群算法求解效率低下,可行解质量不高,容易陷入局部最优解的情况,在充分考虑具有一般性的车辆路径优化问题的数学模型与解决方案后,提出了一种带有轮盘赌运算与2-opt优化运算相结合的改进... 车辆路径优化问题归属于NP-hard问题;针对基本蚁群算法求解效率低下,可行解质量不高,容易陷入局部最优解的情况,在充分考虑具有一般性的车辆路径优化问题的数学模型与解决方案后,提出了一种带有轮盘赌运算与2-opt优化运算相结合的改进蚁群算法,算法在运算过程中对选取路径的概率进行二次计算,扩大了全局的搜索范围;同时对得到的路径进行内部优化,增强了局部搜索能力,提高了解的质量;通过MATLAB软件进行仿真实验的结果表明:相较于基本的ACO算法以及遗传算法得到的结果,改进的蚁群算法在性能上和求解的质量具有很大的优势,可以更好地解决带有容量约束的车辆路径优化问题,为相应的企业更好地节省物流成本。 展开更多

关键词 物流配送 蚁群算法 2-opt CVRP问题

在线阅读 下载PDF 职称材料

城市车辆配送线路设计的模型与算法 被引量：2

11

作者 金升平 《计算机工程与应用》 CSCD 北大核心 2002年第22期38-39,47,共3页

文章建立了城市车辆配送的多旅行商问题(MTSP)模型,设计了一个新的遗传算法,用2Opt算子改进解的总距离,用贪心交叉算子提供变异功能,计算实例表明了该算法的有效性。

关键词 城市车辆配送线路 设计 模型 算法 多路旅行商问题 遗传算法 二边修正法

在线阅读 下载PDF 职称材料

一种改进的遗传算法在TSP问题中的应用 被引量：8

12

作者 王殿超 《辽宁工业大学学报（自然科学版）》 2019年第4期235-239,共5页

物流业作为国家经济体系的重要组成部分,费用居高不下,特别是运输费用达到物流费用的一半以上,是导致物流成本过高的重要因素。旅行商问题是车辆路径问题的特例,是实现车辆路径优化的关键。对遗传算法的交叉和变异算子进行改进,在边集... 物流业作为国家经济体系的重要组成部分,费用居高不下,特别是运输费用达到物流费用的一半以上,是导致物流成本过高的重要因素。旅行商问题是车辆路径问题的特例,是实现车辆路径优化的关键。对遗传算法的交叉和变异算子进行改进,在边集合重组交叉的基础上结合近旁构造的启发式思想,多阶段展开的边集合重组交叉算子,在2-opt算法的基础上提出了基于2-opt启发式算法的不断变异算子,并在实例中进行应用,达到缩短距离、降低物流费用的目的。 展开更多

关键词 旅行商问题 遗传算法 边集合重组交叉 近旁构造 2-opt启发

在线阅读 下载PDF 职称材料

带软时间窗的公共自行车调度路径问题 被引量：2

13

作者 汪岚 吴永春 陈海洋 《延边大学学报（自然科学版）》 CAS 2019年第1期64-69,共6页

为了提高公共自行车调度的效率,研究了一种带软时间窗的自行车调度路径问题.首先根据公共自行车调度工作内容,建立多目标调度路径模型,然后设计一种改进的蚁群算法对模型进行了求解.实验结果显示,本文方法求解的调度路径比模拟退火算法... 为了提高公共自行车调度的效率,研究了一种带软时间窗的自行车调度路径问题.首先根据公共自行车调度工作内容,建立多目标调度路径模型,然后设计一种改进的蚁群算法对模型进行了求解.实验结果显示,本文方法求解的调度路径比模拟退火算法、蚁群算法和遗传算法分别缩短了18.4%、24.3%和13.0%,而且还能有效节约调度车辆. 展开更多

关键词 公共自行车 调度路径问题 混合算法 改进蚁群算法 遗传算法 2-opt算法

在线阅读 下载PDF 职称材料

基于改进MMAS算法的堆垛机货物拣选路径优化 被引量：2

14

作者 程永强 汪岚 《延边大学学报（自然科学版）》 CAS 2017年第3期255-258,共4页

提出了一种基于改进最大最小蚁群算法(MMAS)的货物拣选路径优化算法.首先建立堆垛机货物拣选路径最短化的数学模型,然后利用改进的MMAS对其求解获得临时优化路径,最后融合2-opt策略进行局部调整获得最优拣选路径.实验结果表明,本算法可... 提出了一种基于改进最大最小蚁群算法(MMAS)的货物拣选路径优化算法.首先建立堆垛机货物拣选路径最短化的数学模型,然后利用改进的MMAS对其求解获得临时优化路径,最后融合2-opt策略进行局部调整获得最优拣选路径.实验结果表明,本算法可有效克服蚁群算法易陷入局部最优的不足,且较之遗传、粒子群等算法缩短了货物的拣选路径,提高了仓库作业的效率. 展开更多

关键词 货物拣选路径 改进最大最小蚁群算法 2-opt策略 遗传算法 粒子群算法

在线阅读 下载PDF 职称材料

一种求解TSP问题的改进遗传算法 被引量：5

15

作者 杨华芬 魏延 《重庆工学院学报》 2007年第9期86-90,共5页

旅行商问题(Traveling Salesman Problem TSP)是一个典型的组合优化问题,但应用基本遗传算法求解TSP问题时存在许多不足.结合TSP问题的特点,提出一种改进的遗传算法:应用贪心策略初始化种群,用2-opt对其进行优化,使得在初始个体中就包... 旅行商问题(Traveling Salesman Problem TSP)是一个典型的组合优化问题,但应用基本遗传算法求解TSP问题时存在许多不足.结合TSP问题的特点,提出一种改进的遗传算法:应用贪心策略初始化种群,用2-opt对其进行优化,使得在初始个体中就包含较优子路径,在一定程度上加快算法收敛性,防止早熟和近亲繁殖.对交叉算子和变异算子进行改进后,既能维持种群的多样性,也保留了父代个体大部分优良性能.应用改进的算法对20个城市的TSP问题进行求解,结果表明该算法求解速度快而且求解的质量较好. 展开更多

关键词 TSP 交叉算子 2-opt搜索优化 遗传算法 变异算子

在线阅读 下载PDF 职称材料

基于智能混合算法的车辆配送路径优化 被引量：3

16

作者 汪岚 《延边大学学报（自然科学版）》 CAS 2015年第3期261-266,共6页

为提高车辆配送效率,节约配送成本,建立了以配送路径和成本综合最优为目标的车辆配送路径问题数学模型.设计并实现了一种智能混合算法,首先利用具有自适应交叉率和变异率的改进遗传算法生成全局较优解,再将较优解转换为初始信息素进行... 为提高车辆配送效率,节约配送成本,建立了以配送路径和成本综合最优为目标的车辆配送路径问题数学模型.设计并实现了一种智能混合算法,首先利用具有自适应交叉率和变异率的改进遗传算法生成全局较优解,再将较优解转换为初始信息素进行蚁群算法,并结合2-opt算法对解进一步迭代优化,最终获得了车辆最优配送路径.实验结果表明,该算法优化后的目标值比蚁群算法减少了15.0%,比遗传算法减少了10.4%,验证了该算法的有效性和优越性. 展开更多

关键词 车辆配送路径问题 智能混合算法 遗传算法 蚁群算法 2-opt算法

在线阅读 下载PDF 职称材料

求解多旅行商问题的改进分组遗传算法 被引量：37

17

作者 王勇臻 陈燕 于莹莹 《电子与信息学报》 EI CSCD 北大核心 2017年第1期198-205,共8页

该文针对总路径长度最小的多旅行商问题,提出一种改进分组遗传算法。在该算法中,设计了一种有序分组编码,采用新编码方式的个体与多旅行商问题有效解之间具有一一对应的关系。为了减少算法的运行时间,根据编码的特点构造了一种快速交叉... 该文针对总路径长度最小的多旅行商问题,提出一种改进分组遗传算法。在该算法中,设计了一种有序分组编码,采用新编码方式的个体与多旅行商问题有效解之间具有一一对应的关系。为了减少算法的运行时间,根据编码的特点构造了一种快速交叉算子。同时,结合贪婪算法和2-opt算法设计了一种新的局部搜索算子,以提高算法的收敛精度。实验结果分析表明,所提算法能够有效地解决多旅行商问题,具有可靠的全局收敛性,较高的计算效率。 展开更多

关键词 分组遗传算法 多旅行商问题 编码 2-opt算法

在线阅读 下载PDF 职称材料

基于PGA-2-OPT算法的焊接机器人路径规划

18

作者 刘良斌 赵自鹏 王瑶茜 《电脑与电信》 2023年第8期42-45,共4页

针对白车身焊接过程中焊点数量大、焊接顺序规划凭借经验的问题,提出了将焊接顺序和路径的规划问题转换为TSP问题的方案。传统遗传算法对种群多样化要求较高,后期易陷入局部最优问题;基本单亲遗传算法存在路径交叉问题。文章先对焊接任... 针对白车身焊接过程中焊点数量大、焊接顺序规划凭借经验的问题,提出了将焊接顺序和路径的规划问题转换为TSP问题的方案。传统遗传算法对种群多样化要求较高,后期易陷入局部最优问题;基本单亲遗传算法存在路径交叉问题。文章先对焊接任务采用单亲遗传算法得到相对最优解,然后采用2-OPT领域搜索策略,消除路径存在的交叉问题。文章以宝马某车型右前门板焊接任务为例,对焊接轨迹进行优化。改进后的车门焊接轨迹在同等进化代数的情况下,比传统遗传算法缩短了46%,比原有的单亲遗传算法缩短了29%。实验表明,通过PGA-2-OPT算法可以实现车门板焊接路径的优化,并能很好地消除路径交叉问题。 展开更多

关键词 单亲遗传算法 白车身焊接 2-OPT

在线阅读 下载PDF 职称材料

基于双种群混合遗传算法的车辆调度问题研究

19

作者 胡云清 《物流科技》 2015年第10期134-136,共3页

车辆路径优化问题影响着企业的生存发展,对于企业至关重要。传统遗传算法容易陷入局部最优解,算法求解性能有待改善。针对该问题,文章提出了求解车辆路径优化问题的双种群混合遗传算法。算法在进化过程中采用两个遗传种群,分别选取不同... 车辆路径优化问题影响着企业的生存发展,对于企业至关重要。传统遗传算法容易陷入局部最优解,算法求解性能有待改善。针对该问题,文章提出了求解车辆路径优化问题的双种群混合遗传算法。算法在进化过程中采用两个遗传种群,分别选取不同的交叉和变异概率进行遗传操作。在每一次迭代结束时,将两个种群中的优秀个体进行互换,打破种群间的平衡。同时,为了提高种群质量,文章还采用2-opt算子对种群中的最优个体进行了优化。仿真实验表明,文章所提的算法具有更好的求解性能。 展开更多

关键词 车辆路径问题 双种群遗传算法 2-opt

在线阅读 下载PDF 职称材料

基于2-Opt免疫遗传算法的冷链配送路径优化问题研究 被引量：6

20

作者 王咪 杨孔雨 《物流技术》 2016年第7期72-75,112,共5页

分析了生鲜产品冷链配送的现状,并指出了研究生鲜产品冷链配送路径优化问题的重要意义。考虑配送过程中道路颠簸对于生鲜产品配送成本的影响,同时结合车辆固定成本、运输成本、能源成本、惩罚成本、货损成本等建立冷链物流车辆配送路径... 分析了生鲜产品冷链配送的现状,并指出了研究生鲜产品冷链配送路径优化问题的重要意义。考虑配送过程中道路颠簸对于生鲜产品配送成本的影响,同时结合车辆固定成本、运输成本、能源成本、惩罚成本、货损成本等建立冷链物流车辆配送路径优化模型,并将2-Opt算法与免疫遗传算法相结合对该模型进行求解,最后通过实例分析,证明该模型有效实用,为相关行业的发展和企业运营提供参考。 展开更多

关键词 冷链 2-Opt 免疫遗传算法 配送路径优化

在线阅读 下载PDF 职称材料