陳紅梅，張遠(yuǎn)航，張春玲

(燕山大學(xué) 1.經(jīng)濟(jì)管理學(xué)院；2.區(qū)域經(jīng)濟(jì)發(fā)展研究中心，河北 秦皇島 066004)

隨著我國(guó)經(jīng)濟(jì)的飛速發(fā)展，汽車消費(fèi)迅猛上升，交通擁堵成為我國(guó)城市發(fā)展常態(tài)問(wèn)題，而且呈現(xiàn)愈演愈烈的趨勢(shì)?！?019年中國(guó)城市交通報(bào)告》中指出，集中出行尤其是高峰期通勤，選擇私家車等道路利用率低的出行模式是大多數(shù)城市交通擁堵的重要成因[1]。公共交通方式由于站點(diǎn)、路線固定，選擇其進(jìn)行通勤往往會(huì)在繞行、等待和轉(zhuǎn)乘上花費(fèi)大量時(shí)間，而城市節(jié)奏的不斷加快又使人們對(duì)通勤效率的要求越來(lái)越高，城市公共交通與人們的通勤需求之間存在著較大的矛盾。部分企業(yè)為職工開(kāi)通通勤車，意在緩解職工“通勤難”問(wèn)題，然而由于員工居住地分散，缺乏合理的路線規(guī)劃，難以滿足上班族的通勤需求導(dǎo)致其乘坐率很低。因此許多上班族選擇私家車通勤，高峰期城市交通壓力不斷增大。在這種背景下，本文研究通勤車動(dòng)態(tài)路徑優(yōu)化問(wèn)題，改變傳統(tǒng)企業(yè)通勤車路線固定的模式，對(duì)提高上班族通勤效率，緩解高峰期城市交通擁堵具有較強(qiáng)的現(xiàn)實(shí)意義。

本文在優(yōu)化通勤車路徑時(shí)借鑒運(yùn)籌學(xué)中的VRP(vehicle routing problem，車輛路徑問(wèn)題)。VRP被大多數(shù)學(xué)者用于物流配送車輛路徑問(wèn)題上，有學(xué)者注意到VRP同樣適用于載人的車輛路徑問(wèn)題上，因此SBRP (school bus routing problem，校車路徑問(wèn)題)也得到了一定的發(fā)展。VRP中包含著許多的分支，DVRP(dynamic vehicle routing problem，動(dòng)態(tài)車輛路徑問(wèn)題)就是其中常見(jiàn)的一種，由Psaraftis[2]教授總結(jié)提出，之后Bertsimas等[3]、Gendreau等[4]針對(duì)DVRP的內(nèi)容作了深入的研究，Azi等[5]指出DVRP的動(dòng)態(tài)因素主要分為兩個(gè)方面，一個(gè)是顧客需求的變化；另一個(gè)是交通路況的變化。隨著物聯(lián)網(wǎng)、全球定位系統(tǒng)等的進(jìn)步，實(shí)時(shí)獲取路況信息變得越來(lái)越容易，因此基于實(shí)時(shí)交通信息的DVRP也獲得發(fā)展的契機(jī)，這類問(wèn)題一般都分解為初始路徑設(shè)計(jì)和動(dòng)態(tài)調(diào)整路線兩個(gè)問(wèn)題來(lái)求解。國(guó)內(nèi)外學(xué)者對(duì)此的研究主要集中在路線更新規(guī)則和優(yōu)化算法上。關(guān)于路線更新規(guī)則主要有4種。Kilby等[6]、Abdallah等[7]、張文博等[8]均利用定期更新策略解決DVRP，車輛每隔一段時(shí)間更新一次路線，核心思想是將動(dòng)態(tài)路徑轉(zhuǎn)化為靜態(tài)路徑。Armas等[9]利用動(dòng)態(tài)事件更新策略解決DVRP問(wèn)題，一旦接收到新的動(dòng)態(tài)路況信息就更新路線。Nakamura等[10]利用顧客處更新策略解決DVRP，車輛行駛到?？奎c(diǎn)更新一次路線。Chen等[11]、李妍峰等[12]利用關(guān)鍵點(diǎn)更新策略解決DVRP，車輛在?？奎c(diǎn)、擁堵易發(fā)生點(diǎn)等關(guān)鍵點(diǎn)調(diào)整路徑，其重點(diǎn)在于對(duì)“關(guān)鍵點(diǎn)”的定義。關(guān)于優(yōu)化算法的研究更加豐富，主要有精確算法和啟發(fā)式算法兩種。由于研究數(shù)據(jù)量的不斷擴(kuò)大和對(duì)求解效率要求的提高，啟發(fā)式算法是當(dāng)下的研究熱點(diǎn)，常見(jiàn)的有禁忌搜索算法、蟻群算法、遺傳算法、粒子群算法等。Ozbaygin等[13]設(shè)計(jì)并行禁忌搜索算法，并用其解決一個(gè)迭代再優(yōu)化結(jié)構(gòu)的動(dòng)態(tài)車輛路徑問(wèn)題。蔡婉君等[14]利用蟻群算法對(duì)9個(gè)經(jīng)典算例實(shí)驗(yàn)證明蟻群算法針對(duì)車輛路徑問(wèn)題的有效性。孫小軍等[15]設(shè)計(jì)一種改進(jìn)蟻群算法來(lái)求解雙目標(biāo)帶時(shí)間窗的動(dòng)態(tài)車輛路徑問(wèn)題。Zheng等[16]結(jié)合蟻群算法和遺傳算法構(gòu)建RHC，并通過(guò)10個(gè)DVRP的案例證實(shí)其有效性。Yigit等[17]將蟻群算法和遺傳算法結(jié)合來(lái)實(shí)時(shí)優(yōu)化動(dòng)態(tài)校車路徑問(wèn)題。Abdallah等[7]利用遺傳算法解決需求和路況信息都不斷變化的VRP。Okulewicz等[18]將DVRP作為測(cè)試問(wèn)題，比較離散編碼的遺傳算法與微分進(jìn)化算法的求解效率和穩(wěn)定性。Barkaoui等[19]對(duì)遺傳算子進(jìn)行改進(jìn)，得到自適應(yīng)混合遺傳算法，可以大幅度提高遺傳算法解的質(zhì)量。張亞明等[20]設(shè)計(jì)改進(jìn)的經(jīng)營(yíng)單親遺傳算法來(lái)求解VRP。Okulewicz等[21]提出兩階段粒子群算法，很好地解決動(dòng)態(tài)需求的VRP。陳玉光[22]改進(jìn)粒子群算法，準(zhǔn)確地求解了基于準(zhǔn)時(shí)送貨和成本最小的VRP模型。胡小宇等[23]對(duì)傳統(tǒng)粒子群算法進(jìn)行改進(jìn)解決單倉(cāng)儲(chǔ)多車物流配送路徑優(yōu)化問(wèn)題。陳久梅等[24]利用粒子群算法求解冷鏈配送車輛路徑問(wèn)題并證明了粒子群算法具有很好的收斂性。

通過(guò)對(duì)文獻(xiàn)資料的分析可知，基于實(shí)時(shí)交通信息的DVRP是當(dāng)下的研究熱點(diǎn)，國(guó)內(nèi)外學(xué)者對(duì)其的研究重點(diǎn)大多是路線更新規(guī)則，而車輛路徑問(wèn)題屬于NP-hard問(wèn)題，一些在收斂性上比較好的算法被廣泛使用，如粒子群算法、蟻群算法、遺傳算法等。同時(shí)，有學(xué)者發(fā)現(xiàn)了選址問(wèn)題和車輛路徑問(wèn)題的相關(guān)性。李宏光等[25]指出站點(diǎn)配置是路徑規(guī)劃的約束和前提，通勤車站點(diǎn)配置方案將會(huì)直接影響路徑規(guī)劃。但現(xiàn)有的研究很少有將?？奎c(diǎn)選址問(wèn)題和車輛路徑問(wèn)題相結(jié)合，為此本文首先就如何為通勤車?？奎c(diǎn)選址最為合理進(jìn)行分析，通過(guò)解決初始路徑設(shè)計(jì)和動(dòng)態(tài)調(diào)整路線兩個(gè)部分來(lái)完成對(duì)通勤車的動(dòng)態(tài)路徑優(yōu)化，在最優(yōu)的初始路徑基礎(chǔ)上選擇關(guān)鍵點(diǎn)更新策略作為路線更新規(guī)則，并重新定義實(shí)際交通中的關(guān)鍵點(diǎn)，指出具體的路線更新方式，從而找到基于實(shí)時(shí)交通信息的通勤車最優(yōu)路徑。

1 問(wèn)題描述

?？奎c(diǎn)是通勤車路徑網(wǎng)絡(luò)中的重要節(jié)點(diǎn)，其選址的結(jié)果會(huì)對(duì)優(yōu)化后的路徑優(yōu)劣產(chǎn)生一定的影響，因此本文在路徑優(yōu)化前先對(duì)?？奎c(diǎn)選址問(wèn)題進(jìn)行研究。分析當(dāng)下城市布局，上班族的居住地點(diǎn)大多呈現(xiàn)出離散化分布的特點(diǎn)，許多通勤車在接送上班族時(shí)往往就近選擇?？奎c(diǎn)，導(dǎo)致通勤車需要長(zhǎng)時(shí)間繞行，優(yōu)先上車或靠后下車的乘客會(huì)產(chǎn)生較多時(shí)間上的沉沒(méi)成本。本文將?？奎c(diǎn)選址納入優(yōu)化范圍，通過(guò)已知的數(shù)個(gè)員工住址點(diǎn)確定一個(gè)未知的地點(diǎn)，選址的過(guò)程以距離最短作為目標(biāo)，以歐氏距離作為標(biāo)準(zhǔn)，與實(shí)際距離會(huì)有所差異，本文假設(shè)員工住址與選擇的?？奎c(diǎn)之間不需要過(guò)多繞行，使用歐氏距離對(duì)實(shí)際結(jié)果影響不大。

本文將通勤車的動(dòng)態(tài)路徑優(yōu)化問(wèn)題劃分為初始路徑設(shè)計(jì)和動(dòng)態(tài)路線調(diào)整進(jìn)行解決，在初始路徑設(shè)計(jì)時(shí)需要考慮到現(xiàn)實(shí)中的交通路網(wǎng)是復(fù)雜的，兩個(gè)地點(diǎn)之間往往有多條路線，設(shè)計(jì)初始路徑是在理想狀態(tài)下進(jìn)行的，以路徑最短的路線作為通勤效率最高的路線。假設(shè)：

1) 初始路徑設(shè)計(jì)時(shí)每條路徑的路況相同，沒(méi)有外界因素干擾車輛行駛速度；

2) 多輛車重復(fù)經(jīng)過(guò)同一?？奎c(diǎn)的成本遠(yuǎn)高于未滿載的成本，不能出現(xiàn)多輛車接送一個(gè)?？奎c(diǎn)乘客的情況。

影響動(dòng)態(tài)路徑優(yōu)化的因素有動(dòng)態(tài)的顧客需求和動(dòng)態(tài)的路況變化。本文的研究只集中于動(dòng)態(tài)的路況，即通過(guò)實(shí)時(shí)交通信息動(dòng)態(tài)調(diào)整路線。假設(shè)：

1) 某一時(shí)間段內(nèi)?？奎c(diǎn)的乘客人數(shù)一旦確定就不會(huì)發(fā)生變化，即不考慮乘客需求量動(dòng)態(tài)變化的情況；

2) 可以根據(jù)路況信息大致判斷出通過(guò)每條路線需要花費(fèi)的時(shí)間。

2 模型建立

在對(duì)通勤車進(jìn)行動(dòng)態(tài)車輛路徑優(yōu)化前，需要優(yōu)先考慮?？奎c(diǎn)的選址問(wèn)題，通過(guò)建立“步行距離最短模型”來(lái)解決。在解決動(dòng)態(tài)車輛路徑問(wèn)題時(shí)，將其劃分為初始路徑設(shè)計(jì)和動(dòng)態(tài)路線調(diào)整兩個(gè)部分來(lái)實(shí)現(xiàn)，為初始路徑設(shè)計(jì)過(guò)程建立合適的VRP模型。具體的模型和步驟如圖1所示。

圖1 建立模型的步驟Figure 1 Model construction stages

2.1 符號(hào)及定義變量

2.2 ?？奎c(diǎn)選址過(guò)程分析

停靠點(diǎn)的選址主要受?？奎c(diǎn)數(shù)量和用戶住址的影響，根據(jù)?？奎c(diǎn)的服務(wù)半徑要求大致確定出?？奎c(diǎn)數(shù)量設(shè)置的范圍，計(jì)算并分析多種方案下?？奎c(diǎn)選址對(duì)初始路徑設(shè)計(jì)的影響。利用聚類方法在空間上對(duì)用戶住址進(jìn)行劃分，并建立步行距離最短模型進(jìn)行求解。考慮到上下班高峰期時(shí)間段上班族對(duì)效率的高要求，停靠點(diǎn)的選擇以最便利為原則，在建立模型之前需要確定某一處?？奎c(diǎn)為哪片區(qū)域的上班族提供服務(wù)，即將所有參與研究的上班族居住點(diǎn)劃分為哪些集合。利用K-means聚類方法來(lái)劃分子簇，將各個(gè)住址坐標(biāo)Qi(xi,yi)視作需要進(jìn)行劃分的元素點(diǎn)，以歐氏距離作為劃分的相似度。在聚類前對(duì)所有住址坐標(biāo)進(jìn)行規(guī)劃，避免由于橫縱坐標(biāo)范圍不同對(duì)聚類屬性產(chǎn)生的影響，規(guī)格化后的住址坐標(biāo)記為Q*i(x*i,y*i)，橫坐標(biāo)規(guī)格化的公式如式 (1)，縱坐標(biāo)與之類似。

通過(guò)數(shù)學(xué)模型得到的?？奎c(diǎn)屬于理想化的解，在實(shí)際情況中城市交通網(wǎng)絡(luò)復(fù)雜，并不是所有的地方都能夠停車，要保證選擇的?？空军c(diǎn)在允許泊車的道路外側(cè)，因此得到的最優(yōu)解需要根據(jù)實(shí)際交通情況進(jìn)行適當(dāng)?shù)男拚?/p>

2.3 初始路徑設(shè)計(jì)過(guò)程分析

考慮到在上下班高峰期上班族對(duì)出行效率的高要求，將接送途中的通勤車所需數(shù)量最少、總耗時(shí)最短作為優(yōu)化目標(biāo)，所需最少通勤車數(shù)量，即集合S中的元素?cái)?shù)|S|，可以通過(guò)以下公式估算。

2.4 動(dòng)態(tài)調(diào)整路線分析

在動(dòng)態(tài)視角下，基于實(shí)時(shí)路況信息，本文選擇了關(guān)鍵點(diǎn)更新策略來(lái)對(duì)初始路徑進(jìn)行調(diào)整。李妍峰等[12]設(shè)置了不同的擾動(dòng)頻率、標(biāo)準(zhǔn)差，將4種路線更新策略進(jìn)行對(duì)比，證實(shí)了關(guān)鍵點(diǎn)更新策略的優(yōu)越性。應(yīng)用關(guān)鍵點(diǎn)更新策略最為重要的部分就是確定合適的“關(guān)鍵點(diǎn)”。Chen等[11]最先提出了“critical nodes”，但卻未對(duì)其進(jìn)行具體說(shuō)明。李妍峰等[12]在其研究中將未抵達(dá)的客戶節(jié)點(diǎn)和其他網(wǎng)絡(luò)節(jié)點(diǎn)作為關(guān)鍵點(diǎn)。在已有的基于實(shí)時(shí)交通信息的DVRP研究中，大部分學(xué)者會(huì)為了方便求解選擇采用定期更新策略、顧客處更新策略等，少數(shù)使用關(guān)鍵點(diǎn)更新策略對(duì)關(guān)鍵點(diǎn)的定義也各不相同，例如“未抵達(dá)顧客點(diǎn) + 等距離間隔點(diǎn)”、“未抵達(dá)顧客點(diǎn) + 交通慢行點(diǎn)”等組合。第1種組合方式即在將未抵達(dá)顧客點(diǎn)作為關(guān)鍵點(diǎn)的基礎(chǔ)上，每隔一段固定距離再添加一個(gè)關(guān)鍵點(diǎn)。這種組合方式雖然可以通過(guò)調(diào)整固定間距來(lái)選擇合適的關(guān)鍵點(diǎn)，但使用起來(lái)有很高的局限性，當(dāng)固定間距選擇過(guò)大時(shí)，會(huì)導(dǎo)致關(guān)鍵點(diǎn)之間距離較遠(yuǎn)，精度大大降低，與單純的顧客點(diǎn)更新策略差異不大。當(dāng)固定間距選擇過(guò)小時(shí)，精度高，但實(shí)際交通中很多路段雙向車道是分開(kāi)的，如果在某個(gè)關(guān)鍵點(diǎn)接收到前方擁堵的信息時(shí), 會(huì)因?yàn)殚g距過(guò)小，來(lái)不及掉頭，選擇其他路線。第2種組合方式即在將未抵達(dá)顧客點(diǎn)作為關(guān)鍵點(diǎn)的基礎(chǔ)上，利用經(jīng)驗(yàn)在事故、擁堵易發(fā)生點(diǎn)前選擇某個(gè)點(diǎn)添入關(guān)鍵點(diǎn)。這種組合方式下調(diào)整路線難度較小，但過(guò)分強(qiáng)調(diào)以往經(jīng)驗(yàn)，與擁堵發(fā)生的不確定性有一定的沖突，精度一般。

本文在這些研究基礎(chǔ)上將關(guān)鍵點(diǎn)定義為“尚未達(dá)到的?？奎c(diǎn)節(jié)點(diǎn)和路口交叉點(diǎn)”，即除了未到達(dá)的停靠點(diǎn)外，其他關(guān)鍵點(diǎn)以路口交叉點(diǎn)為基準(zhǔn)進(jìn)行選擇，選擇時(shí)需注意如下問(wèn)題。1) 關(guān)鍵點(diǎn)的選擇以避開(kāi)初始路徑中的擁堵點(diǎn)，且能夠在抵達(dá)下一個(gè)?？奎c(diǎn)前回到初始路徑為基本要求。2) 實(shí)際交通網(wǎng)絡(luò)中的交叉路口太多，且初始路徑是在無(wú)擁堵?tīng)顟B(tài)下的最優(yōu)路徑。為了防止關(guān)鍵點(diǎn)選擇過(guò)多導(dǎo)致出現(xiàn)大量偏離初始路徑過(guò)遠(yuǎn)的無(wú)效備選路徑，浪費(fèi)計(jì)算時(shí)間，因此要求每條備選路徑在回到初始路徑前最多經(jīng)過(guò)5個(gè)關(guān)鍵點(diǎn)。路口交叉點(diǎn)在交通中屬于重要節(jié)點(diǎn)，它是車輛流向的分割點(diǎn)，同時(shí)分布較為均勻，將其設(shè)為關(guān)鍵點(diǎn)一方面避免了使用的局限性，另一方面也能保證調(diào)整的精度。具體路徑調(diào)整方式如圖2所示。其中，CN為路口交叉點(diǎn)前的關(guān)鍵點(diǎn)，以路線1為例，當(dāng)通勤車已經(jīng)經(jīng)過(guò)P1，在?？奎c(diǎn)P1、P2之間找到關(guān)鍵點(diǎn)CN1、CN2、CN3、CN4以及P2，初始路徑可以表示為P1→CN1→CN3→P2→P3，假設(shè)在關(guān)鍵點(diǎn)CN1處收到CN1與CN3之間某處發(fā)生擁堵，按照初始路徑行駛會(huì)大大增加行使時(shí)間，則需要比較其他關(guān)鍵點(diǎn)路徑CN1→CN2→CN3→P2和CN1→CN4→P2的路徑耗時(shí)，從而對(duì)路徑進(jìn)行動(dòng)態(tài)調(diào)整，在調(diào)整過(guò)程中并不會(huì)改變通勤車達(dá)到每個(gè)停靠點(diǎn)的順序，避免因?yàn)榻煌〒矶?、道路故障造成的無(wú)謂時(shí)間損耗。

圖2 動(dòng)態(tài)路徑調(diào)整過(guò)程示意圖Figure 2 Dynamic adjustment of routes

3 算法設(shè)計(jì)

本文的研究涉及到的問(wèn)題較多，針對(duì)每個(gè)問(wèn)題都需要設(shè)計(jì)相對(duì)應(yīng)的算法。由于涉及到數(shù)據(jù)量較大，如何選擇合適的算法使得能夠快速得到結(jié)果就顯得尤為重要。在求解?？奎c(diǎn)選址問(wèn)題時(shí)，本文選擇最速下降法來(lái)迭代尋優(yōu)；通勤車的初始路徑設(shè)計(jì)不考慮外界因素影響，即傳統(tǒng)的VRP問(wèn)題，本文設(shè)計(jì)收斂性較強(qiáng)，收斂速度快的粒子群算法；在進(jìn)行動(dòng)態(tài)調(diào)整路徑時(shí)，本文選擇Dijkstra算法進(jìn)行求解。具體的算法流程如圖3所示。

圖3 求解算法流程圖Figure 3 Algorithm flow chart

3.1 最速下降法

步行距離最短模型即涉及兩個(gè)變量的無(wú)約束極值問(wèn)題，一般采用求偏導(dǎo)的方式即可得到最優(yōu)解，但當(dāng)數(shù)據(jù)量過(guò)大無(wú)法通過(guò)計(jì)算得到答案時(shí)，求導(dǎo)就不再適用。最速下降法又稱為梯度法，以一定的步長(zhǎng)沿著目標(biāo)函數(shù)的負(fù)梯度方向不斷迭代，直到達(dá)到最低點(diǎn)，利用算法時(shí)需要確定初始解向量U，精度eps。在Matlab中利用最速下降法，可以迅速找出最優(yōu)解。

3.2 粒子群算法

求解初始路徑時(shí)采用粒子群算法，具體步驟如下。

1) 構(gòu)造粒子表達(dá)式。針對(duì)每個(gè)?？奎c(diǎn)，需要確定的問(wèn)題如下。 (1)由哪輛車負(fù)責(zé)哪些?？奎c(diǎn)員工的接送； (2)該停靠點(diǎn)在路徑中達(dá)到的次序。通過(guò)對(duì)車輛編號(hào)以及接送次序的安排，可以直接確定所有路徑。利用粒子群算法得到兩個(gè)問(wèn)題的解便可得到通勤車的具體行駛路徑。在粒子群算法中，每個(gè)粒子群都只能代表一個(gè)解，粒子的狀態(tài)通過(guò)位置向量和速度向量來(lái)表示，求解問(wèn)題 (1)的粒子位置向量和速度向量為TS和HS；求解問(wèn)題 (2)的粒子位置向量和速度向量為TK和HK。位置向量表示迭代過(guò)程中的可行解，速度向量表示粒子下一次迭代的運(yùn)動(dòng)速度大小和方向，因此可以通過(guò)迭代找到最優(yōu)的粒子，其位置向量TS、TK反映的即為最優(yōu)狀態(tài)下接送某一?？奎c(diǎn)乘客的車輛編號(hào)、該?？奎c(diǎn)在本條路徑的次序。

2) 確定粒子的初始位置與初始速度。針對(duì)本文研究的問(wèn)題，一個(gè)?？奎c(diǎn)為一個(gè)維度，對(duì)每個(gè)粒子位置向量TS的每一維取 (1，|S|)之間的整數(shù)，TK的每一維取 (1, |K|)之間的實(shí)數(shù)；對(duì)每個(gè)粒子速度向量HS的每一維取 (- (|S|-1)，|S|-1)之間的整數(shù)，HK的每一維取 (- (|K|-1)，|K|-1)，把每個(gè)粒子的初始評(píng)價(jià)值作為迭代前個(gè)體粒子的最優(yōu)解。

3) 更新粒子的位置與速度。利用粒子的個(gè)體極值pbest和全局極值gbest來(lái)不斷更新，根據(jù)粒子位置向量并用式 (4)算得評(píng)價(jià)值，從而比較粒子當(dāng)前位置的優(yōu)劣性。個(gè)體極值pbest為該粒子在之前所有迭代中的最優(yōu)評(píng)價(jià)值，全局極值gbest為整個(gè)粒子群在之前所有迭代中的最優(yōu)評(píng)價(jià)值。粒子的位置和速度進(jìn)行更新的公式為

在第Z次迭代中，H指的是粒子的速度；w是慣性權(quán)重，一般取值在0.1 ～ 0.9之間；r1和r2是學(xué)習(xí)因子，有固定的取值；rand ( )是0 ～ 1之間的隨機(jī)數(shù)；Present表示粒子在此次迭代中的評(píng)價(jià)值。

4) 終止策略。在當(dāng)前迭代次數(shù)未超過(guò)最大次數(shù)max DT之前，如果找到全局最優(yōu)粒子位置滿足最小界限，可以直接以該粒子的位置向量作為最優(yōu)解輸出，未找到則可以繼續(xù)迭代；而當(dāng)前迭代次數(shù)超過(guò)最大次數(shù)max DT時(shí)，直接結(jié)束迭代，以當(dāng)下全局最優(yōu)粒子位置作為最優(yōu)解輸出。

3.3 Dijkstra算法

利用Dijkstra算法來(lái)完成動(dòng)態(tài)調(diào)整路徑的過(guò)程。Dijkstra算法利用廣度優(yōu)先搜索思想，被很多學(xué)者用來(lái)求解兩點(diǎn)之間的最短路，被認(rèn)為是求無(wú)負(fù)權(quán)網(wǎng)絡(luò)最短路問(wèn)題的最好方法，具體步驟如下。首先算出路徑網(wǎng)絡(luò)中各邊的權(quán)重 (可以為長(zhǎng)度、耗時(shí)等)，設(shè)立一個(gè)關(guān)鍵點(diǎn)集合G1，最初集合G1中只包含路線調(diào)整前的末尾關(guān)鍵點(diǎn)CN1一個(gè)元素，未通過(guò)的其他關(guān)鍵點(diǎn)都在集合G2中。從G2中找出所有與G1中關(guān)鍵點(diǎn)(即CN1)有路徑連通關(guān)系的關(guān)鍵點(diǎn)CNi(i=2, 4)，比較選出權(quán)重最小的關(guān)鍵點(diǎn)，將其加入到G1并從G2中剔除；再找出與G1中關(guān)鍵點(diǎn)有路徑連通關(guān)系的關(guān)鍵點(diǎn)，在G2中選出總權(quán)重 (即從CN1到該關(guān)鍵點(diǎn)的權(quán)重和)最小的關(guān)鍵點(diǎn)將其加入G1并從G2中剔除，不斷迭代直至G2為空集。關(guān)鍵點(diǎn)數(shù)量較少時(shí)可以通過(guò)標(biāo)號(hào)法解決，當(dāng)計(jì)算難度較大時(shí)可以在Matlab上通過(guò)編程快速求解。

4 實(shí)證分析

在大中小城市協(xié)調(diào)發(fā)展的背景下，我國(guó)的中小城市的經(jīng)濟(jì)得到快速發(fā)展，交通運(yùn)輸?shù)男枨笸瑫r(shí)也不斷增長(zhǎng)，大城市一般擁有較為健全的軌道交通系統(tǒng)，有軌電車、地鐵等交通方式為公路交通釋放了很大一部分壓力，而中小城市受限于原有城市布局，大部分交通壓力都集中在公路交通上，交通擁堵現(xiàn)象已經(jīng)逐漸開(kāi)始成為中小城市的“痛點(diǎn)”，因此選擇中小城市來(lái)研究通勤車路徑會(huì)更有實(shí)際意義。在《2019年度中國(guó)城市交通報(bào)告》中，秦皇島市高峰期城市交通擁堵同比提高10.68%，擁堵情況在同類型 (汽車保有量同一范圍)的城市中排行第三，上班族面臨著嚴(yán)重的通勤問(wèn)題?？紤]到通勤車主要用于職住分離較為嚴(yán)重的企業(yè)，本文選擇秦皇島經(jīng)濟(jì)技術(shù)開(kāi)發(fā)區(qū)為研究對(duì)象。

秦皇島的城市布局具有一定的特殊性，生活居住區(qū)大多集中在市中心一帶的位置，而大型的工作園區(qū)卻又在較為偏遠(yuǎn)的開(kāi)發(fā)區(qū)位置，直達(dá)的公交路線少且耗時(shí)長(zhǎng)。因此，大多人會(huì)選擇私家車出行，而過(guò)多的私家車又容易導(dǎo)致交通擁堵的出現(xiàn)。因此，為上班族優(yōu)化通勤車輛的行駛路徑，不僅可以提高他們的通勤效率，還可以有效降低私家車的使用次數(shù)，減少交通擁堵情況的出現(xiàn)，緩解城市交通壓力。通過(guò)隨機(jī)調(diào)查，秦皇島市經(jīng)常發(fā)生交通擁堵的時(shí)間和地點(diǎn)如表1所示。

表1 秦皇島市擁堵情況調(diào)查Table 1 Survey of traffic jams in Qinhuangdao

通過(guò)對(duì)時(shí)間的分析，可以大致確定出兩個(gè)擁堵頻繁發(fā)生的時(shí)間段，分別是早上的7:30 —9:00和下午的16:30 —18:30。通過(guò)對(duì)擁堵路段以及交通流向的分析，選擇必經(jīng)擁堵路段來(lái)通勤的上班族的居住小區(qū)作為本次實(shí)證的對(duì)象。員工居住區(qū)的坐標(biāo)以小區(qū)中心所在位置為準(zhǔn)，結(jié)合實(shí)際調(diào)查結(jié)果，在地圖上建立相應(yīng)的坐標(biāo)系，如表2所示。實(shí)證的算法求解過(guò)程均在Matlab R2018a軟件上進(jìn)行編程，在Win10環(huán)境下，CPU為2.70 GHz，內(nèi)存為7.9 GB的計(jì)算機(jī)上完成。

表2 研究選擇的20個(gè)居住區(qū)位置坐標(biāo)Table 2 Coordinates of the 20 selected residential districts

參考公共交通站點(diǎn)的服務(wù)半徑要求550 ～ 650 m，以所選取的20個(gè)小區(qū)最遠(yuǎn)直線距離 (1號(hào)與20號(hào))為直徑作出圓形覆蓋面，發(fā)現(xiàn)大約需要4.78 ～ 5.65個(gè)停靠站才能滿足服務(wù)范圍覆蓋的要求。為了證明停靠點(diǎn)選址會(huì)對(duì)路徑產(chǎn)生影響，本文分別選擇4、5、6個(gè)停靠站，通過(guò)比較初始設(shè)計(jì)路徑的長(zhǎng)度來(lái)分析3種情況在提高通勤效率上的優(yōu)劣。以選取5個(gè)?？奎c(diǎn)為例，則聚類的目標(biāo)數(shù)k= 5，員工住址的坐標(biāo)及規(guī)格化后的結(jié)果如表2所示。雖然初始聚類中心的選擇不會(huì)影響最終聚類結(jié)果，但會(huì)對(duì)聚類過(guò)程難易產(chǎn)生很大影響，因此需要根據(jù)地理位置進(jìn)行初步的直觀判斷，選擇較為分散且能代表某塊區(qū)域的元素點(diǎn)。本文選擇1、8、9、12、18作為初始聚類中心，形成A、B、C、D、E 5個(gè)聚類子簇，最終只經(jīng)過(guò)3次迭代后聚類結(jié)果就穩(wěn)定，如表3所示。在每個(gè)聚類子簇里建立一個(gè)基于步行距離最短的數(shù)學(xué)模型，以A子簇為例，建立模型為

表3 聚類過(guò)程中的結(jié)果Table 3 Results for each clustering step

利用最速下降法在Matlab上進(jìn)行求解。設(shè)置初始解向量U= (0 0)，即坐標(biāo)為 (0,0)的點(diǎn)先被假設(shè)為迭代前的?？奎c(diǎn)位置，精度eps = 1.0e-6，其中，e ≈2.718 281 83，是一個(gè)無(wú)限不循環(huán)小數(shù)。經(jīng)過(guò)9次迭代，得到擬選取的?？奎c(diǎn)坐標(biāo)為PA(2.269 4, 6.340 6)。同理，可以得到其他停靠點(diǎn)的坐標(biāo)，分別為PB(8.300 0,2.300 0)，PC(12.024 1, 0.515 0)，PD(12.684 6, 3.615 9)，PE(16.582 4, 2.145 8)。根據(jù)道路實(shí)際情況對(duì)?？奎c(diǎn)的位置進(jìn)行適當(dāng)調(diào)整，得到最后的選擇P1(沃爾沃)、P2(碧景華庭)、P3(萬(wàn)通大廈)、P4(學(xué)生之家)、P5(秦皇島海三大廈)。本文選擇的研究對(duì)象秦皇島經(jīng)濟(jì)技術(shù)開(kāi)發(fā)區(qū)反映在坐標(biāo)上為P0(9.72, 5.86)，在擁堵易發(fā)生的時(shí)間段里截取8:00—8:30這一時(shí)間段，調(diào)查各聚類子簇的小區(qū)中有通勤需求的數(shù)量，經(jīng)過(guò)整理后可得到如表4所示的數(shù)據(jù)。

表4 各節(jié)點(diǎn)坐標(biāo)及員工數(shù)量Table 4 Coordinates of stations and numbers of office workers

VRP模型中需要確定的定值僅有停靠點(diǎn)數(shù)和通勤車數(shù)量。已通過(guò)服務(wù)半徑確定停靠點(diǎn)數(shù)量為5，利用式 (3)確定所需最小通勤車數(shù)量為3 (選擇最為常見(jiàn)的中型客車作為通勤車，座位數(shù)為45)，在Matlab中利用粒子群算法進(jìn)行迭代搜索，粒子的搜索維度反映在實(shí)際問(wèn)題中即為?？奎c(diǎn)的數(shù)量。設(shè)置搜索維度SD = 5，選擇學(xué)習(xí)因子r1=r2=1.496 2，慣性權(quán)重w= 0.729 8，初始化粒子群數(shù)目N= 10；設(shè)置最大迭代次數(shù)max DT = 100，最終得到的全局最優(yōu)解gbest=41.133 1。按照比例進(jìn)行還原可得到最短路徑長(zhǎng)度為13.71 km。兩個(gè)粒子群的最優(yōu)粒子位置向量如表5所示，TS和TK分別反映了問(wèn)題 (1)、 (2)的解。TS=(1, 2, 3, 3, 3)，結(jié)合問(wèn)題 (1)，可以理解為由1號(hào)通勤車負(fù)責(zé)P1停靠點(diǎn)員工的接送，2號(hào)通勤車負(fù)責(zé)P2?？奎c(diǎn)，3號(hào)通勤車負(fù)責(zé)P3、P4、P5?？奎c(diǎn)。TK= (1, 1, 3,1, 2)，結(jié)合問(wèn)題 (2)，可以理解為P1?？奎c(diǎn)在某條路線中第1個(gè)抵達(dá)，P2停靠點(diǎn)在另一條線路中第1個(gè)抵達(dá)，P3?？奎c(diǎn)在其他路線中第3個(gè)抵達(dá)，P4?？奎c(diǎn)第1個(gè)抵達(dá)，P5?？奎c(diǎn)第2個(gè)抵達(dá)。將兩個(gè)問(wèn)題得到的信息整合，可以得到3條初始路徑：P0→P1→P0，P0→P2→P0，P0→P4→P5→P3→P0。

表5 求解得到的粒子位置向量Table 5 Obtained particle radius vectors

當(dāng)車輛數(shù)目越多，選擇的初始化粒子群數(shù)目應(yīng)該越大，從而避免得到的結(jié)果為局部最優(yōu)解。在此基礎(chǔ)上變更粒子群數(shù)目，設(shè)置N= 20、30、40分別進(jìn)行求解，得到的結(jié)果與N= 10時(shí)一樣，說(shuō)明粒子數(shù)目為10的粒子群已經(jīng)足夠精確求解本文實(shí)例。另外，隨著w值的增大，得到最優(yōu)路徑所需迭代的次數(shù)增多，但w過(guò)小容易陷入局部最優(yōu)。調(diào)整慣性權(quán)重w，取w= 0.229 8、0.529 8以及0.829 8，分別計(jì)算后所得結(jié)果與原結(jié)果相近，因此可以判定結(jié)果的準(zhǔn)確性。為了分析不同停靠點(diǎn)選址對(duì)通勤車路徑規(guī)劃產(chǎn)生的影響，保持學(xué)習(xí)因子r1=r2= 1.496 2，慣性權(quán)重w= 0.729 8，初始化粒子群數(shù)目N= 10。設(shè)置最大迭代次數(shù)max DT = 100不變，分別求解出設(shè)立4、6個(gè)停靠站 (即聚類目標(biāo)數(shù)k= 4或6，搜索維度SD =4或6) 時(shí)初始路徑設(shè)計(jì)的結(jié)果。比較結(jié)果如表6所示，隨著?？奎c(diǎn)選址數(shù)量的變化，設(shè)計(jì)的初始路徑長(zhǎng)度也有所不同。當(dāng)選擇4個(gè)?？奎c(diǎn)時(shí)，實(shí)際距離最短，通勤車的行駛效率是最高的；當(dāng)選擇6個(gè)?？奎c(diǎn)時(shí)，實(shí)際距離最長(zhǎng)，通勤車的行駛效率將最低。

表6 選取不同數(shù)量?？奎c(diǎn)的比較分析Table 6 Comparative analysis for different numbers of stops

由于配置4個(gè)?？奎c(diǎn)時(shí)將略微超出公共交通站點(diǎn)的服務(wù)半徑要求，這將導(dǎo)致上班族出發(fā)步行至停靠點(diǎn)的距離過(guò)遠(yuǎn)，會(huì)對(duì)通勤車的服務(wù)便利性造成一定的影響。因此動(dòng)態(tài)路線調(diào)整過(guò)程以配置5個(gè)?？奎c(diǎn)為例繼續(xù)進(jìn)行分析，將求解的3條初始路徑還原為實(shí)際交通的路線，可以得到優(yōu)化后的初始路線如圖4所示。

圖4 秦皇島經(jīng)濟(jì)技術(shù)開(kāi)發(fā)區(qū)通勤初始路徑設(shè)計(jì)圖Figure 4 Design of initial routes for Qinhuangdao Economic and Technological Development Zone

依照本文對(duì)關(guān)鍵點(diǎn)的定義和要求，在通勤車行駛前，分別為3條路徑找到14、8、24個(gè)除?？奎c(diǎn)之外的關(guān)鍵點(diǎn)，通勤車在接送上班族是優(yōu)先按照初始路徑行駛，每到關(guān)鍵點(diǎn)就自動(dòng)接受前方實(shí)時(shí)路況信息，從而決定是否要調(diào)整路徑行駛。在隨機(jī)調(diào)查過(guò)程中，建設(shè)大街西段某處發(fā)生擁堵，位于?？奎c(diǎn)P4、P5之間，對(duì)第3條初始路徑產(chǎn)生了影響，使車輛行駛速度減慢。截取P4、P5段進(jìn)行分析 ，共選取關(guān)鍵點(diǎn)10個(gè) (包括CN1、CN2、· ··、CN8、P4、P5)，如圖5所示，初始路徑為P4→CN1→CN2→CN3→CN4→P5。為了避開(kāi)CN1和CN2之間的擁堵點(diǎn)對(duì)路徑進(jìn)行調(diào)整得到備選路徑。假定通勤車在不擁堵路段的速度為15 km/h，以擁堵程度判斷從CN1行駛至CN2需要花費(fèi)10 min。將通勤車的行駛時(shí)間作為權(quán)重，在示意圖上以P4、CN1、CN2、· ··、CN8、P5的順序?qū)Ω鱾€(gè)關(guān)鍵點(diǎn)排序，用矩陣?表示路徑網(wǎng)絡(luò)中各邊權(quán)重如下，矩陣的 (i，j)位置表示i號(hào)到j(luò)號(hào)的行使時(shí)間，∞表示兩個(gè)關(guān)鍵點(diǎn)之間沒(méi)有直接通路。在Matlab中可以得出結(jié)果為 (1, 8, 3, 4, 5, 10)，即動(dòng)態(tài)路線調(diào)整結(jié)果為P4→CN7→CN2→CN3→CN4→P5，且總行駛時(shí)間為9.32 min，相較于擁堵?tīng)顟B(tài)下初始路徑行使時(shí)間16.92 min，通勤效率提高大約44.92%。

在無(wú)擁堵的理想狀態(tài)下，依照3條初始路徑行駛花費(fèi)的通勤時(shí)間分別為23.25 min、25.38 min、27.84 min，結(jié)合每條路線中包含的員工人數(shù)，可以得出人均通勤時(shí)間為25.72 min。調(diào)查得到員工當(dāng)下的人均通勤時(shí)間大約為40 min，而在實(shí)際交通中如果發(fā)生擁堵，員工的通勤時(shí)間將延長(zhǎng)到50 min左右。在本文的動(dòng)態(tài)路徑優(yōu)化基礎(chǔ)上，無(wú)擁堵?tīng)顟B(tài)下員工的通勤效率可以提高35.7%，初始路徑中存在擁堵時(shí)通過(guò)動(dòng)態(tài)調(diào)整路線會(huì)使行駛路徑長(zhǎng)度有所增加，但增加的行駛時(shí)間遠(yuǎn)遠(yuǎn)小于擁堵導(dǎo)致的等待時(shí)間，平均通勤時(shí)間也可以控制在30 min以內(nèi)，通勤效率相較于優(yōu)化前可以提高40%左右。

5 結(jié)論

本文主要對(duì)基于實(shí)時(shí)交通信息的通勤車動(dòng)態(tài)路徑優(yōu)化進(jìn)行研究，借鑒“初始路徑設(shè)計(jì) + 關(guān)鍵點(diǎn)更新策略”組合形式完成優(yōu)化過(guò)程，在初始路徑設(shè)計(jì)時(shí)充分考慮到上班族對(duì)高效通勤的需求，建立以行駛路徑最短為目標(biāo)的VRP模型，采用粒子群算法求解出理想狀態(tài)下的初始最優(yōu)路徑，在此基礎(chǔ)上將關(guān)鍵點(diǎn)定義為“尚未達(dá)到的?？奎c(diǎn)和路口交叉點(diǎn)”，利用關(guān)鍵點(diǎn)更新策略并結(jié)合Dijkstra算法實(shí)現(xiàn)路徑的動(dòng)態(tài)調(diào)整。最后進(jìn)行實(shí)證分析，得到一套最優(yōu)的通勤車行駛路徑優(yōu)化方案，并計(jì)算出通勤時(shí)間，驗(yàn)證模型和算法的有效性，可以在很大程度上提高上班族的通勤效率。但本文在研究初始路徑優(yōu)化的過(guò)程中忽視一些時(shí)間成本，例如上下車耗時(shí)成本、通勤車早到的等待時(shí)間成本、晚到的懲罰成本等，如何根據(jù)實(shí)際情況對(duì)模型進(jìn)行調(diào)整，實(shí)現(xiàn)上班族真正意義上的通勤效率最高，將是未來(lái)研究的方向。