[發明專利]一種路徑規劃方法、裝置、存儲介質及設備

在審

• 申請號: 201711334228.4
• 申請日: 2017-12-12
• 公開（公告）號: CN109916404A
• 公開（公告）日: 2019-06-21
• 發明（設計）人: 高磊;王宇;鄺展豪;劉志欣;楊志偉;喻東武;胡奉平;孔晨
• 申請（專利權）人: 順豐科技有限公司
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 北京志霖恒遠知識產權代理事務所(普通合伙) 11435
• 代理人: 梁風霞

一種路徑規劃方法、裝置、存儲介質及設備，所述方法包括：根據各運單生成第一路線集合；將各所述第一路線集合分發至若干算法迭代器，各所述算法迭代器分別進行若干次隨機路徑的摧毀與重建，得到第二路線集合并傳遞給算法協調器；所述算法協調器對各所述第二路線集合進行自適應處理，得到第三路線集合，作為路徑規劃結果輸出。所述裝置、存儲介質與設備用于實現所述方法。它提高了算法計算能力，解決了VRP(路徑規劃問題)的計算瓶頸。

技術領域

本發明涉及物流中路徑規劃領域，尤其涉及一種路徑規劃方法、裝置，存儲介質及設備。

背景技術

在路徑規劃領域的算法中，通常使用的是單機多核的最大鄰域搜索架構。在路徑規劃的實際問題中，單機多核的并行算法架構存在計算能力不足的問題；當任務集數量大于400左右時，單機多核的計算能力已經無法滿足需要。

發明內容

為了解決上述技術問題，本發明提出一種路徑規劃方法、裝置，存儲介質及設備，提高了算法計算能力，解決了VRP(路徑規劃問題)的計算瓶頸。

為了實現上述目的，本發明的技術方案為：

一種路徑規劃方法，包括：

根據各運單生成第一路線集合；

將各所述第一路線集合分發至若干算法迭代器，各所述算法迭代器分別進行若干次隨機路徑的摧毀與重建，得到第二路線集合并傳遞給算法協調器；

所述算法協調器對各所述第二路線集合進行自適應處理，得到第三路線集合，作為路徑規劃結果輸出。

所述摧毀采用的摧毀策略為以下任意一項：shaw/worst/random removal。

所述摧毀與重建采用的插入策略為以下任意一項：greedy/regret。

所述算法協調器通過模擬退火算法進行自適應處理。

所述根據各運單生成第一路線集合在執行過程中，包括：通過貪婪算法對待派送的運單集合進行運算，生成第一線路集合。

一種路徑規劃裝置，包括：

生成單元，配置用于根據各運單生成第一路線集合；

摧毀與重建單元，配置用于將所述第一路線集合分發至若干算法迭代器，各所述算法迭代器分別進行若干次隨機路徑的摧毀與重建，得到第二路線集合并傳遞給算法協調器；

算法協調器，配置用于對各所述第二路線集合進行自適應處理，得到第三路線集合，作為路徑規劃結果輸出。

所述摧毀與重建單元包括：

摧毀模塊，配置用于摧毀策略的選擇。

所述摧毀與重建單元包括：

插入模塊，配置用于插入策略的選擇。

一種設備，所述設備包括：

一個或多個處理器；

存儲器，用于存儲一個或多個程序，

當所述一個或多個程序被所述一個或多個處理器執行時，使得所述一個或多個處理器執行所述的方法。

一種存儲有計算機程序的計算機可讀存儲介質，該程序被處理器執行時實現所述的方法。

本發明的有益效果是：使用分布式的最大鄰域搜索架構，提高了算法計算能力。提高了算法計算能力，解決了VRP(路徑規劃問題)的計算瓶頸。

附圖說明

圖1示出了根據本申請的實施例的單機多核的并行算法架構。