基于空間數據挖掘的巡游巴士路徑規劃與推薦

劉洪宇 渠 華

（鄭州天邁科技股份有限公司，鄭州 450000）

引言

在城市生產生活中，公交出行在滿足市民日常出行需求、改善交通狀況和環境質量方面扮演著重要角色。當前，公眾出行服務的格局正在發生深刻變革，公交企業需要通過智能化技術手段，在為乘客提供個性化、便捷化的高品質服務的同時，提高公交服務的運營效率，促進城市公共交通的高質量發展。

可以認為，需求響應式公交需要解決兩個方面的問題，一是出行需求的空間覆蓋，解決有沒有公交的問題；二是出行需求的時間覆蓋，解決即時出行的問題。本文重在解決第一類問題。公交線路的布設可以抽象為線路規劃問題，以迪杰斯特拉為代表的最短路徑算法、以群體智能算法為代表的啟發式搜索[1-3]和以Q-learning 為代表的強化學習算法是3 類主要的路徑規劃算法。其中強化學習算法以其強大的環境探索能力成為眾多領域的研究熱點。在水上路徑規劃領域，王程博等[4]采用Q-learning算法，基于自定義分段獎勵函數構建了船舶避障并到達目的地的仿真系統；衛玉梁等[5]基于Q-learning算法，采用函數擬合能力較強的RBF（Radial Basic Function）函數對動作價值進行逼近，從而完成智能車輛在行動過程中的避障。彭理群等[6]在公交路徑規劃中基于Q-learning 算法，綜合考慮道路擁堵情況、站點客流人數等進行獎勵函數的設計，確定了定制公交線路的規劃方法。

由以上可知，Q-learning 算法在公交領域的應用，傾向于行駛過程中的避障，并不太關注行駛過程中的獎勵情況，這在公交領域并不特別符合實際情況[7-8]。本文在考慮公交線路結構特征、途經道路特征和周邊環境的基礎上，設定Q-learning 算法的獎勵規則，實現需求響應式公交線路的規劃。

1 相關工作

1.1 強化學習

強化學習（Reinforcement Learning，RL）是機器學習的范式和方法論之一，用于描述和解決智能體（agent）在與環境的交互過程中，通過學習策略達成回報最大化或實現特定目標的問題。強化學習算法在一定程度上具備解決復雜問題的通用智能。其在路徑規劃、游戲AI 等領域有著廣泛的使用場景和應用前景。

不同于一般意義上的路徑導航，巡游巴士是沒有終點或者目的地的。抽象到基于強化學習的路徑規劃場景下，即智能體活動沒有明確的結束條件，智能體能夠到達任意位置，這等價于智能體從任意位置出發，最終出現在起始點。結合Q-learning 算法，對其核心過程描述如下：

（1）初始化Q 表和R 矩陣。分別表示車輛從當前路段行駛到下一個路段的預期收益和即時獎勵。

（2）確定尋路的終點target，該場景下為車輛的出發點。

（3）在圖中隨機起點source，不同于target。

（4）確定source 的鄰居節點nears，如果nears不存在，回到步驟2。

（5）生成隨機變量alpha，比較alpha 和預設值greedy，如果alpha ＜greedy，選擇獎勵值最大的節點作為下一個節點，否則，從nears 中隨機選擇一個節點，記為next。

（6）基于source →next 通行人數，確定獎勵值R(s, n)。

（7）確定next 節點到鄰居節點的最大Q值，記為max(Q(n, *))。

（8）根據式（1）更新source →next 的Q值：

如果next 為target，本次尋路完成，回到步驟2，進行下一次尋路；如果next 不等于target，令source=next，回到步驟3，尋找下一段路徑。

（9）如果到達預設的訓練次數或者Q不再變化，停止訓練過程。

（10）根據以上迭代過程，確定圖中各個邊的權重，然后參考最短路徑或者根據每個節點最大出行方向得到圖中各個點到target 的最優路徑。

Q 表可以初始化為零方陣，真正影響算法結果是獎勵的設置，即R 矩陣。

1.2 車輛巡游

巡游巴士在行駛過程中的駕駛行為、所經道路周邊環境都會對駕乘人員和運營效益產生重要影響。本方法從線路屬性、所經道路等級、周邊POI（興趣點）分布等方面綜合提取巡游巴士行駛特征，從而完成路徑規劃。其整體思路如圖1 所示。

圖1 行駛獎勵計算示意圖

1.2.1 線路結構屬性

線路結構及屬性是巡游巴士運營效果最直接的影響因素。比如線路長度、公交站點數量、公交站點類型（港灣式、半港灣式等）等；另外，線路的轉彎次數以及對應的轉彎類型（左轉、右轉等）都對巡游巴士的運營和體驗有影響。

1.2.2 所經道路情況

一般的，公交線路所經過路段的等級（主干道、次干道等）、車道數以及公交專用道的設置情況都會對公交線路通行的難易程度產生影響。在大型、特大型城市，隨著公交都市建設以及公交優先理念的影響，在道路條件具備的情況下，公交專用道設置較為完善，具體表現為，主干道和次主干道都有對應的BRT 車道或公交專用道，而其他城市公交專用道較少設置。

1.2.3 周邊POI 分布

醫院、學校、商圈等區域人員流量大、交通情況復雜，對巡游巴士運營同樣有著較大影響，比如高峰堵車通常都發生在這些區域。所以這里提取線路周邊重點類型POI 數量，從而量化POI 對巡游巴士路徑選擇的影響。比如，以線路為中心，分別統計線路周邊30m、100m、200m 的醫療單位數量，作為衡量公交班次通行難易程度的特征。

2 算法示例

2.1 數據概況

研究區數據由實際道路抽象得來，其示意圖如圖2 所示。

道路數據共有路段531 條，道路交叉點317 個。東西走向約11km，南北寬在7km 左右。另有研究區內的POI 數據1 萬余條，包括超市、學校、企業單位等各種類型。

對強化學習而言，Q 表是最終結果的體現，而獎勵規則的設計是強化學習成功與否的關鍵。在車輛出行過程中，行駛方向、道路屬性、周邊環境是考慮的核心因素。

行駛方向：常見的動作包括直行、右轉、左轉和調頭四種類型，在無目的地的車輛巡行過程中，認為直行和右轉有更多的選擇傾向，而左轉和調頭因為不利于公交車操作，成為規避行駛方向的可能性更大。

道路屬性：常見的城市道路有快速路、主干道、次干道和普通道路，快速路因其無紅綠燈設置，通行能力和通行體驗都是最好的，一般情況下，可以使用快速路、主干道、次干道、普通道路的順序為道路的通行體驗排序。

POI：興趣點的類型和多少是構成局部區域交通吸引量的重要因素。學校、商場、工業園區是常見的高吸引性POI 類型。值得一提的是，工業園區的交通吸引量有明顯的時間相關性，而商場、公園等時間相關性要弱得多，體現為前者交通吸引量隨時間變化較大而后者相對較小。POI 的類型復雜，量化較為困難，這里采用POI 的數量進行衡量。

2.2 實驗設計

2.2.1 獎勵設置

結合上述描述，從三個角度分別設置獎勵函數，研究獎勵方案對最終路徑的影響。

從表1 可以看出，3 種獎勵方案在結構特征上的設置完全相同，在道路特征方面，方案1 與后兩者有差異，具體表現為快速道路的獎勵值不同，這是為了區別兩種不同的行車目的，如以送客優先和以載客優先為目的的行車，因快速道路通行能力強、行車體驗佳，方案1 給予最大的獎勵取值，而由于快速道路鮮有乘客出現，在后兩個方案中給予最小的獎勵。在POI特征方面，為了更好地量化該維度特征，對POI 數量進行了處理，其中N表示智能體從當前位置所能到達的所有路段周圍的POI 數量總和，n表示當前路段周圍的POI 數量。值得一提的是，方案3 對POI 數量獎勵進行了放大，目的是確認通過調整獎勵，來引導出行路線或者加快算法收斂。

表1 獎勵矩陣設置方案

2.2.2 Q 表更新

Q 表的更新是以Q-learning 為代表的值迭代強化學習算法的重要過程。根據強化學習的算法流程，核心的更新公式如下：

式中： 表示從路段s到路段t的綜合獎勵，Reward表示即時獎勵，即行駛過程中，道路屬性、轉向和POI 所得到的獎勵，α和β分別表示學習率和獎勵折扣，實際計算中，兩者都取值為0.8。

在指定出發路段的基礎上，進行算法的訓練。以Q 表與之前步驟的差異（以Q值的相關系數衡量）作為算法終止的條件（如R2＞0.95）。分別記錄不同獎勵方案在不同步驟下的Q 表值，最后基于Q 表，確定獎勵最大的出行路徑。

2.2.3 結果與討論

Q-learning 算法訓練過程是一個值迭代的計算過程，一般的，其迭代終止條件是Q 表不再發生變化，這對一個較大的系統而言，可能大大降低其訓練速度。為了尋找合適的迭代次數，通過多輪迭代實驗，分別生成各自不同訓練步數下的Q 值，通過Q 表值的相關系數來衡量Q 表的變化情況。圖3 記錄了以50 輪為步長，當前Q值與之前Q的相關系數平方的變化。

圖3 迭代步數與Q 值變化

從圖3 可以看出，隨著迭代次數的增加，當前Q值與之前Q值的相關系數越來越大，也就是說，Q 表的變化是逐漸變小的，在實驗場景下，當前Q值與50 輪之前Q值相關系數的平方在500 步之后，滿足退出條件。

獎勵方案的不同會影響路徑規劃結果，圖4 展示了三種獎勵方案下的路徑規劃效果。值得提出的是，為了避免路徑規劃時頻繁調頭的現象，這里在基于最大獎勵獲取路徑時，禁止回到已經經過的路段。

圖4 三種不同獎勵方案下的路徑規劃結果示意圖

由圖4 可知，方案1（紫色路徑）在路徑生成過程中，右轉的現象非常明顯，這與獎勵方案設置時右轉權重最大呈現正相關關系；對于方案2（紅色路徑），可以看出在常規路段，依然存在右轉的趨勢，不同于方案1 的是，在主干道上能夠保持直線前進；對于方案3（黃色路徑），可以看出路徑是向著POI 集中區域延伸的。綜上可知，獎勵方案會影響強化學習路徑的規劃結果，可以通過調整獎勵方案，為多種出行目的打造對應的路徑規劃方案。

3 總結

本文基于GIS 數據分析和挖掘確定巡游巴士的路徑規劃獎勵方案，采用Q-learning 算法，對比了不同獎勵方案的路徑規劃結果。實驗結果表明，可以通過設置不同的獎勵機制，來影響算法的路徑規劃效果。