[發明專利]一種基于重優化技術的物流網絡高效K最短路徑算法

在審

• 申請號: 202010003810.8
• 申請日: 2020-01-03
• 公開（公告）號: CN111210065A
• 公開（公告）日: 2020-05-29
• 發明（設計）人: 陳碧宇;陳小威;林興強
• 申請（專利權）人: 武漢大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06F17/18
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 魯力

1.一種基于重優化技術的物流網絡高效K最短路徑算法，包括以下步驟：

步驟1、輸入物流網絡數據以及當前物流參數，所述物流網絡數據給定區域所有的路段，并將路段進行抽象化，具體是：采集給定區域內所有物流網絡數據，并將該區域內物流網絡數據中所有路段抽象成有向邊a(n_u,n_v)，每條邊有兩個端節點n_u,n_v，以及一個權重值t(n_u,n_v)(如：行程時間、距離、運輸時間、中轉次數、物流車輛數)，每個節點n_u包含若干列前繼節點和后繼節點，分別用PRED(n_u)和SUCC(n_u)表示，當前物流參數包括起點o、目的地d、路徑數K；

步驟2、根據當前輸入物流參數，調用物流網絡數據，得到當前輸入物流參數所在區域的物流路段數據，并針對物流路段數據執行如下步驟：

步驟2.1，初始化，包括以下子步驟，

S101,調用Dijkstra算法計算從起點o和目的地d的第一條最短路徑標號p¹；

S102,判斷標號p¹是否為空，是則退出程序并返回空；否則設置候選優先隊列C：＝{p¹}，已確定的路徑集L：＝{}，進入步驟2；

步驟2.2，路徑選擇，包括以下子步驟，

S201,判斷路徑集L的數量是否大于k，是則退出程序并返回路徑集L；否則進入S202；

S202,判斷候選優先隊列C是否為空，是則退出程序并返回路徑集L；否則進入S203；

S203,設置p^j為優先隊列C的頂端元素，將p^j添加到L中，并從C中移除；

S204,進入步驟3，計算p^j的偏離路徑集D^j；

S205,將偏離路徑集D^j添加到候選優先隊列C中；

步驟2.3，偏離路徑集計算，包括以下子步驟，

S301,確定路徑的第一個偏離節點以及相應的偏離邊集

S302,從網絡中刪除路徑p^j上前l-1個節點和邊

S303,從網絡中刪除偏離邊集中所有的邊，令i:＝l-1；

S304,判斷i是否大于等于m，是則進入S305，否則還原網絡并返回偏離路徑集D^j；

S305,將節點還原，并令發生變化的節點集合

S306,令從起點o到當前節點的根路徑其是由一系列邊連接而成；

S307,進入步驟4計算子路徑

S308,聯合根路徑和子路徑得到偏離路徑并將添加到偏離路徑集D^j中；

S309,還原邊并令發生變化的邊集合

S310,令i:＝i-1，并返回到步驟S304；

步驟2.4，子路徑計算，包括以下子步驟，

S401,判斷是否首次進入，是則將網絡中每個節點n_u都設置為g(n_u)：＝∞，rhs(n_u)：＝∞，并設置目標點g(d)：＝0,rhs(d)：＝0，將目標節點d添加優先隊列SE中；否則對于中的所有邊a(n_u,n_v)，進入步驟5更新節點n_u，對于中所有的節點n_u，對其所有前繼節點n_v進入步驟2.更新；

S402,判斷優先隊列SE是否為空，是則退出步驟4并返回為空；否則進入S403；

S403,從優先隊列SE中選取并移除關鍵值key(n_u)最小的節點n_u；

S404,判斷當前選取的關鍵值key(n_u)是否大于節點的關鍵值且是否等于是則退出步驟4并返回節點的路徑；否則進入步驟S405；

S405,判斷g(n_u)是否大于rhs(n_u)，是則設置g(n_u):＝rhs(n_u)，并對節點n_u所有的前繼節點n_v進入步驟2.5進行更新；否則返回步驟S402；

S406,返回步驟S402；

步驟2.5，節點更新計算，包括以下子步驟，

S501,判斷節點n_u是否是目標節點d，是則進入S502，否則令然后進入S502；

S502,判斷節點n_u是否在優先隊列SE中，是則將n_u從優先隊列SE，然后進入S503，否則直接進入S503；

S503,判斷rhs(n_u)是否等于g(n_u)，是則退出步驟5；否則將節點n_u添加到優先隊列SE中，SE：＝SE∪{n_u}，然后退出步驟2.5；

步驟3、輸出路段選擇最終優化結果，即：輸出K條最短路徑結果，結果構成包括：第n條最短路徑為：(M₁,M₂,M₃…,M_l)，需要花費H小時；其中，l表示該路徑的節點數；M₁表示第一個節點，M₂表示第二個節點，M₃表示第三個節點，M_l表示第l個節點。