動態(tài)物流路徑優(yōu)化方案研究動態(tài)物流路徑優(yōu)化方案的研究，是建立在對給定區(qū)域優(yōu)先保證特殊供貨點， A,B,C后進行區(qū)域劃分基礎上，(x，y)確定合適的車輛數(shù)、行車路徑，實時記錄車輛當前位置坐標的一種動態(tài)管理過程。1模型假設(1)假設各處路況都是相同的，物流運輸車行駛不受天氣、堵車等因素影響，物流運輸車在道路上均能按平均車速行駛。(2)假設物流運輸車在供貨過程中除了運輸時間，不做其他任何停留和休息，人員換班時間不計。(3)假設所有物流運輸車24小時供貨，連續(xù)正常工作，沒有發(fā)生機械故障等問題，不考慮其他與路徑優(yōu)化求解無關的問題情況。2動態(tài)物流路徑優(yōu)化的模型設計與實現(xiàn)2.1確定動態(tài)物流運輸中車輛數(shù)確定動態(tài)物流運輸中車輛數(shù)一般利用 Floyd算法，F(xiàn)loyd是求任意兩點間最短距離一種方法，在交通分配中應用較為廣泛。用 Floyd算法求出所有節(jié)點間的最短距離矩陣 D并將區(qū)域平面內(nèi)的道路交叉口節(jié)點分別標號為 1,2……k,求最短距離矩陣的Floyd算法步驟如下：先根據(jù)題目數(shù)據(jù)給初始矩陣 D賦值，其中沒連通的節(jié)點的賦值為R,以便于更新。進行迭代計算，對任意兩點 (i,j)，若存在，使D(i,k)D(k,j)：：：D(i,j)，則更新D(i,j)=D(i,k)D(k,j)。

（3）直到所有點的距離不再更新停止計算。則得到最短路距離矩陣D(i,j=1,2,3..…D(i,j=1,2,3..…k)定義1設P（Vi,Vj）是賦權圖G從Vi到Vj的路徑，則稱Pe（Vi,Vj）為路徑P（Vi,Vj）的權。定義2在賦權圖G中，從頂點Vi到Vj的具有最小權的路徑p*（V,Vj）稱為Vi到Vj的最短路。最短路徑問題通常將它們抽象為圖論意義下的網(wǎng)絡問題 [1]，問題的核心就變成了求網(wǎng)絡圖中任意兩供貨節(jié)點之間的最短路。供貨點間距離用矩陣 D來表示。點間距離用矩陣D來表示。式中：p（Vi,Vj）——兩供貨點之間的路徑；G――賦權圖；Vi――區(qū)域中第個需要供貨的點；Pe（Vi,Vj） 每條路徑的權重；p*（y,Vj）――兩供貨點之間的最短路徑；D——最短距離矩陣。根據(jù)供貨區(qū)平面圖，用階數(shù)為kk的0-1矩陣d用來表示各供貨點之間連通與否， 假設0節(jié)點i到j之間可連通d?.=丿ij1節(jié)點i到j之間可連通其中：i,j=1,2……k且dij為了使物流運輸車在一次遍歷中以最少的重復路徑進行供貨，減少互不連通回路個數(shù)，引入額外變量*=（1,2……）k，并加入一個充分約束條件Ui-Ujndj-n-1,1：：i=j蟲k,n=k若i與j可構成回路，則有

dj=iUi—Uj蘭-1uj_Uj啟-1得，0_2不等式成立，節(jié)點i與j可構成回路。若與不構成回路，則有4=o』dji=0Ui 一Uj 王k一1uj一Uj 王k一1得，0丄2(k-1)，等式矛盾，節(jié)點i與j不可構成回路。綜上所述，可得到供貨區(qū)平面內(nèi)任意兩個連通節(jié)點之間的最短路徑模型如下:nminz八dijDiji,j呂嚴n為dij—1j—1, >ki=1￥n為dj i二1，……,kj二st.jUi一Uj+ndjj蘭n-1, 1vi式j蘭n,n=kdj=0或1i,j=1,……,kUi為整數(shù)，i=1,……,kH為整數(shù)，j=1,……,k式中：U式中：Ui為減少互不連通回路個數(shù)而設置的額外變量;n――表示整個供貨區(qū)域中的所有道路交叉節(jié)點數(shù);Dij――供貨點與點之間的最短連通距離。2.3各物流運輸車動態(tài)坐標位置數(shù)據(jù)求解2.3.1行車方式(1)輻射形行車路線：指運輸車行使時從起點到終點后任按照原路線返回。 (2)環(huán)形行車路線：指運輸車從起點出發(fā)單向行駛， 繞行一周，經(jīng)過子區(qū)域內(nèi)各個交叉點，不走重復路線，回到出發(fā)點。(3)混合形行車路線：即是包含輻射形和環(huán)形兩種結構形式的行車路線。根據(jù)各個子區(qū)域內(nèi)行車效果評價指標的要求， 輻射形結構形式的行車路線顯然是不優(yōu)化的， 因而選用環(huán)形或混合形行車路線。2.3.2運輸車坐標位置求解(1)物流運輸車正常運輸時， 每秒鐘步長為y/36O0(m)(為了保證位置精確，步長設定按秒計算的方式；還有就是為了減小迭代過程中未走完路徑不能被最小步長整除， 而進入下一路徑循環(huán)計算所引起的誤差)。(2)根據(jù)道路的起始節(jié)點和下一節(jié)點的橫縱坐標，來確定該條道路與水平正方向的夾角B。 (3)第j次迭代計算時，物流運輸車的橫坐標位置為該條道路初始節(jié)點橫坐標值加上 p<v/3600(m)xco曲(j=1,2,3「)，縱坐標為該條道路初始節(jié)點縱坐標值加上。(4)判斷物流運輸車位置，若未走完該條道路則返回步驟 (3),若走完該條道路以下一節(jié)點繼續(xù)步驟(2),直至把運輸路線走完為止。3實例應用的分析現(xiàn)有某地商品銷售連鎖店的分布節(jié)點區(qū)域圖，如圖 1所示。圖1中以“X”表示道路交叉口節(jié)點，A,B,C分別表示三個優(yōu)先供貨部位，圖中的圓區(qū)域表示優(yōu)先供貨車輛能覆蓋的供貨范圍(圓以A,B,C為圓心，以2km為半徑的圓，半徑大小確定，后面會有具體計算說圖1整個區(qū)域道路交叉口節(jié)點表示圖3.1確定動態(tài)物流運輸中車輛數(shù)由交叉口坐標，每條道路起始、終止交叉口編號，計算出每條道路的道路長度， 所求出的每條道路長度如下表1所示。表1每條道路長度單位：m序號起始交叉口編號終止交叉口編號道路長度1122754.221351033.73252034.14221850.8536720.2該區(qū)域內(nèi)共有 458條道路，根據(jù)表1利用Floyd可求解出所有道路長度和為 551760m，這樣可以得出需求車輛上限值nn551760nI'v（輛）,vi是根據(jù)該物流部門統(tǒng)計的一組車輛行駛速度數(shù)據(jù)，為了保證其它i4意外情況發(fā)生依然能保證正常供貨， 可以適當放寬車輛需求額度；也可以應用概率方法以供貨時間和供貨滿意度為指標，得到滿足該條件下車輛需求置信區(qū)間。式中：w――第輛運輸車行駛速度。所求出的最短距離矩陣D如表2所示。表2任意兩點最短距離矩陣 單位：m02754.26300.55256.34788.37020.797047668.7?2754.203546.32502.12034.14266.56949.84914.5?6300.53546.301044.21512.2720.23403.51368.2?5256.32502.11044.204681764.44447.72412.4?4788.32034.11512.246802232.44915.72880.4?7020.74266.5720.21764.42232.402683.3648?97046949.83403.54447.74915.72683.302035.3?7668.74914.51368.22412.42880.46482035.30?????????0考慮到重點部位的優(yōu)先供貨需求， 以A,B,C點為圓心，半徑為Vi（2/60）=y/30（km）畫圓（圖1設定v=60km），找到a，b，C所構成的三角形的外接圓的圓心 （圖中星號表示V- _該點），畫半徑Vi（2/60）Lkm圓，從而求得保證在隨機缺貨時間 t內(nèi)到達優(yōu)先供貨部30位的最小圓區(qū)域。在該圓區(qū)域內(nèi)專門配備一輛供貨車， 可使優(yōu)先部位的供貨時間和供貨滿意度的顯著性要求得到更好滿足，并明顯優(yōu)于按照指定路線供貨的情形。 模型還要對整個供貨銷售點的隨機缺貨時間進行統(tǒng)計，統(tǒng)計各供應點的缺貨時間 t報表，當然也可以應用概率方法估算t為上述最小圓確定提供實際理論根據(jù)。然后剔除已經(jīng)被最小圓覆蓋的節(jié)點，得出該區(qū)域內(nèi)還有 402條道路，根據(jù)剔除后的節(jié)點再次求解，可求解出所有道路長度和為493621m，這樣可以得出需求車輛上限值n493621n/vVi（輛），考慮優(yōu)先供貨情況及正常供貨情況，得出一共需求車輛數(shù)目。iT3.2最短路徑模型區(qū)域劃分原則，考查實際的城市物流運輸分區(qū)情況，在模型中分區(qū)原則規(guī)定如下：(1)結合人口密集區(qū)、道路網(wǎng)密集程度，越密集，分區(qū)應越多。 (2)各個子區(qū)域內(nèi)的節(jié)點數(shù)相當。(3)各個子區(qū)域的面積相近。將商品銷售連鎖店的區(qū)域應用上述區(qū)域劃分原則進行劃分， 在模型計算過程中通過Lingo動態(tài)規(guī)劃法求解，現(xiàn)以劃分后區(qū)域 7內(nèi)12個供貨節(jié)點為例，計算其最佳行車路線方案，得到如圖2所示行車路線(其他區(qū)域通過區(qū)域劃分后，計算方法一樣) 。計算得到物流運輸車行駛路程 16899.40km，其中：x(1,3)=1x(2,1)=1x(3,6)=1x(4,8)=1x(5,2)=1x(6,11)=1x(7,4)=1x(8,9)=1x(9,5)=1x(10,7)=1x(11,12)=1x(12,10)=1, 表示12個節(jié)點供貨路徑先后順序(x(i,j)=1表示i—j，然后找下一節(jié)點 x(j,k)=1，得到i—j，這樣依次，轉換成圖1，轉換成圖1中對應的供貨節(jié)點:D193~D255~D275~D297T298~D291~D276~D260~D287~D289~D270~D211D193在聚類過程中，下一供貨點是否聚類到當前路徑， 既考慮到當前車輛可容納的負荷， 又充分利用了已知的需求信息， 綜合考慮了下一供貨點的需求情況。 這樣就能得出任意時刻， 下一供貨點歸屬那個供貨路徑， 是否聚類到當前所在區(qū)域車輛供貨路徑中， 給出優(yōu)劣判斷的依據(jù)，還可以為上述的聯(lián)動操作提供方案， 這樣使得實際供貨更具備柔性過程特征， 減小供貨時間提高供貨滿意度。3.3各物流運輸車正常運行坐標位置數(shù)據(jù)求解通過上述計算得到在一個供貨周期內(nèi)，物流運輸車在劃分后區(qū)域內(nèi)正常行使距離與路徑，結合最短距離矩陣及通過“先聚類后排序”確定每輛車對應的供貨節(jié)點，利用 lingo動態(tài)規(guī)劃法得出其最佳供貨行車路線，借助智能交通系統(tǒng) ITS中的路徑誘導系統(tǒng)RGS，充分利用交通信息資源給與有效的路徑誘導， 為當前時刻運輸車提供所在位置的最優(yōu)行車路線， 相互之間對突發(fā)事件進行聯(lián)動操作， 這樣可以實現(xiàn)動態(tài)管理物流路徑， 克服傳統(tǒng)意義上的確定路徑非實時監(jiān)控缺點。通過Matlab程序計算：設定供貨車輛平均行駛速度時，得到 7供貨區(qū)域內(nèi)供貨車輛正常行使位置坐標如下表 3所示。表3任意一時刻運輸車坐標單位：m\時|'間\位置\123456789101112131415626261616060592958585757565656x516172738394940y3029292929282828282827272727260281593715947250290785644220984動態(tài)物流運輸中車輛數(shù)合理性檢驗根據(jù)參考文獻［2］，圓在近似正方形區(qū)域內(nèi)的覆蓋效率大約 80%?85%，當供貨節(jié)點缺貨后，可以提高車輛的平均行駛速度，假設變?yōu)?w/l(km/h)，則在供貨規(guī)定時間內(nèi)覆蓋圓的22圓形面積為：二Wti/(I60)km。整個區(qū)域的面積估算為xy(km)2(x,y表示供貨區(qū)域?qū)膞,y坐標(單位：km))則覆蓋該區(qū)域所需圓的個數(shù)為Xxy/SxMxtj/(I漢60)丫9.,(［］表示取整)，則在該區(qū)域內(nèi)需要y/伉x(y0/(I江60應丿輛車運輸車則可實現(xiàn)80%以上的供貨覆蓋率。這與通過Floyd算法得出總運輸路徑需車輛數(shù)相吻合，從而驗證了模型求解的正確性。模型計算建立過程中對上下貨時間沒考慮等， 可以把將這些作為一個隨機數(shù)進行分析， 可用均勻分布或泊松分布來描述該因素的影響， 把這些元素加入到供貨周期中，假設