動態(tài)視角下城市通勤路徑優(yōu)化研究

陳紅梅，張遠航，張春玲

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

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

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

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

1 問題描述

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

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

1) 初始路徑設計時每條路徑的路況相同，沒有外界因素干擾車輛行駛速度；

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

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

1) 某一時間段內(nèi)停靠點的乘客人數(shù)一旦確定就不會發(fā)生變化，即不考慮乘客需求量動態(tài)變化的情況；

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

2 模型建立

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

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

2.1 符號及定義變量

2.2 ?？奎c選址過程分析

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

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

2.3 初始路徑設計過程分析

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

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

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

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

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

3 算法設計

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

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

3.1 最速下降法

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

3.2 粒子群算法

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

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

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

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

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

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

3.3 Dijkstra算法

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

4 實證分析

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

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

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

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

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

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

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

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

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

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

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

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

表6 選取不同數(shù)量停靠點的比較分析Table 6 Comparative analysis for different numbers of stops

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

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

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

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

5 結(jié)論

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