面向農(nóng)村電商的無人機-車輛聯(lián)合配送系統(tǒng)設(shè)計與實現(xiàn)

吳杭軒 張翠平 傅聿焯 王子宇

DOI：10.19850/j.cnki.2096-4706.2024.02.017

收稿日期：2023-06-19

基金項目：北京信息科技大學(xué)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目-計算機學(xué)院（5112210832）

摘? 要：農(nóng)村配送的“最后一公里”是一大難題。文章分析了目前對于無人機車輛聯(lián)合配送模式研究現(xiàn)狀。結(jié)合貨車單獨配送具有載貨量大，運輸距離長，農(nóng)村路況復(fù)雜等特點，引入無人機加入配送。為了兼顧配送效率，嚴(yán)格分工，采取無人機和貨車聯(lián)合配送的模式來建立模型。文章利用模擬退火算法，優(yōu)先確定貨車的路徑。然后，考慮貨物質(zhì)量與路況等條件對無人機的路徑進(jìn)行規(guī)劃。通過與其他配送模式比較，體現(xiàn)出聯(lián)合配送模式下的配送效率明顯提高。

關(guān)鍵詞：農(nóng)村最后一公里；路徑規(guī)劃；聯(lián)合配送；模擬退火算法

中圖分類號：TP391? 文獻(xiàn)標(biāo)識碼：A? 文章編號：2096-4706（2024）02-0075-07

Design and Implementation of UAV-Vehicle Joint Distribution System for Rural E-Commerce

WU Hangxuan， ZHANG Cuiping， FU Yuzhuo， WANG Ziyu

（Computer School， Beijing Information Science and Technology University， Beijing? 100101， China）

Abstract： The “l(fā)ast kilometer” of rural distribution is a big problem. This paper analyzes the current research status of UAV-vehicle joint distribution mode. In combination with the characteristics of large load， long transportation distance， and complex rural road conditions of separate truck distribution， UAV is introduced to participate in distribution. In order to give consideration to the distribution efficiency and strictly divide the labor， the model is established by adopting the mode of UAV and truck joint distribution. In this paper， the simulated annealing algorithm is used to determine the route of the truck first. Then， it considers the cargo quality and road conditions to plan the route of UAV. Compared with other distribution modes， the distribution efficiency under the joint distribution mode is significantly improved.

Keywords： the last rural kilometer; path planning; joint distribution; simulated annealing algorithm

0? 引? 言

據(jù)調(diào)查，我們發(fā)現(xiàn)農(nóng)村物流的末端基礎(chǔ)設(shè)施不完善，雖已基本實現(xiàn)村村同公路，但通常存在多小路，導(dǎo)致車輛無法運送等困難。并且地形分散，難以建立比較集中的倉庫作為中轉(zhuǎn)站。為了解決農(nóng)村物流配送最后一公里的難題，提高配送效率。我們探究無人機和車輛聯(lián)合配送的模式。旨在通過研究無人機和與車輛聯(lián)合配送的模式，來解決農(nóng)村電商末端配送的問題，提高配送效率。根據(jù)調(diào)查，對于末端配送問題，已有無人機配送，物流小車的多種組合模式。本項目主要通過無人機和車輛之間的聯(lián)合配送、靈活分工，來提高配送效率。

而目前對于“無人機-車輛”聯(lián)合配送的研究主要分為兩類。一類是基于TSP問題不斷改進(jìn)（比如考慮到無人機需要在倉庫或客戶點取貨/送貨）；另一類是基于VRP問題，延伸出考慮續(xù)航問題的VRP-D等。這兩類都是先確定車輛的路徑，之后再對無人機的路徑進(jìn)行規(guī)劃。本項目也采取此方式。

首先建立好聯(lián)合配送的數(shù)學(xué)模型，基本的實現(xiàn)方式是先確定車輛的路徑，之后再對無人機的路徑進(jìn)行規(guī)劃；之后再通過MATLAB平臺對模型進(jìn)行代碼實現(xiàn)。而車輛路徑最優(yōu)解的確定主要通過模擬退火算法找尋；最后對建立的模型進(jìn)行算例分析。

其中，主要問題是無人機與車輛配送時路徑規(guī)劃和分工的問題?；谶@一個中心，對聯(lián)合配送路徑優(yōu)化算法進(jìn)行研究，構(gòu)建無人機參與的末端配送模型，利用模擬退火算法等求解該模型。預(yù)期將通過無人機和車輛組合的聯(lián)合配送模式，以及依賴于貨物重量等因素的靈活分工，驗證配送效率的提升。

1? 農(nóng)村物流與末端配送發(fā)展現(xiàn)狀

1.1? 農(nóng)村電商末端配送現(xiàn)狀

近年來，隨著電子商務(wù)的蓬勃發(fā)展，我國農(nóng)村電商物流發(fā)展規(guī)模不斷龐大，網(wǎng)購已經(jīng)成為農(nóng)村新的消費與農(nóng)產(chǎn)品銷售渠道。我國農(nóng)村龐大的網(wǎng)絡(luò)使用群體與不斷增長的網(wǎng)購需求對農(nóng)村的物流體系建設(shè)提出了新的挑戰(zhàn)與要求，在農(nóng)村寄遞物流體系建設(shè)的大背景下，農(nóng)村物流末端配送模式有待優(yōu)化[1]。農(nóng)村的電子商務(wù)的銷售額增速在不斷提高，在物流配送行業(yè)當(dāng)中已經(jīng)占有較高的市場。但由于農(nóng)村地理位置和路況等原因，對于傳統(tǒng)的車輛運輸有比較大的困難，特別是對于有農(nóng)田以及池塘分布的農(nóng)村區(qū)域，傳統(tǒng)的車輛根本無法進(jìn)行正常的配送。農(nóng)村物流的末端基礎(chǔ)設(shè)施同樣不完善，雖已基本實現(xiàn)村村同公路，但通常存在多小路/多岔路，導(dǎo)致車輛無法運送困難。并且大部分地區(qū)地形分散，難以建立比較集中的倉庫作為中轉(zhuǎn)站[2]。

農(nóng)村電商配送的問題主要可以概括為以下幾個方面：1）農(nóng)村物流體系不健全，網(wǎng)點覆蓋率較低。2）配送服務(wù)質(zhì)量不高，配送能力較低。3）基礎(chǔ)設(shè)施不完善，信息化程度偏低。4）農(nóng)村物流人才匱乏，行業(yè)規(guī)范性不足[3]。

1.2? 無人機-車輛聯(lián)合配送模式在農(nóng)村電商配送中的應(yīng)用價值

隨著我們對科技研究的逐漸深入，無人機在現(xiàn)實生活中的應(yīng)用領(lǐng)域越來越廣。針對物流配送而言，無人機不僅可以滿足傳統(tǒng)快遞送貨上門直達(dá)的一站式服務(wù)，同時還可以緩解傳統(tǒng)陸地配送所帶來的交通壓力，避免交通擁堵，提高物流配送的效率。除此之外，作為一種新型的配送工具，無人機也具有應(yīng)用方便，適應(yīng)性強等多方面的優(yōu)點。

而無人機配送又能無視地面環(huán)境，大幅縮短配送距離，對于實現(xiàn)農(nóng)村物流“最后一公里”配送有著極大的優(yōu)勢。無人機的特點主要有操作簡便、使用靈活、配送服務(wù)效率高、綜合成本低等，而傳統(tǒng)貨車則具有貨物裝載量大、運輸距離長的優(yōu)勢，因此兩者相結(jié)合的新型物流配送方式已逐漸成為近年來關(guān)于配送問題研究熱點。

目前，依托無人機的配送主要由以下兩種方式：其中一種是“一對多”“點對多”的配送模式，此類方式側(cè)重打造由干線到先到支線，再由支線逐個分配到末端的三級智能化物流體系[4]。另一種是“一對一”“點對點”的配送模式，主要側(cè)重于對支線無人機的研制與應(yīng)用。

無論是無人機還是車輛，在配送方面都有各自的限制。無人機需要考慮飛行路徑、燃油情況、貨物載重等，而車輛則需要考慮交通狀況、配送時間等。因此在考慮兩者結(jié)合的配送時，必須滿足在無人機返回到接收車輛并且準(zhǔn)備下一次交付之前，不影響交付車輛進(jìn)行其他交付并能繼續(xù)將貨物進(jìn)行正常配送?；谝陨系姆治龊涂紤]，我們打算研究一臺車輛配備兩臺無人機進(jìn)行聯(lián)合配送，以此來解決農(nóng)村電商配送末端“最后一公里”問題。

1.3? 無人機-車輛聯(lián)合配送模式的研究意義

在市場競爭如此激烈的今天，各企業(yè)商戶都在不斷通過完善和優(yōu)化自己的配送方式，以此增加運力保障、拓展運輸線路。盡可能壓縮配送時間，提高物流配送效率，從而最大限度提高競爭力以及物流市場的占有率。以此催生了無人機車輛聯(lián)合配送的運輸新模式，來實現(xiàn)物流企業(yè)配送效率的最大化。

與傳統(tǒng)的實現(xiàn)送貨上門的單一車輛配送模式相比，將無人機應(yīng)用到配送之中并且與車輛進(jìn)行聯(lián)合配送，不僅可以有效減少配送時間，還能夠提高貨物配送效率，在實現(xiàn)商戶與用戶交付的同時，最大限度節(jié)約物流的綜合成本。

在看到物流業(yè)迅猛發(fā)展的同時，我們也應(yīng)看到傳統(tǒng)單一道路交通配送方式對于環(huán)境的影響。根據(jù)世界衛(wèi)生組織（WHO）的報道，自20世紀(jì)70年代以來，許多地區(qū)物流行業(yè)發(fā)展迅速，傳統(tǒng)的車輛配送所排放的溫室氣體無論對環(huán)境還是人民的生命健康都存在一定的威脅和影響。因此我們在追求物流配送最大化經(jīng)濟(jì)效益的同時，也同樣應(yīng)該考慮其所帶來的環(huán)境問題，研究新型的配送模式來滿足國家對于可持續(xù)發(fā)展戰(zhàn)略的要求。

2? 無人機車輛聯(lián)合配送模式研究現(xiàn)狀

2.1? 國內(nèi)外的研究現(xiàn)狀

目前隨著物流配送形式的不斷創(chuàng)新，對于無人機配送模式的研究逐漸增多，針對不同的配送模式，所考慮的路徑規(guī)劃也不完全相同。對于無人機配送現(xiàn)今一般有兩種研究方向。當(dāng)無人機單獨交付配送時，影響無人機配送路徑規(guī)劃的主要因素有：能耗因素、環(huán)境天氣因素、機械故障因素，等等。當(dāng)無人機與車輛進(jìn)行協(xié)同配送時，影響配送路徑規(guī)劃的主要因素有：無人機的回收問題，車輛與無人機配送的對接問題，無人機飛行距離、飛行時間、貨物載重量受限的問題。面對以上所提出的種種問題，國內(nèi)的研究大多都傾向無人機與車輛進(jìn)行聯(lián)合配送，從而擴(kuò)大配送范圍，提高配送效率的同時最小化配送成本。

根據(jù)配送主體的不同，任新惠[5]主要將配送方式分為以下3類：卡車與無人機組合、無人柜與無人機組合、無人倉與無人機組合。根據(jù)車輛與無人機的配送關(guān)系的不同，又分為車輛支持無人機、無人機支持車輛、無人機車輛同步運行以及無人機和車輛獨立運行4類。

國內(nèi)有研究者提出5類車輛與無人機配送模式：車輛與無人機協(xié)同配送、車輛與無人機并行配送、車輛支持無人機配送、無人機支持車輛配送，以及混合模式配送[6]。也可分為無人機獨自運行配送與無人機與車輛協(xié)同配送，如圖1所示。

從組合模式上來看，根據(jù)無人機與車輛承擔(dān)的角色，分為4類，如圖2所示。圖中，第1類是車輛輔助無人機，無人機作為主要驅(qū)動，車輛負(fù)責(zé)將無人機運輸?shù)教囟ǖ攸c。第2類是無人機輔助車輛運行，讓車輛負(fù)責(zé)配送任務(wù)，無人機作為輔助從倉庫為車輛補充貨物；第3類是無人機與車輛獨立運行，是指無人機和車輛獨立配送；第4類是無人機和車輛并行配送，是指無人機與車輛都進(jìn)行配送任務(wù)，同時車輛作為無人機的起降點和充電站，在車輛運行過程中無人機動態(tài)的與車輛交匯。

農(nóng)村地區(qū)交通條件不便等諸多因素，物流配送經(jīng)常受到比較大的阻礙。無人機同時又具有使用靈活、成本低等優(yōu)勢。而傳統(tǒng)的配送車輛則有貨物載重量大，可配送距離長的優(yōu)勢。所以，采用圖示第4類并以車輛為主要驅(qū)動，無人機作為輔助的組合模式比較合理。

2.2? 配備無人機的車輛路徑問題研究現(xiàn)狀

雖然車輛-無人機從構(gòu)思集成到實際交付服務(wù)中的研究還處于比較起步的研究階段，但在過去幾年中相應(yīng)的研究課題也不斷增加。針對無人機與車輛的路徑問題，研究者在進(jìn)行建模設(shè)計時，主要從兩類模型出發(fā)。一類是從TSP出發(fā)，例如，Murray等[7]提出的FSTSP和PDSTSP；Agatz等[8]提出的TSP- D等。隨后，在此研究基礎(chǔ)上，Yurek等[9]又進(jìn)一步設(shè)計了求解FSTSP的兩階段迭代算法，Kitjacharoenchai等[10]對FSTSP算法進(jìn)行了相應(yīng)的優(yōu)化和改編，進(jìn)一步考慮到了無人機能同時在倉庫或顧客點進(jìn)行取貨或送貨的問題。

總結(jié)之前對于“無人機-車輛”聯(lián)合配送的研究。研究方向大概分為兩類：一類是基于TSP問題不斷改進(jìn)（比如考慮到無人機需要在倉庫或客戶點取貨/送貨）；另一類是基于VRP問題，延伸出考慮續(xù)航問題的VRP-D等[11]。這兩類都是先確定車輛的路徑，之后再對無人機的路徑進(jìn)行規(guī)劃，本文也采取這種方式。

3? 配送模型設(shè)計

3.1? 問題描述

該項目旨在通過研究無人機和與車輛聯(lián)合配送，來解決農(nóng)村電商末端配送的問題。其中，主要問題是無人機與車輛配送時路徑規(guī)劃的問題。并基于配送的總時間最小，來對聯(lián)合配送路徑優(yōu)化算法進(jìn)行研究，構(gòu)建無人機參與的末端配送的數(shù)學(xué)模型，利用模擬退火算法等求解該模型。任務(wù)開始，由一個車輛配備兩架無人機，負(fù)責(zé)一片區(qū)域需求點的配送任務(wù)。無人機與車輛同時從倉庫出發(fā)，到貨物配送完成后的整個過程，需要遍歷完成整片區(qū)域的需求點配送，最終回到倉庫。配送過程中，無人機和車輛任務(wù)分配決定的因素主要有具體的貨物重量、運送的路況等，并且每當(dāng)無人機配送時，車輛將根據(jù)之后的路況和貨物重量，選擇同時配送和等待回收。所以，車輛和無人機的配送時間將會有重合的部分。將通過MATLAB建立的模型并進(jìn)行模擬計算，選取配送時間最大的加入目標(biāo)函數(shù)，減去重復(fù)計算的時間。

3.2? 問題假設(shè)

對數(shù)學(xué)模型設(shè)計做如下假設(shè)，以簡化模型：

1）車輛與無人機在行駛配送路途中沒有被不可抗力干擾。

2）每一個需求點的配送，未考慮等待時間，即時間窗問題。

3）每次配送任務(wù)是遍歷所有需求點，不會重復(fù)經(jīng)過同一需求點。

4）對于彎曲路線，只計算路線距離，不考慮彎曲路線帶來的影響。

3.3? 問題分析

3.3.1? 求出初始最短路徑

首先，對于所有的需求點，通過模擬退火算法求出初始最短配送路徑S，之后根據(jù)最短路徑序列S，分析無人機和貨車的配送情況。

3.3.2? 無人機和貨車路徑分析

1）判定條件。每當(dāng)貨車抵達(dá)一個需求點，獲取下一次的貨物質(zhì)量和需求點的類型，來判定下一次的配送者。判定情況有兩種：當(dāng)“貨物質(zhì)量m≤5或者需求點不可抵達(dá)”，由無人機配送，無人機數(shù)量-1，貨車路徑序列刪除該需求點，直接指向下一個需求點；當(dāng)“貨物質(zhì)量m＞5并且需求點可抵達(dá)”，由貨車配送，貨車路徑序列不變。

2）回收無人機。貨車配備了兩架無人機。遍歷最短路徑序列S，通過判定條件，當(dāng)遇到一個無人機的配送點，貨車前往下一個配送點進(jìn)行回收。當(dāng)遇到連續(xù)兩個無人機的配送點，無人機的數(shù)量等于0之后，貨車前往第3個配送點進(jìn)行回收。當(dāng)遇到3個以上的配送點，貨車在原地等待回收無人機，無人機數(shù)量大于0后，繼續(xù)遍歷剩余的路徑序列。

由a，b可獲取貨車最終的配送路徑序列S1，以及無人機多段的路徑序列F1。

3.4? 符號說明

N表示總共需要配送的需求點；Dij表示第i個需求點和第j個需求點之間的距離；S表示初始貨車最短路徑序列；S1表示貨車路徑序列節(jié)點；S2表示每次退火產(chǎn)生的新解的路徑序列；tk表示遇到無人機配送點時的配送時間；Ti表示遇到貨車配送點時的配送時間；T表示當(dāng)前退火溫度；t總耗費的時間。

3.5? 模型建立

目標(biāo)函數(shù)：

（1）

約束函數(shù)：

（2）

式（2）分配不可達(dá)需求點。一共有N個節(jié)點，貨車從起始節(jié)點發(fā)，對所有配送的需求點N-1進(jìn)行配送；隨機個貨車無法抵達(dá)的需求點，來模擬農(nóng)村貨車無法送達(dá)的情況；剩余需求點根據(jù)貨物重量進(jìn)行分配。

（3）

式（3）每次退火/迭代后舊解的路程減去新解的路程，計算兩者的差值，在此基礎(chǔ)上判斷是否接收新解。

（4）

由式（4）可得對于當(dāng)前溫度，根據(jù)Metropolis準(zhǔn)則，計算接收新解的概率大小P，當(dāng)大于一定0～1的隨機數(shù)時，判定為接受新解。

4? 求解算法與算例分析

4.1? 算法分析

本文的最佳路徑規(guī)劃采用“模擬退火”算法進(jìn)行規(guī)劃。

先設(shè)置一個“初始溫度T0”，和一個“目的溫度Tend”，每次while循環(huán)中，T0縮小10%，直到T0小于Tend終止循環(huán)。（本案例設(shè)定的while循環(huán)，約140次）

while循環(huán)中，嵌套一個循環(huán)100次的for循環(huán)，for循環(huán)內(nèi)，是針對當(dāng)前的溫度T0，隨機生成一個新的路線方案，并判斷在多大程度上接受此方案。

通過函數(shù)Newanswer（S1）生成新方案，函數(shù)Metropolis（S1，S2，D，T0）判斷接受程度。前者每次隨機交換舊路徑S1中，兩個城市序號的位置，獲得一個新路徑；后者比較新老方案，S2和S1兩者的總路程長度，如果新方案的總長度小于舊方案，接受新方案，否則考慮新方案的“可接受程度”，D是記錄了各個城市之間距離的一個二維矩陣。

可接受程度，用e^（-新舊路徑差值/ T0）是否≥一個0～1的隨機數(shù)表示，不小于則接受。這是為了避免陷入“局部最優(yōu)解”，如一個問題要到達(dá)global點，但系統(tǒng)到達(dá)了local點后，local點是“局部的最優(yōu)解”，系統(tǒng)可能無法進(jìn)一步找到真正的全局最優(yōu)解。

所以要考慮接受一個“結(jié)果看似不正確”，但“解題方向正確”的答案，避免陷入局部最優(yōu)解的問題。之所以在一個T0中，嵌套for循環(huán)多次，因為在越高的溫度下，接受新方案的概率越高；出錯的概率就比同樣的溫度下for只執(zhí)行一次要小很多。

生成了最優(yōu)的總體路徑后，針對貨物重量，分派汽車和無人機分別進(jìn)行配送；其中，無人機又分為A、B無人機。

送貨點采用汽車或無人機的依據(jù)是“貨物重量”，隨機生成一個長度與配送點總個數(shù)相同的零矩陣，生成0～10的隨機數(shù)，依次代表當(dāng)前路徑方案順序下，每個點要配送的貨物重量。

貨物重量為0～5時，用無人機配送。設(shè)置無人機飛行矩陣Fj，F(xiàn)j置1，表示“該點需要無人機”；同時，在代表汽車路徑的S1中，將不需要汽車配送的點置為0，并后續(xù)刪除。提前保留原本S1的完整序列到S0中，后續(xù)會使用到。

針對無人機配送，可以分為3種“case”，一個“F1”，五個“分支”。通過Fj判斷需要無人機配送的點及其具體的“case”和“分支”，F(xiàn)1行數(shù)是無人機配送次數(shù)，三列分別表示“起點”“配送目的”“回收點”。

五個“分支”以及三個“case”如下：當(dāng)遇到最后一個“終點”要配送時，F(xiàn)1起點和回收點同為“前一個點”，配送目的為“當(dāng)前點”；記為“case1”，表示會用到1架無人機。當(dāng)遇到最后兩個點，含“終點”要配送時，F(xiàn)1起點和回收點同為“前一個點”，配送目的為“當(dāng)前點”和“下以個點”；記為兩次“case2”，表示會用到2架無人機。當(dāng)遇到下一個“非終點”要配送，且再下一個點不需要時，F(xiàn)1起點、配送目的、回收點依次為“前一個點”“當(dāng)前點”“下一個點”；記為“case1”，表示會用到1架無人機。當(dāng)遇到連續(xù)兩個“非終點”要配送時，F(xiàn)1起點、兩個配送目的、回收點依次為“前一個點”“當(dāng)前點”“下一個點”“下下個點”；記為兩次“case2”，表示會用到2架無人機。當(dāng)遇到連續(xù)三個“非終點”要配送時，F(xiàn)1起點和回收點同為“當(dāng)前點”，所有配送目的為“下一個點”；記為“case3”，表示會用到多架無人機，需要累加。

三種case，所代表派送無人機的情況，用于計算時間；case1和case2汽車和一架或兩架無人機同時行動，選擇其中消耗時間最長的那一趟，case3需要汽車在原地等待，需要將無人機所經(jīng)過的路程進(jìn)行累加并計算時間。

由于有兩架無人機，需要分離A、B無人機。主要方案是，當(dāng)遇到第一、第二個點是，默認(rèn)依次分配給A、B無人機，每次結(jié)束，計算A、B無人機“所經(jīng)過的距離之和”，分別記錄distance_A/B兩個矩陣，若不配送，這當(dāng)前點內(nèi)容為0；后續(xù)優(yōu)先分配給所經(jīng)過路徑總和少無人機。

A_go_x，A_end_x，A_go_y，A_end_y，B_go_x，B_end_x，B_go_y，B_end_y，用于記錄A、B兩架無人機的所有路徑，便于作畫。go表示本架無人機所有從“起點”到“配送目的”的“起點”，和所有從“配送目的”到“回收點”的“配送目的”；end表示本架無人機所有從“起點”到“配送目的”的“配送目的”，和所有從“配送目的”到“回收點”的“回收點”。根據(jù)記錄了無人機配送的矩陣F1對應(yīng)的行列數(shù)，依次讀入信息。

4.2? 算例分析

列舉本案例，虛構(gòu)了序號為1～16的，16個不同X-Y坐標(biāo)的點，其中1為起點，默認(rèn)為出發(fā)的倉庫，最后一個點為終點，其余為非終點的配送點。首先隨機生成一個圖3方案路徑，經(jīng)過近10 000次迭代以后，計算出最終方案圖4（以分離A、B無人機和汽車），迭代過程圖如圖5所示。

接下來隨機賦予除起點以外，所有點一定重量的貨物，本次舉例中，6、14、13、9、11、8，貨物重量不大于5，需要無人機配送貨物；剩余的點，1是起點，10是終點，都無須配送；2、3、4、5、7、12、15、16是汽車配送點。表1是無人機是否需要配送的矩陣，若為1則表示需要，0則不需要；表2是總體的最佳序列；表3是汽車的最終路徑。

獲得了總體方案以后，接下來分離A、B無人機；并記錄各個無人機配送點的“配送情況”即case。三種case，所代表派送無人機的情況，用于計算時間；case1和case2汽車和一架或兩架無人機同時行動，選擇其中消耗時間最長的那一趟，case3需要汽車在原地等待，需要將無人機所經(jīng)過的路程進(jìn)行累加并計算時間。表4是無人機的總路徑表格，從左到右分別為起點、配送目的、終點。

表5表示所有使用到1架無人機的點，從左到右分別為起點、配送目的、終點；

表6表示所有使用到2架無人機的點，從左到右分別為起點、配送目的、終點；

case3為空。

記錄和分離A、B無人機，遇到的第一個、第二個點默認(rèn)賦予A、B無人機，剩下的，優(yōu)先賦予此前所經(jīng)過距離之和最小的無人機。表7是A、B無人機對應(yīng)無人機序列中，每次經(jīng)過點，以及所配送的路程，0則表示該點未使用此架無人機。

分離以后，記錄A、B的相關(guān)坐標(biāo)數(shù)據(jù)——A_go_x，A_end_x，A_go_y，A_end_y，B_go_x，B_end_x，B_go_y，B_end_y，用于記錄A、B兩架無人機的所有路徑，便于作畫。go表示本架無人機所有從“起點”到“配送目的”的“起點”，和所有從“配送目的”到“回收點”的“配送目的”；end表示本架無人機所有從“起點”到“配送目的”的“配送目的”，和所有從“配送目的”到“回收點”的“回收點”。

表8依次記錄了：A無人機的所有起點的x坐標(biāo)，A無人機的所有起點的y坐標(biāo)，A無人機的所有終點的x坐標(biāo)，A無人機的所有終點的y坐標(biāo)；表9依次記錄了：B無人機的所有起點的x坐標(biāo)，B無人機的所有起點的y坐標(biāo)，B無人機的所有終點的x坐標(biāo)，B無人機的所有終點的y坐標(biāo)。

本案例的最終結(jié)果，初始路徑總長度為581.222，最終路徑長度為257.643 8。其中汽車配送距離為215.53，無人機配送距離為334.221，汽車和無人機的速度默認(rèn)為40、30 km/h，汽車和無人機的總時間分別為5.388 2和11.140 7；根據(jù)case1、2、3進(jìn)行計算以后，綜合時間為12.315 1。

這其中，汽車和無人機的速度默認(rèn)為40、30 km/h。

設(shè)想一個對比的場景，及將A、B無人機配送改成駕駛員停下汽車以后，騎乘小電動車，以20 km/h配送。由于需要停車，即只能累加，下列額外計算小車配送的時間。額外的10個案例如表11所示，但只展示最終結(jié)果。

可見“汽車+無人機”方案中，汽車和無人機可以同時工作，且無人機速度快于小車；在時間效率方面，明顯優(yōu)于傳統(tǒng)的“汽車+小車”模式。

5? 結(jié)? 論

本文主要就如今農(nóng)村物流與末端配送發(fā)展現(xiàn)狀和無人機車輛聯(lián)合配送模式研究現(xiàn)狀。發(fā)現(xiàn)農(nóng)村物流的末端基礎(chǔ)設(shè)施不完善，有的農(nóng)村地區(qū)至今未修建水泥公路，群眾出行十分不便。并且大多地形分散，難以建立比較集中的倉庫作為中轉(zhuǎn)站。有的雖已基本實現(xiàn)村村同公路，但通常存在多小路/多岔路，導(dǎo)致車輛無法運送困難。從這一角度，無人機可以發(fā)揮巨大的作用。

而對無人機配送模式的主要研究方向有無人機與車輛組合模式、無人機與無人柜組合模式、無人機與無人倉組合模式。本文進(jìn)一步分析了無人機與車輛的組合模式，選擇車輛與無人機協(xié)同配送的組合模式。對路徑規(guī)劃方面，目前對于“無人機-車輛”聯(lián)合配送的研究主要分為兩類。一類是基于TSP問題不斷改進(jìn)（比如考慮到無人機需要在倉庫或客戶點取貨/送貨）；另一類是基于VRP問題，延伸出考慮續(xù)航問題的VRP-D等。這兩類都是先確定車輛的路徑，之后再對無人機的路徑進(jìn)行規(guī)劃。據(jù)此，本文建立了無人機和車輛的聯(lián)合配送模型，并利用模擬退火算法進(jìn)行路徑的規(guī)劃，以取得總配送時間最小的結(jié)果。通過與傳統(tǒng)的“車輛”加“小車”的配送模式對比，并多次比較，顯示出無人機車輛聯(lián)合配送的效率明顯更優(yōu)。

參考文獻(xiàn)：

[1] 趙怡潔，楊麗莎.農(nóng)村寄遞物流體系建設(shè)背景下末端配送的優(yōu)化路徑 [J].物流科技，2022，45（7）：54-56.

[2] 曹玉姣.鄉(xiāng)村振興背景下湖北農(nóng)村電商物流發(fā)展研究 [J].當(dāng)代經(jīng)濟(jì)，2022，39（9）：66-71.

[3] 楊捷.農(nóng)村鄉(xiāng)鎮(zhèn)物流末端配送現(xiàn)狀分析和建議 [J].中小企業(yè)管理與科技：上旬刊，2021（12）：115-117.

[4] 曹珺雯，佟京昊，曹雁林. 國內(nèi)物流無人機配送體系模 式研究 [J].中國物流與采購，2018（14）：72-73.

[5] 任新惠，王柳，鄒心彤.基于多因素的城市即時配送創(chuàng)新模式研究 [J].商業(yè)經(jīng)濟(jì)研究，2020（11）：133-136.

[6] 任璇，黃輝，于少偉，等.車輛與無人機組合配送研究綜述 [J].控制與決策，2021，36（10）：2313-2327.

[7] MURRAY C C，CHU A G. The flying sidekick traveling salesman problem： Optimization of drone-assisted parcel delivery [J].Transportation Research Part C： Emerging Technologies，2015，54： 86-109.

[8] AGATZ N，BOUMAN P，SCHMIDT M. Optimization approaches for the traveling salesman problem with drone [J].Transportation Science，2018，52（4）： 965-981.

[9] YUREK E E，OZMUTLU H C. A decomposition-based iterative optimization algorithm for traveling salesman problem with drone [J].Transportation Research Part C： Emerging Technologies，2018，91： 249-262.

[10] KITJACHAROENCHAI P，VENTRESCA M，LEE S，et al. Multiple traveling salesman problem with drones：? Mathematical model and heuristic approach [J].Computers & Industrial Engineering，2019，129： 14-30.

[11] 武勝良.農(nóng)村電商物流“最后一公里”無人機配送應(yīng)用對策研究 [J].物流科技，2022，45（8）：61-63.

作者簡介：吳杭軒（2001—），男，漢族，四川綿陽人，本科在讀，研究方向：計算機科學(xué)與技術(shù)；通訊作者：張翠平（1984—），女，漢族，河南南陽人，講師，博士，主要研究方向：計算機應(yīng)用技術(shù)、大數(shù)據(jù)與智能交通；傅聿焯（2001—），男，漢族，福建南平人，本科在讀，研究方向：計算機科學(xué)與技術(shù)；王子宇（2001—），男，漢族，黑龍江綏化人，本科在讀，研究方向：計算機科學(xué)與技術(shù)。