城市軌道交通物資總庫選址模型研究

金忠旭　郭躍顯

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

關鍵詞：物資總庫；城市軌道交通；集合覆蓋選址；遺傳算法

中圖分類號：F27 文獻標識碼：A

原標題：基于LSCP的城市軌道交通物資總庫選址模型研究

收錄日期：2015年11月30日

一、引言

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

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

二、相關研究

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

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

本文在參考上述思想方法與理論的基礎上，對模型的選取進行了深入研究。考慮到物資總庫優化選址屬于服務設施點數量、位置選擇均未知的多物流節點選址問題，重心法和P-中值模型無法滿足其要求，而集合覆蓋模型是解決在時間要求的覆蓋半徑內以最少數量的設施點服務所有需求點的問題，從而完成對設施點的選址。同時，對物資總庫選址相關論文的研究中并未見采取集合覆蓋模型的選址方法。因此，本文從單設施點服務多需求點的思想出發，提出了基于集合覆蓋方法的物資總庫選址模型。

三、建立選址模型及遺傳算法設計

（一）選址模型關鍵因素分析。物資總庫選址是受多重因素影響的綜合性選址問題。不同位置、不同目標的物資總庫在選址時需要考慮的影響因素有所不同，由于本文所研究的選址問題是應用集合覆蓋選址模型對物資總庫進行選址，其主要影響因素重點分析了以下兩點：

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

2、經濟因素。經濟因素主要包括物資總庫的建設費用、建設數量等。具體來說，應該考慮物資總庫所在地地價，同時如果建設過多的物資總庫，雖然為需求點提供服務速度快、時間短，但是建設費用、運營費用會隨著物資總庫數目增加而增多，一般情況下，物資總庫是建設在車輛段內部。所以總體來說物資總庫的數量并不是一味的越多越好。在滿足覆蓋所有需求點的要求下，應盡量建設少的設施點。

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

其中目標函數（1）式要求達到建立的服務設施點數量最少；約束（2）式表示對任意一個需求點i，至少有一個設施點j可以為其提供服務；（3）式是變量取值約束條件。

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

假設1：物資總庫和需求點均為點狀形式存在的離散點；

假設2：任意物資總庫和需求點的時間距離可通過調查或計算產生；

假設3：各物資總庫的容量無限制。

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

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

第一步：確定適應度函數及約束條件。本文采用的適應度函數為所提供的目標函數式（4），將待優化的函數在MATLAB界面點擊New Script，編寫函數式為相應的M文件形式。從而在GUI界面Fitness function處填寫@function name。

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

第三步：確定初始種群。遺傳算法是對群體進行的進化操作，需要準備一些表示起始搜索點的初始群體數據。本文將初始種群數設定為M=40。

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

第五步：終止條件。遺傳算法是一種反復迭代的隨機搜索方法，在每次迭代中，記下適應值最大的染色體，直到已經達到了算法規定的最大迭代次數或在規定的連續迭代次數內最好的染色體不再發生變化時算法終止。當算法終止時，最好的染色體即是該選址問題的最優解。本文設定最大迭代次數。

四、應用算例

沈陽市地鐵線路有40個需求點，現有的物資總庫數目為12個，各個物資總庫的建設及運營成本如表1所示。為整合倉儲資源，節約日常運營成本，合理優化倉儲網絡布局，對物資總庫數量進行削減。首先通過實地調研與考察，由于地鐵線路固定，任意兩地間的行駛時間變化不大，因此各個位置點的相關時間參數如表2所示。假定模型覆蓋時間半徑？茲=20（min）。圖1所示為優化前的需求點與物資總庫布局示意圖。（表1、表2、圖1）

由表3可知，優化后的物資總庫足以滿足現有需求點的調運方案，并由此會節約的成本為8，560萬元。（圖2）

五、總結

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

由于本文是在假設各服務設施點容量無限制的情況下，重點研究時間與成本因素對選址的影響，同時由算例的結論可以知道，某一需求點可由多個設施點為其提供服務，因此將來的拓展方向將是考慮在多目標同時影響的條件下通過多目標決策與其他啟發式算法等對物資總庫選址做進一步優化，并且對多設施點均可提供服務問題，做出優先級的排序，使其更符合現實需要，創造更大的應用價值。

主要參考文獻：

[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.