趙璐陽，王麗娟，宋金鳳

（1．石家莊鐵道大學(xué) 交通運輸學(xué)院，河北 石家莊 050043；2．河北東方學(xué)院 交通學(xué)院，河北 廊坊065001)

0 引言

城際鐵路具有快速、便捷、舒適、環(huán)保等特點，《中長期鐵路網(wǎng)規(guī)劃》中明確提出要發(fā)展城際鐵路以補充現(xiàn)代高速鐵路網(wǎng)。城際鐵路在城際間客運市場內(nèi)與原有的既有鐵路和公路運輸存在競爭，同時因其票價較高、定線定員開行、路網(wǎng)規(guī)模有限等特點，又與既有鐵路和公路運輸存在協(xié)同優(yōu)化的可能。因此，加強城際鐵路、既有鐵路和公路的協(xié)同合作，可以更好地服務(wù)于城市間客運市場。

目前國內(nèi)對列車開行方案優(yōu)化的研究較多，如從坐席分配、列車運行圖、開行時段[1-3]等角度入手，通過對基于Logit[4]等模型構(gòu)建的客流分配模型的求解，采用“按流開車”原則對鐵路列車開行方案進(jìn)行優(yōu)化。除從微觀角度針對某種交通方式的開行方案進(jìn)行優(yōu)化研究外，還有學(xué)者從宏觀角度對多種交通方式間協(xié)同優(yōu)化進(jìn)行了研究。李國文等[5]研究了客運通道內(nèi)多種交通方式間客流分配的協(xié)同優(yōu)化問題；胡輝等[6]利用Benders分解技術(shù)對多方式物流運輸網(wǎng)絡(luò)優(yōu)化模型的求解進(jìn)行研究。求解交通相關(guān)問題時，圖論理論被部分學(xué)者應(yīng)用，Gutiérrez-Jarpa等[7]通過最小費用最大流算法為公路配送及軌道交通選線提供了優(yōu)化思路；張?zhí)靷サ萚8]利用最短路求解思路優(yōu)化了城際鐵路設(shè)站時的城市選擇方法。目前協(xié)同優(yōu)化方法多樣，圖論相關(guān)理論雖然被廣泛應(yīng)用于求解各類交通問題，但利用最小費用最大流理論對多種交通方式開行方案進(jìn)行協(xié)同優(yōu)化的研究還相對較少。為此，在現(xiàn)有研究基礎(chǔ)上，關(guān)注非擁擠狀態(tài)下城際間運輸通道內(nèi)多種交通方式的旅客運輸問題，并設(shè)計最小費用最大流的改進(jìn)算法，對多種交通方式開行方案進(jìn)行協(xié)同優(yōu)化。

1 問題描述

1.1 假設(shè)條件

城際間交通系統(tǒng)大部分時期處于運能充足的狀態(tài)即客流非擁擠狀態(tài)的情況，通過對多種交通方式開行方案的協(xié)同優(yōu)化研究，可以減少運能浪費并降低廣義運輸總成本，引導(dǎo)旅客合理選擇出行方式并引導(dǎo)多種交通方式有序競爭。因此，非擁擠狀態(tài)下城際間運輸通道內(nèi)多種交通方式的開行方案協(xié)同優(yōu)化，主要考慮如何滿足城際綜合運輸系統(tǒng)內(nèi)大城市與中小城市間的旅客運輸需求，包括旅客的換乘可能。城際間運輸通道多種交通方式客運路網(wǎng)如圖1中所示。

圖1 城際間運輸通道多種交通方式客運路網(wǎng)Fig.1 Multiple transport modes network in intercity transport corridors

城際間運輸通道內(nèi)多種交通方式開行方案協(xié)同優(yōu)化研究，假設(shè)相鄰城市間至少存在1種即公路運輸?shù)目瓦\直達(dá)交通方式，而城際鐵路及既有鐵路只在大城市設(shè)樞紐站可始發(fā)或終到列車，2個大城市間的中小城市所設(shè)車站均為中間站，僅可停靠列車。

1.2 參數(shù)及變量定義

大城市1與大城市N分別為城際列車的起點和終點，依次對沿線中小城市進(jìn)行1，2，…，N的自然序列編號。對城際間K種常用交通方式進(jìn)行編號，規(guī)定K= 1表示城際鐵路，K= 2表示既有鐵路，K= 3表示公路運輸。其余參數(shù)及變量分為以下4類。

（1）成本類參數(shù)。為城市i到相鄰城市j之間第K種直達(dá)交通方式的廣義運輸成本(i，j= 1，2，…，N，K= 1，2，3)，元/人，取值范圍≥0或= -1。認(rèn)為當(dāng)i=j時= 0；當(dāng)城市i與相鄰城市j間不存在K種直達(dá)交通方式時，或當(dāng)城市i與城市j不是可直達(dá)的相鄰城市時= -1 (K= 1，2，3)。C K為開行一列列車的廣義運輸成本(K= 1，2)，元/列，取值范圍C K> 0。

（2）0-1變量。為判斷是否為最低廣義運輸成本的0-1變量，當(dāng)?shù)贙種直達(dá)交通方式是城市i到相鄰城市j之間最低廣義運輸成本時，為1，否則為0。此時= 1的集合形成了城際運輸通道內(nèi)最低成本路網(wǎng)。Txy為城市x與城市y間相鄰OD路段最低廣義運輸成本的集合，即Txy= {= 1 |=1，…，= 1}，為首尾相連的相鄰OD路段的0-1變量集合，其中x與c，以及d與y分別為相鄰城市。

（3）客流量類參數(shù)。axy為城市x至城市y的OD客流量，人，取值范圍axy≥0。Aij為城市i到相鄰城市j間路段客流承擔(dān)量，人，取值范圍Aij≥ 0。

（4）其他參數(shù)及變量。V K為K種交通方式的單位載客量即每趟列車或客車的載客量，人/列或人/輛，取值范圍V K> 0。L K為城際鐵路與既有鐵路的合理開行數(shù)(K= 1，2)，列。其中合理開行數(shù)包括基礎(chǔ)開行數(shù)和可調(diào)開行數(shù)2個部分。為城市i與相鄰城市j間公路運輸?shù)暮侠黹_行數(shù)，輛，取值范圍LK≥0，且為整數(shù)。

1.3 協(xié)同優(yōu)化

為方便計算，需簡化實際運輸網(wǎng)絡(luò)。首先，判斷各城市間是否存在直達(dá)交通方式，即2個城市是否相鄰；其次，比較各相鄰城市間廣義運輸成本，確定成本最低的交通方式，逐一為0-1變量賦值，從而得到城際運輸通道內(nèi)最低廣義運輸成本客運路網(wǎng)，形成實際問題的賦權(quán)有向簡單圖。城際運輸通道內(nèi)最低廣義運輸成本客運路網(wǎng)示意圖如圖2所示。

圖2 城際運輸通道內(nèi)最低廣義運輸成本客運路網(wǎng)示意圖Fig.2 Lowest social generalized transport cost passenger transport network

（1）成本參數(shù)邏輯關(guān)系。根據(jù)已知各相鄰城市間多種交通方式的廣義運輸成本可得出城際鐵路或既有鐵路單向開行一列列車的廣義運輸成本，即

式中，認(rèn)為相鄰城市間上行和下行列車開行時廣義運輸成本相等，故列車單向開行時的廣義運輸成本等于往返開行時的一半。

（2）客流參數(shù)邏輯關(guān)系。根據(jù)已知OD客流量及計算出的OD間成本最小路徑，對客流進(jìn)行0-1分配，從而得到各相鄰OD路段的初始客流承擔(dān)量Aij，此時計算出的各OD間客流承擔(dān)量應(yīng)滿足

式中，如果Txy的集合中不存在= 1的成員，則取= 0。當(dāng)某OD間并非成本最小路徑或并非相鄰OD路段時認(rèn)為其不承擔(dān)客流，即Aij= 0。在計算時，Aij的數(shù)值可能會被調(diào)整，調(diào)整后的客流承擔(dān)量仍記為Aij。

（3）目標(biāo)函數(shù)。所構(gòu)建優(yōu)化模型的目標(biāo)函數(shù)為廣義運輸總成本最低，即

（4）0-1變量約束。求解最短路時為避免重復(fù)選線，已確定的0-1變量應(yīng)滿足

（5）客流約束。去往某城市的客流量及該城市發(fā)出的客流量應(yīng)滿足以下關(guān)系

即從城市i發(fā)出路段的總客流承擔(dān)量與進(jìn)入城市i路段的總客流承擔(dān)量之差，應(yīng)等于客流OD表中在城市i下車的總客流量與在城市i上車的總客流量之差。

（6）開行約束。為保證協(xié)同優(yōu)化的開行方案可提高運能的利用率，故開行方案應(yīng)滿足

根據(jù)假設(shè)條件，在非擁擠狀態(tài)下城際間運輸通道內(nèi)多種交通方式的開行方案協(xié)同優(yōu)化運能充足，可滿足客流需求，即如公式 ⑹ 所示。公式 ⑺ 目的是為確保運能的高效利用，避免開行過多列車。

由于公路運輸時每輛車載客量較少，在協(xié)同優(yōu)化開行方案時認(rèn)為其合理開行數(shù)量應(yīng)與客運需求相匹配，即公路運輸提供的運能剛好滿足公路運輸需求。即

由于此類問題使用數(shù)學(xué)模型求解較復(fù)雜，當(dāng)與實際網(wǎng)絡(luò)相結(jié)合，利用網(wǎng)絡(luò)的某些性質(zhì)求解將有效提高其計算效率，因而將此類問題歸納為圖論中最小費用最大流問題，并設(shè)計相關(guān)改進(jìn)算法進(jìn)行求解。

2 多種交通方式開行方案協(xié)同優(yōu)化模型改進(jìn)算法

對傳統(tǒng)的最小費用最大流理論進(jìn)行改進(jìn)，認(rèn)為其弧容量為各路段客流承擔(dān)量而非路段通過能力，弧費用為各路段廣義運輸成本。在計算時對最小費用最大流常用算法之一的最小費用路算法進(jìn)行了改進(jìn)。首先，認(rèn)為弧容量為弧流量的下限而非上限，計算結(jié)束時各弧流量需大于等于其容量但不宜過大；其次，認(rèn)為弧容量是動態(tài)可變的，允許客流承擔(dān)量即弧容量在路段間進(jìn)行合理調(diào)整；最后，當(dāng)弧流量大于等于弧容量時表示該弧已被滿足，不能再作為增廣鏈的一部分。改進(jìn)算法分為3個部分，第1部分僅考慮鐵路運輸并依據(jù)傳統(tǒng)算法求解出基礎(chǔ)開行數(shù)；第2部分考慮3種交通方式并依據(jù)上述要求，通過尋找最小費用增廣鏈調(diào)整系統(tǒng)流量，迭代至所有弧容量被滿足；第3部分比較得出總費用最低的開行方案，確定可調(diào)開行數(shù)。

2.1 基礎(chǔ)數(shù)據(jù)計算

根據(jù)運籌學(xué)圖論中的最短路理論，使用Dijkstra算法求出每一對OD點間已知的廣義運輸成本的最短路，并將結(jié)果記錄在最短路集合表中。最短路集合表樣式如表1所示。在表1的基礎(chǔ)上利用0-1分配法將已知OD交通客流量表中所有客流分配至其對應(yīng)的最短路上，分配時需確?？土鞯倪B續(xù)，從而可快捷準(zhǔn)確得出路段客流承擔(dān)量表。路段客流承擔(dān)量表樣式如表2所示。

在計算最短路時可能出現(xiàn)成本相等的線路，稱其為“可相互替換線路”，2條線路分別被括起或用斜體表示。按照“括起初始計算線路，斜體表示可替換線路”的原則進(jìn)行標(biāo)注，此2條線路不同時參與計算。

表1 最短路集合表樣式Tab.1 Shortest path set table style

表2 路段客流承擔(dān)量表樣式Tab.2 Section passenger flow bearing table style

將相鄰城市間的路段客流承擔(dān)量及其最低廣義運輸成本按照(Aij，)的形式記錄下來，從而得到計算所需的最小費用最大流基礎(chǔ)圖。多種交通方式協(xié)同優(yōu)化最小費用最大流基礎(chǔ)圖如圖3所示。

圖3 多種交通方式協(xié)同優(yōu)化最小費用最大流基礎(chǔ)圖Fig.3 Basic map of minimum cost maximum flow for collaborative optimization of multiple traffic modes

2.2 算法步驟

由于城際鐵路及既有鐵路在開行時，需從城市1始發(fā)至城市N終到，期間提供的運能一定，適用最小費用最大流的求解原則。而公路運輸可從任意城市始發(fā)至周邊城市終到，根據(jù)客流需求可直接求解開行方案，但不適用最小費用最大流的求解原則。故在計算的第1部分，即使用最小費用最大流理論計算時暫不考慮= 1的路段。在計算的第2部分即使用迭代算法計算時再加入此部分。多種交通方式協(xié)同優(yōu)化最小費用最大流計算圖如圖4所示。

圖4 多種交通方式協(xié)同優(yōu)化最小費用最大流計算圖Fig.4 Calculation of minimum cost maximum flow for collaborative optimization of multiple traffic modes

（1）計算第1部分。

步驟1：使用最小費用最大流理論解法求解出當(dāng)前計算圖的最小費用最大流。

步驟2：得到協(xié)同優(yōu)化開行方案的基礎(chǔ)開行數(shù)，并確定計算第2部分迭代算法的初始值。在計算基礎(chǔ)開行數(shù)時可采用四舍五入的方法提高運輸效率。

（2）計算第2部分。

步驟3：設(shè)還需增開n趟城際列車或m趟既有列車，并設(shè)n和m的初始值為0。

步驟4：調(diào)整圖中弧容量，將鐵路沿線可由公路運輸改為鐵路運輸?shù)目土餍枨筮M(jìn)行調(diào)整。

步驟5：將剩余客流需求統(tǒng)一分配給各相鄰城市間的公路運輸。

步驟6：求解得出當(dāng)前開行方案下目標(biāo)函數(shù)z的值，記作znm。

步驟7：判斷城際鐵路及既有鐵路線路上是否存在剩余客流需求未被滿足，若存在則n=n+ 1或m=m+ 1，轉(zhuǎn)至步驟4分別迭代1次，并記錄成本較低的znm開行方案，以簡化后期迭代；若不存在則轉(zhuǎn)至步驟8。

（3）計算第3部分。

步驟8：求解出znm的最小值。

步驟9：確定出開行方案的可調(diào)開行數(shù)，得出非擁擠狀態(tài)下城際間多種交通方式協(xié)同優(yōu)化的開行方案，計算結(jié)束。

算法中步驟4所提到的可由公路運輸改為鐵路運輸?shù)目土餍枨笫侵改砄D對間客流有多種交通方式可選，從廣義運輸成本角度公路運輸?shù)某杀咀畹?。但是，如果增開城際鐵路或既有鐵路，需將此部分客流需求從公路運輸調(diào)整至城際鐵路或既有鐵路上來，從而提高城際間綜合運輸系統(tǒng)整體的運能利用率。

3 算例應(yīng)用

以圖1為例，對城市1至城市8上行方向的協(xié)同優(yōu)化開行方案進(jìn)行計算，以驗證協(xié)同優(yōu)化及其改進(jìn)算法的有效性和準(zhǔn)確性。

假定已知運輸通道內(nèi)相鄰城市間多種交通方式的廣義運輸成本及各城市間OD客流，且在換乘時暫不考慮旅客換乘時間成本。成本及客流取值差異不影響模型計算過程及結(jié)果有效性，即利用該模型總能找到當(dāng)前問題的最優(yōu)協(xié)同開行方案，故算例按城際鐵路、既有鐵路、公路運輸成本依次增大設(shè)置廣義運輸成本，依據(jù)大中小城市規(guī)模間出行數(shù)量依次減少設(shè)置OD客流，具體如下。

（1）城際鐵路各OD點間的廣義運輸成本。城際鐵路線路為：1→2→3→4→6→8。各段線路成本為：= 40元，= 30元，= 30元，= 30元，= 40元。

（2）既有鐵路各OD點間的廣義運輸成本。既有鐵路線路為：1→2→5→6→8。各段線路成本為：= 50元，= 60元，= 40元，= 50元。

（3）公路運輸各OD點間的廣義運輸成本。公路廣義運輸成本如表3所示。

表3 公路運輸廣義運輸成本表 元Tab.3 Generalized transport cost table for road transport

（4）OD調(diào)查上行客流量。OD調(diào)查上行客流量如表4所示。

表4 OD調(diào)查上行客流量表 萬人Tab.4 OD survey traffic flow at up direction

（5）多種交通方式的單位載客量。V1= 600，V2= 1 500，V3= 50。

通過已知數(shù)據(jù)可完成準(zhǔn)備工作，首先使用Dijkstra算法得出各OD點間最短路集合，在此基礎(chǔ)上，可計算出各OD點間路段客流承擔(dān)量。其次計算出開行每列車的廣義運輸成本C1= 10.2萬元/列，C2= 30萬元/列。

在此基礎(chǔ)上，通過第1部分算法，可計算出2種鐵路交通方式的基礎(chǔ)開行數(shù)= 32列= 1列。

通過第2部分算法，經(jīng)11次迭代后，城際鐵路及既有鐵路線路上均不存在剩余客流需求，故迭代完成。其中在第7次迭代后，城際鐵路線路上已不存在剩余客流，故不再參與迭代。

進(jìn)入算法第3部分，比較11次迭代所得出的18種開行方案，可得minznm=z10= 499.3萬元，相應(yīng)可調(diào)開行數(shù)為= 1列，= 0列。故通過協(xié)同優(yōu)化問題計算可得到3種交通方式的合理開行數(shù)分別為：L1= 33列，L2= 1列，= 24輛，= 40輛，= 30輛，= 20輛，= 40輛，= 20輛，= 44輛，= 110輛，= 120輛，= 60輛。

4 結(jié)束語

研究以城際鐵路為主導(dǎo)的城際間運輸通道內(nèi)多種交通方式開行方案的協(xié)同優(yōu)化，對有效降低旅客運輸系統(tǒng)在非擁擠狀態(tài)下的廣義運輸總成本具有重要意義?？紤]廣義運輸成本及OD客流2個要素，將協(xié)同優(yōu)化歸納為最小費用最大流問題，并依據(jù)其常用算法設(shè)計出協(xié)同優(yōu)化改進(jìn)算法以提高計算效率。協(xié)同優(yōu)化結(jié)果為城際間運輸通道內(nèi)多種交通方式的日常開行方案提供了合理方案建議，在降低綜合運輸系統(tǒng)日常廣義運輸總成本的同時，可以促進(jìn)多種交通方式間有序競爭，還可以對更大規(guī)模的城市群或更多種類的交通方式進(jìn)行深入研究，考慮換乘成本等因素，探討更加高效的算法。