基于遗传算法特性的混合粒子群算法求解TSP问题

为解决粒子群算法在旅行商问题上的收敛速度慢和路径最优化选择的问题,提出了一种新型的基于遗传算法特性的混合粒子群算法,对旅行商问题的最优路径进行规划.根据种群比例原则与迭代前的路径进行交叉、变异、复制等操作,建立了具有遗传算法特性的混合粒子群算法,并用于求解burma14问题.结果表明:相比传统的粒子群算法和模拟退火-禁忌搜索算法,混合粒子群算法在求解burma14问题中收敛时间与最优路径等指标上都有明显的优势,且随着迭代次数与种群个数的增大,算法的最优解逐渐减小;当最佳参数为种群个数150,迭代次数300时,最优解为30.179 424.

基于三阶段TSP算法的旅游路线规划

基于201个国家5A级景区,充分考虑出行时间和出行方式的前提下,构建了三阶段TSP模型,利用遗传算法,为旅游爱好者规划合理的出行方案.结果表明:对于自驾游爱好者,要游览所有5A级景区,至少需要11年的时间;考虑乘坐高铁等到达景区所在省、租车自驾游览景区、住宿等的综合费用为392615元;模型推广后,对于北京的旅游爱好者,采用动车、高铁、飞机、自驾等综合出行方式,要在10年内游览所有5A级景区,费用为211204元.

基于旅行商路径与任务指派的风力发电设备检修问题研究

针对风力发电设备地理分布广、检修费时费力的现状,借鉴运筹学方法对其进行科学合理规划,有助于企业节省成本、提高效率.将检修过程中人员物资的往返运送归结为旅行商问题(TSP),将各检修小组与各待检修点的分配归结为指派问题(AP),从而提出基于TSP路径与任务指派的风力发电设备检修问题(MWPEP).结合运筹学知识,给出MWPEP问题的两种建模方法:一是根据TSP路径及任务指派,给出MWPEP问题的基于相邻节点时间递推关系的优化模型;二是基于0-1型决策变量,给出MWPEP问题基于到达时间范围约束的0-1规划模型.最后通过算例给出依据两种模型的分析和计算过程,对MWPEP问题的研究,扩展了运筹学方法的应用,为解决实际生产生活中的类似问题提供了新的思路和方法 .

构建国土空间规划体系背景下北京控规环评优化探索

2019年以来,我国明确要构建“多规合一”“五级三类”国土空间规划体系,由“单一技术型空间规划”转变为“统筹多元诉求,空间、时间多维度的利益协调型规划”,规划编制应统筹考虑社会、经济、生态、安全、文化等诸多因素,纳入环境影响评价、交通影响评价、水影响评价等意见。北京市控制性详细规划环境影响评价在国家规划体系发生重大调整的背景下,存在一些问题,比如与规划编制内容不吻合、与产业园区规划环评界限不明、规划调整建议依据不充分、建设项目环境影响评价简化“落地难”等,提出了明确规划环境影响评价法律地位、规划前期融入环境影响评价技术、完善建设项目环评简化依据等优化路径,进一步推动优化营商环境。

基于改进自适应遗传算法的点焊机器人TSP路径规划

基于TSP问题建立焊点路径数学模型。同时为改善遗传算法自身收敛速度慢问题,采取适应度计算评估、适应度比例选择步骤;为了提高计算速度与避免局部最优缺陷,采用自适应交叉、变异算子,以及加入进化逆转步骤操作来提升算法全局计算和搜索能力。最后利用RobotStuidio仿真软件建立点焊工艺加工站,进一步检验算法在实际编程中的应用。

基于改进禁忌搜索算法的药房批量取药路径规划研究

针对药房批量取药这一现实问题,在设计药房整体环境布局和引入路径规划算法的基础上,提出以重量加权的距离为目标的旅行商问题TSP(Traveling Salesman Problem)。建立一个混合整数规划模型,使用禁忌搜索算法进行模型求解,使用曼哈顿距离作为两点之间距离,在禁忌长度等参数设置上使用动态自适应方法,并在算法中加入扰动方法,避免算法陷入局部最优,增加搜索目标的多样性。最后使用JAVA进行了仿真模拟实验,可视化结果验证了算法的可行性和有效性。

基于TSP问题思想的城市轨道交通乘务排班计划研究

乘务排班计划作为城市轨道交通运输组织与规划中的重要一步,其编制合理性关系着列车开行方案、列车运行图以及车底运用计划能否高效实现。将TSP问题思想应用于城市轨道交通排班计划的核心步骤中,考虑乘务规则、时间标准、运营限制等影响因素,以乘务工作班内乘务作业段间接续时间最小为目标构建乘务排班计划优化模型。将乘务作业段转化为附带时空属性的节点,节点间接续关系转化为弧,从而将乘务工作班的生成转化为类TSP问题。为减少搜索解时的盲目性与匹配时的无效性增加选择节点的方式,设置虚拟点和双路径表来划分乘务工作班,并设计蚁群算法求解。以某地铁线路为实例进行分析,结果显示平均接续时间为70.97 min,平均工作时间为246.14 min,平均工作班时间为307.11 min,证明该模型与算法的有效性。

美国联邦政府“节俭储蓄计划”(TSP)介绍及评价

美国的"节俭储蓄计划"(the Thrift Savings Plan,简称TSP计划)是针对美国联邦雇员及军职人员设立的一项退休储蓄和投资计划。该计划由美国国会1986年通过的《联邦雇员退休制度法案》规定实施,发展至今已经成为目前世界上最大的401(K)型的制度安排。作为联邦雇员养老保障体系的一个重要支柱,TSP计划为提高联邦雇员的养老金替代率贡献了重要力量;不仅如此,TSP计划作为当前世界上第二支柱养老金制度运行成功的案例之一,其投资管理模式尤其值得学习借鉴。目前,TSP计划提供了五支单项基金和五支生命周期基金供参加人选择,而且一直以来TSP基金的投资收益值得称赞。TSP计划在投资管理上的成功与如下制度设计相关:投资行为与潜在政治干预分离,保护非专业人士的投资行为与利益,确保参加人的投资收益。

基于TSP优化和潮流校核的220 kV电网远景网架构建方法

电网目标网架是规划方案适应性分析和电力设施布局规划的基础。220 kV电网网架结构相对复杂,电网安全可靠性要求高,目前缺乏典型的网架模式作为参考,因此如何构建安全经济的220 kV电网远景网架亟待研究。基于此,提出了一种基于TSP优化和潮流校核的220 kV电网远景网架构建方法。该方法通过变电站分群和TSP优化寻找得到220 kV网架构建的最短路径,保障了所构建网架的经济性。通过交直流潮流N-1校核确定该路径上的线路导线型号和回数,保障了所构建网架能够通过N-1安全校核,进而保障了所构建网架的安全可靠性。我国某区域电网的仿真算例结果表明,所提方法能够构建安全经济的220 kV网架,具有工程实际应用价值。

求解TSP的变邻域蝙蝠算法

针对现有蝙蝠算法易早熟、收敛不精等问题,提出一种变邻域蝙蝠算法。通过结合三种变邻域策略,提升算法局部搜索能力,同时加入惯性权重,均衡算法前期的全局搜索能力和后期的局部搜索能力。结果表明提出的变邻域蝙蝠算法能够有效地解决TSP问题,且效果比其他传统算法更优。

TSP规划模型在文本碎纸片拼接复原问题中的应用

研究纵横切双面英文信息碎纸片的拼接复原问题,引入碎纸片正反匹配距离的概念,建立多旅行商的TSP规划模型,运用MATLAB对纵横切双面碎纸片进行拼接复原,得到复原序列和图像,且该算法不需要人工干预,印证该算法的正确性。

遗传算法优化打孔机器人轨迹规划

目的是为了研究打孔机器人加工时的轨迹规划,打孔过程中有两段轨迹需要进行轨迹规划,分别是打孔阶段和进给阶段,两个阶段中主要研究的是进给阶段的轨迹规划,方法上提出了一种基于遗传算法的轨迹规划,将进给阶段轨迹模型转化为TSP模型,采用最小圆算法区分大小区域TSP模型。大区域的TSP模型可以分解为多个小区域的TSP模型,则首先采用遗传算法进行小区域TSP轨迹规划,第一步进行编码初始化种群样本,第二步求出每个个体适应度,第三步进行选择操作,交叉操作,变异操作,如果达到最大迭代次数则输出最优个体,否则返回第三步进行循环。利用暴力穷举法优化小区域模型。大区域TSP模型轨迹规划可以分解为多个小区域模型轨迹规划的累加。通过仿真实现进行验证。结果表明,利用遗传算法下轨迹规划完成度较好。结论是利用遗传算法优化后的轨迹规划对比传统轨迹规划效果好,适用范围广。

基于TSP问题的远航程无人水下航行器路径规划研究

针对远航程无人水下航行器的路径规划问题,本文提出了一种基于旅行商(TSP)问题的路径规划的新方法。阐述了TSP问题的基本原理,并采用了模拟退火算法和遗传算法进行了仿真研究,获得较好的仿真结果。

卷烟零售终端走访路径规划算法集成与应用

为解决卷烟零售终端走访业务领域中的多点路径规划问题,对现有路径规划算法进行归纳和总结。提出了一种Top-K群体算法集成方法将多种路径规划算法进行组合优化及集成应用,以克服单个算法存在的固有缺陷,获得更优的规划结果。以沈阳市卷烟零售终端为研究对象进行15.6万次模拟实验。结果表明:Top-K比6种原算法获得的路径平均缩短约9.82%,算法优化提升效果显著,能够获得更好的路径规划结果,具有更好的可靠性和通用性。基于Top-K开发了一种适用于烟草零售客户走访的路径规划微服务,并在沈阳烟草进行实际应用。过去1年时间里,该服务使用频次超过1.7万次,路径规划总长度超过15.6万公里,具有良好的实用性和通用性。

基于改进收敛因子的CGWO无人机路径规划

在无人机(UAVs,Unmanned Aerial Vehicles)集群应用场景中,无人机集群间面临簇间通信受阻的情况。常规的解决方案是利用无人机收集簇群数据,并将问题转化为TSP(Traveling Salesman Problem)问题。该文研究无人机数据采集过程中的路径规划问题。在灰狼算法(GWO)的基础上提出改进收敛因子的CGWO算法,通过改进收敛因子提高算法的全局搜索能力,使之能适用于无人机数据采集过程中的路径规划问题。通过MATLAB仿真实验表明,CGWO算法相比于GWO算法具有更好的搜索性能。在进行30个采集节点的实验中,CGWO算法相比于现有的改进GWO算法将最短距离缩短27.24%。

多无人机巡航算法研究

无人机(Unmanned Aerial Vehicle,UAV)硬件技术的快速发展使其在许多领域得到广泛使用。当任务区域较多时,受到电量限制,无人机单次巡航难以完成全部任务,需要多架无人机共同协作。文章比较了之前的相关研究,提出一种综合聚类和改进遗传算法的路径规划策略,并通过仿真,对比不同算法的效果,为进一步的工作提供帮助。

基于蚁群算法的多AUV路径规划仿真研究

多AUV路径规划是一种典型的带约束组合优化问题,如果采用传统的方法求解效果并不理想。蚁群算法是对自然界中蚂蚁在寻找食物过程中所表现出来的智能行为的一种模拟,它非常善于处理带约束的大规模复杂组合优化问题。应用蚁群算法结合TSP问题来为一群AUV进行路径规划,寻找最短且安全的路径。算法分为两部分:1)路径优化:使所有AUV的总路程最小化;2)路径校核:检查是否存在潜在的静态或动态碰撞。最后以三个AUV的情形为例对算法加以了验证,仿真结果表明该方法耗时短、效率高,为求解多AUV路径规划问题提供了一个高效解决方案。

基于蚁群算法的白车身焊接机器人路径优化研究

针对目前焊接机器人路径规划缺乏理论依据的现状,本文提出了将路径规划问题抽象为TSP问题的数学模型解决思路。文章分析研究了该数学模型的计算方法,运用蚁群算法作为计算引擎,编写了相应的Matlab优化程序。结果证明,该算法不仅有效,而且具有较快的计算速度。

基于粒子群-蚁群融合算法的移动机器人路径优化规划

基于TSP问题,提出了一种基于粒子群-蚁群算法相互融合的综合优化算法对移动机器人路径规划问题进行研究.通过粒子群算法对全局路径实施粗略搜索,获得部分次优解,在获得次优解的路径上进行信息素分布,再采用蚁群算法进行精确搜索,得到路径规划的最优解.实验结果表明:粒子群-蚁群融合优化算法在路径寻优上优于蚁群算法及粒子群算法.

基于遗传算法的直角坐标式排牙机器人路径规划

针对多目标抓取的直角坐标排牙机器人的路径规划问题,研究了直角坐标排牙机器人的结构及抓取V型块的过程,按照最短行程的标准提出了优化问题,建立了实体的数学模型1,参考典型的TSP问题型将目标问题转化成类似TSP(traveling salesman problem)问题,并将模型1转化成抽象的数学模型2,并采用遗传算法的相关理论进行了求解,求解出了收敛的最优值,找到了最优的路径,具有充分的可行性.