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

有效

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

1.一種基于meanshift分類的大規(guī)模客戶點分類配送方法，其特征在于：所述分類配送方法包括以下步驟：

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

A2、建立配送目標(biāo)節(jié)點分類模型；

在地理坐標(biāo)下，提取各個目標(biāo)節(jié)點的地理坐標(biāo)，依據(jù)樣本密度動態(tài)選取聚類中心，直至將所有的目標(biāo)節(jié)點分類；具體模型如下：

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

Mh=1kΣxi∈sk(xi-x)---(1)]]>

S_k是一個半徑為h的圓形區(qū)域，滿足以下關(guān)系的y點的集合，

S_h(x)={y:(y-x_i)_T(y-x_i)<h²}??????(2)

k表示在這n個樣本點x_i中，有k個點落入S_k區(qū)域中，在2維空間中，任選一個點，然后以這個點為圓心，h為半徑做一個圓形區(qū)域，落在這個圓內(nèi)的所有點和圓心都會產(chǎn)生一個向量，向量是以圓心為起點落在球內(nèi)的點位終點，然后把這些向量都相加，相加的結(jié)果就是Meanshift向量，再以meanshift向量的終點為圓心，再做一個半徑為h的圓，重復(fù)以上步驟，得到一個新的meanshift向量，如此重復(fù)下去，meanshift算法收斂到概率密度最大的點，該點就是聚類的中心點；

A3、建立車輛優(yōu)化調(diào)度模型，所述車輛優(yōu)化調(diào)度模型是針對分類后類中的目標(biāo)節(jié)點建立的，模型中的配送目標(biāo)點將小于原來整體的目標(biāo)點；具體模型如下：

配送車輛向L個客戶送貨，將L個客戶分成K類，每個客戶需求量為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為道路狀況權(quán)重；配送車輛共有q₀類，其中第q類車輛有p₀輛，同時q類車輛載重量為v_qp(p＝1,2,…,p₀)，每輛車每次配送最短距離不超過D_qp；駕駛員行車補(bǔ)助和加班補(bǔ)助每小時分別為s和es；駕駛員在行車途中到中午T₁時刻和下午T₂時刻安排Ｐ分鐘就餐時間，車輛當(dāng)天返回配送倉；

使第q類車的第p輛車輛qp從客戶j到達(dá)客戶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---(3)]]>

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

Σi=0LΣj=0Lyiqpgi≤vqp---(4)]]>A為懲罰因子，是一個足夠大的正整數(shù)，Z為總配送費用；假定各項費用呈線性變化，則有目標(biāo)函數(shù)：

在所述目標(biāo)函數(shù)式中，前4項分別為配送車輛費用、駕駛員補(bǔ)助費用、車輛等待費用和延遲費用；在第4項中，如客戶i不允許配送車輛延遲到達(dá)，則使f_i為

minZ=Σi=0LΣj=0LΣq=1q0Σp=1p0dijwijrijxijqp+Σi=0LΣq=1q0Σp=1p0yiqp(wtqp·s+ewtqp·es)+Σi=1Lei·max(eti-ti,0)+Σi=1Lfi·max(ti-lti,0)+AΣq=1q0Σp=1p0max(Σi=0LΣj=0Ldijxijqp-Dqp,0)---(5)]]>

足夠大的正數(shù)；第5項限制車輛行駛距離不能超過最大配送距離；

A4、首先采用N階最短近鄰算法，確定大規(guī)模客戶點分類的數(shù)目k，并將k值傳遞給meanshift算法，所述meanshift算法用于確定大規(guī)模客戶點分類后的聚類中心，以及各個聚類包含的客戶點；所述meanshift算法的過程如下：

Step1：將N階最短近鄰算法得到的k值作為參數(shù)輸入；

Step2：隨機(jī)產(chǎn)生一個中心R₀，并以R₀為圓心生成一個半徑為d的圓；

Step3：計算meanshift向量，將落在圓內(nèi)的每個樣本點和圓心R₀都會產(chǎn)生一個向量，然后求出這些向量的矢量和，得到meanshift向量；

Step4：再以meanshift向量的終點為圓心再做一個半徑為d的圓，得到一個新的meanshift向量，該步驟直到meanshift向量收斂為零向量，從而得出該聚類的中心R₁；

Step5：將已經(jīng)聚類的樣本點排除在外，在剩下的樣本點中再次重復(fù)step2～step4，得到剩下的k-1類的樣本點中心R₂-R_k；

A5、假設(shè)平均分配，則每一類中的配送目標(biāo)節(jié)點為原來的1/k；此時再對每一類中的配送目標(biāo)節(jié)點采用車輛優(yōu)化調(diào)度算法，即可得到配送結(jié)果；所述車輛優(yōu)化調(diào)度算法的步驟如下：

①根據(jù)類中客戶點數(shù)目產(chǎn)生初始種群進(jìn)行遺傳編碼；

②計算種群的適應(yīng)度函數(shù)；

③最優(yōu)選擇與輪盤賭選擇相結(jié)合的方法進(jìn)行刪減、復(fù)制染色體，最終產(chǎn)生新種群；

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

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

⑥判斷是否滿足終止法則，達(dá)到最大迭代次數(shù)或達(dá)到最優(yōu)解要求，滿足要求則停止，否則轉(zhuǎn)入③；

⑦對計算結(jié)果進(jìn)行解碼；

⑧選擇所有解碼后的計算結(jié)果，并進(jìn)行比較選取結(jié)果最小者。