陸 玲 玲, 胡 志 華
(上海海事大學 物流研究中心,上海 201306 )
海島應急物流作為海島應急管理的關(guān)鍵一環(huán),在面臨道路中斷、天氣惡劣等挑戰(zhàn)時,如何快速、安全地將應急生活物資精準運往需求點,在提高救災效率與安全性的同時,更好地控制系統(tǒng)總成本,是海島應急物流的核心命題.
作為物流行業(yè)邁向自動化、智能化發(fā)展的典型代表之一,無人機將成為解決海島應急物流配送安全和效率問題的一大利器.當海島出現(xiàn)突發(fā)地質(zhì)災害等情況時,傳統(tǒng)的輪渡運送方式一方面缺乏物資轉(zhuǎn)運的靈活性,另一方面,配送人員的人身安全也無法得到保障.此時,若利用無人機生存能力強、機動性能好等優(yōu)勢,在短時間內(nèi)將應急物資從碼頭運往海島上的無人機配送中繼站,再由卡車將物資送往需求點,既能提高抗災救災效率,又能降低因為人員疲勞或單調(diào)場景作業(yè)造成的安全隱患.
“十四五”期間,將進一步擴大無人機物流配送試點范圍,服務鄉(xiāng)村振興戰(zhàn)略.此前,國內(nèi)外學者對于無人機在物流領(lǐng)域的應用已有了較為深入的研究.無人機在飛行過程中產(chǎn)生能耗和電池維護成本,但是投遞小型包裹依然具有經(jīng)濟可行性[1].垂停是無人機設(shè)計的關(guān)鍵技術(shù)問題,用于包裹配送的無人機同樣需要解決和利用懸??刂颇芰2].翁丹寧[3]剖析了無人機進入商業(yè)領(lǐng)域物流配送的主要影響因素.楊代勇[4]提出構(gòu)建一個完整的新型物流配送法律體系應從統(tǒng)一行業(yè)標準體系、強化監(jiān)督管理機制、完善相關(guān)法律法規(guī)3個方面入手.目前已有文獻研究了無人機與卡車合作進行交付的配送模式[5],這種合作模式在最后1 km 的物流配送過程中得到了進一步應用[6].
利用無人機將碼頭物資運往海島災區(qū)的重要前提是確定災區(qū)對接點,在海島中選取一定數(shù)量的無人機配送中繼站負責將物資送往需求點,再由終端卡車從中繼站出發(fā),對該區(qū)域所有需求點進行遍歷,最終回到無人機配送中繼站,從而形成一個兩級海島應急物流網(wǎng)絡(luò).von Boventer[7]最早提出這種將網(wǎng)絡(luò)中設(shè)施選址和路徑優(yōu)化問題綜合考慮的選址-路徑問題(location-routing problem,LRP),對問題中設(shè)施點的選址和運送成本的關(guān)系進行了研究.按照節(jié)點類型,LRP可分為單層選址-路徑問題、雙層選址-路徑問題和多層選址-路徑問題.雙層選址-路徑問題[8]通過決策物流網(wǎng)絡(luò)中備選點的位置和數(shù)量來規(guī)劃兩個層級之間的卡車配送路徑.以物流系統(tǒng)總成本最小為目標函數(shù),建立兩階段隨機規(guī)劃模型[9];加入生產(chǎn)計劃與時間窗約束,利用啟發(fā)式算法求解[10].此外,建立LRP混合整數(shù)規(guī)劃模型,應用于生物質(zhì)資源的供應領(lǐng)域[11].
國內(nèi)對于LRP的研究開始相對較晚,汪壽陽等[12]對LRP的主要研究進展作出綜述,分析了求解該問題相關(guān)算法的主要特點.此后,李冰等[13]、馬艷芳等[14]、劉建仁[15]研究了生鮮產(chǎn)品冷鏈物流背景下的選址-路徑問題;吳迪等[16]、王諾等[17]討論了海運物流體系在構(gòu)建與優(yōu)化中所面臨的選址-路徑問題.此外,LRP在逆向物流[18]和應急物流[19]領(lǐng)域的研究也在逐步深入.
在現(xiàn)有海島應急物流研究中,林婉妮等[20]給出了如何優(yōu)化??諈f(xié)同的群島救援調(diào)度方案.陳立家等[21]運用遺傳算法,以舟山港港區(qū)船舶溢油事故風險應急聯(lián)防設(shè)備選址為例,求解了加權(quán)距離最小化的優(yōu)化選址模型.汪愛嬌等[22]以寧波-舟山海域應急基地選址為例,運用貪婪算法對海上危險化學品應急基地的選址進行了優(yōu)化.佟士祺等[23]針對群島海運物流網(wǎng)絡(luò)的規(guī)劃布局問題,采用主成分分析法對群島內(nèi)島嶼進行計算分析.
從上述文獻的研究成果可以看出,無人機設(shè)備在物流配送中的應用已經(jīng)有了一定的研究深度.然而,目前尚未有文獻將無人機設(shè)備引入海島應急物流救援中.與傳統(tǒng)的LRP不同,本文以海島應急配送為研究背景,考慮應急物資流向的單向性,采用無人機在碼頭與區(qū)域配送中繼站往返運輸?shù)男问剑诤u應急配送的第一級網(wǎng)絡(luò)中引入無人機,因其具有運輸成本低、機動性強等優(yōu)勢,縮短了第二級卡車的配送距離,更好地控制了系統(tǒng)總成本.具體做法是對海島需求點進行聚類分析,求解不同聚類方案下系統(tǒng)運輸總成本,最終給出使得系統(tǒng)總成本最低的無人機配送中繼站數(shù)量及選址方案,并規(guī)劃各配送區(qū)域的終端卡車配送最優(yōu)路徑.
當前,海島應急物流通常采用輪渡將物資運送到對岸海島(圖1(a)),再由配送卡車對需求點進行服務.然而,由于多數(shù)需求點位于海島中部,道路交通遭到災害破壞而被阻斷,配送卡車很難按時完成繁重的配送任務.為進一步提高海島應急物流配送的科學性,保證物資供應端與接收端的配送暢通性,做到安全性好、配送量足、針對性強、覆蓋面廣,本文將無人機配送引入海島應急物流選址-路徑問題中,如圖1(b)所示.將一批物資從供應端碼頭(D)運往海島的無人機配送中繼站(T),再由中繼站(T)派出卡車將物資分發(fā)到每個需求點(Q),由此形成一個包括3類節(jié)點和2個層級相鄰節(jié)點之間的配送路徑的兩級物流網(wǎng)絡(luò).其中,D、T和Q的坐標已知,T的最大建造數(shù)量給定,且容量不限,能夠承擔區(qū)域內(nèi)所有需求點的物資需求.無人機在滿足續(xù)航里程的基礎(chǔ)上,可以多次往返D和T節(jié)點,每個T派出1臺配送卡車對該區(qū)域所有需求點進行1次服務,完成配送任務后返回中繼站.考慮無人機配送中繼站的選址以及D-T、T-Q的配送路徑,使得各配送區(qū)域的卡車完成所有配送任務所行駛的總里程最短.
(a)傳統(tǒng)海島送貨模式
在構(gòu)建無人機-卡車海島配送模型時,需要分兩個階段完成.第一步先給出不同的無人機配送中繼站的選址和需求點分配方案,接著求解各方案下各配送區(qū)域終端卡車的最優(yōu)行駛路徑,并計算無人機和卡車完成所有配送任務的總成本,最終優(yōu)化目標是選取使得系統(tǒng)成本最小的方案.模型相關(guān)符號定義如下:
(1)集合
F,無人機起點D集合,通過f索引;
T,備選中繼站T集合,通過p、q索引;
C,終端需求點Q集合,通過m、n索引;
K,終端卡車集合,通過k索引.
(2)參數(shù)
dmn,網(wǎng)絡(luò)中節(jié)點m與節(jié)點n的距離;
tmax,無人機配送中繼站最大建造數(shù)量;
e,無人機最長續(xù)航里程;
cd,無人機單位距離運輸成本;
ct,卡車單位距離運輸成本.
(3)決策變量
wp∈{0,1},其中wp=1表示節(jié)點p被選為中繼站;否則,wp=0.
xmnk∈{0,1},其中xmnk=1表示卡車k從節(jié)點m到節(jié)點n;否則,xmnk=0.
ynk∈{0,1},其中ynk=1表示節(jié)點n由卡車k配送;否則,ynk=0.
zpm∈{0,1},其中zpm=1表示節(jié)點m由節(jié)點p提供服務;否則,zpm=0.
(1)D、T和Q的地理位置已知,各節(jié)點之間的距離已知,且保持不變.
(2)無人機和卡車均按照兩點間的直線距離行駛.
(3)無人機每次只為一個中繼站服務.
(4)無人機只能在D和T處起降.
(5)不考慮越級配送,即無人機只能將物資送到T;卡車只能由T出發(fā),將物資送到區(qū)域內(nèi)多個Q.
(6)不考慮無人機和卡車的容量限制.
(1)上層模型U:無人機配送中繼站選址模型
在可選范圍內(nèi)確定中繼站的數(shù)量和選址,完成應急物資由一級網(wǎng)絡(luò)節(jié)點向二級網(wǎng)絡(luò)節(jié)點轉(zhuǎn)運.合理的中繼站選址不僅能實現(xiàn)對附近需求點的全覆蓋,還可以使得無人機配送資源的效率最大化,成為使得系統(tǒng)總成本最小化的選址基礎(chǔ).本層模型以配送系統(tǒng)總成本(包括從物資供應端碼頭到無人機配送中繼站的無人機運輸成本和終端卡車配送成本)最小為目標.其目標函數(shù)如式(1)所示,A(xmnk)表示終端卡車完成配送任務后的總成本,c表示配送系統(tǒng)總成本.
(1)
約束(2)為每個需求點只由一個無人機配送中繼站提供服務;式(3)為每一個中繼站與無人機出發(fā)點的直線距離需在無人機續(xù)航里程之內(nèi);式(4)為無人機配送中繼站選址的數(shù)量約束.
(2)
dfp≤e;?f∈F,p∈T
(3)
(4)
變量取值約束為
wp,zpm∈{0,1}
(2)下層模型L:終端卡車路徑優(yōu)化模型
在上層模型U所描述的無人機配送中繼站選址及需求點劃分的基礎(chǔ)上,為了最大化配送效率,無人機將物資卸載到各區(qū)域的T后按原路返航,繼而由各區(qū)域派出1輛配送卡車裝載物資對需求點進行服務.下層模型L需要對各區(qū)域終端卡車的配送路徑進行決策,使得所有卡車在完成配送任務后配送總成本最?。繕撕瘮?shù)如式(5)所示.
(5)
約束(6)保證每個需求點只被服務一次;式(7)規(guī)定了卡車不能在兩個無人機配送中繼站之間行駛;式(8)表示當卡車k經(jīng)過需求點n時,卡車k將對需求點n進行一次配送服務;式(9)、(11)規(guī)定了每一個需求點只能由一輛卡車進行一次服務;式(10)為平衡約束,保證卡車在需求點進出各一次;式(12)表示需求點m由無人機配送中繼站p服務.
(6)
(7)
(8)
(9)
(10)
(11)
(12)
變量取值約束為
xmnk,zpm,ynk∈{0,1}
利用上述雙層模型上下層協(xié)同優(yōu)化的特點對普陀山無人機配送中繼站選址及終端卡車路徑優(yōu)化問題進行構(gòu)建.顯然,上層模型U和下層模型L均為NP難問題,隨著問題規(guī)模的擴大,很難在短時間內(nèi)求出滿意解.因此,本文開發(fā)了一種兩階段算法用于求解上述模型.
海島無人機配送中繼站選址-路徑優(yōu)化問題結(jié)合了選址問題和旅行商問題兩個NP難問題,不宜采用精確算法求解.針對雙層規(guī)劃的主要算法有禁忌搜索算法、遺傳算法、靈敏度分析等.然而,僅選用單一的啟發(fā)式智能算法難以同時求解包含兩個子問題的選址-路徑優(yōu)化問題.據(jù)此,本文對K-means算法和模擬退火算法重新進行設(shè)計,分階段求解,再根據(jù)求解結(jié)果對問題的整體加以優(yōu)化.具體思路是:在上層模型U通過引入K-means算法,隨機選取一個滿足中繼站取值范圍的數(shù)值作為聚類中心個數(shù),將一個區(qū)域內(nèi)距離相對較小的需求點劃分為一類,由此確定區(qū)域內(nèi)的集合覆蓋模型,得到無人機配送中繼站的選址以及服務需求點區(qū)域的劃分方案;在此基礎(chǔ)上,采用改進的模擬退火算法求解下層模型L,對每個區(qū)域的卡車配送路徑進行優(yōu)化,求得各區(qū)域卡車完成配送任務后的配送成本,并計算包含無人機和卡車總運輸成本在內(nèi)的系統(tǒng)總成本.重復上述步驟,完成對中繼站數(shù)量、中繼站選址、需求點分配方案以及卡車配送路徑的優(yōu)化,最終得到使系統(tǒng)總成本最優(yōu)的選址和配送方案.算法流程如圖2所示.
圖2 兩階段算法流程圖Fig.2 Flow chart of the two-stage algorithm
由于本文所要分析的數(shù)據(jù)集規(guī)模較大,選取的需求點地理位置均為其經(jīng)緯度信息,需求點分布不均且跨度較廣,因此選用K-means算法將需求點進行歸類,把一定范圍內(nèi)距離較小的需求點劃分為同一配送區(qū)域.將海島需求點聚類用于確定無人機配送中繼站的位置和數(shù)量,以服務于分銷區(qū)域的需求點.K-means算法作為一種典型的聚類算法,在最大化聚類內(nèi)相似性的同時最小化了聚類間的相似性.在需求點聚類中應用K-means算法時,需求點被分成k0個聚類,目標函數(shù)是使得需求點與聚類中心的距離之和最小.K-means算法能夠在較短時間內(nèi)處理規(guī)模較大的數(shù)據(jù)集合.在應用該算法的過程中,首先需要確定k0值,隨機選取k0個初始聚類中心,然后根據(jù)迭代法原理進行求解,得到無人機配送中繼站的選址以及服務需求點區(qū)域的劃分情況.
在算法1中,步驟3的Nj表示第j個聚類中心所包含的樣本個數(shù).
算法1K-means算法
輸入 初始聚類中心個數(shù)k0、節(jié)點總數(shù)t
輸出 聚類結(jié)果,即無人機配送中繼站選址及服務需求點區(qū)域劃分
步驟1任選k0個初始聚類中心;
步驟2將t-k0個需求點分配給距離最近的th,得到聚類集Sh,h=1,2,…,k0;
步驟4若t′j≠th(h=1,2,…,k0),轉(zhuǎn)步驟2;否則,聚類結(jié)束.
下層模型L研究從無人機配送中繼站到終端需求點的卡車配送路徑優(yōu)化問題,模擬退火算法是一種流行的迭代元啟發(fā)式算法,廣泛用于解決離散和連續(xù)優(yōu)化問題.不同于梯度下降法,模擬退火算法能夠依賴其原理以一定的概率有效地跳出局部最優(yōu)值,增加了尋找全局最優(yōu)解的可能性.因此,本文選用模擬退火算法求解終端卡車配送路徑優(yōu)化問題.
(1)編碼與初始解的產(chǎn)生
由于海島無人機配送中繼站選址-優(yōu)化包含多個子問題,考慮到本文所提出的兩階段算法采取的是自上而下的求解步驟,因此,對于第一階段的選址和第二階段的路徑優(yōu)化,本文以統(tǒng)一的形式對配送網(wǎng)絡(luò)進行編碼.在上層確定好無人機配送中繼站集合{1,2,…,k0}以及區(qū)域分配方案后,在求解下層卡車配送路徑優(yōu)化時,將t-k0個需求點進行編號,一組解空間中,首位代表中繼站的編號,從第二位編號往后代表卡車依次經(jīng)過的需求點.
(2)產(chǎn)生新解
對于傳統(tǒng)的模擬退火算法,在產(chǎn)生新路徑時運用的是路徑交換法,主要做法是從所有需求點中隨機抽取兩個節(jié)點,將這兩個節(jié)點在原有路徑中的位置進行交換,其他節(jié)點位置保持不變,從而產(chǎn)生一條新路徑.本文在使用路徑交換法的基礎(chǔ)上,增加了采用路徑倒置產(chǎn)生新解的方式.以圖3(a)中繼站1的解空間為例,若隨機抽取6和10兩個城市,那么這兩個城市之間的路徑需要倒置排列以獲得新解,如圖3(b)所示.
(a)原始解
改進的模擬退火算法求解步驟如算法2所示.
算法2改進的模擬退火算法
輸入 網(wǎng)絡(luò)中所有節(jié)點的距離矩陣D、無人機中繼站選址及分配結(jié)果S
輸出 各無人機中繼站卡車配送最優(yōu)路徑Xbest及距離E(Xnew)
步驟1將無人機配送中繼站和需求點進行編號,隨機產(chǎn)生一個初始解X0,令Xbest=X0,計算目標函數(shù)E(X0).
步驟2設(shè)置初始溫度T(0)=T0,迭代次數(shù)i=1,衰減函數(shù)T(i+1)=αT(i),鏈長Lmax.
WhileT(i)>Tend
forL=1 toLmax
產(chǎn)生新解Xnew,得到目標函數(shù)的增量ΔE=E(Xnew)-E(Xbest)
若ΔE<0,Xbest=Xnew
否則
若c=random[0,1]
Xbest=Xnew
否則,Xbest不變
end
i=i+1
end
步驟3輸出當前最優(yōu)值,計算結(jié)束.
本文以浙江省舟山市普陀山海島物流配送為例,驗證兩階段算法的可行性.通過對政府官網(wǎng)和國內(nèi)各大旅游網(wǎng)站的調(diào)研,選取了304個需求點,包含普陀山海島內(nèi)的景點、民宿、小區(qū)等物資需求量較大的節(jié)點.無人機從朱家尖客運中心出發(fā),將應急物資送往無人機配送中繼站,再由各中繼站派出卡車對需求點進行服務.
將需求點名稱存入Excel文件后,通過調(diào)用百度地圖應用程序編程接口,批量獲取304個需求點的經(jīng)緯度信息.部分需求點地理坐標如表1所示.在獲取需求點經(jīng)緯度坐標的基礎(chǔ)上,計算任意兩個需求點的地表距離,生成需求點的距離矩陣.
表1 部分需求點地理坐標Tab.1 Geographical coordinates of some demand points
本文以普陀山海島304個需求點和1個無人機出發(fā)點(朱家尖客運中心)的地理坐標為輸入數(shù)據(jù),假設(shè)無人機的單位運輸成本為10元/km,卡車的單位運輸成本為30元/km.
將需求點的地理坐標作為K-means算法的輸入數(shù)據(jù),對304個分布在普陀山海島的需求點進行聚類分析.為選取符合實際配送能力且成本相對較低的選址分配方案,在給定最大無人機配送中繼站數(shù)量的情況下,上層算法通過設(shè)置不同的聚類中心數(shù)量,并提供各種數(shù)量下的最優(yōu)需求點區(qū)域劃分方案,由下層算法計算出該方案的系統(tǒng)總成本,在最大迭代次數(shù)之內(nèi)選取使得系統(tǒng)總成本最低的配送方案.無人機配送中繼站數(shù)量的優(yōu)化過程如圖4所示,可以看出,當聚類中心數(shù)量為38時,即開設(shè)38個無人機配送中繼站時,系統(tǒng)總成本可以達到既定范圍內(nèi)的最低值.
圖4 聚類中心數(shù)量優(yōu)化過程Fig.4 Optimization processes of the number of cluster centers
海島需求點的聚類結(jié)果如圖5所示,部分中繼站的名稱及地理位置信息如表2所示.圖5包含由38種不同顏色所構(gòu)成的需求點集合,同一顏色的需求點被劃分至一個配送區(qū)域,由該區(qū)域的無人機配送中繼站負責配送物資.
圖5 38個聚類中心的聚類結(jié)果Fig.5 Clustering results of 38 cluster centers
表2 部分無人機配送中繼站信息Tab.2 Some drone delivery relay station informations
38個中繼站在普陀山海島地圖中的坐標點如圖6所示.中繼站呈南面密集、北面零散的分布態(tài)勢.這是由于普陀山地勢南面平緩,北面高峻,人口大多聚集在南面平地一帶,因此需求點也集中于南面.所有無人機配送中繼站的選址均在無人機續(xù)航里程范圍之內(nèi),無人機從朱家尖客運中心將物資運往中繼站,規(guī)定無人機每次僅向一個中繼站運送物資,完成任務后返回朱家尖客運中心,裝載下一配送區(qū)域的物資運往對應的無人機配送中繼站,依此類推,每個中繼站均與無人機進行一次對接,完成無人機和卡車的海島兩級配送任務.
圖6 38個無人機配送中繼站分布圖Fig.6 Distribution diagram of 38 drone delivery relay stations
在此基礎(chǔ)上,劃分以無人機配送中繼站為聚類中心的38個配送區(qū)域,每個區(qū)域擁有1輛配送卡車,為包含38個中繼站在內(nèi)的共304個需求點提供服務.無人機將貨物運往各中繼站后,卡車裝載貨物從中繼站出發(fā),沿著最優(yōu)路徑依次為所在區(qū)域需求點進行物資配送,完成任務后返回中繼站.
以所有卡車完成配送任務的卡車配送成本最低為目標函數(shù),利用改進的模擬退火算法求解,算法的參數(shù)設(shè)置為α=0.99,T0=1 000,Tend=0.01,Lmax=300.
經(jīng)計算,所有卡車完成配送任務所行駛的總里程為28.43 km,配送成本為853.0元.各區(qū)域終端最優(yōu)配送路徑、卡車配送里程以及卡車配送成本如表3所示.
表3 部分區(qū)域配送路徑及卡車里程表Tab.3 Delivery routes and truck odometers in some regions
根據(jù)表3的配送情況,結(jié)合無人機從朱家尖客運中心飛往無人機配送中繼站的路線,得到完整的無人機-卡車海島兩級物流配送網(wǎng)絡(luò),如圖7所示.圖6中相同顏色的中繼站在圖7中屬于同一張兩級配送網(wǎng)絡(luò)圖.
圖7 普陀山海島應急物流兩級網(wǎng)絡(luò)圖Fig.7 Two-level network chart of emergency logistics in Putuoshan Island
為驗證本文所采取的無人機配送中繼站選址與卡車路徑一體優(yōu)化的效果,對同一算例設(shè)計選址與路徑兩段優(yōu)化的策略,先確定無人機配送中繼站的數(shù)量、選址,在此基礎(chǔ)上進行卡車路徑優(yōu)化,求得系統(tǒng)總成本.兩種優(yōu)化方法求解結(jié)果對比如表4所示(以304個需求點為例),將無人機配送中繼站的數(shù)量、選址以及卡車路徑同時進行優(yōu)化的效果優(yōu)于兩段優(yōu)化.通過設(shè)置不同的最大中繼站建造數(shù)量,可以看出,隨著最大中繼站建造數(shù)量的增加,一體優(yōu)化方法的總成本改進效果更明顯.
表4 兩種優(yōu)化結(jié)果對比Tab.4 Comparison of two optimization results
海島無人機配送中繼站的選址-路徑優(yōu)化問題是影響海島應急配送效率的關(guān)鍵性問題,對物資配送成本和物資轉(zhuǎn)運靈活度有直接影響.本文針對海島應急物流中引入無人機配送的特征,以系統(tǒng)配送總成本最小為目標,建立了海島無人機配送中繼站的選址-路徑優(yōu)化的雙層規(guī)劃模型.為了求解模型,設(shè)計了K-means聚類算法與改進的模擬退火算法相結(jié)合的兩階段算法.以浙江省舟山市普陀山海島為背景,研究從朱家尖客運中心將一批物資運往普陀山海島304個需求點的兩級配送路徑,在這些需求點中選取38個無人機配送中繼站并為各個中繼站所負責的配送區(qū)域規(guī)劃卡車最優(yōu)路線,使得系統(tǒng)總成本達到最低,為1 013.1元.與兩段優(yōu)化方法相比,本文所采用的一體優(yōu)化方法使得系統(tǒng)總成本降低10.3%.
本文以無人機和卡車配送系統(tǒng)總成本最小為建模目標,但沒有考慮無人機和卡車的容量限制,因此,考慮包含客戶需求量和運載工具容量限制是未來研究的主要方向之一.此外,利用5G網(wǎng)絡(luò)超強的信息傳送能力,移動網(wǎng)絡(luò)海量的站點資源可以為無人機提供從點到線再到面的立體覆蓋,從而實現(xiàn)無人機超視距控制,隨時掌控無人機的位置和空閑狀況、安全狀況等,將是無人機應急物流領(lǐng)域一個跨時代的新應用場景.