[發明專利]基于改進型A*算法的物流配送車輛調度方法

有效

• 申請號: 201710609578.0
• 申請日: 2017-07-24
• 公開（公告）號: CN108154254B
• 公開（公告）日: 2022-04-05
• 發明（設計）人: 易星;吳昊;陳軍;楊曉星;易陽
• 申請（專利權）人: 南京交通職業技術學院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08;G06Q50/30;H04L67/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.基于改進型A^*算法的物流配送車輛調度方法，其特征在于，所述方法包括改進型A^*算法和物流配送算法兩個部分；所述的改進型A^*算法用于快速搜索兩點間較優路徑，包括：網格化配送區域、優選適當評估距離、以遞歸法搜索最短距離三個部分；物流配送算法用于生成從配送中心發往各客戶節點的車輛信息，包括車輛編號、經過的客戶節點、車輛路線、載重量和路線總距離，包括：計算各客戶節點到物流中心的距離和路線、改進的加權圖算法生成配送方案兩個部分；

其中改進型A^*算法的實現步驟為：

(1)網格化配送區域：已知客戶節點精確地理位置的前提下,將地圖按一定的比例劃分為方形網格(Grid)，網格狀態以一個二維數組描述；網格則可通過網格狀態標記為□，在數組中以0表示；網格不可通過則網格狀態標記為在數組中以1表示；路徑是從起點網格S到終點網格E經過網格的集合，其中經過的網格被稱為“節點”，節點有可通過和不可通過兩種狀態，可通過時有沿網格的XY軸方向移動和沿網格對角線方向移動兩種方式；

(2)優選適當評估距離：節點n(x_n,y_n)為從起點S(x_S,y_S)和終點E(x_E,y_E)經過n步所到達的節點，其評估距離f(n)＝g(n)+h(n)，其中g(n)是從起點S到節點n所經過路徑的距離，取網格邊長為d，i為從起點A到節點n所經過的某一網格，如通過該網格是沿網格的XY軸方向移動，則通過該網格經過的距離d(i)＝d，如通過該網格是沿網格的對角線方向移動，則通過該網格經過的距離h(n)是從節點n到終點E的啟發函數，其值為兩點間曼哈頓距離和歐氏距離的最小值，以Min()表示返回最小值函數，則h(n)＝Min((|x_n-x_E|+|y_n-y_E|),如地形已知，且為方便計算，也可直接選用曼哈頓距離，即h(n)＝|x_n-x_E|+|y_n-y_E|；當曼哈頓距離相同時再比較歐氏距離；

(3)以遞歸法搜索最短距離：用A^*(S,E)描述從起點S到終點E之間的較優路徑并返回路徑的權值，路徑權值以L1表示，open集合存放所有被考慮來尋找最短路徑的網格，closed集合存放不再被考慮的網格，集合P_min存放open集合中f(n)值最小的網格，所有集合均以堆棧形式保存，遵循后進先出原則，構建鏈表K存放最終路徑，A^*(S,E)的算法描述如下：

STEP1：清空open、closed集合，將S放到open集合；

STEP2：當open不為空時繼續，否則返回錯誤并退出；

STEP3：在open中找出評估距離最小的節點n，將n放入P_min中；

STEP4：如果n＝E，表示找到終點，轉到step9，否則繼續；

STEP5：將n從open集合移除,添加到closed集合中；

STEP6：檢查n周圍所有可通行的網格G，跳過不可通行的網格；

STEP7：將所有不在open集合中的G添加到open集合中；

STEP8：返回STEP2；

STEP9：從E開始，依次彈出P_min集合中的節點加入鏈表K，直到返回起點S，逆置鏈表K即可得到從起點S到終點E的路徑，且路徑的權值L1＝f(E)；

其中物流配送算法的實現步驟為：

(1)計算各客戶節點到物流中心的距離和路線，已知配送中心A地址為(x_A,y_A),客戶節點Vi的地址(x_Vi,y_Vi)(i＝1,2,…,n)，通過改進型A^*算法計算配送中心到每一節點Vi的路徑權值放入一維數組Lse[Vi]＝A^*(A,Vi)(i＝1,…,n)，并保存其路徑；

(2)通過改進的加權圖算法生成配送方案，已知配送中心A(x_A,y_A),客戶節點和路徑用一個加權無向圖來描述，G＝(V,E),V＝{V1,…,Vn},E＝{(Vi，Vj)}(Vi∈V,Vj∈V)，用二維數組L[Vi][Vj]存儲頂點Vi到Vj之間的權值,L[Vi][Vj]＝A^*(Vi,Vj)；D[k]存放每輛車的行駛距離包括返回到配送中心的距離，其中(k＝1,2,…,M)，M為車輛最大值；Q[k]存放每輛車行駛中的載重量，其中(k＝1,2,…,M)；每輛車的最大行駛距離為L_max；每輛車的最大車載量為Q_max；集合V_T為未分配節點的集合；集合S[k]為分配給第k輛車的頂點的集合；節點a為過程變量，表示當前出發搜索下一跳的頂點；其算法描述如下：

STEP1：初始化變量k＝1，V_T＝V；

STEP2：初始化S[k]＝Φ，Q[k]＝0，D[k]＝0，a＝A；

STEP3：V_T為空時轉STEP10，否則繼續；

STEP4：從集合V_T中通過改進型A^*算法找出與a距離最小的頂點V[i]；

STEP5：判斷(Q[k]+Q[V[i]]＝Q_max)AND(D[k]+L[a][V[i]]+Lse(V[i])＝L_max),如果為真轉STEP6，否則轉STEP9；

STEP6：D[k]＝D[k]+L[a,V[i]]，Q[k]＝Q[k]+Q[V[i]]，a＝V[i]；

STEP7：將頂點V[i]放入集合S[k]中，刪除集合V_T中的V[i]；

STEP8：返回STEP3；

STEP9：D[k]＝D[k]+lse[a]，k＝k+1，返回STEP2；

STEP10：D[k]＝D[k]+lse[a]，結束；

此時返回的S[k]集合中保存的就是車輛k所需訪問的客戶節點，其訪問順序為S[k]集合中元素的順序，所有物流配送車輛只需按照該車對應集合依次訪問其中的客戶節點即可。