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

有效

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

本發明涉及一種基于改進型A^*算法的物流配送車輛調度方法，提出了在物流配送中車輛調度、路徑選擇和路徑規劃的一種方案：包括改進型A^*算法和物流配送算法兩個部分；其中改進型A^*算法用于快速搜索兩點間較優路徑，包括：網格化配送區域、優選適當評估距離、以遞歸法搜索最短距離三個部分；物流配送算法用于生成從配送中心發往各客戶節點的車輛信息，包括車輛編號、經過的客戶節點、車輛路線、載重量和路線總距離，包括：計算各客戶節點到物流中心的距離和路線、改進的加權圖算法生成配送方案兩個部分。本調度方法兼顧車輛路徑中約束條件，減少總運輸距離，增強對物流配送過程的全面控制和管理，實現較經濟實惠的配送線路。

技術領域

本發明涉及車聯網技術領域，尤其涉及一種基于改進型A^*算法的物流配送車輛調度方法。

背景技術

物流配送路徑中的車輛調度問題(VRP)是一個典型的組合優化問題，且已被證明是一個NP難問題，很難用精確算法對該問題在有限時間內求解。

一般常用的算法有Dijkstra算法和最佳優先搜索(BFS)算法，但是這兩種算法都存在一定的缺點，Dijkstra是典型的單源最短路徑算法，遇到地圖中的U 型障礙物，Dijkstra算法就會運行得較慢，執行效率方面還需要改進；BFS盡管它比Dijkstra算法快的多，由于它只考慮到達目標的代價，所以遇到地圖中的 U型障礙物時它不會避開而選擇一條很長的路徑。

發明內容

本發明其目的在于提供一種快速便捷的VRP組合優化方案。

本發明采取的技術方案是：

本發明提出一種基于改進型A^*算法的物流配送車輛調度方法，包括改進型 A^*算法和物流配送算法兩個部分。

本發明中用到的名詞解釋如下：

(1)路徑：被稱為從起點到終點經過節點的連續數列；

(2)路徑權值：從一個節點到另一個節點的路徑長度；

(3)圖：是由節點和邊所組成的集合，通常用G＝(V,E)來表示，V是所有節點的集合，E是所有邊的集合；

(4)無向圖：是一種邊沒有方向的圖，兩個頂點之間沒有次序關系，例(V1,V2) 與(V2,V1)代表相同的邊；

(5)鄰接矩陣：對無向圖而言，鄰接矩陣一定是對稱的，其對角線為0，表示的是圖中每個節點之間相鄰關系的矩陣；

(6)最短路徑：無向圖中從起始頂點開始到達終點頂點的路徑有多條，取其中路徑權值最短的一條則為最短路徑。

本發明中改進型A^*算法用于快速搜索兩點間較優路徑，包括：網格化配送區域、優選適當評估距離、以遞歸法搜索最短距離三個部分。

本發明中物流配送算法用于生成從配送中心發往各客戶節點的車輛信息，包括車輛編號、經過的客戶節點、車輛路線、載重量和路線總距離，包括：計算各客戶節點到物流中心的距離和路線、改進的加權圖算法生成配送方案兩個部分。

本發明中，設物流中心和客戶點的位置是已知的，從物流中心使用最多m 輛貨車向n個客戶配送貨物，貨車最大載重量為Q_max，最大行駛距離L_max，貨車均從物流配送中心出發，完成運送任務后返回物流中心，且具備以下約束條件：

(1)貨車運輸使用時間最少；

(2)運輸距離最短；

(3)使用最少的車輛完成配送；

(4)每次配送線路中的客戶貨物總量要小于或等于貨車的最大載重量；