劉洪宇 渠 華

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

引言

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

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

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

1 相關工作

1.1 強化學習

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 車輛巡游

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

圖1 行駛獎勵計算示意圖

1.2.1 線路結構屬性

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

1.2.2 所經(jīng)道路情況

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

1.2.3 周邊POI 分布

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

2 算法示例

2.1 數(shù)據(jù)概況

研究區(qū)數(shù)據(jù)由實際道路抽象得來，其示意圖如圖2 所示。

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

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

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

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

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

2.2 實驗設計

2.2.1 獎勵設置

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

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

表1 獎勵矩陣設置方案

2.2.2 Q 表更新

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

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

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

2.2.3 結果與討論

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

圖3 迭代步數(shù)與Q 值變化

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

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

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

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

3 總結

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