面向多旅行商问题的多目标模拟退火算法研究

被引:17
作者
梁星星 [1 ]
马扬 [1 ]
冯旸赫 [1 ]
张广平 [2 ]
马豪 [3 ]
机构
[1] 国防科技大学信息系统工程重点实验室
[2] 中国人民解放军部队
[3] 中国西安卫星测控中心
关键词
多旅行商问题; 多目标优化; 模拟退火; 遗传算法; 算法比较;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
多旅行商问题是经典旅行商问题的一种演化,考虑一些约束,可以转换为一些较现实的问题,具有较高的理论研究和应用价值.在多旅行商问题中,一个任务由多位旅行商共同完成,问题的求解难度较经典旅行商问题更大.现有的研究中指定旅行商个数,将问题转换为固定数量的多旅行商问题.本文构建了求解pareto解的多目标多旅行商问题模型,针对一定规模的城市数量和约束的问题,获得多旅行商问题中旅行商的合适数量.本文将旅行商的个数和多旅行商的最长访问路径作为优化目标,采用改进的多目标模拟退火(IMOSA)算法和传统的多目标遗传算法对问题进行了求解.采用30个城市的旅行商问题对两种算法进行了测试,发现改进的多目标模拟退火算法相较于多目标遗传算法计算复杂度低,且能发现较好的pareto解,算法性能更优.
引用
收藏
页码:80 / 86
页数:7
相关论文
共 11 条
[1]   求解多旅行商问题的改进分组遗传算法 [J].
王勇臻 ;
陈燕 ;
于莹莹 .
电子与信息学报, 2017, 39 (01) :198-205
[2]   基于不同条件的旅游路线规划问题研究 [J].
吴成明 ;
王毅 ;
毕红续 ;
曾珍珍 .
数学的实践与认识, 2016, 46 (15) :90-96
[3]   带临时补充点的融雪剂撒布车辆路径问题 [J].
谢秉磊 ;
李颖 ;
刘敏 .
系统工程理论与实践, 2014, 34 (06) :1593-1598
[4]   求解多旅行商问题的新混合遗传算法:以应急物资配送为例 [J].
刘明 ;
张培勇 .
系统管理学报, 2014, 23 (02) :247-254
[5]   多旅行商问题研究综述 [J].
俞庆生 ;
林冬梅 ;
王东 .
价值工程, 2012, 31 (02) :166-168
[6]  
A general variable neighborhood search heuristic for multiple traveling salesmen problem[J] . Banu Soylu.Computers & Industrial Engineering . 2015
[7]  
Area Allocation Algorithm for Multiple UAVs Area Coverage Based on Clustering and Graph Method[J] . Sungjun Ann,Youdan Kim,Jaemyung Ahn.IFAC PapersOnLine . 2015 (9)
[8]  
Minimization of off-grade production in multi-site multi-product plants by solving multiple traveling salesman problem[J] . András Király,Maria Christidou,Tibor Chován,Evangelos Karlopoulos,János Abonyi.Journal of Cleaner Production . 2015
[9]   A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms [J].
Yuan, Shuai ;
Skinner, Bradley ;
Huang, Shoudong ;
Liu, Dikai .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 228 (01) :72-82
[10]   A new grouping genetic algorithm approach to the multiple traveling salesperson problem [J].
Singh, Alok ;
Baghel, Anurag Singh .
SOFT COMPUTING, 2009, 13 (01) :95-101