徐瑞華，李 璇

（同濟大學 交通運輸工程學院，上海201804）

經(jīng)過多年的軌道交通建設，北京、上海、廣州等大城市目前已進入軌道交通網(wǎng)絡化運營的新階段.網(wǎng)絡化運營條件下，原本獨立運營的各線路通過換乘站產(chǎn)生直接或間接的聯(lián)系，軌道交通客流也通過換乘站實現(xiàn)在不同線路上的流動.由于各線路結束運營的時刻不同，網(wǎng)絡上各車站之間的可達關系呈現(xiàn)出動態(tài)變化的特點，一條線路的末班車時刻不僅影響到本線乘客的出行，更大程度上通過到達換乘站的時刻將影響擴大到整個路網(wǎng)，末班車時刻制訂的合理與否直接關系到乘客能否到達目的地，因此，根據(jù)客流流向和流量特點，對網(wǎng)絡末班車計劃進行協(xié)調編制，實現(xiàn)各線路末班車在換乘站的整體合理銜接非常重要.目前，國外涉及城市軌道交通換乘銜接優(yōu)化的研究[1－4]主要集中于常規(guī)公交與軌道交通列車時刻表的協(xié)調優(yōu)化方面，尚無針對軌道交通系統(tǒng)內(nèi)部各線路間的末班車銜接問題的研究，國內(nèi)的研究也處于起步階段，少數(shù)關于城軌末班車的研究[5－6]存在銜接關系確定的主觀性太強、未結合換乘客流特點等問題.

在列車區(qū)間運行時分、停站時分及各換乘站的換乘走行時間均已知的前提下，協(xié)調編制城市軌道交通網(wǎng)絡末班車計劃就是根據(jù)一定的線路銜接關系逐步推算各條線路上、下行方向的末班車在換乘站的到發(fā)時刻及始發(fā)時刻，由于網(wǎng)絡化運營條件下，網(wǎng)絡規(guī)模大、換乘站數(shù)量多、換乘關系復雜，列車在各換乘站的銜接關系存在相互制約、相互影響，因此制訂面向全網(wǎng)絡最合理的末班車銜接計劃難度很大，而關鍵則是需要確定基于全網(wǎng)絡整體優(yōu)化的各換乘站末班車的推算順序及銜接關系，這里稱為網(wǎng)絡末班車銜接方案.本文通過分析確定銜接方案應考慮的因素，建立了網(wǎng)絡末班車銜接方案優(yōu)化模型，并借鑒最小生成樹的Kruskal算法思想，綜合考慮客流需求和運營者的特定銜接需求，提出了網(wǎng)絡末班車銜接方案的優(yōu)化算法.

1 網(wǎng)絡末班車銜接關系分析

1.1 單個換乘站末班車銜接關系分析

兩線換乘的條件下，末班車在換乘站的銜接具有以下3種情形：雙方向銜接、單方向銜接和無方向銜接3種.其中，雙方向銜接即兩列末班車的乘客可以相互換乘，由于地鐵換乘站大多設置換乘通道，換乘走行時間較長，而雙方向銜接要求列車停站時間能夠同時滿足雙向換乘的走行時間要求，實際中較難實現(xiàn)；單方向銜接是只有一列末班車的乘客可以換乘至另一列車，而反向無法換乘，這是最常見的一種銜接狀態(tài)，也是進行末班車計劃協(xié)調時重點考慮實現(xiàn)的狀態(tài)；而無方向銜接即兩列末班車的乘客無法相互換乘，此為最差銜接狀態(tài)，是編制末班車計劃時應盡量避免的.

多線換乘條件下，以某一個N線換乘站為例，若其中有Nt條線路通過此換乘站，Ne條線路終止于此換乘站，在不考慮同一線路上、下行方向之間的換乘的前提下，該換乘站的末班車換乘銜接關系有（2Nt＋Ne）2－（4Nt＋Ne）種，對該換乘站涉及的2N列末班車進行到發(fā)時刻推算，需要選擇其中的2N－1個銜接關系作為推算基礎，本文將它們稱為“主動銜接關系”.

1.2 多個換乘站末班車銜接關系分析

對某一個由N條線路組成的城市軌道交通網(wǎng)絡而言，路網(wǎng)規(guī)模越大，換乘站數(shù)量越多，末班車的換乘銜接關系越復雜，對路網(wǎng)中的2N列末班車進行時刻推算，需要依據(jù)的主動銜接關系為2N－1個，每個主動銜接關系都發(fā)生在某個換乘站內(nèi)，將這些換乘站稱為“主協(xié)調換乘站”.

由于路網(wǎng)中多個換乘站之間的銜接關系存在矛盾，一個換乘站內(nèi)部的銜接關系之間也存在矛盾，主要表現(xiàn)在以下幾個方面：同一個銜接關系不可能在兩個換乘站同時實現(xiàn)；形成“回路”的銜接關系不能同時實現(xiàn)（如Line A上行→LineB上行，LineB上行→LineC下行，LineC下行→Line A上行）；兩列末班車涉及的兩個銜接關系不能同時實現(xiàn)（如Line A上行→LineB上行和LineB上行→LineA上行）.確定網(wǎng)絡末班車銜接關系，就是需要從龐大的銜接關系集中選出彼此沒有矛盾的主動銜接關系和主協(xié)調換乘站，形成一個銜接方案，這是編制網(wǎng)絡末班車計劃需要解決的關鍵問題.

2 網(wǎng)絡末班車銜接方案優(yōu)化模型

從城市軌道交通網(wǎng)絡運營的基本要求來看，網(wǎng)絡末班車銜接需要保證乘客能夠到達目的地，即銜接方案優(yōu)化的目標是使網(wǎng)絡換乘站能夠換乘到末班車的乘客數(shù)量最大化.同時，由于某些特殊的運營需求，運營者可能要求末班車銜接方案要實現(xiàn)某些特定的銜接關系，那么銜接方案優(yōu)化需要將運營者對銜接關系的特定要求作為約束條件.因此，可建立如下的網(wǎng)絡末班車銜接方案優(yōu)化模型：

式中：X是包含2n－1個主動銜接關系的銜接方案，當這些銜接關系不存在矛盾時，稱X為可行銜接方案，n為路網(wǎng)的線路數(shù)；m為路網(wǎng)的換乘站數(shù)；gi（X）是銜接方案為X時，第i個換乘站內(nèi)能夠換乘至末班車的乘客數(shù)量；是運營者要求實現(xiàn)的特定銜接關系集合，包含k個銜接關系，是的子集；同時，?X保證銜接方案考慮了運營者對銜接關系的特殊需求，但銜接方案中包含的特定銜接關系彼此間不能存在矛盾，因此，第三個約束條件要求可行.

路網(wǎng)線路數(shù)量越多，可行銜接方案數(shù)也越多，即X的可行域越大，且可行銜接方案與路網(wǎng)結構相關，無法用數(shù)學公式將X的可行域表達出來，則無法通過對比不同可行解的目標函數(shù)值來找出最優(yōu)解，因此用傳統(tǒng)優(yōu)化方法或啟發(fā)式搜索算法均很難求解.本文放棄對比尋優(yōu)的求解思路，直接以優(yōu)化目標為向導，來確定能夠使目標函數(shù)最大化的最優(yōu)銜接方案，通過分析將其轉化為最大生成樹問題，借鑒Kruskal算法的基本思想，提出了基于乘客換乘需求和運營者的特定銜接需求的網(wǎng)絡末班車銜接方案優(yōu)化算法.

3 網(wǎng)絡線路銜接關系表示

3.1 線路銜接關系的賦權無向圖表示法

軌道交通運營線路有上、下行的區(qū)分，為了描述這種帶有方向性的線路之間的連通關系，通常將城市軌道交通網(wǎng)絡用有向圖來表示，建立車站到頂點的映射和區(qū)間到有向邊的映射.本文考慮將分方向的線路抽象為頂點，用無向圖G來描述城市軌道交通網(wǎng)絡中的線路銜接關系.G為一個有序二元組，記為G＝（V，E），其中，V＝（v11，v12，v21，v22，…，vn1，vn2）為頂點集，表示路網(wǎng)中分方向的線路集合，n為網(wǎng)絡線路的條數(shù)，vi1和vi2（i∈｛1，2，…，n｝）分別表示某條線路i的上、下行方向；E是由V中的無序的元素偶對eip，jq＝（vip，vjq）所構成的邊集（i，j∈｛1，2，…，n｝，i≠j，p，q∈｛1，2｝），表示路網(wǎng)中線路間的銜接關系集合.

對E中每一條邊eip，jq賦以相應的權值ωip，jq，則G成為一個賦權無向圖，ωip，jq代表eip，jq對應的銜接關系的晚間時段換乘客流量.若線路i和線路j有1個換乘交點，則vip和vjq將涉及一個“銜接關系對”，即vip→vjq和vjq→vip，分別表示由線路i的p方向換乘至線路j的q方向和由線路j的q方向換乘至線路i的p方向.由于只考慮單方向銜接狀態(tài)，這兩者在銜接方案中只可能滿足其中一個；若線路i和線路j有m個換乘交點（m＞1），則vip和vjq將涉及m個“銜接關系對”，這2m個銜接關系中，有且僅有一個能夠作為主動銜接關系，成為vip和vjq的末班車時刻推算基礎.根據(jù)第2節(jié)建立的目標函數(shù)，在圖G中，對?vip，vjq∈V，可選取兩者涉及的所有銜接關系對應的換乘客流量最大的一個作為連接兩者的邊的權值.

經(jīng)過以上分析，最終得到的賦權無向圖G具有以下性質：

（1）若路網(wǎng)中線路有n條，則頂點集V的元素個數(shù)為2n；

（2）若路網(wǎng)中線路兩兩相交有k個交點，則邊集E的元素個數(shù)為4k.這里的交點不是物理意義上的兩線換乘點，僅表示兩條線路可以直接換乘.

（4）由于軌道交通路網(wǎng)中的任意兩條線路通過一次或多次換乘可達，所以圖G為連通圖.

在將路網(wǎng)表示為圖G的基礎上，要確定一個覆蓋全網(wǎng)所有線路方向且沒有矛盾的銜接方案，可以轉化為以下問題：在圖G中，尋找由某頂點vip出發(fā)，至圖中所有其他頂點都恰有一條初等鏈的生成樹T＊，T＊的權需滿足W（T＊）＝max｛W（T）｜T為G的一棵生成樹｝，樹T＊可表達為以頂點vip為根的根樹，即求連通賦權無向圖的最大生成樹的問題.

3.2 賦權無向圖表示實例

圖1為一城市軌道交通路網(wǎng)圖例，它包含4條線路｛L1，L2，L3，L4｝，其中，L4為環(huán)線，圖中箭頭表示線路的下行方向；包含6個換乘站｛a，b，c，d，e，g｝.表1為圖1所示路網(wǎng)晚間時段的分線路分方向的換乘客流量表，第一行和第一列中的Li上／下表示線路i的上／下行方向，行與列相交處的單元格由所在行Li上／下?lián)Q乘到所在列Lj上／下的客流量及所在的換乘站序號組成，這里對客流量取了較小的數(shù)字來說明方法.圖2為基于表1給出的圖1所示路網(wǎng)的線路銜接關系的賦權無向圖.

圖1 城市軌道交通路網(wǎng)圖示Fig.1 An urban rail transit networ k

圖2 圖1路網(wǎng)的賦權無向圖Fig.2 Undirected edge－weighted graph of Fig.1

3.3 線路銜接關系的矩陣表示法

上例中，路網(wǎng)的線路條數(shù)n＝4，線路兩兩相交的交點數(shù)k＝6，其對應的賦權有向圖中的頂點數(shù)為8，弧數(shù)為24.而實際的城市軌道交通路網(wǎng)線路數(shù)更多，線路之間的關系更為復雜，對應的賦權無向圖中的元素數(shù)量將更大，下面考慮用矩陣的形式來表示賦權無向圖包含的頂點與頂點及頂點與邊的關聯(lián)關系.

構造一個2n×2n矩陣（n為路網(wǎng)線路數(shù)）B＝（bip，jq）2n×2n，行標號和列標號對應圖G中的頂點下標（i，j∈｛1，2，…，n｝，i≠j；p，q∈｛1，2｝），其中，

表1 圖1路網(wǎng)的換乘客流量表Tab.1 The volume of transfer passenger flow of Fig.1

與上文相同，wip→jq，m仍表示在換乘站m由線路i的p方向換乘至線路j的q方向的客流量.B中不為零的元素個數(shù)與圖G中邊集E的元素個數(shù)相同，為4k（k的意義同上）.在矩陣B外的左邊一列及上方一行標出了圖G的諸頂點（全文同），分別表示銜接關系中的起線方向和到線方向，如下側矩陣所示.

圖1所示路網(wǎng)對應的矩陣如下側矩陣所示.以L1上行和L2上行這一對線路為例，它們涉及2個銜接關系，L1上行→L2上行和L2上行→L1上行，對照表1可知，前者在換乘站a的換乘客流量為23，后者在換乘站a的換乘客流量為66，兩者中較大者為66，根據(jù)對線路銜接關系矩陣的定義，b11，21＝0且b21，11＝66.其他矩陣元素的確定方法同上，由于換乘站與換乘客流量一一對應，線路銜接關系的矩陣表達間接包含了線路銜接所在的換乘站的信息.

4 網(wǎng)絡末班車銜接方案優(yōu)化算法

求最小生成樹的Kruskal算法是在給定圖的基礎上，根據(jù)邊的權值依次找出權值最小的邊加入生成樹，直至生成樹包含原圖中的所有節(jié)點，即形成最小生成樹，規(guī)定每次添加的邊不能造成生成樹有回路[7].該算法的思路和流程同樣適用于求最大生成樹，如前所述，網(wǎng)絡末班車銜接方案優(yōu)化問題可以轉化為求連通賦權無向圖的最大生成樹的問題，因此，本文借鑒Kruskal算法的基本思想，基于線路銜接關系的矩陣表示，設計網(wǎng)絡末班車銜接方案優(yōu)化算法.

4.1 考慮乘客換乘需求的基本算法

根據(jù)“在無回路的條件下優(yōu)先選取較大的元素”這一原則，從矩陣B中逐個挑選出2n－1個元素，依次添加到主動銜接關系集合E中，算法步驟如下：

（1）取E＝?，E中元素個數(shù)記為card（E）＝0；

（3）在矩陣B未標記過的元素中尋找當前最大元素，該元素須滿足行標或列標對應的頂點已標記，且為了避免形成回路，該元素的行標和列標對應的頂點不能同時已標記，即，找出后將該元素進行標 記，并 添 加 到 集 合E中，，card（E）＋＝1.并將其行標和列標對應的頂點中未標記的2個進行標記；

（4）判斷是否所有的頂點都已標記且card（E）＝2n－1，若是，則算法終止，得到最優(yōu)的主動銜接關系集合E＊.由運營單位指定末班車時刻推算的起始線路方向，即可以該線路方向為樹根，根據(jù)集合E＊，對照線路銜接關系矩陣，繪制出各線路方向末班車時刻的推算關系圖T＊（如圖3所示）.T＊是一個無圈連通圖，即為樹，并且T＊是無向圖，其各條邊上的箭頭僅表示邊關聯(lián)的兩個頂點所代表的線路方向間的換乘銜接關系.若否，則轉步驟（3）.

4.2 滿足特定銜接需求的改進算法

在實際運營中，運營者可能對末班車的銜接關系有某些特定的要求，如大型活動舉辦期間，城市軌道交通作為大容量的公共交通工具，將承擔最主要的客流集散任務，為了做好散場客流的運輸，保證乘客可以從直接服務于大型活動的線路換乘至其他線路到達目的地，運營者將結合活動結束時間及散場客流特點指定一些必須成立的末班車銜接關系，此時就要在滿足這些特定銜接需求的基礎上進行網(wǎng)絡末班車銜接關系優(yōu)化，下面給出具體的改進算法.

運營者指定多個換乘站的多個銜接關系必須實現(xiàn)，它們構成基準銜接關系集R，記R中包含的帶方向別的線路集為V基準（V基準∈V），線路條數(shù)記為s，將推算算法分為三大步驟進行：

第一步，確定屬于V基準的線路推算關系.首先，用3.1節(jié)所述方法將R中銜接關系表示為一個有向圖D基準，判斷D基準是否為連通圖.

若D基準為連通圖，則按照以下步驟進行：（1）構造基準銜接關系矩陣，記為B基準＝（bip，jq）s×s，構造方法與線路銜接關系矩陣B相同，但只需將R中包含的銜接關系對應的換乘客流量表示在B基準中的相應元素位置，其余位置元素都為0，若R中針對一對帶方向別的線路存在多于1個的銜接關系（協(xié)調換乘站不同或銜接方向不同），則取其中換乘客流量最大的一個填入矩陣中的相應位置；（2）以B基準為基礎，按照3.1節(jié)所述推算步驟，可得到基準主動銜接關系集E基準.

若D基準為分離圖，則可將D基準分為若干個連通子圖（連通子圖的數(shù)目記為h），對每個連通子圖，分別按照上述連通圖的步驟進行推算.對于只包含兩個節(jié)點的連通子圖，無需推算，其對應的基準主動銜接關系子集只包含一個元素，即圖中唯一弧的權值.最終，可得到h個基準主動銜接關系子集，E基準＝E基準1∪E基準2∪…∪E基準h.

第二步，確定全路網(wǎng)分方向線路的推算關系.首先，構造全路網(wǎng)線路銜接關系矩陣B.

若D基準為連通圖，則將不屬于V基準的線路與路網(wǎng)其他線路的銜接關系在B中表示出來，接著按照以下 步 驟 進 行：（1）取E＝E基準，card（E）＝card（E基準），將屬于V基準的頂點在矩陣B外進行標記；（2）在B未標記過的元素中尋找最大元素，該元素須滿足行標或列標對應的頂點已標記，且不能同時 已 標 記，且找出后將該元素進行標記，并添加到集合E中，＋＝1，并將其行標和列標對應的頂點中未標記的2個進行標記；（3）判斷是否所有的頂點都已標記，若是，則算法終止.若否，則轉步驟（2）.

若D基準為分離圖，則在矩陣B中，表示出不屬于V基準的線路與路網(wǎng)其他線路的銜接關系，及分屬于不同連通子圖的線路間的銜接關系，接著按照以下 步 驟 進 行：（1）取E＝E基準1，card（E）＝card（E基準1），將屬于V基準1的頂點在矩陣B外進行標記；（2）在B未標記過的元素中尋找最大元素，該元素須滿足行標或列標對應的頂點已標記，且不能同時已標記，找出后將該元素進行標記，并添加到集合E中，E＝E∪｛ip，jq｝，card（E）＋＝1，并將其行標和列標對應的頂點中未標記的2個進行標記，若這2個頂點屬于D基準的某個連通子圖，則將該連通子圖對應的E基準i｜i∈｛2，3，…，h｝添加到E中，E＝E∪E基準i，card（E）＋＝card（E基準i），同時，將屬于V基準i的頂點在矩陣B外進行標記；（3）判斷是否所有的頂點都已標記，若是，則算法終止.若否，則轉步驟（2）.

第三步，根據(jù)最終得到的主動銜接關系集合E＊，繪制路網(wǎng)末班車時刻的推算關系圖T＊.

5 算例

以2.2節(jié)中路網(wǎng)為例，結合對矩陣元素和頂點的標記過程（以“□”作標記），來說明基本算法的步驟：a—b—c—d—e—f—g.

設L4下行方向為起始線路方向，那么根據(jù)E＊和線路銜接關系矩陣，可得到以v42為樹根的路網(wǎng)末班車時刻推算關系圖T＊，如圖3a所示.由于換乘客流量數(shù)值彼此不同，線路銜接關系與換乘客流量是一一對應的，所以根據(jù)E＊和T＊，對照換乘客流量表，可得到表2所示的路網(wǎng)末班車時刻推算關系表.

若運營者指定銜接關系｛換乘站d的L4上行→L3下行，換乘站a的L3下行→L1下行｝必須成立，那么利用改進算法可得到主動銜接關系集E′＊＝，及圖3b所示的最優(yōu)生成樹T′＊.

圖3 路網(wǎng)末班車時刻的推算關系圖Fig.3 The calculation relationship graph of the last trains in urban mass transit network

表2 路網(wǎng)各線路方向的末班車時刻推算關系表Tab.2 The calculation relationship Table of all the last trains in urban mass transit network

6 結語

為了提高網(wǎng)絡化運營條件下城市軌道交通客運服務水平，運營管理部門應在準確把握路網(wǎng)客流特點的基礎上，協(xié)調優(yōu)化網(wǎng)絡末班車計劃，促成各線末班車在換乘站的合理銜接.本文基于乘客的換乘需求及運營者的特定銜接需求，提出了網(wǎng)絡末班車銜接方案優(yōu)化模型和算法，通過該算法可最終得到以某個指定起始線路方向為基礎的網(wǎng)絡末班車時刻推算關系表，基于該推算關系表，設定起始線路方向的末班車始發(fā)時刻，依據(jù)列車區(qū)間運行時分、停站時分、換乘銜接時間，可逐步推算其余各線路方向的末班車在主協(xié)調換乘站的到發(fā)時刻，既而計算出末班車的始發(fā)時刻及在所有車站的到發(fā)時刻，則最終得到基于網(wǎng)絡整體優(yōu)化的末班車銜接時刻表.本算法的適用性強，可以輔助城市軌道交通網(wǎng)絡的末班車計劃編制.

[1] Younan B J.Improving transit service connectivity：the application of operations planning and operations control strategies [D]. Cambridge： Department of Civil and Environmental Engineering of Massachusetts Institute of Technology，2004.

[2] Lee K T.Optimization of timed transfers in transit terminals[D].College Park：University of Maryland，1993.

[3] Ting C J.Transfer coordination in transit network[D].College Park：University of Maryland，1997.

[4] Chung E H.Transfer coordination model and real－time strategy for inter－modal transit services[D].Toronto：Department of Civil Engineering of University of Toronto，2009.

[5] 徐瑞華，張銘，江志彬.基于線網(wǎng)運營協(xié)調的城市軌道交通首末班列車發(fā)車時間域研究[J].鐵道學報，2008，30（2）：7.XU Ruihua，ZHANG Ming，JIANG Zhibin.Study on departure time domain of the first and last trains of urban mass transit network based on operation coordination [J].Journal of the China Railway Society，2008，30（2）：7.

[6] 羅欽，徐瑞華，江志彬，等.基于運行圖的軌道交通網(wǎng)絡動態(tài)可達性研究[J].同濟大學學報：自然科學版，2010，38（1）：72.LUO Qin，XU Ruihua，JIANG Zhibin，et al. Dynamic accessibility of urban mass transit network based on train diagram[J].Journal of Tongji University：Natural Science，2010，38（1）：72.

[7] 龔劬.圖論與網(wǎng)絡最優(yōu)化算法[M].重慶：重慶大學出版社，2009.GONG Xun.Graph theory and network optimization algorithm[M].Chongqing：Chongqing University Press，2009.