基于實時交通信息的城市動態(tài)網(wǎng)絡(luò)車輛路徑優(yōu)化問題

孟慶珍

河南省開封市婦幼保健院 河南省開封市 475003

1 引言

根據(jù)交通運(yùn)輸部數(shù)據(jù)顯示：截至2017年，中國各類機(jī)動車的擁有量已達(dá)到5億輛。但是我國城市的人均道路面積僅為7平方米左右。同時，在城鎮(zhèn)化建設(shè)中，隨著我國居民擁有的汽車數(shù)量的不斷增長，我國道路基礎(chǔ)設(shè)施的發(fā)展速度落后，從超大型城市到三線城市，交通擁堵問題日益嚴(yán)重，而交通擁堵給機(jī)動車和道路承受力等資源帶來了損耗，也增加了出行者在道路的時空資源消耗，進(jìn)而導(dǎo)致居民的出行成本、社會的生產(chǎn)成本增加。另外，交通擁堵時，汽車排放的各種污染物如尾氣排放也對城市環(huán)境造成污染，因此增加了外部成本。面對道路交通擁堵以及汽車數(shù)量的增多帶來的安全、環(huán)境等一系列的社會問題，在目前道路投資有限的前提下，本文建議需采用信息化手段盡可能地對道路交通狀況進(jìn)行實時更新，優(yōu)化車輛出行的路徑規(guī)劃，以改善城市的道路交通擁堵情況，節(jié)省人們的出行時間和提高城市環(huán)境質(zhì)量。

2 實時交通信息概況

信息化代表一個國家或地區(qū)利用信息技術(shù)和整合各種資源的能力與水平。它是以數(shù)據(jù)庫技術(shù)、現(xiàn)代通信、網(wǎng)絡(luò)為底層基礎(chǔ)，構(gòu)建一個具有龐大規(guī)模的、自上而下的、有組織的信息網(wǎng)絡(luò)體系。它是一種以培養(yǎng)、發(fā)展以計算機(jī)為主的智能化工具，其也正在成為新的生產(chǎn)力。能夠很大程度上的提升人們辦事的效率和設(shè)備的生產(chǎn)力，為推動人類生活水平和質(zhì)量進(jìn)步提供強(qiáng)有力的技術(shù)支持。其包括信息獲取、信息傳遞、信息處理、信息再生、信息利用五個基本過程。本文中的實時交通信息的含義是運(yùn)用現(xiàn)代化的高新科技，例如：北斗導(dǎo)航系統(tǒng)、地理信息系統(tǒng)等技術(shù)，將城市的各種動態(tài)和靜態(tài)交通信息實時的從采集交通信息管理系統(tǒng)中，將數(shù)據(jù)系統(tǒng)化，并應(yīng)用于車輛路徑優(yōu)化的問題中，以達(dá)到共享資源，向車輛的用戶提供服務(wù)，優(yōu)化交通營運(yùn)管理。實時交通流信息的獲取與分享示意圖見圖1。

實時交通信息管理系統(tǒng)實現(xiàn)了交通數(shù)據(jù)的深度挖掘和細(xì)化加工，用以生成多種交通數(shù)據(jù)信息，并將其傳送給道路中的汽車。該系統(tǒng)的工作原理是：首先，通過k聚類算法或者啟發(fā)式算法識別數(shù)據(jù)的類型（離散或者連續(xù)），處理冗余性和噪音，提高數(shù)據(jù)的合理性和有效性。并對缺失的數(shù)據(jù)進(jìn)行智能補(bǔ)充；第二，構(gòu)建關(guān)聯(lián)度高的多源數(shù)據(jù)融合模型，構(gòu)建數(shù)據(jù)源和類型豐富的數(shù)據(jù)庫或者數(shù)據(jù)源以及符合城市實際環(huán)境的交通狀況指標(biāo)體系；第三，運(yùn)用計量經(jīng)濟(jì)學(xué)或者統(tǒng)計分析的方法對從各種渠道收集的交通流數(shù)據(jù)進(jìn)行歸一化處理，構(gòu)建車輛路徑特征庫，結(jié)合車輛出行實時數(shù)據(jù)和GPS、北斗導(dǎo)航衛(wèi)星形成的定位數(shù)據(jù)，構(gòu)建交通預(yù)測模型，實現(xiàn)了動態(tài)交通預(yù)測。

圖1 實時交通流信息獲取與分享示意圖

3 車輛路徑優(yōu)化

車輛路徑問題（VRP），作為運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域最經(jīng)典的問題，其對于解決城市道路交通擁堵的問題，有著十分重要的作用。在目前研究中，許多學(xué)者假設(shè)任意兩個交通網(wǎng)絡(luò)節(jié)點(diǎn)間的車輛行駛時間和路程為已知條件且為靜態(tài)的常量。在車輛路徑規(guī)劃和根據(jù)交通信息車輛行駛的過程中不會發(fā)生變化，但在實踐中，車輛會受交通流量、上下班高峰期、天氣變化、交通事故等因素的影響，車輛行駛速度總在不斷變化，從而導(dǎo)致了交通網(wǎng)絡(luò)中各個路段行程時間也相應(yīng)地發(fā)生變化。以往采用傳統(tǒng)靜態(tài)VRP理論和方法規(guī)劃車輛路徑，有可能使得車輛陷入城市擁堵的交通環(huán)境中。因此，在20世紀(jì)80年代的動態(tài)車輛路徑（DVRP）提出和研究引起企業(yè)和學(xué)者的關(guān)注。進(jìn)入21世紀(jì)以來，我國引入的GPS和國產(chǎn)的北斗導(dǎo)航衛(wèi)星、計算機(jī)通信、地理信息系統(tǒng)等技術(shù)不斷地完善，相關(guān)政府和企業(yè)投入研發(fā)地智能交通信息系統(tǒng)的日益完善，政府、企業(yè)和個人實時獲取和處理信息地能力得到極大地提高。

眾在VRP中，許多學(xué)者們創(chuàng)造和改進(jìn)了各種智能優(yōu)化算法，例如遺傳算法、粒子群算法、啟發(fā)式算法、神經(jīng)網(wǎng)絡(luò)算法、蟻群算法、果蠅算法等。其中最為經(jīng)典和有效解決問題的是遺傳算法、神經(jīng)網(wǎng)絡(luò)算法和蟻群算法。遺傳算法作為一種最為廣泛的求解車輛路徑問題的算法，其可以以對問題的所處周圍環(huán)境和條件未知為前提，其求解問題的步驟最為固定，包括交叉-適應(yīng)度確定-選擇-變異。遺傳算法從問題解的串集開始搜索，而不是從單個解開始。這是遺傳算法最大的優(yōu)點(diǎn)。遺傳算法從串集開始搜索，受搜索空間的限制性的約束，覆蓋面大，必要求求解的變量具有連續(xù)性、單峰性、可導(dǎo)性，利于全局擇優(yōu)。對于隨機(jī)環(huán)境下的城市交通信息和突發(fā)的車輛問題來說，神經(jīng)網(wǎng)絡(luò)VRP算法有著較好的適應(yīng)性，其可以及時跟蹤和反饋城市交通流的各類型參數(shù)、道路車輛流的變化，算法的計算精確度高，同時VRP神經(jīng)網(wǎng)絡(luò)算法包含了其自有的自組織、自適應(yīng)、自學(xué)習(xí)能力。由于原有的蟻群算法有眾多缺陷，許多學(xué)者們進(jìn)行了改進(jìn)，其中使用最為普遍的是Ant-Qsystem算法。

4 模型構(gòu)建

為了研究實時交通信息的動態(tài)網(wǎng)絡(luò)的車輛路徑問題，本文簡單描述動態(tài)網(wǎng)絡(luò)中VRP問題的模型構(gòu)建過程。本文將動態(tài)交通管理系統(tǒng)與配送貨物的車輛路徑優(yōu)化問題相結(jié)合，研究慮問題中包含常發(fā)性交通擁堵和偶發(fā)性交通擁堵兩種情形，并采用遺傳算法進(jìn)行模型的求解策略，已解決在實時交通狀況和車輛狀態(tài)下規(guī)劃最佳的行車路線。

4.1 問題描述

本文假定：（1）在城市范圍內(nèi)只設(shè)置1個配送中心，所有車輛的裝車容量固定，運(yùn)輸車輛在原始狀態(tài)下都停在配送中心，并在運(yùn)輸任務(wù)完成或者調(diào)度周期結(jié)束前返回：（2）車輛費(fèi)用由車輛購置費(fèi)用、燃油費(fèi)用和維修費(fèi)用三部分組成；（3）車輛行駛速度由時間和道路的交通狀況決定，各時間區(qū)間車輛的行駛速度一定；1個調(diào)度周期分為若干離散區(qū)間，調(diào)度中心只知道當(dāng)前時間行駛速度。（4）在同一個周期內(nèi)的客戶需求確定，l輛車服務(wù)至少服務(wù)一位客戶，在需求有時間差要求，車輛只能等待，但不許服務(wù)延遲。

4.2 構(gòu)建模型

4.3 求解

本文采用遺傳算法（GA）求解得到初始路徑，首先需要安排車輛的初始路徑，初始路線安排后，車輛在行駛過程中需要根據(jù)實時交通信息系統(tǒng)傳輸?shù)慕煌ㄐ畔π旭偟穆窙r判別，然后做出是否更新路線的決定。本文的路線更新機(jī)制是車輛在行駛過程中每到達(dá)一個配送的目的節(jié)點(diǎn)， 路段瞬時行程時間更新一次。并且車輛的路徑優(yōu)化中總是選擇當(dāng)前配送節(jié)點(diǎn)到下一個節(jié)點(diǎn)的瞬時最短路徑。由于現(xiàn)代化的通信移動技術(shù)和實時交通信息系統(tǒng)可以及時準(zhǔn)確的地變化中的交通環(huán)境，且能夠高精度地預(yù)測交通網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)的行程時間， 因此當(dāng)車輛到達(dá)路網(wǎng)中任意一個節(jié)點(diǎn)時都可以更新路段行程時間，并通過采用遺傳算法很容易計算得到當(dāng)前配送節(jié)點(diǎn)到下一個節(jié)點(diǎn)的瞬時最短路徑。

遺傳算法的求解過程：

4.3.1 染色體編碼

遺傳算法不能直接處理問題空間的參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定染色體編碼，目前的幾種常用的編碼技術(shù)有二進(jìn)制編碼、浮點(diǎn)數(shù)編碼、字符編碼和編程編碼等。編碼應(yīng)具備三個原則：完備性。問題空間中的所有點(diǎn)（候選解）都能作為GA空間中的點(diǎn)（染色體）表現(xiàn)；健全性。GA空間中的染色體能對應(yīng)所有問題空間中的候選解；非冗余性。交通信息數(shù)據(jù)的染色體和車輛優(yōu)化路徑的候選解一一對應(yīng)。在算法中的基因是城市路網(wǎng)轉(zhuǎn)換的節(jié)點(diǎn)，所以本例中采取了有序的二進(jìn)制編碼方式。

4.3.2 染色體交叉

雜交體現(xiàn)了信息交換的思想。由交換概率挑選的每兩個父代，通過將相異的部分基因進(jìn)行交換，從而產(chǎn)生新的個體，新個體組合了其父輩個體的特征。在遺傳算法中，在編碼串中某段碼元如果是有效車輛路徑或接近于有效路徑，則其繼承了父代的優(yōu)良基因特征；其次，交叉生成的子代應(yīng)是有效的個體，即符合有序的二進(jìn)制編碼規(guī)則。

4.3.3 染色體選擇

遺傳算法目的選擇的目的是為了從交換后的群體中選出優(yōu)良的個體，使它們有機(jī)會作為父代為下一代繁衍子孫。體現(xiàn)了達(dá)爾文的適者生存原則。在車輛路徑優(yōu)化中，其體現(xiàn)節(jié)點(diǎn)之間最短路徑選擇。本文的選擇機(jī)制是輪盤賭方式，即在第N代個體中如果有有效路徑，則有效路徑中的最佳路徑直接進(jìn)入下一代。

4.3.4 染色體變異

變異首先在所有的路徑中隨機(jī)選擇一定數(shù)量的個體，對于選中的個體以一定的概率隨機(jī)地改變串結(jié)構(gòu)數(shù)據(jù)中某個路徑的值。

最后，可以通過仿真軟件，對該模型進(jìn)行仿真求解，并驗證其可行性和有效性。

5 結(jié)語

本文在實時交通信息環(huán)境下解決車輛路徑問題，介紹了實時交通信息的概況，分析了車輛路徑優(yōu)化的靜態(tài)VRP與動態(tài)VRP的區(qū)別，以及在實踐中使用DVRP的優(yōu)勢，簡要介紹了構(gòu)建這類問題的數(shù)學(xué)模型的過程。今后，還要針對基于實時交通信息的動態(tài)網(wǎng)絡(luò)車輛路徑問題開展進(jìn)一步的研究以便可以有效地找到實時最短路徑、降低配送成本。