[1]梁星星,马 扬,冯旸赫,等.面向多旅行商问题的多目标模拟退火算法研究[J].南京师范大学学报(自然科学版),2017,40(03):80.[doi:10.3969/j.issn.1001-4616.2017.03.012]
　Liang Xingxing,Ma Yang,Feng Yanghe,et al.Research on Multi-objective Simulated Annealing Algorithmfor Multi-traveling Salesman Problem[J].Journal of Nanjing Normal University(Natural Science Edition),2017,40(03):80.[doi:10.3969/j.issn.1001-4616.2017.03.012]
点击复制

面向多旅行商问题的多目标模拟退火算法研究()
分享到：

《南京师范大学学报》（自然科学版）[ISSN:1001-4616/CN:32-1239/N]

卷:
第40卷
期数:
2017年03期
页码:
80
栏目:
·计算机科学·
出版日期:
2017-09-30

文章信息/Info

Title:
Research on Multi-objective Simulated Annealing Algorithmfor Multi-traveling Salesman Problem
文章编号:
1001-4616(2017)03-0080-07
作者:
梁星星1; 马 扬1; 冯旸赫1; 张广平2; 马 豪3
(1.国防科技大学信息系统工程重点实验室,湖南 长沙 410072)(2.中国人民解放军31111部队,江苏 南京 210023)(3.中国西安卫星测控中心,陕西 西安 710043)
Author(s):
Liang Xingxing1; Ma Yang1; Feng Yanghe1; Zhang Guangping2; Ma Hao3
(1.Science and Technology on Information Systems Engineering Laboratory,College of Information System and Management,National University of Defense Technology,Changsha 410072,China)(2.The PLA 31111 Troops,Nanjing 210023,China)(3.China Xi’an Satellite C
关键词:
多旅行商问题; 多目标优化; 模拟退火; 遗传算法; 算法比较
Keywords:
multiple traveling salesmen problem; multi-objective optimization; simulated annealing algorithm; genetic algorithm; algorithm comparison
分类号:
TP311
DOI:
10.3969/j.issn.1001-4616.2017.03.012
文献标志码:
A
摘要:
多旅行商问题是经典旅行商问题的一种演化,考虑一些约束,可以转换为一些较现实的问题,具有较高的理论研究和应用价值. 在多旅行商问题中,一个任务由多位旅行商共同完成,问题的求解难度较经典旅行商问题更大. 现有的研究中指定旅行商个数,将问题转换为固定数量的多旅行商问题. 本文构建了求解pareto解的多目标多旅行商问题模型,针对一定规模的城市数量和约束的问题,获得多旅行商问题中旅行商的合适数量. 本文将旅行商的个数和多旅行商的最长访问路径作为优化目标,采用改进的多目标模拟退火(IMOSA)算法和传统的多目标遗传算法对问题进行了求解. 采用30个城市的旅行商问题对两种算法进行了测试,发现改进的多目标模拟退火算法相较于多目标遗传算法计算复杂度低,且能发现较好的pareto解,算法性能更优.
Abstract:
Multi-traveling salesman problem is an evolution of the classic traveler problem. Considering some constraints,it can be converted into some more realistic problems,with high theoretical research and application value. In the multi-traveling salesman problem,a task is completed by a number of travel agents,the problem is more difficult than the classic traveler problem. In the existing study,they convert the problem into a fixed number of traveling salesmen problem. In this paper,we construct a multi-objective multi-traveling salesman problem model for seeking the pareto solution. In view of the problem of the number of cities and the constraints of a certain scale,we obtain the number of traveling salesmen of the problem. In this paper,the number of traveler and the longest access path of multi-traveler are taken as the optimization target. The improved multi-objective simulated annealing(IMOSA)algorithm and multi-objective genetic algorithm are used to solve the problem. The results show that the improved multi-objective simulated annealing algorithm is more complex than the multi-objective genetic algorithm and can find a better pareto solution and the algorithm performance is better than that of the multi-objective genetic algorithm.

参考文献/References:

[1] 吴成明,王毅,毕红续,等. 基于不同条件的旅游路线规划问题研究[J]. 数学的实践与认识,2016(15):90-96.
[2]SOYLU B. A general variable neighborhood search heuristic for multiple traveling salesmen problem[J]. Computers and industrial engineering,2015,90(C):390-401.
[3]KOTA L,JARMAI K. Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming[J]. Applied mathematical modelling,2015,39(12):3 410-3 433.
[4]俞庆生,林冬梅,王东. 多旅行商问题研究综述[J]. 价值工程,2012,31(2):166-168.
[5]XIE B L,YING L I,MIN L,et al. Vehicle routing problem with temporary supplementary points for spreading deicing salt[J]. Systems engineering-theory and practice,2014,34(6):1 593-1 598.
[6]LIU M,ZHANG P Y. New hybrid genetic algorithm for solving the multiple traveling salesman problem:an example of distribution of emergence materials[J]. Journal of system and management,2014,23(2):247-254.
[7]ANN S,KIM Y,AHN J. Area allocation algorithm for multiple UAVs area coverage based on clustering and graph method[J]. IFAC-papers on line,2015,48(9):204-209.
[8]KIRALY A,CHRISTIDOU M,CHOVAN T,et al. Minimization of off-grade production in multi-site multi-product plants by solving multiple traveling salesman problem[J]. Journal of cleaner production,2016,111:253-261.
[9]王勇臻,陈燕,于莹莹. 求解多旅行商问题的改进分组遗传算法[J]. 电子与信息学报,2017,39(1):198-205.
[10]SINGH A,BAGHEL A S. A new grouping genetic algorithm approach to the multiple traveling salesperson problem[J]. Soft computing,2009,13(1):95-101.
[11]YUAN S,SKINNER B,HUANG S,et al. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms[J]. European journal of operational research,2013,228(1):72-82.
[12]LIU W,LI S,ZHAO F,et al. An ant colony optimization algorithm for the multiple traveling salesmen problem[C]//4th IEEE Conference on Industrial Electronics and Applications,2009. ICIEA 2009. IEEE,2009:1 533-1 537.
[13]NECULA R,BREABAN M,RASCHIP M. Performance evaluation of ant colony systems for the single-depot multiple traveling salesman problem[C]//International Conference on Hybrid Artificial Intelligence Systems. Cham:Springer,2015: 257-268.
[14]XUE M H,WANG T Z,MAO S. Double evolutsional artificial bee colony algorithm for multiple traveling salesman problem[C]//MATEC Web of Conferences. EDP Sciences,2016:44.
[15]VENKATESH P,SINGH A. Two metaheuristic approaches for the multiple traveling salesperson problem[J]. Applied soft computing,2015,26:74-89.

相似文献/References:

[1]李滢,童维勤,亢朝峰,等.基于QoS多目标优化的组合服务执行路径的选择[J].南京师范大学学报(自然科学版),2012,35(03):125.
　Li Ying,Tong Weiqing,Kang Chaofeng,et al.The QoS-Based Multi-Objective Optimization Algorithm of the Composite Service Execution Path[J].Journal of Nanjing Normal University(Natural Science Edition),2012,35(03):125.
[2]许 金,谷 琼,蔡之华,等.基于自适应ε占优的多目标差分演化算法[J].南京师范大学学报(自然科学版),2015,38(01):119.
　Xu Jin,Gu Qiong,Cai Zhihua,et al.Differential Evolution Algorithm for Multi-Objective OptimizationBased on Adaptive ε-Dominance[J].Journal of Nanjing Normal University(Natural Science Edition),2015,38(03):119.
[3]李二超,马玉泉.基于快速二层解修补策略的区间离散遗传算法[J].南京师范大学学报(自然科学版),2019,42(03):73.[doi:10.3969/j.issn.1001-4616.2019.03.010]
　Li Erchao,Ma Yuquan.Interval Discrete Genetic Algorithms Based on FastTwo-Level Solution Repair Strategy[J].Journal of Nanjing Normal University(Natural Science Edition),2019,42(03):73.[doi:10.3969/j.issn.1001-4616.2019.03.010]

备注/Memo

备注/Memo:
收稿日期:2017-03-18.
基金项目:国家自然科学基金(71471174).
通讯联系人:梁星星,博士研究生,研究方向:多Agent强化学习. E-mail:doublestar_l@163.com
更新日期/Last Update: 2017-09-30