[發(fā)明專利]一種基于GIS富網絡屬性路網的大規(guī)模分類配送方法

無效

• 申請?zhí)枺?/td>: 201310202970.5
• 申請日: 2013-05-27
• 公開（公告）號: CN103489082A
• 公開（公告）日: 2014-01-01
• 發(fā)明（設計）人: 張貴軍;姚春龍;張貝金;陳麒伉;程正華;鄧勇躍;明潔;劉玉棟;秦傳慶
• 申請（專利權）人: 浙江工業(yè)大學
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06Q50/28;G06F17/30
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

技術領域

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

背景技術

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

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

但是，不管用哪種方法求解物流配送問題都很少能顧及下面3個問題：①各個配送客戶點之間的距離是以其直線距離作為計算依據，脫離了配送客戶點之間的實際路網；②現有的VRPTW問題的研究，沒有考慮道路的行車實際情況，如：車道數、通流能力等地理信息因素考慮進去；③現有的研究多是針對網點數據較小的情況（一般不超過20個），但在網點數目龐大的情況下，從計算量上，很難得到精確解。?

因此，現有的物流配送方法存在缺陷，需要改進。?

發(fā)明內容

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

本發(fā)明解決其技術問題所采用的技術方案是：?

一種基于富網絡屬性路網的物流配送方法，包括以下步驟：?

A1、獲取矢量地圖（Shape?files），它是ESRI提供的一種矢量數據格式，沒有拓撲信息。一個Shape?files由一組文件組成，其中必要的基本文件包括坐標文件(.shp)、索引文件(.shx)和屬性文件(.dbf)三個文件。坐標文件(.shp)用于記錄空間坐標信息。坐標文件由頭文件和實體信息兩部分構成。索引文件(.shx)主要包含文件的索引信息，文件中每個記錄包含對應的坐標文件記錄距離坐標文件的文件頭的偏移量。通過索引文件可以方便地在坐標文件中定位到指定目標的坐標信息。屬性文件(.dbf)包含一feature一個記錄的feature的特征。這三個文件是一一對應的關系。原始地圖中的道路中至少包含OBJECTID*，Shape*，NAME，Shape_Length，4個字段，這4個字段為下面基于實際路網的分析提供保證。?

A2、地圖數據檢查。構建道路圖層時，影響拓撲關系建立的空間數據關聯錯誤有3中情況，分別是，不及、超過和節(jié)點不相交。這種處理一般量比較大，要是手工逐個修改，耗時大。一般采用自動判斷并且糾正數據錯誤，分為3步：?

①設置交點區(qū)間（即兩條道路端點是否相交的最小距離）；?

②找出道路圖層中每條道路對象的起點和終點（道路線路實體對象分為折線和直線）。?

③比較任意兩線起終點間距離，若距離大于零并且在交點區(qū)間內，則使亮點重合（用兩點間的中點替代）。?