基于最短路多種群遺傳算法的物流園區內部布局研究

孫 焰，馬 馳，鄭文家 （同濟大學 交通運輸工程學院，上海201804）

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

0 引 言

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

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

1 配置布局模型

物流園區內部配置布局的最主要目標是實現各功能模塊之間貨物搬運成本最小和鄰接關聯程度最大。以此建立多目標配置布局模型。

1.1 模型假設

為保證物流園區內部配置布局模型求解的可行性，本文做如下假設：

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

（2） 分割到底。因為在編碼時采用二叉樹分割的方式，地塊分割時會一分到底，故不考慮出現類似如圖1 的情形。分割線相當于園區內的路網，一般路網到底也符合實際情況。（3） 已知以下數據：功能模塊的數目；功能模塊之間的關聯度；功能模塊之間的貨物流動量；單位貨物搬運成本；布局地塊的總面積；各功能模塊的面積。

1.2 模型建立

根據功能模塊間貨物搬運成本最小和鄰接關聯度最大模型的目標要求，構建如下的數學模型：

式中：F1——功能模塊之間搬運的總成本函數；F2——功能模塊之間鄰接關聯度函數；fij——功能模塊i到功能模塊j的貨物流動數；cij——功能模塊i到功能模塊j的單位貨物單位距離搬運成本；dij——功能模塊i到功能模塊j中心的路網最短距離，將在1.3 中詳細介紹；bij——功能模塊i與功能模塊j的鄰近度，將鄰近度值分成六個等級，具體見表1；范圍由來確定，dmax表示最大距離，等于總地塊的長寬之和。

vij——功能模塊i與功能模塊j的關聯度，表示功能模塊之間關系的密切程度，類似系統布局設計的作業單位間關系密切程度，并分成六個等級，具體見表2。

表1 功能模塊間鄰近度

表2 功能模塊間關聯度

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

1.3 最短路引入

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

這兩種距離的算法會影響配置布局的方案，甚至導致配置布局方案的錯誤，與實際不符。如圖2 中所示，模塊2 到模塊6 的距離，不管是用歐式距離還是曼哈頓距離，算得結果即是圖中藍色線所示，而實際距離卻是圖中紅色線表示的；正是藍色線代表的兩種計算方法導致布局圖出現[2,3,5,6 ]累計長條形布局情況。

為了避免長條形布局的出現，張智文等[2]提出采用長寬比范圍作為罰函數的方法。但這存在兩點問題：首先合適的長寬比值的范圍難以確定，其次長寬比值的限定會導致解空間的縮小，甚至達不到最優解。

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

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

遺傳算法是模擬Darwin 進化論和Mendel 遺傳學說的自適應概率性搜索算法。但是單個種群的遺傳算法容易陷入局部收斂和早熟，故選用多種群遺傳算法。同時加入精英策略加速最優解的搜索。

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

2.1 編碼方案

合理合法的染色體編碼是遺傳算法設計的重要環節，本文選用實數編碼和符號編碼結合的編碼方案：實數集合表示m個功能模塊的編號；符號集合中的“+”表示垂直布局，“=”表示水平布局。一個合法的染色體包含m個不同的功能模塊編號和（m- 1 ）個符號。

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

2.2 構造初始解

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

2.3 適應度函數與染色體評估

遺傳算法在運行中基本不利用外部信息，主要以適應度函數（Fitness function） 為依據，充分利用種群中每個個體的適應度值來搜索。因此適應度函數的選取相當重要，影響到對遺傳算法的收斂速度及能否找到最優解。

本文適應度函數由目標函數變換而成。由于物流園區功能模塊配置優化模型中的是多目標函數，因此先將其歸一化后，轉化為單目標函數。轉化后

新的目標函數為：

式中：F——新的目標函數；F1[ ],F2[ ]——對應目標函數的數量級；w——搬運總成本項權重值，權重值可由專家確定；V——功能模塊i與功能模塊j的最大鄰接關聯度，模型中取1。

由于遺傳算法中按照適應度最大篩選染色體，故采用將目標函數進行倒數變換確定適應度函數。即有：

2.4 選擇算子

選擇時，采用精英策略，即當前最大適應度函數的染色體直接入選；其余染色體用輪盤賭進行選擇，即適應度值為fi的染色體i，被選擇的概率為：

2.5 交叉算子

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

隨機所選位置：2

2.6 變異算子

變異算子是對個體染色體的某些基因值作變動。同交叉算子一樣，先將染色體分為編號部分和符號部分，滿足變異概率時，隨機生成變異位置，將符號部分中對應該位置的符號置反，即“+”替換成“=”，將“=”替換成“+”，得到變異后的后代。

3 寧波陸港物流園區的實例驗證

該部分使用前文所述的數學模型和算法原理，以寧波陸港物流園區為例，進行實例驗證。

3.1 園區概況

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

寧波陸港物流園區的園區類型定位：集公鐵運輸、生產服務和商業配送為一體的綜合服務型物流園區。園區層次定位：全國重要的公路貨運主樞紐、浙江省重點交通物流基地、寧波市級物流中心。園區功能定位：城市配送、第三方物流、貨運交易和省際物流、商貿物流、配套商務與商業、配套住宅等六大功能。

3.2 功能模塊劃分

根據物流園區的功能定位，將該物流園區劃分為12 個功能模塊，由市場預測和功能模塊單位處理能力計算得到各功能模塊的占地面積，具體如表3 所示。

3.3 功能模塊關系圖

考慮物流園區的物流、行政、服務、事業等因素，可以判定各個功能模塊之間的關系，繪制出寧波陸港物流園區的功能模塊關系圖，如圖5 所示。

由圖2 功能模塊關系圖和表2 的量化指標，可以得到物流園區功能模塊配置優化模型中的Vij矩陣。如表4 所示。

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

通過對寧波陸港物流園區內部的運作流程分析，結合同等規模物流園區的資料，得到寧波陸港物流園區的功能模塊之間的貨物流量流向表，如表5 所示。

3.5 主要參數確定

種群數目100，種群規模100，迭代代數20。交叉概率選取0.95。變異概率選取0.01。搬運總成本項權重值w本文取0.8，則鄰接關聯度項權重值為0.2。

3.6 遺傳算法求解結果

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

表4 功能模塊之間關聯度量化表

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

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

從圖6 螺旋收斂圖中可以認為目標函數最后達到近似最優解，收斂于1.0280。最終的染色體是：4 2 = 5 6+ 7 = 9 8 3 + = + 12 = + 1 11 + 10 + =。同時，得到對應的功能模塊間貨物搬運成本為1 276.6 萬元/年，鄰接關聯度為89.68。

4 結束語

本文計算了物流園區內部路網最短距離，更貼近實際。在此基礎上，應用分割樹的方法，考慮物流園區內部各功能模塊之間貨物搬運成本最小和鄰接關聯程度最大，建立了物流園區內部功能模塊配置布局模型。采用精英策略，設計了多種群遺傳算法進行求解。應用實例證明，與單種群遺傳算法相比，多種群遺傳算法不會陷入局部最優解，其最終解更接近于物流園區內部布局問題的最優解，更好地兼顧了各功能模塊之間貨物搬運成本最小和鄰接關聯程度最大。

[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] 張智文. 基于遺傳算法的物流園區功能區布局方法研究[D]. 北京：北京交通大學（碩士學位論文），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] 劉訓波，孫小明. 基于二叉樹的遺傳算法求解設施平面布局優化[J]. 數學的實踐與認識，2011,41(21):76-82.

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