基于混合遺傳算法的鐵路物流中心布局研究

劉姣姣

（中國鐵路設(shè)計(jì)集團(tuán)有限公司 線站院，天津 300142）

0 引言

傳統(tǒng)鐵路貨場向現(xiàn)代鐵路物流中心（園區(qū)）轉(zhuǎn)型是我國鐵路貨運(yùn)組織改革的一項(xiàng)重要任務(wù)，物流中心除具備原有鐵路貨運(yùn)站功能外，還將融入現(xiàn)代物流服務(wù)，吸引相關(guān)企業(yè)入駐，使傳統(tǒng)的鐵路貨運(yùn)功能得到增值。

傳統(tǒng)的鐵路物流中心包括貨物倉儲(chǔ)區(qū)、包裝區(qū)、加工區(qū)、配送區(qū)、商貿(mào)業(yè)務(wù)區(qū)、公鐵聯(lián)運(yùn)區(qū)、物流金融區(qū)、電子交易區(qū)、集裝箱轉(zhuǎn)運(yùn)區(qū)等不同功能區(qū)。將它們按照一定的優(yōu)化準(zhǔn)則組合在一起，充分發(fā)揮各區(qū)域的功能屬于一種布局問題[1-2]。

布局問題是NP-hard問題，由于布局問題的復(fù)雜性，在有限的時(shí)間內(nèi)難以獲得問題的精確解[3-4]，所以絕大部分解決布局問題的算法是啟發(fā)式的，在這些啟發(fā)式算法中，遺傳算法以其高效性、并行性和較好的魯棒性在布局問題中得到了較為廣泛的應(yīng)用[5-6]。在國內(nèi)，一部分研究者已將遺傳算法應(yīng)用于鋼鐵物流中心的內(nèi)部規(guī)劃[7-8]和鐵路物流中心的布局研究[9-10]。

物流中心的最優(yōu)布局依賴于優(yōu)化模型的合理性和優(yōu)化算法的高效性。傳統(tǒng)的模型多以矩形為物流中心邊界，并采用傳統(tǒng)的遺傳算法進(jìn)行求解，假設(shè)其矩形邊界缺乏對實(shí)際不規(guī)則邊界的適應(yīng)性，而傳統(tǒng)遺傳算法通常因早熟而易陷入局部最優(yōu)解。為解決上述問題，通過建立能夠考慮物流中心不規(guī)則邊界條件的優(yōu)化模型，在傳統(tǒng)遺傳算法中引入模擬退火局部搜索機(jī)制，以增強(qiáng)算法的全局收斂性，從而獲得最優(yōu)的、合理的物流中心布局。

1 鐵路物流中心最優(yōu)布局?jǐn)?shù)學(xué)模型

1.1 最優(yōu)目標(biāo)的原則及優(yōu)化模型

物流中心布局規(guī)劃應(yīng)當(dāng)遵循以下原則[11]：①運(yùn)輸成本最小化；②功能區(qū)之間的聯(lián)系最大化；③功能區(qū)之間不能重疊并保持一定的距離；④功能區(qū)應(yīng)當(dāng)在物流中心規(guī)劃范圍內(nèi)。運(yùn)輸成本最優(yōu)模型計(jì)算公式為

式中：F1為運(yùn)輸成本；dij為i到j(luò)的距離；gij為i到j(luò)運(yùn)輸物品的重量。

功能區(qū)之間關(guān)系最大化模型計(jì)算公式為

式中：目標(biāo)函數(shù)將功能區(qū)之間關(guān)系最大化模型轉(zhuǎn)換為最小化模型形式，F(xiàn)2為功能區(qū)之間的關(guān)系函數(shù)；V為功能區(qū)i與j的最大相鄰關(guān)聯(lián)度（取V= 4）；Rij為i與j的相互關(guān)系，分為物流關(guān)系mrij和非物流關(guān)系nrij，通過權(quán)重系數(shù)α和β加權(quán)組成；非物流關(guān)系由與業(yè)務(wù)流程、組織管理和環(huán)境安全的nrij1，nrij2，nrij3通過權(quán)重系數(shù)w1，w2，w3組成；bij為廣義距離相鄰度[7]。

為了適應(yīng)物流中心土地的實(shí)際情況，增強(qiáng)優(yōu)化目標(biāo)的靈活性，建立了考慮不規(guī)則邊界情況的約束條件準(zhǔn)則。根據(jù)功能區(qū)的特點(diǎn)，一般功能區(qū)均以矩形功能區(qū)為主，而園區(qū)土地邊界可以考慮任意的邊界形狀。功能區(qū)變量示意圖如圖1所示，對于一個(gè)功能區(qū)而言，中心坐標(biāo) （xi，yi）、長度Li、寬度Wi和角度αi可惟一確定該功能區(qū)的位置和形態(tài)，第k個(gè)角點(diǎn)的坐標(biāo)計(jì)算公式為

式中：θi1—θi4分別為功能區(qū)4個(gè)角點(diǎn)相對于X坐標(biāo)軸正方向的角度。

圖1 功能區(qū)變量示意圖Fig.1 Sketch map of functional area variables

1.2 約束條件

模型需滿足2個(gè)約束條件：①功能區(qū)之間不能重合；②功能區(qū)不得超出邊界，其中邊界通過連續(xù)坐標(biāo)點(diǎn)表示。這2種約束條件可采用計(jì)算幾何的射線法或面積法[12]從檢驗(yàn)功能區(qū)i與功能區(qū)j的點(diǎn)面相對關(guān)系，以及功能區(qū)i與物流中心邊界區(qū)域的點(diǎn)面關(guān)系予以判定。當(dāng)滿足上述2個(gè)邊界條件時(shí)，罰函數(shù)置為0，否則，設(shè)置一個(gè)較大的罰數(shù)。此外，每個(gè)功能區(qū)的長度和寬度要保持一定的比例，即：λmin≤λi=Li/Wi180°≤λmax。按照歸一化原則并考慮各種權(quán)重可將2個(gè)子目標(biāo)函數(shù)組合成一個(gè)單目標(biāo)函數(shù)。

式中：μ1，μ2分別為 2 個(gè)子函數(shù)權(quán)重系數(shù)，μ1+μ2= 1；歸一化系數(shù)其中V含義同前，可取4；Np1，Np2，Np3分別為功能區(qū)相互重疊數(shù)目、功能區(qū)超出物流中心用地界的數(shù)目和功能區(qū)長寬比超出規(guī)定范圍的數(shù)目。

優(yōu)化目標(biāo)函數(shù)的優(yōu)化變量為xi，yi，αi，Li，Wi。優(yōu)化目標(biāo)函數(shù)同時(shí)覆蓋了2個(gè)子優(yōu)化目標(biāo)，并同時(shí)考慮了邊界約束條件。此外，還能夠針對任意物流中心邊界形狀的情況進(jìn)行優(yōu)化。

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

混合遺傳算法將傳統(tǒng)的遺傳算法與模擬退火算法結(jié)合，發(fā)揮遺傳算法泛化搜索和模擬退火算法局部精細(xì)化搜索的優(yōu)點(diǎn)。為了避免Hamming懸崖問題[13]，采用格雷碼進(jìn)行算法設(shè)計(jì)。

將模擬退火算法融入遺傳算法，以遺傳算法中的適應(yīng)度比模擬退火算法中的內(nèi)能，將執(zhí)行遺傳操作之前的種群作為模擬退火算法的輸入解，對該輸入解進(jìn)行遺傳操作產(chǎn)生新解（即遺傳算法的新個(gè)體），并利用Metropolis抽樣法則對新解進(jìn)行抽樣。在算法搜索初期，解的分布范圍比較廣，且目標(biāo)函數(shù)的曲面上分布較多局部峰谷，對適應(yīng)度較低的解，接受概率比較大。在搜索后期，逐步逼近全局最優(yōu)，接受適應(yīng)度較低解的概率應(yīng)當(dāng)趨于0。

在整個(gè)算法過程中，遺傳算法的進(jìn)化代數(shù)與模擬退火的溫度進(jìn)程統(tǒng)一為一個(gè)循環(huán)控制參數(shù)，使得每次遺傳算法操作均發(fā)生在模擬退火算法的某一溫度下，具體算法如下。

（1）設(shè)置各項(xiàng)參數(shù)，隨機(jī)產(chǎn)生初始種群。

（2）評價(jià)初始種群的個(gè)體適應(yīng)度，將高適應(yīng)度的個(gè)體作為父代種群。

（3）父代種群根據(jù)設(shè)定的交叉概率和變異概率執(zhí)行交叉和變異操作產(chǎn)生子代。

（4）根據(jù)進(jìn)化代數(shù)，確定相應(yīng)的模擬退火溫度，執(zhí)行模擬退火局部搜索，保留優(yōu)秀個(gè)體。

（5）檢驗(yàn)結(jié)果是否收斂，若收斂則輸出最優(yōu)解并結(jié)束搜索，否則轉(zhuǎn)（2）。

1.4 算法檢驗(yàn)

通過搜索經(jīng)典有解析解的Schaffer函數(shù)的最大值來檢驗(yàn)所設(shè)計(jì)混合遺傳算法的有效性。該函數(shù)全局最大值為1 （x= 0，y= 0），在全局最高點(diǎn)附近有一圈局部次高點(diǎn)，其對應(yīng)的值約為0.990 28，其函數(shù)表達(dá)式為

混合遺傳算法的控制參數(shù)設(shè)置如下：最大進(jìn)化代數(shù)200，種群規(guī)模200，交叉概率0.7，變異概率0.05，初始溫度10 000。函數(shù)圖像如圖2所示，測試函數(shù)尋優(yōu)收斂曲線如圖3所示，測試函數(shù)優(yōu)化結(jié)果如表1所示。在圖3中，以解的變化曲線表示每一代群體中最優(yōu)秀得個(gè)體，用均值表示每一代群體的總體情況，由于函數(shù)的多峰值性，搜索前期震蕩較大，在前75代左右解的收斂曲線呈階梯形上升，目標(biāo)函數(shù)值由0.995跳到無限接近1的位置，同時(shí)均值收斂曲線斜率增大，收斂速度加快，與解的收斂曲線幾乎重合，快速穩(wěn)定地收斂到全局最優(yōu)解，說明該算法具有很強(qiáng)的全局搜索能力。

圖2 函數(shù)圖像Fig.2 Function images

圖3 測試函數(shù)尋優(yōu)收斂曲線Fig.3 Test function optimization convergence curve

表1 測試函數(shù)優(yōu)化結(jié)果Tab.1 Test function optimization results

2 實(shí)例分析

某鐵路物流中心規(guī)劃總占地1 200 000 m2，由于市政規(guī)劃道路的分割和地形條件的限制，可被用作物流中心的用地邊界通常是不規(guī)則的。物流中心包括倉儲(chǔ)區(qū)、保稅區(qū)、配送區(qū)、流通加工區(qū)、交易展示區(qū)、辦公生活區(qū)、集中停車區(qū)7大功能區(qū)。各功能區(qū)規(guī)劃用地面積如表2所示，各功能區(qū)之間日均物流量如表 3所示，各功能區(qū)之間綜合物流關(guān)系如表 4所示。

表2 各功能區(qū)規(guī)劃用地面積 m2Tab.2 Planning area of each functional area

表3 各功能區(qū)之間日均物流量 tTab.3 Daily average volume of flow between each functional area

表4 各功能區(qū)之間綜合物流關(guān)系Tab.4 Integrated logistics relationship among functional areas

通過優(yōu)化模型以及混合遺傳算法的優(yōu)化求解方法，所得到的最優(yōu)物流中心總布置如圖 4所示。由圖 4中可知，物理中心布局中將停車場沿用地界的斜邊布置，這樣可以節(jié)省場地并滿足用地需求，同時(shí)距離關(guān)系緊密貨運(yùn)量大的倉儲(chǔ)區(qū)、配送區(qū)和流通加工區(qū)較近，交易展示區(qū)和辦公生活服務(wù)區(qū)位于左下角，最大程度實(shí)現(xiàn)了物流中心的優(yōu)化配置。

圖4 物流中心總布置圖Fig.4 General layout of logistics center

3 結(jié)論

針對不規(guī)則物流中心的優(yōu)化目標(biāo)函數(shù)，引入了局部搜索能力較強(qiáng)的模擬退火算法，形成了物流中心布局最優(yōu)化的整套解決方案，并對某物流中心進(jìn)行了布局的優(yōu)化，主要結(jié)論如下。

（1）提出可以適應(yīng)于不同邊界形狀物流中心用地的優(yōu)化算法，同時(shí)在功能區(qū)的空間優(yōu)化目標(biāo)函數(shù)中引入了轉(zhuǎn)動(dòng)自由度，以適應(yīng)不規(guī)則邊界的功能區(qū)布局問題。

（2）將傳統(tǒng)遺傳算法與模擬退火算法相結(jié)合，增強(qiáng)優(yōu)化方法的全局收斂性，保證了優(yōu)化求解的精度。

（3）物流中心的最優(yōu)布局取決于優(yōu)化目標(biāo)函數(shù)的合理性以及求解方法的高效性，所建立的目標(biāo)函數(shù)能夠很好地考慮實(shí)際物流中心規(guī)劃中遇到的用地形狀問題，同時(shí)算法本身具備很強(qiáng)的全局搜索能力，因而有更廣泛的實(shí)用性。

（4）為物流中心的布局提供一種方法，為后續(xù)的物流中心設(shè)計(jì)提供一個(gè)理論的最優(yōu)布局方案，在實(shí)際應(yīng)用中，僅需要根據(jù)實(shí)際情況進(jìn)行局部修改和調(diào)整即可形成最終的物流中心布局方案。