基于卡車與無人機聯(lián)合配送的車輛路徑優(yōu)化

劉艷秋，段聰

(1.沈陽工業(yè)大學 管理學院，遼寧 沈陽，110870；2.沈陽工業(yè)大學 理學院，遼寧 沈陽，110870)

隨著科學技術的不斷發(fā)展，無人機在各個領域的廣泛應用為它在物流領域的發(fā)展提供了新的突破口。對比于傳統(tǒng)卡車運輸，無人機不受地面交通的影響，可以有效提升配送效率。且無人機配送存在小批量、高頻次等特點，也更適合物流末端的配送[1]。但由于無人機飛行受到載重以及飛行耐力的約束[2-3]，因此,可將裝載無人機的卡車(下文均以卡車代替)作為無人機的發(fā)射與回收節(jié)點，二者聯(lián)合進行配送可以有效規(guī)避卡車配送路徑受限以及無人機飛行受載重以及飛行耐力的約束，使之能夠進行高效的配送。

國內外學者對卡車與無人機聯(lián)合配送下的車輛路徑問題(vehicle routing problem with drone，VRP-D)展開了廣泛研究。MURRAY等[4]最先提出了一輛卡車搭載一架無人機合作分發(fā)包裹的問題(FSTSP)，并設計了混合整數(shù)線性規(guī)劃公式，設計了兩種啟發(fā)式算法對小規(guī)模實例進行求解。AGATZ等[5]在此基礎上構建了帶有無人機的旅行售貨員問題(travelling salesman problem，TSP-D)的整數(shù)線性規(guī)劃模型，并將所提出的啟發(fā)式算法應用于不同規(guī)模大小的實例中。HA等[6]提出了關于TSP-D的一個新的問題——最小成本TSP-D，設計了兩種啟發(fā)式算法并進行了對比實驗。LI等[7]研究了帶有時間窗和移動衛(wèi)星的兩級車輛路徑問題，以綜合成本最小化為目標，研究了多車輛與無人機的問題，運用自適應大規(guī)模鄰域搜索算法分別對小規(guī)模和大規(guī)模算例進行求解。

綜上可知：相關路徑文獻為了簡化問題，在構建模型方面考慮的要素比較單一，導致忽略了一些現(xiàn)實的因素。將無人機與卡車聯(lián)合配送模式應用于取送貨問題的文獻暫沒有，而在真實的物流網(wǎng)絡中，考慮在送貨過程中完成取貨任務，比傳統(tǒng)不考慮取貨過程的問題更具有實用性。且在車輛路徑優(yōu)化問題中，考慮正向物流和逆向物流的整合成為企業(yè)提升效率和降低成本的重要途徑[8]。鑒于這種情況，在基于運籌學和智能優(yōu)化算法的基礎上，建立了考慮客戶的取送貨需求混合整數(shù)規(guī)劃模型，并設計嵌入遺傳算法的鄰域搜索算法對模型進行求解。在規(guī)劃如何將客戶的取貨需求與送貨需求有效地分配給無人機與卡車的同時，進行車輛路徑優(yōu)化。最后，將模型與算法應用于算例進行分析驗證，為相關企業(yè)提供理論依據(jù)及解決思路。

1 問題描述與模型建立

1.1 問題描述與模型分析

某地區(qū)有已知取送貨需求的n個客戶點，采用卡車攜帶小型無人機聯(lián)合配送的方式從配送中心O(也作O')出發(fā)為客戶進行配送，配送模式見圖1，在完成所有客戶服務后返回倉庫O'，使得總配送時間最短。由于某些客戶需求無法由無人機完成(例如超過無人機有效載重的包裹，客戶位置超過無人機飛行最大距離的包裹等)。因此，這樣的客戶僅能由卡車進行服務，其余客戶均能由無人機安排配送。

圖1所示為該配送模式的路徑示意圖，以往研究中，卡車與無人機均需承擔配送任務，卡車在某一客戶點處發(fā)射無人機后停止其配送服務，在該處等待無人機并進行回收。但在實際生活中，存在卡車無法長時間停車和交通堵塞情況，必須盡快前往下一個客戶點，不能在發(fā)射地點等待無人機返回。因此，建立模型時考慮在無人機的服務過程中，使卡車繼續(xù)進行配送任務，并在其后續(xù)節(jié)點將無人機進行回收。

圖1 配送模式Fig.1 The distribution mode

為便于該問題中模型的建立及不失問題的一般性，對模型做出如下假設：1)無人機單次發(fā)射只服務一個客戶；2)客戶節(jié)點需求不可分割；3)無人機僅能從客戶點所在位置處或配送中心位置處發(fā)射，且必須在沿途的后續(xù)客戶點或配送中心處匯合；4)當無人機和卡車在某一客戶點匯合時，較早到達的一個等待另一個[9]；5)不考慮其他影響最大飛行速度的因素，且無人機都以最大飛行速度進行配送。

1.2 參數(shù)定義

定義決策變量如下：xijv表示卡車v從節(jié)點i行駛到j的二元變量;yijku表示無人機u從節(jié)點i處發(fā)射，在結束節(jié)點j處服務后返回到節(jié)點k的二元變量;zuv表示無人機u在卡車v所配送路徑上的二元變量。

1.3 模型構建

卡車與無人機聯(lián)合配送的車輛路徑優(yōu)化模型是使總配送時間最短為目標函數(shù)以及多個約束條件組成。在確定目標時考慮無人機與卡車的速度及其各自的服務時間，各個節(jié)點處車輛與無人機的載重等因素，實現(xiàn)真正可行的目標解。其目標函數(shù)公式如下所示:

mintO'

約束條件為

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

ti+η≤li，?i∈Ctruck

(17)

(18)

(19)

(20)

xijv∈{0,1},?i∈Nleave,j∈Narrive,u∈U

(21)

yijkv∈{0,1},?i∈Nleave,j∈CUAV,k∈Narrive,v∈V

(22)

zuv∈{0,1}，?u∈U,v∈V

(23)

目標函數(shù)表示在滿足卡車與無人機需求和容量限制的同時，通過使用最少數(shù)量的車輛來求解最短完成時間。約束(1)～(6)表示卡車與無人機聯(lián)合配送的基本約束。客戶攬貨和送貨的情況如約束(7)和(8)所示，約束中考慮在卡車路徑上存在無人機服務點的情況。約束(9)～(11)表示卡車與無人機的最大載重約束。約束(12)表示無人機的最大飛行距離約束。約束(13)～(20)表示在配送過程中卡車與無人機的時間連續(xù)性約束。約束(21)～(23)表示決策變量的取值范圍。

2 模型求解

卡車-無人機聯(lián)合配送問題屬于一類NP-hard的VRP變體問題，因此，提出嵌入遺傳算法的鄰域搜索算法來求解該問題。

2.1 客戶分類

由于卡車與無人機容量限制有所不同，且無人機的飛行距離更是限制了無人機所能服務的客戶集合。因此，將客戶分成兩類：1)選取所有客戶中需求量滿足無人機最大載重的客戶，再以最短路徑法計算其與卡車客戶之間所產生的最短飛行距離以及次最短距離，若二者距離之和不大于無人機的最大飛行距離，使該客戶加入到無人機客戶集；2)其余客戶加入到卡車客戶集。

2.2 路徑規(guī)劃

為解決卡車與無人機聯(lián)合配送的路徑規(guī)劃問題，提出一種結合遺傳算法的鄰域搜索算法。在形成初始路徑的情況下，采用無人機回收端鄰域搜索的操作進行路徑優(yōu)化。

首先，針對所有卡車客戶，形成一個帶有取送貨的車輛路徑問題[10]，采用遺傳算法生成初始路徑[11]。在卡車初始路徑形成后，將無人機客戶插入到卡車路徑中形成一個完整的初始解。以搜索卡車路徑上距離無人機客戶最近的節(jié)點作為無人機的發(fā)射節(jié)點，該條卡車子路徑上的下一個節(jié)點作為無人機回收節(jié)點。

其次，進行無人機的回收鄰域搜索。根據(jù)所建立模型特點，無人機既可由同一卡車進行回收，也可由不同路徑上的卡車進行回收。因此，針對無人機的回收客戶點，從該次無人機的起飛節(jié)點到其所在卡車路徑上的最后一個客戶點中隨機選取一客戶點作為該次無人機任務的回收節(jié)點進行鄰域搜索。上述鄰域搜索無法保證新解均為可行解，所以給出以下非可行解的調整策略：1)如果當前卡車路徑的所有位置均不可行，則將回收節(jié)點隨機插入其他卡車路徑中；2)如果針對該無人機所有卡車路徑均無法回收該無人機，則放棄本次局部搜索操作。

3 算例分析

由于缺乏對于該問題的適用算例，故本節(jié)采用Solomon數(shù)據(jù)集中的RC101數(shù)據(jù)，生成25個客戶點的算例1和50個客戶點的算例2，將算例中原有的需求列數(shù)據(jù)作為各節(jié)點取貨量需求，采用隨機生成的方式添加送貨量需求的列數(shù)據(jù)。設置卡車和無人機速度分別為58和80 km/h，卡車與無人機最大載重分別為200和10 kg，無人機最遠工作航程為20 km。由于無人機服務時相較于卡車更加便捷，所以將二者的服務時間設置為5和10 min兩部分。通常來說，由于卡車配送會受到地面交通道路的管束，為簡化模型，選取歐式距離的1.2倍來表示卡車在兩節(jié)點間的行駛距離，見式(24)。而無人機飛行距離并不受地面道路影響，所以采取歐式距離，見式(25)，表示單次無人機進行服務全程的距離，包括無人機發(fā)射節(jié)點與該次所服務的無人機客戶節(jié)點的距離以及無人機客戶節(jié)點與無人機回收節(jié)點之間的距離。

(24)

(25)

算例使用Matlab R2018b進行編程，運行環(huán)境為Windows 10操作系統(tǒng)，處理器為Intel(R) Core(TM) i5-7200U CPU @ 2.50 GHz，2.71 GHz。

3.1 僅卡車配送的配送模式

該模式僅以卡車作為配送工具，在滿足各個節(jié)點處卡車的裝載量不大于最大載量的情況下，從配送中心出發(fā)為客戶進行配送與攬收服務并最終返回配送中心。使綜合時間最短為目標合理規(guī)劃運輸路線，利用遺傳算法求解該問題[12]，將算例中各節(jié)點的待攬收量、待配送量以及各客戶的位置信息代入程序[13]。

實驗結果見表1，兩個實例僅由卡車配送時完成所有客戶服務總配送時間為11.490 6和21.206 4 h。最優(yōu)配送方案路線見圖2。

表1 傳統(tǒng)配送模式下最優(yōu)配送方案Table 1 The optimal distribution scheme at traditional distribution mode

圖2 傳統(tǒng)配送模式下最優(yōu)方案路徑圖Fig.2 Path diagrams of the optimal scheme in traditional distribution mode

3.2 卡車和無人機聯(lián)合配送的配送模式

該模式由卡車攜帶無人機從配送中心出發(fā)為客戶進行配送與攬貨服務并最終返回配送中心。以綜合時間最短為目標合理規(guī)劃運輸路線。利用嵌入遺傳算法的鄰域搜索算法求解該問題，將算例中需求量以及各客戶的位置信息代入程序。

運用嵌入遺傳算法的鄰域搜索算法對2個算例進行實驗，最優(yōu)方案見表2，具體數(shù)據(jù)見表3和表4，最優(yōu)配送方案路線見圖3。2個實例由卡車與無人機聯(lián)合配送時完成所有客戶服務總配送時間分別為10.606 4和19.818 8 h，較初始解減少了6.53%和13.91%。

圖3 基于卡車和無人機聯(lián)合配送的最優(yōu)路徑圖Fig.3 The optimal route map based on truck and UAV joint distribution

表2 優(yōu)化前后數(shù)據(jù)對比Table 2 Comparison of data before and after optimization

綜上所述，卡車與無人機聯(lián)合配送比傳統(tǒng)卡車配送在算例1中節(jié)省了0.884 2 h，在算例2中節(jié)省了1.387 6 h。由表3可知：算例1中3條路徑最終解的目標值與初始解的目標函數(shù)值相比均減少0.246 8 h，至少減少了6%；算例2中5條路徑分別減少了0.645 5，0.547 9，0.786 1，0.645 6和0.577 0 h。由表4可知：最終解的目標值與初始解的目標函數(shù)值相比，均至少減少了10%。

表3 算例1的最優(yōu)方案表Table 3 The optimal scheme table for Examples 1

表4 算例2的最優(yōu)方案表Table 4 The optimal scheme table for Examples 2

實驗結果表明：1)通過對算例的求解，驗證了卡車與無人機聯(lián)合配送在配送時間上優(yōu)于傳統(tǒng)卡車配送；2)無人機回收鄰域搜索可以有效地對所建立地初始解進行改進。

4 結論

卡車與無人機聯(lián)合配送的方法和路徑直接影響到配送的速度、成本以及企業(yè)的收益，為滿足日益增長的市場需求，提出了嵌入遺傳算法的鄰域搜索算法，并得出如下結論：

1)考慮卡車搭載裝有包裹的無人機進行取送貨的現(xiàn)實特征，設計添加取送貨條件的無人機車輛路徑問題，將無人機物流運用到正向物流與逆向物流的整合問題中，使無人機在物流問題中的應用得到進一步完善。

2)嵌入遺傳算法的鄰域搜索算法可有效優(yōu)化物流中無人機的配送路徑，能夠將物資有效分配給卡車與無人機，并求得最優(yōu)解。車輛路徑優(yōu)化增添了新的解決方式。

除考慮以配送時間最短為目標外，還有許多現(xiàn)實因素可作為模型來考慮優(yōu)化目標，如客戶滿意度的優(yōu)化、減少運輸工具的能源消耗等。