海島無(wú)人機(jī)配送中繼站選址-路徑優(yōu)化

陸 玲 玲， 胡 志 華

(上海海事大學(xué) 物流研究中心，上海 201306 )

0 引 言

海島應(yīng)急物流作為海島應(yīng)急管理的關(guān)鍵一環(huán)，在面臨道路中斷、天氣惡劣等挑戰(zhàn)時(shí)，如何快速、安全地將應(yīng)急生活物資精準(zhǔn)運(yùn)往需求點(diǎn)，在提高救災(zāi)效率與安全性的同時(shí)，更好地控制系統(tǒng)總成本，是海島應(yīng)急物流的核心命題．

作為物流行業(yè)邁向自動(dòng)化、智能化發(fā)展的典型代表之一，無(wú)人機(jī)將成為解決海島應(yīng)急物流配送安全和效率問(wèn)題的一大利器．當(dāng)海島出現(xiàn)突發(fā)地質(zhì)災(zāi)害等情況時(shí)，傳統(tǒng)的輪渡運(yùn)送方式一方面缺乏物資轉(zhuǎn)運(yùn)的靈活性，另一方面，配送人員的人身安全也無(wú)法得到保障．此時(shí)，若利用無(wú)人機(jī)生存能力強(qiáng)、機(jī)動(dòng)性能好等優(yōu)勢(shì)，在短時(shí)間內(nèi)將應(yīng)急物資從碼頭運(yùn)往海島上的無(wú)人機(jī)配送中繼站，再由卡車將物資送往需求點(diǎn)，既能提高抗災(zāi)救災(zāi)效率，又能降低因?yàn)槿藛T疲勞或單調(diào)場(chǎng)景作業(yè)造成的安全隱患．

“十四五”期間，將進(jìn)一步擴(kuò)大無(wú)人機(jī)物流配送試點(diǎn)范圍，服務(wù)鄉(xiāng)村振興戰(zhàn)略．此前，國(guó)內(nèi)外學(xué)者對(duì)于無(wú)人機(jī)在物流領(lǐng)域的應(yīng)用已有了較為深入的研究．無(wú)人機(jī)在飛行過(guò)程中產(chǎn)生能耗和電池維護(hù)成本，但是投遞小型包裹依然具有經(jīng)濟(jì)可行性[1]．垂停是無(wú)人機(jī)設(shè)計(jì)的關(guān)鍵技術(shù)問(wèn)題，用于包裹配送的無(wú)人機(jī)同樣需要解決和利用懸?？刂颇芰2]．翁丹寧[3]剖析了無(wú)人機(jī)進(jìn)入商業(yè)領(lǐng)域物流配送的主要影響因素．楊代勇[4]提出構(gòu)建一個(gè)完整的新型物流配送法律體系應(yīng)從統(tǒng)一行業(yè)標(biāo)準(zhǔn)體系、強(qiáng)化監(jiān)督管理機(jī)制、完善相關(guān)法律法規(guī)3個(gè)方面入手．目前已有文獻(xiàn)研究了無(wú)人機(jī)與卡車合作進(jìn)行交付的配送模式[5]，這種合作模式在最后1 km 的物流配送過(guò)程中得到了進(jìn)一步應(yīng)用[6]．

利用無(wú)人機(jī)將碼頭物資運(yùn)往海島災(zāi)區(qū)的重要前提是確定災(zāi)區(qū)對(duì)接點(diǎn)，在海島中選取一定數(shù)量的無(wú)人機(jī)配送中繼站負(fù)責(zé)將物資送往需求點(diǎn)，再由終端卡車從中繼站出發(fā)，對(duì)該區(qū)域所有需求點(diǎn)進(jìn)行遍歷，最終回到無(wú)人機(jī)配送中繼站，從而形成一個(gè)兩級(jí)海島應(yīng)急物流網(wǎng)絡(luò)．von Boventer[7]最早提出這種將網(wǎng)絡(luò)中設(shè)施選址和路徑優(yōu)化問(wèn)題綜合考慮的選址-路徑問(wèn)題(location-routing problem，LRP)，對(duì)問(wèn)題中設(shè)施點(diǎn)的選址和運(yùn)送成本的關(guān)系進(jìn)行了研究．按照節(jié)點(diǎn)類型，LRP可分為單層選址-路徑問(wèn)題、雙層選址-路徑問(wèn)題和多層選址-路徑問(wèn)題．雙層選址-路徑問(wèn)題[8]通過(guò)決策物流網(wǎng)絡(luò)中備選點(diǎn)的位置和數(shù)量來(lái)規(guī)劃兩個(gè)層級(jí)之間的卡車配送路徑．以物流系統(tǒng)總成本最小為目標(biāo)函數(shù)，建立兩階段隨機(jī)規(guī)劃模型[9]；加入生產(chǎn)計(jì)劃與時(shí)間窗約束，利用啟發(fā)式算法求解[10]．此外，建立LRP混合整數(shù)規(guī)劃模型，應(yīng)用于生物質(zhì)資源的供應(yīng)領(lǐng)域[11]．

國(guó)內(nèi)對(duì)于LRP的研究開始相對(duì)較晚，汪壽陽(yáng)等[12]對(duì)LRP的主要研究進(jìn)展作出綜述，分析了求解該問(wèn)題相關(guān)算法的主要特點(diǎn)．此后，李冰等[13]、馬艷芳等[14]、劉建仁[15]研究了生鮮產(chǎn)品冷鏈物流背景下的選址-路徑問(wèn)題；吳迪等[16]、王諾等[17]討論了海運(yùn)物流體系在構(gòu)建與優(yōu)化中所面臨的選址-路徑問(wèn)題．此外，LRP在逆向物流[18]和應(yīng)急物流[19]領(lǐng)域的研究也在逐步深入．

在現(xiàn)有海島應(yīng)急物流研究中，林婉妮等[20]給出了如何優(yōu)化?？諈f(xié)同的群島救援調(diào)度方案．陳立家等[21]運(yùn)用遺傳算法，以舟山港港區(qū)船舶溢油事故風(fēng)險(xiǎn)應(yīng)急聯(lián)防設(shè)備選址為例，求解了加權(quán)距離最小化的優(yōu)化選址模型．汪愛(ài)嬌等[22]以寧波-舟山海域應(yīng)急基地選址為例，運(yùn)用貪婪算法對(duì)海上危險(xiǎn)化學(xué)品應(yīng)急基地的選址進(jìn)行了優(yōu)化．佟士祺等[23]針對(duì)群島海運(yùn)物流網(wǎng)絡(luò)的規(guī)劃布局問(wèn)題，采用主成分分析法對(duì)群島內(nèi)島嶼進(jìn)行計(jì)算分析．

從上述文獻(xiàn)的研究成果可以看出，無(wú)人機(jī)設(shè)備在物流配送中的應(yīng)用已經(jīng)有了一定的研究深度．然而，目前尚未有文獻(xiàn)將無(wú)人機(jī)設(shè)備引入海島應(yīng)急物流救援中．與傳統(tǒng)的LRP不同，本文以海島應(yīng)急配送為研究背景，考慮應(yīng)急物資流向的單向性，采用無(wú)人機(jī)在碼頭與區(qū)域配送中繼站往返運(yùn)輸?shù)男问剑诤u應(yīng)急配送的第一級(jí)網(wǎng)絡(luò)中引入無(wú)人機(jī)，因其具有運(yùn)輸成本低、機(jī)動(dòng)性強(qiáng)等優(yōu)勢(shì)，縮短了第二級(jí)卡車的配送距離，更好地控制了系統(tǒng)總成本．具體做法是對(duì)海島需求點(diǎn)進(jìn)行聚類分析，求解不同聚類方案下系統(tǒng)運(yùn)輸總成本，最終給出使得系統(tǒng)總成本最低的無(wú)人機(jī)配送中繼站數(shù)量及選址方案，并規(guī)劃各配送區(qū)域的終端卡車配送最優(yōu)路徑．

1 問(wèn)題描述

當(dāng)前，海島應(yīng)急物流通常采用輪渡將物資運(yùn)送到對(duì)岸海島(圖1(a))，再由配送卡車對(duì)需求點(diǎn)進(jìn)行服務(wù)．然而，由于多數(shù)需求點(diǎn)位于海島中部，道路交通遭到災(zāi)害破壞而被阻斷，配送卡車很難按時(shí)完成繁重的配送任務(wù)．為進(jìn)一步提高海島應(yīng)急物流配送的科學(xué)性，保證物資供應(yīng)端與接收端的配送暢通性，做到安全性好、配送量足、針對(duì)性強(qiáng)、覆蓋面廣，本文將無(wú)人機(jī)配送引入海島應(yīng)急物流選址-路徑問(wèn)題中，如圖1(b)所示．將一批物資從供應(yīng)端碼頭(D)運(yùn)往海島的無(wú)人機(jī)配送中繼站(T)，再由中繼站(T)派出卡車將物資分發(fā)到每個(gè)需求點(diǎn)(Q)，由此形成一個(gè)包括3類節(jié)點(diǎn)和2個(gè)層級(jí)相鄰節(jié)點(diǎn)之間的配送路徑的兩級(jí)物流網(wǎng)絡(luò)．其中，D、T和Q的坐標(biāo)已知，T的最大建造數(shù)量給定，且容量不限，能夠承擔(dān)區(qū)域內(nèi)所有需求點(diǎn)的物資需求．無(wú)人機(jī)在滿足續(xù)航里程的基礎(chǔ)上，可以多次往返D和T節(jié)點(diǎn)，每個(gè)T派出1臺(tái)配送卡車對(duì)該區(qū)域所有需求點(diǎn)進(jìn)行1次服務(wù)，完成配送任務(wù)后返回中繼站．考慮無(wú)人機(jī)配送中繼站的選址以及D-T、T-Q的配送路徑，使得各配送區(qū)域的卡車完成所有配送任務(wù)所行駛的總里程最短．

(a)傳統(tǒng)海島送貨模式

2 數(shù)學(xué)模型

在構(gòu)建無(wú)人機(jī)-卡車海島配送模型時(shí)，需要分兩個(gè)階段完成．第一步先給出不同的無(wú)人機(jī)配送中繼站的選址和需求點(diǎn)分配方案，接著求解各方案下各配送區(qū)域終端卡車的最優(yōu)行駛路徑，并計(jì)算無(wú)人機(jī)和卡車完成所有配送任務(wù)的總成本，最終優(yōu)化目標(biāo)是選取使得系統(tǒng)成本最小的方案．模型相關(guān)符號(hào)定義如下：

(1)集合

F，無(wú)人機(jī)起點(diǎn)D集合，通過(guò)f索引；

T，備選中繼站T集合，通過(guò)p、q索引；

C，終端需求點(diǎn)Q集合，通過(guò)m、n索引；

K，終端卡車集合，通過(guò)k索引．

(2)參數(shù)

dmn，網(wǎng)絡(luò)中節(jié)點(diǎn)m與節(jié)點(diǎn)n的距離；

tmax，無(wú)人機(jī)配送中繼站最大建造數(shù)量；

e，無(wú)人機(jī)最長(zhǎng)續(xù)航里程；

cd，無(wú)人機(jī)單位距離運(yùn)輸成本；

ct，卡車單位距離運(yùn)輸成本．

(3)決策變量

wp∈{0，1}，其中wp=1表示節(jié)點(diǎn)p被選為中繼站；否則，wp=0．

xmnk∈{0，1}，其中xmnk=1表示卡車k從節(jié)點(diǎn)m到節(jié)點(diǎn)n；否則，xmnk=0．

ynk∈{0，1}，其中ynk=1表示節(jié)點(diǎn)n由卡車k配送；否則，ynk=0．

zpm∈{0，1}，其中zpm=1表示節(jié)點(diǎn)m由節(jié)點(diǎn)p提供服務(wù)；否則，zpm=0．

2.1 模型假設(shè)

(1)D、T和Q的地理位置已知，各節(jié)點(diǎn)之間的距離已知，且保持不變．

(2)無(wú)人機(jī)和卡車均按照兩點(diǎn)間的直線距離行駛．

(3)無(wú)人機(jī)每次只為一個(gè)中繼站服務(wù)．

(4)無(wú)人機(jī)只能在D和T處起降．

(5)不考慮越級(jí)配送，即無(wú)人機(jī)只能將物資送到T；卡車只能由T出發(fā)，將物資送到區(qū)域內(nèi)多個(gè)Q．

(6)不考慮無(wú)人機(jī)和卡車的容量限制．

2.2 雙層規(guī)劃模型

(1)上層模型U：無(wú)人機(jī)配送中繼站選址模型

在可選范圍內(nèi)確定中繼站的數(shù)量和選址，完成應(yīng)急物資由一級(jí)網(wǎng)絡(luò)節(jié)點(diǎn)向二級(jí)網(wǎng)絡(luò)節(jié)點(diǎn)轉(zhuǎn)運(yùn)．合理的中繼站選址不僅能實(shí)現(xiàn)對(duì)附近需求點(diǎn)的全覆蓋，還可以使得無(wú)人機(jī)配送資源的效率最大化，成為使得系統(tǒng)總成本最小化的選址基礎(chǔ)．本層模型以配送系統(tǒng)總成本(包括從物資供應(yīng)端碼頭到無(wú)人機(jī)配送中繼站的無(wú)人機(jī)運(yùn)輸成本和終端卡車配送成本)最小為目標(biāo)．其目標(biāo)函數(shù)如式(1)所示，A(xmnk)表示終端卡車完成配送任務(wù)后的總成本，c表示配送系統(tǒng)總成本．

(1)

約束(2)為每個(gè)需求點(diǎn)只由一個(gè)無(wú)人機(jī)配送中繼站提供服務(wù)；式(3)為每一個(gè)中繼站與無(wú)人機(jī)出發(fā)點(diǎn)的直線距離需在無(wú)人機(jī)續(xù)航里程之內(nèi)；式(4)為無(wú)人機(jī)配送中繼站選址的數(shù)量約束．

(2)

dfp≤e；?f∈F，p∈T

(3)

(4)

變量取值約束為

wp，zpm∈{0，1}

(2)下層模型L：終端卡車路徑優(yōu)化模型

在上層模型U所描述的無(wú)人機(jī)配送中繼站選址及需求點(diǎn)劃分的基礎(chǔ)上，為了最大化配送效率，無(wú)人機(jī)將物資卸載到各區(qū)域的T后按原路返航，繼而由各區(qū)域派出1輛配送卡車裝載物資對(duì)需求點(diǎn)進(jìn)行服務(wù)．下層模型L需要對(duì)各區(qū)域終端卡車的配送路徑進(jìn)行決策，使得所有卡車在完成配送任務(wù)后配送總成本最小．目標(biāo)函數(shù)如式(5)所示．

(5)

約束(6)保證每個(gè)需求點(diǎn)只被服務(wù)一次；式(7)規(guī)定了卡車不能在兩個(gè)無(wú)人機(jī)配送中繼站之間行駛；式(8)表示當(dāng)卡車k經(jīng)過(guò)需求點(diǎn)n時(shí)，卡車k將對(duì)需求點(diǎn)n進(jìn)行一次配送服務(wù)；式(9)、(11)規(guī)定了每一個(gè)需求點(diǎn)只能由一輛卡車進(jìn)行一次服務(wù)；式(10)為平衡約束，保證卡車在需求點(diǎn)進(jìn)出各一次；式(12)表示需求點(diǎn)m由無(wú)人機(jī)配送中繼站p服務(wù)．

(6)

(7)

(8)

(9)

(10)

(11)

(12)

變量取值約束為

xmnk，zpm，ynk∈{0，1}

利用上述雙層模型上下層協(xié)同優(yōu)化的特點(diǎn)對(duì)普陀山無(wú)人機(jī)配送中繼站選址及終端卡車路徑優(yōu)化問(wèn)題進(jìn)行構(gòu)建．顯然，上層模型U和下層模型L均為NP難問(wèn)題，隨著問(wèn)題規(guī)模的擴(kuò)大，很難在短時(shí)間內(nèi)求出滿意解．因此，本文開發(fā)了一種兩階段算法用于求解上述模型．

3 算法設(shè)計(jì)

海島無(wú)人機(jī)配送中繼站選址-路徑優(yōu)化問(wèn)題結(jié)合了選址問(wèn)題和旅行商問(wèn)題兩個(gè)NP難問(wèn)題，不宜采用精確算法求解．針對(duì)雙層規(guī)劃的主要算法有禁忌搜索算法、遺傳算法、靈敏度分析等．然而，僅選用單一的啟發(fā)式智能算法難以同時(shí)求解包含兩個(gè)子問(wèn)題的選址-路徑優(yōu)化問(wèn)題．據(jù)此，本文對(duì)K-means算法和模擬退火算法重新進(jìn)行設(shè)計(jì)，分階段求解，再根據(jù)求解結(jié)果對(duì)問(wèn)題的整體加以優(yōu)化．具體思路是：在上層模型U通過(guò)引入K-means算法，隨機(jī)選取一個(gè)滿足中繼站取值范圍的數(shù)值作為聚類中心個(gè)數(shù)，將一個(gè)區(qū)域內(nèi)距離相對(duì)較小的需求點(diǎn)劃分為一類，由此確定區(qū)域內(nèi)的集合覆蓋模型，得到無(wú)人機(jī)配送中繼站的選址以及服務(wù)需求點(diǎn)區(qū)域的劃分方案；在此基礎(chǔ)上，采用改進(jìn)的模擬退火算法求解下層模型L，對(duì)每個(gè)區(qū)域的卡車配送路徑進(jìn)行優(yōu)化，求得各區(qū)域卡車完成配送任務(wù)后的配送成本，并計(jì)算包含無(wú)人機(jī)和卡車總運(yùn)輸成本在內(nèi)的系統(tǒng)總成本．重復(fù)上述步驟，完成對(duì)中繼站數(shù)量、中繼站選址、需求點(diǎn)分配方案以及卡車配送路徑的優(yōu)化，最終得到使系統(tǒng)總成本最優(yōu)的選址和配送方案．算法流程如圖2所示．

圖2 兩階段算法流程圖Fig.2 Flow chart of the two-stage algorithm

3.1 K-means算法

由于本文所要分析的數(shù)據(jù)集規(guī)模較大，選取的需求點(diǎn)地理位置均為其經(jīng)緯度信息，需求點(diǎn)分布不均且跨度較廣，因此選用K-means算法將需求點(diǎn)進(jìn)行歸類，把一定范圍內(nèi)距離較小的需求點(diǎn)劃分為同一配送區(qū)域．將海島需求點(diǎn)聚類用于確定無(wú)人機(jī)配送中繼站的位置和數(shù)量，以服務(wù)于分銷區(qū)域的需求點(diǎn)．K-means算法作為一種典型的聚類算法，在最大化聚類內(nèi)相似性的同時(shí)最小化了聚類間的相似性．在需求點(diǎn)聚類中應(yīng)用K-means算法時(shí)，需求點(diǎn)被分成k0個(gè)聚類，目標(biāo)函數(shù)是使得需求點(diǎn)與聚類中心的距離之和最小．K-means算法能夠在較短時(shí)間內(nèi)處理規(guī)模較大的數(shù)據(jù)集合．在應(yīng)用該算法的過(guò)程中，首先需要確定k0值，隨機(jī)選取k0個(gè)初始聚類中心，然后根據(jù)迭代法原理進(jìn)行求解，得到無(wú)人機(jī)配送中繼站的選址以及服務(wù)需求點(diǎn)區(qū)域的劃分情況．

在算法1中，步驟3的Nj表示第j個(gè)聚類中心所包含的樣本個(gè)數(shù)．

算法1K-means算法

輸入 初始聚類中心個(gè)數(shù)k0、節(jié)點(diǎn)總數(shù)t

輸出 聚類結(jié)果，即無(wú)人機(jī)配送中繼站選址及服務(wù)需求點(diǎn)區(qū)域劃分

步驟1任選k0個(gè)初始聚類中心；

步驟2將t-k0個(gè)需求點(diǎn)分配給距離最近的th，得到聚類集Sh，h=1，2，…，k0；

步驟4若t′j≠th(h=1，2，…，k0)，轉(zhuǎn)步驟2；否則，聚類結(jié)束．

3.2 改進(jìn)的模擬退火算法

下層模型L研究從無(wú)人機(jī)配送中繼站到終端需求點(diǎn)的卡車配送路徑優(yōu)化問(wèn)題，模擬退火算法是一種流行的迭代元啟發(fā)式算法，廣泛用于解決離散和連續(xù)優(yōu)化問(wèn)題．不同于梯度下降法，模擬退火算法能夠依賴其原理以一定的概率有效地跳出局部最優(yōu)值，增加了尋找全局最優(yōu)解的可能性．因此，本文選用模擬退火算法求解終端卡車配送路徑優(yōu)化問(wèn)題．

(1)編碼與初始解的產(chǎn)生

由于海島無(wú)人機(jī)配送中繼站選址-優(yōu)化包含多個(gè)子問(wèn)題，考慮到本文所提出的兩階段算法采取的是自上而下的求解步驟，因此，對(duì)于第一階段的選址和第二階段的路徑優(yōu)化，本文以統(tǒng)一的形式對(duì)配送網(wǎng)絡(luò)進(jìn)行編碼．在上層確定好無(wú)人機(jī)配送中繼站集合{1，2，…，k0}以及區(qū)域分配方案后，在求解下層卡車配送路徑優(yōu)化時(shí)，將t-k0個(gè)需求點(diǎn)進(jìn)行編號(hào)，一組解空間中，首位代表中繼站的編號(hào)，從第二位編號(hào)往后代表卡車依次經(jīng)過(guò)的需求點(diǎn)．

(2)產(chǎn)生新解

對(duì)于傳統(tǒng)的模擬退火算法，在產(chǎn)生新路徑時(shí)運(yùn)用的是路徑交換法，主要做法是從所有需求點(diǎn)中隨機(jī)抽取兩個(gè)節(jié)點(diǎn)，將這兩個(gè)節(jié)點(diǎn)在原有路徑中的位置進(jìn)行交換，其他節(jié)點(diǎn)位置保持不變，從而產(chǎn)生一條新路徑．本文在使用路徑交換法的基礎(chǔ)上，增加了采用路徑倒置產(chǎn)生新解的方式．以圖3(a)中繼站1的解空間為例，若隨機(jī)抽取6和10兩個(gè)城市，那么這兩個(gè)城市之間的路徑需要倒置排列以獲得新解，如圖3(b)所示．

(a)原始解

改進(jìn)的模擬退火算法求解步驟如算法2所示．

算法2改進(jìn)的模擬退火算法

輸入 網(wǎng)絡(luò)中所有節(jié)點(diǎn)的距離矩陣D、無(wú)人機(jī)中繼站選址及分配結(jié)果S

輸出 各無(wú)人機(jī)中繼站卡車配送最優(yōu)路徑Xbest及距離E(Xnew)

步驟1將無(wú)人機(jī)配送中繼站和需求點(diǎn)進(jìn)行編號(hào)，隨機(jī)產(chǎn)生一個(gè)初始解X0，令Xbest=X0，計(jì)算目標(biāo)函數(shù)E(X0)．

步驟2設(shè)置初始溫度T(0)=T0，迭代次數(shù)i=1，衰減函數(shù)T(i+1)=αT(i)，鏈長(zhǎng)Lmax．

WhileT(i)>Tend

forL=1 toLmax

產(chǎn)生新解Xnew，得到目標(biāo)函數(shù)的增量ΔE=E(Xnew)-E(Xbest)

若ΔE<0，Xbest=Xnew

否則

若c=random[0，1]

Xbest=Xnew

否則，Xbest不變

end

i=i+1

end

步驟3輸出當(dāng)前最優(yōu)值，計(jì)算結(jié)束．

4 普陀山海島配送實(shí)例分析

本文以浙江省舟山市普陀山海島物流配送為例，驗(yàn)證兩階段算法的可行性．通過(guò)對(duì)政府官網(wǎng)和國(guó)內(nèi)各大旅游網(wǎng)站的調(diào)研，選取了304個(gè)需求點(diǎn)，包含普陀山海島內(nèi)的景點(diǎn)、民宿、小區(qū)等物資需求量較大的節(jié)點(diǎn)．無(wú)人機(jī)從朱家尖客運(yùn)中心出發(fā)，將應(yīng)急物資送往無(wú)人機(jī)配送中繼站，再由各中繼站派出卡車對(duì)需求點(diǎn)進(jìn)行服務(wù)．

4.1 數(shù)據(jù)預(yù)處理

將需求點(diǎn)名稱存入Excel文件后，通過(guò)調(diào)用百度地圖應(yīng)用程序編程接口，批量獲取304個(gè)需求點(diǎn)的經(jīng)緯度信息．部分需求點(diǎn)地理坐標(biāo)如表1所示．在獲取需求點(diǎn)經(jīng)緯度坐標(biāo)的基礎(chǔ)上，計(jì)算任意兩個(gè)需求點(diǎn)的地表距離，生成需求點(diǎn)的距離矩陣．

表1 部分需求點(diǎn)地理坐標(biāo)Tab.1 Geographical coordinates of some demand points

本文以普陀山海島304個(gè)需求點(diǎn)和1個(gè)無(wú)人機(jī)出發(fā)點(diǎn)(朱家尖客運(yùn)中心)的地理坐標(biāo)為輸入數(shù)據(jù)，假設(shè)無(wú)人機(jī)的單位運(yùn)輸成本為10元/km，卡車的單位運(yùn)輸成本為30元/km．

4.2 無(wú)人機(jī)配送中繼站選址及區(qū)域劃分

將需求點(diǎn)的地理坐標(biāo)作為K-means算法的輸入數(shù)據(jù)，對(duì)304個(gè)分布在普陀山海島的需求點(diǎn)進(jìn)行聚類分析．為選取符合實(shí)際配送能力且成本相對(duì)較低的選址分配方案，在給定最大無(wú)人機(jī)配送中繼站數(shù)量的情況下，上層算法通過(guò)設(shè)置不同的聚類中心數(shù)量，并提供各種數(shù)量下的最優(yōu)需求點(diǎn)區(qū)域劃分方案，由下層算法計(jì)算出該方案的系統(tǒng)總成本，在最大迭代次數(shù)之內(nèi)選取使得系統(tǒng)總成本最低的配送方案．無(wú)人機(jī)配送中繼站數(shù)量的優(yōu)化過(guò)程如圖4所示，可以看出，當(dāng)聚類中心數(shù)量為38時(shí)，即開設(shè)38個(gè)無(wú)人機(jī)配送中繼站時(shí)，系統(tǒng)總成本可以達(dá)到既定范圍內(nèi)的最低值．

圖4 聚類中心數(shù)量?jī)?yōu)化過(guò)程Fig.4 Optimization processes of the number of cluster centers

海島需求點(diǎn)的聚類結(jié)果如圖5所示，部分中繼站的名稱及地理位置信息如表2所示．圖5包含由38種不同顏色所構(gòu)成的需求點(diǎn)集合，同一顏色的需求點(diǎn)被劃分至一個(gè)配送區(qū)域，由該區(qū)域的無(wú)人機(jī)配送中繼站負(fù)責(zé)配送物資．

圖5 38個(gè)聚類中心的聚類結(jié)果Fig.5 Clustering results of 38 cluster centers

表2 部分無(wú)人機(jī)配送中繼站信息Tab.2 Some drone delivery relay station informations

38個(gè)中繼站在普陀山海島地圖中的坐標(biāo)點(diǎn)如圖6所示．中繼站呈南面密集、北面零散的分布態(tài)勢(shì)．這是由于普陀山地勢(shì)南面平緩，北面高峻，人口大多聚集在南面平地一帶，因此需求點(diǎn)也集中于南面．所有無(wú)人機(jī)配送中繼站的選址均在無(wú)人機(jī)續(xù)航里程范圍之內(nèi)，無(wú)人機(jī)從朱家尖客運(yùn)中心將物資運(yùn)往中繼站，規(guī)定無(wú)人機(jī)每次僅向一個(gè)中繼站運(yùn)送物資，完成任務(wù)后返回朱家尖客運(yùn)中心，裝載下一配送區(qū)域的物資運(yùn)往對(duì)應(yīng)的無(wú)人機(jī)配送中繼站，依此類推，每個(gè)中繼站均與無(wú)人機(jī)進(jìn)行一次對(duì)接，完成無(wú)人機(jī)和卡車的海島兩級(jí)配送任務(wù)．

圖6 38個(gè)無(wú)人機(jī)配送中繼站分布圖Fig.6 Distribution diagram of 38 drone delivery relay stations

4.3 終端路徑優(yōu)化

在此基礎(chǔ)上，劃分以無(wú)人機(jī)配送中繼站為聚類中心的38個(gè)配送區(qū)域，每個(gè)區(qū)域擁有1輛配送卡車，為包含38個(gè)中繼站在內(nèi)的共304個(gè)需求點(diǎn)提供服務(wù)．無(wú)人機(jī)將貨物運(yùn)往各中繼站后，卡車裝載貨物從中繼站出發(fā)，沿著最優(yōu)路徑依次為所在區(qū)域需求點(diǎn)進(jìn)行物資配送，完成任務(wù)后返回中繼站．

以所有卡車完成配送任務(wù)的卡車配送成本最低為目標(biāo)函數(shù)，利用改進(jìn)的模擬退火算法求解，算法的參數(shù)設(shè)置為α=0.99，T0=1 000，Tend=0.01，Lmax=300．

經(jīng)計(jì)算，所有卡車完成配送任務(wù)所行駛的總里程為28.43 km，配送成本為853.0元．各區(qū)域終端最優(yōu)配送路徑、卡車配送里程以及卡車配送成本如表3所示．

表3 部分區(qū)域配送路徑及卡車?yán)锍瘫鞹ab.3 Delivery routes and truck odometers in some regions

根據(jù)表3的配送情況，結(jié)合無(wú)人機(jī)從朱家尖客運(yùn)中心飛往無(wú)人機(jī)配送中繼站的路線，得到完整的無(wú)人機(jī)-卡車海島兩級(jí)物流配送網(wǎng)絡(luò)，如圖7所示．圖6中相同顏色的中繼站在圖7中屬于同一張兩級(jí)配送網(wǎng)絡(luò)圖．

圖7 普陀山海島應(yīng)急物流兩級(jí)網(wǎng)絡(luò)圖Fig.7 Two-level network chart of emergency logistics in Putuoshan Island

4.4 優(yōu)化方法對(duì)比

為驗(yàn)證本文所采取的無(wú)人機(jī)配送中繼站選址與卡車路徑一體優(yōu)化的效果，對(duì)同一算例設(shè)計(jì)選址與路徑兩段優(yōu)化的策略，先確定無(wú)人機(jī)配送中繼站的數(shù)量、選址，在此基礎(chǔ)上進(jìn)行卡車路徑優(yōu)化，求得系統(tǒng)總成本．兩種優(yōu)化方法求解結(jié)果對(duì)比如表4所示(以304個(gè)需求點(diǎn)為例)，將無(wú)人機(jī)配送中繼站的數(shù)量、選址以及卡車路徑同時(shí)進(jìn)行優(yōu)化的效果優(yōu)于兩段優(yōu)化．通過(guò)設(shè)置不同的最大中繼站建造數(shù)量，可以看出，隨著最大中繼站建造數(shù)量的增加，一體優(yōu)化方法的總成本改進(jìn)效果更明顯．

表4 兩種優(yōu)化結(jié)果對(duì)比Tab.4 Comparison of two optimization results

5 結(jié) 語(yǔ)

海島無(wú)人機(jī)配送中繼站的選址-路徑優(yōu)化問(wèn)題是影響海島應(yīng)急配送效率的關(guān)鍵性問(wèn)題，對(duì)物資配送成本和物資轉(zhuǎn)運(yùn)靈活度有直接影響．本文針對(duì)海島應(yīng)急物流中引入無(wú)人機(jī)配送的特征，以系統(tǒng)配送總成本最小為目標(biāo)，建立了海島無(wú)人機(jī)配送中繼站的選址-路徑優(yōu)化的雙層規(guī)劃模型．為了求解模型，設(shè)計(jì)了K-means聚類算法與改進(jìn)的模擬退火算法相結(jié)合的兩階段算法．以浙江省舟山市普陀山海島為背景，研究從朱家尖客運(yùn)中心將一批物資運(yùn)往普陀山海島304個(gè)需求點(diǎn)的兩級(jí)配送路徑，在這些需求點(diǎn)中選取38個(gè)無(wú)人機(jī)配送中繼站并為各個(gè)中繼站所負(fù)責(zé)的配送區(qū)域規(guī)劃卡車最優(yōu)路線，使得系統(tǒng)總成本達(dá)到最低，為1 013.1元．與兩段優(yōu)化方法相比，本文所采用的一體優(yōu)化方法使得系統(tǒng)總成本降低10.3%．

本文以無(wú)人機(jī)和卡車配送系統(tǒng)總成本最小為建模目標(biāo)，但沒(méi)有考慮無(wú)人機(jī)和卡車的容量限制，因此，考慮包含客戶需求量和運(yùn)載工具容量限制是未來(lái)研究的主要方向之一．此外，利用5G網(wǎng)絡(luò)超強(qiáng)的信息傳送能力，移動(dòng)網(wǎng)絡(luò)海量的站點(diǎn)資源可以為無(wú)人機(jī)提供從點(diǎn)到線再到面的立體覆蓋，從而實(shí)現(xiàn)無(wú)人機(jī)超視距控制，隨時(shí)掌控?zé)o人機(jī)的位置和空閑狀況、安全狀況等，將是無(wú)人機(jī)應(yīng)急物流領(lǐng)域一個(gè)跨時(shí)代的新應(yīng)用場(chǎng)景．