[發明專利]一種實時路況下的車輛路徑規劃問題模型創建方法

有效

• 申請號: 201910973500.6
• 申請日: 2019-10-14
• 公開（公告）號: CN110766211B
• 公開（公告）日: 2022-05-06
• 發明（設計）人: 李長河;肖龍;王俊臣
• 申請（專利權）人: 中國地質大學（武漢）
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06N3/08;G08G1/01
• 代理公司: 武漢知產時代知識產權代理有限公司 42238
• 代理人: 金慧君

1.一種實時路況下的車輛路徑規劃問題模型創建方法，其特征在于：包括以下步驟：

步驟1：采集每條道路坐標數據，依據采集到的坐標數據 利用數據結構鏈表建立路網拓撲結構，路網拓撲結構包括相互交叉的道路之間的拓撲結構及單條道路的拓撲結構；

步驟2：連續采集每條道路在24小時之內間隔1min的車輛速度，持續三周，將采集到的車輛速度與路網拓撲結構中坐標點進行匹配，并利用采集到的車輛速度以及對應的時刻分別對每個路段的路況趨勢進行BP神經網絡建模，建立好的模型的輸入是時刻，輸出是該時刻對應的車輛速度；

步驟3：利用最短路徑算法A*驗證步驟1路網拓撲結構的正確性，并以A*算法作為任意兩個坐標之間最短路徑的求解算法；

步驟4：從已有的客戶訂單數據中獲取客戶貨物需求，包含投遞和揀貨需求、客戶時間窗范圍，將這些客戶信息附加到路網拓撲結構中的每個坐標點，使每個客戶信息和坐標點一一對應，每個坐標點相當于一個客戶；

步驟5：設置車輛路徑規劃問題中的基礎信息，包括倉庫位置、倉庫開放時間、是否有動態訂單、訂單的個數、訂單服務時間和車輛最大載貨量，至此，實時路況下的車輛路徑規劃問題模型創建完畢；

步驟5中實時路況下的車輛路徑規劃問題模型相關函數如下：

目標函數：

f₁＝K (1)

約束條件：

其中：目標函數f₁表示使用的車輛總數目；目標函數f₂表示所有車輛行駛的總路程；目標函數f₃表示所有車輛的延遲時間之和；目標函數f₄表示所有車輛的等待時間之和；目標函數f₅表示最長的車輛行駛時間，其他符號定義如下：

K：實際用到的車輛數；

k：第k輛車；

D_ij：節點v_i到v_j的路徑長度；

a_i(t)：車輛到達顧客節點i的時間；

若車輛k從節點v_i訪問節點v_j，值為1，否則為0；

v_ik：若節點v_i由車輛k服務過，則值為1，否則為0；

b_i(t)：若t時刻節點v_i已被服務，則值為1，否則為0；

車輛k通過節點v_i到節點v_j之間的路徑行駛的時間；

CS(t)：客戶不滿意度，即所有客戶的等待時間之和；

TT_k(t)：車輛k的行駛時間之和；

s_i：車輛在顧客節點i的服務時間；

S_k：車輛k的服務時間之和；

b_i：訂單i的起始時間窗；

e_i：訂單i的最晚時間窗；

q_i：客戶節點v_i的收貨需求；

g_i：客戶節點v_i的發貨需求；

C：車輛的最大載重量。

2.如權利要求1所述的一種實時路況下的車輛路徑規劃問題模型創建方法，其特征在于：所述步驟1中采集道路坐標數據的方法為：首先利用地圖平臺的交通態勢API獲取指定區域的道路坐標并轉化成圖層覆蓋到地圖平臺的經緯度查詢地圖上，之后沿著顯示的道路點選所需坐標點并記錄其經緯度，主要記錄各道路交叉路口坐標點的經緯度信息并保證交叉路口所連接的各條道路在交叉路口處的坐標相同。

3.如權利要求1所述的一種實時路況下的車輛路徑規劃問題模型創建方法，其特征在于：所述步驟1中路網拓撲結構重建的方法為：道路坐標數據集中包含了各個路段之間的連接關系，由于道路之間具有鏈式連接關系，利用雙向鏈表將單個道路中的坐標點連接起來，每個坐標點有多個前驅及后繼，只要將每個坐標點的前驅和后繼全部找到，就完成了路網拓撲結構的重建。