基于混合算法的物流園區(qū)布局優(yōu)化研究

許 程

（西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031）

XU Cheng

(School of Transportation and Logistics,Southwest Jiaotong University,Chengdu 610031,China)

0 引言

現(xiàn)代物流園區(qū)不僅包含傳統(tǒng)意義上的倉儲(chǔ)、運(yùn)輸、包裝、裝卸搬運(yùn)、配送、流通加工等功能外，還具有與之配套的信息、咨詢、綜合服務(wù)、物流金融等功能。園區(qū)為完成這些功能形成的不同功能區(qū)，為了實(shí)現(xiàn)物流園區(qū)的整體功能，離不開園區(qū)內(nèi)各功能區(qū)間的合理布局。合理的物流園區(qū)布局對于減少占地面積，降低園區(qū)建設(shè)和運(yùn)營成本，提高物流園區(qū)內(nèi)的作業(yè)效率，為園區(qū)企業(yè)提供滿意的服務(wù)，最終獲得更好的經(jīng)濟(jì)效益具有相當(dāng)重要的作用。

目前，我國正在建設(shè)或者計(jì)劃建設(shè)物流園區(qū)的城市很多，但在物流園區(qū)建設(shè)過程中，發(fā)現(xiàn)了一些問題如缺乏準(zhǔn)確的定位、不夠規(guī)范的功能區(qū)布局、園區(qū)的建設(shè)規(guī)模一味的貪大求全等。根據(jù)調(diào)研發(fā)現(xiàn)，一方面，大量的資金投入用于建設(shè)物流園區(qū)或物流中心；而另一方面，大量的物流園區(qū)處于空閑狀態(tài)，資源閑置，沒有產(chǎn)生實(shí)際作用。因此在園區(qū)規(guī)劃設(shè)計(jì)的前期工作中，就要對功能區(qū)進(jìn)行合理布置，節(jié)約土地面積。

系統(tǒng)布置設(shè)計(jì)（SLP）法是由美國學(xué)者M(jìn)uther 于1961年提出來的，是一種基本的程序模式，廣泛應(yīng)用于物流園區(qū)功能區(qū)布局規(guī)劃問題中。該方法條理清晰，以物料搬運(yùn)費(fèi)用最小為目標(biāo)，將功能區(qū)間的物流分析（定量分析）與非物流關(guān)系（定性分析）相結(jié)合，求得合理的布局方案。但通常情況物流園區(qū)功能區(qū)的數(shù)量比較多，解的數(shù)目將呈指數(shù)倍擴(kuò)大，用上面思想的算法將難以對可能解進(jìn)行比較，所求的解往往與最優(yōu)解有較大差距，所以本文將嘗試構(gòu)造混合算法對問題進(jìn)行求解。

1 物流園區(qū)內(nèi)部布局優(yōu)化模型

1.1 問題假設(shè)

鑒于研究上的局限性，根據(jù)以往設(shè)施布置問題的相關(guān)文獻(xiàn)所提供的方式，本文對物流園區(qū)功能布局模型作如下假設(shè)：

（1）假設(shè)進(jìn)行布局規(guī)劃的物流園區(qū)的范圍是已知的，且形狀為矩形；

（2）將場內(nèi)道路所占面積按比例分?jǐn)偟狡渌δ軈^(qū)，則模型中就不再考慮道路對布局的影響；

（3）各功能區(qū)的進(jìn)、出口都設(shè)置在各個(gè)功能區(qū)的中心；

（4）假設(shè)進(jìn)行布局規(guī)劃的物流園區(qū)出入口的個(gè)數(shù)和位置確定。

另外，根據(jù)模型需求，還必須已知以下一些數(shù)據(jù)：

（1）功能區(qū)數(shù)目及面積；

（2）各功能區(qū)間的物流量及非物流關(guān)系關(guān)聯(lián)度；

（3）功能區(qū)和園區(qū)出入口間的物流量及非物流關(guān)聯(lián)度；

（4）各功能區(qū)長寬比例的上下限；

（5）園區(qū)出入口的位置；

（6）征地面積及其長寬。

1.2 數(shù)學(xué)模型

盡可能提高物流園區(qū)的效率，減少物流園區(qū)的運(yùn)營成本，使園區(qū)內(nèi)的職工在更為便利、舒適、安全和環(huán)保的環(huán)境下工作是物流園區(qū)布局優(yōu)化的主要目標(biāo)。同時(shí)合理緊湊的布局，提高土地利用率，減少征地面積，能有效節(jié)約物流園區(qū)的成本。上述目標(biāo)可拆為以下幾個(gè)子目標(biāo)。

（1）物料搬運(yùn)費(fèi)用最小化

主要考慮貨物在物流園區(qū)內(nèi)部流動(dòng)時(shí)產(chǎn)生的搬運(yùn)費(fèi)用。由于物流園區(qū)與外部環(huán)境有著復(fù)雜的聯(lián)系，出入口的位置設(shè)置對園區(qū)功能區(qū)的布局有一定程度上的影響，所以計(jì)算物流搬運(yùn)費(fèi)用時(shí)，不僅要考慮貨物在各功能區(qū)塊之間的流動(dòng)，還需考慮貨物進(jìn)出物流園區(qū)時(shí)在進(jìn)出口與各功能區(qū)之間的流動(dòng)。

（2）鄰接關(guān)聯(lián)度最大化

該目標(biāo)函數(shù)主要考慮物流園區(qū)中的非物流關(guān)系。非物流關(guān)系主要從程序關(guān)系、組織關(guān)系以及環(huán)境安全三方面衡量，主要包括：設(shè)施設(shè)備的共用，方便監(jiān)督和管理，人員工作聯(lián)系頻繁程度，保障人員工作和生活安全等。為提供便利的工作環(huán)境，布局時(shí)需要使關(guān)系密切程度緊密的功能區(qū)在位置上盡可能相鄰。為了便于計(jì)算，引入關(guān)聯(lián)度和鄰接度兩個(gè)概念，分別表示功能區(qū)間的非物流關(guān)系的密切程度及功能區(qū)間的距離鄰近度，具體數(shù)值如表1 所示。

表1 園區(qū)功能區(qū)間非物流關(guān)系值與功能區(qū)距離鄰近度表

（3）土地利用率最大化

由于物流園區(qū)具有占地面積大的特點(diǎn)，需要較大的土地面積，而土地成本往往很高，因此在園區(qū)建設(shè)前進(jìn)行有效的規(guī)劃，作出合理緊湊的布局，能夠節(jié)約土地資源，降低園區(qū)的成本。

多目標(biāo)表達(dá)式：

其中：F1表示功能區(qū)間及功能區(qū)與出入口之間的物料搬運(yùn)費(fèi)用；F2表示功能區(qū)間及功能區(qū)與出入口之間的鄰接關(guān)聯(lián)度函數(shù)；F3表示土地利用率；N 為功能區(qū)數(shù)目，i,j=1,2,…,N,且i≠j；cij為功能區(qū)i 與功能區(qū)j 間的單位搬運(yùn)成本，cik為功能區(qū)i 與出入口k 間的單位搬運(yùn)成本；fij為功能區(qū)i 與功能區(qū)j 間的物流量，fik為功能區(qū)i 與出入口k 間的物流量；（xi,yi）表示功能區(qū)i的中心坐標(biāo)；表示功能區(qū)i 與功能區(qū)j 間的矩形距離，表示功能區(qū)i 與出入口k 間的矩形距離；vij和bij分別表示功能區(qū)i 與功能區(qū)j 的關(guān)聯(lián)度和鄰接度，vik和bik分別表示功能區(qū)i 與出入口k 的關(guān)聯(lián)度和鄰接度；si為功能區(qū)i的面積；）為某一布局方案下布局結(jié)果所占土地面積；λi表示功能區(qū)i 的長寬比；lxi為功能區(qū)i 在x軸方向上的長度，lyi功能區(qū)i 在y 軸方向上的長度；L 表示所征土地的長度，B 為所征土地的寬度。約束（1）表示各功能區(qū)的長寬比要求；約束（2）和（3）表示各功能區(qū)的布置不能重疊；約束（4）和（5）為邊界約束，保證各功能區(qū)布局在設(shè)定區(qū)域內(nèi)。

2 算法設(shè)計(jì)

本文利用遺傳算法的可擴(kuò)展性這一優(yōu)點(diǎn)，在遺傳算法實(shí)現(xiàn)過程中加入爬山算法，實(shí)現(xiàn)對遺傳算法的改進(jìn)，加強(qiáng)其局部搜索能力，形成求解物流園區(qū)功能區(qū)布局模型的混合算法。該混合遺傳算法的基本思想是：在遺傳算法選擇、交叉和變異操作前，利用爬山算子在其鄰域進(jìn)行搜索，找到一個(gè)相對滿意的長寬比，再利用遺傳算法的選擇、交叉和變異操作，進(jìn)行全局搜索，得到全局最優(yōu)的搜索結(jié)果。

2.1 編碼機(jī)制

本文采用浮點(diǎn)數(shù)編碼方式作為染色體的編碼機(jī)制。染色體直接用功能區(qū)序號(hào)和長寬比表示，一條完整的染色體有兩行，第一行是功能區(qū)序列，第二行是功能區(qū)序列對應(yīng)的長寬比序列。例如：對于8 個(gè)功能區(qū)的物流園區(qū)，染色體A是一條合法的染色體。

2.2 初始化

本文采用隨機(jī)方法產(chǎn)生popsize 個(gè)染色體。初始化就是產(chǎn)生初始種群，初始種群里面的每一個(gè)個(gè)體有兩行，第一行是功能區(qū)序列，第二行是功能區(qū)序列對應(yīng)的長寬比序列。功能區(qū)序列就是用函數(shù)[unused_data,inde x ]=sort（randi（n,1,n））實(shí)現(xiàn)，index就是功能區(qū)序列，即n 個(gè)1 到n 間的互不重復(fù)的自然數(shù)序列。函數(shù)randi（max_min（i）,l,l）產(chǎn)生功能區(qū)i 對應(yīng)的長寬比，其中max_min（i）表示功能區(qū)i 的長寬比上限和下限。

2.3 適應(yīng)度函數(shù)

本文物流園區(qū)功能區(qū)布局模型為多目標(biāo)函數(shù)，采用權(quán)重系數(shù)法轉(zhuǎn)化為單目標(biāo)求解。目標(biāo)函數(shù)分別是物流搬運(yùn)費(fèi)用最小化，鄰接關(guān)聯(lián)度最大化和土地利用率最大化，優(yōu)化方向不同且具有不同的量綱，故對物料搬運(yùn)費(fèi)用最小化目標(biāo)函數(shù)進(jìn)行倒數(shù)處理，使其優(yōu)化方向相同，同時(shí)每個(gè)目標(biāo)乘以系數(shù)，使其具有相同的數(shù)量級。因此，有適應(yīng)度函數(shù)Fitness=c1/F1+c2F2+c3F3，其中c1,c2,c3為系數(shù)。

2.4 爬山算子

由于初始化時(shí)長寬比是長寬比上下限區(qū)間內(nèi)隨機(jī)產(chǎn)生的，后面的交叉、變異過程都沒有改變長寬比，即長寬比隨機(jī)產(chǎn)生后將不再改變，最后的目標(biāo)值顯然不會(huì)是最優(yōu)的。因此，為了搜索到最優(yōu)的長寬比組合，本文在交叉、變異前加入爬山算子是對每個(gè)功能區(qū)的長寬比進(jìn)行鄰域搜索，以使得目標(biāo)值更優(yōu)。

2.5 選擇算子

選擇算子采用排序選擇，即對通過爬山算子輸出的個(gè)體進(jìn)行適應(yīng)度值排序，并選擇適應(yīng)度值排在前popsize 個(gè)個(gè)體作為最優(yōu)個(gè)體。

2.6 交叉與變異

對選到個(gè)體采用隨機(jī)方式進(jìn)行兩兩配對，對配對的個(gè)體組進(jìn)行交叉操作。本文采用多點(diǎn)交叉方式，假設(shè)雙親為P1 和P2，交叉時(shí)從P1 中隨機(jī)地將一半數(shù)量的基因遺傳給子代1 等位置的基因座上，按照父輩2 的順序?qū)⒆哟? 缺少的另一半基因值依次賦給空基因座，用同樣的方法產(chǎn)生子代2。

本文對染色體的功能區(qū)序列基因進(jìn)行變異操作，即在功能區(qū)序列任選兩個(gè)基因進(jìn)行交換，以此獲得變異的后代。

3 實(shí)例計(jì)算與結(jié)果分析

某物流園區(qū)規(guī)劃用地形狀可近似為矩形，有以下功能區(qū)：倉儲(chǔ)區(qū)、中轉(zhuǎn)區(qū)、配送區(qū)、流通加工區(qū)、辦公事務(wù)區(qū)、展示交易區(qū)、綜合服務(wù)區(qū)以及停車場區(qū)。

作者通過MATLAB 編制了物流園區(qū)布局優(yōu)化問題的混合算法計(jì)算機(jī)程序，通過運(yùn)算求得，適應(yīng)度函數(shù)收斂與一個(gè)最大值，可認(rèn)為達(dá)到了最優(yōu)解。此時(shí)對應(yīng)的染色體為功能區(qū)布局示意圖如圖1 所示。

圖1 混合算法布局示意圖

將混合算法的優(yōu)化布局方案與原布局方案從物料搬運(yùn)費(fèi)用、鄰接關(guān)聯(lián)度以及土地利用率等方面進(jìn)行比較，結(jié)果如表2所示。

由表2 可知，在物料搬運(yùn)費(fèi)用方面，混合算法下的布局方案成本為4 610 單位費(fèi)用，而原布局方案是5 279 單位費(fèi)用。在關(guān)聯(lián)度方面，原方案功能區(qū)間關(guān)聯(lián)度為20.8 個(gè)單位，混合算法下的方案功能區(qū)間的關(guān)聯(lián)度總和為29.5 個(gè)單位，方案更優(yōu)。在土地利用率方面，混合算法下的方案較好地提高了土地的利用率。

表2 某園區(qū)布局方案對比

4 結(jié)論

本文在建立物流園區(qū)功能區(qū)布局優(yōu)化問題的數(shù)學(xué)模型基礎(chǔ)上，針對遺傳算法因局部搜索能力不強(qiáng)導(dǎo)致尋優(yōu)效果較差的弱點(diǎn)，將局部搜索能力較強(qiáng)的爬山算法與之結(jié)合，從而構(gòu)造混合算法求解該問題。根據(jù)實(shí)驗(yàn)結(jié)果可直觀地作出評價(jià)，加入遺傳算法的功能區(qū)布局方法在降低物流搬運(yùn)費(fèi)用，增加功能區(qū)之間的關(guān)聯(lián)度以及土地利用率方面均有較大優(yōu)勢，具有一定的可行性和先進(jìn)性。

[1]Raja GKasilingam.Logistics and Transportation Design and Planning[M].Kluwer Academic Publishers,USA,1998.

[2]Jay deep Bal Krishnan,etc.A hybrid genetic algorithm for the dynamicplant layout problem[J].International Journal of Production Economics,2003,86(2):107-120.

[3]KL Mar,YS Wong,FTS Chan.Genetic algorithm for facilities layout problems[J].Compvter Integrate,1998,11(15):113-127.

[4]郎茂祥，胡思繼.用混合遺傳算法求解物流配送路徑優(yōu)化問題的研究[J].中國管理科學(xué)，2002,10(5):51-55.

[5]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，1999.

[6]M.Adel EI-Baz.A genetic algorithm for facility layout Problems of different manufacturing environments[J].Computers &Industrial Engineering,2004(2):233-246.

[7]汪一筇，米智偉.SLP 和遺傳算法結(jié)合在車間設(shè)備布局中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2010,46(5):211-213.