旅行商问题算法研究综述_陈文兰

第D卷 第期’

滁

州学 院 学 报

G7=VD ,V= %W9’!"V"#

!""#年 # 月

1%X,YZ[ S1Q?X\ ?1 XX,]HG/Y].

^旅行商问题算

研法究综

述陈兰文 树贵戴

（滁 学院州 学系，数安 滁徽州! ’"+"）"

摘

旅行问题是一个商典经 ,的-完 问题 全 由于，在许多其域领内有具实际的用价应值， 一有直多学众者要 ：

对其行进研。究文本介绍从. / 模型入手-， 据旅行商根题问的分类，概 介绍了近要五年来旅商行题问算的法 研究状，况 对并行旅商题未问的来研作了究展。

,-望 全完题； 旅问商行问题 ；精算法 0确 启式算发 法关词键：1 ２ １ Ａ２ １６３－７７９１ ０４－００３０１０－ ６中分图号： 类文标识献：码 文章编号：（ ０２６）

０文兰 陈（+2!*) ） ，，女 汉， 浙江族兴绍人， 士， 硕滁州院学数学系讲。 作者简师：

介 *引 旅言商行题 （ 问.453769: /487;67

U"K

8（

） * !） （ ’（

）

;@U8KFV

"

*， 边 86 在最K路径上优 ， " 68K边不在最优 路径上8 G

!!

UF*， 8

K "K8

徽安高省级自校然学科金基资项目 助!""（$%!#’& (） 。 金基项：目

"!#)"")*"&收 稿日：期

) *

)!# $

%

!"，! "!

""&

’（ ） （*）

!

$#!

!，"

""(

(， 为() 的子图

为 ,⑴-(.的 标目数函 ⑵/⑷限，定回路每上个求经 过所顶有点的回的最路小离距 其中+。(+图为( 的点数。 顶顶点仅一有入边和条一条出。 ⑸ 边定在回路限中不现子回出。路型实模上是在质个带权图中求一条一 01234!5 回路。若对6有所! ，，" "7&， 等式 不!8"9"87#8!7均 成立 则，称该题问满是足三不角式的等。: - .(算法 于 由(- .许多领域内的应用价在，值 众学者对多其进了行究， 研生产许了解多决该题问的法算另外，。 据该依题在问同领不域的用，应由 -(. ,又衍出生了许多该题的扩问问题展如不，对称 -. (（ ;=4?@13 !-.， (;(.- -）..(E ）-(G. ）、配送 收 集(- .（- ( A.!B4 .!7@D C16 8E3!F>>=，? 多人 、-(. G（C4!33D>- .( ，、大 规 5-(.G）（ H1 ?>I (-JH-(.. 、）多目标 - . ( G（C4!K3L">5@4 -(，. 、 时有间约束的-( （. -(. !4BA 4!2>模 -(.A !856A， @> -(.7N-J.(） 。下面等基 于(. 的-类分 分，概要别介绍几近年各类 来-(.算法的 研成果究 。O: %典 -经(., (. 是-在个一带无权完全图中找一向个值最小的权012! 4563回 。在路各类 -.(中 该类，问题研的成 究最多果。几近年， 来研者究者或基数于学论理造近构似算法， 或者用各使种仿然的算自框法结合架不同局的 搜索方部构造法混合法算同。时，神经网 和自组络图方织在该问题法上的用应研也引起究研了者究的注。关 OE>!6>75&P%Q建立了基R松于驰卡尔曼逊的阵矩（ ?>13># S83211671C>?B等 通过一个乘常量法子对因 B,?算 法进行了改修， 复度为杂（ 。 从 而立了一建个求解满不足角不三式的 等,-.(的具有常 数似率近高效近的算法似)?>。I5=? )C4!6 等XP基R于T 6）:似 理论然、图论、 群论及数论以理论的方和法立建一个时了间杂度为 （复 的近似算法— —贪—期婪望算法 I（>?>8K>D>@#441!56 31I5!?42B） U。Y?Z>2G5 654P6%R给出[一个了分近似算微。法这些 算法有较好具时间复的度， 可杂在较短以的时间求出内问题的似近优解最 但是对于有些，题问 算 法，求得的解的性所可能难能令人以满意 。\5?L>

搜索空间而从快求加速度。解立平郑P%*R通过混合等使多种用交算子杂， 出提一种了新 的,(- .的遗算法。传李 宇炳P等%R提出小窗口]蚁群法， 算并与基模式于的蚁群法相结算，合通过提取 模式和变计算改粒设度计了一个高 效的群蚁算。法 高尚P%R利用^混运沌动遍的历性 随、机性和律规性等点，特提出 了一新的种混沌群蚁算。 P法X% R燮孙华 对解 求,(.- 模的拟火退算作了改法，进增加 了产生解新的函，数 修改了算原计算法路总长回度的代价函数J 用混并随机序列替代沌适宜不随的机数。 函巍庞等P_R采用%模糊矩来阵示粒子的表置位和速J度并重新 义定更新其公J式提出了 种改进一粒的子 优化算群法。黄等P岚QR[过引入交换子和通交序换的概念 构，造种一殊的特粒子群优化法J 算并用于解 ,求-(.。算法通 过杂粒交子择机选J 制皓等P[谭%提R出种结合粒一群算法结构子和解求,-( .的 蚁算法群特点算法的 。运用设计的两种杂算交子 成功模J拟自然了界中同物种同种不间的协群作交流J 将多子群与策略和子间群 交操杂作引粒子群入构之结J 增中强算法的优能寻力。 高尚等P[R[合结遗传法算 蚁群、算和模法拟火退算的法想J思提出用 混粒合群子算法求来解,- .。(这 仿些自然算由于具法很强有空的搜间索能，力合恰当的结操作子算计和局设部优化策的略应用 ，所

K [K

构造的算

法都具有较强寻的优力能，通 常能得求人令满意的好最， 解相对但于述前的近算法似，这些 法算 执行的间时和果结的良优很性程度大取决于上作算操子设计，的 何设如出优良的计作操子是值得继算续研究的 问。 !题"#%$& #’% " 等)*+(过通对自织组图法中两算个适应参 数 !,"-#%.#& ./-）"（ 学习 （ 和邻率域函变量 数 （ "-#&0%1.0223 25#46%2# /".%"76-）#） 的 研，究 出了一给解个决8 9;:的 高自效组图算法。 (等)+研?究初了始方法化参数设及置则规，通过 者的两合，联 计出设了一个自织组图法算 算法，具有较的高 求精度解收敛速度。和 A.@%"38B"C.D--.% 2(等E)+过为 8通9;: 中每个的点赋予一个顶经元，神 并用神经元的值使表城市在示路 回中置位方法，的建立 了个一散多离 值2F4%$-,3模 型 以此，来求 8解:;。陆9生勋( G)+对应 F用2$4-%3, 网络解 8:; 的9算做了改进工作法 提，出了解F 24$%-, 3网络方程的态动消元算法， 服了初值和克数参不的稳性健 是， 一有效个求解 的89:; 的法方。HI@I 2680".#-等 (J和 +KL2&B#:M" N5-# &(等O)+出给基了自组织于与神经网络图的 89: 算;。 自组法织和神经图络由于网具自学有、习 想联储功能和存高寻速找优化的能力解， 于对合优组化问的题 求具有解一定的势优 ，们和它

其它法相方结合可设计出更具以智能性求的算法。 但是 解98; :解表的示相 关参及的设数置需要尚一进研步究。 其它对8 9; :的研中究 ，万颖瑜()等P+的作成工果值得是注的， 关们它求解 8对:; 的环9路构造法和环算 改路进算进法行了究研。过在通环中成路批入加顶，点并 构在过造程对环路中进局行优部化， 得到一了种被称为 : Q%:-",-6B8#C/25./6 算法R同时在分析的部最优局与解局最优全之解关间的系础上R基 出提另了个采一 用局部优最解交集的为初始作路环新算法—的——: Q%:6-,"B-S$D2.-。7 *I)不 称 9对;:若在 89; :模型中 ，个两点 顶% 和 间T距离 的3T 和 %T%3不一 相等定 则，称为U9 ;。:U9; :于由两点间离 的不对距称性， 所以解更求困难 ，但时同对于于基际交通实网络物流的配送来，说其 比8 :; 9更有实具应用际 值价 。V ?W ）闻卫振)J+针( U对9;: 利用 *，2B$ 迭代/取 89:;代求 中解 )的2B/$ 代迭 ，给出个时一间复杂为 度 ・ （@ 为顶点数） （W@ 两顶点为的最间距离， 的启大式迭发算法代:"#&。FB KL22 等#(*+X建立一个了候选弧Y很 有能出可现在最解中的弧Z集概念优 ，计设了定候确选的方弧法 ，此为基础以 通，实验过研究 ，设了计个衰减 函数用以求一 解U9:。S#B80;"#802% 等( *[+过通有的地目在种群中入引无效个体，并在 有效个和无效个体间体 行遗进传操作 构造了，个一解求 9:;U的 遗算传法。\ -.2&.]\ 5/#%等( *+的)究成研果于评对启发式算法价的能性具有重意要义他。认们 W为; 题问通常以难 多用式算法求得精项确，解所 通以以常造构多式近项算法来似得求近解似；或 者使各用启发式种法求算得 (**+ 好解较 ，是启但发式算缺法乏理支持。 他论们在^I \ 27-. 提,的评出价发式启法的支配率的基算础上出了 提评价发式启法性算能支配数的，并以此 基为础造构了个一启式发法，算 对并法算行了理论研究进 *I。*配 送收集9 ; 9:;:=; 由 8是9;:适 应物流配送领的实际需域而产求生的。 个问这题及到两涉类顾客要：需 类一是配送 需求 要求将，货物从配送心中送到需求点； 另一是类收集求需， 要求货将物需从点求运往配送中心。当有 的所配和收集需送求都由辆从配一中送心发出、 限定量的车辆容来成时，完怎 安排样行路线才驶构能成一条 行程短最 的FD"%,2# /回路 F%。_,$%/ 2F.-‘#3#-QBA;.Q- (等?+*假在设从户收客集的物可货被以运给其它客户送的基础上， 建了一个立 9;:=; 的XB [数线性整型， 并给模了一出个解求型模的分支剪算切法 由。于去过 的9;;=: 研究中，多 设先假配送再收集， 际实上问题转化为被向 9双;:问 。 题国学者内秉磊和谢 (+E霍 震在佳突此破设假的前提， 下

对 :;;=9进 了研行。谢究磊等秉 扩展模了拟退算法和爬山法等启发火式算 法指的准则导—— —-@./22$,% 接C受则 （准 若当前在的解邻内域索到搜的新 C解 T目标函的 4T数 于当小解 前C 的 目Z[随内机产一生 个#， 标数函4 时 R 受接新； 否解则 在YXR 当 -a，$(4Y4TBZb/cΔ 时+ ，受接解。新） ， 将其修为正：

* BB

当

"!! 时#受新接解$否则拒#绝受新解。以此为基础构造接一了个解求%&!!’ 的模拟退 火算法。霍 震佳 等()*+修以正的,-./ 013/25647节约 发式算启法和最近邻算法基础为进行入式排序插解了该决问题 。)89 人多行商问旅题 多即个行旅商历多遍个城， 在满足每市个城被市个一行旅商过经次的前提一， 下遍历求全部城市的 短最路径。决 解:%!&对 决解 “ 车辆度路调径排”安问题 有重要具意义过。的研去大多究 :将&%! 转化成多个 &%， 再!使用解 %求& !的算法行进解。 ; ? 等()@+合结胜全者取 （A4==/172.120.--） 竞的争制设机计了个一柱形竞争神的经络网模来型求 解%&:!。 对网络收敛于可行解进行了并分析论和证 代坤等。)(+B使用路径码编式， 并方专门针对: %&!设 了计遗 传子， 算造构了解求 %&:! 的遗传算法 C/7。?/ 6D 8./,7/ 等()1E+对有 个顶=和 F 点旅个商的行 :&%!设计了 种新的一度长 为=G F个体编的方 码式（ 个体 的 =前 位 H2= 是的数整一个的列排，后 位中F每一是位个一数，表整示旅该行商所责的负市 这城近几年在应是用传遗法求解算%& 的 !。数） ， 并据 此设了计传操作，遗给 出了个求一 :%解&! 的传遗算法。 研究中，少见的从改 变个体码编手的研入，究对遗 传法在 算&!% 的应用研究具有指导意义中 。)* 大规模 8&! %%&I! 一认为般是顶数超点 JK过K的 &!， 从%格严义意上说来， 它仍然是典的经 %&， 但是由于顶!点的 增数加 ，往会使常规往求解%& !的 算在法间时杂度复或解性能的不上令能满意人为此。 有些学者针，对 I%& !计了设求解算法。 ,6=512L .M%4 .等@+(出了一提多个种的蚁群群化优算法。 蚁群各首独先地立行搜索，进搜 索期间下式进 行信息按交换： 若%& (0 为 群种量数 ， 为一个种群A在信息 （4 表第示 4 个群，种 !"#%$&"!$#)%’(+ "#$%!’ 否* （ (则)）*H2A 示其它种表在信息素表中群的权重，K! !A。 NH。并 对针 %I& !出了提最多邻域和近双最素表 的中重，权

!

!

#$"%&"!$# （+"!#%$* ’% ’)*）

(近域邻法方对解行进优化。 &F?.1 C-8 ?:-1/P (9K等+并 出了该算法的通给模型用 。宁爱兵()O+提出等一种解决 I%了& 的!争决竞算策， 法自适将应共振理论入 引I=24Q/=1456. 局=部化算法， 结优合治分类聚， 法出给一个了 I4=2Q比/1=564= .和它 其种变更定并具有更高稳并行性算

的法。

2 9

2

行程尽能短。可 用路使编码径式方， 并此设计了启为发规则式 构，了造求 谢解磊秉!等"#"时将间窗约束化成目标转约束 具有，硬时间软限窗的制$%&。 爱宁兵!等’#"用利数学导和证明推出得了个一 ($% &下界快速估法， 算在此础上基利用竞决策算法争通 的用型， 给出了模一 ($%个& 竞争决的策算法 。" 结与总望展本文对一个经典的 & 完全问题—— —)行商问旅及题变种其近年的几究情况作了概研要介绍 。几近年，研 但是 ，由对于 %$&特 性认的的识加， 试图深使精用算法求确解 人员究试图用运种各法对方$%& 行求解进 ，$%& 的研究基本销匿迹，声取 而之代是的各近种方似；法 图使用试一方单法求 $解%& 题问的究研减少在， 使而多用方种结法合研的逐究渐占了研据究主流。的观近纵年几的究成果研， 究者主研要用使以下几了种

方 %&$ *对 法进了行研： 究 ） （用各使纯数学种的方法构造时复间杂为多项度式近的似法。 算 （） +用使规的常 ,-0/. 和其它局部优化法方回对路行优进 发式启法算：通首常先构一造所有个点回顶路然后，使 用,+-/、 .用遗使传法、算蚁 算法群、 模拟退火算、法 子群算法粒和经神络等仿网然自算。法由遗于算传法 、 蚁化 。 （0） 群法和算子粒群法具有较强的算群体索搜能， 但同力时存在可又能入陷局部优的最题问 ，因而研究通常者 其它搜索将法算和些算法相这合以构造更高效的混合算结法。经网络神自和织图由于具组有学习自、联 想储功能和存速高找寻化优解的力能 ，用使它和其它方法相结们合研究得的了到究者的研视。 重%$& 将仍算法研究领域是一的热点个问题。但 由于是 %& 的广$泛的际实应背用，景未 来相长时当间内 ，除有新非解决的合组优问题化的法框算架出，现各种 仿然的自算法合结部优局的化法算想仍将是思研究 重点的。合实结问际设题适当的计作操算子局和部优化策以构略造混合法算将是解决 $%&仍 重要途径的在 。现行的用利仿然算自对法$%& 进 的行究中，研 的表示方法似解乎经已为成限制破的突个一颈，瓶如果能 设计够新出型更的产易生更解优解的表示方的， 并据法此计设出解求法方， 将是$ %&算 法究研的破突 。!参 文考 #

!献*#231245/.- 67 $-/8 & 9%-5 )5; :3(428 42? -@(4?4> 13=/=53= A2-3/85 B DC:5/:=4 %25FC:42&3 -F5:G H#!9 24I>5:52/ 4 6 ( %9-F@=-/ -A 42P 235> 2%FC52:4 &3G-5F :H#9 !.53Q2/=-4C RC553282:=4:>$35 2/5:/ -4 A/85 $3E25F=> 4%F2C5:2 43&G-5F:! #H 7H9BI1*JM7， + （J ） !"#6953A54C5//5/H H 76-2F. 7R RC-:2/2= 7 5/ 2(9 F545/6= B-3=/:8 C-3 $3AE2F5=> %2F54:C4 2&3G-5F:B!! S4T9 &3-C - 2A S4453/2/=-424F -4A1553=3=-/8: C42?$ 5=3 B.8F=,V2 4C$=2718@,4W= $C2=758=1>,1482>4$C 45> 9 4B;5 DG8=?38 5@=3/C F42>53 /2E35F4=>C 25CF:2 .4-GF53 !:#9S4HA-:3/=-24 %=63- 6@D=/47B?45C 35-9Y&-FD 4:-2= F..23Z-:2/==4-2 F>3-/8=C :-3 /8A $5%&2 4 /?58 B[ ;&=/ 8 A2F25:2C4 &-G35F :!#H 95)@23 )5/F;3]C7- +L0，L 9（ M ）*! *L#^N59=4]59)-; 5Z5.454/-=2F 45>=8-G38-? A--3 .F-4-D:=2FD CFF-2EF5 $%GC!&H#9 \5

L， 9（ *）X! **#2_4CH-22F $9-;23C? 8/54 -/=4--A C/ G2F=/= -DA2 .3-Z.:=2=-/4A - 93 28? 3-.=/:O2==-4 //2CC]24? /85/3 25E=4>F 2FC5C24 :3-.FG5!H:#9$5835/=- C25C:24 F24 ?35F2/5?. -G35F: CH!9# SA-34:2/=-4&3 4 5P/53/7 +LCL+，9 （ K+ !）0*#-VG3C H5(93@-];C=] &9-Z=3=/: 24D?.3= -3/D=T2. .D=4F >2>54 55.3Z5C=-C42F -3=>8: /- /8/ $532EF54= %2F5>.C35-C &34-GF5:9 ! H# 923&2F5F F1-:./@4=> +7LL"，（ L）0

,

’,

!#$姜"华昌% 胡华幼 一种&解求旅行商题问的效混高合遗传法!算’$计&机工算程与用应， ())#， & (（(） ())* &， !"*郑立$， 平郝孝忠 基于混&合交杂的传算法求遗旅行商解题问!’&计$机算工，程（ ()） !"+$ 李宇炳 ，)(,， & )蕴诗 萧基&于式求模旅解商问题行蚁的算群!法$’同&大济学报， 学（"" & ）!-$高尚 "&解旅商问行题的混沌蚁算群!法’&$统系工理程论与践实()%)，* .（） "!/$燮华孙&用模拟退火 算法解行商旅题!问$&中’计国量学院学报(%))*，& "（ ） ()*，) & "!.$庞巍，等 & 模糊离粒散子优化群法算解求行旅问商题’$!&小型型计算机系统， （微/） ()!黄$岚，()),， &等 & 子粒优群化法算求解行商旅问题!$&吉’林大学学报（ 理学）版， #（ ）))*(， &!("$ 谭，皓 等&一 种基于子杂交机制群粒子群算法求解旅的商行问题!’$系统&工程 （，#） & !( $高尚( 等 &求，解旅商问行题的合粒混群子化算优法’$!控制与&决策%( )#) （，"） 78"2:295; 2 ?8AB:C5@21442D5E13? ?F 1CF85 A:G ?C:@4H52F:C@ ZA:C F852B 1Z K8\25Q P%4 QNB:5 ’422 %:25 B6;28^ &=2 Q8_3129254 8@A?B :C512D4425 82CQ1@ 8F>2CZ :A: C: %2 PQBR218] E4 S1%24B]G5Q 1]2&58N8CEF21F4:4 :A 2F

，& （(,） !"$d2 ,BJ1FF4?: H1@I@ 81M8?? 19 2@42Z58?1 >44F 1 33C:1F48C:?!’$&[8QCZ1 [8F@:>CZ%(?)), （，" + !#）"N:C1$8@I1V1E I:%1J T?C c851: L%C98 V:H@C& 8N11F F?CQMQC8?F1 9 8i2MF4:28M4DM V&8284FM @:M1 @?18C

戴辑支 $

祥

B+ B