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

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

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

2問題分析

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

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

3模型的建立與求解

3.1問題1的建模與求解

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

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

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

記

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

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

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

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

運行就近響應(yīng)分配算法:

步驟1:將數(shù)據(jù)帶入MATLAB程序中,并將模擬的交通網(wǎng)絡(luò)G(V,E)建立權(quán)矩陣w=(w(i,j))nxn。步驟2:采用最短路徑算法Dijstra算法,求出G的每個頂點到達其他各頂點的最短路徑及路長,即d(i,j)。步驟3:將全部約束條件代入LINGo軟件求解。由于就近響應(yīng)分配算法中的描述和調(diào)整過于繁瑣,所以繪制出的圖形不易觀察分析,具體如圖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)絡(luò)最短路徑矩陣轉(zhuǎn)化為集合覆蓋問題,即:

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

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

3.2問題2的建模與求解

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

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

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

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

綜上可得:

運行L1NGo程序,可得轉(zhuǎn)化方案如表1所示。

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

3.3問題3的建模與求解

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

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

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

則有下列約束條件:

運行距離矩陣算法:

步驟l:設(shè)每個絕對重心最多能覆蓋的節(jié)點數(shù)為Pmax,則至少需要絕對重心個數(shù)K=~]＋l,且m≥k。步驟2:將上述建立的交通網(wǎng)絡(luò)G(v,E)拆分成r(r<k)個互不相關(guān)的絕對重心yi,并以yi為中心,構(gòu)建所有路徑P(yi,j)的星型圖,記為7(vi,Ei′)。步驟3:由于實際考慮絕對重心周圍的所有節(jié)點即為施工工地,則其施工工地的總需求量應(yīng)小于建筑材料倉庫的最大日產(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)絡(luò)分布圖,如圖2所示。這些絕對重心位置即為新站點的取址,各子圖的頂點集即為受

其供給的施工工地。

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

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

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

則有下列約束條件:

運用圖論指標計算:

步驟l:將所有工作地點設(shè)為數(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,則其基礎(chǔ)公式改為:

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

其中:

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

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

4結(jié)語

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