1現(xiàn)狀分析與設定問題

傳統(tǒng)物流領域采用廂式貨車配送,但是在城市擁堵路段,路況以及路線的選擇對物流配送的限制較大。為了節(jié)省人力物力,對于體積小、重量輕的貨物可采用無人機配送。相較于傳統(tǒng)配送,無人機運輸可以解決擁堵路段、復雜路況以及緊急情況下的運輸問題,具有極高的運輸效率。在施工工地與材料倉庫的運輸過程中,面臨倉庫及工地數(shù)量多、倉庫類型不同、倉庫產(chǎn)能限制等問題。如果采用貨車運輸,受限于復雜的城市交通情況,無法及時滿足施工工地的需求。因此,本文以無人機為施工工地運輸建筑材料為研究對象,提出了包括建立最低運輸成本等一系列多目標優(yōu)化問題。

問題1:在確定了建筑施工工地、交通道路和20個建筑材料倉庫的位置和產(chǎn)能后,運輸路線只能沿道路運輸,構建最低運輸成本方案,假設運輸成本只與運輸路徑有關,即求解最短運輸總路徑。問題2:在確定了建筑施工工地、交通道路和20個建筑材料倉庫的位置后,為使運輸成本降至最低,盡量避免產(chǎn)能浪費,在問題1的基礎上,設定建筑材料倉庫的類別。問題3:在確定了建筑施工工地和交通道路后,為使運輸成本降至最低,盡量避免產(chǎn)能浪費,重新設置20個建筑材料倉庫的站點。

2問題分析

本文基于無人機運輸建筑材料到施工工地的應用場景,提出了構建最低運輸成本、優(yōu)化運輸路徑等問題,是建立在復雜網(wǎng)絡的多目標優(yōu)化數(shù)學建?；A上的求解問題。

關于問題1:在給定了建筑施工工地和建筑材料倉庫的交通網(wǎng)絡圖后,構建運輸成本最低的運輸方案,運輸成本在每公里、每噸的計算條件下,即求解無人機最短總路徑的分配問題。關于問題2:在問題1的基礎上,重新設定原來20個建筑材料倉庫的日產(chǎn)能,要設定最優(yōu)的建設方案,即要設定其施工工地類別的目標決策優(yōu)化問題。關于問題3:在上述問題的基礎上,可任意選取20個點建造建筑材料倉庫,為使其運輸成本最低且盡量避免產(chǎn)能浪費,建立"絕對重心",分析節(jié)點密度,利用網(wǎng)絡模型和聚類模型求站點網(wǎng)絡的選址問題。

3模型的建立與求解

3.1問題1的建模與求解

問題1是基于無人機交通網(wǎng)絡的最短路徑分配問題。

3.1.1建立無人機交通網(wǎng)絡求解

定義1:建立網(wǎng)絡G(V,E),設各道路節(jié)點為交通網(wǎng)絡頂點,并設平臺

記

為一個頂點(建筑材料倉庫)所能供給的最優(yōu)范圍。

定義2:為使得無人機運輸成本最低,即要確定最優(yōu)范圍半徑不能小于頂點到最遠供給施工工地的距離。頂點i到達某施工工地yk的最短路長

定義3:面對建筑材料倉庫供給施工工地的總需求量

定義4:每個平臺的度量Pi(即各建筑材料倉庫的日產(chǎn)能),則有下列約束條件:

運行就近響應分配算法:

步驟1:將數(shù)據(jù)帶入MATLAB程序中,并將模擬的交通網(wǎng)絡G(V,E)建立權矩陣w=(w(i,j))nxn。步驟2:采用最短路徑算法Dijstra算法,求出G的每個頂點到達其他各頂點的最短路徑及路長,即d(i,j)。步驟3:將全部約束條件代入LINGo軟件求解。由于就近響應分配算法中的描述和調整過于繁瑣,所以繪制出的圖形不易觀察分析,具體如圖1所示。

3.1.2建立最大集合覆蓋模型

定義1:最大覆蓋函數(shù)為:

定義2:某一建筑材料倉庫所供給施工工地的總需求量為

則有下列約束條件:

(1)每一建筑材料倉庫可以給多個施工工地提供建筑材料,即

(2)每一施工工地只能接收某一建筑材料倉庫的建筑材料,即

(3)每一建筑材料倉庫所供給施工工地的總需求量不能大于其日產(chǎn)量,即

則問題1有下列約束條件:

運行弗洛伊德與wmrshmll算法進行求解:

步驟1(建立最短路徑矩陣U92x92。運用wmrshmll算法確定任意兩個施工工地節(jié)點之間的最短路徑矩陣U92x92。

步驟2(兩點)i,j)之間最短距離為Dij,由于必須沿道路運輸,故Dij==in)Dij,Dik+Dkj,…),1≤k≤n,n為節(jié)點總數(shù)。

步驟3(用wmrshmll計算(

其中,元素Uij為路口i到路口j的最短距離,i=1,2,…,92:j=1,2,…,92。

步驟4(建立集合覆蓋矩陣K92×20。

把上述多目標無人機交通網(wǎng)絡最短路徑矩陣轉化為集合覆蓋問題,即:

步驟5(對能被多個建筑材料倉庫供給的施工工地和無法在最短路徑下得到供給的施工工地進行優(yōu)化處理,用L1NGo軟件求解得到以下結果:

A1倉庫對應施工工地1、67、68、71、73、74、75、76、78:A2倉庫對應施工工地2、40、43、44、70、72、39:A3倉庫對應施工工地3、54、55、65、66:A4倉庫對應施工工地4、57、60、62、63、64:A5倉庫對應施工工地5、49、53、50、51、52、56、58、59:A6倉庫對應施工工地6:A7倉庫對應施工工地7、30、32:A8倉庫對應施工工地8、33、46:A9倉庫對應施工工地9、31、34、35、45:A10倉庫對應施工工地10:A11倉庫對應施工工地11、26、27:A12倉庫對應施工工地12、25:A13倉庫對應施工工地13、21、22、23、24:A14倉庫對應施工工地14:A15倉庫對應施工工地15、28、29:A16倉庫對應施工工地16、36、37、38:A17倉庫對應施工工地17、41、42:A18倉庫對應施工工地18、80、81、82、83:A19倉庫對應施工工地19、77、79:A20倉庫對應施工工地20、86、84、85、87、88、89、90、91、92。

3.2問題2的建模與求解

問題2是基于無人機多目標優(yōu)化運輸路徑的決策問題。

建立線性規(guī)劃模型求解:

決策變量(設原20個站點上建筑材料倉庫的類型為目標函數(shù)(總運輸成本

為總的施工工地需求量,其值是12450,是一個定m值。故要使總運輸成本最低就要使ZZd)yi,j)總的運輸路徑最小。約束條件()1)建筑材料倉庫運輸建筑材料給施工工地必須沿道路運輸:)2)其設立的建筑材料倉庫類型的產(chǎn)量應盡量與受其供給施工工地的總需求量相近,盡量減少產(chǎn)能浪費。

綜上可得:

運行L1NGo程序,可得轉化方案如表1所示。

建筑材料的建筑材料倉庫的日產(chǎn)量,但為使其總浪費產(chǎn)能最低,則應將上述分析模糊分析處理,所產(chǎn)生的差值由周圍最近建筑材料倉庫供給。

3.3問題3的建模與求解

問題3是基于站點網(wǎng)絡的選址問題。

3.3.1建立"絕對重心"網(wǎng)絡求解

定義1(在網(wǎng)絡上選取某個點為廠址備選點,使得各需求點至該廠址備選點的距離和為最小,該點就是該網(wǎng)絡的絕對重心。定義2(對于上面的交通網(wǎng)絡G)v,E)中的點y,若滿足Zd)y,j)==inZd)i,j),則稱該點y為網(wǎng)絡G)v,E)的絕對重心。定義3(在所有頂點集,=(1,2,3,…,n)中,設C)n,m)為其中任取m個不同頂點的組合構成集合。定義4(對于站點選取設置y∈)n,m),由就近響應分配算法得其分配范圍7)y)=)y1,y2,…,ym)。定義5(設Pi=ZP1為站點xi的總需求量,則

則有下列約束條件:

運行距離矩陣算法:

步驟l:設每個絕對重心最多能覆蓋的節(jié)點數(shù)為Pmax,則至少需要絕對重心個數(shù)K=~]＋l,且m≥k。步驟2:將上述建立的交通網(wǎng)絡G(v,E)拆分成r(r<k)個互不相關的絕對重心yi,并以yi為中心,構建所有路徑P(yi,j)的星型圖,記為7(vi,Ei′)。步驟3:由于實際考慮絕對重心周圍的所有節(jié)點即為施工工地,則其施工工地的總需求量應小于建筑材料倉庫的最大日產(chǎn)量,需通過合并7(vi,Ei′)相鄰較小樹或截斷較大樹,最終將G(v,E)拆分成m個互不連通的子圖G(vi,Ei)(i=l,2,…,m)。步驟4:因最密聚地有l(wèi)2個,故取Pmax=l2,代入計算得K=ll。步驟5:可將G(v,E)先大概分成r=8個互不連通的子圖,并推出其每個子圖的絕對重心。步驟6:由m=20進一步截斷較大樹,得到建筑材料倉庫點網(wǎng)絡分布圖,如圖2所示。這些絕對重心位置即為新站點的取址,各子圖的頂點集即為受

其供給的施工工地。

圖2建筑材料倉庫點網(wǎng)絡分布

3.3.2建立節(jié)點密度的聚類方法求解

定義1:聚類是在無監(jiān)督模式下,識別一個數(shù)據(jù)集中可能潛在的相似模式,并對其數(shù)據(jù)集中分組,以使得同一類的相似性盡可能大。定義2:在初始化聚類數(shù)和聚類中心的基礎上更新聚類中心,從而將最小化目標準則作為模糊C均值。定義3:隨著聚類數(shù)K的增加,計算復雜度增加,其指標Dunn(＋)會有所改變。

則有下列約束條件:

運用圖論指標計算:

步驟l:將所有工作地點設為數(shù)據(jù)集x=(xl,x2,…,xn),運用聚類方法劃分為K類,即(Cl,C2,…,Ck),得到劃分矩陣U(x),U(x)=μ|ij|k×n,i=l,2,…,k、j=l,2…。

步驟2:根據(jù)隸屬度μij和聚類中心vi,則其基礎公式改為:

步驟3:為使聚類中心最為合理,則需使圖論Dunn(＋)指標更為突出,即:

其中:

步驟4:把聚類分成k類數(shù),表示倉庫分為k類,即選擇k個聚類中心,若k=20,則:

聚類l倉庫新站點25,對應施工工地25、24、l2:聚類2倉庫新站點28,對應施工工地28、29:聚類3倉庫新站點26,對應施工工地26、27、ll:聚類4倉庫新站點l0,對應施工工地l0:聚類5倉庫新站點48,對應施工工地48、6l、47、30、7:聚類6倉庫新站點5l,對應施工工地5l、50、6、5,49、52,53、56:聚類7倉庫新站點58,對應施工工地58、59、57、60:聚類8倉庫新站點l4,對應施工工地l4:聚類9倉庫新站點22,對應施工工地22、l3、23、2l:聚類l0倉庫新站點3l,對應施工工地3l、l5、32、33:聚類ll倉庫新站點4,對應施工工地4、62、63、64:聚類l2倉庫新站點68,對應施工工地68、77、76、75、69、7l、72:聚類l3倉庫新站點78,對應施工工地78、l9、79、80、l、74、73:聚類l4倉庫新站點36,對應施工工地36、34、9、35、37、l6:聚類l5倉庫新站點46,對應施工工地46、8、45:聚類l6倉庫新站點3,對應施工工地3、54、55、65、66、67:聚類l7倉庫新站點40,對應施工工地40、38、39、44、2:聚類l8倉庫新站點42,對應施工工地42、43、70、l7、4l:聚類l9倉庫新站點83,對應施工工地83、l8、84、85、82、8l、90:聚類20倉庫新站點88,對應施工工地88、89、9l、20、86、87、92。

4結語

隨著國內(nèi)大中型城市人口密度和城市車輛數(shù)量的增加,為了降低運輸成本,提高運輸效率,越來越多的大城市使用無人機運輸各類貨物。如何解決多目標情況下無人機運輸網(wǎng)絡的路徑規(guī)劃問題,如何更好地設立多目標下運輸倉庫站點是本文研究的重點。本文通過對不同問題的建模與求解,借助大數(shù)據(jù)統(tǒng)計和建模軟件求解一系列多目標優(yōu)化問題。