基于空間數(shù)據(jù)挖掘的巡游巴士路徑規(guī)劃與推薦

劉洪宇 渠 華

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

引言

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

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

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

1 相關(guān)工作

1.1 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)（Reinforcement Learning，RL）是機(jī)器學(xué)習(xí)的范式和方法論之一，用于描述和解決智能體（agent）在與環(huán)境的交互過程中，通過學(xué)習(xí)策略達(dá)成回報(bào)最大化或?qū)崿F(xiàn)特定目標(biāo)的問題。強(qiáng)化學(xué)習(xí)算法在一定程度上具備解決復(fù)雜問題的通用智能。其在路徑規(guī)劃、游戲AI 等領(lǐng)域有著廣泛的使用場景和應(yīng)用前景。

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

（1）初始化Q 表和R 矩陣。分別表示車輛從當(dāng)前路段行駛到下一個(gè)路段的預(yù)期收益和即時(shí)獎(jiǎng)勵(lì)。

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

（3）在圖中隨機(jī)起點(diǎn)source，不同于target。

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

（5）生成隨機(jī)變量alpha，比較alpha 和預(yù)設(shè)值greedy，如果alpha ＜greedy，選擇獎(jiǎng)勵(lì)值最大的節(jié)點(diǎn)作為下一個(gè)節(jié)點(diǎn)，否則，從nears 中隨機(jī)選擇一個(gè)節(jié)點(diǎn)，記為next。

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

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

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

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

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

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

Q 表可以初始化為零方陣，真正影響算法結(jié)果是獎(jiǎng)勵(lì)的設(shè)置，即R 矩陣。

1.2 車輛巡游

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

圖1 行駛獎(jiǎng)勵(lì)計(jì)算示意圖

1.2.1 線路結(jié)構(gòu)屬性

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

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

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

1.2.3 周邊POI 分布

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

2 算法示例

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

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

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

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

行駛方向：常見的動(dòng)作包括直行、右轉(zhuǎn)、左轉(zhuǎn)和調(diào)頭四種類型，在無目的地的車輛巡行過程中，認(rèn)為直行和右轉(zhuǎn)有更多的選擇傾向，而左轉(zhuǎn)和調(diào)頭因?yàn)椴焕诠卉嚥僮?，成為?guī)避行駛方向的可能性更大。

道路屬性：常見的城市道路有快速路、主干道、次干道和普通道路，快速路因其無紅綠燈設(shè)置，通行能力和通行體驗(yàn)都是最好的，一般情況下，可以使用快速路、主干道、次干道、普通道路的順序?yàn)榈缆返耐ㄐ畜w驗(yàn)排序。

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

2.2 實(shí)驗(yàn)設(shè)計(jì)

2.2.1 獎(jiǎng)勵(lì)設(shè)置

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

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

表1 獎(jiǎng)勵(lì)矩陣設(shè)置方案

2.2.2 Q 表更新

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

式中： 表示從路段s到路段t的綜合獎(jiǎng)勵(lì)，Reward表示即時(shí)獎(jiǎng)勵(lì)，即行駛過程中，道路屬性、轉(zhuǎn)向和POI 所得到的獎(jiǎng)勵(lì)，α和β分別表示學(xué)習(xí)率和獎(jiǎng)勵(lì)折扣，實(shí)際計(jì)算中，兩者都取值為0.8。

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

2.2.3 結(jié)果與討論

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

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

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

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

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

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

3 總結(jié)

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