﻿ 遗传算法求解多旅行商问题的相对解空间分析
«上一篇
 文章快速检索 高级检索

 智能系统学报  2018, Vol. 13 Issue (5): 760-768  DOI: 10.11992/tis.201706061 0

引用本文

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.

文章历史

Analysis on the relative solution space for MTSP with genetic algorithm
ZHAO Xinchao, GUO Sai
School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
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.
Key words: multiple traveling salespersons problem    genetic algorithm    chromosome encoding    relative solution space    Stirling formula

1 3种染色体方案

MTSP染色体的设计主要有以下3种[1]

1.1 单染色体设计

1.2 双染色体设计

1.3 两段式染色体设计

2 3种染色体编码方案下的相对解空间分析

2.1 相对解空间

3种染色体编码方案对应的解空间大小[1]分别为

 ${C_{\rm{one}}}= \left( {m + n - 1} \right)!$ (1)
 ${C_{\rm{two}}}= n!{m^n}$ (2)
 ${C_{2 {\text{-}} {\rm{part}}}}= n!C_{n - 1}^{m - 1}$ (3)

 ${C_{31}}= \frac{{{C_{2 \text{-} {\rm{part}}}}}}{{{C_{\rm{one}}}}}= \frac{{n!C_{n - 1}^{m - 1}}}{{\left( {m + n - 1} \right)!}}$ (4)
 ${C_{32}}= \frac{{{C_{2 - {\rm{part}}}}}}{{{C_{\rm{two}}}}}= \frac{{n!C_{n - 1}^{m - 1}}}{{n!{m^n}}}$ (5)
 ${C_{12}}= \frac{{{C_{\rm{one}}}}}{{{C_{\rm{two}}}}}= \frac{{(m + n - 1)!}}{{n!{m^n}}}$ (6)
2.2 相对解空间的极限分析

2.2.1 C31的极限分析

1) m适当大时

 \begin{aligned}& \quad{{\rm{ln\;}}{C_{31}} = \sum\limits_{k = 1}^n {{\rm{ln\;}}} k + \sum\limits_{k = 1}^{n - 1} {{\rm{ln\;}}} k - \sum\limits_{k = 1}^{m + n - 1} {{\rm{ln\;}}} k - \sum\limits_{k = 1}^{n - m} {{\rm{ln\;}}} k - }\\& {\sum\limits_{k = 1}^{m - 1} {{\rm{ln\;}}} k = \sum\limits_{k = 1}^n {{\rm{ln\;}}} k + \sum\limits_{k = 1}^{n - 1} {{\rm{ln\;}}} k - \left( {\sum\limits_{k = 1}^{n - 1} {{\rm{ln\;}}} k + \sum\limits_{k = n}^{n + m - 1} {{\rm{ln\;}}} k} \right) - }\\&\quad {\left( {\sum\limits_{k = 1}^n {{\rm{ln\;}}} k - \sum\limits_{k = n - m + 1}^n {{\rm{ln\;}}} k} \right) - \sum\limits_{k = 1}^{m - 1} {{\rm{ln\;}}} k = - \sum\limits_{k = n}^{n + m - 1} {{\rm{ln\;}}} k + }\\& \quad\quad\quad\;\;{\sum\limits_{k = n - m + 1}^n {{\rm{ln\;}}} k - \sum\limits_{k = 1}^{m - 1} {{\rm{ln\;}}} k - < \sum\limits_{k = 1}^{m - 1} {{\rm{ln\;}}} k < 0}\\&\quad\quad\quad\quad\quad\; {{C_{31}} = {{\rm{e}}^{ - \ln \left( {m - 1} \right)!}} = \frac{1}{{\left( {m - 1} \right)!}}}\end{aligned}

C31<1意味着第三种编码方案对应的解空间严格小于第一种方案对应的解空间，这严格证明了Carter[1]给出的解空间的定性比较结果。当n足够大时，所需的旅行商数也有相应增大，因此当n充分大、m适当大时， ${C_{31}} \ll 1$ 。例如：m=10， ${C_{31}}{\rm{ }} < {{\rm{e}}^{ - \sum\limits_{k = 1}^9 {\ln } k}} \approx 2.76 \times {10^{ - 6}}$

2) m是不大的常数时

(n–1)!可与(n+m–1)!相抵消，n!可与(nm)!相抵消，所以当n趋于无穷时得出：

 ${C_{31}}= \frac{{{C_{t \text{-} {\rm{part}}}}}}{{{C_{\rm{one}}}}}= \frac{{n! n - 1!}}{{\left( {n + m - 1} \right)! \left( {n - m} \right)! \left( {m - 1} \right)!}} \to \frac{1}{{\left( {m - 1} \right)!}}$

2.2.2 C32的极限分析

1)m适当大时

 \begin{aligned}\begin{array}{l}\;{\kern 1pt} {\rm{ln\;}}{C_{32}} = \displaystyle\sum\limits_{k = 1}^{n - 1} {\ln\; } k - \displaystyle\sum\limits_{k = 1}^{n - m} {\ln\; } k - n{\rm{ln\;}}m - \displaystyle\sum\limits_{k = 1}^{m - 1} {\ln\; } k = \\\displaystyle\sum\limits_{k = n - m + 1}^{n - 1} {\ln\; } k - n{\rm{ln\;}}m - \displaystyle\sum\limits_{k = 1}^{m - 1} {\ln\; } k\end{array}\end{aligned}

$\displaystyle \sum\limits_{k = n - m + 1}^{n - 1} {\ln\; } k$ 中有m-1项，通项是城市数n的对数，而nln m中有n项，ln m是旅行商数目的对数，并且当n充分大时， $\mathop {\lim }\nolimits_{n \to \infty } \displaystyle\frac{n}{{{\rm{ln\;}}n}}= + \infty$ [14]，所以当 $n \to \infty$ 时， $\displaystyle\sum\limits_{k = n - m + 1}^{n - 1} {\ln\; } k - n{\rm{ln\;}}m < 0$ 。因为

 $\begin{array}{c} \mathop \sum \limits_{k= n - m + 1}^{n - 1} {\rm{ln\;}}k - n{\rm{ln\;}}m < \left( {m - 1} \right) \cdot {\rm{ln\;}}\left( {n - 1} \right) - n{\rm{ln\;}}m < \\m{\rm{ln\;}}n - n{\rm{ln\;}}m < 0\end{array}$

C32<1同样意味着第三种编码方案对应的解空间小于第二种方案对应的解空间。同C31的分析类似，当n足够大、m适当大时， ${C_{32}} \ll 1$

2)m是不大的常数时

 $\begin{array}{c}{C_{32}}= \displaystyle \frac{{{C_{t \text{-} {\rm part}}}}}{{{C_{{\rm two}}}}}= \frac{{n!C_{n - 1}^{m - 1}}}{{n!{m^n}}}= \frac{{\left( {n - 1} \right)!}}{{\left( {m - 1} \right)!\left( {n - m} \right)!{m^n}}}= \\\displaystyle \frac{{\left( {n - 1} \right)\left( {n - 2} \right) \cdots \left( {n - m + 1} \right)}}{{\left( {m - 1} \right)!{m^n}}} < \displaystyle \frac{{{n^m}}}{{\left( {m - 1} \right)!{m^n}}}\end{array}$

2.2.3 C12的极限分析

 $\begin{array}{c}\ln\;{C_{12}}= \displaystyle \mathop \sum \limits_{k= 1}^{n + m - 1} {\rm{ln\;}}k - \displaystyle \mathop \sum \limits_{k= 1}^n {\rm{ln\;}}k - n{\rm{ln\;}}m=\displaystyle \mathop \sum \limits_{k= n + 1}^{n + m - 1} {\rm{ln\;}}k - n{\rm{ln\;}}m <\\ \left( {m - 1} \right)\ln\; \left( {n + m - 1} \right) - n{\rm{ln\;}}m\end{array}$

n充分大时， $\mathop {\lim }\nolimits_{n \to \infty } \displaystyle\frac{n}{{{\rm{ln\;}}n}}= + \infty$ ，因此 ${\rm{ln\;}}{C_{12}} < 0$ ${C_{12}} < 1$ C12的大小说明第一种编码方案对应的解空间小于第二种编码方案对应的解空间。

2.3 相对搜索空间的粗略估计

 Download: 图 5 n=10m情形下的相对搜索空间变化曲线图 Fig. 5 Solution space change in the case of n= 10 m
 Download: 图 6 n=m2情形下的相对搜索空间变化曲线图 Fig. 6 Solution space change in the case of n=m2
 Download: 图 7 ${\bf n}{ =}{\bf e}^{ m}$ 情形下的相对搜索空间变化曲线图 Fig. 7 Solution space change in the case of ${ n}{ =}{\bf e}^{ m}$
2.4 分情形下的相对解空间大小分析 2.4.1 Stirling公式

 $\mathop {{\rm{lim}}}\nolimits_{n \to \infty } \displaystyle\frac{{n!}}{{\sqrt {2{\text{π}} n} {{\left( {\displaystyle\frac{n}{{\rm{e}}}} \right)}^n}}}= 1$ (7)
 Download: 图 8 n!与 $\sqrt {2{\text{π}} n} {\left( {\displaystyle\frac{n}{{\rm{e}}}} \right)^n}$ 变化示意图 Fig. 8 Diagram of changes in n! and $\sqrt {2{\text{π}} n} {\left( {\displaystyle\frac{n}{{\rm{e}}}} \right)^n}$
2.4.2 n=10m时相对解空间分析

n=10m时：

 $\begin{array}{l}{C_{31}}= \displaystyle\frac{{{C_{2 \text{-} {\rm part}}}}}{{{C_{\rm one}}}}= \displaystyle\frac{{n!C_{n - 1}^{m - 1}}}{{\left( {m + n - 1} \right)!}}\sim \displaystyle\frac{{\sqrt {2{\text{π}} n} {{\left( {\displaystyle\frac{n}{{\rm{e}}}} \right)}^n}\sqrt {2\pi \left( {n - 1} \right)} {{\left( {\displaystyle\frac{{n - 1}}{{\rm{e}}}} \right)}^{n - 1}}}}{{\sqrt {2{\text{π}} \left( {m + n - 1} \right)} {{\left( {\displaystyle\frac{{m + n - 1}}{{\rm{e}}}} \right)}^{m + n - 1}}\sqrt {2{\text{π}} \left( {m - 1} \right)} {{\left( {\displaystyle\frac{{m - 1}}{{\rm{e}}}} \right)}^{m - 1}}\sqrt {2{\text{π}} \left( {n - m} \right)} {{\left( {\displaystyle\frac{{n - m}}{{\rm{e}}}} \right)}^{n - m}}}}\sim \\\displaystyle \sqrt {\displaystyle\frac{{5\left( {10m - 1} \right)}}{{9\pi \left( {11m - 1} \right)\left( {m - 1} \right)}}} \cdot \displaystyle\frac{{{m^m}{{\left( {m - \displaystyle\frac{1}{{10}}} \right)}^{10m - 1}}}}{{{{\left( {m - \displaystyle\frac{1}{{11}}} \right)}^{11m - 1}}{{\left( {m - 1} \right)}^{m - 1}}}} \cdot \displaystyle\frac{{{{10}^{20m - 1}} \cdot {{\rm e}^{m - 1}}}}{{{{11}^{11m - 1}} \cdot {9^{9m}}}}\end{array}$ (8)

 ${C_{31}}= \frac{{{C_{2 \text{-} {\rm part}}}}}{{{C_{{\rm one}}}}}\sim \sqrt {\frac{1}{{2{\text{π}} m}}} {\left( {\frac{{\rm{e}}}{m}} \right)^m}$ (9)

 ${C_{{\rm one}}}= {C_{2 \text{-} {\rm part}}} \cdot O\left( {{{\left( {\frac{m}{{\rm{e}}}} \right)}^m}} \right)$ (10)

 ${C_{32}}= \frac{{{C_{2 \text{-} {\rm part}}}}}{{{C_{{\rm two}}}}}= \frac{{n!C_{n - 1}^{m - 1}}}{{n!{m^n}}}$ (11)

m取较大正整数时，指数项可以用二项展开式的前两项近似替代，具体过程不在此赘述，以下相似替代过程将不特殊说明，式(11)化简为

 ${C_{32}}\sim \sqrt {\frac{1}{{2{\text{π}} m}}} \cdot \frac{1}{{{m^{10m}}}} \cdot \frac{{{{10}^{10m - 1}}}}{{{9^{9m}}}}$ (12)

 ${{\rm{C}}_{\rm {two}}}= {C_{2 \text{-} {\rm part}}} \cdot {{O}}\left( {{m^{10m}}} \right)$ (13)

 $\begin{array}{l}{C_{12}}= \displaystyle\frac{{{C_{\rm one}}}}{{{C_{\rm two}}}}= \displaystyle\frac{{m + n - 1!}}{{n{m^n}}}= \displaystyle\frac{{\left( {11m - 1} \right)!}}{{\left( {10m} \right)!{m^{10m}}}}\sim \\\displaystyle \frac{{\sqrt {2{\text{π}} \left( {11m - 1} \right)} {{\left( {\displaystyle\frac{{11m - 1}}{e}} \right)}^{11m - 1}}}}{{\sqrt {2{\text{π}} \left( {10m} \right)} {{\left( {\displaystyle\frac{{10m}}{e}} \right)}^{10m}}{m^{10m}}}}\sim \sqrt {\displaystyle\frac{{11}}{{10}}} \cdot \displaystyle\frac{1}{{{m^{9m}}}} \cdot \displaystyle\frac{1}{{{{\rm e}^{m - 1}}}}\end{array}$ (14)

 ${C_{{\rm two}}}= {C_{{\rm one}}} \cdot O\left( {{m^{9m}} \cdot {{\rm e}^m}} \right)$ (15)

 ${C_{{\rm one}}}= {C_{2 \text{-} {\rm part}}} \cdot {{O}}\left( {{{\left( {\frac{m}{{\rm{{\rm e}}}}} \right)}^m}} \right)$ (16)
 ${{\rm{C}}_{{\rm two}}}= {C_{2 \text{-} {\rm part}}} \cdot {{O}}\left( {{m^{10m}}} \right)$ (17)

 $\frac{{{C_{\rm two}}}}{{{C_{\rm one}}}}= \frac{{{C_{2 - \rm part}} \cdot {{O}}\left( {{m^{10m}}} \right)}}{{{C_{2 - \rm part}} \cdot O\left( {{{\left( {\displaystyle\frac{m}{{\rm{e}}}} \right)}^m}} \right)}}= {{O}}\left( {{m^{9m}} \cdot {{\rm e}^m}} \right)$ (18)

2.4.3 平方关系下的相对解空间分析

n=m2代入式（19）：

 $\begin{array}{l}{C_{31}}= \displaystyle \frac{{{C_{2 \text{-} \rm part}}}}{{{C_{\rm one}}}}= \displaystyle \frac{{n!C_{n - 1}^{m - 1}}}{{\left( {m + n - 1} \right)!}}= \displaystyle \frac{{{m^2}!\left( {{m^2} - 1} \right)!}}{{\left( {{m^2} + m - 1} \right)!\left( {m - 1} \right)!({m^2} - m)!}}\sim \\ \displaystyle \frac{{\sqrt {2{\text{π}} {m^2}} {{\left( {\displaystyle\frac{{{m^2}}}{{\rm{e}}}} \right)}^{{m^2}}}\sqrt {2{\text{π}} ({m^2} - 1)} {{\left( {\displaystyle\frac{{{m^2} - 1}}{{\rm{e}}}} \right)}^{{m^2} - 1}}}}{{\sqrt {2{\text{π}} \left( {{m^2} + m - 1} \right)} {{\left( {\displaystyle\frac{{{m^2} + m - 1}}{{\rm{e}}}} \right)}^{{m^2} + m - 1}}\sqrt {2{\text{π}} \left( {m - 1} \right)} {{\left( {\displaystyle\frac{{m - 1}}{{\rm{e}}}} \right)}^{{{m}} - 1}}\sqrt {2{\text{π}} \left( {{m^2} - m} \right)} {{\left( {\displaystyle\frac{{{m^2} - m}}{{\rm{e}}}} \right)}^{{m^2} - {{m}}}}}}\end{array}$ (19)

 ${C_{31}}\sim \frac{1}{{\sqrt {2{\text{π}} m} }} \cdot \frac{1}{{{m^m}}} \cdot {{\rm{e}}^{m - 1}}$ (20)

 ${C_{\rm one}}= {C_{2 \text{-} \rm part}} \cdot O\left( {{{\left( {\frac{m}{{\rm{e}}}} \right)}^m}} \right)$ (21)

 $\begin{array}{l}\quad\quad{C_{32}}= \displaystyle\frac{{{C_{2 \text{-} \rm part}}}}{{{C_{\rm two}}}}= \displaystyle\frac{{n!C_{n - 1}^{m - 1}}}{{n!{m^n}}}= \displaystyle\frac{{\left( {n - 1} \right)!}}{{\left( {m - 1} \right)!\left( {n - m} \right)!{m^n}}}=\\ \quad\quad\quad\quad\quad\quad\;\displaystyle\frac{{\left( {{m^2} - 1} \right)!}}{{\left( {m - 1} \right)!\left( {{m^2} - {\rm{m}}} \right)!{m^{{m^2}}}}}\sim \\\displaystyle\frac{{\sqrt {2{\text{π}} \left( {{m^2} - 1} \right)} {{\left( {\displaystyle\frac{{{m^2} - 1}}{{\rm{e}}}} \right)}^{{m^2} - 1}}}}{{\sqrt {2{\text{π}} \left( {m - 1} \right)} {{\left( {\displaystyle\frac{{m - 1}}{{\rm{e}}}} \right)}^{m - 1}}\sqrt {2{\text{π}} \left( {{m^2} - m} \right)} {{\left( {\displaystyle\frac{{{m^2} - m}}{{\rm{e}}}} \right)}^{{m^2} - {{m}}}}{m^{{m^2}}}}}\sim \\\quad\quad\quad\quad\quad\quad\displaystyle \frac{1}{{\sqrt {2{\text{π}} \left( {m - 1} \right)} }} \cdot \frac{1}{{{m^{{m^2} - m}}}} \cdot \frac{1}{m}\end{array}$ (22)

 ${C_{\rm two}}= {C_{2 \text{-} \rm part}} \cdot O\left( {{m^{{m^2} - m}}} \right)$ (23)

 ${C_{\rm two}}= {C_{\rm one}} \cdot O\left( {\frac{{{m^{{m^2}}} - 2m}}{{{{\rm{e}}^m}}}} \right)$ (24)

2.4.4 指数关系下的相对解空间分析

n=em代入式（4）：

 $\begin{array}{c}{C_{31}}= \displaystyle \frac{{{C_{t - \rm part}}}}{{{C_{\rm one}}}}= \displaystyle \frac{{n!C_{n - 1}^{m - 1}}}{{\left( {m + n - 1} \right)!}}\sim \displaystyle \frac{{\sqrt {2{\text{π}} {{\rm{e}}^m}} {{\left( {\displaystyle\frac{{{{\rm{e}}^{m}}}}{{\rm{e}}}} \right)}^{{{\rm{e}}^m}}}\sqrt {2{\text{π}} \left( {{{\rm e}^m} - 1} \right)} {{\left( {\displaystyle\frac{{{{\rm{e}}^m} - 1}}{{\rm{e}}}} \right)}^{{{\rm{e}}^m} - 1}}}}{{\sqrt {2{\text{π}} \left( {m + {{\rm{e}}^{m}} - 1} \right)} {{\left( {\displaystyle\frac{{m + {{\rm{e}}^m} - 1}}{{\rm{e}}}} \right)}^{m + {{\rm{e}}^m} - 1}}\sqrt {2{\text{π}} \left( {m - 1} \right)} {{\left( {\displaystyle\frac{{m - 1}}{{\rm{e}}}} \right)}^{m - 1}}\sqrt {2{\text{π}} \left( {{{\rm{e}}^m} - m} \right)} {{\left( {\displaystyle\frac{{{{\rm{e}}^m} - m}}{{\rm{e}}}} \right)}^{{{\rm{e}}^m} - m}}}}\sim \\ \displaystyle \frac{1}{{\sqrt {2{\text{π}} m} }} \cdot \displaystyle \frac{1}{{{m^m}}} \cdot {{\rm{e}}^{m - 1}}\end{array}$ (25)

 ${C_{31}}\sim \frac{1}{{\sqrt {2{\text{π}} m} }} \cdot \frac{1}{{{m^m}}} \cdot {{\rm{e}}^{m - 1}}$ (26)

 ${C_{\rm one}}= {C_{2 \text{-} \rm part}} \cdot O\left( {{{\left( {\frac{m}{{\rm{e}}}} \right)}^m}} \right)$ (27)

 ${C_{32}}= \frac{{{C_{2 \text{-} \rm part}}}}{{{C_{\rm two}}}}= \frac{{n!C_{n - 1}^{m - 1}}}{{n!{m^n}}}= \frac{{\left( {n - 1} \right)!}}{{\left( {m - 1} \right)!\left( {n - m} \right)!{m^n}}}$ (28)

 ${C_{\rm two}}= {C_{2 \text{-} \rm part}} \cdot O\left( {{m^{{{\rm{e}}^m}}}} \right)$ (29)

 ${C_{\rm two}}= {C_{\rm one}} \cdot O\left( {\frac{{{m^{{{\rm{e}}^m} - m}}}}{{{{\rm{e}}^m}}}} \right)$ (30)

3 结束语

 [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. DOI:10.1016/j.ejor.2005.04.027 (0) [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. DOI:10.1016/j.ejor.2013.01.043 (0) [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. (0) [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. DOI:10.1109/TEVC.2015.2429314 (0) [5] GOLDBERG D E. Genetic algorithms in search, optimization, and machine learning[M]. Reading, Mass: Addison-Wesley Publishing Company, 1989. (0) [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. DOI:10.1007/s10479-014-1667-6 (0) [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. (0) [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. (0) [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. DOI:10.3969/j.issn.1001-3695.2007.07.013 (0) [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. (0) [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. DOI:10.1007/s00500-016-2279-7 (0) [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. DOI:10.3321/j.issn:0254-4164.2007.05.005 (0) [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. (0) [14] 张筑生. 数学分析新讲(第2册)[M]. 北京: 北京大学出版社, 1990. (0)