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

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

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

2問題分析

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

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

3模型的建立與求解

3.1問題1的建模與求解

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

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

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

記

為一個(gè)頂點(diǎn)(建筑材料倉(cāng)庫(kù))所能供給的最優(yōu)范圍。

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

定義3:面對(duì)建筑材料倉(cāng)庫(kù)供給施工工地的總需求量

定義4:每個(gè)平臺(tái)的度量Pi(即各建筑材料倉(cāng)庫(kù)的日產(chǎn)能),則有下列約束條件:

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

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

3.1.2建立最大集合覆蓋模型

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

定義2:某一建筑材料倉(cāng)庫(kù)所供給施工工地的總需求量為

則有下列約束條件:

(1)每一建筑材料倉(cāng)庫(kù)可以給多個(gè)施工工地提供建筑材料,即

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

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

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

運(yùn)行弗洛伊德與wmrshmll算法進(jìn)行求解:

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

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

步驟3(用wmrshmll計(jì)算(

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

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

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

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

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

3.2問題2的建模與求解

問題2是基于無人機(jī)多目標(biāo)優(yōu)化運(yùn)輸路徑的決策問題。

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

決策變量(設(shè)原20個(gè)站點(diǎn)上建筑材料倉(cāng)庫(kù)的類型為目標(biāo)函數(shù)(總運(yùn)輸成本

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

綜上可得:

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

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

3.3問題3的建模與求解

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

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

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

則有下列約束條件:

運(yùn)行距離矩陣算法:

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

其供給的施工工地。

圖2建筑材料倉(cāng)庫(kù)點(diǎn)網(wǎng)絡(luò)分布

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

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

則有下列約束條件:

運(yùn)用圖論指標(biāo)計(jì)算:

步驟l:將所有工作地點(diǎn)設(shè)為數(shù)據(jù)集x=(xl,x2,…,xn),運(yùn)用聚類方法劃分為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(＋)指標(biāo)更為突出,即:

其中:

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

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

4結(jié)語

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