李 眩,吳曉兵,劉 瓊

(銅陵職業(yè)技術(shù)學(xué)院 經(jīng)貿(mào)系，安徽 銅陵 244061)

0 引 言

物流作為一個新興服務(wù)行業(yè)，正在全球范圍內(nèi)迅速發(fā)展，給生產(chǎn)、生活及國際貿(mào)易帶來重大影響.其中，物流配送中心在物流系統(tǒng)中舉足輕重，是物流系統(tǒng)的中心樞紐，連接著貨物供應(yīng)和配送需求2個重要的物流節(jié)點，通過大規(guī)模采購和高效配送方式能有效降低企業(yè)的運營成本，為企業(yè)帶來更大的利潤.物流配送中心選址問題[1]是物流系統(tǒng)的核心問題.物流配送中心在空間上的分布和選址必須合理和科學(xué)，需考慮多種因素對整個物流系統(tǒng)運行效率和效益的影響.因物流配送中心選址問題存在非線性、復(fù)雜度高、約束條件多且相互之間難以協(xié)調(diào)，傳統(tǒng)數(shù)學(xué)模型難以求得全局最優(yōu)解.由于基本蟻群算法[2]有結(jié)構(gòu)簡單、易實現(xiàn)、采用群體并行搜索方式計算求解且求解效率較高的優(yōu)點，本研究應(yīng)用變異和自適應(yīng)的精英策略對基本蟻群算法進行改進，將其應(yīng)用于帶約束條件的物流配送中心選址問題中，并在MATLAB中用仿真實例驗證其合理和可行性.

1 物流配送中心選址問題

物流系統(tǒng)中，物流配送中心的任務(wù)就是根據(jù)客戶需求及時、準(zhǔn)確和經(jīng)濟地配送貨物，決定著物流系統(tǒng)的運作效率.由于物流配送中心在空間上的位置對于物流活動具有十分重要的影響，合理科學(xué)的物流配送中心選址不僅可以大幅降低建設(shè)成本，還可以有效促進物流系統(tǒng)的均衡良性發(fā)展，因此對物流配送中心選址問題的研究具有理論和實際意義.物流配送中心選址問題屬于最小成本問題[3]，既要考慮前期建設(shè)成本，又要考慮后期配送成本及商品流通加工成本，是復(fù)雜度較高且?guī)в卸嗉s束的非線性優(yōu)化問題.對于物流配送中心選址問題的數(shù)據(jù)模型存在如下假設(shè)：1個客戶僅由1個物流配送中心供應(yīng)，物流配送中心的容量能滿足客戶的需求；根據(jù)2個點的坐標(biāo)計算出的直線距離近似看成此2個點間的運輸距離；在允許的配送范圍內(nèi)，配送車輛能在一定的時效范圍內(nèi)將貨物配送給客戶，故配送的時效性約束可以轉(zhuǎn)化為最大允許配送距離來描述；配送的客戶都在一定范圍內(nèi)，即客戶的坐標(biāo)有上限與下限約束.本數(shù)學(xué)模型的設(shè)計思路是，給定1個地址集合，從中選出滿足要求的地址建立物流配送中心，使得選出的地址建立物流配送中心與各需求點組成的配送系統(tǒng)總成本最小.

在區(qū)域范圍內(nèi)擬為n個客戶建立1個物流配送中心，客戶i的坐標(biāo)為(xi,yi)，需求量為ωi，最大允許配送距離為D.確定物流配送中心的坐標(biāo)為(X，Y)，單位貨物運輸成本為p(單位：元/(t·km))，g表示商品在物流配送中心的單位流通加工費用.將配送區(qū)域劃分為m個子區(qū)域，對應(yīng)子區(qū)域內(nèi)物流配送中心的建設(shè)成本為Cj，此時物流配送中心的尋址問題就簡化為在滿足最大允許配送距離的前提下使得總成本f(包括建設(shè)成本、商品在物流配送中心的流通加工總費用及后續(xù)配送成本)最小.

物流配送中心選址問題的數(shù)學(xué)模型描述如下：

目標(biāo)函數(shù)：

(1)

約束條件：

(2)

Ia≤xi≤Ib,Ua≤yi≤Ub

(3)

ωi≥0,D≥0,p≥0,Cj≥0

(4)

上述式中，Ia與Ib為選址問題m個可行解坐標(biāo)xi的下限與上限，即下限Ia=[min(xi)]，上限Ib=[max(xi)]；Ua與Ub為選址問題m個可行解坐標(biāo)yi的下限與上限，即下限Ua=[min(yi)],上限Ub=[max(yi)].式(1)表示后期運營和前期建設(shè)總成本最低，然而實際中僅考慮最低運輸周轉(zhuǎn)量或后期成本最低這個條件是不夠的，因為有些緊急情況下一些貨物的配送有時效性要求，比如搶險救災(zāi)物資、生鮮冷鏈產(chǎn)品、緊急醫(yī)護產(chǎn)品等貨物；式(2)表示每個客戶的配送距離必須在允許范圍之內(nèi)，通過此約束條件將時效性要求轉(zhuǎn)變?yōu)榕渌途嚯x要求，利于后期編程的簡化；式(3)表示配送的客戶點都分布在一定的地理范圍內(nèi)；式(4)表示各參數(shù)在實際應(yīng)用中的非負(fù)要求.式(1)～式(4)共同構(gòu)成滿足時效性要求的物流配送中心選址問題的數(shù)學(xué)模型，表示滿足時效性要求下總成本最小的選址目標(biāo).

對于物流配送中心選址這種復(fù)雜非線性問題的求解，由于傳統(tǒng)數(shù)學(xué)算法求解效率低或很難求得最優(yōu)解，啟發(fā)式智能算法被應(yīng)用來求解該類問題.雖然傳統(tǒng)智能算法有早熟收斂等缺點，在求解物流配送中心選址問題時會出現(xiàn)求解精度不高而導(dǎo)致物流系統(tǒng)配送效率低的情況，但通過適當(dāng)改進和優(yōu)化，算法的效率和全局收斂能力會得到顯著提高.改進后的算法完全可以求解多約束條件且復(fù)雜非線性的諸如物流配送中心選址的實際問題.

考慮到基本蟻群算法具有調(diào)整參數(shù)少、原理較簡單且易實現(xiàn)的優(yōu)點，本研究嘗試應(yīng)用基本蟻群算法來求解物流配送中心選址問題，但發(fā)現(xiàn)基本蟻群算法和其他智能算法一樣易早熟收斂且求解精度不高.為此，本研究引入變異和自適應(yīng)調(diào)整機制的精英策略對基本蟻群算法進行改進，并用于物流配送中心選址問題以提高問題的求解精度.

2 帶變異的自適應(yīng)精英改進蟻群算法

2.1 基本蟻群算法

基本蟻群算法是受自然界蟻群集體覓食行為的啟發(fā)而誕生的仿生智能算法.螞蟻個體行為很簡單，但由個體組成的蟻群卻能完成遠超個體能力的復(fù)雜任務(wù)，個體之間通過信息素來進行信息的傳遞，共同協(xié)作完成復(fù)雜任務(wù).蟻群有能力在沒有任何先行提示情況下找到從巢穴到食物的最短路徑，并能跟隨環(huán)境變化搜索新的路徑，此處體現(xiàn)了一種信息的正反饋現(xiàn)象[4]，即，某路徑上走過的螞蟻越多，此路徑上螞蟻留下的信息素就多，對后面螞蟻的吸引力就越大，就越使其向信息素強度高的方向移動，從而通過此種信息交流達到搜索食物的目的.螞蟻具有的智能行為得益于螞蟻的簡單行為規(guī)則，該規(guī)則讓螞蟻具有多樣性和正反饋能力.在螞蟻覓食時，多樣性使螞蟻不會走進死胡同導(dǎo)致無限循環(huán)，是螞蟻的一種創(chuàng)新能力；正反饋使優(yōu)良信息保存下來，是螞蟻的一種學(xué)習(xí)強化能力.多樣性與正反饋的巧妙結(jié)合使螞蟻具有智能行為.如果多樣性過剩，螞蟻過于活躍，則蟻群會有過多的隨機運動而陷入混沌狀態(tài)；如果多樣性不夠，正反饋過強，將導(dǎo)致蟻群僵化，當(dāng)環(huán)境發(fā)生變化時蟻群不能做相應(yīng)調(diào)整[5].受蟻群覓食尋找最短路徑行為的啟發(fā)，模仿蟻群覓食行為的基本蟻群算法被提出來，其應(yīng)用從最初的旅行商問題擴展到了網(wǎng)絡(luò)路由、車輛調(diào)度、路線航跡規(guī)劃及集成電路布線設(shè)計等領(lǐng)域.基本蟻群算法的出現(xiàn)為解決復(fù)雜困難的系統(tǒng)優(yōu)化問題提供了新的求解思路.

基本蟻群算法的螞蟻個體被表征為優(yōu)化問題的一個潛在可行解，在眾多潛在可行解構(gòu)成的解空間中根據(jù)適應(yīng)度不斷進化迭代，直至算法收斂得到最終的全局最優(yōu)解.基本蟻群算法體現(xiàn)了螞蟻覓食行為中的自催化機制:當(dāng)一個問題的較優(yōu)解附近聚集的螞蟻較多，其留下的信息素也增多，則螞蟻移向該區(qū)域的概率就越大，反過來也增強了該區(qū)域的信息素強度.這種自催化機制利用信息作為反饋，通過對較優(yōu)解或較優(yōu)方案的自增強，使得問題的解向著全局最優(yōu)的方向不斷進化[6].基本蟻群算法中信息素和真實蟻群一樣存在著揮發(fā)，使得螞蟻逐漸淡忘過去而不受歷史經(jīng)驗的過分約束，同時基于概率的前進決策策略使螞蟻向較優(yōu)區(qū)域移動，從而逐步找到問題的最優(yōu)解或最優(yōu)方案[7].

將基本蟻群算法應(yīng)用于優(yōu)化問題的基本思路如下：螞蟻個體表示待優(yōu)化問題的潛在可行解，整個螞蟻群體構(gòu)成待優(yōu)化問題的解空間.在較優(yōu)解上，螞蟻釋放的信息素量較多.隨著時間的推進，較優(yōu)解上累積的信息素濃度逐漸增高，較優(yōu)解位置聚集的螞蟻數(shù)量也愈來愈多.較差解上遺留的信息素濃度會逐漸減少，直至最后被遺忘.信息素的揮發(fā)機制使得螞蟻個體在移動時不會過多局限于以往螞蟻留下的歷史經(jīng)驗，最終，整個蟻群中的螞蟻個體會在正反饋的作用下集中到最優(yōu)解[8]上.

基本蟻群算法求解優(yōu)化問題的實現(xiàn)過程如下：設(shè)置蟻群螞蟻數(shù)Ant、迭代次數(shù)G、信息素?fù)]發(fā)參數(shù)Rho、轉(zhuǎn)移概率閾值Po及算法的搜索范圍.搜索范圍根據(jù)具體問題設(shè)定.螞蟻數(shù)Ant必須根據(jù)問題規(guī)模來設(shè)置，若過小則不能保證群體的多樣性，以致算法性能很差;若過大，盡管可以增加尋優(yōu)的效率、阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長.基本蟻群算法對每只螞蟻位置進行隨機初始化，并依據(jù)問題定義的適應(yīng)度函數(shù)計算每只螞蟻對應(yīng)的適應(yīng)度值Tau(i)，進而求出蟻群當(dāng)前最佳適應(yīng)度值Tau(BestIndex).基本蟻群算法采用以概率為基礎(chǔ)的狀態(tài)轉(zhuǎn)移策略，而螞蟻個體依照以適應(yīng)度值計算得來的狀態(tài)轉(zhuǎn)移概率選擇前進的方向.

每只螞蟻的轉(zhuǎn)移概率如式(5)所示：

P(NC,i)=(Tau(BestIndex)-Tau(i))/

Tau(BestIndex)

(5)

式中，NC表示當(dāng)前的迭代循環(huán)次數(shù);i表示蟻群中第i只螞蟻個體;P(NC,i)表示第NC次循環(huán)中第i只螞蟻的轉(zhuǎn)移概率.當(dāng)螞蟻相對蟻群當(dāng)前最佳位置較遠時，P(NC,i)值將大于轉(zhuǎn)移概率閾值Po，則螞蟻應(yīng)該離開當(dāng)前位置區(qū)域去展開全局探索以避免陷入局部最優(yōu)；當(dāng)螞蟻相對蟻群當(dāng)前最佳位置較近時，P(NC,i)將小于轉(zhuǎn)移概率閾值Po，則螞蟻在當(dāng)前位置鄰域展開局部搜索.每只螞蟻限定在解空間范圍內(nèi)移動，如果超過邊界條件，則為了防止螞蟻逃出解空間，按如下方法處理：X(i,j)>Xjmax時，X(i,j)=Xjmax；X(i,j)

根據(jù)P(NC,i)更新螞蟻個體的位置、適應(yīng)度值及蟻群最優(yōu)的適應(yīng)度值，隨著時間的推移，如果蟻群找到當(dāng)前較優(yōu)解，則用當(dāng)前較優(yōu)解替換以前的解，這樣以前的解將被遺忘.如果當(dāng)前解較差，則以前的解被保留，解的信息量會因螞蟻留下的信息素得到加強，且可行較優(yōu)解的信息素含量按式(6)調(diào)整：

Tau(i)=(1-Rho)*Tau(i)+Macro(i)

(6)

式中，Tau(i)表示蟻群第i只螞蟻找到的解的原有信息素含量;Rho表示信息素的揮發(fā)度；Macro(i)為當(dāng)前循環(huán)中第i只螞蟻找到解對應(yīng)的適應(yīng)度值，如此不斷進化迭代直至找到問題的最優(yōu)解.信息素的應(yīng)用使得基本蟻群算法具有較強的自我學(xué)習(xí)能力，可根據(jù)環(huán)境信息素濃度的變化和過去的行為結(jié)果對環(huán)境進行調(diào)整，從而實現(xiàn)算法求解能力的再進化.

2.2 帶變異的自適應(yīng)精英改進蟻群算法

基本蟻群算法與其他智能算法一樣，解決多維復(fù)雜優(yōu)化問題時易陷入局部最優(yōu).應(yīng)用自適應(yīng)策略改進基本蟻群算法是重要的思路之一.通過自適應(yīng)策略改變算法信息素?fù)]發(fā)度參數(shù)，可以在保證收斂速度的同時提高全局收斂的能力.當(dāng)問題規(guī)模比較大時，由于信息素?fù)]發(fā)參數(shù)的存在，那些從未被搜索到的候選解信息量會減少至接近于0，算法的全局搜索能力降低.另外，當(dāng)信息素?fù)]發(fā)度參數(shù)較小，較優(yōu)解留存的信息量比較大，以前搜索過的解被重新選擇的可能性過大，則算法的全局搜索能力也會被影響.若通過增大信息量揮發(fā)參數(shù)與減少信息量的留存來提高算法的全局搜索能力，則算法的收斂速度將降低[9].因此，算法在陷入局部極值而停滯時，可以自適應(yīng)增大信息素?fù)]發(fā)參數(shù)，降低當(dāng)前局部最優(yōu)解的信息素濃度，極大降低當(dāng)前局部最優(yōu)解被重新搜索到的可能性，使得算法能重新自動搜索其他候選可行解區(qū)域，算法的全局收斂能力得到提高.

信息素?fù)]發(fā)參數(shù)的自適應(yīng)調(diào)整如式(7)所示:

(7)

式中，Rho(t)表示第t代信息素的揮發(fā)參數(shù)；a為自適應(yīng)調(diào)整系數(shù).當(dāng)a取值在1.2至2之間，算法效率[10]較好.在a取值為1.5時，每次循環(huán)后信息素調(diào)整規(guī)則式(6)可改為式(8)：

Tau(i)=(1-Rho(t))*Tau(i)+Macro(i)

(8)

帶精英策略的改進蟻群算法使用了遺傳算法中的精英策略.遺傳算法中，將當(dāng)前代中最適應(yīng)個體的基因進行突變和重組產(chǎn)生下代的個體，以此將當(dāng)前最優(yōu)個體的優(yōu)良基因最大限度遺傳到下代[11].類似地，改進蟻群算法為了使目前所找到的最優(yōu)解在下代循環(huán)中對螞蟻個體更具有吸引力，在每次循環(huán)后給予最優(yōu)解以額外的信息素增量，從而突出該解的優(yōu)良性.精英策略將螞蟻的搜索行為集中到最優(yōu)解附近，提高了解的質(zhì)量和收斂速度，從而改進了算法的性能.按照此策略找到優(yōu)質(zhì)解的螞蟻稱為精英螞蟻.

改進蟻群算法中信息素的更新規(guī)則如式(9)所示：

Tau(i)=(1-Rho(t))*Tau(i)+Macro(i)+Macro(i)/sum

(9)

式中，sum為蟻群所有螞蟻找到的解的適應(yīng)度值之和；Macro(i)/sum為給予優(yōu)質(zhì)解額外的信息素增量.如果第i只螞蟻為非精英螞蟻，找到的解不是蟻群當(dāng)前最優(yōu)解，其信息素仍按式(8)更新.如果第i只螞蟻為精英螞蟻，找到的解為蟻群當(dāng)前最優(yōu)解，解的信息素按式(9)更新.

從上述信息素更新的2種情況來看，精英螞蟻找到的解的信息素含量除按正常方式更新外，另外還按照解的質(zhì)量額外給信息素含量1個增量，提高了該解對螞蟻個體的吸引力.這樣，使得最優(yōu)解和普通解的信息素含量差異進一步增大，將引導(dǎo)螞蟻的搜索行動向最優(yōu)解的領(lǐng)域靠近，增強了對蟻群搜索行為的指導(dǎo)性.

改進蟻群算法的當(dāng)前最優(yōu)解因為所含的信息素在當(dāng)前最高，對螞蟻個體的移動行為有很大的影響，所以當(dāng)算法陷入局部最優(yōu)時，蟻群當(dāng)前最優(yōu)適應(yīng)度值(最優(yōu)函數(shù)值)不再發(fā)生變化.本研究對蟻群當(dāng)前最優(yōu)適應(yīng)度值(問題的當(dāng)前最優(yōu)解)給予了隨機擾動使其產(chǎn)生突變，從而改變蟻群中螞蟻的移動行為，增強了算法全局尋優(yōu)能力，也避免了算法過早收斂.

改進蟻群算法實現(xiàn)變異操作的描述如下：

Tau_Best(NC)=Tau_Best(NC)+(rand(1)+100)

(10)

式中，Tau_Best(NC)為第NC代蟻群找到的當(dāng)前最優(yōu)解(即蟻群當(dāng)前最優(yōu)適應(yīng)度值)；rand(1)為0到1的隨機數(shù).

只有算法陷入局部最優(yōu)停頓時，蟻群當(dāng)前最優(yōu)適應(yīng)度值才發(fā)生變異，因此如何判斷算法陷入局部最優(yōu)顯得尤為重要.算法停頓時，表現(xiàn)為蟻群當(dāng)前最佳適應(yīng)度值與前幾次最佳適應(yīng)度值相等，以此來構(gòu)造判斷條件，如式(11)所示：

NC>n&&NC<300&&Tau_Best(NC)==

Tau_Best(NC-n)

(11)

式中，NC表示當(dāng)前迭代次數(shù);n表示參照當(dāng)前的循環(huán)迭代次數(shù).本研究中n取值為5，即發(fā)生5次循環(huán)迭代，此時算法求得的蟻群當(dāng)前最優(yōu)適應(yīng)度值沒有明顯改進，即認(rèn)定算法處于停頓.

3 物流配送中心選址問題求解

為了驗證帶變異的自適應(yīng)精英改進蟻群算法應(yīng)用于求解實際中比較復(fù)雜且多約束問題的有效性，本研究以物流配送中心選址問題為例，采集8位客戶的位置坐標(biāo).各客戶位置坐標(biāo)及其后續(xù)物資需求量如表1所示.

表1 客戶位置坐標(biāo)與物資需求量

若在位置坐標(biāo)(x,y)滿足x[0,800]且y[0,800]的范圍內(nèi)建設(shè)物流配送中心，則前期建設(shè)成本、商品流通加工成本及后期配送總成本將最小.為了滿足物流配送的時效性要求，約定配送中心到客戶間的配送距離不得大于500 km，配送價格設(shè)定為10元/(t·km).商品在配送中心的單位流通加工成本為150元/t.在不同的子區(qū)域內(nèi)，建設(shè)成本會不一樣.若位置坐標(biāo)(x,y)在x[20,400]且y[20,400]范圍內(nèi)，建設(shè)成本為500萬元；若位置坐標(biāo)(x,y)在x(400,800]且y(400,800]范圍內(nèi)，建設(shè)成本為650萬元；若位置坐標(biāo)(x,y)在x[20,400]且y(400,800]范圍內(nèi)，建設(shè)成本為480萬元；位置坐標(biāo)(x,y)在x(400,800]且y(20,400]范圍內(nèi)，建設(shè)成本為370萬元.本研究根據(jù)給定的約束條件應(yīng)用提出的改進蟻群算法優(yōu)化模型確定物流配送中心的最優(yōu)位置坐標(biāo)，使其總運作成本最少.

本研究提出的改進蟻群算法與基本粒子群算法(慣性權(quán)重與加速因子均為常數(shù))、基本蟻群算法(揮發(fā)參數(shù)為常數(shù)、無變異且信息素按正常無差異更新)的求解結(jié)果進行比較，得出適應(yīng)度函數(shù)值變化和物流配送中心最優(yōu)選址結(jié)果如圖1～圖4所示.

圖1 基本粒子群算法適應(yīng)度函數(shù)值變化曲線圖

圖2 基本蟻群算法適應(yīng)度函數(shù)值變化曲線圖

圖3 改進蟻群算法適應(yīng)度函數(shù)值變化曲線圖

圖4 物流配送中心最優(yōu)選址結(jié)果

基本粒子群算法求解的最佳坐標(biāo)為(283.715 1,599.999 9),運行時間為0.843 s.基本蟻群算法求解的最佳坐標(biāo)為(523.477 8,577.896 6),運行時間為1.733 s.本研究提出的改進蟻群算法(即帶變異的自適應(yīng)精英改進蟻群算法)用于求解物流配送中心選址問題時收斂較快，求得最優(yōu)解的運行時間為1.344 s，最佳坐標(biāo)為(541.693 6，598.218 2)，建設(shè)成本、后期配送成本及流通成本等最少總成本為415 298萬元.基本粒子群算法收斂速度雖然很快,但不能收斂于全局最優(yōu)解.從適應(yīng)度函數(shù)值變化看，基本蟻群算法收斂速度極慢，收斂時間也最長，而且不能收斂于全局最優(yōu)解.綜上所述，用帶變異的自適應(yīng)精英策略改進蟻群算法非常成功地求解了物流配送中心選址問題.本研究通過此改進蟻群算法求解的最優(yōu)物流配送中心選址方案能滿足每位客戶的時效性和配送容量要求，而且顯著地將總成本降低到最少.由此可知，采用帶變異的自適應(yīng)精英策略改進蟻群算法解決物流配送中心選址問題取得了較好的結(jié)果，在實際中具有十分積極的意義.

4 結(jié) 語

本研究通過物流配送中心選址問題數(shù)學(xué)模型的應(yīng)用，驗證了選址數(shù)學(xué)模型的正確性和帶變異的自適應(yīng)精英改進蟻群算法的合理性.改進蟻群算法解決了復(fù)雜優(yōu)化問題的有效性，改善了基本蟻群算法易陷入局部最優(yōu)且魯棒性差的缺點，在物流配送中心選址問題的求解中體現(xiàn)了較好的動態(tài)觀測性和收斂性，是一種解決優(yōu)化問題及進行優(yōu)化決策的好算法，具有較好的應(yīng)用前景.