孫 焰，馬 馳，鄭文家 （同濟(jì)大學(xué) 交通運(yùn)輸工程學(xué)院，上海201804）

SUN Yan, MA Chi, ZHENG Wen-jia (School of Traffic and Transport Engineering, Tongji University, Shanghai 201804, China)

0 引 言

物流園區(qū)是眾多物流功能的載體，其內(nèi)部功能模塊的合理布局直接影響著物流園區(qū)的有效運(yùn)作和功能發(fā)揮。物流園區(qū)內(nèi)部布局方法源于工廠車間布局設(shè)計(jì)[1]。Richard Muther 提出的系統(tǒng)設(shè)施規(guī)劃布置——SLP（Systematic Layout Planning） 設(shè)計(jì)方法使平面配置布局設(shè)計(jì)從定性階段發(fā)展到了定量階段。Lee R.C、Buffa 等設(shè)施規(guī)劃和設(shè)計(jì)學(xué)者將計(jì)算機(jī)技術(shù)引入到平面布局中，如CRAFT、CORELAP、ALDEP、COFAD、Multi-PLE 等，對(duì)布局問題進(jìn)行優(yōu)化設(shè)計(jì)。之后，圖論法，割樹法等都逐漸應(yīng)用到平面布局中，并用遺傳算法、禁忌搜索等啟發(fā)式算法來求解。

本文在前人研究基礎(chǔ)上，采用分割樹作為中間媒介，將遺傳算法的染色體和配置布局的結(jié)果對(duì)應(yīng)轉(zhuǎn)化，保持染色體的合法性。創(chuàng)新性引入最短路距離，使模型更符合實(shí)際情況，解空間更自由。引入精英策略，加速最優(yōu)解的搜索。選用多種群遺傳算法，避免單個(gè)種群的遺傳算法陷入局部收斂和早熟。

1 配置布局模型

物流園區(qū)內(nèi)部配置布局的最主要目標(biāo)是實(shí)現(xiàn)各功能模塊之間貨物搬運(yùn)成本最小和鄰接關(guān)聯(lián)程度最大。以此建立多目標(biāo)配置布局模型。

1.1 模型假設(shè)

為保證物流園區(qū)內(nèi)部配置布局模型求解的可行性，本文做如下假設(shè)：

（1） 各個(gè)功能模塊和所要布局的地塊形狀均為矩形。

（2） 分割到底。因?yàn)樵诰幋a時(shí)采用二叉樹分割的方式，地塊分割時(shí)會(huì)一分到底，故不考慮出現(xiàn)類似如圖1 的情形。分割線相當(dāng)于園區(qū)內(nèi)的路網(wǎng)，一般路網(wǎng)到底也符合實(shí)際情況。（3） 已知以下數(shù)據(jù)：功能模塊的數(shù)目；功能模塊之間的關(guān)聯(lián)度；功能模塊之間的貨物流動(dòng)量；單位貨物搬運(yùn)成本；布局地塊的總面積；各功能模塊的面積。

1.2 模型建立

根據(jù)功能模塊間貨物搬運(yùn)成本最小和鄰接關(guān)聯(lián)度最大模型的目標(biāo)要求，構(gòu)建如下的數(shù)學(xué)模型：

式中：F1——功能模塊之間搬運(yùn)的總成本函數(shù)；F2——功能模塊之間鄰接關(guān)聯(lián)度函數(shù)；fij——功能模塊i到功能模塊j的貨物流動(dòng)數(shù)；cij——功能模塊i到功能模塊j的單位貨物單位距離搬運(yùn)成本；dij——功能模塊i到功能模塊j中心的路網(wǎng)最短距離，將在1.3 中詳細(xì)介紹；bij——功能模塊i與功能模塊j的鄰近度，將鄰近度值分成六個(gè)等級(jí)，具體見表1；范圍由來確定，dmax表示最大距離，等于總地塊的長(zhǎng)寬之和。

vij——功能模塊i與功能模塊j的關(guān)聯(lián)度，表示功能模塊之間關(guān)系的密切程度，類似系統(tǒng)布局設(shè)計(jì)的作業(yè)單位間關(guān)系密切程度，并分成六個(gè)等級(jí)，具體見表2。

表1 功能模塊間鄰近度

表2 功能模塊間關(guān)聯(lián)度

ak——功能模塊k的面積；A——布局地塊的總面積。

1.3 最短路引入

傳統(tǒng)的計(jì)算模塊i到功能模塊j的距離dij的方法包括歐式距離方法和曼哈頓距離。即：

這兩種距離的算法會(huì)影響配置布局的方案，甚至導(dǎo)致配置布局方案的錯(cuò)誤，與實(shí)際不符。如圖2 中所示，模塊2 到模塊6 的距離，不管是用歐式距離還是曼哈頓距離，算得結(jié)果即是圖中藍(lán)色線所示，而實(shí)際距離卻是圖中紅色線表示的；正是藍(lán)色線代表的兩種計(jì)算方法導(dǎo)致布局圖出現(xiàn)[2,3,5,6 ]累計(jì)長(zhǎng)條形布局情況。

為了避免長(zhǎng)條形布局的出現(xiàn)，張智文等[2]提出采用長(zhǎng)寬比范圍作為罰函數(shù)的方法。但這存在兩點(diǎn)問題：首先合適的長(zhǎng)寬比值的范圍難以確定，其次長(zhǎng)寬比值的限定會(huì)導(dǎo)致解空間的縮小，甚至達(dá)不到最優(yōu)解。

為此，將布局圖中每個(gè)模塊的邊界看作路網(wǎng)，引入最短路距離來計(jì)算模塊i到功能模塊j的距離dij，即圖2 中紅色表示，是完全符合實(shí)際又能避免上述問題的，同時(shí)也保證了解空間的自由性。本文采用Dijkstra 算法來求解模塊之間的最短路。

2 多種群遺傳算法的模型求解

遺傳算法是模擬Darwin 進(jìn)化論和Mendel 遺傳學(xué)說的自適應(yīng)概率性搜索算法。但是單個(gè)種群的遺傳算法容易陷入局部收斂和早熟，故選用多種群遺傳算法。同時(shí)加入精英策略加速最優(yōu)解的搜索。

單個(gè)種群的遺傳算法由隨機(jī)產(chǎn)生的一組初始解開始，通過模擬自然選擇和遺傳過程中的交叉、變異過程，代代進(jìn)化，得到該種群的更優(yōu)解。多種群遺傳算法在此基礎(chǔ)上，將每個(gè)種群的更優(yōu)解帶入到臨近的種群中，作為其初始解的一部分，繼續(xù)交叉變異迭代，最后得到問題的最優(yōu)解，其一般流程示意圖如圖3 所示。

2.1 編碼方案

合理合法的染色體編碼是遺傳算法設(shè)計(jì)的重要環(huán)節(jié)，本文選用實(shí)數(shù)編碼和符號(hào)編碼結(jié)合的編碼方案：實(shí)數(shù)集合表示m個(gè)功能模塊的編號(hào)；符號(hào)集合中的“+”表示垂直布局，“=”表示水平布局。一個(gè)合法的染色體包含m個(gè)不同的功能模塊編號(hào)和（m- 1 ）個(gè)符號(hào)。

應(yīng)用遺傳算法求解實(shí)際問題的關(guān)鍵是如何進(jìn)行編碼空間與解空間的相互轉(zhuǎn)換。本文采用分割樹作為中間媒介，使染色體和配置布局達(dá)到對(duì)應(yīng)互換。染色體轉(zhuǎn)化成分割樹后，從分割樹的根部開始，自上而下分割，得到兩個(gè)分支，先處理右分支，將其布局在離原點(diǎn)（即左下角的頂點(diǎn)） 最近的位置，再處理左分支；接著分別從各分割樹的根部開始，繼續(xù)從上而下分割，直到最后沒有根節(jié)點(diǎn)，最終得到功能模塊的配置方案，舉例見圖4。

2.2 構(gòu)造初始解

用（m+ 1,m+2 ）表示符號(hào)｛+,= ｝，那么在Matlab 中就可用一個(gè)集合變量來表示一條合法的染色體。構(gòu)造染色體時(shí)，按照從左向右的順序依次放置，記模塊編號(hào)個(gè)數(shù)為n，在染色體完成前保證符號(hào)的個(gè)數(shù)小于n-1；同時(shí)要保證模塊編號(hào)的唯一性。

2.3 適應(yīng)度函數(shù)與染色體評(píng)估

遺傳算法在運(yùn)行中基本不利用外部信息，主要以適應(yīng)度函數(shù)（Fitness function） 為依據(jù)，充分利用種群中每個(gè)個(gè)體的適應(yīng)度值來搜索。因此適應(yīng)度函數(shù)的選取相當(dāng)重要，影響到對(duì)遺傳算法的收斂速度及能否找到最優(yōu)解。

本文適應(yīng)度函數(shù)由目標(biāo)函數(shù)變換而成。由于物流園區(qū)功能模塊配置優(yōu)化模型中的是多目標(biāo)函數(shù)，因此先將其歸一化后，轉(zhuǎn)化為單目標(biāo)函數(shù)。轉(zhuǎn)化后

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

式中：F——新的目標(biāo)函數(shù)；F1[ ],F2[ ]——對(duì)應(yīng)目標(biāo)函數(shù)的數(shù)量級(jí)；w——搬運(yùn)總成本項(xiàng)權(quán)重值，權(quán)重值可由專家確定；V——功能模塊i與功能模塊j的最大鄰接關(guān)聯(lián)度，模型中取1。

由于遺傳算法中按照適應(yīng)度最大篩選染色體，故采用將目標(biāo)函數(shù)進(jìn)行倒數(shù)變換確定適應(yīng)度函數(shù)。即有：

2.4 選擇算子

選擇時(shí)，采用精英策略，即當(dāng)前最大適應(yīng)度函數(shù)的染色體直接入選；其余染色體用輪盤賭進(jìn)行選擇，即適應(yīng)度值為fi的染色體i，被選擇的概率為：

2.5 交叉算子

交叉算子使兩個(gè)父代隨機(jī)地交換某些基因，產(chǎn)生新的基因組合，期望將有益基因組合在一起。本文采用位置的雜交，先將染色體分為編號(hào)部分和符號(hào)部分。當(dāng)滿足交叉概率時(shí)，兩個(gè)父代染色體的符號(hào)部分參與交叉：隨機(jī)選取一個(gè)位置，兩個(gè)父代染色體符號(hào)部分從該位置開始交換，最后將新的符號(hào)部分和之前的編號(hào)部分組合，得到新的子代的染色體。舉例說明如下：

隨機(jī)所選位置：2

2.6 變異算子

變異算子是對(duì)個(gè)體染色體的某些基因值作變動(dòng)。同交叉算子一樣，先將染色體分為編號(hào)部分和符號(hào)部分，滿足變異概率時(shí)，隨機(jī)生成變異位置，將符號(hào)部分中對(duì)應(yīng)該位置的符號(hào)置反，即“+”替換成“=”，將“=”替換成“+”，得到變異后的后代。

3 寧波陸港物流園區(qū)的實(shí)例驗(yàn)證

該部分使用前文所述的數(shù)學(xué)模型和算法原理，以寧波陸港物流園區(qū)為例，進(jìn)行實(shí)例驗(yàn)證。

3.1 園區(qū)概況

寧波陸港物流園區(qū)位于寧波三江片北部進(jìn)城門戶，離中心城區(qū)距離適中，極易開展城市及區(qū)域配送；緊鄰寧波城市工業(yè)功能區(qū)、江北高新技術(shù)產(chǎn)業(yè)園，極易開展工業(yè)第三方物流；此外還是鎮(zhèn)海、北侖、舟山連接長(zhǎng)三角上海、杭州、蘇南地區(qū)通道的重要節(jié)點(diǎn)，極易形成區(qū)域性的物流集散中心。研究該物流園區(qū)的功能區(qū)的配置問題對(duì)拓展物流寧波區(qū)位優(yōu)勢(shì)、服務(wù)優(yōu)勢(shì)、戰(zhàn)略優(yōu)勢(shì)都具有舉足輕重的作用。

寧波陸港物流園區(qū)的園區(qū)類型定位：集公鐵運(yùn)輸、生產(chǎn)服務(wù)和商業(yè)配送為一體的綜合服務(wù)型物流園區(qū)。園區(qū)層次定位：全國(guó)重要的公路貨運(yùn)主樞紐、浙江省重點(diǎn)交通物流基地、寧波市級(jí)物流中心。園區(qū)功能定位：城市配送、第三方物流、貨運(yùn)交易和省際物流、商貿(mào)物流、配套商務(wù)與商業(yè)、配套住宅等六大功能。

3.2 功能模塊劃分

根據(jù)物流園區(qū)的功能定位，將該物流園區(qū)劃分為12 個(gè)功能模塊，由市場(chǎng)預(yù)測(cè)和功能模塊單位處理能力計(jì)算得到各功能模塊的占地面積，具體如表3 所示。

3.3 功能模塊關(guān)系圖

考慮物流園區(qū)的物流、行政、服務(wù)、事業(yè)等因素，可以判定各個(gè)功能模塊之間的關(guān)系，繪制出寧波陸港物流園區(qū)的功能模塊關(guān)系圖，如圖5 所示。

由圖2 功能模塊關(guān)系圖和表2 的量化指標(biāo)，可以得到物流園區(qū)功能模塊配置優(yōu)化模型中的Vij矩陣。如表4 所示。

3.4 功能模塊貨物流量流向表

通過對(duì)寧波陸港物流園區(qū)內(nèi)部的運(yùn)作流程分析，結(jié)合同等規(guī)模物流園區(qū)的資料，得到寧波陸港物流園區(qū)的功能模塊之間的貨物流量流向表，如表5 所示。

3.5 主要參數(shù)確定

種群數(shù)目100，種群規(guī)模100，迭代代數(shù)20。交叉概率選取0.95。變異概率選取0.01。搬運(yùn)總成本項(xiàng)權(quán)重值w本文取0.8，則鄰接關(guān)聯(lián)度項(xiàng)權(quán)重值為0.2。

3.6 遺傳算法求解結(jié)果

運(yùn)行該遺傳算法，得到迭代螺旋收斂圖，如圖6 所示。圖中，俯視時(shí)共有100 個(gè)圓，每個(gè)圓代表一個(gè)種群的在迭代20 次過程中的更優(yōu)解的變化，相當(dāng)于一個(gè)單種群的遺傳算法。明顯看出，與單種群遺傳算法相比，多種群遺傳算法不會(huì)陷入局部最優(yōu)解，其最終收斂的解更接近于問題的最優(yōu)解。

表4 功能模塊之間關(guān)聯(lián)度量化表

表5 功能模塊之間貨物流量流向表 單位：噸/年

功能模塊布局圖，如圖7 所示。

從圖6 螺旋收斂圖中可以認(rèn)為目標(biāo)函數(shù)最后達(dá)到近似最優(yōu)解，收斂于1.0280。最終的染色體是：4 2 = 5 6+ 7 = 9 8 3 + = + 12 = + 1 11 + 10 + =。同時(shí)，得到對(duì)應(yīng)的功能模塊間貨物搬運(yùn)成本為1 276.6 萬元/年，鄰接關(guān)聯(lián)度為89.68。

4 結(jié)束語

本文計(jì)算了物流園區(qū)內(nèi)部路網(wǎng)最短距離，更貼近實(shí)際。在此基礎(chǔ)上，應(yīng)用分割樹的方法，考慮物流園區(qū)內(nèi)部各功能模塊之間貨物搬運(yùn)成本最小和鄰接關(guān)聯(lián)程度最大，建立了物流園區(qū)內(nèi)部功能模塊配置布局模型。采用精英策略，設(shè)計(jì)了多種群遺傳算法進(jìn)行求解。應(yīng)用實(shí)例證明，與單種群遺傳算法相比，多種群遺傳算法不會(huì)陷入局部最優(yōu)解，其最終解更接近于物流園區(qū)內(nèi)部布局問題的最優(yōu)解，更好地兼顧了各功能模塊之間貨物搬運(yùn)成本最小和鄰接關(guān)聯(lián)程度最大。

[1] AIELLO G, LA SCALIA G, ENEA M. A multi objective genetic algorithm for the facility layout problem based upon slicing structure encoding[J]. Expert Systems with Applications, 2012,39(12):103-105.

[2] 張智文. 基于遺傳算法的物流園區(qū)功能區(qū)布局方法研究[D]. 北京：北京交通大學(xué)（碩士學(xué)位論文），2007.

[3] MELLER R D, GAU K-Y. The facility layout problem: recent and emerging trends and perspectives[J]. Journal of manufacturing systems, 1996,15(5):351-366.

[4] 劉訓(xùn)波，孫小明. 基于二叉樹的遺傳算法求解設(shè)施平面布局優(yōu)化[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011,41(21):76-82.

[5] 張超群，鄭建國(guó)，錢潔. 遺傳算法編碼方案比較[J]. 計(jì)算機(jī)應(yīng)用研究，2011(3):819-822.