考慮個性化出行需求的多模式公交路徑規劃

王志建，劉士杰，周錦瑤，孫 健

（1.北方工業大學電氣與控制工程學院，北京 100144；2.北京航天測控技術有限公司，北京 100041）

多模式交通系統將不同的出行方式連接在一起，通過結合每種方式的優點，既滿足了乘客不同的出行需求和偏好，又提高了便捷性，具有較大提升潛力[1].國內外許多學者對多模式交通多目標路徑規劃的模型及求解算法開展了大量研究.陳海鵬等[2]從時間、費用角度出發，構建了實時環境下多目標的路徑選擇模型.付旻[3]利用不同公交模式的交通特性和網絡結構特點，構建了公交超級網絡模型.黃明華等[4]考慮高峰時段乘客聚集的影響，基于非線性規劃方法，構建了以網絡總換乘等車時間最短為目標的數學模型.張瑞兵[5]考慮城際多模式出行的多個影響因素，提出了一種基于歷史訂單數據的個體出行偏好挖掘方法，用于計算不同出行個體的權系數.Idri等[6]提出了一種基于時刻表的多模式交通最短路徑算法.Dib等[7]設計可變鄰域-遺傳算法求解多模式交通多目標路徑規劃問題.趙婷等[8]研究了換乘次數等3種約束條件下，以實際出行成本最少為優化目標的多模式交通路徑決策問題，并提出了基于模擬退火-遺傳算法的4種求解策略.李浩楠等[9]考慮到時間的波動性與突發事件的影響，建立了基于馬爾可夫決策過程的多模式交通路線決策模型與算法.賴元文等[10]設計模擬退火-自適應布谷鳥算法求解基于不同利益方權重下的公交調度問題.

綜上，國內外學者在多模式交通路網模型的構建上，考慮到了實際路網的時變特性，但時刻表的建立基于固定發車時刻、固定運行速度等方式，無法準確地計算行程時間.在數學模型的構建上，以約束條件的形式將多目標求解轉化為單目標求解問題，可能會導致計算結果出現無解的情況.在求解算法的研究上，目前主要集中于將幾種元啟發式算法組合到一起來解決單一目標的優化問題，無法為具有多個出行需求的乘客提供個性化的出行方案.因此，本文利用IC卡數據建立了一個多模式公交路網模型，并提出一種基于乘客多種出行需求的評價值模型，將真實的路網數據應用到上述模型中，同時，設計一個改進遺傳算法對模型進行求解，并與使用較廣的模擬退火-遺傳算法（simulated annealing-genetic algorithm，GA-SA）進行對比分析.結果表明本文算法在所得出行方案的質量、尋優效率和迭代次數上更優.

1 建模方法

1.1 城市多模式交通網絡

本文利用包含交通站點、交通站臺、交通線路和多組旅程的圖對多模式交通網絡進行建模，該方法建模的關鍵是將每一種交通方式表示為一個獨立的有向圖，然后將所有的子圖集成到一個統一的圖中.對于一個有向網絡N= (S,P,J,M)，其中：S為站點集，用于乘客換乘；P為站臺集，用于乘客等候車輛，每個站臺和所對應的站點相連；J為旅程集，是某種交通線路在特定的時間沿著特定的路線訪問站臺的車輛集；M為交通線路集.圖1所示為一個包含4個站點、7個站臺、8組旅程以及2種交通線路的小型多模式交通網絡.

圖1 城市多模式交通網絡Fig.1 Urban multimodal transit network

1.2 模擬公交時刻表

公交系統的運行易受到道路網絡的時變特性影響，無法通過傳統時刻表準確地計算行程時間.因此，為提高路徑規劃方案對應的時間計算精度，本文利用IC卡刷卡數據模擬公交時刻表.具體步驟如下：

步驟1首先對刷卡時間進行升序排列，設卡號為b的公交司機在站臺編號為Q的第i次刷卡時間為DbQ,i，V為這位司機單次運行的刷卡總次數.則站臺Q的刷卡時間間隔集TbQ為

步驟2對刷卡時間進行聚類，當兩個刷卡時間間隔DbQ,i+1?DbQ,i≤72 s時，保留DbQ,i，否則剔除.設n為保留的時間點個數.

步驟3計算公交車在站臺Q的離站時刻tQ，如式（2）所示.

步驟4如果n≤3，則通過站點間距和公交車運行速度來估計離站時刻.

地鐵線路運行比較獨立，運行時不受干擾，因此，根據地鐵運營公司給出的時刻表便可準確地計算行程時間.

1.3 數學模型

基于乘客的4種出行需求，分別建立各單一目標下的數學模型.

以出行時間為目標函數的數學模型如式（3）所示.

式中：Tjnl為出行總時間；tj為乘客在站臺j處的等待時間，j∈P；t(j,k),λ(a)為乘客在時刻a從站臺j出發選擇交通線路 λ到達站臺k所花費的行程時間，k∈P，λ∈M；tj,(λ,θ)為乘客在站臺j處由交通線路 λ換乘交通線路 θ所花費的換乘時間，θ∈M；x(j,k),λ為站臺j到站臺k是否選擇交通線路 λ，若是，則x(j,k),λ=1，否則，x(j,k),λ=0；xj,(λ,θ)表示是否在站臺j處由交通線路，λ換乘交通線路 θ，若是，則xj,(λ,θ)=1，否則，xj,(λ,θ)=0.

以出行成本為目標函數的數學模型如式（4）和式（5）所示.

式中：Cjnl為出行總成本;C(j,k),λ(f)為乘客從站臺j到站臺k采用交通線路 λ經過里程數f所花費的票價；Cq為第q段里程（里程數區間為(fq?1，fq]）所花費的票價.

以換乘次數為目標函數的數學模型如式（6）所示.

式中：Njnl為出行總換乘次數.

以步行距離為目標函數的數學模型如式（7）所示.

式中：Djnl為出行總步行距離；dj,k為站臺j到站臺k的步行距離.

2 算法設計

遺傳算法是模擬生物進化過程的計算模型，以其評價值簡單、隨機性強、可群體搜索等特點，應用于大量多目標最優化的問題中.但其計算結果對初始種群具有一定的依賴性，并且易陷入局部最優解.深度優先搜索算法[11]可遍歷到包含自身的所有起終點路徑，且不會重復訪問相同節點，二者的結合可在確保初始種群可行性的前提下，提高尋優能力，使得算法跳出局部最優解.因此，本文提出了深度優先搜索-遺傳組合算法（depth first search-genetic algorithm，GA-DFS）來實現多模式公交多目標的路徑規劃.

2.1 算法步驟

算法的具體步驟如下：

步驟1將路網中所有多模式公交站臺進行編碼；

步驟2應用深度優先搜索算法隨機產生初始種群；

步驟3計算各個單一目標下，種群中所有方案對應的函數值；

步驟4把同一方案不同出行目標下的函數值進行無量綱化處理，并基于用戶的出行需求賦予權重，通過線性加權法得到出行總評價值；

步驟5判斷是否收斂或達到迭代次數，是則輸出最優值，否則轉步驟6；

步驟6進行父代選擇、單點交叉和基于深度優先搜索算法的變異操作，生成子代種群.再次判斷是否收斂或達到迭代次數，是則輸出最優解，否則轉步驟6，直至滿足終止條件.

2.2 編碼設計

遺傳算法中的每個染色體表示起、終點間一個潛在的出行方案，針對本文建立的多模式公交網絡，對染色體分兩層進行編碼，現以一個起點站臺為1，終點站臺為7的出行方案為例進行闡述，如圖2所示.第一層編碼{1, 2, 3, 4, 5, 6, 7}表示公交網絡中的站臺編號，第二層編碼{1, 1, 1, 1, 1, 1}表示各個站臺間是否連通，若連通，則編碼為1，否則，編碼為0.

圖2 編碼示意Fig.2 Coding schematic

2.3 初始種群

初始種群中的每個出行方案應避免出現回路和無效路徑.為解決上述問題，本文采用深度優先搜索算法進行初始種群的生成.方法如下：

步驟1基于城市公共交通網絡建立鄰接矩陣；

步驟2把起始站臺放入數組中，設為當前站臺；

步驟3擴展當前的站臺，產生一個新的鄰近站臺放入數組，同時把新產生的站臺設為當前站臺；

步驟4判斷當前站臺是否與數組中的站臺相重復，如果重復則返回上一個站臺，產生它的另一個鄰近站臺；

步驟5判斷當前站臺是否為目標站臺，如果是，則找到一個初始個體，結束算法，否則，轉步驟3.

2.4 評價與選擇

路徑規劃方案的選擇操作選用出行總評價值Asum描述候選個體的適應值，由于初始種群以及迭代過程中的每一代種群是否包含最優個體是未知的，因此，本文采用動態閾值化法進行無量綱化處理，如式（8）～ （11）所示.

式中：Asingle為無量綱化后的指標評價值；omax為種群中每一代單一指標下的最大值；omin為種群中每一代單一指標下的最小值；rreal為指標的實際值；Auv為出行需求為u的第v個個體經無量綱化處理的結果，u= 1, 2, 3, 4，v= 1,2,···,H，為種群中個體的總數；ξT、ξC、ξN、ξD分別為出行時間、出行成本、換乘次數、步行距離對應的權重系數.

乘客可根據自己的個性化需求進行選擇，且每個出行需求之間為平行目標，選擇方式為輪盤賭.

2.5 交叉操作

本文采用具有相同站臺的單點交叉方法，如圖3所示.現以兩個起點站臺為1，終點站臺為13的出行方案為例進行闡述.具體的操作步驟為：隨機選擇兩個父代個體P1、P2作為交叉個體；遍歷搜索父代個體中的相同站臺9、10、11，若存在多個相同的站臺，則隨機選擇一個站臺作為交叉點進行交叉操作，本例中選擇站臺11；保持P1中交叉點11之前的序列{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}不變，將P2中交叉點11之后的序列{33, 34, 35, 36, 13}與之相組合形成子代S1；保持P2中交叉點11之前的序列{1, 28,29, 9, 10, 11}不變，將P1中交叉點11之后的序列{12, 13}與之組合形成子代S2.

圖3 交叉操作Fig.3 Cross operation

若在進行交叉操作后，子代個體出現了重復的基因或片段，這表明新產生的子代個體出現了回路，應當予以消除，同時將父代個體保留至子代.

2.6 變異操作

經交叉操作產生的子代個體與未發生交叉操作的父代個體組成一個新的種群，再進行變異操作.由于交叉操作可能產生退化種群，由此導致算法陷入局部最優解.因此，為了跳出局部最優解，尋找全局最優，本文提出了一種新的變異方法，基于深度優先搜索算法的兩點變異方法，讓變異定向地向著乘客出行需求的方向進行變異，如圖4所示.

圖4 變異操作Fig.4 Mutation operation

具體的變異過程為：在父代的個體P1中隨機產生兩個不同的站臺作為變異點，本例中為站臺1和站臺9；將變異點1、變異點9分別設置為起、終點，利用深度優先搜索算法尋找兩變異點間所有的路徑片段{1, 28, 29, 9}、{1, 2, 3, 4, 5, 6, 7, 8, 9}、{1, 37,38, 39, 5, 14, 15, 16, 17, 18, 19, 20, 9}，分別計算所有路徑片段的基于乘客個性化需求的出行總評價值V1= 0.91、V2= 0.83、V3= 0.75，將評價值最大的路徑片段{1, 28, 29, 9}作為兩變異點之間的新路徑片段，與父代P1變異點9之后的序列{10, 11, 33, 34, 35,36, 13}相組合后形成子代個體S1.

3 數值實驗

本文實驗基于某市區的真實路網數據對GADFS算法進行驗證，并將GA-DFS算法與GA-SA算法[8]進行比較.數據由區交通委提供，路網實例如圖5所示，圖中數字所示為站點編號.數據包括兩種交通方式（公交、地鐵）的地理位置信息以及對應的IC卡刷卡數據信息.更準確地說，數據包括2條地鐵線路、4條公交線路、48個站臺、321條起終點路線、1110組旅程.

圖5 城市多模式交通網絡實例Fig.5 Case of urban multimodal transit network

首先，選取路網節點中的站臺38和站臺39進行模擬時刻表可行性實驗.IC卡刷卡信息選取的是2017年3月13日382路公交車的刷卡數據，如表1所示，其中，站臺38和站臺39的實際到站時刻依次為表中黑體數據，對應的傳統時刻表信息和本文模擬時刻表信息如表2所示.傳統的時刻表基于固定運行速度、固定站點間距求得，受早高峰時段路網的時變特性影響，造成到站時刻不準確.本文的模擬時刻表方法，基于實際的刷卡數據，2個站臺到站時刻的精度分別提升了94%和98%.

表1 IC卡刷卡數據Tab.1 IC card data

表2 傳統時刻表和模擬時刻表Tab.2 Traditional timetable and simulated timetable

通過假設3種不同出行需求的出行場景，設置不同權重系數，得到不同的推薦路徑規劃方案，驗證說明本文算法在乘客選擇不同出行需求時提供的路徑規劃方案更優.場景一，乘客為一名旅游度假人員，出行需求為：出行成本低、換乘次數少；場景二，乘客為一名上班通勤人員，出行需求為：出行時間短、換乘次數少；場景三，乘客為一名購買生活必需品的通勤人員，出行需求為：出行成本低、步行距離短.

現某名乘客在8：00從起點1出發到終點13，分別給出3種場景對應的路徑規劃方案.

種群規模為30，最大迭代數為50次，通過MATLAB軟件編程計算，不斷調整交叉概率（probability crossover，PC），變異概率（probability mutation，PM）后，連續運行10次，得到對應方案的平均出行時間（average travel time，ATT）、平均換乘次數（average travel number，ATN）、平均出行成本（average travel cost，ATC）、平均步行距離（average walk distance，AWD）和達到穩定時所需的平均迭代次數（average iteration，AI）.

在PC為0.9，PM為0.10且相同初始種群條件下，不同場景的GA-DFS、GA-SA算法迭代過程各參數結果見圖6～ 8，相同場景下，GA-DFS算法達到穩定時所需的迭代次數更少.

圖6 場景一下相同遺傳參數的算法對比Fig.6 Comparison of algorithms with the same parameters under scene one

圖7 場景二下相同遺傳參數的算法對比Fig.7 Comparison of algorithms with the same parameters under scene two

改變遺傳參數和出行場景，GA-DFS和GA-SA算法各參數結果見表3.以場景一為例，當PC為0.9，PM為0.10時，GA-DFS、GA-SA算法的AI分別為17.80、30.62次，ATC分別為0.96、1.76元，ATN分別為1.2、2.2次.與GA-SA算法相比，GA-DFS算法AI減少了42%，計算效率更高，更有效節約時間成本.

表3 不同出行場景下的算法對比Tab.3 Comparison of algorithms under different scenarios

在場景一的背景下，PC為0.9，PM為0.10時，改變種群規模的大小，GA-DFS、GA-SA算法參數結果見表4.GA-DFS算法在種群規模為60時，基本上每次計算都可以找到最優解（ATC為0.80元，ATN為1.0次），GA-SA算法則需要種群規模達到120時才可以找到最優解，由此可見，與GA-SA算法相比，GA-DFS算法的尋優效率提高了50%，更適用于應用在實際路網中.

圖8 場景三下相同遺傳參數的算法對比Fig.8 Comparison of algorithms with the same parameters under scene three

表4 相同參數、不同種群規模在場景一下的算法對比Tab.4 Comparison of algorithms with the same parameters and different population sizes under scene one

根據本文多目標路徑規劃算法的原理分析可知，針對遺傳算法對初始種群具有一定的依賴性的問題，本文采用基于深度優先搜索算法的產生策略，利用其不重復訪問節點特性，保證初始種群中無回路和無效路徑，有效降低了算法的平均迭代次數，節約了計算的時間成本；針對遺傳算法的易陷入局部最優解的特點，本文創新地提出了基于深度優先搜索算法的兩點變異法，利用深度優先搜索算法的遍歷性，在進行變異操作時，產生變異點間所有可能的路徑片段，通過計算路徑片段的適應值，選擇適應值較大的路徑片段進行拼接，讓變異定向地向著乘客個性化出行需求的方向進行，有效地改善了算法的全局搜索能力，使得給出的路徑規劃方案更優.

通過GA-DFS算法的求解，得到3種出行場景下的最優路徑方案.場景一的最優路徑：1→28→29→30→31→32→33→34→35→36→13；場景二的最優路徑：1→2→3→4→5→6→7→8→9→10→11→12→13；場景三的最優路徑：1→28→29→30→31→32→33→34→35→36→13.場景一與場景三所示最優路徑，對應的換乘次數和步行距離均為本網絡中的最小值，因此出現相同的推薦路徑.

4 結 論

1）本文在多模式交通出行的背景下，以乘客個性化的出行需求為目標，同時考慮路網的時變特性影響，建立了基于模擬時刻表的多模式公交路網模型和數學模型，并設計了一個基于乘客多出行需求的路徑規劃求解算法.

2）所提出的模型和算法，能夠根據乘客的多種出行需求提供對應的路徑規劃方案，其有效性在以某市區為實例背景的算例中得到驗證，相比已有的研究，可以提供更優的路徑規劃方案和更高的尋優效率，適用于規模較大的路網.

3）未來可對算法框架進行改進，以提高求解效率；此外，還將對其他出行方式（如網約車、共享單車等）進行研究，以提供更加多樣化的多模式交通路徑規劃方案.

致謝：北方工業大學“毓優人才”項目（213051360020 XN173/013）的資助.