[發明專利]一種任務包裹優化方法、系統、設備

在審

• 申請號: 201710600029.7
• 申請日: 2017-07-21
• 公開（公告）號: CN107392374A
• 公開（公告）日: 2017-11-24
• 發明（設計）人: 王宇;高磊;劉志欣;楊志偉;喻東武;胡奉平;孔晨
• 申請（專利權）人: 順豐科技有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06K9/62;G06Q10/08
• 代理公司: 北京志霖恒遠知識產權代理事務所(普通合伙)11435
• 代理人: 曹麗

技術領域

本發明涉及路徑規劃，尤其涉及一種任務包裹優化方法、系統、設備。

背景技術

隨著物流行業的快速發展，物流業之間的競爭也不斷加劇。物流成本和周期的縮短主要集中在路徑的優化上。選擇出最優路徑已經成為物流企業最為迫切的需求。大規模鄰域搜索算法是解決此類問題的方法之一。

在路徑規劃領域的算法中，通常是將海量包裹數據直接傳入算法模型進行路徑規劃，但是如果將海量數據傳入算法模型，也就是當問題數量級過大的時候，意味著搜索空間巨大，可能會導致解的質量極差。還可能由于輸入量級過大，算法的計算能力有限，導致無法找到可行解的毀滅式問題。

發明內容

為了解決上述技術問題，本發明的目的在于提供一種任務包裹優化方法、系統、設備。

根據本發明的一個方面，提供了一種任務包裹優化方法，包括：

S1、獲取多個包裹的屬性信息；

S2、根據包裹屬性信息建立與其相對應的多維向量；

S3、將多維向量輸入k-means聚類算法對包裹進行分類，其中，相同分類組的包裹作為一個整體輸入大規模鄰域搜索算法進行路徑規劃。

進一步的，包裹的屬性信息包括地址流向、打包要求和時間窗。

其中，地址流向為包裹的起始、終止地址，打包要求如包裹是否需要正向放置，時間窗為客戶寄件時間和要求送達時間。

進一步的，與包裹屬性信息相對應的多維向量包括地址流向、打包要求、時間窗向量。

進一步的，將多維向量輸入k-means聚類算法對包裹進行分類包括：

S31、從多個多維向量中隨機取K個向量，作為K個簇各自的中心；

S32、分別計算剩下的向量到K個簇中心的相異度，將這些向量分別劃歸到相異度最低的簇；

S33、根據聚類結果，重新計算K個簇各自的中心；

S34、將上述多個多維向量中全部向量按照新的中心重新聚類；

S35、重復步驟S34，直到聚類結果不再變化；

S36、將對包裹進行分類的結果輸出。

進一步的，S32、S34、S35中，非簇中心向量按照向量距離d(X,Y)最小原則分配到相異度最低的簇，進行聚類處理，

其中，

X為一個簇的中心，

X＝{x₁,x₂,...,x_n}，

Y為非簇中心，

Y＝{y₁,y₂,...y_n}。

進一步的，簇中心的選取數量K＝a×包裹總數，其中，0＜a≤1，a的具體取值與包裹的區域特性有關。

根據本發明的另一個方面，提供了一種任務包裹優化系統，包括：

獲取多個包裹的屬性信息的采集單元；

根據包裹屬性信息建立與其相對應的多維向量的多維向量建立單元；

將多維向量輸入k-means聚類算法對包裹進行分類的數據優化預處理單元。

進一步的，相同分類組的包裹作為一個整體輸入大規模鄰域搜索算法進行路徑規劃。

該系統為基于上述任一任務包裹優化方法的系統，故包裹的屬性信息、多維向量的建立、通過k-means聚類算法對包裹進行分類等步驟如任務包裹優化方法部分所述。

根據本發明的另一個方面，提供了一種任務包裹優化設備，其特征是，包括存儲有計算機程序的計算機可讀介質,所述程序被運行用于執行：

S1、獲取多個包裹的屬性信息；

S2、根據包裹屬性信息建立與其相對應的多維向量；

S3、將多維向量輸入k-means聚類算法對包裹進行分類，其中，相同分類組的包裹作為一個整體輸入大規模鄰域搜索算法進行路徑規劃。

該設備為基于上述任一任務包裹優化方法的設備，故包裹的屬性信息、多維向量的建立、通過k-means聚類算法對包裹進行分類等步驟如任務包裹優化方法部分所述。

與現有技術相比，本發明具有以下有益效果：