[發明專利]一種基于多目標優化的電動車輛出行規劃方法

有效

• 申請號: 201410534280.4
• 申請日: 2014-10-11
• 公開（公告）號: CN104331743A
• 公開（公告）日: 2015-02-04
• 發明（設計）人: 李克強;張書瑋;羅禹貢;秦兆博;陳龍;向勇;連小珉;王建強;楊殿閣;鄭四發
• 申請（專利權）人: 清華大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00
• 代理公司: 北京尚德技研知識產權代理事務所(普通合伙) 11378
• 代理人: 嚴勇剛

1.一種基于多目標優化的電動車輛出行規劃方法，分為如下步驟進行：

第一步，建立出行規劃問題模型，其中包括(1)含充電站信息的路網模型建立、(2)車輛模型的建立、(3)出行目標與出行約束定義，

(1)含充電站信息的路網模型建立方法是：定義動態隨機路網模型為G＝(V,γ,P,T,φ)，V＝{a,b,...,n}為路網中節點集合，共有|V|個節點，為路網中的有向邊集，代表路段的長度，代表路段的坡度；設路網模型中|V|個節點中存在P個節點建設有充電站，設每個充電站有C_w個充電等級；T是時間區間{(t₀+hδ，t₀+(h+1)δ)}的集合，其中t₀是初始時刻，h＝1,2,3,...,H，δ為單位時間間隔；φ代表路網中平均通行速度的概率集合，包括各路段平均通行速度處于各種可能狀態的概率分布，當車輛到達路網中某路段的時刻處于同一時段內時，則視為通過該路段的平均通行速度均服從此時段對應的速度概率分布特性；

根據地理信息系統獲知城市內路網中的各交叉路口、各路段的位置坐標，以及各交叉路口和各路段間的連接關系，定義交叉路口為節點，每條通行路段為邊；根據交通管理中心統計多天中的各路段在各時段中的平均通行速度，計算各路段在各個時段內的平均通行速度值的均值與方差，用以描述各路段平均通行速度處于各種可能狀態的概率分布；

(2)車輛模型包括了車輛當前剩余能量、車輛消耗能量、車輛充電能量的內容，所述能量指電能量；

(3)出行目標與出行約束定義包括了出行目標制定和出行約束條件制定；

第二步，由駕駛員提供出行信息，

其中，分為以下幾種情況：(1)駕駛員未提供任何信息，此時定義出行目標數目L為1，僅考慮交通環境約束，進行單約束下的單目標優化，(2)駕駛員只提供約束信息，此時L為1，考慮多種約束條件，進行多約束下的單目標優化，(3)駕駛員提供優化目標與約束條件相結合的信息,此時L為駕駛員所提出的目標的個數，考慮多約束條件，進行多約束下的多目標優化；

第三步，基于賦時多目標蟻群優化算法求解最優出行方案，

其中，包括(1)信息素初始化、(2)計算路線轉移概率、(3)搜索出行方案、(4)確定空調是否使用、(5)出行方案排序、(6)信息素更新幾個基本步驟，以及循環(2)～(6)的步驟，直至推薦出優化的出行路徑及路徑上的通行速度、空調的使用狀態，具體求解過程如下：

(1)信息素初始化：

在進行首次搜索前，需要為路網模型初始化信息素值，定義從當前節點向下一狀態轉移的初始化信息素值如下：

τp(q+m)l(th)=1|Rp|+Cw]]>

其中：

p∈V,q∈R_p,m＝1,2,...,C_w,l＝1,2,...,L

t_h∈T,h＝1,2,...,H

代表任一節點p在時段t_h內，目標l所對應的向下一狀態轉移的信息素值，|R_p|代表節點p的鄰接節點的數目，C_w為每個充電站的充電等級；

定義行駛過程中的推薦通行速度的初始化信息素值如下：

τpq_Vsl(th)=1VK]]>

其中：

pq→∈γ,l=1,2,...,L]]>

s＝1,2,...,V_K

t_h∈T,h＝1,2,...,H

(2)計算路線轉移概率：

定義一個由s個稱為螞蟻的搜索者組成的群體，設第k只螞蟻在搜索過程中，在當前節點p轉移到下一狀態時，選擇概率的大小是根據在時段t_h內的各個目標的路段上及充電站上的信息素值來定義的：

pp(q+m)k(th)=[Πl=1L(τp(q+m)l(th))αλkl]×(ηp(q+m)(th))βΣNp[[Πl=1L(τp(q+m)l(th))αλkl]×(ηp(q+m)(th))β]]]>

同樣，在確定狀態轉移是移動到鄰接節點的情況下，推薦該路段的出行速度選擇概率是根據時段t_h的路段上各目標的推薦速度信息素值定義的：

ppq_Vsk(th)=[Πl-1L(τpq_Vs)l(th))αλkl]ΣVK[Πl=1L(τpq_Vsl(th))αλkl]]]>

其中，L代表待優化的目標數目，這一數目與駕駛員所提供的輸入信息有關，當駕駛員沒有提供任何優化目標信息，L為1；

當駕駛員提供了優化的目標信息，就利用所提供的目標信息進行多目標優化，代表了在時段t_h從節點p到q+m狀態的目標l所對應的信息素，η_p(q+m)(t_h)代表了在時段t_h從節點p到q+m狀態的所對應的啟發信息，代表了在時段t_h通過路段時，目標l對應的推薦速度為V_s時的信息素值，α代表在搜索過程中，蟻群對于信息素的權重大小，β代表搜索過程中，蟻群對于啟發信息的權重大小；代表了第k只螞蟻對于第l個目標的搜索偏好，Xant代表粒度，自定義，這個量與人們想要以多大的精度來區分各個螞蟻的搜索偏好有關，搜索偏好滿足以下條件：

ΣLλkl=1]]>

λkl∈{0,1Xant,2Xant,...,1}]]>

(λk1,...,λkl,...,λkL)≠(λq1,...,λql,...,λqL),∀k,q∈s]]>

(3)搜索出行方案：

設第k只螞蟻從起點i在時刻t₀出發進行搜索，到達目的地j，設任一節點p的鄰接節點集為R_p，則存在兩種情況：

如果節點p為非充電站節點，在時段t_h內任意時刻，從節點p處向鄰居節點q移動的轉移概率

如果節點p為充電站節點，在時段t_h內任p意時刻，從節點p處向其他狀態轉移，包括兩種情況：一是在此點p進行充電，包括C_w個充電等級，每個級別m對應一個充電功率P_m,m∈N；二是在從點p向鄰居節點q進行轉移，因此其轉移概率為

根據轉移概率的大小，利用輪盤賭的方式選擇下一步轉移狀態，

當采用輪盤賭的方式選擇從當前點p向下一節點q進行轉移時，為該路段推薦出行速度，仍采用轉移概率的方法，定義從點p到點q的各個推薦速度值的概率為推薦速度從最小速度到最大速度共設定V_K個級別，

再采用輪盤賭的方式決定路段的推薦出行速度值

到達節點q后，按上述方法重復在節點p的狀態轉移和推薦速度，如此反復，直到找到目的地，則該螞蟻的出行方案包括出行路徑route(ant_k)和推薦速度velocity(ant_k)；

route(antk)={(ia→,t(ia→)),(ab→,t(ab→)),(bc→,t(bc→)),...(qq↔,t(qq↔))...,(mj→,t(mj→))}]]>

其中：

ia→,ab→,bc→,...,mj→∈γ]]>

q∈V

ia→=rijk(1)ab→=rijk(2)bc→=rijk(3)...qq↔=rijk(z)...mj→=rijk(|rijk|)]]>

代表路段選擇為是車輛進行該路段選擇的時刻，以此類推，出行方案的每條路段依次連接；當出行方案選擇在節點q處進行充電時，則定義車輛停留在該節點，所示，車輛在節點q停留充電，做出此選擇的時刻是設路網中的節點i與節點j共有K條路徑，設第k只螞蟻搜索到的路徑共有個組成部分，各個組成部分由來表示，代表通行該路徑的第z步動作，這一步動作可表達兩種含義，既可表示車輛通過某路段，也可表示這一步是車輛在某節點處進行停留充電，

velocity(antk)={(vT(ia→),t(ia→)),(vT(ab→),t(ab→)),(vT(bc→),t(bc→)),...,(vT(qq↔),t(qq↔)),...,(vT(mj→),t(mj→))}]]>

其中：

ia→,ab→,bc→,...,mj→∈γ]]>

q∈V

ia→=rijk(1)ab→=rijk(2)bc→=rijk(3)...qq↔=rijk(z)...mj→=rijk(|rijk|)]]>

代表在路段上的推薦通行速度值為當出行方案選擇在節點處進行充電時，則定義出行速度值為零；

在每個節點向下一狀態進行轉移的時候，包括兩種情況：當從一個節點向下一個節點進行轉移時，兩狀態的時間間隔為行駛時間：

t(rijk(z+1))=l(rijk(z))VT(rijk(z),t(rijk(z)))+t(rijk(z))]]>

當在當前節點p進行充電，不向其他節點轉移時，兩狀態的時間間隔為在該節點的等待時間與充電時間之和，其中節點p對應于第a個充電站：

t(rijk(z+1))=Tac+Taw+t(rijk(z))]]>

為該充電站的等待時間，為該充電站的充電時間；

重復以上步驟得到了所有螞蟻的出行方案，包括了出行路徑集與推薦速度集；

(4)確定空調是否使用：

在空調運行的每個循環周期ε中，需要判斷R(n)取值，R(n)取值為0或1，以決定空調是否工作，決策算法也是采用賦時多目標蟻群優化方法：

設第k只螞蟻從時刻t₀開始進行搜索，每個循環周期ε的轉移概率定義為和和分別代表了第k只螞蟻在第n個循環周期R_k(n)選擇為1或0的概率；

初始化概率和各占50％，n＝1,2,...,N；利用輪盤賭的方式決定各個周期的R_k(n)取值；

(5)出行方案排序：

如果駕駛員沒有提供目標信息，則分別利用出行時間最短和行駛距離最短作為目標；如果駕駛員提供了優化目標信息，根據所選目標集作為優化目標，然后評價任意兩個螞蟻所對應的出行方案，具體情況分為3種：

(5.1)螞蟻k對應的出行方案是可行解，螞蟻q對應的出行方案是不可行解，在這種情況下，螞蟻k的出行方案優于螞蟻q的出行方案，

(5.2)螞蟻k與螞蟻q對應的出行方案都是可行解，具體分為兩種情況：

情況1)：當螞蟻k對應的各目標都不差于螞蟻q所對應的各目標，說明螞蟻k優于螞蟻q；

情況2)：當螞蟻k對應的各目標并未全部優于螞蟻q對應的各目標，且螞蟻q對應的各目標也并未全部優于螞蟻k對應的各目標，說明螞蟻k與螞蟻q屬于同一級別；

(5.3)螞蟻k與螞蟻q對應的出行方案都是不可行解，此情況下，比較螞蟻k與螞蟻q的超過約束限制的值的大小，分為兩種情況：

情況1)：當螞蟻k對應出行方案的超限值都不大于螞蟻q對應出行方案的超限值，并且至少存在一個約束，是螞蟻k的超限值絕對小于螞蟻q的超限值，在這種情況下，說明螞蟻k對應的出行方案能夠更少的違反約束限制，說明螞蟻k優于螞蟻q；

情況2)：螞蟻k對應出行方案的各超限值沒有都小于螞蟻q對應出行方案的各超限值，同時，螞蟻q對應出行方案的各超限值沒有都小于螞蟻k對應出行方案的各超限值，在這種情況下，說明螞蟻k對應的出行方案與螞蟻q對應的出行方案彼此不能分辨優劣，說明這兩個螞蟻的出行方案屬于同一類別；

對所有螞蟻進行上述評價，計算每個螞蟻優于其他螞蟻的數目，記為η(k)，將所有η(k),k∈s值相同的螞蟻分為一類，共分為e組，根據組值對各個組進行降序排序；

(6)信息素更新：

首先定義各個螞蟻對應的信息素更新值，然后為各出行方案的沿途的信息素進行更新，信息素更新包括兩步，信息素加強與信息素蒸發；

1)定義各個螞蟻對應的信息素更新值

對于出行方案中排序靠前的解，讓該出行方案沿途的信息素值增強幅度大，對于排序靠后的解，讓該出行方案沿途的信息素值增強幅度小，

設定出行路徑信息素更新權重大小為τ，空調使用信息素更新權重為τ₀，出行路徑的每組的權重更新大小為I(i)，空調使用的每組的權重更新大小為I₀(i),i＝1,2,...,e：

I(i)=τe×(e-i+1),i=1,2,...,e]]>

I0(i)=τ0e×(e-i+1),i=1,2,...,e]]>

對于同組別的解，還要根據各個解之間的距離來對該組別的信息素權重進行加權：

對于同組別中的各螞蟻來說，如果該組別中只有一個螞蟻k，則這個螞蟻k的路徑選擇信息素更新權重Δ(k)即為該組別i的路徑選擇更新權重I(i)，空調使用信息素更新權重Δ₀(k)即為該組別的空調使用更新權重I₀(i)；如果該組別中有多個螞蟻，則每個螞蟻的信息素的更新權重需要根據該螞蟻的解與同組內的其他解的距離大小來評價；

利用如下公式計算同組別內各個螞蟻p和q之間的距離大小，其中代表螞蟻p的第l個目標的目標值，代表螞蟻q的第l個目標的目標值，代表本代搜索中第l個目標的最大值，代表本代搜索中第l個目標的最小值：

dpql=|Opl-OqlO_maxl-O_minl|]]>

設定聚集距離參數σ_share與比例系數ω值，σ_share取值在0-1，ω取值在1-1.5，利用如下公式計算各組別s(i)的每個解p與同組別的其他解q在第l個目標的相對距離值，并進行加和，得到同組內聚集在每個解p的第l個目標上與周圍的其他解的聚集程度

ncpl=Σq∈nSh(dpql)]]>

由此，可以計算每個解的信息素的更新權重大小Δ(k)和Δ₀(k)如下定義：

Δl(k)=I(i)nckl,k∈s(i),i=1,2,...,e,l=1,2,...,L]]>

Δ0l(k)=I0(i)nckl,k∈s(i),i=1,2,...,e,l=1,2,...,L]]>

2)信息素加強

對各出行方案沿途的出行路徑與推薦速度信息素和空調使用的信息素進行加強，對于第k只螞蟻的出行路徑的信息素更新過程，如下：

τial(th1)=τial(th1)+Δl(k),t0+h1δ≤t(ia→)≤t0+(h1+1)δ]]>

τabl(th2)=τabl(th2)+Δl(k),t0+h2δ≤t(ab→)≤t0+(h2+1)δ]]>

...

τpml(thd)=τpml(thd)+Δl(k),t0+hdδ≤t(pp↔)≤t0+(hd+1)δ]]>

τpql(thr)=τpql(thr)+Δl(k),t0+hrδ≤t(pq→)≤t0+(hr+1)δ]]>

...

τxjl(thw)=τxjl(thw)+Δl(k),t0+hwδ≤t(xj→)≤t0+(hw+1)δ]]>

其中

l＝1,2,...,L

h₁,h₂,...,h_d,...,h_r∈N⁺

m∈N⁺,m≤C_K

設代表車輛在時到達路段算法推薦車輛在路段行駛的平均通行速度，對于第k只螞蟻的推薦通行速度的信息素更新過程，如下：

τia_VT(ia→,t(ia→))l(th1)=τia_VT(ia→,t(ia→))l(th1)+Δl(k),t0+h1δ≤t(ia→)≤t0+(h1+1)δ,]]>

τab_VT(ab→,t(ab→))l(th2)=τab_VT(ab→,t(ab→))l(th2)+Δl(k),t0+h2δ≤t(ab→)≤t0+(h2+1)δ]]>

...

τpq_VT(pq→,t(pq→))l(thr)=τpq_VT(pq→,t(pq→))l(thr)+Δl(k),t0+hrδ≤t(pq→)≤t0+(hr+1)δ]]>

...

τxj_VT(xj→,t(xj→))l(thw)=τxj_VT(xj→,t(xj→))l(thw)+Δl(k),t0+hwδ≤t(xj→)≤t0+(hw+1)δ]]>

其中，

l＝1,2,...,L

h₁,h₂,...,h_d,...,h_r∈N⁺

m∈N⁺,m≤C_K對

VT(ia→,t(ia→)),VT(ab→,t(ab→)),...,VT(pq→,t(pq→)),....VT(xj→,t(xj→))∈{Vmin,Vmin+Vmax-VminVK-1,Vmin+2×Vmax-VminVK-1,...,Vmax}]]>

于第k只螞蟻的空調使用的信息素更新過程，如下：

τR(1)l(1)=τR(1)l(1)+Δ0l(k)]]>

τR(2)l(2)=τR(2)l(2)+Δ0l(k)]]>

...

τR(n)l(n)=τR(n)l(n)+Δ0l(k)]]>

...

τR(N)l(N)=τR(N)l(N)+Δ0l(k)]]>

其中

l＝1,2,...,L

n∈N⁺,n≤N

對所有螞蟻重復以上步驟，將所有螞蟻對應的出行方案都用于信息素更新，使得本輪搜索到的解指導下一輪的搜索過程；

3)信息素蒸發

在每輪搜索結束后，需要對地圖的信息素進行減弱，以避免算法過早收斂到次優解，信息素蒸發的表達式如下：

τp(q+m)l(th)=ρ×τp(q+m)l(th)]]>

其中：

pq→∈V]]>

m＝1,2,...,C_w

l＝1,2,...,L

h＝1,2,...,H

0＜ρ＜1

對于推薦通行速度的信息素蒸發，公式如下：

τpq_Vsl(th)=ρ×τpq_Vsl(th)]]>

其中：

pq→∈V]]>

l＝1,2,...,L

h＝1,2,...,H

s＝1,2,...,V_K

0＜ρ＜1

對于空調使用的信息素蒸發，公式如下：

τ1l(n)=ρ×τ1l(n)]]>

τ0l(n)=ρ×τ0l(n)]]>

其中

l＝1,2,...,L

n∈N⁺,n≤N。