[發明專利]一種支持充放電策略的電動汽車配送路徑優化方法

有效

• 申請號: 202011081222.2
• 申請日: 2020-10-09
• 公開（公告）號: CN112200367B
• 公開（公告）日: 2021-05-28
• 發明（設計）人: 李家樂;王雪菲;劉真伯;馬國偉;李永建
• 申請（專利權）人: 河北工業大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/06;G06N3/12;B60L53/00
• 代理公司: 天津翰林知識產權代理事務所(普通合伙) 12210
• 代理人: 張國榮

1.一種支持充放電策略的電動汽車配送路徑優化方法，其特征在于，該方法的步驟如下：

步驟1：搭建以車輛固定成本、行駛成本、懲罰成本以及充放電成本為優化的目標函數：

上述目標函數遵從電動汽車出行約束和電網約束；

所述電動汽車出行約束為：

∑_j∈V,i≠jX_0jk≤1 k∈K (3)

0≤D_j≤C_ik-D_i， i∈V,j∈V,k∈K (5)

所述電網約束為：

上述公式中，有：

此外，C₀為單位車輛的固定成本；C_d為單位距離成本；C₂為違反時間窗的懲罰成本；C₃為違反電量約束的懲罰成本；C₁為違反載重約束的懲罰成本；K為使用車輛數量的集合；0為配送中心，N為顧客點集合，G為換電站點的集合，V為全部節點的集合；d_ij為節點i到節點j的距離，D_i為顧客點i的需求量；Cap為車輛的最大裝載容量，C_ik為車輛k到達節點i時剩余的載重量，BQ為車輛的最大電池容量，qa_ik為車輛k到達節點i時車輛的剩余電量，ql_ik為車輛k 離開節點i時車輛的剩余電量；e_i為顧客點i的最早服務時間,i∈N；l_i為顧客點i的最晚服務時間,i∈N；ta_i為車輛到達顧客點i時的時間,i∈V；tl_i為車輛離開顧客點i時的時間,i∈V；tω_i為車輛在顧客點i的處的等待時間,i∈N；tμ_i為車輛在顧客點i的處的遲到時間,i∈N；ts_i為車輛在顧客點i的服務時間或充電時間,i∈V；t_ij為車輛從顧客點i到j的行駛時間,i、j∈V；speed為車輛在配送中行駛的速度；η為電池能量消耗系數；P_ev(i,j)為在j時刻電池i的實際充放電速率；SOC(i,j)為在j時刻電池i的荷電狀態；S_j為在j時刻的分時電價；P_avr為包含電動車的電網的平均功率；P_Lj為不含電動汽車的原電網j時刻的功率；

其中：目標函數式(1)代表了車輛成本、行駛成本、懲罰成本以及充放電成本四項和，其中充放電成本按分時電價，當電池放電時為負，即充放電成本為負時，說明在充放電過程中總體為獲利；約束式(2)表示每個顧客點都被服務且只服務一次；約束式(3)表示每條配送路線只安排一輛運輸車輛；約束式(4)保證了每個顧客點i都被服務過且僅被服務過一次；約束式(5)表示載重量與每個顧客點的需求量的關系，例如，車輛在顧客點j點的需求量不能超過車輛在顧客點i的剩余量減去顧客點i的需求量；約束式(6)表示每條路徑的總需求量不得超過車輛的最大承載容量；約束式(7)-(8)分別表示了顧客點到顧客點、換電站到顧客點的電量約束，如約束式(7)，顧客點j的剩余電量不得超過顧客點i的剩余電量減去從顧客點i到顧客點j所消耗的電量；約束式(9)表示任意點的剩余電量始終非負；約束式(10)表示車輛訪問顧客點節點的前后電量保持一致；約束式(11)-(12)表示電動汽車到達顧客點i的等待時間和遲到時間，例如約束式(11)所示，當車輛到達時間早于最早服務時間，那么等待時間為e_i-ta_i，否則取0；約束式(13)表示車輛離開顧客點i的時間為車輛到達顧客點i的時間與服務時間、等待時間之和；約束式(14)表示車輛從顧客點i到顧客點j所用時間的公式；約束式(15)表示車輛到達顧客點j的時間等于離開顧客點i的時間加從顧客點i到顧客點j所耗費的時間；約束式(16)-(17)為二進制0-1變量；公式(18)為負荷均方差，表示電網負荷的波動情況，均方差越小，電網負荷波動越小；約束式(20)表示電池的充放電速率的上下限；公式(21)表示電池可用容量約束，表示電池電荷狀態的最大值與最小值；

步驟2：根據顧客點和充電站的坐標，采用遺傳算法與局部搜索的混合算法進行路徑規劃，得到最優路徑方案；

所述步驟2具體包括：

步驟2.1：將電動汽車的配送路徑作為遺傳算法的染色體，不同的電動汽車配送路徑將一條染色體分為多組，采用十進制的編碼方式進行染色體編碼；具體的，染色體長度為n+ch+k-1，其中n代表了顧客點的數量，序列號為1,2,…,n，ch代表了換電站的數量，序列號為n+1,n+2,…,n+ch；k代表了使用電動汽車的數量，同時也代表一共有多少條路徑，k-1表示了配送中心在染色體上的位置，其序列號為n+ch+1,…,n+ch+k-1；

步驟2.2：采用遺傳算法與局部搜索的混合算法進行路徑規劃，具體為：

(1)參數初始化：設置種群規模、最大迭代次數、交叉概率和變異概率；

(2)初始化種群：輸入各個顧客點和充電站的坐標，隨機生成初始種群作為遺傳過程中的父代，并計算父代每條染色體的適應度值；

(3)選擇操作：選擇采用輪盤賭選擇法，每個個體被選中的概率與該個體的適應度大小成正比，并按照此概率隨機生成第一代子代種群；由于適應度較好的個體選擇的概率更高，父代個體中適應度較好的個體可能會被多次選中，第一代子代種群與父代種群的種群大小保持一致；父代個體被遺傳到第一代子代種群中的概率：

其中Fitness(x_i)為個體i的適應度；

(4)交叉操作：采用OX交叉操作，具體的：隨機選取第一代子代種群中的兩個染色體作為OX交叉操作的父代染色體，分別命名為父代1染色體和父代2染色體，每條染色體上隨機選取a和b兩個位置，該染色體上a到b之間的部分則稱為交叉片段，將父代2染色體的交叉片段拼接到父代1染色體的前面，將父代1染色體的交叉片段拼接到父代2染色體的前面；然后將新得到的父代1染色體和父代2染色體中重復的個體進行標記，接著按照從前到后的順序將第二個重復的個體刪除，形成兩個子代個體；按照上述的OX交叉操作，將第一代子代種群進行迭代更新，直至交叉概率達到設定值，此時的種群稱為第二代子代種群；

(5)變異操作：按照預先設置的變異概率判斷第二代子代種群中是否有染色個體需要變異，若不需要則進行下一步操作；若需要，則在該染色體上隨機選取兩個變異位置a、b，隨后將兩個位置的部分進行交換，生成變異的染色體，直至該群體中的染色體的變異概率到達設定值；經過變異操作輸出的種群稱為第三代子代種群；

(6)進行局部搜索操作：

a.對第三代子代種群中染色體編碼字符串中的顧客點編碼采用移除算子進行隨機刪除，將一定數量η的顧客點隨機從路徑中移除，并刪除顧客點數為零的空路徑；

b.采取貪婪插入的方法，計算被移除的顧客點與未被移除顧客點的相關性，按照相關性的大小依次插入未被移除的顧客點的路徑中，隨后判斷該路徑是否違反電動汽車出行約束約束，未違反則記錄該點，否則重新插入；若是未發現合適的插入點則新建一條路徑；貪婪插入根據顧客點之間的相關性，將被移除顧客點插入到當前解最優的位置，使得每次插入的成本最低；

c.由于每次顧客點位置都會重新調整，換電站位置也需重新插入，將換電站按照與該路徑中顧客點i的相關性進行插入，插入后記錄該路徑是否違反了電量約束；若是違反則重新插入，否則記錄該點；

d.計算經步驟a、b、c操作之后得到的每條染色體的適應度值，保留適應度值更大的染色體，更新種群；

(7)判斷迭代次數是否滿足迭代終止條件，若不滿足終止條件，則迭代次數加一，轉步驟(4)；若滿足則轉步驟(8)；

(8)從當前種群中選擇適應度值最優的個體作為遺傳算法與局部搜索的混合算法的最優解并輸出，該最優解即為最優路徑方案；

步驟3：根據步驟2得到的電動汽車配送路徑的最優路徑方案，結合分時電價，以換電站交換電池的供電方式，指導電力市場制定利潤最大化的充放電決策；

所述每條染色體適應度值的計算過程為：

Fitness(x_i)為染色體i的適應度，f(x_i)是以車輛固定成本、行駛成本、懲罰成本為優化的函數；C₃為違反電量約束的懲罰成本，設定為1000000。