第!"卷 第#期 运 筹 与 管 理 $%&’!"，(%’#
"))*年+月 ,-./012,(3/. 09:’，"))*
收稿日期："))";!!;!<
作者简介：翟东海（!=>#;），博士研究生，主要研究方向：组合优化、神经网络，模糊推理。
用嵌套插队算法解决13-问题
翟东海， 靳 蕃
（西南交通大学 计算机与通信工程学院，四川 成都?!))*!）
摘 要：本文提出了一种求解13-问题的近似算法—嵌套插队算法。这种算法结合了启发式算法和随机化算
法以及局部寻优的思想。实验结果表明对于较小规模的13-问题，直接用插队算法（@A0）就能以很大的概率获
得已知最优解。对于规模较大的问题实例，嵌套插队算法（(@A0）能获得质量高于著名的启发式算法的解。另
外，用嵌套插队算法找到的4BCDE!##的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对13-问
题而提出的，但其思想也可以给求解其他(-难解的组合优化问题以启发。
关键词：13-问题；插队算法；嵌套插队算法；随机化算法
中图分类号：,""!F> 文章标识码：0 文章编号：!))>;*""!（"))*）)#;))#=;)?
!"#$"%&’"’"()’*+,-./,$3*4125267"0,"#*6-921:0"*
G50H6%D:;5EC，A2(IED
（!"#$$%$&’$()*+,-./0’$((*/1".+1$/2/31/,,-1/3，!$*+#4,5+
61.$+$/37/18,-51+9，’#,/30*?!))*!，’#1/.）
/:#$26;$：1BCJKEKLMKM%K%JLJEDLNEKKM%OCPEQLE&:%MCQBP—DLJQLRS9L9L;T9PKCD:E&:%MCQBPU%MQMEVL&CD:
JE&LJPEDKM%W&LP’1BLKM%K%JLRE&:%MCQBPCDX%MK%MEQLJQBLQB%9:BQJ%UBL9MCJQCXE&:%MCQBP，MEDR%PCYLRE&:%;
MCQBPEDR&%XE&%KQCPCYEQC%D’(9PLMCXE&MLJ9&QJJB%NQBEQ，Q%QBLJPE&&;JXE&LCDJQEDXLJ，9JCD:S9L9L;T9PKCD:
E&:%MCQBPRCMLXQ&ZXED%WQECDQBL[D%NDWLJQJ%&9QC%DNCQBE&EM:LKM%WEWC&CQZ’2DQBLXEJL%U&EM:L;JXE&LCD;
JQEDXLJ，DLJQLRS9L9L;T9PKCD:E&:%MCQBP:LDLMEQLJBC:B;S9E&CQZJ%&9QC%DX%PKEMLRQ%NL&&;[D%NDB9MCJQCX
PLQB%RJ’7%ML%VLM，QBLJB%MQLJQQ%9MQ%4BCDE!##13-U%9DRWZ(@A0CJJB%MQLMQBEDQBL[D%ND%KQCPE&
Q%9M’2QXEDWLEVLMZKM%PCJCD:E&QLMDEQCVLU%MUCDRCD:EJ%&9QC%DQ%QBL13-’(LJQLRS9L9L;T9PKCD:E&:%MCQBP
CJJKLXCE&&ZRLVCJLRU%M13-’\9QCQJQB%9:BQXEDL&CXCQ%QBLM(-;BEMRX%PWCDEQ%MCE&%KQCPCYEQC%DKM%W&LPJ’
<"=>12%#：QMEVL&CD:JE&LJPEDKM%W&LP；S9L9L;T9PKCD:E&:%MCQBP；DLJQLRS9L9L;T9PKCD:E&:%MCQBP；MEDR%P;
CYLRE&:%MCQBP
) 引言
旅行商问题（13-问题）是一个著名的组合优化问题。13-问题的应用包括不同调度、路径规划问
题、电路板设计问题等等。目前普遍认为对13-问题不存在有效的精确算法，所以寻找13-问题的近似
解法是必由之路。人们一方面提出了专门针对13-问题的多种启发式算法，另一方面把各种最优化新方
法运用于13-问题的求解，这些方法包括模拟退火、神经网络、遗传算法、禁忌搜索算法、蚂蚁算法、竞争
算法等，推动了对13-问题和这些算法本身的研究。
万方数据
! 算法的提出
!"! 插队算法
寻求"#$最短路径的过程，实际上就是寻求所有城市的一个旅行次序的过程，按照这个次序去旅行
会得到最短路径。我们把与最短路径相对应的旅行次序，叫做最优循环队列（简称最优队列）。
生成所有城市的一个随机全排列，用它来构成初始循环队列（简称初始队列），运行插队算法的过程就
是调整初始队列得到最优队列的过程。初始队列中前三个城市的旅行次序是唯一的，用它们来构成一个
新的小循环队列作为最优队列的雏形。把初始队列中的第四个城市插入这个新队列时，不同的插入位置
会导致不同的旅行次序。最终的插入位置必须使得插入以后的旅行路径的长度最小（也就是长度的增量
最小）。初始队列中剩余城市的插入过程与此类似，直到最后一个城市插入这个新队列为止。这个算法的
思想类似于现实生活中的一些人的“插队”行为，故我们把这种算法叫做插队算法（%&’&’()&*+,-./(
2,34*，%)/）。从不同的随机全排列开始，进行多次计算，记录所得的最好结果作为算法的最终结果。
应该指出的是本文所述的启发式方法与文献［!］所述的最小增量法及最近插入法是不同的。最主要
的差别是本方法先把下一个插入的城市定下来，然后选择插入的位置，而文献［!］所述的算法则是根据插
入的情况选择下一个插入的城市。
插队算法的伪语言描述如下：
512（6760’8!；6760’!86760’ 3,*’9；6760’::）
｛ 生成城市的一个随机全排列，置入数组,-,3,;0 <&’&’［］中
512（=8!；=!8>；=::）1+3,*;0 <&’&’［=］8,-,3,;0 <&’&’［=］；
512（,8?；,!8@A"B CDE；,::）
｛94123’93,-62’*’-386,37=,93（1+3,*;0 <&’&’［!］，,-,3,;0 <&’&’［,］）
:6,37=,93（,-,3,;0 <&’&’［,］，1+3,*;0 <&’&’［F］）
G6,37=,93（1+3,*;0 <&’&’［F］，1+3,*;0 <&’&’［!］）；
512（H8!；H!8,G!；H::）
｛,5（H!,G!）
6&22’-3,-62’*’-386,37=,93（1+3,*;0 <&’&’［H］，,-,3,;0 <&’&’［,］）
:6,37=,93（,-,3,;0 <&’&’［,］，1+3,*;0 <&’&’［H:!］）
G6,37=,93（1+3,*;0 <&’&’［H:!］，1+3,*;0 <&’&’［H］）；
,5（H8,G!）
6&22’-3,-62’*’-386,37=,93（1+3,*;0 <&’&’［H］，,-,3,;0 <&’&’［,］）
:6,37=,9（,-,3,;0 <&’&’［,］，1+3,*;0 <&’&’［!］）
G6,37=,93（1+3,*;0 <&’&’［!］，1+3,*;0 <&’&’［H］）；
,5（6&22’-3,-62’*’-3!894123’93,-62’*’-3）
｛94123’93,-62’*’-386&22’-3,-62’*’-3；
,-9’23 +0;6’8H；
｝
｝
512（58!；5!8,-9’23 +0;6’；5::）
32;-9,3,1- <&’&’［5］81+3,*;0 <&’&’［5］；
32;-9,3,1- <&’&’［,-9’23 +0;6’:!］8,-,3,;0 <&’&’［,］；
512（58,-9’2 +0;6’:F；5!8,；5::）
32;-9,3,1- <&’&’［5］81+3,*;0 <&’&’［5G!］；
512（58!；5!8,；5::）
1+3,*;0 <&’&’［5］832;-9,3,1- <&’&’［5］；
IJ 运 筹 与 管 理 FII>年第!F卷
万方数据
｝
如果所得的路径长度小于记录的最优路径，则置最优路径为所得路径
｝
其中，!"!#$ %&’$(表示循环的次数，)*+, -./为城市的个数，!&%"0&(%（’，1）为城市’，1之间的距
离，&1&%&2# 34$4$［］存放初始队列，56%&’2# 34$4$［］存在最终得到的最优队列，%721(&%&51 34$4$［］是起传
递作用的中间数组。(857%$(%&1!7$’$1%表示插入一个城市时的最短路径增量，!477$1%&1!7$’$1%表示插
入在当前位置时的路径增量。&1($7% 6#2!$表示最佳插入位置。
!"# 首尾固定插队算法及嵌套插队算法
为了使所得的解进一步被优化，需要用下面所述的首尾固定插队算法来进行局部优化。
先用插队算法得到一个近优解（在近优解中，城市的排列也接近最优队列），然后从所得近优解的局部
截取一段旅行路径，再按插队算法的思想对所截取的局部路径进行优化。为了使优化后的局部路径能够
合理地接回到近优解，必须保证这个局部路径的首尾城市固定。这个过程相当于在一个顺序队列（9$:
34$1%&2#;4$4$）中的插队过程。如果所得的局部路径长度小于其原来的长度，就用新的局部路径取代原
来的局部路径。我们把优化一个局部路径的算法叫做首尾固定插队算法（<$20210+2&#=&>$0;4$4$:
?4’6&1@A#@57&%8’，<+=;?A）。
首尾固定插队算法的算法的伪语言描述如下：
开始
用;?A
!
算法生成一个近优解
!
从近优解上截取一段局部路径
用<+=;?A算法对局部路径进行优化
!
产生一个新的局部路径
新的局部路径
!
短于原有路径？
"
-
,
!
接受新的局部路径作为当前局部路径
是否满足算法
!
终止条件？
,
!
结束
#
-
图B 嵌套插队算法的流程图
=&@B =#5C!827%5D-?;A
D57（!"!#$EB；!"!#$$E!"!#$ %&’$；!"!#$FF）
｛令&1&%&2# 34$4$［B］E首城市，&1&%&2# 34$4$［G］E
尾城市。
把中间的城市随机排列以后置入&1&%&2# 34$4$［H］
⋯⋯&1&%&2# 34$4$［#5!2# -./］中
D57（0EB；0$EG；0FF）56%&’2# 34$4$［0］E&1&:
%&2# 34$4$［0］；
D57（&EH；&$E#5!2# -./；&FF）；
｛(857%$(% &1!7$’$1%E!&%"0&(%（56%&’2# 34$4$
［B］，&1&%&2# 34$4$［&］）
F!&%"0&(%（&1&%&2# 34$4$［&］，
56%&’2# 34$4$［G］）
I!&%"0&(%（56%&’2# 34$4$
［B］，56%&’2# 34$4$［G］）；
D57（JEB；J$&IB；JFF）
｛!477$1% &1!7$’$1%E!&%"0&(%（56%&’2#
34$4$［J］，&1&%&2#
34$4$［&］）
F!&%"0&(%（&1&%&2#
34$4$［&］，56%&’2#
34$4$［JFB］）
I!&%"0&(%（56%&’2#
34$4$［J］，56%&’2#
34$4$［JFB］）；
&D（!477$1% &1!7$’$1%$E
(857%$(%&1!7$’$1%）
｛(857%$(%&1!7$’$1%E!477$1%&1!7$’$1%；
&1($7% 6#2!$EJ；
｝
BK第L期 翟东海，等：用嵌套插队算法解决+9M问题
万方数据
｝
!"#（!$%；!!$&’()#* +,-.)；!//）
*#-’(&*&"’ 01)1)［!］$"+*&2-, 01)1)［!］；
*#-’(&*&"’ 01)1)［&’()#* +,-.)/%］$&’&*&-, 01)1)［&］；
!"#（!$&’()#* +,-.)/3；!!$&；!//）
*#-’(&*&"’ 01)1)［!］$"+*&2-, 01)1)［!4%］；
!"#（!$%；!!$&；!//）
"+*&2-, 01)1)［!］$*#-’(&*&"’ 01)1)［!］；
如果所得的路径长度小于记录的最优路径，则置最优路径为所得路径
其中，5".-, 678为被优化的局部路径中的城市个数，其他变量的含义与插队算法的算法描述中相
同。
插队算法和首尾固定插队算法结合使用会使解的质量大幅度提高，我们把插队算法和首尾固定插队
算法结合使用所构成的新算法叫做嵌套插队算法（6)(*)9:1)1);<12+&’=>,="#&*?2，6:<>）。嵌套插队算
法的流程图如图%所示。
3 实例验证及结果分析
!"# 用插队算法对$%&’()#、*+&,-.)/的计算结果
用插队算法求解@?&’-A%及B,&C)#AD的EFG问题的结果如表%（循环次数为HDD次）。其中，E"+*：得到已知最
优解的次数；G"+*：得到已知最优解的概率。国内对@?&’-A%的EFG问题的研究结果参见文献［3;I］。
表# 用插队算法对$%&’()#及*+&,-.)/的计算结果
实 例 执行次数 !"#$ %"#$ 运算时间（&）
BC,&C)#AD HD HD %DDJ DKLMA
@?&’-A% HD HD %DDJ DK%DM
与其他众多求解EFG问题的算法相比，插队算法具有时间复杂度低，解的质量稳定（能以很大的概率
得到已知最优解），算法结构清楚，实现简单（全部@程序不到%DD行）的优点。
值得提出的是：如果把插队算法略加修改，记录每次循环的结果，按路径长度加以排序，就可以一次得
到EFG问题的多个近优解。作者对@?&’-A%问题，记录了%DDD次循环的结果，得到了文献［I］中的全部
近优解。
!"! 用嵌套插队算法对$%&’(#00的求解结果
用模拟退火算法（F>）和锐化空间模拟退火算法（F>FFF）计算所得结果如表3所示（为执行HD次所得
结果）［N］，为了便于比较，用嵌套插队算法求解@?&’-%LL的结果也放在表3中（执行HD次所得结果）。其
中，局部优化时所用的近优解为执行%D次插队算法所得的最好结果。
表! 三种算法计算$%&’(#00所得计算结果（单位：公里，秒）
算 法
结 果
平 均 最 好 最 差
长度 时间 长度 时间 长度 时间
标准退火 ADNM%OI A%ION ADLADON A%PON A%%MDOP 3PHOP
锐化退火 ADNLAOL 3LNO3 ADAHIOD 3D3OA A%%H3ON 3HDO%
嵌套插队算法 ADLNAOI N%OD ADAHHO% N%OD ADI3IOA N%OD
目前，@?&’-%LLEFG的已知最优解为ADAHIOD（结果把每两城市之间的距离取整，路径长度为
ADALN）［N］。用嵌套插队算法找到的一条最短路径也为ADAHIOD（距离取整后为ADALM），其遍历图（如图3）
与文献［N］中的已知最优解的遍历图也完全一样。两者的取整结果之所以不一致可能是因为所用的取整
3H 运 筹 与 管 理 3DDA年第%3卷
万方数据
函数不同所致。另外，用嵌套插队算法找到的其他几个次短路径的取整长度依次为!"!#!，!"!##，!"!$"。
其中，长度为!"!$"的路径与文献［%"］中的一致。
图& 目前已知的最短路径 图! 用嵌套插队算法找到的最短路径
用嵌套插队算法找到的最短路径为!"!##’%（距离取整为!"!($），其遍历图见图!。
路径质量的定义为：所得路径的长度比已知最短路径高出的百分比。三种算法所得路径的平均长度
的路径质量如表!所示。可以看出嵌套插队算法优于模拟退火算法及锐化模拟退火算法。
表! 平均路径长度的质量比较结果
算 法 模拟退火 锐化退火 嵌套插队算法
路径质量 %’(() %’&$) "’!*)
"#! 用嵌套插队算法对$%&!’(、)**+!"的求解结果
用来测试嵌套插队算法性能的实例是：+,-!%$、.//#!&。它们的原始数据来源于网址0/1：／／230/4,56
7,8969:;的目录／1;5／/214,5下的<=>+?@。
采用经典冷却进度表时，用模拟退火算法（=.）和两阶段模拟退火算法（<==.）计算所得结果如表(
所示［$］。采用自适应冷却进度表时，用模拟退火算法（=.）和两阶段模拟退火算法（<==.）计算所得结果
如表#所示［$］。所有平均结果都是运行&"次的平均结果［$］。
表, 文献［(］中采用经典冷却进度表时的结果
实 例
模拟退火算法 两阶段模拟退火算法
平均A>B时间（2） 平均路径长度 平均A>B时间（2） 平均路径长度
+,-!%$ %&#’*$ (!&*#’& $C’D! (!!C#’%
.//#!& D#%’C" $*###’* !(#’(* $*D($’D
表+ 文献［(］中采用自适应冷却进度表时的结果
实 例
模拟退火算法 两阶段模拟退火算法
平均A>B时间（2） 平均路径长度 平均A>B时间（2） 平均路径长度
+,-!%$ %C&&’*$ (&$D*’D C"!’&& (&$!#’"
.//#!& %"%"(’C" $$%"#’# D"((’%C $$%D&’%
用嵌套插队算法计算的结果如表D所示（平均值为运行&"次后的平均）。其中，局部优化时所用的近
优解为执行%"次插队算法所得的最好结果。
表- 用嵌套插队算法所得的结果
实 例
平均 最好 最差
时间（!） 长度 时间（!） 长度 时间（!） 长度
+,-!%$ &!#’& (&#($’" &!(’* (&!#( &!#’C (&C($
.//#!& !D%’# $$"*"’D !D%’& $C#($ !D&’! $*C%D
比较的结果显示：（%）对于+,-!%$、.//#!&，嵌套插队算法都能用较短的时间，却取得了更短的平均路
径长度，而且计算时间是合理的。（&）对于A>B的运行时间，嵌套插队算法每次所用时间的变化很小，而
!#第(期 翟东海，等：用嵌套插队算法解决<=>问题
万方数据
模拟退火算法和两阶段模拟退火算法，!"#所用时间的变化却较大。特别是当采用自适应冷却进度表
时，变化就更大。显然，在不降低解的质量的前提下，嵌套插队算法明显优于模拟退火算法和两阶段模拟
退火算法。
!"# 用嵌套插队算法对$%#&’的求解结果
$%"&’(中的)*+*,问题是一个已知最优解的$%"问题，这样就能用一个比较客观的标准来判断所
得的质量。文献［-］中，用嵌套划分算法（./01/2"3415156789:6451;<，简称."）和其他启发式算法相结合
（=>6?1，@>6?1）计算了)*+*,问题，结果如表,所示。其中，路径质量的定义见=A=。
用嵌套插队算法对)*+*,计算*B次所得的结果如表C所示。其中，局部优化时所用的近优解为执行
=B次插队算法所得的最好结果。路径质量定义同上。
表’ 文献［(］对$&#&’的计算结果
方 法 路径质量 !"#时间（0）
=>6?1，起始路径随机选择 *+ADE **=
."算法结合=>6?1
*+ABE @F
+A-E +*--
@>6?1，起始路径随机选择 BA,CE =BD=-C
."算法结合@>6?1 *A@DE =F@DC
BAF*E *@@*=-
表) 用嵌套插队算法计算&*次所得的结果
实 例 平均 最好 最差
)*+*,
路径质量 !"#时间（0） 路径质量 !"#时间（0） 路径质量 !"#时间（0）
BA@*E =+B BABC+E =@C BAF+CE =+=
从)*+*,的计算结果可以看出，嵌套插队算法所得的质量明显好于文献［-］。可见，嵌套插队算法是
解决$%"问题的一种极具竞争力的算法。
@ 结论
本文提出的插队算法（GH8）结合了启发式算法和随机化算法的思想，其用于求解较大规模$%"问题
的改进形式嵌套插队算法（.GH8），更进一步结合了局部寻优的思想，即当问题规模较大时，再把这种方
法用于对局部旅行路径的优化上。实例验证的结果表明对于规模较小的$%"问题，用插队算法就能在合
理的!"#时间内以很大的概率找到已知最优解。对于规模较大的问题，用嵌套插队算法能在合理的
!"#时间内找到一个高质量的近优解。这些实验结果表明，嵌套插队算法是一种很有竞争力的求解$%"
问题的算法。嵌套插队算法是作为求解$%"问题的方法提出的，但其思想方法给求解其他."难解的组
合优化问题提供借鉴意义。
参考文献
［*］卢开澄I计算机科学组合学丛书：单目标、多目标与整体规划［J］I清华大学出版社，*---I
［=］靳蕃，范俊波，谭永东I神经网络与神经计算机［J］I西南交通大学出版社，*--*I
［@］陈沐天，蔡和熙I货郎担问题的几何分块算法及!;573$%"问题的最终解决［H］I计算机科学与工程，K69=B，.6*I)/L*--CI
［+］周培德I货郎担问题的几何解法［H］I软件学报，*--F（D）I
［F］于志伟，陶波，王元美I一种竞争算法及其在组合优化问题上的应用［H］I软件学报，*--C（*B）I
［D］鄢烈祥I用列队竞争法解旅行商问题［H］I运筹与管理，*---（@）I
［,］高国华，沈林成，常文森I求解$%"的空间锐化模拟退火算法［H］I自动化学报，*---，=F（@）I
［C］JM3437/995H3</0，!6;667H3</0"I8N301</1;62N64:/7/4395O/20134157:1/<?/431P4/2/1/4<573156757;6<6:/7/6P01Q6>013:/05<P931/237>
7/3957:0R01/<［H］I!6<?P1/4372S?/4315674/0/34T;，=D（*---）：+C*>FB@I
［-］%;5&/RP37，!93N0067%5:P42P4，%:I./Q?34399/943726<5O/239:6451;<0N641;/143M/957:039/0<37?46L9/<［H］I!6<?P1/4372S?/431567
4/0/34T;，=D（*---）@,*>@-+I
［*B］康立山，谢云，尤矢勇，罗祖华I非数值并行算法（第一册）：模拟退火算法［J］I北京：科学出版社，*--+I
+F 运 筹 与 管 理 =BB@年第*=卷
万方数据
