基于集合覆蓋度的ULS各級節(jié)點選址問題

包 敏

(西南石油大學(xué) 理學(xué)院，四川 成都 610500)

地下物流系統(tǒng)(ULS)是城市內(nèi)部及城市間的貨物高效運輸?shù)男滦拖到y(tǒng)[1]，它不僅能夠減輕城市環(huán)境污染，而且能夠緩解交通擁堵問題. 而交通擁堵是世界大城市目前遇到的“困局”之一，因此統(tǒng)籌規(guī)劃地下物流系統(tǒng)受到越來越多的發(fā)達(dá)國家的重視[2]. 構(gòu)建地下物流系統(tǒng)的實質(zhì)是構(gòu)建地下物流網(wǎng)絡(luò)，其中地下物流網(wǎng)絡(luò)是由一級、二級節(jié)點和節(jié)點間地下通道構(gòu)成. 各級物流節(jié)點是整個地下物流網(wǎng)絡(luò)的關(guān)鍵，其數(shù)量和位置決定了整個物流網(wǎng)絡(luò)的格局和規(guī)模[3]，直接影響了物流系統(tǒng)的建設(shè)成本和緩解交通擁堵的能力. 因此研究各級物流節(jié)點的數(shù)量和位置具有極大的現(xiàn)實意義.

李利華等[4]根據(jù)物流網(wǎng)絡(luò)具有需求不確定性，建立了以重心法為核心的物流網(wǎng)絡(luò)區(qū)間節(jié)點決策模型. 施宏偉等[5]綜合考慮物流節(jié)點服務(wù)空間屬性和成本約束，構(gòu)建了物流節(jié)點布局優(yōu)化模型. 閆文濤等[6-7]基于雙層規(guī)劃模型研究地下物流的選址問題. 姜光陽等[8]在節(jié)點候選集確定的條件下，分析了基于集合覆蓋度模型的城市地下物流系統(tǒng)的物流節(jié)點選址. 此時有一個重要的前提是物流節(jié)點個數(shù)確定和不考慮節(jié)點級數(shù). 但是在實際問題中，設(shè)計地下物流系統(tǒng)網(wǎng)絡(luò)時，各級物流節(jié)點數(shù)往往是不確定的，并且地下物流系統(tǒng)具有造價高、風(fēng)險大及改建困難等特點. 這為借助地面交通網(wǎng)絡(luò)劃分法研究基于集合覆蓋度的地下物流系統(tǒng)各級節(jié)點選址問題提供了技術(shù)路線.

在本文中，首先設(shè)計了地面交通貨運的網(wǎng)絡(luò)加權(quán)有向圖，然后基于地區(qū)網(wǎng)格劃分法確定地下物流系統(tǒng)的節(jié)點候選集，不同區(qū)域地面交通狀況不同，對應(yīng)的地面網(wǎng)絡(luò)圖不同，從而對應(yīng)的節(jié)點候選集不同；其次，構(gòu)建基于集合覆蓋的地下物流各級節(jié)點選址模型，并設(shè)計主目標(biāo)法解決這一節(jié)點選址問題；最后，對南京市仙林地區(qū)的ULS的建設(shè)，進(jìn)行數(shù)值實例分析，驗證所該選址模型的合理性.

1 構(gòu)建地面交通貨運的網(wǎng)絡(luò)加權(quán)有向圖

在對建設(shè)地下物流系統(tǒng)進(jìn)行頂層設(shè)計時，必須考慮地面路況. 于是構(gòu)建地面交通貨運網(wǎng)絡(luò)加權(quán)有向圖G=(V,E,W). 其頂點集V包括物流園區(qū)和各區(qū)域中心，邊集E是指各頂點間連線集，把各頂點對應(yīng)的區(qū)域面積s、交通擁堵指數(shù)T作為頂點的權(quán)值；將頂點間的邊上的距離d和貨運流量Od作為邊的權(quán)值. 地面交通貨運網(wǎng)絡(luò)加權(quán)有向圖如圖1所示.

2 基于地區(qū)網(wǎng)格劃分法確定地下物流系統(tǒng)的節(jié)點候選集

由于物流節(jié)點群需要服務(wù)整個交通貨運地區(qū)，設(shè)各節(jié)點服務(wù)半徑是在rkm范圍以內(nèi)自由選擇，若部分區(qū)域面積大于πr2km2(即半徑大于rkm)，此時節(jié)點選在區(qū)域中心并不一定能完全滿足整體服務(wù)，需優(yōu)先尋找候選節(jié)點位置，確定節(jié)點候選集.

圖1 地面交通貨運網(wǎng)絡(luò)加權(quán)有向圖

圖2 地區(qū)網(wǎng)格劃分示意圖

3 構(gòu)建基于集合覆蓋度的地下物流各級節(jié)點選址模型

3.1 地下物流網(wǎng)絡(luò)節(jié)點選址模型

所謂集合覆蓋模型就是對于已知的一些需求點，設(shè)立相應(yīng)的目標(biāo)函數(shù)以及約束條件，確定一組特定的物流節(jié)點來滿足需求點的需求量，具體地說就是確定物流節(jié)點的最少數(shù)量和最合適的位置[9]. 而要保證物流節(jié)點選取位置最合理，需要尋求緩解交通擁堵能力越大、物流成本最低的節(jié)點個數(shù)及位置. 根據(jù)網(wǎng)格劃后的貨運網(wǎng)絡(luò)加權(quán)圖確定的節(jié)點候選集，建立地下物流選址模型.

3.1.1 決策變量的確定

要尋找最合適的物流節(jié)點選址，只需考慮在節(jié)點候選集中選取合適節(jié)點，滿足緩解交通擁堵以及節(jié)點服務(wù)覆蓋整個區(qū)域的要求即可. 因此將決策變量確定為0～1變量xj和yij.xj=1表示在候選節(jié)點j建立地下物流節(jié)點，xj=0表示不在候選節(jié)點j建立地下物流節(jié)點；yij=1表示區(qū)域i被節(jié)點j服務(wù)，yij=0表示區(qū)域i不被節(jié)點j服務(wù). 其中候選節(jié)點j∈M={1,2,…,n}，n為節(jié)點候選集的節(jié)點總數(shù)，服務(wù)區(qū)域包括n1個物流園區(qū)和n2個貨運區(qū)域，則區(qū)域i∈M0={1,2,…,n0},n0為區(qū)域總個數(shù)，即n0=n1+n2.

3.1.2 目標(biāo)函數(shù)的確定

由于地下物流系統(tǒng)作用是減輕交通壓力、降低貨物物流成本以及提高物流作業(yè)效率，因此緩解交通擁堵能力、建設(shè)成本、運貨效率以及服務(wù)面積4個方面考慮進(jìn)行節(jié)點選取，故目標(biāo)函數(shù)確定為以下5個.

目標(biāo)函數(shù)一：物流節(jié)點數(shù)最少

由于物流節(jié)點數(shù)量越少，建設(shè)成本越低，于是目標(biāo)函數(shù)一為：

(1)

其中M為物流節(jié)點候選集，因此j∈M.

目標(biāo)函數(shù)二：物流節(jié)點群緩解交通擁堵能力最大

由于物流節(jié)點群緩解交通擁堵的能力等于各個節(jié)點改善服務(wù)區(qū)域的擁堵程度之和，于是將區(qū)域按照各節(jié)點服務(wù)范圍進(jìn)行劃分，利用各節(jié)點的擁堵系數(shù)與區(qū)域的平均擁堵系數(shù)偏差刻畫各節(jié)點改善交通擁堵程度. 于是目標(biāo)函數(shù)二為：

(2)

其中Ti為區(qū)域i的交通擁堵系數(shù).

目標(biāo)函數(shù)三：物流成本最少

利用各節(jié)點與服務(wù)區(qū)域的距離刻畫物流成本. 于是目標(biāo)函數(shù)三為：

(3)

其中dij為節(jié)點j與區(qū)域i的距離.

目標(biāo)函數(shù)四：物流節(jié)點轉(zhuǎn)運率最低

由于在滿足運輸要求的前提下，保證轉(zhuǎn)運率最低，節(jié)點選址才最合理. 而各節(jié)點轉(zhuǎn)運率是指節(jié)點出貨量與其他節(jié)點總出貨量的比值，因此目標(biāo)函數(shù)四為：

(4)

其中Odj表示節(jié)點j的出貨量，Odj0表示節(jié)點j0的出貨量，j,j0∈M.

目標(biāo)函數(shù)五：節(jié)點覆蓋面積均勻化程度最好

利用各節(jié)點服務(wù)面積與候選節(jié)點均分區(qū)域面積的偏差平方刻畫節(jié)點覆蓋面積均勻化程度，因此目標(biāo)函數(shù)五為：

(5)

其中si為區(qū)域i的面積.

3.1.3 約束條件的確定

由于地下物流系統(tǒng)網(wǎng)絡(luò)節(jié)點服務(wù)范圍以及節(jié)點運行總量有嚴(yán)格的標(biāo)準(zhǔn)，因此將約束條件確定為以下5個.

約束條件一：物流節(jié)點的范圍半徑限制

為了保證物流作業(yè)效率，每個節(jié)點在所服務(wù)區(qū)域的服務(wù)范圍是以節(jié)點為中心，半徑為rkm的圓域，于是對每個物流節(jié)點服務(wù)區(qū)域滿足：

dijryij,i∈M0,j∈M

(6)

約束條件二：區(qū)域被服務(wù)節(jié)點數(shù)量限制

被網(wǎng)格劃后的各區(qū)域只需被一個節(jié)點服務(wù)，于是得到約束條件二：

(7)

約束條件三：物流節(jié)點貨運總量限制

由于一級節(jié)點從地面收發(fā)貨物總量上限為N1t，二級節(jié)點從地面收發(fā)貨物總量上限為N2t，故物流節(jié)點的貨運總量上限為N1t，于是約束條件三為：

(8)

約束條件四：區(qū)域服務(wù)限制

由于區(qū)域只有在節(jié)點建設(shè)的條件下，才有可能被服務(wù)，因此可得到約束條件四：

(9)

為了簡化計算，將上述約束轉(zhuǎn)化為yijxj,i∈M0,j∈M.

約束條件五：0～1約束

決策變量xj和yij只能取0或1，因此得到約束條件五：

xj∈{0,1},yij∈{0,1}

(10)

通過此模型可以得到地下物流網(wǎng)絡(luò)的節(jié)點總數(shù)和各節(jié)點的位置、服務(wù)范圍以及運轉(zhuǎn)率. 但由于對上式計算非常復(fù)雜，于是采用主目標(biāo)法，簡化上式模型.

3.1.4 基于主目標(biāo)法簡化多目標(biāo)優(yōu)化模型

由于要求地下物流網(wǎng)絡(luò)以緩解交通擁堵和降低物流成本為直接目標(biāo)，而這兩個目標(biāo)都是由物流節(jié)點數(shù)確定，節(jié)點數(shù)越少物流成本越低，節(jié)點數(shù)越多緩解交通擁堵能力越好，因此可將降低物流成本確定為主要目標(biāo). 因此將物流節(jié)點數(shù)最少作為主目標(biāo)，其余四個目標(biāo)轉(zhuǎn)化為約束條件，其中各個約束值由對應(yīng)目標(biāo)的期望值確定，則有：

(11)

3.2 確定節(jié)點的等級

由上可得最優(yōu)的物流節(jié)點總數(shù)以及各節(jié)點位置，因此只需在此基礎(chǔ)上區(qū)分節(jié)點群中各節(jié)點的等級. 由于一級節(jié)點從地面收發(fā)貨物總量上限為N1t，二級節(jié)點從地面收發(fā)貨物總量上限為N2t，于是各節(jié)點級數(shù)為：

(12)

綜上所述便可得各級節(jié)點的數(shù)量、位置、服務(wù)范圍以及實際貨運量和一級節(jié)點的轉(zhuǎn)運率.

3.3 基于Floy算法和主目標(biāo)法求解ULS的節(jié)點選址問題

本文基于區(qū)域面積和貨運流量等信息，首先構(gòu)建交通貨運網(wǎng)絡(luò)加權(quán)有向圖；然后根據(jù)節(jié)點服務(wù)范圍將該地區(qū)進(jìn)行網(wǎng)格劃分，確定物流節(jié)點候選集，并采用元胞數(shù)組存儲候選集節(jié)點距各區(qū)域中心點的距離矩陣和流量矩陣；其次以是否作為節(jié)點和是否歸屬該節(jié)點為決策變量，以物流節(jié)點數(shù)最少、緩解交通擁堵能力最大、物流成本最低、轉(zhuǎn)運率最低、覆蓋面積最均衡為目標(biāo)，建立基于集合覆蓋的地下物流網(wǎng)絡(luò)節(jié)點的選址模型，并根據(jù)多目標(biāo)優(yōu)化算法，選用主目標(biāo)法對選址模型進(jìn)行求解[10-11]；最后，基于最優(yōu)節(jié)點選址結(jié)果，從而確定各級節(jié)點個數(shù)及位置、實際貨運量以及服務(wù)范圍和一級節(jié)點的轉(zhuǎn)運率. 算法具體步驟如下：

Step1 獲取交通貨運區(qū)域劃分圖和圖數(shù)據(jù)，其中圖數(shù)據(jù)包括各區(qū)域中心點坐標(biāo)(ci,di)、各區(qū)域面積si、交通擁堵指數(shù)Ti和相應(yīng)的貨運流量矩陣Od，i∈M0；

Step3 計算各區(qū)域中心坐標(biāo)與候選節(jié)點間的最短距離，采用Floyd算法得到最短路徑矩陣；

Step4 基于建立的多目標(biāo)采用主目標(biāo)法將本文的多目標(biāo)優(yōu)化模型轉(zhuǎn)化為以節(jié)點個數(shù)最少為單一主目標(biāo)的優(yōu)化模型公式(11)，利用LINGO軟件對模型進(jìn)行求解，確定出各一、二級節(jié)點位置；

Step5 統(tǒng)計各一、二級節(jié)點的個數(shù)及其對應(yīng)位置，并對節(jié)點位置進(jìn)行編號；統(tǒng)計各一、二級節(jié)點的實際輸入、輸出的貨運量；采用元胞數(shù)組存儲一、二級節(jié)點所服務(wù)的區(qū)域；

Step6 計算物流園區(qū)與最近一級節(jié)點間的貨物轉(zhuǎn)運率；

Step7 統(tǒng)計并存儲各級節(jié)點個數(shù)及位置、實際貨運量、服務(wù)范圍、一級節(jié)點轉(zhuǎn)運率；

Step8 結(jié)束.

其算法流程圖如圖3所示.

4 應(yīng)用實例

用本文提出的研究地下物流系統(tǒng)物流網(wǎng)絡(luò)節(jié)點選址方法，為中國南京市的仙林地區(qū)規(guī)劃最佳的網(wǎng)絡(luò)路線時序，數(shù)據(jù)來源于第十四屆研究生數(shù)學(xué)建模競賽F賽題的附件.

通過構(gòu)建的交通貨運網(wǎng)絡(luò)加權(quán)有向圖、基于地區(qū)網(wǎng)格劃分法確定地下物流系統(tǒng)的節(jié)點候選集、基于集合覆蓋的地下物流各節(jié)點選址模型以及設(shè)計的Floyd算法和主目標(biāo)法，采用Matlab軟件和Lingo軟件編程求解獲得了13個一級節(jié)點和32個二級節(jié)點的位置(見表1、表2、圖4)、服務(wù)范圍、實際運貨量以及一級節(jié)點的轉(zhuǎn)運率.

圖3 物流節(jié)點選址算法流程圖

編號節(jié)點位置X節(jié)點位置Y貨物流出貨物流入轉(zhuǎn)運率/%服務(wù)區(qū)域編號2148 037.4149 443.91 544.0861 528.1841.574914145 146.8151 489.611 698.7111 064.5511.4006、8、10、19、3224140 416.6152 146.114 112.5614 103.5414.5313、20、23、29、3336149 366.9153 648.19 541.8569 226.7449.5064744144 403.3155 93010 114.6512 104.6212.47138、8067137 889.7157 781.78 299.68 540.798.79962、68、7276141 629.7160 163.76 707.1575 996.626.17869、70、74、7986148 375.7159 294.37 146.0256 914.6147.12481、90、9489150 413.2159 364.710 813.939 715.01210.00949、84、100101155 477.4162 651.16 601.2675 761.775.93696104158 487.3164 413.46 442.0075 625.6195.796103、108106169 251.1165 333.2153.939252.7690.260109163 428166 293.46 622.3736 225.3336.414110

圖4 各級物流節(jié)點分布示意圖

從圖4可以看出，二級節(jié)點個數(shù)遠(yuǎn)多于一級節(jié)點個數(shù)，并且二級節(jié)點均勻分布在一級節(jié)點附近.

5 結(jié)論

針對地下物流系統(tǒng)這一高效運輸系統(tǒng)，ULS網(wǎng)絡(luò)的物流各級節(jié)點的選址是地下物流系統(tǒng)必不可少的關(guān)鍵步驟. 在研究ULS的各級節(jié)點選址時，可以考慮圖論、最優(yōu)化理論、集合覆蓋度、選址模型以及Floyd算法和主目標(biāo)算法等理論與方法. 在已知地面貨運交通信息后，首先，構(gòu)造地面交通貨運網(wǎng)絡(luò)加權(quán)有向圖，依據(jù)網(wǎng)格劃分法確定地下物流系統(tǒng)的節(jié)點候選集，然后構(gòu)建基于集合覆蓋度的最優(yōu)化選址模型，獲取地下物流各節(jié)點總個數(shù)及其位置；最后設(shè)計基于Floyd算法和主目標(biāo)算法的最優(yōu)選址算法,解決了ULS節(jié)點選址的頂層設(shè)計問題. 為中國南京市仙林地區(qū)的ULS網(wǎng)絡(luò)節(jié)點選址提供方法，其實例研究表明所提出的研究思想和方法是正確可行的，建立選址模型及設(shè)計的求解算法對于解決地下物流系統(tǒng)的網(wǎng)絡(luò)節(jié)點選址是合理的.

表2 二級節(jié)點(32個)相關(guān)數(shù)據(jù)表