龍思，黃晴，郭權

(長沙理工大學 交通運輸工程學院，湖南 長沙 410114)

樞紐選址問題研究以運輸網絡為背景，運輸網絡由交錯的起始點與目的點連接組成，在這樣的系統(tǒng)中，OD間的直接運輸既不實際也沒有成本效應。針對樞紐選址問題，Sibel A.A.等對其研究方向進行了討論，包括P-Hub樞紐問題和含固定費用的樞紐選址問題；Puerto J.等在樞紐有容量約束的條件下研究單分配中值問題，通過預處理過程解決變量，并通過增加有效不等式組合來強化模型；Sibel A.A.等考慮不確定性因素進行樞紐選址，不確定性來源于樞紐建設成本和OD間流量需求兩方面；熊孝娟等對外界因素造成流量的不確定性進行建模，解決樞紐網絡在面對干擾時的調節(jié)能力問題；王達等建立基于乘客需求的綜合客運樞紐信息重要度模型，提高客運樞紐的服務水平；劉杰等分析交通樞紐客流量的變化特點，建立城市交通樞紐短期客流量組合預測模型；楊年等對容量分配下空鐵聯(lián)運網絡設計進行研究，優(yōu)化樞紐的運營能力；康凱等針對彈性需求下樞紐選址，考慮特定樞紐的隨機生效模式，從博弈論角度提出一種能實現平戰(zhàn)網絡性能權衡的樞紐選址策略?，F有研究只考慮OD間的流量需求不確定性，未考慮樞紐換乘系數對需求的影響；將單分配和多分配樞紐選址問題分別考慮，研究不具有針對性，各個角度的研究均不夠透徹；未對不確定性與確定性進行比較分析。為此，該文在OD需求不確定的情境下，提出無容量的P-Hub選址問題，流量不確定性以不確性集合形式表現，建立2種不確定規(guī)劃模型，將不確定轉化為相應的分布函數，在相應約束條件下分別使期望成本和α-成本最小，并用算例對模型進行驗證。

1 模型建立

1.1 問題描述

樞紐在運輸網絡中是從起點到終點進行流量收集和分配的設施，在運輸網絡中起到產生規(guī)模經濟的作用。P-Hub選址的目的是在運輸網絡中選P個樞紐，使OD上的流量經過這些樞紐的運輸費用最小。該文討論無容量限制的多分配P-Hub樞紐選址問題的魯棒性，非樞紐間不能直接鏈接。

在運輸網絡中，客流量集中到樞紐，通過樞紐間的集中運輸實現規(guī)模經濟。之前的研究中，各OD間的客流量已知，解決P-Hub樞紐選址問題的關鍵是處理需求不確定性。而現實生活中需求很大程度上會受到外界因素的影響。因此，在傳統(tǒng)P-Hub樞紐問題的基礎上考慮需求不確定性因素對運輸成本魯棒性進行分析。

1.2 模型假設

對模型作如下假設：1)運輸方式單一；2)運輸網絡規(guī)模較??；3)網絡中運輸車輛充足；4)不確定系數具有獨立性。

1.3 模型構建

為表示事件發(fā)生的置信度，引入不確定測度。

定義2(不確定變量)：一個不確定變量是從三元空間到實數集的可測函數，即對于任意實數的Borel集B，集合{ξ∈B}={γ∈Γ|ξ(γ)∈B}為一個事件。

定義5：不確定變量ξ的期望值由式(1)計算。

(1)

引理3：假設ξ1，ξ2，…,ξn分別是具有不確定性分布的自變量，Φ1，Φ2,…,Φn為其對應的分布函數，若f(x1,x2,…,xn)相對于x1,x2,…,xn嚴格單調遞增，則不確定變量的期望值ξ=f(ξ1,ξ2,…,ξn)可由式(2)計算。

(2)

例如：設a

當α=0.9時，Φ-1(0.9)=0.2b+0.8c，E[ξ]=(a+2b+c)/4。

1.4 不確定模型建立

由于P-Hub選址問題與P-median公式類似，也被稱為P-Hub中值問題。設有n個節(jié)點，每個節(jié)點都可以是出發(fā)點、目的地或潛在的樞紐選擇點。從n個節(jié)點中選擇P個樞紐，所有樞紐節(jié)點彼此連接。每個非樞紐節(jié)點完全連接到單個樞紐，2個非樞紐節(jié)點之間不直接連接。為便于描述，對參數進行設置，設i為節(jié)點，ξi為假定不確定變量的始發(fā)地i到目的地j的流量，cik為非樞紐節(jié)點i到樞紐節(jié)點k的單位運輸成本，fk為樞紐位于節(jié)點k時的建設固定成本，φ為樞紐間長途移動系數，λ為出發(fā)點i運輸到樞紐的成本系數，β為樞紐分配到目的地點的成本系數，取λ=β=1，僅考慮樞紐換乘系數的影響。P-Hub樞紐選址問題的決策變量為：

如果xkk的值為1，表示節(jié)點k被分配給自己，也就是說節(jié)點k實際上是一個樞紐節(jié)點。總成本由固定成本、將節(jié)點i連接到樞紐節(jié)點的成本、將目的地節(jié)點連接至樞紐節(jié)點的成本、樞紐之間連接成本組成，有：

總成本如下：

為便于分析，令

1.4.1 期望成本最小化模型

不確定變量的度量通常采用期望值，即不確定測度意義下的平均值。根據這一準則，具有不確定流的P-Hub樞紐選址問題的最小期望成本為：

(3)

式中：E為不確定變量的期望算子。

式(3)的約束中，第一個公式表示要求選擇精確的P個樞紐點，第二個公式表示確保每個節(jié)點被分配給一個且僅分配給一個樞紐，第三個公式表示標準完整性約束。

引理4：假設所有的ξij都是獨立的不確定變量，且不確定分布為Φij，可將式(3)轉化為等效模型(4)。

(4)

對于任意的i,j對，gij(x)≥0，設S={(i′,j′):gi′j′(x)>0}，則總成本為：

(5)

式(5)在(i′,j′)∈S內是關于ξi′j′的嚴格遞增函數，因為所有的ξij都是獨立的，ξi′j′也是獨立的，由引理3可得：

gij(x))dα

加上與Φij-1(α)gij(x)相對應的ξijgij(x)，gij(x)=0，可得：

在定理4的條件下，從引理2可得：

由于E[ξij]是所有i和j的一個精確期望值，模型(4)本質上是一個經典的無容量的P-hub樞紐選址模型，不存在不確定性。

1.4.2α-成本期望最小化模型

文獻[14]將機會約束規(guī)劃引入不確定決策系統(tǒng)建模中，文獻[15-16]討論了不確定條件的約束規(guī)劃的優(yōu)化。根據這一模型準則，建立在給定置信水平下使成本最小化即α-成本最小化模型(α-CMM)：

(6)

引理5：假設所有的ξij是具有規(guī)則不確定性分布的自變量Φij，可將α-CMM模型轉化為等效模型(7)。

(7)

根據不確定性分布的定義，有：

(8)

為了簡化，將X按照下式進行描述：

i,k=1,2,…,n}

如果ξij為某些特定類型的不確定分布，則有以下推論：

推論1：如果ξij=Ζ(aij,bij,dij)是Z的不確定變量，則模型(7)可寫成：

(0.5≤α≤1)

(0<α<0.5)

模型參數如下：Wij表示起點i到目的地點j的總需求量，即經過樞紐的總需求；xijkm表示由i到j經過樞紐k、m的流量。

2 算法設計

采用MATLAB編寫粒子群算法對模型進行求解。粒子群算法通過設計一種無質量的粒子來模擬鳥群中的鳥，粒子僅具有速度和位置兩個屬性，速度代表移動的快慢，位置代表移動的方向。每個粒子在搜索空間中單獨搜尋最優(yōu)解，將其記為當前個體極值，并將個體極值與整個粒子群里的其他粒子共享，找到最優(yōu)的那個個體極值作為整個粒子群的當前全局最優(yōu)解。粒子群中的所有粒子根據自己找到的當前個體極值和整個粒子群共享的當前全局最優(yōu)解來調整自己的速度和位置。

PSO初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。在每次迭代中，粒子通過跟蹤2個極值(pbest,gbest)來更新自己。在找到2個最優(yōu)值后，粒子通過下式更新自己的速度和位置：

vi=vi+c1×rand()×(pbesti-xi)+c2×

rand()×(gbesti-xi)

xi=xi+vi

vi=w×vi+c1×rand()×(pbesti-xi)+

c2×rand()×(gbesti-xi)

式中：i=1,2,…,N;N為群中粒子總數；vi為粒子速度，如果vi大于vi的最大值vmax(大于0)，則vi=vmax；rand()為介于(0,1)之間的隨機數；xi為粒子當前位置；c1和c2為學習因子，c1=1.5，c2=2.0；w為慣性因子，其值為非負，w=0.99。

3 算例分析

下面通過算例分析，檢驗上述模型的有效性。采用《從統(tǒng)計看民航2004》中的數據，考慮20個待選樞紐節(jié)點，每個節(jié)點的建設固定成本與GPS坐標定位見表1。假設節(jié)點之間運輸單位成本與節(jié)點間距離成比例，設cik=10×dik、cik=cki，即單位成本矩陣是對稱的。起點i與終點j之間的流量不確定，表2為待選樞紐節(jié)點之間的不確定需求流量，表3為待選節(jié)點之間需求流量期望值(由引理3計算得出)，即用期望成本最小化模型計算的期望值。如數據(45,48,50)表示從起點1到終點2的曲折不確定流量，48為最可能的流量，45為最小流量，50為最大流量。當然曲折不確定流量也可以是確定的數值，常數可看成特殊的曲折不確定流量，即服從Z(b,b,b)分布。表4為運用α-成本最小化模型計算得出的節(jié)點間需求流量期望值。

表1 部分城市的直角坐標值與樞紐固定成本值

表2 部分城市間的不確定需求流量 人次

表3 部分城市間的需求流量期望值 人次

表4 α=0.8時部分城市間的需求流量期望值 人次

節(jié)點之間的實際距離由下式計算：

化簡得d=Rarccos[cos(x1-x2)cosy1cosy2+siny1siny2]。其中A、B兩點的地理坐標分別為(x1,y1)、(x2,y2)，過A、B兩點的大圓的劣弧長即為兩點的實際距離。R=6 370 km為地球半徑。計算結果見表5、表6。

表5 ECMM模型的計算結果

表6 α-CMM模型的計算結果(ψ=0.8)

由表5、表6可知：對于期望成本最小化模型，樞紐換乘系數ψ增大時，期望成本增大；系數固定不變時，網絡總成本值隨著樞紐數量的增多而減少；P=4時，網絡總成本最小。對于α-成本最小化模型，樞紐數值一定時，成本值隨著成本置信水平α的增大而增大。如圖1、圖2所示，P=4、ψ=0.8與P=4、ψ=0.8、α=0.9所選的樞紐點是一致的，表明不確定模型具有穩(wěn)定性；P=4時，ψ=0.8與ψ=0.9的結果一致。而根據表6，除α=0.7和α=0.8外，其余置信水平狀態(tài)下所得樞紐皆為[3,9,11,12]，說明所建立的模型具有魯棒性。

圖1 P=4、ψ=0.8時的結果

圖2 P=4、ψ=0.8、α=0.9時的結果

采取的粒子群算法收斂速度快，迭代100次時已收斂(見圖3)。圖4、圖5為兩模型的運輸成本計算結果，圖6為不同樞紐數對應的運輸成本結果與標準模型結果的比較。

圖3 粒子群算法的收斂速度

圖4 期望成本模型樞紐-成本圖

圖5 α-成本模型樞紐-成本圖

圖6 需求不確定與需求確定的比較

4 結論

針對需求不確定的P-Hub選址問題，建立期望成本最小化模型與α-成本最小化模型，將不確定的需求流量轉換為不確定變量的期望值，并設計粒子群算法對模型進行求解。結論如下：

(1)滿足最優(yōu)解時，需求不確定性不會導致樞紐位置發(fā)生較大改變，即使改變，也是鄰近樞紐間的移動。

(2)樞紐位置的細微變化可削減需求不確定性對運輸成本的影響，并獲得成本節(jié)約。將運量需求不確定性因素考慮到運輸網絡中，相對于運量需求確定的情況更具有使用和研究價值。