[1]ZHAO Xinchao,GUO Sai.Analysis on the relative solution space for MTSP with genetic algorithm[J].CAAI Transactions on Intelligent Systems,2018,13(5):760-768.[doi:10.11992/tis.201706061]
Copy
Analysis on the relative solution space for MTSP with genetic algorithm
CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume:
13
Number of periods:
2018 5
Page number:
760-768
Column:
学术论文—智能系统
Public date:
2018-09-05
- Title:
- Analysis on the relative solution space for MTSP with genetic algorithm
- Keywords:
- multiple traveling salespersons problem; genetic algorithm; chromosome encoding; relative solution space; Stirling formula
- CLC:
- O224;TP18
- DOI:
- 10.11992/tis.201706061
- Abstract:
- This paper introduces the concept of multiple traveling salespersons problem (MTSP) and a chromosome encoding design method for solving the MTSP using genetic algorithm. In order to reduce the cost of redundant solution, two traditional chromosome design methods (single and double chromosome designs) are proposed, as well as the current two-part chromosome encoding design. Then the concept of relative solution space is introduced to quantitatively compare the relative size order of spaces for different solutions. Then on based on the relative solution space, the relative size order of the solution spaces of three chromosome-encoding designs are analyzed under an infinite limit. Subsequently, the relative size order of the solution spaces is analyzed individually when the relationship presents different situations between the number of travelers and the number of cities. The theoretical results of the quantitative analysis on the search space given in this paper are of great significance in guiding engineering applications and solving practical problems.
- References:
-
[1] CARTER A E, RAGSDALE C T. A new approach to solving the multiple traveling salesperson problem using genetic algorithms[J]. European journal of operational research, 2006, 175(1):246-257.
[2] YUAN Shuai, SKINNER B, HUANG Shoudong, 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.
[3] WANG Xuping, XU Chuanlei, HU Xiangpei. Genetic algorithm for vehicle routing problem with time windows and a limited number of vehicles[C]//Proceedings of 2008 International Conference on Management Science and Engineering 15th Annual Conference. Long Beach, CA, USA, 2010:128-133.
[4] BRANKE J, NGUYEN S, PICKARDT C, et al. Automated design of production scheduling heuristics:a review[J]. IEEE transactions on evolutionary computation, 2016, 20(1):110-124.
[5] GOLDBERG D E. Genetic algorithms in search, optimization, and machine learning[M]. Reading, Mass:Addison-Wesley Publishing Company, 1989.
[6] KESHAVARZ T, SALMASI N, VARMAZYAR M. Minimizing total completion time in the flexible flowshop sequence-dependent group scheduling problem[J]. Annals of operations research, 2015, 226(1):351-377.
[7] 张永库, 尹灵雪, 孙劲光. 基于改进的遗传算法的模糊聚类算法[J]. 智能系统学报, 2015, 10(4):627-635 ZHANG Yongku, YIN Lingxue, SUN Jinguang. Fuzzy clustering algorithm based on the improved genetic algorithm[J]. CAAI transactions on intelligent systems, 2015, 10(4):627-635
[8] KATAYAMA K, SAKAMOTO H, NARIHISA H. The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem[M]. The Netherlands:Elsevier Science Publishers B. V., 2000.
[9] 黄可为, 汪定伟. 热轧计划中的多旅行商问题及其计算方法[J]. 计算机应用研究, 2007, 24(7):43-45, 57 HUANG Kewei, WANG Dingwei. Multiple traveling salesman problem and its application to hot rolling planning[J]. Application research of computers, 2007, 24(7):43-45, 57
[10] 江贺, 张宪超, 车皓阳, 等. 带多项式量级约束条件的多商品流BWTSP线性规划[J]. 计算机研究与发展, 2007, 44(10):1796-1800 JIANG He, ZHANG Xianchao, CHE Haoyang, et al. A multi-commodity flow linear programming with polynomial constraints for black and white traveling salesman problem[J]. Journal of computer research and development, 2007, 44(10):1796-1800
[11] TRIGUI S, CHEIKHROUHOU O, KOUBAA A, et al. FL-MTSP:a fuzzy logic approach to solve the multi-objective multiple traveling salesman problem for multi-robot systems[J]. Soft computing, 2017, 21(24):7351-7362.
[12] 王宇平, 李英华. 求解TSP的量子遗传算法[J]. 计算机学报, 2007, 30(5):748-755 WANG Yuping, LI Yinghua. A novel quantum genetic algorithm for TSP[J]. Chinese journal of computers, 2007, 30(5):748-755
[13] 赵新超, 刘国莅, 刘虎球, 等. 基于非均匀变异和多阶段扰动的粒子群优化算法[J]. 计算机学报, 2014, 37(9):2058-2070 ZHAO Xinchao, LIU Guoli, LIU Huqiu, et al. Particle swarm optimization algorithm based on non-uniform mutation and multiple stages perturbation[J]. Chinese journal of computers, 2014, 37(9):2058-2070
[14] 张筑生. 数学分析新讲(第2册)[M]. 北京:北京大学出版社, 1990.
- Similar References:
Memo
-
Last Update:
2018-10-25