貨車聯合無人機的農村電商物流運輸路徑規劃

褚衍昌，王雪婷，張 娜

（1.中國民航大學 經濟與管理學院，天津 300300；2.石河子大學 經濟與管理學院，新疆 石河子 832000）

1 引言

隨著信息技術日趨成熟，農村電商快速發展，帶動物流業發生了翻天覆地的變化。2019年農村網絡零售額達1.7萬億元，同比增長19.1%；全國快遞企業業務量累計達到635.2 億件，同比增長25.3%。“互聯網+”背景下，電商與物流是協同發展、共生共榮的復雜關系，但目前物流發展速度與電商發展速度不匹配，特別是農村電商物流與農村電商市場的發展不適應。農村物流末端配送具有客戶點分散、單位面積物流需求量小、交通道路條件差等特點，使農村電商末端物流陷入“長物流鏈+低消費密度”的困境，面臨“最初一公里”攬件和“最后一公里”配送難題[1-2]。

無人機具有能耗小、飛行速度快、可直線飛行、不受地面交通條件和地形的限制等優點[3]。因此無人機配送可降低物流配送成本和運輸時間，使其在物流配送中的應用越來越廣泛。國內外大型電商物流企業如亞馬遜、DHL、順豐、京東紛紛開展了末端物流無人機的研究和應用[4]。2020 年初爆發的新冠肺炎由于具有強大傳染性，使得無接觸配送受到了人們的廣泛關注，促進了前沿末端物流配送工具如無人機、無人機車和配送機器人等的推廣應用。民航局也下發通知為通用航空提供政策支持，并進一步推動了無人機在物流配送中的應用。但是由于無人機具有載重小、續航能力短等缺點，使得無人機不適合運輸載重大、航程遠的包裹。因此將無人機與貨車結合起來進行物流運輸，可以用貨車載重大、運距遠的優點彌補無人機的缺點[5]。

無人機和貨車合作的運行模式分為四種，分別為無人機輔助貨車運行、貨車輔助無人機運行、無人機和貨車獨立運行、無人機和貨車同步運行[6]。目前關于貨車輔助無人機運行模式以及無人機和貨車同步運行模式的研究較多。Murray 等[7]提出的無人機旅行商問題（traveling salesman problem with drone,TSPD）是較早關于無人機與貨車合作進行物流配送的研究，采用無人機和貨車同步運行的模式，研究目標是使配送時間最短。Ha 等[8]也進行了無人機和貨車同步運行模式的研究，其研究目標是配送總成本最小，其中包括無人機和貨車的等待成本。Chang等[9]研究了以時間最短為目標的貨車輔助無人機的運行模式。林驛等[10]針對我國農村實際情況，提出城鄉客運班車輔助無人機的配送模式，并加入客運班車的時間窗約束。隨著電商和物流的發展，客戶退換貨需求越來越多，形成逆向物流，同時取送貨的車輛路徑問題逐漸受到廣大學者的關注。周永等[11]研究了冷鏈物流同時送取貨車輛路徑優化問題。Karak等[12]研究了貨車和無人機合作的同時取送貨的車輛路徑問題。段鳳華[13]研究了帶碳費約束的同時取送貨車輛路徑問題。現代人對于時間的管控更加嚴格，往往希望包裹能在時間方便時送達，針對此問題，有關帶時間窗約束的車輛路徑研究不斷發展[14-16]。

但是已有研究主要針對卡車的同時取送貨和帶時間窗的車輛路徑問題，本文在前人研究的基礎上提出貨車聯合無人機的同時取送貨和帶軟時間窗的車輛路徑問題（Drone-Vehicle Routing Problem with Simultaneous Pickup-Delivery and Soft Time Windows，DVRPSPDSTW）。以末端物流運作總成本最小為研究目標，建立數學約束模型，采用遺傳算法求解，以期解決農村電商物流面臨的“最初一公里”攬件和“最后一公里”配送難題。

2 問題描述

貨車聯合無人機的同時取送貨和帶軟時間窗的車輛路徑問題（DVRPSPDSTW）描述如下：一個配送中心有多輛同車型貨車和一架無人機為所負責區域的客戶提供送貨和取貨服務，本文研究的是貨車和無人機獨立運行的模式，貨車負責配送或收取運距遠、質量重的包裹，無人機負責配送或收取運距短、質量輕的包裹，如圖1所示。客戶對于服務時間區域有一定要求，如果客戶在要求的時間區域內被服務，客戶將會對服務時間很滿意，如果早于或者晚于要求的服務時間，客戶可以接受服務，但物流企業需要接受一定的經濟懲罰。DVRPSPDSTW的研究目的是如何使物流企業在“最初一公里”和“最后一公里”的運作總成本最低，運作總成本包括貨車司機的人工成本、貨車和無人機的運輸成本以及時間窗懲罰成本。

3 模型構建

3.1 模型的一般假設

本文對DVRPSPDSTW問題進行如下假設：

（1）只有一個配送中心；

（2）有多個貨車和一架無人機；

（3）貨車采用同一車型；

（4）同一客戶點，要先執行送貨任務，再執行取貨任務；

圖1 貨車聯合無人機的運行模式

（5）送貨和取貨任務提前獲知，不發生變更；

（6）不考慮貨物體積因素；

（7）貨車和無人機均勻速運行；

（8）配送貨物和收取貨物可以混裝；

（9）采用更換鋰電池方法解決無人機鋰電池儲能小的問題，所以充電時間忽略不計。

3.2 模型的參數設置

首先定義如下符號：

N={1,2,...,n}表示所有的客戶節點；

N0={0,1,...,n}表示所有的出發節點；

N+={1,2,...,n+1}表示所有的到達節點；

V表示配送車輛集合，V=1,2,...,m；

D表示無人機航次集合，D=1,2,...,k；

dij表示客戶i到客戶j的路線距離；

lij表示客戶i到客戶j的飛行距離；

Qv表示車輛的最大載重；

Qd表示無人機的最大載重；

Dv表示車輛的最大行駛里程；

Dd表示無人機的最大航程；

Vv表示車輛的平均行駛速度；

Vd表示無人機的平均飛行速度；

ch表示單位時間人工成本；

bij表示車輛由客戶i行駛至客j每公里產生的費用；

cij表示無人機由客戶i飛行至客戶j每公里產生的費用；

qi表示客戶i的送貨量；

pi表示客戶i的取貨量；

ai表示客戶i約定的最早服務時間；

bi表示客戶i約定的最晚服務時間；

qij表示運輸工具從客戶i到客戶j時還需要配送的貨物重量；

pij表示運輸工具從客戶i到客戶j時已經收取的貨物重量；

α1表示運輸工具在ai之前到達客戶i處開始服務的懲罰系數；

α2表示運輸工具在bi之后到達客戶i處開始服務的懲罰系數；

3.3 模型建立

根據以上符號和變量，貨車聯合無人機的農村電商物流運輸路徑規劃問題可表示為如下模型：

式（1）是目標函數，表示最小化成本；式（2）表示貨車從配送站出發并回到配送站；式（3）表示無人機從配送站出發并回到配送站；式（4）表示客戶僅被訪問一次；式（5）表示貨車的裝貨總量不超過貨車最大載重；式（6）表示無人機的裝貨總量不超過無人機的最大載重；式（7）表示送貨量等于客戶需要收貨量的總和；式（8）表示取貨量等于客戶需要寄貨量的總和；式（9）表示第v 輛貨車行駛距離小于貨車最大行駛里程；式（10）表示無人機飛行距離小于無人機最大航程；式（11）-式（14）表示貨車和無人機的服務時間窗；式（15）-式（16）表示決策變量的取值范圍。

4 算法設計

本文研究的DVRPSPDSTW 問題是傳統VRP 問題的變體，對于這類NP-hard 問題，一般方法較難求解，由于遺傳算法具有高效、魯棒性強、不容易陷入局部最優等優點，所以本文采用遺傳算法求解。遺傳算法運算流程如圖2所示。

4.1 染色體編碼

圖2 遺傳算法流程圖

遺傳算法不能直接對問題參數進行處理，需要將這些參數轉換成遺傳算法可以識別的個體或者是染色體，這一過程稱為編碼。常用的編碼方法包括二進制編碼、浮點編碼、自然數編碼等。本文使用自然數編碼，配送中心的編號是“0”，顧客編號是1-n的自然數，如染色體“05304210”表明有兩條配送路線，分別是配送中心-客戶5-客戶3-配送中心；配送中心-客戶4-客戶2-客戶1-配送中心。

4.2 初始化種群

初始化種群在遺傳算法求解過程中扮演著重要的角色，種群規模大小會對遺傳算法最終的運行結果以及運行效率產生重大影響。在種群規模較小時，會影響遺傳算法的優化性能，一般情況下不太好，種群規模較大時可以降低算法陷入局部最優的概率，但是計算復雜程度和運行時間會增加。染色體長度不是很大時，種群規模的大小在10～200之間，對于比較復雜的問題，可根據具體情況適當增加種群規模。

4.3 適應度計算

適應度即種群中個體適應環境的能力，適應度值越大代表個體適應環境的能力越強，適應度函數的評價是選擇操作的依據，它的設計會對遺傳算法性能產生影響。本文的目標函數是成本最小，故適應度函數為目標函數的倒數。

4.4 選擇操作

選擇的目的是淘汰劣質個體，選擇優質個體，本文采用輪盤賭選擇法，其表達式為：

式中：fi為單個個體的適應度，NP 為種群規模。個體適應度值越大，被選擇的概率越大，優質個體基因遺傳到下一代的機會越大。

4.5 交叉操作

本文采用兩點交叉法，從父代選擇兩個染色體，從每條染色體中選擇兩個點作為交叉點，將兩條染色體對應位置交叉點的字符串交換，便可得到兩個子代染色體。

4.6 變異操作

變異操作是模仿生物進化中基因突變的現象，從種群中選擇若干個體，改變個體中的某些基因值，變異的概率一般很小，取值范圍為0.001～0.1，如果變異率太大，會破環優質個體。

5 算例分析

5.1 算例數據

目前，無人機的優勢在偏遠農村地區能夠得到更好體現，因此選擇貴州省某農村地區作為本文貨車聯合無人機運輸模式的研究地區，本區域有2輛貨車和一架無人機，為20 個客戶提供送貨或者取貨服務。具體模型參數見表1。

表1 模型參數

通過百度地圖測得貨車行駛距離以及無人機飛行距離，無人機飛行距離采用兩點之間的直線距離，各個客戶點的取貨量、送貨量以及時間窗隨機生成，配送時間設置為早上九點至下午五點，以min 計算，早上九點設為0min,下午五點設為480min。貨車行駛距離見表2，無人機飛行距離見表3，取送貨信息見表4。

5.2 MATLAB求解

本文采用MATLAB R2019b軟件進行編程，其中種群規模設為200，最大迭代次數設為300，交叉概率為0.9，變異概率為0.1。迭代55次時算法收斂，遺傳算法的迭代情況如圖3所示。

經過多次程序運行，貨車聯合無人機的運輸路徑規劃結果見表5，求得最低總成本為1 995.73 元，無人機服務對象為載重和航程在其承受范圍之內的客戶，剩余客戶由貨車負責服務。大部分服務時間都在客戶要求的時間窗范圍內，極大地提升了客戶服務水平，并在配送過程中完成取貨任務。以上結果表明DVRPSPDSTW 模式能夠在物流運輸中應用并有效完成運輸任務。

表2 配送站與各客戶點以及各客戶點之間的貨車行駛距離

表3 配送站與各客戶點以及各客戶點之間的無人機飛行距離

表4 顧客取送貨信息

圖3 目標函數迭代次數

表5 DVRPSPDSTW運輸路徑規劃結果

為了表明DVRPSPDSTW 運輸方式的優越性，本文對單獨使用貨車運輸的方式進行求解，貨車運輸路徑規劃結果見表6。

表6 VRPSPDSTW運輸路徑規劃結果

通過對比表5和表6的求解結果，可知僅使用貨車運輸的最低總成本為2 614.05元，而DVRPSPDSTW模式最低總成本為1 995.73 元，相比只使用貨車運輸成本降低了23.65%。這表明無人機在物流運輸方面有很大的優越性，“貨車+無人機”的運輸方式可有效降低物流運輸成本。

不同區域的客戶對于物流服務品質的要求會有一些差別，經濟發達地區的客戶對配送時間的敏感程度較高，經濟較差地區的客戶對配送時間窗的容忍程度較大。本文針對客戶對配送時間敏感程度的不同，從農村電商物流利潤最大化的角度出發，對時間敏感程度較低地區的客戶，可以將提供時間窗約束的服務去掉，降低物流企業成本。不考慮時間窗約束的“貨車+無人機”運輸路徑規劃結果見表7。

表7 DVRPSPD運輸路徑規劃結果

時間窗約束在運輸路徑規劃中會產生很大影響，通過對比表5 和表7 的求解結果可知，不考慮時間窗約束的成本為1 677.57元，無人機飛行航次減少為3 次，成本降低了15.94%。故從利潤最大化角度考慮，針對不同地區的客戶，可采用不同的運輸模式。

為了研究不同無人機載重對本文所提出運輸模式成本的影響，對3-13kg 不同無人機載重的運輸模型進行求解，模型運行結果見表8，結果表明無人機載重為9kg 時運輸總成本最小。這啟示物流企業在購買或者租賃末端物流無人機時，可根據用戶需求量選擇合適載重的無人機型號，有效降低末端物流運作總成本。

表8 不同無人機載重的運輸規劃結果

6 結語

本文分析了農村電商物流面臨“最初一公里”攬件和“最后一公里”配送成本高的難題，并針對該問題提出了一種新的末端物流運輸模式，即貨車聯合無人機的同時取送貨和帶軟時間窗問題（DVRPSPDSTW）的運輸模式。以末端物流運作總成本最小為目標建立數學模型，采用遺傳算法求解，結果表明DVRPSPDSTW 模式可以有效完成物流運輸任務，和傳統的貨車運輸模式相比，該模式能夠有效降低物流運作總成本。末端物流成本高一直是困擾物流企業向下延伸服務的難題，本文提出的運輸模式顯著降低了末端物流成本，為物流企業進一步拓展農村市場提供了解決方案。雖然本文對農村電商物流面臨的難題提出了一種新的解決方案，但是只考慮了在時間窗約束和同時取送貨情況下貨車和無人機獨立運行的一種模式，未來可考慮貨車和無人機合作的其他模式，應對多種末端物流運輸情境。