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

無效

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

1.一種基于GIS富網絡屬性路網的大規模分類配送方法，其特征在于：所述富網絡屬性路網的目標節點分類配送方法包括以下步驟：

A1、獲得帶有至少包含OBJECTID*，Shape*，NAME，Shape_Length4個字段的路網矢量數據，對原始的矢量數據的不及、超過和節點不相交3種情況進行處理；

A2、處理不及、超過和節點不相交的3種情況，分3步糾正數據錯誤：

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

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

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

A3、建立GIS富網絡路網模型；通過GIS軟件（ArcGIS），建立網絡數據集，同時設置網絡數據集中的連通性，建立路網之間的拓撲關系；根據矢量數據中的Shap_Length字段屬性建立網絡數據集中的道路阻值;再對網絡數據集進行網絡分析，可以得到配送目標節點之間的最短距離的OD矩陣（源點到目標節點的距離矩陣），為車輛優化調度模型提供車輛行駛費用權值；

A4、建立配送目標節點分類模型；分類的目的是減小配送目標節點的規模，將配送范圍大而化小;在地理坐標下，提取各個目標節點的地理坐標；模型采用一種數據樣本分布算法，算法依照數據分布動態選取聚類中心，直至將所有的目標節點分類；具體模型如下：

假設樣本數據集U={L_z|z=1,2,…,n}，C_h(h=1,2,…,k)為第h個樣本數據集合，k為樣本數據集個數，L_z為第z個樣本數據，h為樣本數據集的下標，z為樣本數據的下標，n為樣本數據集中樣本數據的個數；

ch=1nhΣl∈Chl]]>(h＝1，2，…，k)????(1)

式(1)中c_h為類C_h的聚集中心，其中l為C_h中的樣本點，n_h為各類數據集中的樣本個數；樣本數據具有m個屬性，假設存在樣本x，y，且x，y∈U，則樣本數據x可以表示為x=(x₁,x₂，…,x_m)，樣本數據y可以表示為y=(y₁,y₂,…,y_m)，x和y之間的距離采用歐式距離：

dist[x,y]=(x1-y1)2+(x2-y2)2+...+(xm-ym)2---(2)]]>

dist[x,y]為樣本x，y之間的歐式距離，x₁,x₂,…,x_m是樣本數據x的m個屬性值，y₁，y₂，…，y_m是樣本數據y的m個屬性值；limit為允許加入集合的最大空間距離閥值：

limit=(max1≤A≤n,1≤B≤n(dist[A,B])-min1≤a≤n,1≤b≤n(dist[a,b]))/k---(3)]]>

式(3)中，A，B為n個樣本數據中最大歐式距離的兩個樣本數據，a，b為n個樣本數據中最小歐式距離的兩個樣本數據；樣本數據x與樣本數據集合C_h之間的最小距離為：

dist[x,C_h]=min(dist[x,l]),l∈C_h????(4)

樣本數據x與樣本數據集合C_j之間的最大距離為：

Dist[x,C_h]=max(dist[x,l]),l∈C_h????(5)

A5、建立車輛優化調度模型，考慮到運輸費用中的車輛費用、駕駛員補助費用、等待費用和車輛延遲費用建立目標函數；這里的車輛優化調度模型是針對分類后類中的目標節點建立的，模型中的配送目標點將小于原來整體的目標點；具體模型如下：

配送車輛向L個客戶送貨，每個客戶需求量為g_i(i=1,2,…,L)，其中i為客戶點，同時要求送貨的時間窗及卸貨時間分別為[et_i,lt_i]和ut_i(i=1,2,…,L)；車輛每小時等待費用為e_i，每小時延遲費用為f_i(i=1,2,…，L)；倉庫與客戶、客戶與客戶之間的最短運距、平均車速和車輛每公里費用分別為d_ij，v_ij和ω_ijr_ij(i,j=0,1,2,…,L)其中i，j為配送客戶點中的任意兩點；i=0時，為卷煙倉庫，ω_ij為道路狀況權重；配送車輛共有q₀類，其中第q類車輛有p₀輛，同時q類車輛載重量為v_qp(p=1,2,…,p₀)，每輛車每次配送最短大離不超過D_qp；駕駛員行車補助和加班補助每小時分別為s和es；駕駛員在行車途中到中午12:00和18:00時安排30min就餐時間，車輛當天返回配送倉庫；

運輸費用分別由配送車輛費用、駕駛員補助費用、等待費用和車輛延遲費用組成；配送車輛費用由燃油費用、車輛折舊費用和維護費用組成，管理者可以根據經營情況核算出每車每公里應付的配送車輛費用，且能將車輛費用轉化為線性變量；駕駛員補助費用中，如駕駛員工作時間不超過8小時，則以工作時間計算；如果駕駛員工作時間超過8小時，則超過部分時間應按加班補助費用計算；客戶貨運需求通常要在客戶規定時間范圍內送達，否則物流中心需要支付額外費用；如車輛提前達到客戶點，則支付等待費用；若車輛延遲到達客戶點，則支付延遲費用；

使車輛qp（第q類車的第p輛）從客戶j到達客戶i時刻為t_i，則t_i=t_j+ut_j+d_ij/v_ij，其中j為i的前一個客戶點，若t_j<12且t_i≥12或t_j<18且t_i≥18，則需要考慮駕駛員的就餐時間；對t_j<12且t_i≥12的情況，有：

ti=tj+uti+dij/vij+0.5,tj+utj<12dij/vij+12.5,12≤tj+utj≤12.5tj+utj+dij/vij,tj+utj>12.5---(6)]]>

t_j<18且t_i≥18的情況與(6)式類似；弧段(i,j)表示倉庫與客戶或客戶與客戶之間的最短路徑，x_ijqp=1表示車輛qp經過弧段(i,j)，x_ijqp=0表示車輛qp未經過弧段(i,j)；y_iqp=1表示車輛qp給客戶i送貨，y_iqp=0表示車輛不給客戶i送貨；令wt_qp表示駕駛員工作時間在8小時之內，可表示為wt_qp=min(t₀₀-t₀,8)，其中t₀是發車時刻，t₀=et_i-dt_i-d_0i/v_0i（i是第一個客戶點，dt_i為到達第一個客戶點的等待時間）或t₀=et_i+yt_i-d_0i/v_0i（i為第一個客戶點，yt_i為達到第一個客戶點的延遲時間），t₀₀為車輛返回倉庫時刻；ewt_qp表示駕駛員的加班時間，可表示為ewt_qp=max(t₀₀-t₀-8,0)；每條線路客戶點配送量之和要小于線路車載量，可表示為：

Σi=0LΣj=0Lyiqpgi≤vqp]]>

A為懲罰因子，是一個足夠大的正整數，Z為總配送費用；假定各項費用呈線性變化，則有目標函數：

minZ=Σi=0LΣj=0LΣq=1q0Σp=1p0dijωijrijxijqp+Σi=0LΣq=1q0Σp=1p0yiqp(wtqp·s+ewtqp·es)]]>

+Σi=1Lei·max(eti-ti,0)+Σi=1Lfi·max(ti-lti,0)---(7)]]>

+AΣq=1q0Σp=1p0max(Σi=0LΣj=0Ldijxijqp-Dqp,0)]]>

在上述目標函數式中，前4項分別為配送車輛費用、駕駛員補助費用、車輛等待費用和延遲費用；在第4項中，如客戶i不允許配送車輛延遲到達，則可以使f_i為足夠大的正數；第5項限制車輛行駛距離不能超過最大配送距離，線路中任何一輛車超過最大配送距離都會引起上述目標函數急劇增大，從而保證搜索時在可行域之內；

A6、分類算法設計；因為聚類簇是在數據分布密集區域形成，所以選取這些密集區域的平均值作為初始的聚類中心；為了找到與數據在空間分布上相一致且可代表k個聚類的數據集合，輸入聚類個數k，含有n個樣本的數據集合，同時輸出k個數據中心；算法步驟如下：

①利用式(2)計算距離矩陣D=(d_rs)，其中d_rs=dist[r,s](1≤r≤n,1≤s≤n)，其中r，s為樣本數據；

②掃描坐標距離矩陣D，尋找距離的最大值和最小值，用式(3)計算limit；

③掃描坐標距離矩陣D，尋找矩陣中距離最小的2個數據a，b，將數據a，b加入集合C_h(h=1,2,…,k)，C_h={a,b}，同時將數據a，b從U中刪除，更新距離矩陣D；

④利用(4)式在U中尋找距離集合C_h最近的樣本數據t，如果Dist[t,C_h]小于limit，則將t加入集合C_h，同時將t從集合U中刪除，更新距離矩陣D，重復⑤，否則停止；

⑤若r<k，r=r+1，重復步驟③、④，直至k個集合完成；

⑥取集合C_h(1≤h≤k)中數據的算術平均值記作數據中心c_h，并計算得到c_h的坐標值，完成k個數據中心的選取；

A7、車輛優化調度算法設計；通過A5，已經將較大配送目標點大而化小，假設平均分配，則每一類中的配送目標節點為原來的1/k；此時再對每一類中的配送目標節點采用車輛優化調度算法，即可得到配送結果；步驟如下：

①根據類中客戶點數目產生初始種群進行遺傳編碼；

②計算種群的適應度函數；

③最優選擇與輪盤賭選擇相結合的方法進行刪減、復制染色體，最終產生新種群；

④以交叉概率p_c對種群進行交叉操作，檢查是否滿足約束條件，產生新種群；

⑤以變異概率p_m對種群進行變異操作，檢查是否滿足約束，形成新種群；

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

⑦對計算結果進行解碼；

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