楊平樂，崔曉燕，劉樹森

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

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

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

基于改進蟻群算法的物流網(wǎng)絡

楊平樂1，崔曉燕2，劉樹森3

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

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

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

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

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

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

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

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

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

1 樞紐容量受限的軸-輻式網(wǎng)絡設計模型

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

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

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

2 蟻群算法模型

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

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

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

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

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

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

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

3 用改進的蟻群算法解決CSAHLP的策略

3.1 改進蟻群算法的設計

蟻群算法固有的容易陷入局部最優(yōu)的缺點在CSAHLP問題中體現(xiàn)得比較明顯，相比于TSP問題來說，因為CSAHLP問題里蟻群選擇路徑的多樣性導致其運算過程中容易陷入局部最優(yōu).

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

舉例:對一般情況，解的構成假設有i，m通過k，l向j運送貨物，可用圖1描述.

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

圖1 解的描述Fig.1 Solution composition

圖2 解對Fig.2 Solution pair

改進的蟻群算法處理CSAHLP步驟如下.

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

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

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

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

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

3.2 局域搜索策略

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

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

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

3)設置新樞紐.將任一隨機的節(jié)點設為樞紐節(jié)點，生成只有1個節(jié)點的新組團.

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

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

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

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

4 仿真實驗與結果分析

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

表1 計算結果Table 1 Calculation results

表2 計算結果對比Table 2 Comparisons of results

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

5 結論

文中利用蟻群算法在求解組合優(yōu)化問題上的優(yōu)勢，最終的解以解對的形式構造，將6種局部搜索算法嵌入各并行計算的蟻群群組內(nèi)，以增強蟻群算法對最優(yōu)解的搜索能力，并結合AP數(shù)據(jù)庫進行了算例仿真試驗.實驗結果表明:改進的蟻群算法的確可以較好用于CSAHLP問題中，這樣解決了很多復雜的難以計算的選址問題.其本身是概率選擇算法，具有其他的固定算法所不能比擬的速度和便捷的優(yōu)勢.結合其他的一些成熟算法，應用前景將極為廣泛，能夠適應物流配送的多樣化發(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］ 喬彥平，張駿.基于一種改進遺傳模擬退火算法的TSP求解［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］ 李陽.軸輻式網(wǎng)絡理論及應用研究［D］.上海:復旦大學，2006.

［4］ 劉洪，葛少云，李慧.基于硬約束調(diào)節(jié)的改進粒子群無功優(yōu)化［J］.天津大學學報，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中基于蟻群模擬退火算法的移動Agent訪問路徑規(guī)劃［J］.西北工業(yè)大學學報，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］.交通運輸系統(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］.系統(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.

(責任編輯:童天添)

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

國家自然科學基金資助項目(50575043，60573006)

楊平樂(1983—)，男，講師，研究方向為人工智能、量子密碼.E-mail:plyoung@126.com