楊麗馨

（唐山市第十二中學(xué)，河北 唐山 063000）

基于混合蟻群算法的“多日游”路線優(yōu)化問(wèn)題

楊麗馨

（唐山市第十二中學(xué)，河北 唐山 063000）

針對(duì)“多日游”路線優(yōu)化問(wèn)題，提出了一種新的混合蟻群算法，并建立了“多日游”旅游交通路線的數(shù)學(xué)模型。通過(guò)多次實(shí)驗(yàn)和計(jì)算，證明將混合蟻群算法運(yùn)用于“多日游”旅游交通線路，可以有效求得問(wèn)題的最優(yōu)解或近似最優(yōu)解，并以秦皇島地區(qū)各旅游景點(diǎn)為例進(jìn)行了分析。

“多日游”旅游交通路線；混合蟻群算法；路徑優(yōu)化

“多日游”旅游交通路線優(yōu)化問(wèn)題的研究在旅游研究領(lǐng)域中具有十分重要的理論和現(xiàn)實(shí)意義。在旅游企業(yè)中，找到一組費(fèi)用最小、旅游景點(diǎn)最多的旅游路徑，可有效降低成本、提高服務(wù)效益并增加總體經(jīng)濟(jì)效益，因此，采取科學(xué)合理的方法確定旅游路線是一項(xiàng)非常重要的工作。蟻群算法是一種來(lái)自大自然的隨機(jī)搜索尋優(yōu)方法，是生物界的群體啟發(fā)行為，現(xiàn)已應(yīng)用于組合優(yōu)化、人工智能等多個(gè)領(lǐng)域。蟻群算法的正反饋性和協(xié)同性使其可用于分布式系統(tǒng)，隱含的并行性使之具有極強(qiáng)的發(fā)展?jié)摿?。已有文獻(xiàn)[1,2]用蟻群算法對(duì)“多日游”路線優(yōu)化問(wèn)題進(jìn)行了研究并取得較好的效果。本文在前人研究的基礎(chǔ)上，將混合蟻群算法用于多日游路線優(yōu)化問(wèn)題，以期為旅游企業(yè)的決策提供理論指導(dǎo)。

1 混合蟻群算法原理

本文蟻群算法是以TSP（旅行商問(wèn)題）的蟻群算法為基礎(chǔ)，充分考慮VRP（車(chē)輛路徑問(wèn)題）的具體要求，并在此基礎(chǔ)上對(duì)算法的選擇機(jī)制、更新機(jī)制以及協(xié)調(diào)機(jī)制做進(jìn)一步改進(jìn)，引入自適應(yīng)的轉(zhuǎn)移策略和信息素更新策略，并融合大洪水算法、節(jié)約法等方法，以克服蟻群算法計(jì)算時(shí)間長(zhǎng)、易出現(xiàn)停滯的缺陷[3-5]。

1.1 混合蟻群算法設(shè)計(jì)

1.1.1 算法基本規(guī)則[6-8]

1.1.1.1 轉(zhuǎn)移規(guī)則

借鑒Dorigo的Ant-Q算法思想，采用確定性選擇和隨機(jī)性選擇相結(jié)合的轉(zhuǎn)移策略。

1.1.1.2 信息素更新規(guī)則[9]

信息素更新采用局部更新和全局更新相結(jié)合的策略。

1）局部更新規(guī)則

定義1 設(shè)經(jīng)過(guò)結(jié)點(diǎn)i的螞蟻數(shù)為R，經(jīng)過(guò)有向邊(i, j)的螞蟻數(shù)為r，則稱(chēng)r/R為邊(i, j)的螞蟻吸引力。

在進(jìn)行信息素局部更新時(shí)，若每次施放的信息素量Q為常量，則(i, j)的螞蟻吸引力越大，經(jīng)過(guò)邊(i, j)的螞蟻相對(duì)其它的邊來(lái)說(shuō)數(shù)量越多，從而局部更新的次數(shù)就越多，久而久之，會(huì)導(dǎo)致邊之間的信息素量差距過(guò)大，限制算法搜索的全局性。Q值也會(huì)影響算法的搜索效率，Q值過(guò)大會(huì)使算法易收斂于局部極小值，過(guò)小又會(huì)影響算法的收斂速度。隨著算法搜索狀態(tài)的變化，Q值也應(yīng)該不斷調(diào)整，調(diào)整的原則是，邊的吸引力越大，t時(shí)刻的信息素量Q(t)越小，不妨設(shè)Q(t) = Q(1-r/R)，t為時(shí)刻。

假設(shè)第k只螞蟻在第nc次迭代周期中的第f次轉(zhuǎn)移時(shí)經(jīng)過(guò)邊(i, j)，在此之前共有Rk只螞蟻經(jīng)過(guò)i點(diǎn)，其中有rk只螞蟻選擇了邊(i, j)，于是得到算法的局部更新規(guī)則如下：

2）全局更新規(guī)則

在所有螞蟻均構(gòu)造完路徑后，對(duì)所有可行解以及迄今為止最優(yōu)解的邊進(jìn)行全局信息素更新。采取的規(guī)則如下

p2p當(dāng)(i, j) ∈L*時(shí)，Δ=Q3D( L*)，否則Δτ*ij=0。其中，D( Ap)表示第p個(gè)可行解的路徑長(zhǎng)度，D(L*)表示迄今為止最優(yōu)解的路徑長(zhǎng)度；ρ2表示更新后信息素的揮發(fā)度；Q2、Q3分別表示對(duì)應(yīng)時(shí)刻的信息素量；Ap為第p個(gè)可行解。

3）負(fù)反饋機(jī)制

蟻群算法的選擇機(jī)制就是使好的路徑以較大的概率選中，而正反饋機(jī)制又必然會(huì)促使這些路徑在以后的選擇中更具競(jìng)爭(zhēng)優(yōu)勢(shì)。當(dāng)搜索陷入局部最優(yōu)解時(shí)，算法無(wú)法從局部極小值點(diǎn)跳出來(lái)，為此引入負(fù)反饋機(jī)制，包括：（1）借鑒MIN-MAX的思想，將各個(gè)路徑上的信息量限定在某個(gè)固定的范圍內(nèi)，以便在一定程度上減少路徑之間信息素濃度差距；（2）在全局更新時(shí)，加入負(fù)反饋信息量，即讓Q2Q3<0，以減少該局部解所對(duì)應(yīng)路徑上的信息素量。

1.1.2 可行解問(wèn)題

在VRP中，每只螞蟻所構(gòu)造的回路僅是可行解的一個(gè)組成部分，各螞蟻所構(gòu)造的回路可能組成一些可行解，但也可能一個(gè)可行解都得不到。如果得不到可行解，則該次迭代除施加了局部信息素影響外對(duì)最優(yōu)解的搜索未有任何影響，若經(jīng)常出現(xiàn)這種情況，則顯然會(huì)浪費(fèi)大量的計(jì)算時(shí)間。因此如何有效避免無(wú)可行解現(xiàn)象是算法設(shè)計(jì)的一個(gè)關(guān)鍵問(wèn)題?？梢圆扇∫韵虏呗裕海?）大螞蟻數(shù)策略。增加算法的螞蟻數(shù)量M，擴(kuò)大組合范圍，從而增加可行解產(chǎn)生的可能性；（2）螞蟻初始分布均勻策略。在每次迭代前，將螞蟻隨機(jī)均勻分布于各個(gè)結(jié)點(diǎn)，從而增加發(fā)現(xiàn)可行解的機(jī)會(huì)；（3）多周期螞蟻組合策略。在螞蟻數(shù)較少情況下，可以將本次迭代中各螞蟻所產(chǎn)生的回路和往次未發(fā)現(xiàn)可行解的迭代（一次或多次）所產(chǎn)生的子回路進(jìn)行組合；（4）近似解可行化策略。在找不到可行解的情況下，選擇一些和可行解接近的非可行解作為問(wèn)題的近似解，再按照某些規(guī)則（如節(jié)約法等）將近似解轉(zhuǎn)變成可行解。當(dāng)算法不存在可行解時(shí)，采取該策略顯然可以保證獲取至少一個(gè)可行解。

1.2 混和蟻群算法的步驟

混合蟻群算法求解VRP問(wèn)題的步驟如下：

（1）初始化各參數(shù)，輸入系統(tǒng)基礎(chǔ)數(shù)據(jù)，設(shè)找到的最優(yōu)解為L(zhǎng)*，迭代計(jì)數(shù)器nc=0；

（2）將M個(gè)螞蟻隨機(jī)均勻地放到N個(gè)結(jié)點(diǎn)上，得到結(jié)點(diǎn)i的螞蟻集Si和螞蟻數(shù)bi，初始化螞蟻k的已走點(diǎn)集tabuk以及候選點(diǎn)集allowedk；l表示已旅游完一天的螞蟻數(shù)，l=0；初始點(diǎn)為0的螞蟻的過(guò)程變量Pro[k]=1，初始點(diǎn)為非0點(diǎn)的螞蟻的過(guò)程變量Pro[k]=2；

（3）在結(jié)點(diǎn)i取螞蟻k，判斷其初始結(jié)點(diǎn)。若為0點(diǎn)，按轉(zhuǎn)移規(guī)則確定結(jié)點(diǎn)j，更新tabuk、Si、bi。并且若Pro[k]=1，則Pro[k]=2，轉(zhuǎn)步驟3；而當(dāng)Pro[k]=2時(shí)，若j點(diǎn)為初始結(jié)點(diǎn)，則l++，轉(zhuǎn)步驟3；否則轉(zhuǎn)步驟4。若為非0點(diǎn)，則按轉(zhuǎn)移規(guī)則確定轉(zhuǎn)移結(jié)點(diǎn)j，更新tabuk、Si、bi。并且當(dāng)Pro[k]=1時(shí)，若j點(diǎn)為0，則Pro[k]=2，轉(zhuǎn)步驟3；當(dāng)Pro[k]=2時(shí)，若j點(diǎn)為初始結(jié)點(diǎn)，則l = l+1，轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟4；

（4）更新Si，重復(fù)步驟3-4直到該結(jié)點(diǎn)的螞蟻數(shù)量bi=0為止；

（5）重復(fù)步驟3-5，直到所有結(jié)點(diǎn)的bi=0；

（6）在所有螞蟻都移動(dòng)一次后，按局部更新規(guī)則對(duì)所有路徑的信息素進(jìn)行更新；

（7）更新所有結(jié)點(diǎn)的bi，若所有結(jié)點(diǎn)上螞蟻數(shù)量bi=0或l = M，轉(zhuǎn)下一步，否則轉(zhuǎn)步驟3；

（8）由各螞蟻的tabuk得到路徑集

在L中尋找可行解，得到可行解集

若未發(fā)現(xiàn)可行解，實(shí)施多周期螞蟻組合策略生成L-ch子回路集，再在L-ch中尋找可行解。若仍未發(fā)現(xiàn)可行解，則采取近似解可行化策略，轉(zhuǎn)下一步。

（9）采用大洪水算法對(duì)可行解集A中各個(gè)可行解進(jìn)行局部?jī)?yōu)化，得到A′，計(jì)算本次搜索到的最優(yōu)路徑L*(nc)，并得到迄今為止的最優(yōu)路徑，

L*=min{L*(nc),L*}，nc為迭代計(jì)數(shù)；

（10）若算法陷入停滯，采用負(fù)反饋機(jī)制調(diào)整路徑上的信息素，并調(diào)大r0，否則按全局更新規(guī)則進(jìn)行信息素的全局更新；

（11）判斷nc是否等于最大迭代次數(shù)ncmax，若是，則算法終止，輸出L*；否則，nc++，轉(zhuǎn)步驟2。

2 實(shí)驗(yàn)及分析

2.1 實(shí)例仿真

設(shè)有20個(gè)旅游景點(diǎn)（JD）隨機(jī)分布于邊長(zhǎng)為10 km的正方形區(qū)域內(nèi)。休息地位于區(qū)域正中央，其坐標(biāo)為(0, 0)。各旅游地游玩所需時(shí)間也由計(jì)算機(jī)隨機(jī)產(chǎn)生，每天的游玩時(shí)間為9 h?；A(chǔ)數(shù)據(jù)如表1所示，其中tdp為單個(gè)景點(diǎn)游玩的時(shí)間（h）。

表1 實(shí)驗(yàn)基礎(chǔ)數(shù)據(jù)

采用的參數(shù)為M=60，最多迭代次數(shù)ncmax=50，τij=10，游玩最多公里數(shù)MAX=100，游玩最少公里數(shù)MIN=2，α=1，β=1，γ=0.5，ρ1=0.85，ρ2=0.95，Q1=10，Q2=50，Q3=100，r0=1。運(yùn)行10次，結(jié)果如表2所示，其中為平均最小行走距離（km），T為（游玩）所用天數(shù)（d），ncf為首次搜索終解代數(shù)，tc為計(jì)算用時(shí)（s），為行走距離與最小行走距離差（km）。

表2 實(shí)驗(yàn)計(jì)算結(jié)果

從表2可以看出，用蟻群算法的10次求解中，都得到了質(zhì)量很高的解。其中最好解為41.86 km，路線1：0-18-0；路線2：0-1-17-14-8-0；路線3：0-12-6-7-4-3-19-0；路線4：0-2-10-11-16-13-5-15-9-0。蟻群算法的計(jì)算結(jié)果穩(wěn)定，10次求解中最差解的游玩里程僅比最好解多5.8%。從計(jì)算效率看，10次求解的平均計(jì)算時(shí)間為2.14 s，計(jì)算效率較高，有效地解決了計(jì)算時(shí)間長(zhǎng)的問(wèn)題。從上述分析可見(jiàn)，對(duì)于VRP，利用蟻群算法可取得比較理想的結(jié)果，且計(jì)算結(jié)果穩(wěn)定。

為了便于比較，分別用爬山法、遺傳算法、模擬退火算法對(duì)該實(shí)例求解了10次，解的搜索次數(shù)都為15 000次，4種算法的計(jì)算結(jié)果見(jiàn)表3，其中Ddev為解的標(biāo)準(zhǔn)差。

表3 爬山法、遺傳算法、模擬退火算法及蟻群算法比較

由表3不難看出，從尋優(yōu)結(jié)果看，蟻群算法明顯優(yōu)于其它3種算法；從計(jì)算效率看，蟻群算法低于爬山算法和模擬退火算法，但高于遺傳算法；從算法的穩(wěn)健性看，蟻群算法計(jì)算結(jié)果的穩(wěn)定性明顯優(yōu)于其它3種算法。

2.2 運(yùn)行參數(shù)和算法策略對(duì)蟻群算法性能的影響

2.2.1 運(yùn)行參數(shù)對(duì)蟻群算法搜索性能的影響

蟻群算法的運(yùn)行參數(shù)主要有螞蟻數(shù)M、基本信息素量τij、轉(zhuǎn)移規(guī)則各相對(duì)重要性參數(shù)（α、β、γ、λ）、信息素的持久度（ρ1、ρ2）以及施放量（Q1、Q2、Q3）等。本文僅以螞蟻數(shù)M為例討論運(yùn)行參數(shù)對(duì)算法搜索性能的影響。

對(duì)上述實(shí)例，分別取M =30、40、50、60、70、80、90、100，τij=20， ncmax=50， MAX=80， MIN=2，α=2，β=1，γ=0.5，λ=0.2，ρ1=0.85，ρ2=0.95，Q1=5，Q2=50，Q3=100，r0=1，各運(yùn)行50次，結(jié)果如表4所示，其中為平均迭代步數(shù)。

表4 螞蟻數(shù)M對(duì)蟻群算法性能的影響分析表

由表4可以看出，螞蟻數(shù)較大時(shí)，解的質(zhì)量比較高，但隨著螞蟻數(shù)的不斷增加，解的質(zhì)量的提高越來(lái)越不明顯，而計(jì)算時(shí)間卻大幅度增加。因此就本實(shí)例而言，采用60～80個(gè)螞蟻就可以了。

2.2.2 算法策略（SC）對(duì)蟻群算法搜索性能的影響

實(shí)驗(yàn)中發(fā)現(xiàn)，若不采取任何可行解獲取策略，較大規(guī)模問(wèn)題的蟻群算法基本發(fā)現(xiàn)不了可行解，因此對(duì)大螞蟻數(shù)策略、螞蟻初始分布均勻策略、多周期螞蟻組合策略以及近似解可行化策略等4個(gè)策略以及它們之間的組合進(jìn)行實(shí)驗(yàn)比較，具體分析6種算法：SC1，采取小螞蟻數(shù)（M =40）和初始螞蟻分布均勻策略；SC2，采取大螞蟻數(shù)（M =80）和初始螞蟻分布均勻策略；SC3，在SC1的基礎(chǔ)上，增加多周期螞蟻組合策略；SC4，在SC1的基礎(chǔ)上，增加近似解可行化策略；SC5，在SC2的基礎(chǔ)上，增加近似解可行化策略；SC6，在SC4的基礎(chǔ)上，添加多周期螞蟻組合策略。分別對(duì)前述實(shí)例求解，最大迭代次數(shù)為20，各運(yùn)行20次，結(jié)果如表5所示，其中ncn為找不到解的迭代數(shù)，為平均無(wú)可行解數(shù)。

表5 算法策略對(duì)蟻群算法性能的影響分析表

由表5可見(jiàn)，SC3相對(duì)SC1而言，雖然計(jì)算時(shí)間稍長(zhǎng)，但其求解質(zhì)量有較大提高，而相對(duì)SC2而言，其計(jì)算結(jié)果和平均無(wú)可行解次數(shù)均比較接近，而計(jì)算時(shí)間卻有較大幅度的節(jié)省。后3種算法由于引進(jìn)了近似解可行化策略，因此不存在無(wú)可行解的問(wèn)題。SC4的計(jì)算結(jié)果質(zhì)量較前3者有很大提高。在各種算法中，計(jì)算結(jié)果最好的為SC5，其平均計(jì)算結(jié)果為43.13 km，離問(wèn)題最好解41.86 km相當(dāng)接近，其原因在于它既采用了大螞蟻策略，又采用了近似解可行化策略，但計(jì)算時(shí)間也最長(zhǎng)。

3 實(shí)例分析——秦皇島地區(qū)“多日游”交通路線模型

3.1 模型建立

表6 實(shí)驗(yàn)基礎(chǔ)數(shù)據(jù)

秦皇島旅游區(qū)域內(nèi)現(xiàn)有12個(gè)旅游景點(diǎn)，其基礎(chǔ)數(shù)據(jù)如表6所示，休息地位于區(qū)域正中央的天下第一關(guān)，各景點(diǎn)游玩所需時(shí)間tdp（h）由實(shí)際估計(jì)得到。

3.2 模型求解

假設(shè)：（1）采用的運(yùn)行參數(shù)為M=60，ncmax=50，τij=10，MAX=100，MIN=2，α=1，β=1，γ=0.5，ρ1=0.85，ρ2=0.95，Q1=10，Q2=50，Q3=100，r0=1；（2）每天的游玩時(shí)間為9 h；（3）運(yùn)行10次。按上述混合蟻群算法計(jì)算，結(jié)果如表7所示。

表7 實(shí)驗(yàn)計(jì)算結(jié)果

從表7中可以看出，用蟻群算法的10次求解中，都得到了質(zhì)量很高的解，其中最好解為83.72 km，路線1的行走路徑為0-1-3-0；路線2為0-2-7-0；路線3的為0-8-6-0；路線4的為0-11-10-12-0；路線5的為0-9-5-4-0。蟻群算法的計(jì)算結(jié)果也較穩(wěn)定，10次求解中，最差解的游玩里程僅比最好解多5.8%。從計(jì)算效率看，10次求解的平均計(jì)算時(shí)間為2.14 s，計(jì)算效率較高?？梢?jiàn)，對(duì)于VRP，利用蟻群算法可取得比較理想的結(jié)果，且計(jì)算結(jié)果也較穩(wěn)定。

4 結(jié)論

將蟻群算法引入到VRP中來(lái)，通過(guò)分析VRP與TSP的區(qū)別，構(gòu)造了適于求解VRP的蟻群算法。為減少計(jì)算時(shí)間，避免算法停滯，對(duì)算法的選擇機(jī)制、更新機(jī)制以及協(xié)調(diào)機(jī)制作了進(jìn)一步研究，并融合了大洪水算法以及節(jié)約法等方法。在此基礎(chǔ)上，本文所設(shè)計(jì)的自適應(yīng)混合蟻群算法不但具有很強(qiáng)的發(fā)現(xiàn)較好解的能力，還具有較高的計(jì)算效率，計(jì)算結(jié)果相當(dāng)穩(wěn)定。

[1] 王大志,汪定偉,閆楊.一類(lèi)多旅行商問(wèn)題的計(jì)算及仿真分析[J].系統(tǒng)仿真學(xué)報(bào),2009,21(20)∶6378-6381.

[2] 李偉,趙瑜.基于蟻群算法的“多日游”線路優(yōu)化問(wèn)題[J].

中國(guó)物流與采購(gòu),2009(10)∶76-77.

[3] 姜啟源,謝金星,葉俊.數(shù)學(xué)模型[M].北京∶高等教育出版社,2003∶111-120.

[4] 李士勇.蟻群算法及其應(yīng)用[M].哈爾濱工業(yè)大學(xué)出版社, 2004∶10-98.

[5] 馬良,朱剛,寧愛(ài)兵.蟻群優(yōu)化算法[M].科學(xué)出版社,2008∶35-112.

[6] 邢文訓(xùn),謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].清華大學(xué)出版社, 1999∶102-135.

[7] 高尚,楊靜宇.群智能算法及其應(yīng)用[M].水利水電出版社, 2006∶9-157.

[8] 雷德明,嚴(yán)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M].科學(xué)出版社,2009∶22-38.

[9] 劉任任.算法設(shè)計(jì)與分析[M].武漢理工大學(xué)出版社, 2003∶40-47.

（責(zé)任編輯、校對(duì)：趙光峰）

Optimization Problem about the Choice of “Multi-Day” Tourism Route Based on Hybrid Ant Colony Algorithm

YANG Li-xin

(Tangshan No.12 Middle School, Tangshan 063000, China)

For the “multi-day” line optimization, a new hybrid ant colony algorithm is proposed and a “multi-day” tourist traffic route model is established. Through experiments and calculations, it shows that the optimal solution or near optimal solution can be effectively obtained when the hybrid ant swarm algorithm is applied to the “multi-day” tourist traffic lines.

“multi-day” tourism route; hybrid ant colony algorithm; path optimization

F59

A

1009-9115(2013)05-0037-04

10.3969/j.issn.1009-9115.2013.05.011

2013-05-09

楊麗馨（1968-），女，唐山人，碩士，高級(jí)教師，研究方向?yàn)樽顑?yōu)化。