[發明專利]一種可實現避障的自導向電動物流車輛路徑規劃方法

在審

• 申請號: 202011257594.6
• 申請日: 2020-11-12
• 公開（公告）號: CN112684790A
• 公開（公告）日: 2021-04-20
• 發明（設計）人: 刁利軍;范思源;苗春暉;梅偉耀;李偉杰;林文立;蔡道萌;陳浩;刁利堅
• 申請（專利權）人: 北京交通大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 北京衛平智業專利代理事務所(普通合伙) 11392
• 代理人: 張新利;謝建玲

1.一種可實現避障的自導向電動物流車輛路徑規劃方法，其特征在于，包括如下步驟：

步驟1：讀取數據，所述數據包括：由配送中心、充電站、客戶點形成的坐標矩陣；各客戶點的需求量；各客戶要求的時間窗上下限；

步驟2：計算距離矩陣：通過坐標矩陣計算所有配送中心、充電站和客戶點之間的距離；

步驟3：使用貪心算法分配任務：比較客戶點離配送中心的距離，從小到大排序，依序交叉放入1號車數組和2號車數組，由此建立兩輛電動物流車的任務順序列表；

步驟4：建立電動物流車路徑計算函數，兩輛車分別調用電動物流車路徑計算函數，得到每輛電動物流車需要服務的客戶點順序；

步驟5：使用蟻群算法求解電動物流車路徑計算函數；

步驟6：建立繪圖函數，輸入步驟5求解得到的結果調用避障函數，使用繪圖函數作最短路徑圖；

步驟7：作迭代收斂曲線圖：雙y軸，y1軸表示步驟4中電動物流車路徑計算函數計算的每代最短路徑長度，y2軸表示步驟4中電動物流車路徑計算函數計算的每代平均路徑長度，得到總的迭代趨勢。

2.如權利要求1所述的可實現避障的自導向電動物流車輛路徑規劃方法，其特征在于，步驟3包括如下步驟：

步驟3.1：對所有客戶點按其到配送中心的距離從小到大進行排序，形成序列index＝{c₁′,c₂′,...c_m′,...c_n′}，其中c_m′表示根據距離排序后的客戶點序號，m表示它在index數列的序號；

步驟3.2：建立兩電動物流車的任務順序列表，包括1號車數組car₁和2號車數組car₂，將index中的元素交叉放入兩電動物流車的任務順序列表中，得到car₁＝{c₁′,c₃′,...}，car₂＝{c₂′,c₄′,...}。

3.如權利要求2所述的可實現避障的自導向電動物流車輛路徑規劃方法，其特征在于，步驟4具體包括如下步驟：

步驟4.1：建立電動物流車路徑計算函數：

建立Tabu矩陣和Path數組，Tabu矩陣儲存本代到過的客戶點，Path數組儲存本代到過的所有點，包括配送中心和充電站；

設頂點集G＝N∪F，其中，客戶和配送中心點集N是客戶集N₀＝{1,2,...i,...j,...,n}和配送中心{O}的集合；F是充電站點集，所述充電站點集中充電站只有1個；

包括所有連接N中點的弧，每個弧(i,j)與行駛時間t_ij和距離d_ij相關聯，行駛速度v_ij被假定為是恒定的，建立啟發式矩陣，每當電動物流車準備從客戶點i出發時，啟發式矩陣會從步驟2中的距離矩陣中查詢客戶點i到所有任務順序列表中未訪問客戶點的距離，并利用這些距離計算每一個客戶點的轉移概率，按照輪盤賭方法確定要前往的目標客戶點j后，啟發式矩陣會從距離矩陣中查詢i與j之間的距離d_ij，利用d_ij計算所消耗的電量和所行駛的時間；

電動物流車路徑計算函數的數學模型如下：

y_jk≥min{τd_i0,τ(d_ij+d_j0)} (7)

式中，Z表示總成本，Z_e表示能源消耗成本，Z_t表示時間成本，Z_p表示懲罰費用，δ_i、δ_j分別為客戶點i的需求，單位為噸，i∈N₀,δ_j為客戶點j的需求，單位為噸，j∈N₀；Q為電動物流車k的電池總容量，單位為庫倫，τ為電能消耗速度，單位為千瓦時/千米；M為電動物流車的限重，單位為噸；x_ijk表示弧i,j上電動物流車流量的二進制變量，如果電動物流車k離開客戶點i去j，x_ijk＝1，否則，x_ijk＝0；d_ij表示頂點i,j之間的距離，d_j0表示頂點i和配送中心的距離，y_jk為在離開頂點i去j時電動物流車的剩余電池容量，初始時刻y_jk＝Q；

步驟4.2：計算電池參數：

Bat_alert＝(D_max+D′_max)/v×I_work (12)

式中，P為電池功率，U為電池工作電壓，I_work是放電電流，C為電池容量，t_charge為充電時間，η_loss為電池損耗百分比，Bat_alert為預警電量值，當電量達到此值是電動物流車需要返回配送中心充電，D_max是離充電站距離最遠的配送點到充電站的距離，D′_max是距離矩陣中最大的距離；

步驟4.3：建立基于軟時間窗的總體最優的評價規則：

設客戶點i規定的時間窗為[ET_i,LT_i]，ET_i為客戶點i允許的最早到達時間，LT_i為客戶點i允許的最晚到達時間，將電動物流車從配送中心出發設為初始時刻t₀＝0，設t_i為電動物流車到達客戶點i的時間；

軟時間窗約束允許電動物流車到達時間在[ET_i,LT_i]之外，但是如果電動物流車到達時間早于ET_i，還需要停車等待直到t_i＝ET_i；

早到或晚到需要付出懲罰費用，所述懲罰費用如下式所示：

Z_p＝a×max{ET_i-t_i,0}+b×max{t_i-LT_i,0} (13)

其中，a和b為人為設置的懲罰系數，設定a為0.2，b為0.5；

步驟4.4：建立電動物流車路徑計算函數的數學模型的總體利用最優方案，如式(14)所示：

式中，第一項為耗電成本的總和，第二項為時間成本的總和，第三項為時間窗懲罰費用的總和；

Z為總成本，b_ij為頂點i到j所消耗的電量；r為充電時間，單位為小時；s裝卸貨物速度，單位為噸/小時，所述充電時間和裝卸貨物速度是在路線規劃開始之前就確定的常數；C_e為單位電能的價格，單位為元/千瓦時；C_t時間成本，單位為元/小時；

步驟4.5：將car_k，k＝1,2作為電動物流車需要服務的客戶點序列，調用電動物流車路徑計算函數，得到每輛電動物流車需要服務的客戶點順序；記錄每一代所有的路徑長度，計算得到每代最短路徑長度和每代平均路徑長度，并將二者以雙y軸的形式畫出，以觀察算法的收斂程度。