徐海軍，趙 靖 （上海理工大學(xué) 管理學(xué)院，上海 200093）

XU Haijun,ZHAO Jing (Management School,University of Shanghai for Science and Technology,Shanghai 200093,China)

0 引言

公共汽車交通出行是一種綠色高效的出行方式[1-2]，但由于城市公交線路走向和站點分布的復(fù)雜性，如何尋找最為便捷快速的公交出行方案，成為城市居民和外地旅客在使用公交出行中最為關(guān)注的問題[3]。因此，有必要采取合適的方法為公交乘客選擇合理的乘車線路和換乘站點，以提高公交出行效率。

由于公交系統(tǒng)由站點和線路構(gòu)成，在運營中存在共線運行，使得公交出行路徑選擇與小汽車交通相比，有其顯著的特點。主要體現(xiàn)在出行者并不在意具體的行駛路徑，甚至不拘泥于乘坐的線路，相比小汽車交通無法同時嘗試兩條不同的線路，在公交共線運行區(qū)段，公交出行者可在換乘站選擇多條均可到達(dá)目的地的線路中最先到達(dá)的公交線路。

本研究將針對公交系統(tǒng)的這一特征，考慮站點及共線運行，建立公交出行路徑選擇模型。

1 相關(guān)研究綜述

關(guān)于公交乘客出行路徑選擇的方法主要有以下三類：（1）基于傳統(tǒng)小汽車交通出行最短路徑算法。這類算法是研究路網(wǎng)中兩點間阻抗最小的路徑，針對小汽車交通，有包括Di jkstra算法、Floyd-Warshall算法等經(jīng)典算法[4]。在此基礎(chǔ)上，后續(xù)研究從駕駛員偏好、多任務(wù)點以及緊急救援等方面，提出了一系列改進算法[5-7]。基于小汽車出行最短路徑算法，李文勇[8]針對于公共交通利用Di jkstra算法通過線路激素強度的更新機制，實現(xiàn)了以換乘次數(shù)最少和公交出行站點最少的公交出行路徑選擇優(yōu)化目標(biāo)。許倫輝[9]基于蟻群系統(tǒng)中對最優(yōu)路徑信息素的加強和對次優(yōu)路徑信息素的揮發(fā)并行正反饋的機制，設(shè)計出求解公交出行最優(yōu)選擇路徑算法。（2）基于圖論的公交出行最短路徑選擇算法。這類算法將公交系統(tǒng)抽象建模成一個以公交站點為節(jié)點、以線路為連線的圖，基于圖論搜尋公交出行換乘方案。A?ez首先提出的二重圖公交網(wǎng)絡(luò)模型[10]。蘇愛華[11]針對公交網(wǎng)絡(luò)換乘問題構(gòu)造了公共交通網(wǎng)絡(luò)模型，將站點及經(jīng)過這些站點的線路構(gòu)成換乘矩陣進行搜索。楊新苗[12]利用了地理信息系統(tǒng)（GIS）中站臺聯(lián)接邊表，通過公交站臺表以及站臺經(jīng)過線路表示公交網(wǎng)絡(luò)，并且用GIS方向估價函數(shù)搜索節(jié)點的相鄰站點，建立了公交乘客出行路徑選擇模型。傅冬綿[13]把圖論中針對單個節(jié)點的廣度優(yōu)先搜索思想推廣到擁有若干個節(jié)點集合的廣度優(yōu)先搜索，提出了換乘最少路徑選擇算法。（3）考慮換乘次數(shù)、換乘等待時間和票價等綜合因素的公交出行路徑選擇算法。Nicholas[14]提出了公交網(wǎng)絡(luò)靜態(tài)多路徑選擇算法，其中以換乘次數(shù)最少為第一目標(biāo)，出行距離最短為第二目標(biāo)。Jolliffe[15]研究得出換乘等待時間的隨機性隨公交車發(fā)車時間間隔的增加而降低?；诖耍罄m(xù)研究人員建立了一系列考慮換乘等待時間的路徑選擇模型[16-18]。趙巧霞[19]建立了以換乘次數(shù)最少為主要目標(biāo)，途經(jīng)站數(shù)最小為次要目標(biāo)的最優(yōu)路徑出行模型。并設(shè)計了廣度優(yōu)先算法。何勝學(xué)[20]考慮了公交線路票價的變化對乘客出行路徑的選擇的影響，并且對等車時間進行了量化改進，以降低算法的復(fù)雜度。

綜上所述，基于小汽車交通最短路徑算法，結(jié)合公交線網(wǎng)，研究人員建立了一系列綜合考慮了換乘次數(shù)、出行時間等因素的公交出行路徑選擇模型。但現(xiàn)有方法多以單個公交線路及換乘出行鏈為搜索目標(biāo)，將不同的公交線路作為不同的公交出行路徑方案進行比選，忽略了公交共線運行這一常見特征。而實際乘客出行中當(dāng)兩站點間存在多條公交線路時，會選擇最先到達(dá)的線路。因此，有必要改進以往算法中將不同公交線路完全作為競爭關(guān)系的處理方法，考慮共線運行時不同公交線路的合作關(guān)系，從而給乘客提供更為合理、全面的公交出行路徑。

本文以此為切入點，為解決以往未考慮公交共線運行，造成公交線路選擇不合理的問題，提出了一種基于站點及共線運行的公交乘客出行路徑選擇方法，通過搜尋合理的換乘站點，將途經(jīng)站點間的所有共線公交線路作為乘客可乘坐的線路。

2 模型構(gòu)思

從上述文獻綜述看出，以往研究中公交出行路徑多以單個公交線路及換乘出行鏈為搜索目標(biāo)，將不同的公交線路作為不同的公交出行路徑方案，分別計算出行時間，進行比選。如圖1所示，由起點A至終點F備選的公交出行方案包括：（1）R1線換乘R3線，換乘點為C或D或E；（2） R1線換乘R4線，換乘點為E；（3） R2線換乘R3線，換乘點為D或E；（4） R2線換乘R4線，換乘點為E。按上述備選方案進行比選，便將不同公交線路完全作為競爭關(guān)系進行處理。

圖1 模型構(gòu)思

而實際公交乘客最合理的出行方案應(yīng)當(dāng)是在A站乘坐R1或R2線路，然后在E站換乘R3或R4線路。為此，本算法將以換乘站點選擇為基礎(chǔ)，將兩站點間的線路作為合作關(guān)系，從而最終公交出行路徑方案由最優(yōu)換乘站點及換乘站點間可選擇線路集構(gòu)成。由于在公交站點有多條線路可供選擇，大大減少了乘客等車時間，提高了公交出行的便利性和效率。

具體出行時間包括兩部分：（1）車外時間，指乘客到達(dá)站點時間和在站點等車時間，在等車時間計算中將考慮可選線路集的線路數(shù)及各線路發(fā)車頻率；（2）車內(nèi)時間，根據(jù)可選線路集中各線路行程時間，以發(fā)車頻率為權(quán)重，加權(quán)平均確定。

3 模型算法

3.1 優(yōu)化目標(biāo)

本研究以換乘次數(shù)最少為首要優(yōu)化目標(biāo)，出行時間最小為次要優(yōu)化目標(biāo)，即首先選擇換乘次數(shù)最少的路徑集，在相同的換乘次數(shù)下選擇出行時間最短的路徑。

3.2 網(wǎng)絡(luò)描述

站點層面：H表示公交站點集合；i表示公交站點，i∈H；Hj表示公交線路j沿線的站點集合，Hj?H。

公交線路層面：R表示公交線路集合；j表示公交線路，j∈R；Ri表示途經(jīng)公交站點i的線路集合，Ri?R；Ri,i'表示途經(jīng)公交站點i和站點i'的線路集合，Ri,i'?R；Rn表示第n層潛在換乘站點所有線路的集合。

3.3 算法步驟

Step 1：初始化起訖點o、d，換乘次數(shù)n=0，進入Step 2。

Step 2：確定途經(jīng)起點o的線路集合R0和途經(jīng)終點d的線路集合Rd，R0=R0，進入Step 3。

Step 3：搜尋直達(dá)線路集Ro,d，若R0|Rd=?，進入Step 4，否則進入Step 7。

Step 4：確定換乘次數(shù)和潛在換乘站點，具體步驟包括：

Step 4-1：換乘次數(shù)加1，n=n+1，進入Step 4-2。

Step 4-2：確定第n層潛在換乘站點集合Hn，如式（1）所示，進入Step 4-3。

Step 4-3：確定途經(jīng)第n層潛在換乘站點所有線路的集合Rn，如式（2）所示，進入Step 4-4。

Step 4-4：搜尋從第n層潛在換乘站點至終點的線路集，若Rn|Rd=?，返回Step 4-1，否則進入Step 5。

Step 5：記錄總換乘次數(shù)m=n，進入Step 6。

Step 6：回溯整個換乘過程，確定可行換乘站點，具體步驟包括：

Step 6-1：確定第n層可行換乘站點集Hpn，如式（3） 所示，進入Step 6-2。

Step 6-2：進入前1層，n=n-1；若n≥1，返回Step 6-1，否則進入Step 7。

Step 7：確定可行的公交出行路徑，由起始站點o，各層可行換乘站in∈Hpn的組合，以及終點d構(gòu)成，進入Step 8。

Step 8：確定各條可行公交出行路徑的出行時長，由各站點的等車時間和站點間行程時間組成，具體步驟包括：

Step 8-1：計算路徑k第n層站點至第n+1層站點的公交線路集合，如式（4）所示，進入Step 8-2。

Step 8-2：計算路徑k第n層站點的等車時間期望值。如式（5）所示，式中假設(shè)公交到達(dá)滿足泊松分布[21-23]，則乘客的等車時間服從負(fù)指數(shù)分布，公交線路單位時間發(fā)車數(shù)量為λj，進入Step 8-3。

Step 8-3：計算路徑k第n層站點至第n+1層站點的行程時間期望值，等于兩公交站點間各條線路行程時間對線路發(fā)車頻率gj的加權(quán)平均值。如式（6）所示。進入Step 8-4。

Step 8-4：計算路徑k第n層站點至第n+1層站點的出行時長Tkn，如式（7）所示，進入Step 8-5。

Step 8-5：將各站點間出行時長累加，得到各條可行路徑的出行時長，如式（8）所示，進入Step 9。

Step 9：取各條可行公交出行路徑中出行時長最小的路徑為推薦路徑，輸出結(jié)果包括各途經(jīng)站點以及可乘坐的公交線路，如圖2所示。

圖2 出行路徑方案示意圖

4 案例分析

以上海市軍工路周家嘴路交叉口至源深體育中心6號門公交出行為例，驗證模型效果。

根據(jù)本文所提出的算法，首先確定途經(jīng)起始點的公交線路有59路、103路、124路、874路、1238路，途經(jīng)終點的公交線路有130路、181路、609路、775路、785路、隧道三線，因此起訖點間無直達(dá)的線路。然后搜尋經(jīng)過起點公交線路途經(jīng)的全部公交站點，再得到途經(jīng)這些換乘站點所有線路的集合，并與途經(jīng)終點的公交線路比對，發(fā)現(xiàn)存在共同線路，因此起訖點間可通過一次換乘到達(dá)。所生成的備選方案如表1所示（列舉總行程時間最小的6個方案）。其中，方案一為最優(yōu)路徑，最優(yōu)換乘站點為羽山路南洋涇路，從羽山路南洋涇路站至終點共有5條共線線路可供選擇。

表1 案例出行路徑方案

為了進一步分析模型優(yōu)化效益，選用Di jkstra算法作為傳統(tǒng)路徑選擇模型和百度地圖作為一種較為成熟的商業(yè)路徑選擇軟件，將其與本文模型進行比較，分別如表2和圖3所示。對比發(fā)現(xiàn)本文優(yōu)化方案總出行時長較Di jkstra算法推薦方案減少19.92%，乘客在站點的候車時間減少了45.45%；較百度地圖推薦方案1和方案2總出行時長分別減少20.70%和23.39%。進一步對比發(fā)現(xiàn)，本文優(yōu)化模型通過選取合適的換乘站點，有5條線路供乘客換乘選擇（傳統(tǒng)路徑選擇模型僅提供1條），從而乘客可在該站點換乘最先到達(dá)的線路，優(yōu)化方案更具合理性。

表2 Di jkstra算法出行路徑方案

圖3 百度地圖推薦路徑

5 結(jié)論

針對公交共線運行的特征，建立了公交出行路徑選擇模型，模型具有以下特點：（1）改進以往算法中將不同公交線路完全作為競爭關(guān)系的處理方法，將換乘站點間共線運行的公交線路作為合作關(guān)系，從而減少了乘客在站點的等待時間。（2）在出行時長計算中，等車時間考慮了公交站點間所有共線線路的發(fā)車間隔，即乘客可選擇所有共線線路中最先到達(dá)的線路，有別于以往算法中僅單一線路的發(fā)車間隔；站點間行程時間，考慮了所有共線線路的行程時間的加權(quán)平均值，有別于以往算法中僅單一線路的行程時間，保障了優(yōu)化結(jié)果的準(zhǔn)確性。（3）通過案例分析，本文所推薦的公交出行路徑方案更具靈活性，尤其是當(dāng)某條公交線路發(fā)生故障或在上游阻塞后，乘客可靈活選擇其他線路，提高了出行可靠性，使模型計算結(jié)果更具合理性。

本文在建模計算中假設(shè)車輛到達(dá)站點的分布及站點間的行程時間均是確定的，但實際運行中由于交通擁堵和事故，往往存在諸多不確定性，因此可將不確定性算法分析引入本模型中，提高模型的準(zhǔn)確性，有待進一步研究。