求解無容量設施選址問題的混合蟻群算法

李　倩,　張惠珍,　Cesar Beltran-Royo

(1.上海理工大學 管理學院,上海　200093; 2.西班牙胡安卡洛斯大學 統(tǒng)計與運籌系,馬德里)

?

求解無容量設施選址問題的混合蟻群算法

李倩1,張惠珍1,Cesar Beltran-Royo2

(1.上海理工大學 管理學院,上海200093; 2.西班牙胡安卡洛斯大學 統(tǒng)計與運籌系,馬德里)

無容量設施選址(UFL)問題是經典的優(yōu)化問題,屬于NP難題,易于描述卻難于求解.首先,介紹了UFL問題的數(shù)學模型,并對UFL問題的特點進行深入分析,得到其最優(yōu)解所具有的基本特征;其次,針對UFL問題的最優(yōu)解所具有的基本特征,設計了兩種局部搜索策略,并將其與基本蟻群算法相結合,提出了一種用于求解UFL問題的混合蟻群搜索算法;最后,為了測試該算法的性能,分別利用混合蟻群算法和基本蟻群算法求解UFL問題基準問題庫中的16個測試算例.計算結果表明,混合蟻群算法有效改進了基本蟻群算法求解UFL問題時易陷入局部最優(yōu)、收斂速度慢等不足,該算法對求解UFL問題具有明顯的可行性和有效性.

無容量設施選址問題; 蟻群算法; 局部搜索

無容量設施選址問題(uncapacitated facility location,UFL)是從沒有限定容量大小的設施位置集合中選擇要開放的設施,使其以最小的代價服務于給定的所有客戶.無容量設施選址問題具有廣泛的實際應用背景,生活中許多實際的問題均可被抽象為UFL問題進行求解,如銀行選址、網絡設計、聚類分析、證券投資管理等.

目前,用于求解UFL問題的算法大致可以分為3類:近似算法、精確算法和智能優(yōu)化算法.在多項式時間內能夠求得問題的一個解,并且其目標函數(shù)值與最優(yōu)解的目標函數(shù)值之比不超過一個常數(shù)的算法被稱為近似算法[1].1997年,Williamson等[2]給出了求解設施選址問題的第一個常數(shù)近似度算法;2013年,Li[3]提出了求解UFL問題的1.488-近似算法.求解UFL問題的精確算法主要有:割平面算法、列生成算法、Erlenkotters算法[4]、分支定界法[5-6]等.這些算法能夠求得問題的最優(yōu)解,但適用于規(guī)模較小的問題,且計算速度慢.雖然智能優(yōu)化算法搜索效率高,適用于求解大規(guī)模的問題,但是這些算法容易陷入局部最優(yōu),一般情況下只能求得問題的滿意解,不一定是最優(yōu)解.為了克服單一智能優(yōu)化算法易陷入局部最優(yōu)、收斂速度慢等不足之處,近年來求解UFL問題的混合智能優(yōu)化算法得到了長足的發(fā)展,如:混合多層啟發(fā)式算法[7]、并行多粒子群優(yōu)化算法[8]、優(yōu)化啟發(fā)式算法[9]、啟發(fā)式并行局部搜索算法[10]等.

蟻群算法(ant colony algorithm,ACA)具有魯棒性強、可以進行分布式計算、易與其他算法有效結合等優(yōu)點,但其容易陷入局部最優(yōu)[11].針對UFL問題的具體特點,將兩種局部搜索策略與基本蟻群算法相融合[12-13],提出了一種求解UFL問題的混合蟻群算法,并通過求解系列經典UFL問題驗證該算法的求解性能.

1　無容量設施選址問題

給定建造無容量限制的設施位置集M={1,…,m},客戶集N={1,…,n},對于任意給定的i∈N和j∈M,cij表示客戶i與設施j之間的運輸費用,fj>0表示設施j的開放費用.要求每個客戶必須選擇一個且只能選擇一個設施來滿足其需求,同時使總費用最少.UFL問題的數(shù)學模型可被描述為

(1)

(2)

(3)

(4)

(5)

式中:z為目標函數(shù)值,即總費用;yj表示設施j是否開放,如果設施j選擇開放,則yj=1,否則yj=0;xij表示客戶i是否選擇設施j為其提供服務,如果客戶i選擇設施j為其提供服務,則xij=1,否則xij=0.

記X*為UFL問題(1)～(5)的最優(yōu)解集,分析UFL問題的具體特點,可以得到定理1.

計算使下式成立的j″:

這與(x*,y*)∈X*相矛盾.

2　混合蟻群算法的設計

2.1基本蟻群算法

蟻群算法是一種源于大自然中生物世界的新的仿生類算法,屬于隨機型搜索算法.其基本原理來自于昆蟲學家們對生物界中螞蟻搜索食物源的過程的觀察:螞蟻在搜索食物時,能在其經過的路徑上釋放一種螞蟻特有的分泌物——信息素,使得其他螞蟻可以感知并且影響其行為.當選擇某些路徑的螞蟻越來越多時,該路徑上累積的信息素就越多,以致后來螞蟻選擇該路徑的概率也越高,也就增加了該路徑的吸引強度,依靠這種生物機制,螞蟻最終可以找到一條到達食物源的最短路線.本文將這種螞蟻群體尋優(yōu)思想作一些修改和引申,以便符合所要求解的UFL問題.

(6)

(7)

表1輪盤賭法

Tab.1Roulette method

設施123456789Pkij0.180.160.150.130.110.090.070.060.03累計概率0.180.340.490.620.730.820.890.950.98

隨著時間的推移,螞蟻在路徑上留下的信息素逐漸衰減.記信息素衰減系數(shù)為ρ(0<ρ<1),螞蟻完成一次循環(huán)后,利用式(8)更新信息素為

(8)

式中:Q為常數(shù);zk為螞蟻k在本次循環(huán)中的目標函數(shù)值.

2.2局部搜索

在定理1的基礎上,設計了兩種求解UFL問題的局部搜索策略,并將其嵌入蟻群優(yōu)化算法,以有效改進由蟻群算法所求得的UFL問題的可行解.下面通過一個例子來對兩種局部搜索策略進行簡要介紹.

例給定一個m=5和n=5的UFL問題,該問題中客戶與設施之間的運輸費用矩陣C和設施安裝費用向量F分別為

F=[130,199,139,127,103]

該問題的最優(yōu)目標函數(shù)值為1 034.假設螞蟻算法中l(wèi)只螞蟻搜索一次所得的滿意解為:x14=1,x23=1,x32=1,x42=1,x55=1,y1=0,y2=1,y3=1,y4=1,y5=1.即:開放的設施集合為{2,3,4,5};客戶1選擇設施4;客戶2選擇設施3;客戶3和4選擇設施2;客戶5選擇設施5;總費用為199+139+127+103+1 224+1 749+1 227+1 783+1 149=7 700.

利用兩種局部搜索策略對上述螞蟻算法的求解結果改進如下:

策略1以設施2所服務的客戶3和4為例,客戶集{3,4}分別被各個設施服務的費用為

設施1c31+c41+f1=1 488+1 235+130=2 853;

設施2c32+c42+f2=1 227+1 783+199=3 209;

設施3c33+c43+f3=1 240+1 831+139=3 210;

設施4c34+c44+f4=121+1 340+127=1 588;

設施5c35+c45+f5=1 375+112+103=1 590.

由上述計算結果及定理1可知,若客戶3和4選擇為其服務費用最小的設施4,則可使螞蟻算法的求解結果得以改進,則令x32=0,x42=0,x34=1,x44=1,y2=0,y4=1.改進后的結果為x14=1,x23=1,x34=1,x44=1,x55=1,y1=0,y2=0,y3=1,y4=1,y5=1,目標函數(shù)值計算結果為v=5 952.

策略2螞蟻算法的求解結果經策略1改進后,開放的設施集合為{3,4,5}.由定理1知:給定開放的設施集合,每個客戶應選擇運輸費用最小的開放設施為其服務.

客戶1由min {c13,c14,c15}=min {1 354,1 224,192}=192得設施5應為客戶1提供服務,則令x14=0,x15=1;

客戶2由min (c23,c24,c25)=min (1 749,132,1 439)=132得設施4應為客戶2提供服務,則令x23=0,x24=1;

客戶3由min (c33,c34,c35)=min (1 240,121,1 375)=121得客戶3的服務設施保持不變,仍為設施4,即x34=1;

客戶4由min (c43,c44,c45)=min (1 831,1 340,112)=112得設施5應為客戶4提供服務,則令x44=0,x45=1;

客戶5由min (c53,c54,c55)=min (108,1 004,1 149)=108得設施3應為客戶5提供服務,則令x55=0,x53=1.

經策略2改進后的結果為x15=1,x24=1,x34=1,x45=1,x53=1,y1=0,y2=0,y3=1,y4=1,y5=1,v=1 034.顯然,螞蟻算法的計算結果經策略1和策略2得到了明顯改進.

2.3混合蟻群算法

將基本蟻群算法和兩種局部搜索策略相結合,提出了求解UFL問題的混合蟻群算法.算法具體步驟為:

Step 1初始化螞蟻個數(shù)b、反映信息素重要程度的因子α、反映啟發(fā)函數(shù)重要程度的因子β、信息素衰減因子ρ、常數(shù)q0和Q、最大迭代次數(shù)N和信息素矩陣T=(τij)N×M,令迭代次數(shù)nc=1,螞蟻編號k=1和滿意解的目標函數(shù)值v=+;

Step 2將[1,m]區(qū)間內產生的一個隨機整數(shù)作為螞蟻k為客戶1所選擇的設施,根據(jù)式(6)和式(7)為螞蟻k的其他客戶選擇一個設施;

Step 3若k

Step 4運用兩種局部搜索方法對螞蟻的本次搜索結果進行改進;

Step 5更新當前滿意解及其所對應的目標函數(shù)值v;

Step 6根據(jù)式(8)更新信息素矩陣;

Step 7令Δτij=0(i∈N,j∈M)和nc=nc+1;

Step 8若nc≤N,則轉Step 2;否則,結束搜索,并輸出結果.

3　算例分析

為驗證混合蟻群算法的可行性及其求解性能,采用兩組UFL基準問題庫中的16個算例(每個算例的設施數(shù)等于其客戶數(shù),即m=n)進行求解測試,并對基本蟻群算法和混合蟻群算法的計算結果進行對比分析.

實驗環(huán)境:Intel(R) Core(TM) i7-3770 CPU @ 3.40 GHz,3.41GB內存,操作系統(tǒng)為Windows 7,數(shù)據(jù)處理由Matlab 2010完成.

表2給出了基本蟻群算法和混合蟻群算法中的相關參數(shù).表3給出了所求算例的規(guī)模、文獻[14]所給的(已知)最優(yōu)目標函數(shù)值、基本蟻群算法和混合蟻群算法的計算結果.計算結果包括:迭代200次的運行總時間、找到所輸出的滿意解時的迭代時間(迭代時間)、滿意解的目標函數(shù)值(目標函數(shù)值)、滿意解的目標函數(shù)值與文獻[14]所給的(已知)最優(yōu)目標函數(shù)值之間的差距(Gap).其中,所有時間均以s為單位,Gap的計算公式如下:

表2相關參數(shù)

Tab.2Related parameters

參數(shù)含義混合蟻群算法參數(shù)值基本蟻群算法參數(shù)值螞蟻個數(shù)b20b20信息素重要程度因子a1a1啟發(fā)函數(shù)重要程度因子β5β5衰減系數(shù)ρ0.1ρ0.1常數(shù)1q00.15q00.15最大迭代次數(shù)N200N200常數(shù)2Q100Q100局部搜索選擇螞蟻個數(shù)A30%--局部搜索選擇客戶個數(shù)B50%--

表3計算結果

Tab.3Computational results

算例規(guī)模(已知)最優(yōu)目標函數(shù)值基本蟻群算法運行總時間/s迭代時間/s目標函數(shù)值Gap/%混合蟻群算法運行總時間/s迭代時間/s目標函數(shù)值Gap/%gs00250al250257964141.9154.4638370248.74142.80129.852588750.35gs00250bl250276761142.2444.21572121106.72144.48141.5935157127.03gs00500al500511229537.6090.0377493651.58551.53491.965183571.39gs00500bl500537931538.21113.871167231116.99542.51501.9370951431.90gs00750al7507636711273.92269.43117340353.651295.361108.787820132.40gs00750bl7507970261276.63426.171775518122.771334.501274.51107744635.18ga00250al250257957153.478.5538059847.54168.76159.202579890.01ga00250bl250276339159.8792.84578149109.22167.62134.8235095127.00ga00500al500511422551.22382.7576819750.21571.65362.165207801.83ga00500bl500538060548.96102.071178861119.09578.93526.3273163235.98ga00750al7507635761243.59698.79116299252.311278.581077.407809012.27ga00750bl7507964801245.33386.171780709123.571281.731281.73107635735.14500-100050099169527.73116.3924611682381.79566.88343.201057596.651000-100010002205602273.38432.9351793212248.262327.98990.4927591125.101500-100015003349625720.581746.7078418362241.115837.525581.623599257.452000-1000200043768611497.83179.54106672342337.1911567.029037.724491982.63平均值687.50461299.561739.53 321.56 2365373.50 638.171772.371446.46537948.88 15.14

由表3可知:混合蟻群算法和基本蟻群算法求解16個算例的平均運行總時間分別為1 740 s和1 773 s.雖然混合蟻群算法中加入兩種局部搜索策略,致使其運行總時間略高于基本蟻群算法的運行總時間,但是混合蟻群算法的求解結果明顯優(yōu)于基本蟻群算法的求解結果,混合蟻群算法求解16個算例的平均目標函數(shù)值為537 948,其明顯小于由基本蟻群算法計算得到的平均目標函數(shù)值2 365 374.對于一半以上的算例而言,利用混合蟻群算法求解的Gap值均小于8%,表明利用混合蟻群算法求解的滿意解非常接近于文獻[14]給出的已知最優(yōu)解.然而,這些算例利用基本蟻群算法計算的最小Gap值為47.54%,最大的Gap值竟達2 381.79%.

此外,表3的計算結果表明,相對于基本蟻群算法而言,混合蟻群算法的收斂性能明顯得到改善.如:利用基本蟻群算法和混合蟻群算法求解算例ga00250a1的運行總時間分別為153.47 s和168.76 s,并且混合蟻群算法在迭代時間為159.20 s時求得所輸出的滿意解,但基本蟻群算法在迭代時間為8.55 s時就已求得所輸出的滿意解,剩余144.92 s的搜索迭代對所求得的滿意解沒有任何改進.

4　結論

首先,深入分析了UFL問題的最優(yōu)解所具有的特點,并在此基礎上提出了兩種適用于UFL問題求解的局部搜索策略,然后將這兩種局部搜索策略和基本蟻群算法相結合,設計了求解UFL問題的混合蟻群算法.求解UFL基本問題庫中的16個測試算例的結果表明,這兩種局部搜索策略明顯改進了基本蟻群算法的計算性能和求解結果.

結合模型特點,給出的這兩種求解UFL問題的局部搜索策略,不僅可以與基本蟻群算法相結合,而且可與其他智能優(yōu)化算法相結合構成求解UFL問題的混合智能優(yōu)化算法,這對改進求解UFL問題的智能優(yōu)化算法的求解性能是非常有益的.

[1]堵丁柱,葛可一,胡曉東.近似算法的設計與分析[M].北京:高等教育出版社,2011.

[2]WILLIAMSON D P,HALL L A,HOOGEVEEN J A,et al.Short shop schedules[J].Operations Research,1997,45(2):288-294.[3]LI S.A 1.488 approximation algorithm for the uncapacitated facility location problem [J].Information and Computation,2013,222:45-58.

[5]CAPRARA A,GONZLEZ S.A branch-and-cut algorithm for a generalization of the uncapacitated facility location problem [J].Top,1996,4(1):135-163.

[6]李翼,趙茂先,李岳佳.無容量限制設施選址問題的分支定界法[J].山東理工大學學報(自然科學版),2012,26(1):70-73.

[7]RESENDE M G C,WERNECK R F.A hybrid multistart heuristic for the uncapacitated facility location problem [J].European Journal of Operational Research,2006,174(1):54-68.

[8]王大志,閆楊,汪定偉,等.基于OpenMP求解無容量設施選址問題的并行PSO算法[J].東北大學學報(自然科學版),2008,29(12):1681-1684.[9]KLINCEWICZ J G,LUSS H,ROSENBERG E.Optimal and heuristic algorithms for multiproduct uncapacitated facility location [J].European Journal of Operational Research,1986,26(2):251-258.

[10]CURA T.A parallel local search approach to solving the uncapacitated warehouse location problem [J].Computers & Industrial Engineering,2010,59(4):1000-1009.

[11]王欣盛,馬良.工件排序的改進蟻群算法優(yōu)化[J].上海理工大學學報,2011,33(4):362-366.

[12]李煜,馬良.用量子蟻群算法求解大規(guī)模旅行商問題[J].上海理工大學學報,2012,34(4):355-358.

[13]李俊青,潘全科,王法濤.求解混合流水線調度問題的離散人工蜂群算法[J].運籌與管理,2015,24(1):157-163.[14]BELTRAN-ROYO C,VIAL J P,ALONSO-AYUSO A.Semi-Lagrangian relaxation applied to the uncapacitated facility location problem [J].Computational Optimization and Applications,2012,51(1):387-409.

(編輯:丁紅藝)

Hybrid Ant Colony Algorithm for the Uncapacitated Facility Location Problem

LI Qian1,ZHANG Huizhen1,Cesar Beltran-Royo2

(1.Business School,University of Shanghai for Science and Technology,Shanghai 200093,China;2.Statistics and Operations Research,Rey Juan Carlos University,Madrid,Spain)

Uncapacitated facility location problem (UFL) is a classic NP hard problem,easy to describe but difficult to solve.Combined with two local search strategies,a hybrid ant colony algorithm was proposed for solving the UFL problem.By solving 16 typical instances of UFL problem,the basic ant colony algorithm and the hybrid ant colony algorithm were tested.The numerical results prove the feasibility and effectiveness of the hybrid algorithm for solving the UFL problem.The hybrid algorithm performs better in terms of local optimum and rate of convergence.

uncapacitated facility location problem; ant algorithm; local search

1007-6735(2016)04-0367-06

10.13255/j.cnki.jusst.2016.04.011

2015-11-06

國家自然科學基金資助項目(71401106);高等學校博士學科點專項科研基金聯(lián)合資助課題(20123120120005);上海市教育委員會科研創(chuàng)新項目(14YZ090);上海市高校青年教師培養(yǎng)資助計劃(slg12010)

李倩(1990-),女,碩士研究生.研究方向:智能優(yōu)化.E-mail:liucan_qian@163.com

張惠珍(1979-),女,副教授.研究方向:運籌學、智能優(yōu)化.E-mail:zhzzywz@163.com

TP 183

A