基于改進(jìn)蟻群算法的物流網(wǎng)絡(luò)

楊平樂(lè)，崔曉燕，劉樹(shù)森

(1.江蘇科技大學(xué)張家港校區(qū)基礎(chǔ)教學(xué)部，江蘇張家港 215600)

(2.東南大學(xué)交通學(xué)院，江蘇南京 210096)

(3.中山大學(xué)信息科學(xué)與技術(shù)學(xué)院，廣東廣州 510006)

基于改進(jìn)蟻群算法的物流網(wǎng)絡(luò)

楊平樂(lè)1，崔曉燕2，劉樹(shù)森3

(1.江蘇科技大學(xué)張家港校區(qū)基礎(chǔ)教學(xué)部，江蘇張家港 215600)

(2.東南大學(xué)交通學(xué)院，江蘇南京 210096)

(3.中山大學(xué)信息科學(xué)與技術(shù)學(xué)院，廣東廣州 510006)

文中將受容量限制的單分配軸-輻式網(wǎng)絡(luò)抽象為一個(gè)三次變量的混合整數(shù)線性規(guī)劃模型方程;提出了一種改進(jìn)的蟻群算法，將6種局域搜索算子加入算法中，因此具有較高的全局搜索能力和局部搜索能力;同時(shí)提出“解對(duì)”的概念，對(duì)問(wèn)題的構(gòu)成進(jìn)行分解優(yōu)化，轉(zhuǎn)化為確定問(wèn)題，切實(shí)使本問(wèn)題符合蟻群算法使用的前提和優(yōu)勢(shì);最后，使用澳大利亞郵政的數(shù)據(jù)進(jìn)行選址仿真實(shí)驗(yàn)，驗(yàn)證此算法模型在該應(yīng)用中的求解效率和計(jì)算穩(wěn)定性.

軸-輻式網(wǎng)絡(luò);改進(jìn)蟻群算法;解對(duì);受限樞紐選址

軸-輻式網(wǎng)絡(luò)往往來(lái)描述這樣一類問(wèn)題［1］:在一個(gè)包含多個(gè)點(diǎn)的圖集中，所有的點(diǎn)都發(fā)送和接受貨物.在這種問(wèn)題的某一個(gè)子集中，所有貨物的流動(dòng)都必須經(jīng)過(guò)其中某個(gè)特殊節(jié)點(diǎn)，文中稱這個(gè)特殊節(jié)點(diǎn)為樞紐點(diǎn)，稱該子集中的其他點(diǎn)為分配給該樞紐點(diǎn)的節(jié)點(diǎn).

軸-輻式網(wǎng)絡(luò)越來(lái)越多地應(yīng)用于郵政、航空和電信等領(lǐng)域，是現(xiàn)代化物流系統(tǒng)的模型［2］.在設(shè)計(jì)物流系統(tǒng)時(shí)，物流樞紐選址需要模型化、數(shù)量化，樞紐點(diǎn)的合理選址能夠減少貨物運(yùn)輸費(fèi)用，降低運(yùn)營(yíng)成本，促進(jìn)生產(chǎn)和消費(fèi)兩種流量的協(xié)調(diào)配合.一個(gè)樞紐點(diǎn)的存在使得貨物傳輸過(guò)程中重新查找路徑選擇成為可能，同樣也引起了網(wǎng)絡(luò)構(gòu)建成本和運(yùn)輸成本的變化.軸-輻式網(wǎng)絡(luò)在實(shí)際的物流網(wǎng)絡(luò)設(shè)計(jì)中，其樞紐點(diǎn)的容量不可能無(wú)限制，因此研究容量受限的軸-輔式網(wǎng)絡(luò)更有實(shí)際意義.文中將研究樞紐容量受限的單分配軸-輻式網(wǎng)絡(luò)選址問(wèn)題(capacitated single allocation hub location problems，CSAHLP)的解決策略.

樞紐選址問(wèn)題是一個(gè)多目標(biāo)、多約束的組合優(yōu)化問(wèn)題.國(guó)內(nèi)外學(xué)者針對(duì)物流模型與算法展開(kāi)了一系列的研究，建立了一系列的選址模型與算法，如重心法、數(shù)值分析法、模擬退火算法和遺傳算法等［3-7］.但這些方法應(yīng)用的側(cè)重點(diǎn)有所不同，對(duì)于求解規(guī)模較大的實(shí)際問(wèn)題存在困難.

文中研究了澳大利亞郵遞系統(tǒng)樞紐選址問(wèn)題，提出了一種改進(jìn)的蟻群算法求解該問(wèn)題，確定系統(tǒng)成本最低的樞紐點(diǎn)和結(jié)點(diǎn)的位置、規(guī)模和數(shù)量.文中將改進(jìn)蟻群算法用來(lái)求解CSAHLP問(wèn)題.

1 樞紐容量受限的軸-輻式網(wǎng)絡(luò)設(shè)計(jì)模型

CSAHLP問(wèn)題其實(shí)是樞紐選址問(wèn)題，也可表述為物流中轉(zhuǎn)站選址問(wèn)題(中轉(zhuǎn)站容量受限)，樞紐選址問(wèn)題是軸-輻式網(wǎng)絡(luò)設(shè)計(jì)的關(guān)鍵，主要包括3方面內(nèi)容:確定樞紐節(jié)點(diǎn)的數(shù)量、樞紐節(jié)點(diǎn)的選址以及將非樞紐節(jié)點(diǎn)分配給樞紐節(jié)點(diǎn).

求解整個(gè)網(wǎng)絡(luò)運(yùn)行費(fèi)用成本最低是方程的目標(biāo)函數(shù)，此費(fèi)用包括樞紐節(jié)點(diǎn)固定設(shè)施費(fèi)用和總的運(yùn)輸費(fèi)用之和.

綜上所述，可用三次線性方程描述CSAHLP問(wèn)題的模型，如式(1).

2 蟻群算法模型

可以這么來(lái)看蟻群算法:基于解空間參數(shù)化概率分布模型的搜索算法框架［8］，在該算法中，求解空間參數(shù)化概率，信息素就是模型的參數(shù)，因而信息素模型就是這種參數(shù)化概率分布模型.基于模型的搜索算法中，通過(guò)在一個(gè)解空間參數(shù)化概率分布模型上的搜尋產(chǎn)生可行解，用產(chǎn)生的解來(lái)更新此模型的信息素，促使在新模型上的搜索能夠聚集在高質(zhì)量的解搜索空間內(nèi)［9-12］.

具體算法步驟及參數(shù)設(shè)定如下:

1)在每個(gè)周期的循環(huán)中，蟻群中的每個(gè)螞蟻解決問(wèn)題時(shí)，他們一邊移動(dòng)，一邊構(gòu)成自己的解，直到螞蟻構(gòu)成所有的解.

2)在每只螞蟻完成求解時(shí)，根據(jù)解的構(gòu)成進(jìn)行信息素更新.螞蟻通過(guò)信息素交換各自的解.通過(guò)信息素的更新，使得解空間趨向優(yōu)化區(qū)域.下一只螞蟻的移動(dòng)方向和移動(dòng)方向的概率，以及以后螞蟻選擇移動(dòng)路徑，由更新之后的信息素來(lái)決定.

更新所用的公式如下所示:

式中q0∈(0，1)是常數(shù)，q∈(0，1)是隨機(jī)數(shù)，τgh(i，j)為解構(gòu)成部分(i，j)的信息素，ηg(i，j)為解構(gòu)成(i，j)啟發(fā)式因子，α為螞蟻在爬行過(guò)程中積累的信息量在蟻群搜索過(guò)程中的重要程度，β為啟發(fā)式因子的相對(duì)強(qiáng)弱.Jgh(r)為被第g個(gè)蟻群中的第h個(gè)螞蟻在步驟r中能加入到解構(gòu)成中.在下一步之前隨機(jī)產(chǎn)生q.如果q的值不大于常數(shù)q0，就從余下全部可行的解構(gòu)成之中找出［τgh(i，j)］α·［ηg(i，j)］β最大的那個(gè)解構(gòu)成，也就是接下來(lái)要被選擇的解構(gòu)成;如果q的值大于常數(shù)q0，則按方程(9)計(jì)算出來(lái)的概率來(lái)選擇下一個(gè)解構(gòu)成.

4)每一個(gè)周期循環(huán)中，找到達(dá)到最優(yōu)目標(biāo)函數(shù)值的螞蟻，然后由其更新關(guān)于解構(gòu)成的全局信息素，使用的公式如下:

3 用改進(jìn)的蟻群算法解決CSAHLP的策略

3.1 改進(jìn)蟻群算法的設(shè)計(jì)

蟻群算法固有的容易陷入局部最優(yōu)的缺點(diǎn)在CSAHLP問(wèn)題中體現(xiàn)得比較明顯，相比于TSP問(wèn)題來(lái)說(shuō)，因?yàn)镃SAHLP問(wèn)題里蟻群選擇路徑的多樣性導(dǎo)致其運(yùn)算過(guò)程中容易陷入局部最優(yōu).

在用蟻群算法解決CSAHLP問(wèn)題時(shí)引入了禁忌表搜索方法，該算法顯著收縮每一步解空間的分布，能夠加快收斂，可以在有限次循環(huán)中得到較優(yōu)解.同時(shí)采用與局域搜索策略相結(jié)合的方法，以達(dá)到避免陷入局部最優(yōu)，同時(shí)加快算法的收斂速度.利用多只螞蟻以樞紐選址模型的總成本最低為依據(jù)劃分樞紐點(diǎn)和節(jié)點(diǎn)，為更好地表述想要的結(jié)果，文中提出解對(duì)的概念，在CSAHLP問(wèn)題中，把一個(gè)節(jié)點(diǎn)i和其對(duì)應(yīng)的樞紐點(diǎn)k稱為一個(gè)解對(duì)，特別的，為了下面解的有序性將樞紐點(diǎn)k和樞紐自身k也稱為一個(gè)解對(duì).

舉例:對(duì)一般情況，解的構(gòu)成假設(shè)有i，m通過(guò)k，l向j運(yùn)送貨物，可用圖1描述.

有了解對(duì)的概念后，文中把CSAHLP問(wèn)題的解分解為多個(gè)離散解對(duì)的構(gòu)成.經(jīng)過(guò)解對(duì)模型處理后可以得到以下數(shù)個(gè)解對(duì)(圖2).不難看出，在CSAHLP問(wèn)題中，有多少個(gè)城市對(duì)就有多少個(gè)解對(duì)，解分解為解對(duì)后，將此問(wèn)題轉(zhuǎn)變?yōu)榇_定問(wèn)題，便于算法求解.

圖1 解的描述Fig.1 Solution composition

圖2 解對(duì)Fig.2 Solution pair

改進(jìn)的蟻群算法處理CSAHLP步驟如下.

2)下面開(kāi)始尋找解對(duì):每只螞蟻挑選一個(gè)隨機(jī)化的城市序列，開(kāi)始構(gòu)造解對(duì)，從第一個(gè)城市開(kāi)始構(gòu)造解對(duì)，在每一個(gè)城市上kj螞蟻都運(yùn)用偽隨機(jī)比例選擇規(guī)則，使用式(8，9)尋找與其關(guān)系最強(qiáng)的城市構(gòu)成ksp，文中用數(shù)組鏈接的方式標(biāo)記為comba［kj］= kjsp，特別注意的是，標(biāo)記完后需要把 ksp的 comba［kjsp］標(biāo)記成comba［kjsp］=kjsp，以防止后續(xù)運(yùn)算中ksp指向其他別的城市，即樞紐不再和已知以外的點(diǎn)構(gòu)成任何解對(duì).找到解對(duì)后，把Cap(ksp)容量減去Weight(kj)，即Cap(ksp)=Cap(ksp)-Weight(kj)，體現(xiàn)容量限制的約束.每只螞蟻都根據(jù)此步驟構(gòu)造自己的解.

3)計(jì)算目標(biāo)函數(shù)值:每只螞蟻爬行完途中所有點(diǎn)后，對(duì)解對(duì)進(jìn)行整理，依據(jù)式(1)計(jì)算出目標(biāo)函數(shù)值L.

4)局部信息素更新:每只螞蟻計(jì)算完目標(biāo)函數(shù)值L后，對(duì)其解對(duì)進(jìn)行局部信息素更新.

5)全局信息素更新:每個(gè)周期循環(huán)中目標(biāo)函數(shù)值L最小的那只螞蟻將根據(jù)自己的解對(duì)進(jìn)行全局信息素更新.

6)連續(xù)多次計(jì)算，如結(jié)果之差小于ε，則保存解，并清空禁忌搜索表，否則轉(zhuǎn)向步驟2.

3.2 局域搜索策略

蟻群算法需與局域搜索策略相結(jié)合才能更好發(fā)揮作用.文中引入局域搜索算法以避免陷入局部最優(yōu)，并加快收斂速度.文中參照文獻(xiàn)［13］提出的6種局域搜索算子進(jìn)行運(yùn)算.在介紹這6種局域搜索算子前要定義組團(tuán)，組團(tuán)是指劃分節(jié)點(diǎn)群，群內(nèi)含有1個(gè)樞紐節(jié)點(diǎn)和被分配給該樞紐的非樞紐節(jié)點(diǎn)，其中樞紐節(jié)點(diǎn)被分配給其自身.以下是6種局域搜索算子:

1)重置樞紐.將任一組團(tuán)內(nèi)另一隨機(jī)選取的節(jié)點(diǎn)置為新樞紐節(jié)點(diǎn)，該轉(zhuǎn)換應(yīng)用于那些至少包含 1個(gè)非樞紐節(jié)點(diǎn)的組團(tuán).

2)重置節(jié)點(diǎn).將任一組團(tuán)的1個(gè)非樞紐節(jié)點(diǎn)分配給另一隨機(jī)選取的組團(tuán).尤其是當(dāng)某個(gè)組團(tuán)內(nèi)只包含1個(gè)節(jié)點(diǎn)時(shí)，那么將該節(jié)點(diǎn)分配給其他組團(tuán)，就減少了組團(tuán)的數(shù)量.

3)設(shè)置新樞紐.將任一隨機(jī)的節(jié)點(diǎn)設(shè)為樞紐節(jié)點(diǎn)，生成只有1個(gè)節(jié)點(diǎn)的新組團(tuán).

4)合并組團(tuán).將某個(gè)組團(tuán)內(nèi)的所有節(jié)點(diǎn)分配給另外1個(gè)隨機(jī)選取的組團(tuán)內(nèi)的樞紐節(jié)點(diǎn)，實(shí)現(xiàn)了這2個(gè)隨機(jī)選取的組團(tuán)合并為1個(gè)組團(tuán).

5)分裂組團(tuán).將1個(gè)組團(tuán)內(nèi)的部分節(jié)點(diǎn)分配給另一隨機(jī)的非樞紐節(jié)點(diǎn)，分裂為2個(gè)組團(tuán).

6)交換節(jié)點(diǎn).將2個(gè)組團(tuán)內(nèi)的非樞紐節(jié)點(diǎn)對(duì)換分配給對(duì)方組團(tuán)的樞紐節(jié)點(diǎn).

所有這些局域搜索算子在運(yùn)算過(guò)程中都受容量約束限制，且對(duì)于每個(gè)蟻群，應(yīng)在局域搜索完成后進(jìn)行本身蟻群算法的全局更新.如上局域搜索算子的運(yùn)算遵循最先允許準(zhǔn)則［14］，某個(gè)局域搜索算子帶來(lái)更合理的目標(biāo)函數(shù)值，那么就將解更新.

4 仿真實(shí)驗(yàn)與結(jié)果分析

文中使用澳大利亞郵政數(shù)據(jù)對(duì)此方法進(jìn)行了驗(yàn)證.這是目前應(yīng)用于CSAHLP問(wèn)題的基準(zhǔn)數(shù)據(jù)庫(kù)，含澳200個(gè)郵政中心的坐標(biāo)、包裹數(shù)量、運(yùn)輸費(fèi)用、固定設(shè)施費(fèi)用以及節(jié)點(diǎn)容量約束，設(shè)定折扣系數(shù)χ為3，α為0.75，δ為2.固定設(shè)施費(fèi)用的類型被分為緊型(T型)和松型(L型)，在固定設(shè)施費(fèi)用為T(mén)型的問(wèn)題中，流量較大的節(jié)點(diǎn)其固定建設(shè)費(fèi)用也較高，使得這些節(jié)點(diǎn)難以被設(shè)定為樞紐，因此這類問(wèn)題難于求解.對(duì)于L型的問(wèn)題則不會(huì)如此.同時(shí)，容量約束也被分為緊型(T型)和松型(L型)，用來(lái)表示容量約束的強(qiáng)弱程度.所以，相同規(guī)模的問(wèn)題可被分為4種類型:LL，LT，TL和TT型.文中分別針對(duì)節(jié)點(diǎn)數(shù)為10，20和25的情況進(jìn)行仿真試驗(yàn).

表1 計(jì)算結(jié)果Table 1 Calculation results

表2 計(jì)算結(jié)果對(duì)比Table 2 Comparisons of results

從實(shí)驗(yàn)結(jié)果可以清晰看到樞紐點(diǎn)確定情況和節(jié)點(diǎn)分配情況，計(jì)算結(jié)果表明:對(duì)于較難求解的25個(gè)節(jié)點(diǎn)的雙緊約束問(wèn)題，算法運(yùn)算時(shí)間為1.01s，運(yùn)算偏差不大于0.12%，遠(yuǎn)低于已有的其他算法，具有更優(yōu)的求解效果，很好地證明了這種解決方案的可行性和可靠性.25TT以下的數(shù)據(jù)各次結(jié)果都是經(jīng)過(guò)數(shù)次運(yùn)行得到的最優(yōu)解，且與已被證明的最優(yōu)解相同.此算法在設(shè)計(jì)過(guò)程中加入了一些合并組團(tuán)的方法，隨機(jī)合并一些樞紐點(diǎn)，減少了解的個(gè)數(shù).

5 結(jié)論

文中利用蟻群算法在求解組合優(yōu)化問(wèn)題上的優(yōu)勢(shì)，最終的解以解對(duì)的形式構(gòu)造，將6種局部搜索算法嵌入各并行計(jì)算的蟻群群組內(nèi)，以增強(qiáng)蟻群算法對(duì)最優(yōu)解的搜索能力，并結(jié)合AP數(shù)據(jù)庫(kù)進(jìn)行了算例仿真試驗(yàn).實(shí)驗(yàn)結(jié)果表明:改進(jìn)的蟻群算法的確可以較好用于CSAHLP問(wèn)題中，這樣解決了很多復(fù)雜的難以計(jì)算的選址問(wèn)題.其本身是概率選擇算法，具有其他的固定算法所不能比擬的速度和便捷的優(yōu)勢(shì).結(jié)合其他的一些成熟算法，應(yīng)用前景將極為廣泛，能夠適應(yīng)物流配送的多樣化發(fā)展.

References)

［1］ Randall M.Solution approaches for the capacitated single a location hub location problem using ant colony optimization［J］.Computational Optimization Applications，2008，39:239-261.

［2］ 喬彥平，張駿.基于一種改進(jìn)遺傳模擬退火算法的TSP求解［J］.計(jì)算機(jī)仿真，2009，26(5):205-208.

Qiao Yanping，Zhang Jun.Traveling salesman problem solving based on an improved genetic simulated annealing algorithm［J］.Computer Simulation，2009，26(5): 205-208.(in Chinese)

［3］ 李陽(yáng).軸輻式網(wǎng)絡(luò)理論及應(yīng)用研究［D］.上海:復(fù)旦大學(xué)，2006.

［4］ 劉洪，葛少云，李慧.基于硬約束調(diào)節(jié)的改進(jìn)粒子群無(wú)功優(yōu)化［J］.天津大學(xué)學(xué)報(bào)，2009，42(9):796-801.

Liu Hong，Ge Shaoyun，Li Hui.Reactive power optimization based on improved particle swarm optimization algorithm with hard restriction regulation［J］.Journal of Tianjin University，2009，42(9):796-801.(in Chinese)

［5］ Alumur S，Kara B Y.Network hub location problem: the state of the art［J］.European Journal of Operational Research，2008，190(1):1-21.

［6］ Lee Der-Horng，Dong Meng.A heuristic approach to logistics network design for end-of-lease computer products recovery［J］.Transportation Research Part E，2008，44(3):455-474.

［7］ Galski R L.Application of a GEO+SA hybrid optimization algorithm to the solution of an inverse radiative transfer problem［J］.Inverse Problems in Science＆Engineering，2009，17(3):321-334.

［8］ 張亞明，史浩山，劉燕，等.WSNs中基于蟻群模擬退火算法的移動(dòng)Agent訪問(wèn)路徑規(guī)劃［J］.西北工業(yè)大學(xué)學(xué)報(bào)，2012，30(5):629-635.

Zhang Yaming，Shi Haoshan，Liu Yan，et al.A better itinerary analysis for mobile agent(MA)through using ACA-SAA algorithm in wireless sensor networks［J］.Journal of Northwestern Polytechnical University，2012，30(5):629-635.

［9］ Srivastava S K.Network design for reverse logistics［J］.The International Journal of Management Science，2008，36(4):535-548.

［10］ 王保華，何世偉.不確定環(huán)境下物流中心選址魯棒優(yōu)化模型及其算法［J］.交通運(yùn)輸系統(tǒng)工程與信息，2009，9(2):69-74.

Wang Baohua，He Shiwei.Robust optimization model and algorithm for logistics center location and allocation under uncertain environment［J］.Journal of Transportation Systems Engineering and Information Technology，2009，9(2):69-74.(in Chinese)

［11］ Yu Hongtao，Xue Jingling，Wei Huo，et al.Level by level:making flow-and context-sensitive pointer analysis scalable for millions of lines of code［C］∥Proc of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization.New York:ACM Press，2010:218-229.

［12］ Pearce J，Kelly P J，Hankin C.Efficient field-sensitive pointer analysis for C［J］.ACM Trans on Programming Languages and Systems，2007，30(1):37-42.

［13］ 秦進(jìn)，史峰.物流設(shè)施選址問(wèn)題的雙層模擬退火算法［J］.系統(tǒng)工程，2007.25(2):36-40.

Qin Jin，Shi Feng.Bi-level simulated annealing algorithm for facility location［J］.Systems Engineering，2007，25(2):36-40.(in Chinese)

［14］ Costa M D G，Captivo M E，Climaco J.Capacitated single allocation hub location problem-A bi-criteria approach［J］.Computers and Operations Research，2008，35(11):3671-3695.

(責(zé)任編輯:童天添)

Logistics network based on improved ant colony algorithm

Yang Pingle1，Cui Xiaoyan2，Liu Shusen3
(1.Department of Basic Courses，Zhangjiagang Campus，Jiangsu University of Science and Technology，Zhangjiagang Jiangsu 215600，China)
(2.School of Transportation，Southeast University，Nanjing Jiangsu 210096，China)
(3.School of Information Science and Technology，Sun Yat-sen University，Guangzhou Guangdong 510006，China)

Capacitated single allocation hub-and-spoke networks can be abstracted as a mixed integer linear programming model equation with three variables.By introducing an improved ant colony algorithm which has six local search operators and the"Solution Pair"concept to decompose and optimize the composition of the problem，it can become specific and more effective to meet the premise and advantages of using ant colony algorithm.Finally，location simulation experiment is made with Australia Post data to demonstrate that this algorithm has high efficiency and stability for solving this problem.

hub-and-spoke network;improved ant colony algorithm;solution pair;capacitated hub location

TP15

A

1673-4807(2014)01-0166-05

10.3969/j.issn.1673-4807.2014.02.013

2013-09-03

國(guó)家自然科學(xué)基金資助項(xiàng)目(50575043，60573006)

楊平樂(lè)(1983—)，男，講師，研究方向?yàn)槿斯ぶ悄堋⒘孔用艽a.E-mail:plyoung@126.com