|Table of Contents|

Research on Multi-objective Simulated Annealing Algorithmfor Multi-traveling Salesman Problem(PDF)

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

Issue:
2017年03期
Page:
80-
Research Field:
·计算机科学·
Publishing date:

Info

Title:
Research on Multi-objective Simulated Annealing Algorithmfor Multi-traveling Salesman Problem
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
PACS:
TP311
DOI:
10.3969/j.issn.1001-4616.2017.03.012
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.

Memo

Memo:
-
Last Update: 2017-09-30