金忠旭　郭躍顯

[提要] 國(guó)內(nèi)現(xiàn)有物資總庫(kù)選址多采用一條線路至少設(shè)置一個(gè)物資總庫(kù)，雖然這種方法可以極大地縮短設(shè)施點(diǎn)處理突發(fā)事件的時(shí)間，但卻容易造成重復(fù)建設(shè)。本文以時(shí)間與成本因素為主要考慮對(duì)象的物資總庫(kù)選址問(wèn)題，提出以集合覆蓋選址模型為基礎(chǔ)的單物資總庫(kù)服務(wù)多線路的研究方法，建立物資總庫(kù)選址模型。以沈陽(yáng)市現(xiàn)有物資總庫(kù)布局情況為例，運(yùn)用遺傳算法通過(guò)MATLAB進(jìn)行運(yùn)算求解，優(yōu)化該城市現(xiàn)有物資總庫(kù)數(shù)量，從而有效降低建設(shè)及運(yùn)營(yíng)成本，希望本文所研究?jī)?nèi)容對(duì)相關(guān)研究者起到一定借鑒意義。

關(guān)鍵詞：物資總庫(kù)；城市軌道交通；集合覆蓋選址；遺傳算法

中圖分類號(hào)：F27 文獻(xiàn)標(biāo)識(shí)碼：A

原標(biāo)題：基于LSCP的城市軌道交通物資總庫(kù)選址模型研究

收錄日期：2015年11月30日

一、引言

近年來(lái)，城市軌道交通的發(fā)展在為人們出行提供便利的同時(shí)，也面臨著各種突發(fā)情況，需要對(duì)損壞區(qū)域進(jìn)行及時(shí)維修，而要達(dá)到維修的及時(shí)性，不止維修人員要按時(shí)趕赴現(xiàn)場(chǎng)，材料工具更需要及時(shí)送到，從設(shè)施點(diǎn)到需求點(diǎn)的時(shí)間長(zhǎng)短將直接影響到維修的效率和事故損失程度，因此時(shí)間是決定維修效率高低和損失大小的關(guān)鍵因素，必須對(duì)物資總庫(kù)進(jìn)行合理布局以縮短設(shè)備工具的供應(yīng)時(shí)間。傳統(tǒng)的布局方式將時(shí)間因素過(guò)度敏感化，認(rèn)為服務(wù)設(shè)施點(diǎn)數(shù)量越多，距離需求點(diǎn)越近，維修的能力就越強(qiáng)，事故造成的損失也就越小，這樣做雖然可以有效減少設(shè)備的供應(yīng)時(shí)間，但是由于地鐵運(yùn)行狀況的特殊性，其事故發(fā)生的概率相對(duì)較小，而服務(wù)設(shè)施點(diǎn)的建立和日常管理與維護(hù)都需要大量資金，如果建立的服務(wù)設(shè)施點(diǎn)數(shù)量太多就會(huì)導(dǎo)致上述成本成倍增長(zhǎng)，設(shè)施利用率顯著降低等。

本文物資總庫(kù)選址與一般物流配送中心等服務(wù)設(shè)施選址需要考慮的因素不同。傳統(tǒng)物流配送中心多考慮成本因素對(duì)其選址的影響程度，而本文物資總庫(kù)的選址更注重將時(shí)間因素與成本因素相結(jié)合考慮。因此，本文采用集合覆蓋模型對(duì)現(xiàn)有物資總庫(kù)進(jìn)行選址。通過(guò)應(yīng)用集合覆蓋選址模型既可以有效減少物資總庫(kù)建設(shè)數(shù)量，節(jié)約建設(shè)成本與運(yùn)營(yíng)成本，又可以通過(guò)大批量采購(gòu)或者配送，降低采購(gòu)和配送成本，提高運(yùn)輸設(shè)備的裝載率，極大地緩解城市交通壓力。

二、相關(guān)研究

關(guān)于選址問(wèn)題，國(guó)外學(xué)者研究相對(duì)較早，Coober（1963）第一次提出了設(shè)施選址問(wèn)題，并將極值方程與啟發(fā)式算法應(yīng)用于選址問(wèn)題中。在此之后，不斷總結(jié)出的選址模型有重心法、集覆蓋法、P-中值模型等。Vladmir討論了基于P-中值的排隊(duì)論覆蓋選址問(wèn)題。Toregas等人最早討論了應(yīng)急服務(wù)設(shè)施選址的集合覆蓋模型，即對(duì)于事先給定的服務(wù)覆蓋半徑，如何確定服務(wù)設(shè)施點(diǎn)的數(shù)量及位置，使得所有的需求點(diǎn)距離其最近的設(shè)施點(diǎn)不超過(guò)覆蓋半徑。Toregas和Revelle又分別提出了精確求解LSCP的行和列簡(jiǎn)化算法。Brotcorne等研究了求解需求點(diǎn)離散、潛在設(shè)施點(diǎn)連續(xù)的大規(guī)模覆蓋選址問(wèn)題的快速啟發(fā)式算法。Karasakal（2015）在其發(fā)表的文章中提出了基于多目標(biāo)問(wèn)題的部分覆蓋下設(shè)施選址問(wèn)題，并應(yīng)用改進(jìn)的SPEA2對(duì)其模型進(jìn)行求解。Iris發(fā)表了一篇將遺傳算法應(yīng)用到物流供應(yīng)鏈設(shè)計(jì)問(wèn)題中的論文，具有良好的參考價(jià)值。

國(guó)內(nèi)相關(guān)學(xué)者在選址問(wèn)題的研究方面也有突出貢獻(xiàn)。沈默等運(yùn)用了重心法對(duì)物流配送中心進(jìn)行選址研究，分析了重心法選址的優(yōu)點(diǎn)與缺點(diǎn)，并且將重心法選址模型運(yùn)用到蘇寧配送中心選址方案選擇中。苗興東等結(jié)合物理學(xué)中相關(guān)知識(shí)，提出了重心法能利用一個(gè)二維封閉圖形求解重心，以此來(lái)解決物流設(shè)施的選址問(wèn)題并通過(guò)一個(gè)算例對(duì)其進(jìn)行了具體實(shí)踐。張彩慶等提出了基于P-中值模型的電網(wǎng)檢修分公司選址模型，構(gòu)建了基于P-中值模型的電網(wǎng)檢修分公司靜態(tài)選址方案和改進(jìn)的P-中值模型的動(dòng)態(tài)選址方案，為檢修公司分部的選址問(wèn)題提供了一種有效的研究方法和選擇依據(jù)。王世偉提出了在最壞失效狀態(tài)下的P-中值選址問(wèn)題，并列舉了幾個(gè)求解中值問(wèn)題的常用算法。Li等人在考慮實(shí)際工程要求的基礎(chǔ)上，研究了用經(jīng)典集覆蓋模型進(jìn)行地鐵設(shè)備應(yīng)急搶修點(diǎn)選址問(wèn)題。當(dāng)存在成本或資源約束而不能滿足所有的需求點(diǎn)時(shí)，則要盡可能覆蓋可達(dá)到的需求點(diǎn)。肖俊華（2012）發(fā)表的論文在考慮總體成本最低的情況下，通過(guò)對(duì)應(yīng)急儲(chǔ)備庫(kù)選址的深入研究，提出了集合覆蓋模型的構(gòu)建方法。在應(yīng)用遺傳算法對(duì)選址問(wèn)題進(jìn)行求解方面，譚前進(jìn)（2007）等發(fā)表的文章論述了以遺傳算法為基礎(chǔ)的物流配送系統(tǒng)方案設(shè)計(jì)，闡述了遺傳算法在車輛調(diào)度中的應(yīng)用。通過(guò)模擬實(shí)驗(yàn)，該智能化配送系統(tǒng)適合于任何中小型物流公司調(diào)度車輛。張琨（2011）對(duì)武漢城市軌道交通網(wǎng)進(jìn)行了全面的調(diào)查和研究，基于成本因素的考慮提出了多線共用物資總庫(kù)的模式，并對(duì)物資總庫(kù)布局建立了相應(yīng)的總體規(guī)劃模型，通過(guò)遺傳算法與MATLAB軟件實(shí)現(xiàn)了武漢市物資總庫(kù)的選址研究。

本文在參考上述思想方法與理論的基礎(chǔ)上，對(duì)模型的選取進(jìn)行了深入研究?？紤]到物資總庫(kù)優(yōu)化選址屬于服務(wù)設(shè)施點(diǎn)數(shù)量、位置選擇均未知的多物流節(jié)點(diǎn)選址問(wèn)題，重心法和P-中值模型無(wú)法滿足其要求，而集合覆蓋模型是解決在時(shí)間要求的覆蓋半徑內(nèi)以最少數(shù)量的設(shè)施點(diǎn)服務(wù)所有需求點(diǎn)的問(wèn)題，從而完成對(duì)設(shè)施點(diǎn)的選址。同時(shí)，對(duì)物資總庫(kù)選址相關(guān)論文的研究中并未見(jiàn)采取集合覆蓋模型的選址方法。因此，本文從單設(shè)施點(diǎn)服務(wù)多需求點(diǎn)的思想出發(fā)，提出了基于集合覆蓋方法的物資總庫(kù)選址模型。

三、建立選址模型及遺傳算法設(shè)計(jì)

（一）選址模型關(guān)鍵因素分析。物資總庫(kù)選址是受多重因素影響的綜合性選址問(wèn)題。不同位置、不同目標(biāo)的物資總庫(kù)在選址時(shí)需要考慮的影響因素有所不同，由于本文所研究的選址問(wèn)題是應(yīng)用集合覆蓋選址模型對(duì)物資總庫(kù)進(jìn)行選址，其主要影響因素重點(diǎn)分析了以下兩點(diǎn)：

1、時(shí)間因素。本文重點(diǎn)研究在時(shí)間因素影響下進(jìn)行物資總庫(kù)選址的問(wèn)題。城市軌道交通屬于公共基礎(chǔ)設(shè)施范疇，主要作用是為人們出行提供便利，改善人們生活質(zhì)量，如遇到緊急事故，一條線路出現(xiàn)問(wèn)題將會(huì)影響另一條線路的正常運(yùn)行，在鏈?zhǔn)椒磻?yīng)的作用下，整個(gè)城市的軌道交通都可能陷入癱瘓，其造成的經(jīng)濟(jì)損失將無(wú)法估量。因此，應(yīng)將維修的及時(shí)性放在首位，在要求的時(shí)間內(nèi)將事故妥善處理好，從而避免更大的經(jīng)濟(jì)損失。根據(jù)國(guó)外研究統(tǒng)計(jì)，在發(fā)生事故20min內(nèi)如果能得到及時(shí)處理，所造成的經(jīng)濟(jì)損失與40min后才得到處理，經(jīng)濟(jì)損失比值約為1∶8。故本文以20min作為集合覆蓋模型時(shí)間覆蓋半徑，即每個(gè)設(shè)施點(diǎn)所服務(wù)對(duì)象是以20min能到達(dá)為基準(zhǔn)，否則該設(shè)施點(diǎn)將失去對(duì)其服務(wù)的能力。

2、經(jīng)濟(jì)因素。經(jīng)濟(jì)因素主要包括物資總庫(kù)的建設(shè)費(fèi)用、建設(shè)數(shù)量等。具體來(lái)說(shuō)，應(yīng)該考慮物資總庫(kù)所在地地價(jià)，同時(shí)如果建設(shè)過(guò)多的物資總庫(kù)，雖然為需求點(diǎn)提供服務(wù)速度快、時(shí)間短，但是建設(shè)費(fèi)用、運(yùn)營(yíng)費(fèi)用會(huì)隨著物資總庫(kù)數(shù)目增加而增多，一般情況下，物資總庫(kù)是建設(shè)在車輛段內(nèi)部。所以總體來(lái)說(shuō)物資總庫(kù)的數(shù)量并不是一味的越多越好。在滿足覆蓋所有需求點(diǎn)的要求下，應(yīng)盡量建設(shè)少的設(shè)施點(diǎn)。

（二）模型建立及描述。集合覆蓋（LSCP），是指在備選設(shè)施點(diǎn)和需求點(diǎn)的數(shù)量已知情況下，用盡可能少的設(shè)施點(diǎn)來(lái)覆蓋所有需求點(diǎn)，從而確定一個(gè)滿意的設(shè)施點(diǎn)集合，要求其滿足所有的需求點(diǎn)至少覆蓋1次，同時(shí)總體建設(shè)成本最低，其基本模型如下：

其中目標(biāo)函數(shù)（1）式要求達(dá)到建立的服務(wù)設(shè)施點(diǎn)數(shù)量最少；約束（2）式表示對(duì)任意一個(gè)需求點(diǎn)i，至少有一個(gè)設(shè)施點(diǎn)j可以為其提供服務(wù)；（3）式是變量取值約束條件。

物資總庫(kù)選址只包括兩類站點(diǎn)，一類是需求站點(diǎn)，文中稱為需求點(diǎn)；一類是服務(wù)站點(diǎn)，文中稱為物資總庫(kù)。本文以各個(gè)物資總庫(kù)的建設(shè)及運(yùn)營(yíng)成本Cj以及物資總庫(kù)與各需求點(diǎn)之間的時(shí)間距離Tij作為主要參考數(shù)據(jù)，建立物資總庫(kù)集合覆蓋選址模型，模型假設(shè)如下：

假設(shè)1：物資總庫(kù)和需求點(diǎn)均為點(diǎn)狀形式存在的離散點(diǎn)；

假設(shè)2：任意物資總庫(kù)和需求點(diǎn)的時(shí)間距離可通過(guò)調(diào)查或計(jì)算產(chǎn)生；

假設(shè)3：各物資總庫(kù)的容量無(wú)限制。

目標(biāo)函數(shù)（4）表示模型以總成本最低為目標(biāo)；約束（5）表示每個(gè)需求點(diǎn)i至少由1個(gè)設(shè)施點(diǎn)j為其提供服務(wù)；約束（6）表示yij=1時(shí)需滿足的前提條件是需求點(diǎn)i到服務(wù)設(shè)施點(diǎn)j的時(shí)間距離不大于時(shí)間覆蓋半徑？茲，否則為0；約束（7）為二元整數(shù)決策變量。

（三）模型求解算法。遺傳算法是一種較新的全局隨機(jī)搜索算法，其基本思想源自于達(dá)爾文的“適者生存”理論和生物遺傳學(xué)觀點(diǎn)，具有較強(qiáng)的可操作性，魯棒性高，應(yīng)用范圍廣。遺傳算法自出現(xiàn)以來(lái)就在函數(shù)優(yōu)化問(wèn)題中得到了廣泛應(yīng)用，由于其只需函數(shù)值的相關(guān)信息，不需要設(shè)計(jì)空間或函數(shù)的連續(xù)，因而適合于求解各類函數(shù)優(yōu)化問(wèn)題。同時(shí)，遺傳算法能在設(shè)計(jì)空間的較大范圍內(nèi)尋找最優(yōu)解，因而更有可能獲得全局優(yōu)化解。目前，遺傳算法已用來(lái)解決連續(xù)變量?jī)?yōu)化問(wèn)題、混合離散變量?jī)?yōu)化問(wèn)題、組合優(yōu)化問(wèn)題等。但是遺傳算法的應(yīng)用難點(diǎn)在于對(duì)研究者的編程能力有一定要求，而這一問(wèn)題在MATLAB 7.0軟件之后得到了妥善解決，在MATLAB 7.0中增添了GADS的GUI界面，它使用MATLAB矩陣函數(shù)為實(shí)現(xiàn)廣泛領(lǐng)域的遺傳算法建立了一套通用工具，這套工具是用M文件寫(xiě)的命令行形式的函數(shù)，是完成遺傳算法大部分重要功能的程序的集合。用戶可通過(guò)這些命令行函數(shù)，在GUI界面上根據(jù)實(shí)際分析的需要，選擇不同形式的初始種群數(shù)量、遺傳算子等。其基本實(shí)現(xiàn)步驟如下：

第一步：確定適應(yīng)度函數(shù)及約束條件。本文采用的適應(yīng)度函數(shù)為所提供的目標(biāo)函數(shù)式（4），將待優(yōu)化的函數(shù)在MATLAB界面點(diǎn)擊New Script，編寫(xiě)函數(shù)式為相應(yīng)的M文件形式。從而在GUI界面Fitness function處填寫(xiě)@function name。

第二步：確定編碼方式。采用序號(hào)編碼方式（Double vector），編碼位串長(zhǎng)度為需求點(diǎn)的個(gè)數(shù)，基因的數(shù)值為設(shè)施點(diǎn)的編號(hào)，基因的位置為需求點(diǎn)的編號(hào)。例如，有4個(gè)服務(wù)設(shè)施點(diǎn)，8個(gè)需求點(diǎn)，染色體{1，3，4，2，4，1，2，1}表示設(shè)施點(diǎn)1為需求點(diǎn)1、6、8配送設(shè)備工具，設(shè)施點(diǎn)2為需求點(diǎn)4提供配送，設(shè)施點(diǎn)3為需求點(diǎn)2提供配送，設(shè)施點(diǎn)4為需求點(diǎn)3、5提供配送服務(wù)。

第三步：確定初始種群。遺傳算法是對(duì)群體進(jìn)行的進(jìn)化操作，需要準(zhǔn)備一些表示起始搜索點(diǎn)的初始群體數(shù)據(jù)。本文將初始種群數(shù)設(shè)定為M=40。

第四步：設(shè)計(jì)遺傳算子。選擇算子作為實(shí)施“適者生存”的演化方式，采用最佳個(gè)體保存法，本文直接復(fù)制種群中的兩個(gè)最佳染色體到下一代，再按輪盤(pán)賭方式進(jìn)行剩余個(gè)體選擇操作，這樣可以保證遺傳算法的收斂性；交叉算子使用Scattered（分散）方式，這是一個(gè)缺省的交叉函數(shù)，它創(chuàng)建一個(gè)二進(jìn)制向量，如果這個(gè)向量某位是1，則這個(gè)基因從第一個(gè)父輩中來(lái)，并且設(shè)定本文的交叉概率PC=0.8；變異算子采用常用的高斯變異，其中將Scale和Shrink設(shè)置為缺省值即可。

第五步：終止條件。遺傳算法是一種反復(fù)迭代的隨機(jī)搜索方法，在每次迭代中，記下適應(yīng)值最大的染色體，直到已經(jīng)達(dá)到了算法規(guī)定的最大迭代次數(shù)或在規(guī)定的連續(xù)迭代次數(shù)內(nèi)最好的染色體不再發(fā)生變化時(shí)算法終止。當(dāng)算法終止時(shí)，最好的染色體即是該選址問(wèn)題的最優(yōu)解。本文設(shè)定最大迭代次數(shù)。

四、應(yīng)用算例

沈陽(yáng)市地鐵線路有40個(gè)需求點(diǎn)，現(xiàn)有的物資總庫(kù)數(shù)目為12個(gè)，各個(gè)物資總庫(kù)的建設(shè)及運(yùn)營(yíng)成本如表1所示。為整合倉(cāng)儲(chǔ)資源，節(jié)約日常運(yùn)營(yíng)成本，合理優(yōu)化倉(cāng)儲(chǔ)網(wǎng)絡(luò)布局，對(duì)物資總庫(kù)數(shù)量進(jìn)行削減。首先通過(guò)實(shí)地調(diào)研與考察，由于地鐵線路固定，任意兩地間的行駛時(shí)間變化不大，因此各個(gè)位置點(diǎn)的相關(guān)時(shí)間參數(shù)如表2所示。假定模型覆蓋時(shí)間半徑？茲=20（min）。圖1所示為優(yōu)化前的需求點(diǎn)與物資總庫(kù)布局示意圖。（表1、表2、圖1）

由表3可知，優(yōu)化后的物資總庫(kù)足以滿足現(xiàn)有需求點(diǎn)的調(diào)運(yùn)方案，并由此會(huì)節(jié)約的成本為8，560萬(wàn)元。（圖2）

五、總結(jié)

本文在進(jìn)行物資總庫(kù)選址時(shí)，由于考慮到城市軌道交通的特殊性，時(shí)間因素是影響其選址的重要因素，同時(shí)又必須考慮建設(shè)及運(yùn)營(yíng)成本對(duì)選址的影響，故本文在兩者共同影響下，應(yīng)用集合覆蓋選址方法，建立了物資總庫(kù)的選址模型，并借助遺傳算法尋求最合理的選址結(jié)果，通過(guò)算例對(duì)模型的應(yīng)用進(jìn)行了實(shí)驗(yàn)，結(jié)果顯示優(yōu)化后的物資總庫(kù)布局可降低總成本數(shù)額為8，560萬(wàn)元。

由于本文是在假設(shè)各服務(wù)設(shè)施點(diǎn)容量無(wú)限制的情況下，重點(diǎn)研究時(shí)間與成本因素對(duì)選址的影響，同時(shí)由算例的結(jié)論可以知道，某一需求點(diǎn)可由多個(gè)設(shè)施點(diǎn)為其提供服務(wù)，因此將來(lái)的拓展方向?qū)⑹强紤]在多目標(biāo)同時(shí)影響的條件下通過(guò)多目標(biāo)決策與其他啟發(fā)式算法等對(duì)物資總庫(kù)選址做進(jìn)一步優(yōu)化，并且對(duì)多設(shè)施點(diǎn)均可提供服務(wù)問(wèn)題，做出優(yōu)先級(jí)的排序，使其更符合現(xiàn)實(shí)需要，創(chuàng)造更大的應(yīng)用價(jià)值。

主要參考文獻(xiàn)：

[1]Cooper S.L.Location-allocation Problems[J].Operation Research，1963.11.

[2]Vladmiir Charles.The queuing probabilistic location set covering and some extension[J].Socio-economic Planning Science，1994.28.

[3]Toregas Revelle，L.Bergman.The local of emergency services facilities[J].Operations Research，2011.19.

[4]Toregas Revelle.Optimal location under time or distance constrains[J].Papers of the Regional Science Association，2012.28.

[5]Toregas Revelle.Binary logic solutions to a class of location problems[J].Geographical Analysis，2011.5.

[6]Brotcorne Laporte.Fast heuristics for large scale covering location problems[J].Computers & Operations Research，2002.29.

[7]Karasakal Silav.A multi-objective genetic algorithm for a bi-objective facility location problem with partial coverage[J].2015.

[8]Iris Asan.A review of genetic algorithm applications in supply chain network design[J].Computational intelligence systems in industrial engineering—with recent theory and applications. Atlantic Press，2012.

[9]Li Man. Research on the location allocation model for subway emergency service facilities under network operating conditions[C].IEEE Press，2011.