-
题名求解多旅行商问题的改进分组遗传算法
被引量：34
- 1
-
-
作者
王勇臻
陈燕
于莹莹
-
机构
大连海事大学交通运输管理学院
-
出处
《电子与信息学报》
EI
CSCD
北大核心
2017年第1期198-205,共8页
-
基金
国家科技支撑计划(2014BAH24F04)
国家自然科学基金(71271034)~~
-
文摘
该文针对总路径长度最小的多旅行商问题,提出一种改进分组遗传算法。在该算法中,设计了一种有序分组编码,采用新编码方式的个体与多旅行商问题有效解之间具有一一对应的关系。为了减少算法的运行时间,根据编码的特点构造了一种快速交叉算子。同时,结合贪婪算法和2-opt算法设计了一种新的局部搜索算子,以提高算法的收敛精度。实验结果分析表明,所提算法能够有效地解决多旅行商问题,具有可靠的全局收敛性,较高的计算效率。
-
关键词
分组遗传算法
多旅行商问题
编码
2-opt算法
-
Keywords
Grouping Genetic Algorithm （GGA）
multiple traveling salesman problem （mtsp）
Encoding
2-opt algorithm
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名放射状路网条件下动车组运用优化研究
被引量：10
- 2
-
-
作者
陈旭
李海鹰
王莹
贺英奇
-
机构
北京交通大学轨道交通控制与安全国家重点实验室
北京交通大学交通运输学院
-
出处
《铁道学报》
EI
CAS
CSCD
北大核心
2017年第11期23-29,共7页
-
基金
中央高校基本科研业务费(2017JBM031)
中国铁路总公司科技研究开发计划(2015F020)
-
文摘
针对以大型枢纽为中心的高速铁路放射状路网,提出动车组的混杂运用方式,考虑动车组在枢纽内不同车站、同一车站内不同高速铁路线路间进行调拨。将动车组运用问题转化为多旅行商问题,选取蚁群算法进行求解,通过引入有限后向运行线数量和分析蚁群算法中参数取值来提高收敛速度和求解质量。以上海枢纽的一周运行线进行案例分析,结果表明动车组混杂运用能够减少动车组的运用数量和检修次数,降低运营成本。在当前运行图中,后向运行线数量为275条,参数ρ取值为0.7,参数α取值大于β且取值适中时,收敛速度和计算结果相对较好。
-
关键词
放射状路网
动车组混杂运用
多旅行商问题
蚁群算法
参数分析
-
Keywords
radial RSH network
mixed EMU operation mode
multiple traveling salesman problem(mtsp)
ant colony algorithm(ACA)
parameter analysis
-
分类号
U238
[交通运输工程—道路与铁道工程]
-
-
题名航空集群多目标群攻击路径规划仿真研究
被引量：9
- 3
-
-
作者
徐国训
梁晓龙
张佳强
王维佳
-
机构
空军工程大学空管领航学院
-
出处
《计算机仿真》
北大核心
2017年第6期66-70,324,共6页
-
基金
国家自然科学基金面上资助项目(61472442
61472443)
+1 种基金
陕西省自然科学技术研究发展计划资助项目(2013JQ8042
2016JM6071)
-
文摘
研究航空集群多目标群对地攻击问题,是实现航空集群作战的重要内容。其中确定对地多目标群攻击的最优路径是难点问题,根据集群多目标群攻击路径规划的研究现状,建立了航空集群多目标群攻击路径规划模型,并将对地多目标群攻击的路径规划问题转化为多旅行商问题(MTSP)。提出基于MTSP-GA的模型解算方法,分别得到单基地和双基地起飞条件下集群最优攻击路径规划结果。仿真结果表明,所提出的基于MTSP-GA的模型解算方法能快速的得到集群最优攻击路径结果,可适用于多基地和多目标群下的集群攻击路径规划。
-
关键词
航空集群
多目标群攻击
遗传算法
多旅行商问题
-
Keywords
Aircraft swarms
Multi - target group attack
Genetic algorithm （GA）
multiple traveling salesman problem （mtsp）
-
分类号
TP391.9
[自动化与计算机技术—计算机应用技术]
-
-
题名基于GA的最小旅行时间的多旅行商问题研究
被引量：6
- 4
-
-
作者
周辉仁
唐万生
魏颖辉
-
机构
天津大学系统工程研究所
辽宁科技学院管理系
-
出处
《计算机应用研究》
CSCD
北大核心
2009年第7期2526-2529,共4页
-
基金
辽宁省教育厅科研课题资助项目(20060439)
-
文摘
以往对求解多人旅行商问题的研究局限于以所有旅行商路径总和最小为优化标准,而对最小完成时间的多旅行商一类问题研究得相对较少。针对所有旅行商最小完成时间的多旅行商一类问题,用遗传算法进行优化,且提出了矩阵解码方法。以距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较,适于距离对称和非对称的多旅行商问题求解。
-
关键词
遗传算法
多旅行商问题
最小完成时间
解码方法
-
Keywords
genetic algorithm
multiple traveling salesman problem （mtsp）
minimum completion time
decoding method
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
-
题名基于遗传算法的无人机编队高速公路巡检任务规划方法
被引量：2
- 5
-
-
作者
李彦强
王建辉
-
机构
广东交科检测有限公司
广东省路桥建设发展有限公司广贺分公司
-
出处
《市政技术》
2023年第11期67-73,共7页
-
文摘
利用无人机编队对高速公路进行巡检具有不占用道路资源、不受交通流量和天气影响等优点,能够有效提升路况信息服务水平。针对无人机编队对高速公路进行巡检的任务规划需求,利用多旅行商问题对其进行建模,构建了基于道路路网条件和巡检任务的约束条件,并以执行任务的最短总路径为优化目标,利用遗传算法对模型进行求解,从而获得了最优的任务规划方案。仿真试验结果表明,该方法能够获得高质量的任务规划方案且算法实时性较高,具有较好的应用前景。
-
关键词
遗传算法
无人机
高速公路巡检
任务规划
多旅行商问题
-
Keywords
genetic algorithm
UAV
expressway patrol inspection
task planning
multiple traveling salesman problem(mtsp)
-
分类号
TM75
[电气工程—电力系统及自动化]
-
-
题名基于自组织优化算法的一类多旅行商问题
被引量：3
- 6
-
-
作者
李天龙
吕勇哉
-
机构
浙江大学智能系统与控制研究所
-
出处
《计算机应用》
CSCD
北大核心
2010年第2期458-460,共3页
-
基金
国家创新研究群体科学基金资助项目(NCRGSFC:60721062)
国家自然科学基金资助项目(60774081)
-
文摘
多旅行商问题作为旅行商问题的一个扩展,是一个经典的组合优化问题,具有更高的复杂性,也具有更广泛的实际意义。针对每个旅行商允许经过的城市数有上限的多旅行商问题,通过引入虚拟城市把多旅行商问题转化为单旅行商问题,并且应用自组织优化算法进行了求解。虚拟城市局部适值的定义很好地处理了此类问题的能力约束,针对多旅行商问题的实例进行的仿真表明自组织优化算法可以很好地求解此类问题。
-
关键词
多旅行商问题
虚拟城市
自组织优化算法
局部适值
-
Keywords
multiple traveling salesman problem （mtsp）
virtual city
Self-Organizing Algorithm （SOA）
local fitness
-
分类号
TP30
[自动化与计算机技术—计算机系统结构]
TP182
[自动化与计算机技术—计算机科学与技术]
-
-
题名求解加权MTSP问题的CUDA并行群智能方法
被引量：2
- 7
-
-
作者
苏守宝
赵威
李智
-
机构
江苏科技大学计算机学院
金陵科技学院数据科学与智慧软件江苏省重点实验室
-
出处
《郑州大学学报（工学版）》
CAS
北大核心
2021年第6期34-41,共8页
-
基金
国家自然科学基金资助项目(61375121,41801303)
金陵科技学院高层次引进人才科研项目(jit-rcyj-201505)。
-
文摘
针对混合迭代算法执行时间长的问题,根据粒子群优化(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并行算法
代价均衡
粒子群聚类
蚁群算法
-
Keywords
multiple traveling salesman problem(mtsp)
CUDA parallel algorithm
cost-balanced
particle swarm clustering
ant colony algorithm
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
TP303.6
[自动化与计算机技术—控制科学与工程]
-
-
题名求解加热炉调度的改进修复式约束满足算法
- 8
-
-
作者
赵艳艳
李铁克
王柏琳
-
机构
北京科技大学东凌经济管理学院
钢铁生产制造执行系统技术教育部工程研究中心
-
出处
《计算机工程与应用》
CSCD
2012年第18期23-26,56,共5页
-
基金
国家自然科学基金(No.70771008)
教育部博士学科点专项科研基金(No.20100006110006)
中央高校基本科研业务费专项资金资助
-
文摘
针对钢铁生产中加热炉调度问题,考虑炉容受限的情况,以最小化板坯的Makespan和最小化总在炉加工时间为目标建立问题的多目标优化模型,将其归结为多旅行商问题。针对问题的NP-难特性,提出一种改进的修复式约束满足算法求解。松弛炉容约束得到初始调度,在检测冲突变量并构造冲突板坯的可替换加热炉集合的基础上,以开工时间偏移最小规则为冲突板坯重新指派加热炉,得到可行的调度方案。数据实验验证了模型和算法的可行性和有效性。
-
关键词
调度
炉容约束
修复式约束满足
多旅行商
-
Keywords
scheduling
capacity constraint
repair-based constraint satisfaction
multiple traveling salesman problem（mtsp）
-
分类号
TP278
[自动化与计算机技术—检测技术与自动化装置]
-
-
题名自动驾驶条件下共享车辆车队规模
被引量：2
- 9
-
-
作者
王冠
杨超
张英杰
陈海林
-
机构
同济大学道路与交通工程教育部重点实验室
上海市新能源汽车公共数据采集与监测研究中心
-
出处
《综合运输》
2019年第2期48-53,共6页
-
文摘
随着自动驾驶技术的发展和普及,未来以自动驾驶车辆替代传统有人驾驶私家车辆成为大势所趋,本文研究的目标是提出一种解决小规模自动驾驶共享车辆(Shared Autonomous Vehicle, SAV)车队规模的方法,并进行实际案例分析。使用的数据集是上海市50辆新能源私家车一年的轨迹数据,使用此部分出行需求,给出了计算两次出行是否可以衔接的具体方法,得到衔接矩阵。然后将求解最小车队规模问题转化为求解多旅行商问题(Multiple Travelling Salesman Problem, MTSP)的最短路问题,并证明两者具有等价性。论文提出使用排序遗传算法对此问题进行求解,使用5种常见的排序交叉算子分别验证求解质量,得到OX1交叉算子的质量最优。最后选择OX1交叉算子计算出行需求数排名前20天的SAV的最小规模,得到SAV的平均替代率为2.4。即在本研究中,一辆SAV平均可以替代2.4辆传统私家车,为未来自动驾驶技术普及后,SAV的车队规模问题提供参考。
-
关键词
自动驾驶共享车辆
最小车队规模
多旅行商问题
遗传算法
-
Keywords
Shared autonomous vehicle(SAV)
Minimum fleet size
multiple travelling salesman problem(mtsp)
Genetic algorithm(GA)
-
分类号
U495
[交通运输工程—交通运输规划与管理]
U463.6
[交通运输工程—道路与铁道工程]
-
