李婷婷 宋 瑞

(1北京交通大學城市交通復雜系統(tǒng)理論與技術教育部重點實驗室,北京100044)(2北京交通大學交通運輸學院,北京100044)

國家層面綜合客運樞紐分層布局魯棒優(yōu)化模型

李婷婷1宋 瑞2

(1北京交通大學城市交通復雜系統(tǒng)理論與技術教育部重點實驗室,北京100044)(2北京交通大學交通運輸學院,北京100044)

為提高國家層面綜合客運樞紐的運行效率,充分分析樞紐等級和需求層次的對應關系,考慮城鎮(zhèn)化發(fā)展階段客運需求的不確定性,構建了基于有能力限制的層級選址模型和隨機p-魯棒(p為相對后悔值限定系數(shù))的綜合客運樞紐布局優(yōu)化模型.設計免疫克隆算法對模型進行求解,通過算例驗證模型和算法的有效性.結果表明:分層布局方法比非分層布局方法更優(yōu),當p小于分層隨機優(yōu)化模型所有情景中的最大相對后悔值時,分層魯棒優(yōu)化模型求解結果的魯棒性比分層隨機優(yōu)化模型更強,設計的算法比優(yōu)化軟件CPLEX更高效,同時p的取值、樞紐覆蓋范圍和情景概率對樞紐布局方案產(chǎn)生較大影響.分層魯棒優(yōu)化模型能為國家層面綜合客運樞紐布局提供決策參考.

交通運輸系統(tǒng)工程;布局優(yōu)化;層級選址模型;綜合客運樞紐;魯棒優(yōu)化;免疫克隆算法

合理的綜合客運樞紐布局對構建高效的綜合運輸體系、提升客運服務水平、促進城鎮(zhèn)化發(fā)展有重要的現(xiàn)實意義.國家層面綜合客運樞紐布局規(guī)劃是戰(zhàn)略性問題,研究不同等級樞紐節(jié)點城市的選取,屬于分層設施選址問題.同時,我國近年來大規(guī)模的城鎮(zhèn)化進程使客運需求的不確定性進一步加劇,故該問題屬于不確定的分層設施選址問題.國外針對分層設施選址問題提出了層級選址模型[1-6],并廣泛應用于醫(yī)療衛(wèi)生、產(chǎn)品布局、教育系統(tǒng)、通信網(wǎng)絡等方面,但考慮不確定性的分層設施選址問題研究較少[7-8],而結合魯棒優(yōu)化的分層設施選址模型更為鮮見.國內(nèi)對國家層面綜合客運樞紐規(guī)劃布局的研究主要有節(jié)點重要度法[9]、數(shù)學優(yōu)化模型[10-12],這些方法沒有體現(xiàn)不同等級樞紐和不同層次需求之間的關系,同時缺乏對城鎮(zhèn)化發(fā)展背景下客運需求不確定性的考慮.

針對上述問題,本文按照“客流分層,樞紐分級,分層布局”的思路,構建國家層面綜合客運樞紐布局優(yōu)化模型，以制定魯棒性強的布局方案滿足規(guī)劃年限內(nèi)客運的需求,為省級層面綜合客運樞紐布局規(guī)劃提供正確指導.

1 國家層面綜合客運樞紐布局規(guī)劃

1.1 目標和特點

綜合客運樞紐布局規(guī)劃分為國家層面、省級層面、城市層面3個層次.國家層面規(guī)劃作為頂層規(guī)劃,即在國家綜合運輸網(wǎng)絡的基礎上,結合城市的人口規(guī)模、經(jīng)濟發(fā)展及其在國家綜合運輸網(wǎng)絡中的地位和功能,選擇重要節(jié)點城市作為綜合客運樞紐,以滿足國家生產(chǎn)力戰(zhàn)略布局和促進區(qū)域一體化發(fā)展.此層面綜合客運樞紐布局規(guī)劃是戰(zhàn)略性問題,主要確定樞紐節(jié)點城市及其交通功能,不涉及具體場站的選址問題.

目前,我國正處在城鎮(zhèn)化快速發(fā)展時期,國家層面綜合客運樞紐布局規(guī)劃具有如下特點:① 由于經(jīng)濟發(fā)展和交通運輸方式變革的影響,客運需求呈現(xiàn)層次性.因此,國家層面綜合客運樞紐應具有合理的等級結構,根據(jù)客流需求進行分層布局,以更好地為不同層次的需求服務.② 由于城鎮(zhèn)化進程中客運需求具有不確定性,在樞紐布局規(guī)劃前期難以對其進行精確預測,樞紐布局規(guī)劃時應加以考慮.

1.2 建模思路

根據(jù)國家層面綜合客運樞紐布局規(guī)劃的特點,在建模時,首先分析不同層次客運需求與不同等級樞紐的對應關系,應用層級選址模型描述這種關系.對于城鎮(zhèn)化進程中客運需求的不確定性,結合不確定優(yōu)化方法——隨機p-魯棒優(yōu)化方法進行處理.

1) 不同層次客運需求與不同等級樞紐的對應關系.層級選址模型[2]按照服務屬性可劃分為嵌套型和非嵌套型,嵌套型層級系統(tǒng)的高等級設施提供低等級設施的所有服務和至少一種額外服務；而非嵌套型系統(tǒng)中各等級設施提供不同的服務.由表1中各等級樞紐對應的服務客流可知,國家層面的綜合客運樞紐系統(tǒng)屬于嵌套型層級系統(tǒng),建模時采用嵌套型層級選址模型描述不同層次客運需求與不同等級樞紐的對應關系.

表1 綜合客運樞紐等級及其對應服務客流

2) 客運需求不確定性的處理.不確定性優(yōu)化方法主要有兩類:隨機優(yōu)化和魯棒優(yōu)化.隨機優(yōu)化一般以最小化期望成本為目標函數(shù),能得出平均期望成本最小的方案,但有時會出現(xiàn)部分情景下方案較優(yōu)而某些情景下方案較差的情況.同時,隨機優(yōu)化依賴于不確定參數(shù)的概率分布,而這種分布往往難以獲取.魯棒優(yōu)化中不確定參數(shù)對應離散的情景或連續(xù)區(qū)間,一般以最小化最大成本或后悔值為目標函數(shù).然而,典型的魯棒優(yōu)化方法過于保守,雖能避免最壞情況的發(fā)生,但最壞情況發(fā)生的概率卻很低.

隨機p-魯棒優(yōu)化模型為

(1)

(2)

式中,qs為情景s發(fā)生的概率；Ω為可行解空間.

綜上所述,本文借鑒隨機p-魯棒優(yōu)化方法處理城鎮(zhèn)化進程中客運需求的不確定性.

2 國家層面綜合客運樞紐分層布局魯棒優(yōu)化模型

首先作以下假設：需求點和備選樞紐點同在城市的中心;同一需求點同一層次需求分配到同一樞紐;一定時期內(nèi)各等級樞紐覆蓋范圍為確定值.除了考慮綜合客運樞紐與客運需求的對應關系及需求不確定性,模型對樞紐不同層次服務能力加以約束,即所有樞紐提供任何層次服務的能力均有限,樞紐承擔的各層次交通需求均應在樞紐各層次服務的最大能力范圍內(nèi),而由于樞紐功能有所側(cè)重,只要求其承擔的最高層需求量超過相應值,對其承擔的低層次服務量不作最小能力限制.分層布局(HR)模型為

(3)

(4)

(5)

(6)

(7)

(8)

wjks≥bjkyjt?j∈J,t∈H,

(9)

(10)

(11)

(12)

(13)

式中,H表示需求點的需求層次、樞紐點的服務層次和樞紐等級的集合,H={1,2,3};I為需求點集合;J為所有備選樞紐點集合；k為需求點的需求層次和樞紐點的服務層次；t為樞紐等級;dij為需求點i和樞紐點j間的距離;uiks為情景s下需求點i第k層的需求量;bjk為若在樞紐點j設立樞紐,該樞紐點承擔的第k層需求量至少達到的值(下文稱為服務能力最小值);Bjk為樞紐點j能提供的第k層服務的最大能力(下文稱為服務能力最大值);Dk為第k層需求用戶能接受的需求點到樞紐的最遠出行距離；yjt為如果樞紐點j被選中為t級樞紐,則yjt=1,否則為0;xijks為情景s下如果需求點i第k層需求由樞紐點j服務,則xijks=1,否則為0;wjks為情景s下樞紐點j承擔的第k層需求量.

式(3)表示所有情景的期望需求加權距離最小化;式(4)表示情景s下的需求加權距離;式(5)表示任何情景下所有需求點任何層次的需求都得到滿足;式(6)表示任何樞紐點都不允許同時設立不同等級的樞紐;式(7)表示任何情景下需求點任一層次的需求必須由相同或更高等級的樞紐服務(1級為高級,3級為低級);式(8)表示任何情景下樞紐承擔的任一層次的需求量等于由該樞紐點服務的所有需求點的對應層次的需求量之和;式(9)表示任何情景下樞紐承擔的最高層次的需求量必須大于等于該樞紐點最高層次服務能力最小值;式(10)表示任何情景下樞紐承擔的任一層次的需求量必須在其對應層次服務的最大能力范圍內(nèi);式(11)為魯棒約束,表示任何情景下的需求加權距離不超過對應最優(yōu)解的100%p;式(12)表示任何情景下如果需求點到樞紐點的距離在可接受范圍之外,需求點不由該樞紐點服務;式(13)表示變量的取值范圍約束.

3 模型求解

3.1 模型分析

不考慮約束(11):對給定的情景s,模型HR的需求參數(shù)為確定值,其實質(zhì)為確定性分層優(yōu)化(HD)模型;對給定的情景集S,模型HR實質(zhì)為如下基于情景的分層隨機優(yōu)化(HS)模型：

s.t. 式(5)～(10)、(12)和(13)

3.2 免疫克隆算法

對于大規(guī)模、多情景問題,使用免疫克隆算法求解.算法設計如下:

1) 編碼方案.采用二進制編碼,每個抗體由3部分組成,每部分表示為各需求點某層次需求服務的樞紐點編號,抗體長度為需求點數(shù)量與需求層次總數(shù)的乘積.如圖1所示,圈中數(shù)字表示編號為1的需求點的1級需求由編號為0的樞紐點服務,而其2級和3級需求均由編號為1的樞紐點服務.另外,從抗體可以判斷樞紐的等級:為1級需求服務的樞紐點是1級樞紐;為2級需求服務的樞紐點,如果同時出現(xiàn)在1級需求部分,則為1級樞紐,否則為2級樞紐;為3級需求服務的樞紐點,如果同時出現(xiàn)在1級需求部分,則為1級樞紐,如果同時出現(xiàn)在2級需求部分而不出現(xiàn)在1級需求部分,則為2級樞紐,僅在3級需求部分出現(xiàn)的為3級樞紐.

圖1 免疫克隆算法編碼方案

2) 初始化.首先進行數(shù)據(jù)預處理,根據(jù)要求(需求點在樞紐點覆蓋范圍內(nèi),且樞紐點能提供相應層次服務)篩選出能為各需求點各層次需求服務的樞紐點集合,然后從集合中隨機選取任一樞紐編號生成抗體.

3) 親和度函數(shù).同時考慮約束(9)～(11),采用罰函數(shù)法,將約束合并到目標函數(shù)中,以δ1，δ2，δ3為懲罰因子,親和度函數(shù)為

4) 克隆個數(shù)、變異概率、選擇個數(shù)、變異操作.每個抗體的克隆個數(shù)與其親和度成正比；變異概率、選擇個數(shù)為迭代次數(shù)的函數(shù),隨著迭代次數(shù)增加,變異概率變大,選擇個數(shù)變少；變異操作為抗體每部分各自按單點變異法進行,具體可見文獻[14].

5) 算法終止條件.當最優(yōu)值連續(xù)迭代若干次不再變化或者迭代次數(shù)達到最大迭代次數(shù)M時，終止運行.

算法步驟如下:

① 數(shù)據(jù)預處理和初始化.隨機產(chǎn)生N個抗體,組成初始抗體群P.

② 根據(jù)親和度函數(shù)計算親和度.根據(jù)親和度值從大到小進行排序.

③ 對抗體種群中的抗體進行克隆擴增操作,得到擴增后的抗體群C.

④ 對抗體群C中的抗體進行高頻變異,得到C*.

⑤ 從C*中選擇d個親和度高的抗體，替換P中d個親和度低的抗體.

⑥ 判斷終止條件是否滿足,如果滿足，則程序結束并輸出最優(yōu)解,否則轉(zhuǎn)至③.

4 算例

4.1 算例設計

下面設計算例對模型和算法進行驗證,圖2為研究區(qū)域及其路網(wǎng).

圖2 研究區(qū)域需求點分布及路網(wǎng)圖

圖2中,城市A～城市M為需求點,城市A～城市E為1級樞紐備選點,城市A～城市I為2級樞紐備選點,城市A～城市M為3級樞紐備選點,1、2、3級樞紐覆蓋范圍分別為600,300,100 km.各城市間距離如表2所示,各城市服務能力最小值相同,1、2、3級分別為6 000,5 000,3 500萬人次/a,服務能力最大值如表3所示.設計10個情景，每個情景對應不同需求.表4為情景1需求,其他情景需求依此按5%的比例增長,各情景概率均為0.1.

4.2 結果分析

在Intel Core I5-2450M CPU@2.50 GHz,內(nèi)存2 GB,Visual Studio 2008平臺上調(diào)用優(yōu)化軟件CPLEX12.2對模型HD求解,同時編程實現(xiàn)免疫克隆算法對模型HR進行求解.其中運行參數(shù)設置為:初始種群規(guī)模為100,克隆個數(shù)最大值為15,克隆個數(shù)最小值為5,變異概率最大值為0.8,變異概率最小值為0.1,變異概率常數(shù)為0.8,最大迭代次數(shù)為1 000,或連續(xù)迭代50次不變化則終止,δ1,δ2均取10 000,δ3取10.

表2 城市之間的距離 km

表3 城市各層次服務能力最大值 萬人次/a

表4 城市各層次需求(情景1) 萬人次/a

4.2.1 算法分析

如表5所示,當p≥0.12時,免疫克隆算法求解得到的目標函數(shù)值比采用優(yōu)化軟件CPLEX求解得到的值大,但相對偏差不超過5%,說明該情況下免疫克隆算法求解結果是有效的,而由于軟件CPLEX求解時間遠小于免疫克隆算法,故該情況下采用軟件CPLEX求解更為適用.當p<0.12時,使用CPLEX求解由于內(nèi)存不足而停止運算,此時得到的上下界與免疫克隆算法的相對偏差均小于4%.因此,當p<0.12時,免疫克隆算法目標函數(shù)值與最優(yōu)目標函數(shù)值更接近,且免疫克隆算法的求解時間短得多,故該情況下使用免疫克隆算法求解具有更明顯的優(yōu)勢.

表5 免疫克隆算法與CPLEX的比較

注：Δ表示使用免疫克隆算法求解得到的目標函數(shù)值與使用軟件CPLEX求得值的相對偏差;*表示由于內(nèi)存不足停止運算.

4.2.2 不同模型求解結果的比較

如表6所示,當p=0.15時模型HR的目標函數(shù)值比模型HS的目標函數(shù)值大；當p=0.12時，兩模型的目標函數(shù)較為接近；而p=0.1或0.05時,模型HR的目標函數(shù)值均比模型HS小.原因可以從表7看出,由于所有情景下模型HS對模型HD的相對后悔值均低于12%,若模型HR中p>0.12,某些情景的相對后悔值比模型HS的大,從而導致模型HR的目標函數(shù)值更大.此外,從表6看出,當p≥0.12時,模型HS和HR求得的樞紐布局方案相同,當p=0.1或0.05時,模型HR與模型HS求得的布局方案不同.由表7可看出,模型HD在不同情景下對應的最優(yōu)樞紐布局方案存在差異.

綜上所述:需求不確定情況下,不同的p值對布局方案影響不同,當p大于模型HS所有情景中的最大相對后悔值時,模型HR與模型HS求得的布局方案一致,而p小于該值時布局方案差異較大;需求確定情況下,不同需求對應的樞紐布局分配方案不同.

如表7所示,各情景下模型non-HD(指不分層的確定性需求下的布局方法,即重復利用中位模型分別對各級樞紐進行布局)的目標函數(shù)值遠遠大于分層布局(HD,HS,HR)的方法,即分層布局方法求解結果在可達性方面更具優(yōu)勢.另外,對于模型HR,當p=0.12時,情景4的相對后悔值比模型HS大,其他情景相對后悔值與模型HS相同;當p=0.05時,除情景3的相對后悔值比模型HS大,其他情景相對后悔值比HS小得多.可見,當p<0.12時模型HR的魯棒性比模型HS更強.

表6 模型HS和HR求解結果比較

表7 各情景下不同模型相對后悔值的比較及模型HD的布局方案

4.2.3 靈敏度分析

表8為覆蓋范圍或情景概率改變時,p取不同值時的目標函數(shù)值和樞紐布局方案(初始參數(shù)設置下的目標函數(shù)值和樞紐布局方案見表6).當各級樞紐覆蓋范圍從600,300,100 km變?yōu)?00,300,100 km,p取不同值時,樞紐布局方案均沒有變化，而分配方案變化,目標函數(shù)值變小.可見,覆蓋范圍對樞紐布局和分配方案有一定影響.若前5種情景的概率均增加0.05，而后5種情景概率均減少0.05,當p=0.15或0.12時,樞紐布局和分配方案不變,目標函數(shù)值變小,因為前5種情景對應的需求加權距離均比后5種小;當p=0.10或0.05時,樞紐布局方案和目標函數(shù)值均發(fā)生變化.可見,情景概率對樞紐布局方案有重要的影響.

表8 不同p值下覆蓋范圍變化、情景概率變化后模型HR的求解結果

5 結論

1) 針對城鎮(zhèn)化進程中國家層面綜合客運樞紐布局優(yōu)化問題，構建了分層布局魯棒優(yōu)化模型.基于有能力限制的層級選址模型能反映樞紐等級系統(tǒng)的特征,同時結合魯棒優(yōu)化方法處理城鎮(zhèn)化發(fā)展中需求的不確定性,模型更貼近實際情況.

2) 設計免疫克隆算法對模型求解,通過算例分析驗證了算法的有效性.與軟件CPLEX相比,算法在一定范圍的p值下更高效.

3) 算例結果表明,分層布局方法優(yōu)于重復使用中位模型分別對各級樞紐布局的方法,當p取值小于模型HS所有情景中的最大相對后悔值時,模型HR的求解結果比模型HS的求解結果具有更強的魯棒性,同時p的取值、覆蓋范圍和情景概率對樞紐布局方案有重要影響.

4) 本文對城鎮(zhèn)化快速發(fā)展背景下的國家層面綜合客運樞紐布局規(guī)劃有一定的理論參考意義.規(guī)劃部門應充分分析樞紐等級系統(tǒng)的運行機理,考慮城鎮(zhèn)化進程中各類不確定性因素,根據(jù)需求制定具有一定魯棒性的布局方案,為省級層面綜合客運樞紐布局規(guī)劃提供正確指導.

References)

[1]Farahani R Z, Hekmatfar M, Fahimnia B, et al. Hierarchical facility location problem: models, classifications, techniques, and applications [J].Computers&IndustrialEngineering, 2014, 68: 104-117.

[2]Pehlivan C, Augusto V, Xie Xiaolan. Dynamic capacity planning and location of hierarchical service networks under service level constraints [J].IEEETransactionsonAutomationScienceandEngineering, 2014, 11(3): 863-880.

[3]Smith H K, Harper P R, Potts C N. Bicriteria efficiency/equity hierarchical location models for public service application [J].JournaloftheOperationalResearchSociety, 2013, 64(4): 500-512.

[4]Chen Zhifen, Chen Xiang, Li Qiang, et al. The temporal hierarchy of shelters: a hierarchical location model for earthquake-shelter planning [J].InternationalJournalofGeographicalInformationScience, 2013, 27(8): 1612-1630.

[5]Mestre A M, Oliveira M D, Barbosa-Povoa A. Organizing hospitals into networks: a hierarchical and multiservice model to define location, supply and referrals in planned hospital systems [J].ORSpectrum, 2012, 34(2): 319-348.

[6]Yan Yan, Zhang Baoxian, Zheng Jun, et al. Hierarchical location service for wireless sensor networks with mobile sinks [J].WirelessCommunicationsandMobileComputing, 2010, 10(7): 899-911.

[7]Shavandi H, Mahlooji H. Fuzzy hierarchical queuing models for the location set covering problem in congested systems [J].ScientiaIranica, 2008, 15(3): 378-388.

[8]Wang Zhen, Du Donglei, Gabor A F, et al. An approximation algorithm for the k-level stochastic facility location problem [J].OperationsResearchLetters, 2010, 38(5): 386-389.

[9]孫小年, 石瓊. 省級區(qū)域公路運輸樞紐宏觀布局研究 [J]. 交通標準化, 2007 (9): 32-36. Sun Xiaonian, Shi Qiong. Research on macroscopic layout of provincial areal highway transportation hinge [J].TransportStandardization, 2007(9): 32-36.(in Chinese)

[10]劉強, 陸化普, 王慶云. 區(qū)域綜合交通樞紐布局雙層規(guī)劃模型 [J]. 東南大學學報:自然科學版, 2010, 40(6): 1358-1363. Liu Qiang, Lu Huapu, Wang Qingyun. Bi-level programming model for regional integrated transportation hub layout [J].JournalofSoutheastUniversity:NaturalScienceEdition, 2010, 40(6): 1358-1363. (in Chinese)

[11]丁金學, 金鳳君, 王成金, 等. 中國交通樞紐空間布局的評價、優(yōu)化與模擬 [J]. 地理學報, 2011, 66(4): 504-514. Ding Jinxue, Jin Fengjun, Wang Chengjin, et al. Evaluation, optimization and simulation of the spatial layout of transport hubs in China [J].ActaGeographicaSinica, 2011, 66(4): 504-514. (in Chinese)

[12]李代坤, 何世偉, 申永生, 等. 基于免疫克隆算法的綜合交通樞紐布局優(yōu)化研究 [J]. 武漢理工大學學報:交通科學與工程版, 2012, 36(2): 382-386. Li Daikun, He Shiwei, Shen Yongsheng, et al. Layout optimization of comprehensive transportation hub based on immune clone algorithm [J].JournalofWuhanUniversityofTechnology:TransportationScience&Engineering, 2012, 36(2): 382-386. (in Chinese)

[13]Snyder L V, Daskin M S. Stochastic p-robust location problems [J].IIETransactions, 2006, 38(11): 971-985.

[14]黃友銳. 智能優(yōu)化算法及其應用 [M]. 北京：國防工業(yè)出版社, 2008: 68-70.

Hierarchical layout robust optimization model for integrated passenger hub at national level

Li Tingting1Song Rui2

(1MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University, Beijing 100044,China) (2School of Traffic and Transportation,Beijing Jiaotong University, Beijing 100044, China)

In order to improve the efficiency of integrated passenger hub at national level, the relationship between integrated passenger hub classification and passenger transport demand is analyzed. The uncertainty of the passenger transport demand in the process of urbanization is taken into account. A model based on capacitated hierarchical location model and stochasticp-robust (pis relative regret restricted coefficient) optimization is proposed. An immune clonal algorithm is designed to solve the problem and a numerical example is given to validate the effectiveness of the model and algorithm. The results show that hierarchical layout model is superior to non-hierarchical layout model. Whenpis less than the maximum relative regret of hierarchical stochastic (HS) model, the result of hierarchical robust (HR) model has stronger robustness than that of the HS model and the immune clonal algorithm performs more efficiently than optimization software CPLEX. The value ofp, the coverage of hubs and the scenario probability greatly affect the layout planning scheme. The HR model provides decision references for integrated passenger hub layout planning.

transportation system engineering; layout optimization; hierarchical location model; integrated passenger hub; robust optimization; immune clonal algorithm

2014-08-04. 作者簡介: 李婷婷(1985—),女,博士生;宋瑞(聯(lián)系人),女,博士,教授,博士生導師,rsong@bjtu.edu.cn.

國家重點基礎研究發(fā)展計劃(973計劃)資助項目(2012CB725403).

李婷婷,宋瑞.國家層面綜合客運樞紐分層布局魯棒優(yōu)化模型[J].東南大學學報:自然科學版,2015,45(1):189-195.

10.3969/j.issn.1001-0505.2015.01.033

U491

A

1001-0505(2015)01-0189-07