[發明專利]一種帶軟時間窗口的物流配送控制方法

在審

• 申請號: 201310733371.6
• 申請日: 2013-12-26
• 公開（公告）號: CN103699982A
• 公開（公告）日: 2014-04-02
• 發明（設計）人: 張貴軍;郭冰冰;明潔;鐘思恒
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06Q50/28
• 代理公司: 杭州斯可睿專利事務所有限公司 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問題的研究，沒有考慮道路的行車實際情況，如：通流能力、道路節點等地理信息因素考慮進去；③現有的研究多是針對硬時間窗情況，要求車輛必須在規定時間段內到達，較少考慮車輛可以在時間窗外到達，但會增加成本費用。

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

發明內容

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

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

一種帶軟時間窗口的物流配送控制方法，所述物流配送控制方法包括以下步驟：

A1.建立網絡模型，使用ArcGIS軟件，建立網絡數據集和路網之間的拓撲關系；根據矢量數據中的Shap_Length字段屬性建立網絡數據集中的道路阻值；再對網絡數據集進行網絡分析，得到配送目標節點之間的最小費用的OD矩陣，為車輛優化調度模型提供車輛行駛費用權值，考慮道路節點，為道路交通燈路口、收費站賦予費用權重；

A2.建立帶軟時間窗車輛優化調度模型VRPTW；

問題描述：有m個產品生產地A生產某種產品，其產量分別為a_i，有n個客戶點B，其需求量分別為b_j，按照客戶點的需求將產品在規定時間窗內配送，如果各項配送任務沒有在指定的時間范圍內完成，則給予懲罰；

要求各車輛的行駛路線滿足約束條件：i.每條路線的起點必須是生產地，終點為客戶點，不考慮回程；ii.每條路線的總載量不得大于運載車輛的最大允許載重量；iii.每個指定客戶必須僅被服務一次；iv.每個客戶都有它被服務的規定的時間窗限制，如果車輛提前達到客戶點，則支付等待費用，若車輛延遲到達客戶點，則支付延遲費用；