彭理群，羅明波，盧 赫，柏躍龍

(華東交通大學(xué)交通運輸與物流學(xué)院，南昌330013)

0 引 言

學(xué)者圍繞定制公交自適應(yīng)路徑規(guī)劃方法展開了研究.雷永巍等[1]針對互聯(lián)網(wǎng)定制公交線路規(guī)劃問題提出了最大需求、最小費用雙層規(guī)劃模型，采用并行遺傳算法對定制公交調(diào)度模型進(jìn)行求解.Cao 等[2]綜合考慮定制公交線路通行時間、等待時間、延誤懲罰和票價的組合人均成本最小化，結(jié)合乘客出行需求對定制公交乘客分配方案進(jìn)行優(yōu)化.Ma 等[3]針對定制公交線網(wǎng)資源分配率低的問題，提出基于旅客OD 出行需求劃分的區(qū)域聚類線網(wǎng)規(guī)劃方法，通過選擇社會效益最大化和運營成本最小化的OD對進(jìn)行匹配計算，提高了定制公交的經(jīng)濟(jì)效益.Lyu 等[4]應(yīng)用多種出行數(shù)據(jù)對公交車站位置、公交線路、時刻表、乘客選擇定制公交的概率等問題進(jìn)行優(yōu)化.以上規(guī)劃方法須通過訓(xùn)練數(shù)據(jù)來擬合模型參數(shù)，通過權(quán)重參數(shù)反映路網(wǎng)狀態(tài)的隨機(jī)性，根據(jù)相應(yīng)的算法求解規(guī)劃線路.這類參數(shù)模型的訓(xùn)練常因數(shù)據(jù)存在異常值而導(dǎo)致模型參數(shù)存在偏差，在實際模型中需要增設(shè)假設(shè)條件才能達(dá)到合理的結(jié)果，實際問題難以得到驗證.例如，Gao 等[5]通過分析離散路徑分布數(shù)量的多項式算法，指出參數(shù)數(shù)量與路段數(shù)量成指數(shù)關(guān)系，部分參數(shù)模型因為參數(shù)維度高求解效果不理想.另有學(xué)者基于非參數(shù)模型對線網(wǎng)優(yōu)化展開研究，Mao等[6]設(shè)計了一種非參數(shù)強(qiáng)化學(xué)習(xí)模型解決隨機(jī)時變網(wǎng)絡(luò)中的自適應(yīng)路徑問題.研究表明，在需求高峰期Q學(xué)習(xí)與基于樹的函數(shù)逼近相結(jié)合的性能優(yōu)于傳統(tǒng)隨機(jī)動態(tài)規(guī)劃方法.Q學(xué)習(xí)是一類高效的非參數(shù)模型[7]，通過智能體在未知環(huán)境下采取動作去探索狀態(tài)空間，并通過環(huán)境獎勵做出判斷，以解決維度高、數(shù)據(jù)需求大等問題.傳統(tǒng)的Qlearning 算法因獎勵稀疏會導(dǎo)致求解速度慢，效率低等問題.

本文基于改進(jìn)Q-learning 算法提出了一種基于勢能場的非參數(shù)強(qiáng)化學(xué)習(xí)路徑規(guī)劃方法，有效解決了城市復(fù)雜路網(wǎng)條件下路徑求解速度慢、時間長的問題.針對現(xiàn)有公交系統(tǒng)大客流跨區(qū)域出行需求及實際道路環(huán)境，提高了跨區(qū)域定制公交路徑的通行效率，通過減小乘客步行需求和出行時間，改善定制公交線路的搭乘舒適度.

1 問題描述

大客流跨區(qū)域通勤出行在中大型城市非常常見，城市通勤者每天需要換乘不同交通工具才能到達(dá)目的地，若搭乘線路發(fā)生擁堵會導(dǎo)致通勤者的時間不確定性.定義跨區(qū)域定制公交路線具有以下特征：①在出發(fā)區(qū)域和目的地區(qū)域設(shè)置多個公交?？空?，有助于乘客短距離步行得到定制公交服務(wù)；②為乘客提供直達(dá)式服務(wù)；③定制公交路線只安排少量或無中間?？空荆鐖D1中虛線所示.

圖1 典型的公交線路示意圖Fig.1 Schematic diagram of a typical bus line

圖1中，A區(qū)域和C區(qū)域為定制公交線路上下車需求區(qū)，B 區(qū)域中存在少量乘客搭乘，通過減少中間區(qū)域乘客需求，解決因中途站點請求數(shù)量多引起的頻繁停車、等待、再次啟動等問題.傳統(tǒng)公交因無法準(zhǔn)確估計沿線乘客數(shù)量，在高峰時期難以保障出行者的需求，而定制公交可以根據(jù)城市客流規(guī)律有效地提供定制化服務(wù)，解決公交服務(wù)配套設(shè)施供給不足問題.本文通過改進(jìn)Q-learning算法對區(qū)域公交搭乘路徑進(jìn)行搜尋，通過乘客與定制公交平臺的信息交互獲取乘客上下車需求，進(jìn)而優(yōu)化定制公交跨區(qū)域通勤的承載率.并結(jié)合區(qū)域道路環(huán)境，乘客數(shù)量，道路擁堵狀態(tài)等因素設(shè)置Q-learning的獎懲函數(shù)，解決實際交通路網(wǎng)環(huán)境下路徑搜尋不合理，計算效率低等問題.

2 基于Q-learning強(qiáng)化學(xué)習(xí)的定制公交路徑優(yōu)化

2.1 Q-learning規(guī)劃方法

Q-learning 為馬爾可夫決策過程(S,A,P,γ,R)，其中，S為所有環(huán)境狀態(tài)，A是智能體適應(yīng)環(huán)境所能采取的動作集，P為系統(tǒng)動態(tài)過程，P(s′|s,a)表示狀態(tài)s過度到s′采取動作a的概率，獎勵R為采取動作a時所獲得的回報，γ為折扣系數(shù)，表示歷史經(jīng)驗對將來估計的重要程度.如圖2所示，Q-learning算法通過搜索動作獲得最大獎勵，并基于獎勵的反饋為智能體提供決策依據(jù).首先，智能體在當(dāng)前狀態(tài)s下從可用動作列表中選擇一個動作a.然后，執(zhí)行或評估所選擇的動作，并將所選行動中獲得的獎勵R在Q 表中更新.智能體將識別環(huán)境模型中的下一個狀態(tài)s′，并采取下一個動作a′.最后，智能體將檢查目標(biāo)完成情況.

圖2 Q-learning 算法流程圖Fig.2 Q-learning algorithm flow chart

式(1)為Q-learning 迭代更新公式，根據(jù)maxa′Q(s′,a′)，即下一個狀態(tài)s′中選取最大的Q(s′,a′)i值乘以折扣因子γ加上真實回報值為Q現(xiàn)實，而根據(jù)過往Q 表中的Q(s′,a′)i-1作為Q估計.i為迭代數(shù)，通過更新其估計值來逼近真實Q現(xiàn)實值.其中，學(xué)習(xí)率α是新學(xué)習(xí)經(jīng)驗的權(quán)重，α∈(0,1)，折扣因子γ是決定未來狀態(tài)重要性的變量.高折扣因素將更多關(guān)注可能的未來獎勵并忽略當(dāng)前經(jīng)驗的重要性，并使得Q-learning 算法能夠以更快的速率收斂.在選擇動作的執(zhí)行過程中，Q-learning 將搜索具有最大獎勵的動作，即為貪婪選擇，由貪婪概率觸發(fā).貪婪概率過高會促使智能體在環(huán)境中繼續(xù)探索，智能體將面臨難以收斂的問題.

下面我通過比喻、夸張、對比和反問四種修辭手法，分別闡述在《哈利·波特》小說的翻譯過程中，修辭法準(zhǔn)確的翻譯與我們的習(xí)俗與文化相互結(jié)合幫助讀者真正理解《哈利·波特》的內(nèi)容，地道準(zhǔn)確的融合提高讀者對《哈利·波特》的理解力。

2.2 狀態(tài)行為對矩陣

智能體的狀態(tài)表示為公交在城市區(qū)域中所處的位置，本研究將城市區(qū)域分為交叉口、路段和居民小區(qū)，分別代表一個狀態(tài).車輛在開始進(jìn)入?yún)^(qū)域后啟動初始化參數(shù)并識別當(dāng)前狀態(tài)，從Q 表中選擇一個動作確定下一個狀態(tài)獲得的獎勵是否達(dá)到目標(biāo)，如果達(dá)到目標(biāo)則結(jié)束，未達(dá)到目標(biāo)則更新Q表中的獎勵值.通過Q-learning算法動作列表引導(dǎo)智能體進(jìn)入下一個狀態(tài)，直至智能體在整個過程中獲得最優(yōu)解.

定制公交智能體在城市區(qū)域內(nèi)尋找路徑時會在每一個狀態(tài)空間進(jìn)行探索，因此將區(qū)域內(nèi)的路段及交叉口作為Q-learning算法動作選擇依據(jù).如圖3所示，在交叉口和路段的狀態(tài)位置時智能體有4 種動作可以選擇，分別為前進(jìn)、左轉(zhuǎn)、右轉(zhuǎn)和掉頭，智能體將依次在路段和交叉口的狀態(tài)位置之間選擇，所選擇的動作將會被存儲在路徑時序計劃管理中，并輸出每個時間段所經(jīng)歷的路段和交叉口，直到達(dá)到Q-learning算法最優(yōu)的路徑方案.

圖3 智能體動作選擇過程Fig.3 Agent action selection process

2.3 獎勵和懲罰函數(shù)設(shè)置

如圖4所示，綜合考慮定制公交的路段行程時間、乘客搭乘便利性、公交線路可達(dá)性等因素設(shè)置了Q-learning算法的獎勵和懲罰函數(shù).

圖4 Q-learning 環(huán)境示意圖Fig.4 Schematic diagram of Q-learning environment

(1)乘客的獎勵函數(shù)設(shè)定.

根據(jù)乘客提交的出行需求，將出行的起訖點記入數(shù)據(jù)集中，把有相似OD需求通過k-means方法進(jìn)行聚類分組，以公交站點位置u(xk,yk)為聚類中心，k為聚類中心數(shù).有n位乘客請求位置坐標(biāo)數(shù)據(jù)集為X={(x1,y1),…,(xj,yj),…,(xn,yn)} ，其中dk∈Rd,Rd≤500 m，將集合中的相似數(shù)據(jù)劃分為k類，對于每一組樣本數(shù)據(jù)中的數(shù)據(jù)采用歐式距離計算每類數(shù)據(jù)點到聚類中心u(xk,yk)的距離平方和，即

式中：dk為聚類中心約束半徑；cj取值為0或1，表示判斷該點是否在約束內(nèi)；uk為聚類中心位置坐標(biāo)；Xj為乘客請求位置坐標(biāo)；f(dk)為乘客位置距聚類中心距離累計函數(shù).

基于小區(qū)邊緣街道的公交站點設(shè)置定制公交乘車獎勵，本文將乘客數(shù)量作為Q-learning的獎勵值，將每一位乘客的獎勵值設(shè)置為1，每一個公交站臺的乘客人數(shù)N，即為該站點的獎勵值.

(2)道路擁堵懲罰.

實際車輛在路段行駛過程中存在部分路段擁堵，根據(jù)擁堵的程度不同，加入擁堵系數(shù)T作為獎勵函數(shù)的一部分.乘客獎勵和路段懲罰后的獎勵函數(shù)為

式中：T為城市道路擁堵指數(shù)，根據(jù)道路等級和交通車輛行駛速度將擁堵指數(shù)分為5 級，分別為“暢通(0,2]”“基本暢通(2,4]”“輕度擁堵(4,6]”“中度擁堵(6,8]”“嚴(yán)重?fù)矶?8,10]”，數(shù)值越高表明交通擁堵狀況越嚴(yán)重.N為乘客需求請求數(shù)，φ,θ為道路擁堵指數(shù)和乘客需求權(quán)重系數(shù).

(3)小區(qū)位置懲罰.

為防止定制公交線路搜尋過程中通過居民小區(qū)，本文將其狀態(tài)設(shè)置為Q-learning 算法的懲罰項，獎勵值設(shè)置為-10，使其學(xué)習(xí)有用經(jīng)驗達(dá)到最大累計獎勵值.

2.4 獎勵函數(shù)塑形

稀疏的獎勵函數(shù)導(dǎo)致算法收斂緩慢，通過改進(jìn)Q-learning 算法的獎勵函數(shù)，增加額外的獎勵F(s,a,s′)可以豐富稀疏的獎勵信號，為智能體提供獎勵梯度信息.將額外獎勵添加到環(huán)境獎勵中，以創(chuàng)建一個合成獎勵信號R′(s,a,s′)，用于算法學(xué)習(xí)，可以解決獎勵稀疏性問題.將出口設(shè)定為大目標(biāo)，獎勵值為20，其他乘客和道路狀態(tài)設(shè)為道路額外獎勵.改進(jìn)后的獎勵回報函數(shù)如為

式中：Φ(?)是返回狀態(tài)s的電勢函數(shù)；λ是更新值函數(shù)估計值使用的折扣因子.通過定義勢能函數(shù)，并結(jié)合先驗知識，使智能體在探索開始時不是均勻隨機(jī)的，而是偏向探索具有高潛力的狀態(tài)，當(dāng)智能體從一個低勢能狀態(tài)轉(zhuǎn)移到高勢能狀態(tài)轉(zhuǎn)移時，它將獲得額外地獎勵，使用兩個狀態(tài)的勢能差值作為額外獎勵可以保證不改變MDP的最優(yōu)解[7].

3 實驗與結(jié)果分析

本文對江西省南昌市高新區(qū)的定制公交路線進(jìn)行了實驗分析.圖5為高新區(qū)的城市道路結(jié)構(gòu)示意圖，其中，橫向有艾溪湖北路、民強(qiáng)路和火炬大街3條主干道，縱向有青山湖大道、高新大道、京東大道和高新七路4條主干道.共有68個路段、43個交叉口和28個小區(qū).該區(qū)域的功能主要以企業(yè)、工業(yè)園和學(xué)校為主，從高新區(qū)通往南昌縣、新建中心和昌北開發(fā)區(qū)日常通勤需求量較大，且該區(qū)域離南昌市地鐵1號線有一定距離，對于遠(yuǎn)距離通勤的工作者們下班極為不便，適合定制公交在該地區(qū)應(yīng)用.經(jīng)過實際調(diào)查發(fā)現(xiàn)該地區(qū)的公共交通系統(tǒng)較為落后，公交站臺設(shè)置不完善，部分采用臨時站臺，甚至在部分道路上不設(shè)置公交?？空军c.本次實驗中，模擬包括乘客OD需求點對55個，合計的服務(wù)乘客數(shù)量200人次，車輛核載人數(shù)為35人，乘客需求與發(fā)車時間誤差不超過20 min.

如圖5所示，建立一個15×11 的小型網(wǎng)絡(luò)方格，其中圖5(b)白色方格代表區(qū)域中的路段，灰色部分代表交通小區(qū)，黑色虛線代表智能體行駛線路，其中每一個方格代表一個狀態(tài)—行為對.智能體將根據(jù)需求獎勵，搜尋出口目標(biāo)及中途乘客獎勵目標(biāo)，完成線路搜尋.本次實驗平臺基于python3.6，電腦配置為4 核CPU，七彩虹顯卡GTX1060 3 G，固態(tài)硬盤240 G，設(shè)置Q-learning 學(xué)習(xí)率從0.5～1.0，按每0.1 個單位取值，折扣因子同理取值計算，訓(xùn)練次數(shù)為700次.學(xué)習(xí)率α=0.9，折扣因子γ=0.9時，智能體能最有效地獲取獎勵值.

(1)高新區(qū)定制公交路徑分析.

圖6～圖8為計算所得區(qū)域路徑結(jié)果，圖6為高新區(qū)至南昌縣1、2 和3 號線定制公交線路圖，圖7為高新至昌北開發(fā)區(qū)定制公交4和5號路線圖，圖8為高新區(qū)至新建中心定制公交6 號和7 號路線圖，具體參數(shù)如表1所示.定制公交車區(qū)域線路直線系數(shù)均大于1.4，比傳統(tǒng)公交直線系數(shù)大25%左右，定制公交在區(qū)域內(nèi)承載率達(dá)到90%，保證定制公交在區(qū)域范圍內(nèi)接送更多的乘客.還能服務(wù)少部分在定制區(qū)域外上車的乘客.

圖5 區(qū)域交通街區(qū)示意圖Fig.5 Schematic diagram of regional traffic block

圖6 定制公交1、2 和3 號線路區(qū)域軌跡圖Fig.6 Customized bus line 1,2 and 3 area trajectory

圖7 定制公交4 和5 號線路區(qū)域軌跡圖Fig.7 Customized bus line 4 and 5 area trajectory

圖8 定制公交6 和7 號線路區(qū)域軌跡圖Fig.8 Customized bus line 6 and 7 area trajectory

表1 高新區(qū)定制公交線路信息Table1 Basic information of customized bus in high-tech zone

(2)算法性能分析.

從表2中可以看出，通過獎勵重塑的方法有效提升了Q-learning算法的計算效率.改進(jìn)Q-learning算法相比傳統(tǒng)算法的迭代次數(shù)平均下降了11.64%，計算時間平均縮短了19.76%.通過增加勢能函數(shù)對獎勵函數(shù)的重塑，能有效引導(dǎo)智能體獲得目標(biāo)獎勵，相比傳統(tǒng)的Q-learning 算法盲目搜索，改進(jìn)的算法更容易完成路徑搜尋.針對實驗中7條公交路徑進(jìn)行優(yōu)化的計算效率波動較大，迭代次數(shù)最高下降了22.83%，最低下降了6.1%.提升效率最為明顯的是線路6，迭代次數(shù)和計算時間均下降22%以上，這可能與狀態(tài)的位置及獎勵函數(shù)大小有關(guān).改進(jìn)后的迭代次數(shù)線路1 比線路6 相差179 次(40%)，在相同的環(huán)境下設(shè)定不同的獎勵對算法的求解性能影響很大，說明合理設(shè)置獎勵函數(shù)可以提高Q-learning算法效率.

表2 改進(jìn)Q-learning 算法計算效率對比Table2 Improved Q-learning algorithm calculation efficiency comparison table

(3)定制公交線網(wǎng)分析.

如圖9所示，為定制公交線網(wǎng)3條路徑規(guī)劃示意圖，中間定制公交停靠站點較少，線路較為固定，以保證定制公交在服務(wù)過程中能夠有效抵達(dá)目的地區(qū)域.減少中途停車需求，有效縮短乘客的通行時間，提高乘客舒適滿意度.

圖9 區(qū)域定制公交線網(wǎng)示意圖Fig.9 Schematic diagram of regional custom bus network

定制公交全線數(shù)據(jù)如表3所示，直線系數(shù)在1.4 左右，部分略低于1.4，而在表1中區(qū)域內(nèi)的定制公交直線系數(shù)均大于1.63，是由于區(qū)域內(nèi)路徑曲折，導(dǎo)致總程公交線路系數(shù)增大，相比傳統(tǒng)公交在直線系數(shù)的優(yōu)化上不存在明顯優(yōu)勢.

與表1中的行程速度和滿載率相比，定制公交因中途停站少，?？繒r間短，實際定制公交的行程速度比區(qū)域內(nèi)的行程速度要快很多，滿足了公交1 h 內(nèi)通行時間的要求.區(qū)域定制公交在通行效率、可達(dá)性等方面有明顯的優(yōu)勢，且基本保證乘客一人一座，在乘坐舒適度上相比普通公交有較好改善.

表3 區(qū)域通行線路基本信息Table3 Basic information on regional access routes

4 結(jié) 論

本文研究了城市區(qū)域定制化公共交通的搭乘方案，基于改進(jìn)的Q-learning強(qiáng)化學(xué)習(xí)算法為定制公交系統(tǒng)提供有效的區(qū)域路徑規(guī)劃，解決了區(qū)域乘客通行需求問題，并優(yōu)化了乘客步行距離、通行時間及乘客搭乘站點位置.通過對高新區(qū)路段、交叉口及居民小區(qū)位置設(shè)定獎懲函數(shù)，采用獎勵重塑的獎勵改進(jìn)優(yōu)化方法，提高了智能體在環(huán)境中探索效率，通過小獎勵的誘導(dǎo)以獲得最大的獎勵值.結(jié)果表明，改進(jìn)的Q-learning 學(xué)習(xí)算法在求解定制公交通行路徑上有所提升.并為跨區(qū)域定制公交區(qū)域路徑尋找提供了新的解決方案.改善了傳統(tǒng)公交服務(wù)不能直達(dá)目的地、換乘等待時間過長及低峰時段公交運力浪費等問題，是對傳統(tǒng)公交運營模式的一種創(chuàng)新.