褚衍昌，王雪婷，張 娜

（1.中國民航大學(xué) 經(jīng)濟(jì)與管理學(xué)院，天津 300300；2.石河子大學(xué) 經(jīng)濟(jì)與管理學(xué)院，新疆 石河子 832000）

1 引言

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

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

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

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

2 問題描述

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

3 模型構(gòu)建

3.1 模型的一般假設(shè)

本文對DVRPSPDSTW問題進(jìn)行如下假設(shè)：

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

（2）有多個貨車和一架無人機(jī)；

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

（4）同一客戶點(diǎn)，要先執(zhí)行送貨任務(wù)，再執(zhí)行取貨任務(wù)；

圖1 貨車聯(lián)合無人機(jī)的運(yùn)行模式

（5）送貨和取貨任務(wù)提前獲知，不發(fā)生變更；

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

（7）貨車和無人機(jī)均勻速運(yùn)行；

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

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

3.2 模型的參數(shù)設(shè)置

首先定義如下符號：

N={1,2,...,n}表示所有的客戶節(jié)點(diǎn)；

N0={0,1,...,n}表示所有的出發(fā)節(jié)點(diǎn)；

N+={1,2,...,n+1}表示所有的到達(dá)節(jié)點(diǎn)；

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

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

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

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

Qv表示車輛的最大載重；

Qd表示無人機(jī)的最大載重；

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

Dd表示無人機(jī)的最大航程；

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

Vd表示無人機(jī)的平均飛行速度；

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

bij表示車輛由客戶i行駛至客j每公里產(chǎn)生的費(fèi)用；

cij表示無人機(jī)由客戶i飛行至客戶j每公里產(chǎn)生的費(fèi)用；

qi表示客戶i的送貨量；

pi表示客戶i的取貨量；

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

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

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

pij表示運(yùn)輸工具從客戶i到客戶j時已經(jīng)收取的貨物重量；

α1表示運(yùn)輸工具在ai之前到達(dá)客戶i處開始服務(wù)的懲罰系數(shù)；

α2表示運(yùn)輸工具在bi之后到達(dá)客戶i處開始服務(wù)的懲罰系數(shù)；

3.3 模型建立

根據(jù)以上符號和變量，貨車聯(lián)合無人機(jī)的農(nóng)村電商物流運(yùn)輸路徑規(guī)劃問題可表示為如下模型：

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

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

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

4.1 染色體編碼

圖2 遺傳算法流程圖

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

4.2 初始化種群

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

4.3 適應(yīng)度計(jì)算

適應(yīng)度即種群中個體適應(yīng)環(huán)境的能力，適應(yīng)度值越大代表個體適應(yīng)環(huán)境的能力越強(qiáng)，適應(yīng)度函數(shù)的評價是選擇操作的依據(jù)，它的設(shè)計(jì)會對遺傳算法性能產(chǎn)生影響。本文的目標(biāo)函數(shù)是成本最小，故適應(yīng)度函數(shù)為目標(biāo)函數(shù)的倒數(shù)。

4.4 選擇操作

選擇的目的是淘汰劣質(zhì)個體，選擇優(yōu)質(zhì)個體，本文采用輪盤賭選擇法，其表達(dá)式為：

式中：fi為單個個體的適應(yīng)度，NP 為種群規(guī)模。個體適應(yīng)度值越大，被選擇的概率越大，優(yōu)質(zhì)個體基因遺傳到下一代的機(jī)會越大。

4.5 交叉操作

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

4.6 變異操作

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

5 算例分析

5.1 算例數(shù)據(jù)

目前，無人機(jī)的優(yōu)勢在偏遠(yuǎn)農(nóng)村地區(qū)能夠得到更好體現(xiàn)，因此選擇貴州省某農(nóng)村地區(qū)作為本文貨車聯(lián)合無人機(jī)運(yùn)輸模式的研究地區(qū)，本區(qū)域有2輛貨車和一架無人機(jī)，為20 個客戶提供送貨或者取貨服務(wù)。具體模型參數(shù)見表1。

表1 模型參數(shù)

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

5.2 MATLAB求解

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

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

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

表3 配送站與各客戶點(diǎn)以及各客戶點(diǎn)之間的無人機(jī)飛行距離

表4 顧客取送貨信息

圖3 目標(biāo)函數(shù)迭代次數(shù)

表5 DVRPSPDSTW運(yùn)輸路徑規(guī)劃結(jié)果

為了表明DVRPSPDSTW 運(yùn)輸方式的優(yōu)越性，本文對單獨(dú)使用貨車運(yùn)輸?shù)姆绞竭M(jìn)行求解，貨車運(yùn)輸路徑規(guī)劃結(jié)果見表6。

表6 VRPSPDSTW運(yùn)輸路徑規(guī)劃結(jié)果

通過對比表5和表6的求解結(jié)果，可知僅使用貨車運(yùn)輸?shù)淖畹涂偝杀緸? 614.05元，而DVRPSPDSTW模式最低總成本為1 995.73 元，相比只使用貨車運(yùn)輸成本降低了23.65%。這表明無人機(jī)在物流運(yùn)輸方面有很大的優(yōu)越性，“貨車+無人機(jī)”的運(yùn)輸方式可有效降低物流運(yùn)輸成本。

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

表7 DVRPSPD運(yùn)輸路徑規(guī)劃結(jié)果

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

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

表8 不同無人機(jī)載重的運(yùn)輸規(guī)劃結(jié)果

6 結(jié)語

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