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

在審

• 申請號: 201310733371.6
• 申請日: 2013-12-26
• 公開（公告）號: CN103699982A
• 公開（公告）日: 2014-04-02
• 發明（設計）人: 張貴軍;郭冰冰;明潔;鐘思恒
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06Q50/28
• 代理公司: 杭州斯可睿專利事務所有限公司 33241
• 代理人: 王利強

1.一種帶軟時間窗口的物流配送控制方法，其特征在于：所述物流配送控制方法包括以下步驟：

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

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

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

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

以運輸費用建立目標函數，運輸費用分別由配送車輛固定費用、運輸費用、車輛等待費用和延遲費用組成；其中，配送車輛固定費用由車輛折舊費用和維護費用組成，該部分費用只與配送的車輛數有關，運輸費用與車輛所行使的路段狀況有關，包括路段長度，路段的擁擠狀況，還包括整個路段中所經過的交通燈、收費站所產生的時間成本及收費情況，客戶貨運需求通常要在客戶規定時間范圍內送達，否則物流中心需要支付額外費用，這里的車輛優化調度模型是針對分類后類中的目標節點建立的，具體模型如下：

配送路網模型描述為：

G=(A∪B∪V,R)A={a1,a2,...,an}B={b1,b2,...,bm}V={v1,v2,...vk}R={Rs}]]>

其中A為路網中生產地集合，B為路網中客戶節點集合，V為路網中道路交點集合，它們構成網絡的頂點，R為道路中的有向路段集；

運輸成本最低模型為：帶軟時間窗的動態車輛路徑規劃問題，目標函數為：

minZ=Σk=1mck+Σg=0nΣh=0nΣk=1kcghxghk+p1Σj=1nmax(Sj-tj,0)+p2Σj=1nmax(tj-Ej,0)]]>

s.t.

①a_i＞b_j,i∈{1,2,...,m},j∈{1,2,...,n}；

②c_k為每輛車的固定成本；

③m取整數，為配送車輛數，a為參數，0＜a＜1，約束條件越多，貨物裝卸車越復雜，a越小；

④c_gh為路段(v_g,v_h)的運輸成本，與該路段的長度和路段的擁擠狀況有關，以及所包含的交通燈以及收費站的數量有關，c_gh＝c_gh'd_gh+c_gh''l_gh其中c_gh'為路段(v_g,v_h)單位距離的費用，d_gh為路段(v_g,v_h)的距離，c_gh''為路段(v_g,v_h)所經過的交通燈以及收費站的單位費用，l_gh為該路段所包含的交通燈和收費站的數量；

⑤x_ghk＝{0,1}，車輛k經過路段(v_g,v_h)，x_ghk＝1，否則為0；g,h∈{0,1,2...,n},k∈{1,2,...m}；

⑥y_jk表示若客戶點j的任務由車輛k完成，y_jk＝1，否則y_jk＝0；q為車輛的最大載重量；

⑦[S_j,E_j]客戶點j的配送時間窗要求；

⑧t_j為車輛到達客戶點j的時刻；

⑨p₁，p₂分別為早于和超出到達客戶點j時間窗的懲罰成本系數；

其中min表示最小，max表示最大，s.t.表示約束條件；

A3.模糊聚類分析：采用基于定量分析和定性分析相結合的方法來進行聚類，首先根據目標節點的時間窗屬性對客戶點進行初步劃分，然后再結合定量的方法按客戶位置進行客戶的聚類分析，通過模糊聚類分析將大規模的車輛路徑規劃的問題降級，轉化成小規模的組合優化問題進行求解，模糊聚類分析步驟如下：

3.1）客戶訂單信息的獲取，包括客戶的地理位置和需求量；

3.2）根據研究的對象，選擇與研究對象的關系密切的指標，先進行定量分類；

3.3）對數據的標準化；

3.4）建立模糊相似矩陣；

3.5）模糊等價關系的建立；

3.6）進行聚類分析，給定不同的置信水平，求R_λ截陣，找出R的λ顯示,每個樣品歸為一類，隨著λ的降低，由細變粗逐漸并類；

A4.車輛優化調度啟發式算法設計，通過A3，已經將較大配送目標點大而化小，此時再對每一類中的配送目標節點采用車輛優化調度算法，即可得到配送結果，步驟如下：

4.1）采用自然數編碼方法，根據類中客戶點數目產生初始種群進行遺傳編碼，構造客戶點作為配送路線優化問題解向量中的染色體，

4.2）計算每個配送方案的種群適應度函數，對于目標函數取最小化的組合優化問題,其適應度函數就要對目標函數進行適當的變化，以轉化為極大化的情況，且保證適應度值非負，

4.3）最佳個體保存法與輪盤賭選擇相結合的方法進行刪減、復制染色體，最終產生新種群，

4.4）采用順序交叉法實施交叉操作，以交叉概率p_c對種群進行交叉操作，檢查是否滿足約束條件，產生新種群，

4.5）采用多次對換變異方法，以變異概率p_m對種群進行變異操作，隨機產生一個交換次數L，檢查是否滿足約束，形成新種群，

4.6）判斷是否滿足終止法則，達到最大迭代次數或達到最優解要求，滿足要求則停止，否則轉入4.3），

4.7）計算結果進行解碼，

4.8）選擇所有解碼后的計算結果，并進行比較選取費用最小者。