[發明專利]一種基于meanshift分類的大規模客戶點分類配送方法

有效

• 申請號: 201310547712.0
• 申請日: 2013-11-07
• 公開（公告）號: CN103593747B
• 公開（公告）日: 2016-11-23
• 發明（設計）人: 張貴軍;陳銘;明潔;姚春龍;張貝金;程正華;鄧勇躍;劉玉棟;秦傳慶
• 申請（專利權）人: 銀江股份有限公司;浙江工業大學
• 主分類號: G06F17/00
• 分類號: G06F17/00;G06Q10/08;G06Q50/28;G06N3/12
• 代理公司: 杭州斯可睿專利事務所有限公司 33241
• 代理人: 王利強

技術領域

本發明涉及一種地理信息數據處理、計算機應用領域，交通運輸工程，管理科學與工程，運籌學，圖論與網絡分析，尤其涉及的是，物流配送領域。

背景技術

隨著經濟全球化和網絡信息技術的飛速發展，物流配送作為一個新的經濟增長點已經引起了人們的普遍關注。配送是物流系統的核心環節，是伴隨著市場而誕生的一種必然的市場行為，隨著市場競爭的日益激烈以及客戶要求的不斷提高，配送在未來的市場競爭中將起到舉足輕重的作用。

國內外學者著力于研究VRPTW(vehicle?routing?problem?with?time?windows)問題，主要因為它是物流配送和交通運輸的核心問題，只有解決了調度問題才能使配送有效合理。VRPTW問題的目標函數可以描述為車輛從倉庫(單倉庫)到各分散客戶點之間的行駛總距離最短和線路總花費最小。線路設計原則是，每個一個客戶點只能被一輛車訪問，同時必須在規定的時間窗之內。所有的線路的起點和終點必須是同一個倉庫，并且在每一條線上的客戶點的貨運需求總量不能超過線路上的車輛的載重量。VRPTW問題實用性較強，尤其在3PL(thirdparty?logistic)中。對于上百個客戶點的配送問題，通過可伸縮方法在限制的時間內能得到較好的結果。Lenstra和Kan(1981)證明VRPTW問題屬于NP難組合優化問題。VRPTW問題的解法豐富，比較常見的可以分為精確算法和啟發式算法。采用精確算法解決VRPTW問題時，時間復雜度過高。近幾年，雖然一些學者在研究VRPTW問題中用到了精確算法，但是啟發式算法能在可行的時間復雜度之內優化問題，大多數學者還是著力研究啟發式算法來解決VRPTW問題。總的來說，VRPTW問題比VRP問題難些。因此，采用啟發式算法解決VRPTW問題更好些。近期以來，用啟發式算法解決VRPTW問題已取得了較好的結果。

但是，無論用哪種方法求解物流配送問題都很少能全面綜合考慮下面3個問題：①各個配送客戶點之間的距離是以其直線距離作為計算依據，脫離了配送客戶點之間的實際路網；②現有的VRPTW問題的研究，沒有考慮道路的行車實際情況，如：車道數、通流能力等地理信息因素考慮進去；③現有的研究多是針對網點數據較小的情況(一般不超過20個)，但在網點數目龐大的情況下，從計算量上，很難得到精確解；④基于GIS的大規模客戶點配送方法中，對大規模客戶點分類數目的確定缺乏理論支持，一般通過經驗來確定分類數目，具有一定的主觀性。

因此，現有的物流配送方法存在不足，需要改進。

發明內容

為了解決大規模客戶點的物流配送問題，克服已有的配送中的各個配送點之間是以直線距離為計算依據、沒有考慮道路質量，流通能力等地理信息因素、網點數較小等不足，本發明提供一種以配送點間的實際路網線路距離為計算依據，同時考慮道路實際行車能力、網點數較大、配送點對貨運需求時間的物流配送方法。

本發明解決其技術問題所采用的技術方案是：

一種基于meanshift分類的大規模客戶點分類配送方法，包括以下步驟：

A1、獲取帶有至少包含NAME，OBJECTID^*，Shape^*，Shape_Length4個字段的路網矢量數據，對原始的矢量數據的不及、超過和節點不相交3種情況進行處理；然后建立GIS富網絡路網模型；

A2、建立配送目標節點分類模型；

在地理坐標下，提取各個目標節點的地理坐標，依據樣本密度動態選取聚類中心，直至將所有的目標節點分類；具體模型如下：

給定2維空間R²的n個樣本點,i=1,…,n,在空間中任選一點x，那么Mean?Shift向量的基本形式定義為: