期刊文献+
共找到18篇文章
< 1 >
每页显示 20 50 100
K-DSA for the multiple traveling salesman problem 被引量:1
1
作者 TONG Sheng QU Hong XUE Junjie 《Journal of Systems Engineering and Electronics》 SCIE EI CSCD 2023年第6期1614-1625,共12页
Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering ... Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering method to divide all cities into several categories based on the center of various samples;the large-scale MTSP is divided into multiple separate traveling salesman problems(TSPs),and the TSP is solved through the DSA.The proposed algorithm adopts a solution strategy of clustering first and then carrying out,which can not only greatly reduce the search space of the algorithm but also make the search space more fully explored so that the optimal solution of the problem can be more quickly obtained.The experimental results from solving several test cases in the TSPLIB database show that compared with other related intelligent algorithms,the K-DSA has good solving performance and computational efficiency in MTSPs of different scales,especially with large-scale MTSP and when the convergence speed is faster;thus,the advantages of this algorithm are more obvious compared to other algorithms. 展开更多
关键词 k-means clustering donkey and smuggler algorithm(DSA) multiple traveling salesman problem(mtsp) multiple depots and closed paths.
下载PDF
路径交叉测绘任务规划问题
2
作者 王维 张开放 《陆军工程大学学报》 2024年第5期49-56,共8页
不同于传统多旅行商问题,小型飞机测绘任务规划问题的每个测绘目标需要测绘多个测绘载荷,同时多次测绘间要有时间间隔,称之为路径交叉的多旅行商路径规划问题。针对点目标测绘任务场景,将最少飞机数量的求解目标转化为求解最短航行路径... 不同于传统多旅行商问题,小型飞机测绘任务规划问题的每个测绘目标需要测绘多个测绘载荷,同时多次测绘间要有时间间隔,称之为路径交叉的多旅行商路径规划问题。针对点目标测绘任务场景,将最少飞机数量的求解目标转化为求解最短航行路径。在采用遗传算法求解最短路径的基础上,结合探测载荷约束、探测任务时长约束等条件,进一步规划出最优的调度方案。针对点目标和区域目标测绘任务规划问题,考虑各机场测绘任务工作量的均衡,定义测绘工作量指标为每个机场完成的测绘目标点和目标道路的数目,求解调度策略和飞机数量。在此基础上求解均衡性,使3个机场探测的目标点和目标道路数量相当。结果表明,所提方案兼顾了测绘代价与任务分配的均衡性。 展开更多
关键词 多旅行商问题 遗传算法 组合优化 多目标规划 测绘任务规划 均衡度
下载PDF
基于双层规划的装备保障优化预调度
3
作者 胡志刚 楼京俊 史跃东 《现代防御技术》 北大核心 2024年第5期147-155,共9页
装备保障影响作战任务完成质量甚至直接关系任务成败,装备保障优化调度是提升装备保障系统效益的关键。针对装备保障系统双层决策和组合优化的特点,提出一种基于双层规划的装备保障优化预调度模型。分析装备保障系统运行过程和建模框架... 装备保障影响作战任务完成质量甚至直接关系任务成败,装备保障优化调度是提升装备保障系统效益的关键。针对装备保障系统双层决策和组合优化的特点,提出一种基于双层规划的装备保障优化预调度模型。分析装备保障系统运行过程和建模框架;结合组合优化问题,建立双层规划模型,上层为粗粒度层,采用MTSP(multiple travelling salesman problem)方法,下层为细粒度层,采用JSP(job-shop scheduling problem)方法;通过改进MTSP算法设计和迁移JSP算法描述构建双层迭代算法进行模型求解。算例分析表明:该方法在大规模系统优化调度中具有结构开放性和参数适应性。 展开更多
关键词 装备保障 双层规划 预调度 大规模优化调度 改进mtsp
下载PDF
求解加权MTSP问题的CUDA并行群智能方法 被引量:2
4
作者 苏守宝 赵威 李智 《郑州大学学报(工学版)》 CAS 北大核心 2021年第6期34-41,共8页
针对混合迭代算法执行时间长的问题,根据粒子群优化(PSO)算法和蚁群优化(ACO)算法的并行特点,结合其在GPU上并行化实现技术和编程优化技巧,提出一种基于CUDA的粒子群聚类蚁群的并行群智能混合方法GPSO-AC。该算法利用GPU的多个流处理器(... 针对混合迭代算法执行时间长的问题,根据粒子群优化(PSO)算法和蚁群优化(ACO)算法的并行特点,结合其在GPU上并行化实现技术和编程优化技巧,提出一种基于CUDA的粒子群聚类蚁群的并行群智能混合方法GPSO-AC。该算法利用GPU的多个流处理器(SM)和单指令多线程(SIMT)的指令架构,将GPSO-AC算法在运行中的独立个体的搜索过程同时并行执行,在保证算法精度的基础上,加快混合迭代法的执行速度。考虑到实际场景中旅行商在每个路段上各项开销不同,可以抽象为每段路程区间上都有一个与之对应的代价,将路程代价考虑到MTSP问题中。采用TSPLIB库中6个测试数据集,将GPSO-AC与PSO-AC、TPHA、K-means-AC等算法进行比较,并进一步探讨了加入代价均衡约束后对加权MTSP问题最优解收敛性能的影响。使用chn31数据集上不同旅行商数时,GPSO-AC在不考虑代价均衡、代价均衡约束、加权代价均衡的情况下的代价标准差分别为1165.26、54.97、6.74。结果表明:在求解一般MTSP问题及其衍生加权、代价均衡MSTP问题上,GPSO-AC在执行速度和收敛精度上均优于CPU串行算法,且随着模型规模增加,其速度优势更加明显。 展开更多
关键词 多旅行商问题 CUDA并行算法 代价均衡 粒子群聚类 蚁群算法
下载PDF
基于遗传算法的无人机编队高速公路巡检任务规划方法 被引量:3
5
作者 李彦强 王建辉 《市政技术》 2023年第11期67-73,共7页
利用无人机编队对高速公路进行巡检具有不占用道路资源、不受交通流量和天气影响等优点,能够有效提升路况信息服务水平。针对无人机编队对高速公路进行巡检的任务规划需求,利用多旅行商问题对其进行建模,构建了基于道路路网条件和巡检... 利用无人机编队对高速公路进行巡检具有不占用道路资源、不受交通流量和天气影响等优点,能够有效提升路况信息服务水平。针对无人机编队对高速公路进行巡检的任务规划需求,利用多旅行商问题对其进行建模,构建了基于道路路网条件和巡检任务的约束条件,并以执行任务的最短总路径为优化目标,利用遗传算法对模型进行求解,从而获得了最优的任务规划方案。仿真试验结果表明,该方法能够获得高质量的任务规划方案且算法实时性较高,具有较好的应用前景。 展开更多
关键词 遗传算法 无人机 高速公路巡检 任务规划 多旅行商问题
下载PDF
基于遗传算法的一类多旅行商问题研究 被引量:10
6
作者 王海龙 周辉仁 魏颖辉 《计算机应用》 CSCD 北大核心 2009年第1期119-122,共4页
旅行商问题是一个经典的NP完全问题,对多人旅行商问题的求解则更具有意义。以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准,而对所有旅行商路径最大值最小的多旅行商一类问题研究的相对较少。针对所有旅行商... 旅行商问题是一个经典的NP完全问题,对多人旅行商问题的求解则更具有意义。以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准,而对所有旅行商路径最大值最小的多旅行商一类问题研究的相对较少。针对所有旅行商路径最大值最小的多旅行商一类问题,用遗传算法优化,并且提出了矩阵解码方法。该方法适于距离对称和非对称的多旅行商问题求解。以距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较。 展开更多
关键词 遗传算法 多旅行商问题 优化 解码方法
下载PDF
多目标旅行商问题的模拟植物生长算法求解 被引量:15
7
作者 郗莹 马良 戴秋萍 《计算机应用研究》 CSCD 北大核心 2012年第10期3733-3735,共3页
针对多目标旅行商问题,提出了一种基于模拟植物生长的优化算法。该算法将Deb等人提出的非支配排序及构造偏序集等方法用于模拟植物生长的过程中,克服了模拟植物生长算法搜索空间过大及收敛性不够理想的缺点。基于该算法的核心思想,用MAT... 针对多目标旅行商问题,提出了一种基于模拟植物生长的优化算法。该算法将Deb等人提出的非支配排序及构造偏序集等方法用于模拟植物生长的过程中,克服了模拟植物生长算法搜索空间过大及收敛性不够理想的缺点。基于该算法的核心思想,用MATLAB编程实现,对参考文献的算例进行仿真测试。与其他算法比较,获得了满意的结果。 展开更多
关键词 多目标旅行商 模拟植物生长算法 非支配排序 偏序集
下载PDF
热轧计划中的多旅行商问题及其计算方法 被引量:16
8
作者 黄可为 汪定伟 《计算机应用研究》 CSCD 北大核心 2007年第7期43-45,57,共4页
针对热轧批计划问题进行了MTSP(多旅行商问题)建模,并对该问题设计了混合遗传算法,经某大型钢厂实例数据进行了仿真测试。计算结果表明,该算法给出了较优的轧制批计划方案,解决了热轧轧制批计划的编制问题。
关键词 多旅行商问题 数学模型 热轧轧制计划 遗传算法
下载PDF
基于GA的最小旅行时间的多旅行商问题研究 被引量:6
9
作者 周辉仁 唐万生 魏颖辉 《计算机应用研究》 CSCD 北大核心 2009年第7期2526-2529,共4页
以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准,而对最小完成时间的多旅行商一类问题研究得相对较少。针对所有旅行商最小完成时间的多旅行商一类问题,用遗传算法进行优化,且提出了矩阵解码方法。以距离非... 以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准,而对最小完成时间的多旅行商一类问题研究得相对较少。针对所有旅行商最小完成时间的多旅行商一类问题,用遗传算法进行优化,且提出了矩阵解码方法。以距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较,适于距离对称和非对称的多旅行商问题求解。 展开更多
关键词 遗传算法 多旅行商问题 最小完成时间 解码方法
下载PDF
求解加热炉调度的改进修复式约束满足算法
10
作者 赵艳艳 李铁克 王柏琳 《计算机工程与应用》 CSCD 2012年第18期23-26,56,共5页
针对钢铁生产中加热炉调度问题,考虑炉容受限的情况,以最小化板坯的Makespan和最小化总在炉加工时间为目标建立问题的多目标优化模型,将其归结为多旅行商问题。针对问题的NP-难特性,提出一种改进的修复式约束满足算法求解。松弛炉容约... 针对钢铁生产中加热炉调度问题,考虑炉容受限的情况,以最小化板坯的Makespan和最小化总在炉加工时间为目标建立问题的多目标优化模型,将其归结为多旅行商问题。针对问题的NP-难特性,提出一种改进的修复式约束满足算法求解。松弛炉容约束得到初始调度,在检测冲突变量并构造冲突板坯的可替换加热炉集合的基础上,以开工时间偏移最小规则为冲突板坯重新指派加热炉,得到可行的调度方案。数据实验验证了模型和算法的可行性和有效性。 展开更多
关键词 调度 炉容约束 修复式约束满足 多旅行商
下载PDF
求解多旅行商问题的改进分组遗传算法 被引量:36
11
作者 王勇臻 陈燕 于莹莹 《电子与信息学报》 EI CSCD 北大核心 2017年第1期198-205,共8页
该文针对总路径长度最小的多旅行商问题,提出一种改进分组遗传算法。在该算法中,设计了一种有序分组编码,采用新编码方式的个体与多旅行商问题有效解之间具有一一对应的关系。为了减少算法的运行时间,根据编码的特点构造了一种快速交叉... 该文针对总路径长度最小的多旅行商问题,提出一种改进分组遗传算法。在该算法中,设计了一种有序分组编码,采用新编码方式的个体与多旅行商问题有效解之间具有一一对应的关系。为了减少算法的运行时间,根据编码的特点构造了一种快速交叉算子。同时,结合贪婪算法和2-opt算法设计了一种新的局部搜索算子,以提高算法的收敛精度。实验结果分析表明,所提算法能够有效地解决多旅行商问题,具有可靠的全局收敛性,较高的计算效率。 展开更多
关键词 分组遗传算法 多旅行商问题 编码 2-opt算法
下载PDF
放射状路网条件下动车组运用优化研究 被引量:10
12
作者 陈旭 李海鹰 +1 位作者 王莹 贺英奇 《铁道学报》 EI CAS CSCD 北大核心 2017年第11期23-29,共7页
针对以大型枢纽为中心的高速铁路放射状路网,提出动车组的混杂运用方式,考虑动车组在枢纽内不同车站、同一车站内不同高速铁路线路间进行调拨。将动车组运用问题转化为多旅行商问题,选取蚁群算法进行求解,通过引入有限后向运行线数量和... 针对以大型枢纽为中心的高速铁路放射状路网,提出动车组的混杂运用方式,考虑动车组在枢纽内不同车站、同一车站内不同高速铁路线路间进行调拨。将动车组运用问题转化为多旅行商问题,选取蚁群算法进行求解,通过引入有限后向运行线数量和分析蚁群算法中参数取值来提高收敛速度和求解质量。以上海枢纽的一周运行线进行案例分析,结果表明动车组混杂运用能够减少动车组的运用数量和检修次数,降低运营成本。在当前运行图中,后向运行线数量为275条,参数ρ取值为0.7,参数α取值大于β且取值适中时,收敛速度和计算结果相对较好。 展开更多
关键词 放射状路网 动车组混杂运用 多旅行商问题 蚁群算法 参数分析
下载PDF
航空集群多目标群攻击路径规划仿真研究 被引量:9
13
作者 徐国训 梁晓龙 +1 位作者 张佳强 王维佳 《计算机仿真》 北大核心 2017年第6期66-70,324,共6页
研究航空集群多目标群对地攻击问题,是实现航空集群作战的重要内容。其中确定对地多目标群攻击的最优路径是难点问题,根据集群多目标群攻击路径规划的研究现状,建立了航空集群多目标群攻击路径规划模型,并将对地多目标群攻击的路径规划... 研究航空集群多目标群对地攻击问题,是实现航空集群作战的重要内容。其中确定对地多目标群攻击的最优路径是难点问题,根据集群多目标群攻击路径规划的研究现状,建立了航空集群多目标群攻击路径规划模型,并将对地多目标群攻击的路径规划问题转化为多旅行商问题(MTSP)。提出基于MTSP-GA的模型解算方法,分别得到单基地和双基地起飞条件下集群最优攻击路径规划结果。仿真结果表明,所提出的基于MTSP-GA的模型解算方法能快速的得到集群最优攻击路径结果,可适用于多基地和多目标群下的集群攻击路径规划。 展开更多
关键词 航空集群 多目标群攻击 遗传算法 多旅行商问题
下载PDF
基于自组织优化算法的一类多旅行商问题 被引量:4
14
作者 李天龙 吕勇哉 《计算机应用》 CSCD 北大核心 2010年第2期458-460,共3页
多旅行商问题作为旅行商问题的一个扩展,是一个经典的组合优化问题,具有更高的复杂性,也具有更广泛的实际意义。针对每个旅行商允许经过的城市数有上限的多旅行商问题,通过引入虚拟城市把多旅行商问题转化为单旅行商问题,并且应用自组... 多旅行商问题作为旅行商问题的一个扩展,是一个经典的组合优化问题,具有更高的复杂性,也具有更广泛的实际意义。针对每个旅行商允许经过的城市数有上限的多旅行商问题,通过引入虚拟城市把多旅行商问题转化为单旅行商问题,并且应用自组织优化算法进行了求解。虚拟城市局部适值的定义很好地处理了此类问题的能力约束,针对多旅行商问题的实例进行的仿真表明自组织优化算法可以很好地求解此类问题。 展开更多
关键词 多旅行商问题 虚拟城市 自组织优化算法 局部适值
下载PDF
基于改进蚁群算法的铁路乘务交路计划的编制 被引量:5
15
作者 王东先 孟学雷 +2 位作者 乔俊 汤霖 焦志臻 《计算机应用》 CSCD 北大核心 2019年第9期2749-2756,共8页
针对提高铁路乘务交路计划编制质量和效率的问题,将乘务交路计划编制问题抽象为单基地、均衡行驶路程的多旅行商问题(MTSP),引入均衡因子,建立了以乘务交路用时少和子乘务交路间任务均衡为目标的数学模型。针对该模型提出了一种双重策... 针对提高铁路乘务交路计划编制质量和效率的问题,将乘务交路计划编制问题抽象为单基地、均衡行驶路程的多旅行商问题(MTSP),引入均衡因子,建立了以乘务交路用时少和子乘务交路间任务均衡为目标的数学模型。针对该模型提出了一种双重策略蚁群优化算法,该算法首先构建满足时空约束的解空间,分别对乘务区段节点和接续路径设置信息素浓度,然后采用双重策略状态的转移概率,使蚂蚁遍历所有乘务区段,最终找到符合乘务约束规则的子乘务交路。最后运用广深线城际铁路数据对设计的模型及算法进行检验,经与遗传算法的实验结果对比分析表明:在相同的模型条件下,运用双重策略蚁群优化算法编制的乘务交路计划乘务交路个数减少了约21.74%、乘务交路总时长降低了约5.76%、交路超劳率为0。运用所设计的模型和算法编制乘务交路计划能够减少乘务计划交路时长,均衡工作量,避免产生超劳交路。 展开更多
关键词 铁路 乘务交路计划 均衡因子 多旅行商问题 双重策略蚁群算法
下载PDF
基于改进蚁群算法的铁路乘务排班计划编制 被引量:4
16
作者 王东先 孟学雷 +2 位作者 何国强 孙慧萍 王喜栋 《计算机应用》 CSCD 北大核心 2019年第12期3678-3684,共7页
为了提升铁路乘务排班计划编制的质量和效率,将乘务排班计划编制问题抽象为单基地、考虑中途休息的多旅行商问题(MTSP),建立以排班周期最小、乘务交路间冗余接续时间分布最均衡为优化目标的单一循环乘务排班计划数学模型,并针对该模型... 为了提升铁路乘务排班计划编制的质量和效率,将乘务排班计划编制问题抽象为单基地、考虑中途休息的多旅行商问题(MTSP),建立以排班周期最小、乘务交路间冗余接续时间分布最均衡为优化目标的单一循环乘务排班计划数学模型,并针对该模型提出了一种启发式修正蚁群算法。首先,构建满足时空约束的解空间,分别对乘务交路节点和接续路径设置信息素浓度;然后,确定基于修正的启发式信息,规定蚂蚁按乘务交路顺序依次出发,使蚂蚁遍历所有乘务交路;最后,从不同的乘务排班方案中选择最优的排班计划。以广深城际铁路为例对所提模型及算法进行验证,并与粒子群算法进行对比。实验结果表明:在相同的模型条件下,采用启发式修正蚁群算法编制的乘务排班计划平均月工时降低了8.5%,排班周期降低了9.4%,乘务人员超劳率为0。所提模型和算法能够压缩乘务排班周期,降低乘务成本,均衡工作量,避免乘务人员超劳。 展开更多
关键词 铁路 乘务排班计划 多旅行商问题 冗余时间 启发式修正蚁群算法
下载PDF
A novel method for solving the multiple traveling salesmen problem with multiple depots 被引量:2
17
作者 HOU MengShu LIU DaiBo 《Chinese Science Bulletin》 SCIE CAS 2012年第15期1886-1892,共7页
Multi-traveling salesman problem(MTSP) is an extension of traveling salesman problem,which is a famous NP hard problem,and can be used to solve many real world problems,such as railway transportation,routing and pipel... Multi-traveling salesman problem(MTSP) is an extension of traveling salesman problem,which is a famous NP hard problem,and can be used to solve many real world problems,such as railway transportation,routing and pipeline laying.In this paper,we analyze the general properties of MTSP,and find that the multiple depots and closed paths in the graph is a big issue for MTSP.Thus,a novel method is presented to solve it.We transform a complicated graph into a simplified one firstly,then an effective algorithm is proposed to solve the MTSP based on the simplified results.In addition,we also propose a method to optimize the general results by using 2-OPT.Simulation results show that our method can find the global solution for MTSP efficiently. 展开更多
关键词 多旅行商问题 仓库 中期战略 NP难问题 mtsp 现实世界 铁路运输 管道铺设
原文传递
自动驾驶条件下共享车辆车队规模 被引量:2
18
作者 王冠 杨超 +1 位作者 张英杰 陈海林 《综合运输》 2019年第2期48-53,共6页
随着自动驾驶技术的发展和普及,未来以自动驾驶车辆替代传统有人驾驶私家车辆成为大势所趋,本文研究的目标是提出一种解决小规模自动驾驶共享车辆(Shared Autonomous Vehicle, SAV)车队规模的方法,并进行实际案例分析。使用的数据集是... 随着自动驾驶技术的发展和普及,未来以自动驾驶车辆替代传统有人驾驶私家车辆成为大势所趋,本文研究的目标是提出一种解决小规模自动驾驶共享车辆(Shared Autonomous Vehicle, SAV)车队规模的方法,并进行实际案例分析。使用的数据集是上海市50辆新能源私家车一年的轨迹数据,使用此部分出行需求,给出了计算两次出行是否可以衔接的具体方法,得到衔接矩阵。然后将求解最小车队规模问题转化为求解多旅行商问题(Multiple Travelling Salesman Problem, MTSP)的最短路问题,并证明两者具有等价性。论文提出使用排序遗传算法对此问题进行求解,使用5种常见的排序交叉算子分别验证求解质量,得到OX1交叉算子的质量最优。最后选择OX1交叉算子计算出行需求数排名前20天的SAV的最小规模,得到SAV的平均替代率为2.4。即在本研究中,一辆SAV平均可以替代2.4辆传统私家车,为未来自动驾驶技术普及后,SAV的车队规模问题提供参考。 展开更多
关键词 自动驾驶共享车辆 最小车队规模 多旅行商问题 遗传算法
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部