許 菱，楊林超，朱文興，鐘少君

1.江西理工大學 經濟管理學院，江西 贛州 341000

2.江西理工大學 商學院，南昌 330013

在全面推進鄉(xiāng)村振興和構建雙循環(huán)新發(fā)展格局的背景下，完善現代農村物流配送體系對推動農村電商產業(yè)發(fā)展、活躍農村消費市場具有重大戰(zhàn)略意義[1]。然而，由于農村電商物流配送還面臨著地理環(huán)境復雜、高標準基礎設施不足、“縣-鄉(xiāng)（鎮(zhèn)）-村”三級配送物流鏈條較長、客戶點分布密度較低等挑戰(zhàn)，農村電商物流尤其在末端配送部分還存在成本較高、時效性不強、客戶滿意度較低的問題[2]。因此，如何改進傳統(tǒng)配送方式，發(fā)展現代化農村電商物流配送體系，打通農村電商物流“最后一公里”，成為亟需解決的問題。

近年來，隨著無人機技術的不斷發(fā)展，因其具有成本低、速度快、實用性強、機動靈活不受地形道路限制的優(yōu)點，無人機在物流領域的應用成為現代物流業(yè)發(fā)展的新趨勢[3-4]。有研究報告指出，大約90%～95%的包裹重量不超過5磅（約2.27公斤），在最后一公里使用無人機配送，能夠降低80%配送成本[5-6]。此外，我國農村具有地域廣闊，鄉(xiāng)村聚落大多為聚類分布，沒有超高建筑、復雜的電磁環(huán)境的環(huán)境特點，適合物流無人機的應用[7]。但無人機配送也存在自身弊病，當前在物流末端配送領域應用的通常為旋翼無人機，還受到載重、續(xù)航能力的制約，使其難以單獨執(zhí)行大規(guī)模物流配送任務，因此無人機與車輛協同的配送模式成為必然選擇[8]。在此模式下，車輛作為無人機的移動倉庫和充電站，能提高無人機的配送能力與安全性，減少車輛的配送任務。綜合農村電商物流配送特點與無人機與車輛協同配送模式，如何優(yōu)化配送路徑，將無人機和車輛作為兩個既合作又相對獨立的運載工具進行融合使用，成為該模式成功應用的關鍵。

關于無人機與車輛協同配送的研究可以根據無人機與車輛的數量劃分為單無人機與單車輛的旅行商問題（traveling salesman problem with drone，TSP-D）、多無人機與單車輛的旅行商問題（traveling salesman problem with multiple drones，TSP-MD）、多無人機與多車輛的路徑規(guī)劃問題（vehicle routing problem with drones，VRPD）三類。2015 年，Murray 等[9]首次研究車輛搭載無人機聯合配送理論，提出了飛行助手旅行商問題（flying sidekick traveling salesman problem，FSTSP）和與之互補的并行無人機調度旅行商問題（parallel drone scheduling traveling salesman problem，PDSTSP）。隨后，眾多學者對該領域進行了細分和深入研究。Agatz等[10]提出搭載無人機旅行商問題（TSP-D），并基于局部搜索和動態(tài)規(guī)劃設計出兩階段啟發(fā)式算法來解決該問題。Ha 等[11]以總運營成本最小為目標構建TSP-D模型，并考慮了等待時間所產生的罰金成本。上述研究均是單無人機與單車輛配送的情形，Tu 等[12]擴展研究了一輛車輛搭載多架無人機的情形（TSP-MD）。Chang等[13]以最小化配送時間為目標，采用K-means算法并增加移動權重優(yōu)化車輛停靠點位置。Yoon 等[14]通過優(yōu)化無人機數量以及車輛和無人機的路線來最小化無人機的成本。曹英英等[15]考慮了時間窗限制，采用改進后的K-means 算法和遺傳模擬退火算法聯合優(yōu)化配送路線。隨著研究的深入，Wang 等[16]研究從單車輛擴展到多車輛模式下配備多無人機的協同配送問題的車輛路徑問題（VRPD）。Schermer 等[17]構建了VRP-D 的混合整數線性規(guī)劃模型，并引入一些不等式加速求解。Daknama 等[18]對無人機起降于不同車輛的場景進行研究。

從上述文獻可以看出，目前關于無人機與車輛協同配送的研究主要集中于城市場景，其中無人機起飛點多直接選擇配送區(qū)域中的某個點，或是簡單移動到最近的客戶點位置；在配送方式上多為無人機單包裹配送，且對于存在單一包裹超出無人機最大載重量這一實際情況考慮較少。因此，本文根據農村物流配送環(huán)境以及無人機配送特點，對K-means 算法進行改進，限制簇心即無人機起飛點僅能在客戶點位置，包含配送區(qū)域內沒有配送任務的客戶點，并篩選出每個簇中所有的簇心可行解。其次，考慮在無人機載重和續(xù)航能力的約束下，多無人機多包裹配送以及存在單個包裹超出無人機載重量只能由車輛配送的情況，改進遺傳算法，對所有無人機可起飛點進行全局考慮，聯合優(yōu)化無人機與車輛協同配送路徑。

綜上，本文綜合考慮農村物流配送環(huán)境、多無人機多包裹配送、無人機載重和續(xù)航等約束，以及存在單一包裹超出無人最大載重和無人機可在配送區(qū)域內無配送任務客戶點起飛等情形，以最小化配送成本為目標，構建混合整數規(guī)劃模型，并將改進后的K-means算法和遺傳算法相結合進行求解。最后，通過實驗仿真和案例驗證了模型和算法的可行性與有效性。研究結果表明，本文構建的模型更加符合農村物流配送場景，提出的改進算法能夠有效降低配送成本，進一步發(fā)展物流領域中無人機的應用理論；同時，本文的研究成果也可為多無人機-多包裹配送方面的后續(xù)研究提供參考。

1 問題描述

當前，農村電商物流末端配送通常使用車輛，從鄉(xiāng)鎮(zhèn)或核心村的物流網點向區(qū)域內的所有客戶配送包裹，如圖1所示。由于面臨“長物流鏈，低消費密度”等配送困境，導致物流難以形成規(guī)模，配送成本無法分攤降低，配送效率也難以提高，甚至在很多偏遠地區(qū)，包裹只能由用戶自取。因此，本文對無人機與車輛協同配送模式進行研究，如圖2 所示，車輛攜帶多架無人機和全部包裹從末端物流網點出發(fā)，按照規(guī)劃路線依次前往各車輛?？奎c，與無人機協同完成所有配送任務。其中將車輛完成配送任務及起飛無人機的客戶點稱為車輛?？奎c；將由無人機完成配送任務的客戶點稱為無人機客戶點；集群是指一個車輛停靠點及附近若干滿足無人機續(xù)航和載重約束的無人機客戶點的集合。具體而言，車輛從物流網點出發(fā)，行至車輛?？奎c后，首先根據客戶點需求由車輛完成該點配送任務，然后在該點起飛無人機對集群內無人機客戶點進行配送。無人機可在載重和飛行范圍內裝載多個包裹。無人機配送時，車輛在原地等候。最后，完成配送任務的無人機返回車輛裝載包裹和更換電池進行下一輪配送直至完成集群內所有配送任務。以此循環(huán)完成所有集群配送任務后一同返回配送網點?？紤]農村配送現實環(huán)境，限制車輛?？奎c只能在客戶點，包含區(qū)域內沒有配送任務的客戶點，同時考慮到無人機使用場景，規(guī)定配送網點和超出無人機載重的客戶點必須為車輛停靠點，其余車輛?？奎c由優(yōu)化結果決定，車輛?？奎c以外的包裹全部由無人機配送并根據無人機客戶點與不同車輛?？奎c距離進行集群劃分。

圖1 傳統(tǒng)的車輛單獨配送模式Fig.1 Traditional vehicle separate delivery mode

圖2 無人機與車輛協同配送模式Fig.2 Drones and vehicle collaborative delivery mode

為進一步對問題進行量化研究和數學建模，對場景及問題進行簡化，做出如下假設：

（1）所有客戶點位置、需求已知，可以起降無人機；

（2）無人機有載重量和飛行半徑限制且已知，車輛有足夠的容量、燃料和無人機電源，無載重和續(xù)航限制；

（3）無人機在其載重范圍內最大飛行距離固定不變，不考慮無人機飛行速度和環(huán)境對無人機飛行距離的影響；

（4）無人機一次能訪問一個或多個客戶，超出無人機最大載重量客戶由車輛配送，配送完成后只能返回車輛?？奎c更換電池或充電；

（5）無人機可以在車輛?？奎c重復起飛或降落，無人機起飛后，車輛在原地等待；

（6）無人機配送距離用歐氏距離計量，車輛配送距離用曼哈頓距離計量，均不允許出現子回路；

（7）每個客戶點由車輛或者無人機訪問一次，無人機和車輛都不能回訪任何客戶點。

2 模型構建

2.1 參數及變量說明

模型中涉及參數及變量說明如表1所示。

表1 參數及變量說明Table 1 Parameter and variable description

2.2 構建模型

根據問題描述和參數及變量定義，構建模型如下：

其中，公式（1）為目標函數，表示最小配送成本，包括車輛與無人機的配送成本；公式（2）表示每個客戶節(jié)點只能由無人機或是車輛服務一次；公式（3）確保無人機發(fā)射點都是車輛停靠點；公式（（4）表示所有無人機起飛點都至少有一架無人機起飛；公式（5）表示所有無人機客戶點都只能分配給一個集群；公式（6）表示車輛進出配送網點有且僅有一次；公式（7）表示集群半徑不超過無人機續(xù)航半徑；公式（8）表示車輛遍歷所有的?？奎c且僅一次；公式（9）表示無人機只能在單一集群內作業(yè)，即無人機只能在同一車輛?？奎c起降；公式（10）確保每個無人機客戶點有且僅有一架無人機服務；公式（11）表示無人機對每一節(jié)點進出度相同；公式（12）表示車輛對每一?？奎c進出度相同；公式（13）表示無人機飛行載重約束；公式（14）表示無人機飛行距離約束；公式（15）表示消除車輛子回路；公式（16）表示消除無人機子回路。

3 算法設計

本文研究的問題屬于NP-Hard 問題，精確算法僅在小規(guī)模算例中存在優(yōu)勢，傳統(tǒng)優(yōu)化方法也很難求解，考慮到啟發(fā)式算法在這類問題中的廣泛應用，尤其是K-means 算法與遺傳算法在車輛路徑規(guī)劃問題中的成功應用。本文基于K-means算法與遺傳算法，結合農村物流配送實際環(huán)境與無人機與車輛協同配送方式，對算法進行改進。將問題拆分為兩個階段，聯合優(yōu)化無人機與車輛路徑，實現配送成本最小化，具體算法流程邏輯如圖3所示。

圖3 兩階段混合算法流程邏輯圖Fig.3 Flow logic diagram of two-stage hybrid algorithm

第一階段，首先根據客戶包裹重量與無人機最大載重量將客戶分為超重客戶和無人機客戶。其次，將超重客戶點和物流網點設為初始車輛?？奎c，并以它們?yōu)橹行膶⒅車鸁o人機續(xù)航半徑范圍內的無人機客戶按距離劃分至相應的初始車輛?？奎c。最后，采用改進K-means算法，根據無人機續(xù)航半徑對剩余無人機客戶進行聚類，將配送區(qū)域劃分為數量最小且不重疊的簇，并篩選出每個簇內所有車輛候選?？奎c；第二階段，以第一階段為基礎，采用爬山算子與分裂算子改進遺傳算法，以最小配送成本為目標，對每個簇內車輛候選?？奎c和無人機客戶點進行全局考慮，優(yōu)化無人機與車輛聯合配送路徑。

3.1 第一階段——客戶分簇

K-means 算法是一種基于劃分的聚類算法，具有簡單、快捷的特點，且在處理大型數據集時具有可擴展性和高效性，但對初始聚類中心和異常值較為敏感，且需要預先指定聚類數值。在實際應用中傳統(tǒng)的K-means算法先給定聚類數值K，按照相似度將對象分成K個簇，簇間對象彼此相似度盡量低，相似度通常通過計算對象之間的歐式距離dij得出，距離越小表示二者越相似，每個簇的簇心由該簇內所有對象點的均值得到。為解決農村電商物流末端配送實際環(huán)境下無人機與車輛協同配送路徑優(yōu)化問題，本文對K-means 算法進行改進，首先，參考文獻[13]中自適應方法，通過迭代的方式將無人機客戶點劃分成最小K個不重疊的簇。其次，為滿足車輛?？啃枨?，限制簇心位置僅能在客戶點，包括區(qū)域內沒有配送任務的客戶點，以擴大搜索范圍。最后，根據無人機續(xù)航半徑，對簇內所有客戶進行篩選，將滿足簇心條件的客戶點設為簇心候補解，擴大搜索空間，避免丟失最優(yōu)解。優(yōu)先選擇配送網點和超重點為簇心。具體實現過程如下：

（1）對無人機客戶點進行K-means 聚類，限制簇心位置在客戶點，設定初始聚類數K=1。

（2）計算簇內所有客戶點到簇心的歐式距離，將距離最近的客戶點更新為新簇心。

（3）計算簇內客戶點到新簇心的距離，如均不超出無人機續(xù)航半徑，轉步驟（4），否則，更新K=K+1，轉步驟（1），循環(huán)操作。

（4）計算各簇內所有客戶點之間距離矩陣，篩選滿足到簇內所有客戶點距離都小于無人機續(xù)航半徑的客戶點為該簇的簇心候補解。

（5）輸出聚類結果。

3.2 第二階段——聯合優(yōu)化

遺傳算法是一種模擬大自然中生物進化過程來搜索最優(yōu)解的方法，通過適應度評估篩選個體來尋找問題的滿意解，是一種具有自適應、全局搜索能力的啟發(fā)式算法。傳統(tǒng)的遺傳算法在全局搜索能力上較強，但局部搜索能力不足，易陷入局部最優(yōu)，在運算過程中易過早收斂，出現“早熟”現象。爬山算法是一種局部搜索優(yōu)化算法，雖然全局搜索能力較弱，但具有較強的局部搜索能力。本文采用爬山算子改進遺傳算法，以增強算法局部搜索能力，并提升算法的計算性能。且為避免搜索空間不足，丟失最優(yōu)解情況，設計一種虛位操作，對所有簇心候選解進行全局考慮。此外，考慮無人機多包裹配送情況，設計分裂算子，根據無人機載重和續(xù)航能力的約束對算法中染色體進行分裂操作，實現無人機多點配送，從而提高配送效率。具體操作步驟如下：

（1）設定遺傳算法初始化參數。種群規(guī)模N、最大迭代次數M、選擇概率Ps、交叉概率Pc、變異概率Pm等，生成初始種群。初始種群采用隨機生成的方式，染色體編碼對應車輛前往?？奎c順序，隨機生成N條長度為K的染色體，K為車輛停靠點數。

（2）虛位操作。將聚類的簇心基因即車輛在該簇?？奎c位置設置為虛位，用字母X、Y等表示。根據一階段聚類結果，每個虛位對應該簇的簇心候補解集。初始化時，每條染色體隨機選擇簇心候補解集中的客戶點作為該虛位的實際基因，并計算適應度。染色體操作時，先對虛位基因進行，再根據虛位在不同染色體中隨機對應的實際基因進行還原。

（3）建立適應度函數。目標函數公式（1）為配送成本最小函數，故以其倒數作為適應度函數。適應度函數是用來篩選群體中染色體的優(yōu)良程度，適應度值越大，個體越優(yōu)則總成本越低。

（4）遺傳算子操作，根據遺傳策略進行選擇、交叉、變異一系列操作，并計算適應度函數。

選擇操作是以選擇概率Ps從種群中選擇若干個個體進行后續(xù)交叉、變異等操作，選擇過程是一種基于適應度的優(yōu)勝劣汰的過程。本文采用輪盤賭的方式進行選擇，通過模擬將種群中所有染色體的適應度值在一個圓盤上呈現，轉動圓盤進行選擇。圓盤上個體適應度值越大則所占面積就越大，轉動圓盤選擇時被選中的概率就越大。個體被選中的概率與其適應度大小成正比，其概率計算公式如公式（17）所示：

交叉操作是將選擇出的個體兩兩以交叉概率Pc進行隨機部分染色體交換，產生新的個體。本文采用部分映射的方式進行交叉，隨機部分片段進行交叉，以部分映射的方式對交叉后有沖突的位置進行消除。過程如圖4所示。

圖4 交叉操作Fig.4 Cross operation

變異操作是以變異概率Pm將個體染色體中的某些基因位上的基因進行交換，從而形成一個新的個體。本文采用隨機兩點互易的方式進行變異，提高局部搜索能力。過程如圖5所示。

圖5 變異操作Fig.5 Mutation operation

（5）爬山算子操作。對新種群中的個體進行爬山操作并計算適應度，將爬山優(yōu)化前后個體的適應度值進行比較，若爬山優(yōu)化后個體適應度提升，則用新個體取換原個體；否則保留原個體。具體爬山操作為，首先選擇遺傳操作篩選后種群中的染色體為原染色體，隨機截取該染色體上的基因片段，然后對截取的基因片段進行隨機排序并插入原染色體得到新染色體，最后對比原染色體和新染色體適應度，若新染色體適應度高于原染色體，則用新染色替代原染色體，否則保留原染色體。過程如圖6所示。

圖6 爬山操作Fig.6 Climbing operations

（6）分裂算子操作。針對無人機配送中一次配送多個包裹的情況，考慮無人機載重和續(xù)航的約束對種群中的個體進行分裂操作，使無人機往返起飛點進行補給，具體操作步驟如下：

①選擇初始種群中的染色體為原染色體，令初始n=1，計算無人機完成前n個客戶的配送距離以及前n個客戶的累計包裹重量并與無人機最大續(xù)航和載重進行對比。

②若二者均小于無人機最大續(xù)航和載重則更新n=n+1 轉步驟1，否則在染色體n與n+1 中間插入1（1為無人機起飛點）并從n+1 處轉步驟1。

③循環(huán)①和②至染色體全部基因位，產生新的染色體并計算新染色體的適應度。以n1=3、n2=6 處分裂為例，過程如圖7所示。

圖7 分裂操作Fig.7 Splitting operation

4 實驗仿真與分析

為驗證本文數學模型與兩階段算法的有效性和可行性，本文使用Solomon[19]算例集以及某地實際案例對模型和算法進行有效性測驗。本文兩階段算法均由Matlab 編程實現；實驗運行環(huán)境為Windows10 操作系統(tǒng)，Intel?Core?i5-7200U CPU @ 2.50 GHz 處理器，16 GB內存。算法參數設置方面，種群規(guī)模設為200、最大迭代次數設為200、選擇概率設為0.9、交叉概率設為0.9、變異概率設為0.1，車輛和無人機的單位配送成本分別設為1.25元/km和0.15元/km[20]。

同時，為了評估本文模型的準確性和兩階段算法的有效性，參考文獻[21]中的做法，設置松弛條件：無人機沒有續(xù)航和載重限制，即一架無人機可完成聚類內所有無人機客戶點的配送。將無人機路徑問題轉化成TSP問題，通過求解標準的TSP模型確定無人機最短路徑。

4.1 算例描述

目前，針對本文所研究的問題尚缺乏標準測試算例，為驗證本文模型及算法的有效性和可行性，本文以Solomon算例集作為基礎數據集，改進生成不同規(guī)模的數據集。改進方法為：將算例集全部配送點設為配送區(qū)域內所有客戶點，隨機選擇部分設為有配送任務的客戶，選擇10、20、30 個客戶點，構建中小規(guī)模數據集，選擇50、70 個客戶點，構建大規(guī)模數據集。為方便計算，無人機配送的飛行距離采用歐式距離，車輛配送的行駛距離采用曼哈頓距離。設定超重點比例為客戶點數M的10%，剩余客戶的需求量為原來的1/4，單位為kg，以符合現實情況。Solomon 算例中根據顧客分布情況分為3類：C類表示顧客分布比較集中，R類顧客分布比較隨機，RC 類既有集中分布的顧客，又有隨機分布的顧客。為避免隨機選取數據造成的實驗結果偏差，對Solomon算例集包含的三大類算例分別進行選取，由于每一類算例中內部所有算例的節(jié)點坐標和顧客需求相同，因此僅從每一類中選取一個算例。設定無人機最大載重量15 kg，最大續(xù)航里程15 km。

4.2 算例結果與分析

根據Solomon 測試算例和無人機與車輛的相關參數，結合無人機與車輛協同配送模型，對算例采用自適應K-means算法和CPLEX商業(yè)求解器兩階段求解與本文提出的兩階段算法求解結果進行對比，結果如表2所示。表2顯示了在不同算例及規(guī)模下，在兩種求解方法下的車輛?？奎c數量、車輛行駛距離、無人機飛行距離以及配送成本之間的誤差GAP，GAP 的具體計算公式如公式（18）所示：

表2 自適應K-means+CPLEX與兩階段算法結果對比Table 2 Comparison of results between adaptive K-means+CPLEX and two-stage algorithm

由表2可知，本文提出的兩階段算法在15個不同測試算例中配送成本均有下降，其中有7個測試算例的配送成本降低10%以上，驗證了模型和算法的可行性與有效性。具體說來，優(yōu)化結果可以分為兩種類型：一是優(yōu)化車輛停靠點位置，基于K-means 算法改進，篩選滿足到簇內所有客戶點距離都小于無人機續(xù)航半徑的客戶點為車輛候選停靠點，通過改進遺傳算法對所有車輛候選?？奎c進行全局優(yōu)化，如RC101/30、C101/50等；二是不僅優(yōu)化?？奎c位置且減少車輛?？奎c數量：考慮將沒有配送任務的客戶點加入車輛可停靠點，在無人機續(xù)航半徑有限的情況下，擴大車輛?？奎c搜索范圍，減少聚類數即車輛?？奎c數量并優(yōu)化車輛?？奎c位置，如RC101/70、R101/30等。

為進一步驗證改進遺傳算法的性能，以RC101/20為例，采用改進遺傳算法與傳統(tǒng)的遺傳算法分別求解，參數設置同上，結果對比如圖8 所示。由圖可知，改進遺傳算法較傳統(tǒng)遺傳算法迭代次數更少，求出的解也更優(yōu)，這表明改進遺傳算法較傳統(tǒng)遺傳算法有著更好的求解性能，尋優(yōu)效率更高，尋優(yōu)能力更強。

圖8 收斂性能對比圖Fig.8 Convergence performance comparison chart

4.3 靈敏度分析

本文分別對無人機續(xù)航半徑、無人機載重量等參數進行靈敏度分析，探討無人機性能參數對配送成本的影響。

4.3.1 無人機續(xù)航半徑靈敏度分析

本文選擇客戶點數為50 的C 組、R 組和RC 三組算例，將無人機最大載重量設定為15kg，對無人機續(xù)航半徑分別設定為10 km、15 km、20 km 和25 km，進行靈敏度實驗測試，分析無人機續(xù)航半徑對配送成本的影響，其結果對比如圖9所示。

圖9 無人機續(xù)航半徑靈敏度分析圖Fig.9 Sensitivity analysis of drone range radius

綜合算例結果可以發(fā)現，在無人機續(xù)航半徑不斷提高下，配送成本不斷降低；在無人機續(xù)航半徑從10 km變動到15 km 時，配送成本下降幅度較大；在無人機續(xù)航半徑從15 km 變動到20 km、20 km 變動到25 km 時，配送成本下降幅度較小。分析原因為：在無人機續(xù)航半徑較小時，由于農村配送區(qū)域廣闊，無人機能承擔的配送任務有限，在協同配送模式中發(fā)揮作用較小。隨著無人機續(xù)航半徑的增加，無人機承擔的配送任務能力提升，發(fā)揮作用較大，配送成本下降，但無人機還受載重量限制，所以無人機飛行范圍繼續(xù)增加時，配送成本降低幅度較小。通過對不同算例組數據進行分析發(fā)現，由于C組客戶分布較為集中，R組客戶分布較為分散，所以在無人機續(xù)航半徑不斷提高時，C組配送成本下降幅度較小、R組配送成本下降幅度較大。RC組數據由和C組數據和R組數據混合而成，所以下降幅度介于二者之間。

4.3.2 無人機載重量靈敏度分析

本文選擇客戶點數為50 的C 組、R 組和RC 三組算例，將無人機最大續(xù)航半徑設定為15 kg，對無人機載重量分別設定為10 kg、15 kg、20 kg 和25 kg，進行靈敏度實驗測試，分析無人機載重量對配送成本的影響，其結果對比如圖10所示。

圖10 無人機載重量靈敏度分析圖Fig.10 Sensitivity analysis of drone load capacity

綜合算例結果可以發(fā)現，在無人機載重量不斷提高下，配送成本降低，但下降幅度較小。究其原因為：隨著無人機載重量提高，一方面，超重客戶減少能減少車輛固定行駛距離，且使無人機單次可配送客戶數量增加也能減少無人機飛行距離。但另一方面，由于配送區(qū)域面積與無人機續(xù)航半徑不變，超重點客戶減少會促進無人機客戶分簇數量增多，這反過來又增加車輛前往各簇心距離與無人機配送距離。通過對不同算例組數據進行分析發(fā)現，C 組客戶需求量較為規(guī)整，多為5 的倍數，R組客戶需求量較為零散，且存在部分需求量較小的客戶點，所以隨著無人機載重范圍的變動，C 組配送成本波動幅度較小，R組配送成本波動幅度較大，RC組數據由和C組數據和R組數據混合而成，所以同樣出現下降情況，但下降變化滯后。

4.4 案例分析

綜上分析，本文所提出的兩階段算法對無人機與車輛協同配送路徑優(yōu)化問題具有較好的求解性能，為進一步驗證本文所提模型和算法的實用性和有效性，選取江西省贛州市某農村地區(qū)來對無人機與車輛協同配送模式進行案例研究。贛州市是革命老區(qū)，地理環(huán)境多山地、丘陵，基礎設施缺乏，物流業(yè)的發(fā)展先天受限，同時也是國內首個獲批物流無人機運行區(qū)申請的地區(qū)，因此選擇其作為案例具備一定的代表性。具體位置分布如圖11所示。

圖11 客戶點分布Fig.11 Customer point distribution

案例具體描述為：某配送網點需要將包裹配送至周邊三十個村莊的村莊代收點，詳細信息如表3 所示，其中序號12、17、26三個代收點需求超過無人機最大載重量，其他代收點均可由無人機配送。無人機配送距離用歐氏距離計量，車輛配送距離用百度地圖道路距離計量，車輛無載重和續(xù)航限制，無人機最大載重量15 kg，最大續(xù)航里程15 km，車輛和無人機的單位配送成本分別設為1.25元/km和0.15元/km。

表3 客戶點信息Table 3 Customer point information

根據案例區(qū)域內各村代收點位置和需求信息，以及無人機和車輛相關參數，運用兩階段算法對無人機與車輛協同配送模式進行求解，并采用傳統(tǒng)粒子群算法、蟻群算法與CPLEX商業(yè)求解器對傳統(tǒng)車輛單獨配送模式求解，每次計算進行十次，取最小值。結果對比如表4所示，結果表明，無人機與車輛協同配送模式不僅能夠在農村地區(qū)有效完成“最后一公里”配送任務，并且在配送成本上無人機與車輛協同配送模式較比傳統(tǒng)車輛配送具有優(yōu)勢。

表4 協同配送與車輛配送訪問順序及成本Table 4 Access sequence and cost of collaborative delivery and vehicle delivery

5 結束語

隨著農村電商產業(yè)的迅猛發(fā)展，給農村電商物流配送體系，尤其是末端配送部分帶來了巨大挑戰(zhàn)，也催生了農村電商物流變革創(chuàng)新的需求。近年來，無人機技術逐漸成熟，無人機參與配送成為解決物流業(yè)末端配送難題的重要手段。無人機與車輛協同模式克服了無人機配送能力有限、安全性不高的弊端，能切實有效解決“長物流鏈，低消費密度”等特點給農村電商物流末端配送帶來的成本較高、時效性不強、客戶滿意度低等問題，在農村電商物流領域具有較大的發(fā)展空間。

本文基于農村電商物流配送實際環(huán)境以及無人機發(fā)展現狀，綜合考慮車輛?？课恢玫南拗埔约盁o人機多包裹配送、存在單個包裹超出無人機載重等約束，以最小化配送成本為目標構建了無人機與車輛路徑問題的混合整數規(guī)劃模型，并提出一個兩階段算法。第一階段改進了K-means 算法，通過迭代的方式確定聚類數K，求解各簇內所有能夠以無人機續(xù)航半徑覆蓋的簇心候選解，并限制簇心位置為客戶點位置，包含沒有配送任務的客戶點，以擴大搜索范圍，符合實際情況。第二階段通過爬山算子和分裂算子改進遺傳算法對無人機和車輛路徑進行聯合優(yōu)化。最后，通過算例實驗和案例分析，驗證了無人機與車輛協同模式的可行性以及模型和算法的有效性，并分析了無人機性能參數對綜合配送成本的靈敏度。

此外，由于路徑優(yōu)化問題是一個復雜難題，影響決策的因素眾多。本文未考慮配送效率對路徑優(yōu)化的影響，未來將把時間窗因素考慮在內，優(yōu)化配送時間提升配送效率，進一步建立多目標求解模型進行更深入的研究。