基于改進(jìn)遺傳算法的鐵路物流中心功能區(qū)布局優(yōu)化研究

張 恒

(中國鐵路武漢局集團(tuán)有限公司 計劃統(tǒng)計部，湖北 武漢 410073)

0 引言

近年來，隨著貨運需求的增加及市場競爭的加劇，鐵路物流基地和貨運場站作為鐵路貨運中心樞紐，是貨運至關(guān)重要的環(huán)節(jié)，其規(guī)劃和設(shè)計將影響整個鐵路貨運效率。針對鐵路物流中心規(guī)劃設(shè)計進(jìn)行研究，對我國鐵路貨運適應(yīng)現(xiàn)代物流的競爭環(huán)境并取得主導(dǎo)地位現(xiàn)實意義重大。由于貨物品類不同，且鐵路物流中心各功能區(qū)之間的貨運量存在差異，功能區(qū)之間的相關(guān)性各有不同。另外，加上物流中心的客觀限制條件，使得鐵路物流中心功能區(qū)布局優(yōu)化成為一個NP 難問題。

目前我國關(guān)于物流中心的研究多集中于物流中心運營模式理論[1]、單一物流中心選址[2]及傳統(tǒng)貨運站向現(xiàn)代物流中心轉(zhuǎn)化的定性分析[3-4]等方面。求解鐵路物流中心功能區(qū)布局問題的方法主要有數(shù)學(xué)模型法[5-6]、系統(tǒng)布置規(guī)劃法(Systematic Layout Planning，SLP)[7]及計算機(jī)仿真等。近年來，從定性和定量2方面考慮的SLP 方法應(yīng)用較多，采用的算法主要有啟發(fā)式算法、智能算法、計算機(jī)仿真方法等，其中智能算法被廣泛采用，包括遺傳算法、模擬退火算法、蟻群算法等。針對鐵路物流中心功能區(qū)布局優(yōu)化模型，馮芬玲等[7]設(shè)計遺傳算法進(jìn)行求解，通過對中心點位置和擺放方式進(jìn)行編碼，將約束條件作為懲罰加入適應(yīng)度函數(shù)；由于各功能區(qū)域相互位置的約束，造成該種方法無法保證解的可行性，容易產(chǎn)生不可行解；同時搜索空間過大，不易搜索到優(yōu)解。谷樂陽[8]采用嚴(yán)格分層布局的方式進(jìn)行求解，保證解的可行性，然而這種方法大大縮小了解的搜索空間，存在忽略相對優(yōu)解的情況。

通過對鐵路物流中心功能區(qū)布局優(yōu)化模型求解算法研究，提出一種高效遺傳算法。采用改進(jìn)分層思想，通過從左到右、從下往上的緊密堆積布局方式，同時對各功能區(qū)域豎直采用連續(xù)上下位移選擇，優(yōu)化物流區(qū)域布局。對編碼方式進(jìn)行改進(jìn)，針對功能區(qū)域布局順序、堆積方式和擺放方式，分別采用自然整數(shù)編碼、離散二進(jìn)制編碼和連續(xù)區(qū)間的二進(jìn)制編碼方式進(jìn)行編碼，并進(jìn)行遺傳操作，搜索區(qū)域布局優(yōu)化解。通過算例比較，體現(xiàn)了改進(jìn)遺傳算法的優(yōu)越性。算法在保證解可行的前提下，擴(kuò)大了搜索范圍，提高解質(zhì)量，從而能夠獲得更優(yōu)的鐵路物流中心功能區(qū)布局方案，為鐵路物流中心功能區(qū)布局提供技術(shù)支撐。

1 鐵路物流中心功能區(qū)布局優(yōu)化模型

鐵路物流中心主要通過鐵路聯(lián)絡(luò)線以鐵路運輸方式進(jìn)行物流活動，包括貨物承運、配送、儲存、運輸和交付等，按其作業(yè)流程及各項作業(yè)特點劃分為基本功能、增長功能和輔助功能3 大類12 個功能區(qū)?；竟δ軈^(qū)包括：理貨區(qū)、流通加工區(qū)、倉儲區(qū)。增長功能區(qū)包括：交易展示區(qū)、卡車停車場和辦公服務(wù)區(qū)。輔助功能區(qū)包括：后勤保障區(qū)、生活服務(wù)區(qū)、綠化區(qū)，以及物流中心儲備用地和道路規(guī)劃用地等功能區(qū)。

一般將物流區(qū)域假設(shè)成平面圖，物流中心規(guī)劃區(qū)域和功能區(qū)域形狀為矩形。功能區(qū)域的集合為N，且n=[N]為功能區(qū)域的數(shù)量。假設(shè)功能區(qū)域的邊分別與物流中心規(guī)劃區(qū)域坐標(biāo)圖的X 軸和Y 軸平行，且每個功能區(qū)域在進(jìn)行布局時有橫倒和豎立2 種放置方式，對于功能區(qū)i，si=1 表示橫倒，si=0 表示豎立。功能區(qū)域放置方式的向量形式為S=(si)n×1，設(shè)功能區(qū)域i的中心位置坐標(biāo)di為(xi，yi)，功能區(qū)域的中心位置坐標(biāo)向量表示為d=(di)n×1，則以(d，S)為決策變量的鐵路物流中心功能區(qū)布局優(yōu)化模型如下。

式中：Z為總成本，元；F為fij的向量，F(xiàn)=(fij)n×n，其中，fij為功能區(qū)域i與區(qū)域j日均物流量，t；cij為單位物流量單位距離的成本，元/ t·m；dij為曼哈頓距離，即dij=|xi-xj|+|yi-yj|，m；hi和hj分別為功能區(qū)i和區(qū)域j的水平邊長度，m；wi和wj分別為功能區(qū)域i和區(qū)域j的垂直邊長度，m；pij為功能區(qū)邊界之間的最小間距，m；H和W分別為物流中心規(guī)劃區(qū)域水平邊和垂直邊的長度，m。

對于一般物流區(qū)域布局優(yōu)化包括2 個約束條件。①不重疊約束。兩相鄰功能區(qū)域不得相互重疊，如公式⑵—公式⑶。②功能區(qū)邊界約束。各功能區(qū)的邊界不得超出物流中心規(guī)劃區(qū)域，如公式⑷—公式⑸。需要注意的是，針對具體的物流區(qū)域布局問題，還需增加相應(yīng)的約束，比如鐵路物流中心功能區(qū)布局中存在鐵路裝卸線功能區(qū)固定約束、物流中心出入口約束等。鐵路物流中心功能區(qū)布局優(yōu)化模型為非線性混合整數(shù)規(guī)劃模型，難以用凸規(guī)劃算法直接求解，屬于NP 難問題，適宜采用遺傳算法進(jìn)行求解。

2 改進(jìn)遺傳算法設(shè)計

2.1 分層布局方式改進(jìn)

遺傳算法的編碼方式對遺傳操作方式及適應(yīng)度函數(shù)均有直接影響，同時也影響算法對于解的搜索能力，包括算法整體計算量和搜索解的質(zhì)量。對于鐵路物流中心功能區(qū)布局優(yōu)化模型，決策變量為(d，S)，即各功能區(qū)域的坐標(biāo)和放置方式。其中功能區(qū)域放置方式可以采用二進(jìn)制編碼表示。而對于各功能區(qū)域坐標(biāo)，如果直接對其進(jìn)行編碼，雖然搜索范圍包含了所有解空間，但存在2 個缺點：一是基于一定的精度，對實數(shù)區(qū)間進(jìn)行編碼，編碼長度較長，且隨著精度提高，編碼長度也相應(yīng)增加；二是由于直接對坐標(biāo)編碼，編碼并沒有考慮約束條件，則大部分解的編碼無效或不正確，且進(jìn)行遺傳操作時，獲得的解也會包含大量無效解。

設(shè)計采用分層思想解決上述問題，分層布局方式主要是針對功能區(qū)的整體布局。將規(guī)劃區(qū)域進(jìn)行分層，并采用從左到右、從下往上的緊密排列方式對功能區(qū)域進(jìn)行布局，利用自然整數(shù)編碼對功能區(qū)域布局順序進(jìn)行編碼，即定義一個功能區(qū)域與布局順序一一對應(yīng)的函數(shù)o :N→{1，2，3，…，|N|}。分層思想示意圖如圖1 所示，對7 個功能區(qū)域，按照順序從左到右、從下往上分層排列，同時同層緊密排列。由于第1 層容不下功能區(qū)域5，所以功能區(qū)域5 只能布局在第2 層。采取這種方式布局后記錄各功能區(qū)域坐標(biāo)，獲得該編碼下的布局解。按照這種方式編碼后，每一組編碼均會獲得一個解，且通過這種方式獲得的解的可行度大大增加。

圖1 分層思想示意圖Fig.1 Hierarchical thinking

盡管圖1 所示分層布局方式提高了解的質(zhì)量，同時也大大削弱了解的搜索能力和搜索范圍。為了同時提高算法搜索解的效率和質(zhì)量，采用改進(jìn)的分層思想，按照從左到右、從下往上的緊密堆積方式進(jìn)行布局，并采用三進(jìn)制對堆積方式進(jìn)行編碼。改進(jìn)分層思想示意圖如圖2 所示。圖2 中，3 個子圖分別表示功能區(qū)域7 的3 種堆積方式。

在圖2 的布局方式中，第1 層包括功能區(qū)域1～ 4，第2 層包括功能區(qū)域5～ 7。對于功能區(qū)域7，方式1 是將功能區(qū)域7 布局在該區(qū)域X 軸范圍內(nèi)所能放置的最下面；方式2 是將功能區(qū)域7 布局在該區(qū)域X 軸范圍內(nèi)最高的水平高度，與該區(qū)域X 軸范圍之外的左邊緊挨的第1 個區(qū)域水平高度上進(jìn)行堆積，即在區(qū)域4 的水平高度上堆積；方式3 是將功能區(qū)域7 布局在第1 層所有功能區(qū)域中最高的水平高度基礎(chǔ)上，即在區(qū)域2 的水平高度上堆積。

圖2 所示的布局方式，從左到右緊挨著布局，會出現(xiàn)某功能區(qū)域無法容納的情況，即超出規(guī)劃區(qū)域Y 軸邊界。對于這種情況，越界處理方法如圖3 所示。第1 層包含區(qū)域1～ 4；第2 層包含區(qū)域5～ 7；第3層包含區(qū)域8 和區(qū)域9；當(dāng)布局到區(qū)域10，且采用堆積方式3，在堆積第4 層時，由于區(qū)域10 從最左邊開始布局，剩余豎直高度不夠，造成Y 軸越界，此時找出區(qū)域10 的X 軸覆蓋區(qū)域中水平高度最高的區(qū)域，即區(qū)域8，移動區(qū)域10 的X 軸，使其布局在區(qū)域8 的右邊，重新布局。此時第4 層可以包含區(qū)域8。由于采用堆積方式3，則若Y 軸高度不夠，可以降低區(qū)域10，使其剛好能布局到規(guī)劃區(qū)域內(nèi)為止，此時第4 層包含區(qū)域8 和區(qū)域10。如果此時仍越界，重復(fù)上述過程，直至將區(qū)域10 布局到規(guī)劃區(qū)域內(nèi)為止，同時記錄各層區(qū)域信息。

圖2 改進(jìn)分層思想示意圖Fig.2 Improved hierarchical thinking

圖3 越界處理方法Fig.3 Cross-border handling method

通過改進(jìn)分層的布局方法，擴(kuò)大了原來分層布局方法下搜索解的范圍，同時保持了搜索質(zhì)量，提高了物流區(qū)域布局優(yōu)化解的搜索效率。

2.2 堆積方式改進(jìn)

為了進(jìn)一步擴(kuò)大解的搜索范圍，對堆積方式進(jìn)一步改進(jìn)。改進(jìn)的堆積方式，主要針對單個功能區(qū)域的縱向堆積。當(dāng)對區(qū)域i進(jìn)行堆積時，找出區(qū)域i的X 軸覆蓋的所有區(qū)域中的最低水平高度y?i為下限，同時找出前一層中所有區(qū)域的最高水平高度yˇi為上限，此時能夠通過參數(shù)ri(0 ≤ri≤1)，確定區(qū)域i的Y 軸坐標(biāo)yi如公式 ⑹ 所示。

式中：ri表示第i個區(qū)域的堆積參數(shù)。

同樣以圖2 中區(qū)域7 的布局堆積方式為例，區(qū)域高度的隨機(jī)確定方法如圖4 所示。水平高度上限為d，水平高度下限為0，則確定r7=0.5，則區(qū)域7的Y 軸坐標(biāo)為：r7=0.5d+0.5h7。

圖4 區(qū)域高度的隨機(jī)確定方法Fig.4 Random determination of area height

對堆積方式的編碼等價于對各區(qū)域的堆積參數(shù)ri進(jìn)行編碼，由于任何區(qū)域的堆積參數(shù)的范圍均為[0，1]的連續(xù)區(qū)間，則可以利用連續(xù)區(qū)間的二進(jìn)制編碼近似表示。

綜上，通過引入堆積參數(shù)確定堆積方式，以及相應(yīng)的編碼方式，進(jìn)一步擴(kuò)大了解的搜索空間，同時保持了分層思想的優(yōu)點，可實現(xiàn)提高搜索解的質(zhì)量。

2.3 遺傳算子與算法流程設(shè)計

采用符號編碼和二進(jìn)制編碼相結(jié)合的方式表示布局問題的解空間。采用二進(jìn)制編碼{0，1}表示功能區(qū)域的放置方式，“0”代表橫放，“1”代表豎放；采用自然數(shù)編碼{1，…，N}表示功能區(qū)編號，特別將功能區(qū)域12 與功能區(qū)域10 交換位置，方便更好地求解問題。此外，以[0，1]之間的隨機(jī)數(shù)對堆積方式進(jìn)行編碼。每條染色體代表1 種布局方案，用C={Z1，Z2，…，ZN|T1，T2，…，TN|R}表示，其中Zi(1 ≤i≤N)代表功能區(qū)域編號；Tj(1 ≤j≤N)代表與之對應(yīng)的功能區(qū)域放置方向；R表示堆積方式。

以目標(biāo)函數(shù)即布局方案的成本函數(shù)為適應(yīng)度函數(shù)，對個體的編碼串進(jìn)行解碼處理，從而得到個體的表現(xiàn)型，由個體的表現(xiàn)型計算出目標(biāo)函數(shù)值。淘汰不滿足要求的染色體，而對于滿足限制條件的個體，以輪盤賭法作為選擇算子。具體操作過程為：對滿足要求的個體進(jìn)行分類處理，適應(yīng)度高的個體不需要參與遺傳操作直接進(jìn)入下一代種群中，以保留優(yōu)秀的基因，其他個體則采用輪盤賭法從上一代選擇n-1 個個體進(jìn)行接下來的遺傳操作，使得下一代的種群規(guī)模保持不變。對選擇出的個體進(jìn)行交叉操作，為保證交叉操作的有效性，避免子代無變化情況，采用部分交叉操作方式，即隨機(jī)選擇2 個個體，選擇交叉概率下的部分染色體編碼進(jìn)行交叉映射操作。在進(jìn)行變異操作時，設(shè)計2 種變異方法以增加種群的多樣性，包括基本位變異和交換變異?；疚蛔儺愂侵笇﹄S機(jī)個體的隨機(jī)位置產(chǎn)生隨機(jī)編碼替代的變異方式；交換變異是指對一條染色體的2 個部分進(jìn)行交換操作，以獲得新的子代的方式。遺傳算法流程圖如圖5 所示。

圖5 遺傳算法流程圖Fig.5 Flow chart of genetic algorithm

3 算法驗證

采用馮芬玲等[7]研究的算例，設(shè)置種群個數(shù)為500，最大繁衍代數(shù)為100，交叉概率為0.9，變異概率為0.01。分別對簡單堆積方式和改進(jìn)堆積方式進(jìn)行求解，從而驗證基于分層思想的改進(jìn)堆積方式的優(yōu)化效果。

對分層思想下的簡單堆積方式進(jìn)行求解，簡單堆積方式的物流區(qū)域布局如圖6 所示。由圖6 可知，各功能區(qū)域均滿足不重疊約束、功能區(qū)域邊界約束、固定約束和物流中心出入口約束。功能區(qū)簡單地根據(jù)下一層的最高點的縱坐標(biāo)和各個功能區(qū)之間的最短間距約束進(jìn)行堆積。分層思想下的算法收斂圖如圖7所示。由圖7 可知，遺傳算法收斂速度很快，通過14 代計算，目標(biāo)函數(shù)值快速下降，最后經(jīng)過100 代遺傳，目標(biāo)函數(shù)值達(dá)到6.673 9 萬元。該種方式下，最優(yōu)染色體為C1={3，11，4，9，6，7，10，8，2，1，5 | 0，0，0，0，0，0，1，1，0，0，0}。由于功能區(qū)10 為固定的坐標(biāo)和放置方向，因此，染色體只考慮了其余11 個功能區(qū)，即包含11 個因子。

圖6 簡單堆積方式的物流區(qū)域布局圖Fig.6 Layout of logistics area with simple accumulation method

圖7 簡單堆積方式的算法收斂圖Fig.7 Algorithm convergence graph of simple accumulation method

對分層思想下的改進(jìn)堆積方式算例進(jìn)行求解，改進(jìn)堆積方式的物流區(qū)域布局圖如圖8 所示。各功能區(qū)之間位置更加緊湊，布局更加緊密，得到較為滿意的布局結(jié)果。改進(jìn)堆積方式的算法收斂圖如圖9所示，由圖9 可知，遺傳算法收斂速度很快，通過16 代計算，目標(biāo)函數(shù)值快速下降，最后通過100 代遺傳，目標(biāo)函數(shù)值達(dá)到5.887 2 萬元，相比簡單堆積方式的情況，目標(biāo)值下降了約11.79%。在此方案下，最優(yōu)染色體為C2={7，3，5，10，4，2，11，6，1，9，8 | 1，1，1，1，0，0，0，0，0，1，0 | 0.750 79}，由此驗證，通過對堆積方式改進(jìn)，能夠獲得更加優(yōu)化的目標(biāo)函數(shù)值。

圖8 改進(jìn)堆積方式的物流區(qū)域布局圖Fig.8 Optimized logistics area layout map with improved accumulation method

圖9 改進(jìn)堆積方式的算法收斂圖Fig.9 Algorithm convergence graph with improved accumulation method

通過計算，2 種方式的最優(yōu)方案功能區(qū)坐標(biāo)如表1 所示。除了部分特殊功能區(qū)的位置較為相似，其他功能區(qū)的分布情況截然不同，同時可以看出改進(jìn)堆積方式的遺傳算法所求解更優(yōu)。

表1 2種方式的最優(yōu)方案功能區(qū)坐標(biāo) mTab.1 Coordinates of the optimal functional area schemes for the two methods

4 結(jié)束語

針對求解物流區(qū)域布局優(yōu)化模型，通過改進(jìn)分層布局方式和堆積方式，設(shè)計不同編碼方案，對提高算法搜索解質(zhì)量，擴(kuò)大算法搜索解空間具有良好的效果。通過改進(jìn)前后的遺傳算法對算例求解，表明所改進(jìn)遺傳算法在短時間內(nèi)獲得更加滿意的結(jié)果，目標(biāo)值較改進(jìn)前計算目標(biāo)值優(yōu)化11.79%，驗證了改進(jìn)后的布局方法可以有效降低各功能區(qū)之間的物流成本。此外，設(shè)計的算法能夠提高整個物流中心的運行效率，從而在競爭日益激烈的物流運輸中，提高鐵路的競爭力。算法基于緊湊型分層思想設(shè)計，但是對區(qū)域互斥情形考慮不全面，為了繼續(xù)擴(kuò)大搜索解的空間，同時保證解的可行性，可以對每層高度作為決策變量進(jìn)行進(jìn)一步優(yōu)化。