基于網(wǎng)絡連接及服務中心選擇的高鐵路網(wǎng)區(qū)域劃分方法

張強鋒, 王恪銘, 倪少權，呂紅霞

(1.西南交通大學 交通運輸與物流學院，四川 成都 610031；2.西南交通大學 信息科學與技術學院，四川 峨眉山 614202)

近年來我國高鐵線網(wǎng)規(guī)模躍居世界第一，全國性的高鐵路網(wǎng)日益完善，區(qū)域內高鐵線路的網(wǎng)絡化正在形成。在高鐵客運需求大幅增長、部分高鐵線路運力緊張趨勢加劇的背景下，我國高鐵運輸產(chǎn)品有了在區(qū)域內公交化開行、跨區(qū)域范圍提升直達旅行比例及換乘便捷程度等更高的設計要求。隨著改革縱深的推進，區(qū)域鐵路公司的市場主體地位進一步確定。為了適應高鐵的特點和鐵路的發(fā)展，亟待進行高鐵最佳管轄區(qū)域的研究，以編制出符合區(qū)域協(xié)同優(yōu)化要求的高鐵運行圖，增強區(qū)域性鐵路公司的經(jīng)營自主性，滿足新時代我國高鐵運輸?shù)陌l(fā)展變化要求，而合理地進行高鐵路網(wǎng)的區(qū)域劃分是解決這一難題的基礎。

目前已有不少學者進行了運輸區(qū)域劃分相關問題的研究。袁長偉等[1]的研究中關注了公路運輸區(qū)域的等級劃分問題，而路網(wǎng)區(qū)域劃分問題需要進一步考慮路網(wǎng)的連接性；劉偉銘 等[2]使用聚類分析方法對高速公路最佳運營區(qū)域劃分問題進行了研究，且考慮了區(qū)域連接性的指標；在鐵路區(qū)域的劃分問題中，PITTMAN[3]研究了中國貨運鐵路劃分的風險規(guī)避問題；KOPICKI與THOMPSON等[4]，NILSSON[5]，MIZUTANI與NAKAMURA[6]，PITTMAN[7]從政策與財務的角度，研究了鐵路公司的劃分與重組問題；莫輝輝與王姣娥[8]基于功能區(qū)的網(wǎng)絡分析方法研究了中國貨物路網(wǎng)區(qū)域的劃分問題，但缺少定量的劃分決策模型；孫有霞[9]使用聚類方法對中國鐵路區(qū)域進行了劃分，由于聚類劃分方法只適合于分類問題，無法保證同一劃分區(qū)域的連接性，需要事后對分類結果進行調整。目前對運輸區(qū)域劃分問題的研究仍較少，且存在未考慮區(qū)域中心的選擇及路網(wǎng)區(qū)域的連接性、忽略最佳服務距離及網(wǎng)絡均衡性等缺陷，缺少可以進行定量決策的模型化研究成果。

本文針對以上研究現(xiàn)狀，基于高鐵區(qū)域內的路網(wǎng)連結特性與區(qū)域中心點的特征，并體現(xiàn)高鐵區(qū)域劃分依據(jù)的約束要求，以區(qū)域內路網(wǎng)節(jié)點與服務中心的距離及連接緊密度為目標，以服務半徑、服務容量約束劃分后的子區(qū)域規(guī)模，建立了高鐵區(qū)域路網(wǎng)劃分決策優(yōu)化模型?；诙嗄繕宿D化方法，設計了一種向量編碼的遺傳算法進行求解。最后，以中國鐵路總公司管轄路網(wǎng)區(qū)域構建算例進行計算，提出了高鐵轉運量折算方法，通過對比聚類算法的缺陷，說明了本文模型與算法的適應性與靈活性，并分析目標權重系數(shù)、服務半徑系數(shù)、服務容量系數(shù)等參數(shù)對劃分結果的影響，測試得出了服務半徑系數(shù)、服務容量系數(shù)的設定方法。

1 問題描述

1.1 高鐵區(qū)域路網(wǎng)劃分因素

在高鐵區(qū)域路網(wǎng)劃分問題中，不能將區(qū)域的重心直接確定為區(qū)域路網(wǎng)內的中心點。為滿足區(qū)域內與區(qū)域間的動車開行需要，區(qū)域路網(wǎng)內的中心點除了具有較強的動車儲備與檢修能力，還應與區(qū)域內各個地區(qū)(節(jié)點)連接距離較短，并與各個節(jié)點有較好的連通性，且區(qū)域劃分范圍應考慮高鐵最佳管理距離的要求。此外，為了保持各個子區(qū)域服務能力的均衡性，應對子區(qū)域的最大服務能力進行約束；且為了突出各個子區(qū)域內部的網(wǎng)絡特性，區(qū)域內的各個地區(qū)(節(jié)點)之間應具有較好的連接度?？梢?，在考慮以上約束的前提下，需要決策的問題有：哪些最小地區(qū)單元同屬一個子區(qū)域；劃分后的子區(qū)域中，選擇哪個地區(qū)的路網(wǎng)中心作為該子區(qū)域的服務中心。

1.2 模型假設

建模之前，為清晰描述，做如下假設。

(1) 區(qū)域劃分的數(shù)量由決策者根據(jù)相關發(fā)展規(guī)劃給定。在網(wǎng)絡圖中，最小劃分單元用該單元的網(wǎng)絡中心點表示。

(2) 劃分后的區(qū)域路網(wǎng)服務中心應在動車儲備與檢修能力最強的最小地區(qū)單元。采用動車所的檢查庫線與存車線數(shù)量之和代表動車儲備與檢修能力。

(3) 通過區(qū)域服務半徑與服務容量約束限制區(qū)域劃分規(guī)模。即區(qū)域服務中心與區(qū)域內各單元中心點之間的距離應滿足最大服務半徑的要求，劃分后區(qū)域的服務容量之和不高于服務容量約束。用區(qū)域內的高鐵客運總周轉量表示其服務容量。

(4) 除區(qū)域服務中心與同一區(qū)域各個地區(qū)路網(wǎng)中心節(jié)點之間的距離之和越小這一指標外，另采用區(qū)域內各節(jié)點之間高鐵線路連接的數(shù)量之和與區(qū)域內的節(jié)點總數(shù)之比表示該區(qū)域的網(wǎng)絡連通度，該值越大表示區(qū)域內的網(wǎng)絡連接程度越好。

2 決策優(yōu)化模型

2.1 符號說明

1)參數(shù)

G=G(V,E)為整個路網(wǎng)的集合，其中V為路網(wǎng)中節(jié)點(最小劃分單元的網(wǎng)絡中心點)的集合，V={v1,v2,…，vn}；E為節(jié)點之間的高鐵線路，即路網(wǎng)中的邊，E={eij|i=1,2,…n;j=1,2,…n}，其中n為節(jié)點總數(shù)。

rij：節(jié)點vi與vj之間的高鐵線路連接數(shù)量，即邊的數(shù)量，rij=|∑eij|， ?i,j∈V。

Dij：vi與vj之間的距離，?i,j∈V。

xi,yi：vi的橫、縱坐標，?i∈V。

Ui：vi所轄區(qū)域的動車儲備與檢修能力，?i∈V。

Pi：vi所轄區(qū)域的年高鐵客運總周轉量，?i∈V。

Dv：鐵路平均運距。

2)中間變量

3)決策變量

aik：0-1變量，vi屬于子圖(區(qū)域)k時aik為1，否則為0，?i∈V,k∈K。

hik：0-1變量，vi為子圖(區(qū)域)k的中心節(jié)點時hik為1，否則為0，?i∈V,k∈K。

2.2 模型建立

(1)

(2)

s.t.

(3)

(4)

(5)

?j∈Vdk},?k∈K

(6)

(7)

(8)

(9)

Dij=fun(xi,yi,xj,yj),?i,j∈V

(10)

aik,cik∈{0,1}, ?i∈V,k∈K

(11)

目標函數(shù)中：式(1)是使各個子區(qū)域內中心點距離其他點之和最小化，式(2)是使各區(qū)域內的網(wǎng)絡連通度之和最大化。約束條件中：式(3)是子區(qū)域中心點的定義，式(4)為子區(qū)域中心點決策變量約束，式(5)為子圖各節(jié)點的集合，式(6)表示子圖中動車儲備與檢修能力最強的節(jié)點，式(7)為1個節(jié)點只能屬于1個子圖的約束，式(8)為子圖中心點的服務半徑約束，式(9)為子圖中心點的服務容量約束，式(10)為兩節(jié)點之間距離函數(shù)的表達式，式(11)為決策變量的值域約束。

3 模型求解

3.1 多目標轉化

上述模型是一個多目標優(yōu)化問題，引進目標值權重系數(shù)ω1，ω2，且ω1+ω2=1，將上述模型轉化成單目標問題模型，即

(12)

3.2 向量編碼遺傳優(yōu)化算法

上述模型是一個混合整數(shù)規(guī)劃模型，屬于NP-hard問題。為此，文中設計了一種遺傳算法進行求解。針對研究問題的特點，算法編碼采用了向量的形式[10]，即直接以編碼中的各基因值(Allele值)對應相應的路網(wǎng)節(jié)點編號，采用編碼中前段|K|個基因代表候選區(qū)域中心點，即字串1，剩余編碼為字串2，即各個候選節(jié)點。此向量方式的編碼與解碼過程較為簡捷，但編碼長度增加，交叉、變異時的處理時間相應增長，運算時占用更多的存儲空間，但相對于目前大容量的計算機內存及較快的處理速度可忽略不計，不失為解決本文特定問題的一種有效方法。

編碼與解碼示意圖如圖1所示。其中，可行解的產(chǎn)生過程如下：通過計算各個候選節(jié)點與各個候選中心點的區(qū)域松散值，即按式(12)計算兩點之間距離與連通度對應的目標函數(shù)值，根據(jù)計算結果進行排序，分配各個候選節(jié)點至與其有最小區(qū)域松散值的候選中心點；按區(qū)域內各點的Ui值調整得出新的中心點；按最大服務半徑約束檢查區(qū)域內各個節(jié)點，通過對超出約束的節(jié)點至其他中心點的區(qū)域松散值從小到大排序，確定候選接收區(qū)域順序，將超出約束的節(jié)點調整至候選接收區(qū)域接納后，仍可滿足服務半徑與服務容量約束的候選接收區(qū)域中；按最大服務容量約束檢查各個區(qū)域，在不滿足容量的區(qū)域內，將與其他節(jié)點聚合性最差的節(jié)點依次標記為超出約束節(jié)點，按上述超出距離約束節(jié)點的調整方法，將這些節(jié)點調整至合適區(qū)域中，直到該區(qū)域的容量約束得到滿足為止。模型求解過程如下。

Step 1：令遺傳進化代數(shù)g=0，設置最大進化代數(shù)gm。根據(jù)向量編碼規(guī)則，按元素編號生成q個初始種群。

Step 2：按解碼規(guī)則遍歷當前種群每條染色體l的基因位，計算得出各個中心點所屬的各節(jié)點，按距離與容量約束調整各個子區(qū)域大小，并重新計算調整得出中心點，形成可行的區(qū)域劃分方案。

Step 3：計算每條染色體l的適應度函數(shù)值F(l)=(1 000/Z(l))2，Z(l)為第l條染色體的目標值，按式(12)計算，l=1,2,…,q。

圖1 編碼與解碼示意圖

Step 4：使用輪盤賭策略選擇染色體，進行遺傳進化操作，生成臨時種群。

對各條染色體進行交叉、變異操作：按交叉率Pc進行單點交叉與部分匹配交叉，按變異率Pm進行逆轉變異。

Step 5：采用精英保留策略從當前種群中選擇部分染色體，結合臨時種群生成下一代的種群。

Step 6：若g≤gm，g=g+1，轉至Step 2；否則，以進化過程中求得到的具有最大適應度個體所對應的區(qū)域劃分方案為最優(yōu)方案。

4 算例分析

4.1 算例構建

(13)

(14)

表1 各地區(qū)的分析統(tǒng)計數(shù)據(jù)

表2 各地區(qū)之間的高鐵路網(wǎng)連通度

其他參數(shù)設置如下：gm=1 000，Pc=0.7，Pm=0.7，q=100。取ω1=0.5，ω2=0.5，|K|=7。其中，2017統(tǒng)計年鑒得出的鐵路平均運距Dv為447 km，另外取α=2，β=2。采用Matlab R2017a編程實現(xiàn)上述算法，在inter CORE i7+7700CPU，16G內存的微機上對測試算例進行了求解，計算時間約為160 s，目標函數(shù)值的收斂情況如圖2所示。

圖2 目標函數(shù)值的收斂情況

表3為本文模型算法的劃分方案，其中“★”為中心點。本文研究中同時使用聚類算法進行的一系列測試計算發(fā)現(xiàn)：層次聚類算法的結果依賴于之前層次的劃分方案，無法證實當前層次劃分結果為最優(yōu)解；K均值聚類算法的結果對初始中心值的選擇非常敏感[12]，導致各次計算結果不一致，得到最優(yōu)解有一定的隨機性，算法的穩(wěn)定性差。這些聚類算法只能輸入相互獨立的指標參數(shù)，適用于常規(guī)的分類問題。該類算法無法處理網(wǎng)絡相關問題，輸入多個指標進行聚類的結果沒有網(wǎng)絡連接性，得不出可行解，且該算法缺少調節(jié)性參數(shù)。本文模型算法解決了一個比分類問題的復雜度更高的網(wǎng)絡劃分問題，且通過改變參數(shù)(如服務半徑與容量約束、目標函數(shù)權重等)，該模型算法可以得到更多適應性的劃分方案，體現(xiàn)了較好的靈活性。

表3 基于路網(wǎng)連接及中心點選擇的劃分結果

表4為僅輸入距離參數(shù)的|K|均值聚類算法得出的劃分方案，其中各區(qū)域的中心為該區(qū)域的重心。對比表3分析如下。

(1) 路網(wǎng)鄰域連接影響了區(qū)域劃分結果。在表4僅考慮距離這一個目標的劃分方案中，區(qū)域中心是該區(qū)域的重心，各節(jié)點與該中心點團簇構成各個子區(qū)域。為了最小化區(qū)域內距離，表4中貴州與四川為一個區(qū)域，而在表3中綜合考慮了路網(wǎng)鄰域連接(貴廣高鐵)，貴州與廣東劃分在同一區(qū)域。同理，因為路網(wǎng)的連接性(鄭西高鐵)，陜西也與河南劃分在同一區(qū)域中。

(2) 中心點的選擇也對區(qū)域劃分造成了影響。在表3中，中心點的選擇與動車儲備與檢修能力相關，如因有較強的動車服務能力，在子區(qū)域靠外圍位置的北京、上海被調整為區(qū)域的中心點。

(3) 最大服務半徑與服務容量約束影響劃分結果。由于服務容量的約束，對比表4發(fā)現(xiàn)，表3中北京、上海兩節(jié)點所在的區(qū)域范圍減小。在表3中，湖北與中心點陜西的距離最近，其次是上海。若湖北被劃入陜西的省會為中心的所在區(qū)域，由于湖北的動車儲備與檢修能力較大，湖北的省會會被調整成為該區(qū)域的中心，增大了目標函數(shù)值，且造成湖北的省會與青海的省會兩點之間不滿足服務半徑約束；由于容量約束的限制，湖北也不會被劃分到上海所在區(qū)域中，而是被劃入與其連接度較好的中心點為廣東省會所在的區(qū)域中。

表4僅輸入距離參數(shù)的劃分結果(|K|均值聚類算法)

區(qū)域編號區(qū)域所轄的地區(qū)1黑龍江,吉林,遼寧2內蒙古,山西,河北,河南,山東,天津,北京3湖北,湖南,江蘇,安徽,江西,福建,浙江,上海4廣西,海南,廣東5云南,重慶,貴州,四川6青海,甘肅,陜西7新疆

4.2 參數(shù)敏感性分析

通過式(12)對各個目標函數(shù)的權重系數(shù)進行設置，可以得出更多體現(xiàn)決策偏好的參考劃分方案。當設置距離權重系數(shù)ω1與區(qū)域內連接度權重系數(shù)ω2均為0.5時，最優(yōu)目標函數(shù)值約等于0。當ω1=0.59，ω2=0.41時，計算得出的最優(yōu)劃分方案對比表3產(chǎn)生的變化為：貴州被劃入距離其較近的中心節(jié)點為四川的省會所在的區(qū)域中。當ω1=1.0，ω2=0時，該模型將退化成一個帶服務半徑與服務容量約束的最小化區(qū)域內連接距離的單目標模型，青海、甘肅與云南、重慶都被劃入了以四川的省會為中心點的區(qū)域中，陜西、河南、湖南、江西劃入以湖北的省會為中心的區(qū)域中，區(qū)域內部的連通性均下降。當ω1=0.7，ω2=0.3時得出的計算結果仍與表3相同。而當ω1=0，ω2=1.0時，該模型將退化成一個最大化區(qū)域內連接度的單目標模型，計算得出的區(qū)域劃分方案中，由于路網(wǎng)的疏密程度導致求解方案中的以北京、上海、廣東的省會為中心的區(qū)域劃分過大，各子區(qū)域之間的均衡性下降。該測試結果說明：目標函數(shù)的權重系數(shù)選取需要體現(xiàn)決策偏好，應綜合距離與連接度指標，設置適當目標權重，以得出合理劃分方案。

模型中通過設置最大服務半徑與最大服務容量約束以調節(jié)劃分方案中各個區(qū)域的均衡性，可見這兩個約束的設定值會影響劃分結果。保持其他參數(shù)與表3相同，改變半徑系數(shù)α、容量系數(shù)β的值，測試得出不同約束條件下子區(qū)域的最大節(jié)點數(shù)量及最優(yōu)目標函數(shù)的變化，如表5所示。“/”表示無解或無對比，α=1時，無法計算得出1～7個子區(qū)域的劃分方案，當取β=1時也無法得出劃分方案。以表中α=3，β=4時的值“7，-，↓”為例，表示此時得出的最優(yōu)方案中，子區(qū)域包含的最大節(jié)點為7個，目標函數(shù)值與左前表格中即α=3，β=3時的值對比沒有變化，但與上前方表格即α=2，β=4時的值對比減小。

表5 不同約束條件下子區(qū)域的最大節(jié)點數(shù)量及目標函數(shù)值的變化

表6 不同劃分數(shù)量下的半徑系數(shù)取值

5 結 論

針對目前國內外研究中對鐵路區(qū)域劃分尚無模型化研究成果這一難題，本文提出了一種決策方法：結合路網(wǎng)鄰接特性，并考慮動車儲備與維修能力進行區(qū)域中心的選擇，以最小連接距離、最大路網(wǎng)平均連接度為目標，建立了高鐵路網(wǎng)區(qū)域劃分混合整數(shù)規(guī)劃模型，設計了一種向量編碼方式的遺傳優(yōu)化算法進行求解，提出了高鐵客運周轉量折算的方法，并以中國鐵路總公司所屬路網(wǎng)區(qū)域構建算例，對模型與算法進行了驗證。結果表明：

(1) 模型和算法可以有效解決高鐵路網(wǎng)區(qū)域劃分問題，劃分方案體現(xiàn)了高鐵網(wǎng)絡連接特性與動車服務水平?；诼肪W(wǎng)鄰域連接及中心點選擇的劃分方案較強的適應性與靈活性，解決了均值聚類算法無法處理路網(wǎng)參數(shù)及穩(wěn)定性差的問題，提高了最優(yōu)解的求解能力，避免了僅考慮距離或連接度單一指標的劃分缺陷。

(2) 應當綜合調整距離目標與連接度目標的權重，計算得出符合決策者偏好的劃分方案。且需要設置適當?shù)淖畲蠓瞻霃脚c服務容量參數(shù)，以約束劃分方案的均衡性。在給定區(qū)域劃分數(shù)量時，最大服務半徑的取值有下限要求；較小的最大服務容量約束也會導致無法得出可行解，且最大服務容量超出平均區(qū)域服務容量的一定倍數(shù)時，該約束失效。

目前在全國范圍內我國高鐵線路尚沒有形成較強的網(wǎng)絡特性，因此未來的研究包括：考慮以未來建成的中長期高鐵規(guī)劃路網(wǎng)為劃分對象；研究合理區(qū)域劃分數(shù)量的確定方法等。