市區內卡車與無人機協同配送路徑優化研究

陳添博，謝寶玲（沈陽工業大學 化工裝備學院，遼寧 遼陽 111000）

0 引言

近年來，隨著經濟的不斷進步與物流業的快速發展，人們的需求也逐漸增加，對物品的配送效率提出了更高的要求。傳統的單一卡車配送所帶來的問題逐漸暴露在面前，不但耗時長、效率低進而增加了時間成本，而且還會加重環境污染問題，不符合我國低碳環保的發展理念。隨著無人機研發技術逐漸成熟，制造成本大幅降低，無人機[1]在各個領域得到了廣泛應用，除軍事領域外，還包括農業植保、電力巡檢、警用執法、地質勘探以及應急救援等民用領域。但單單使用無人機配送的缺點也十分明顯，如無人機續航時間不夠長、有區域配送限制、有潛在的不安全性等。為了整合兩者單一配送的優勢、規避存在的劣勢，提出“卡車與無人機協同配送”的模式，卡車僅僅作為無人機的移動配送站點，由無人機進行末端配送，保證安全的同時高效地將所需貨品送到需求點。

目前看來，國外學者Murray 和Chu[2]提出了兩種數學規劃模型，分別是PDSTSP 模型和FSTSP 模型，兩種模型的區別主要在于PDSTSP 模型是無人機與卡車分別同時進行配送，FSTSP 模型是卡車搭載無人機進行配送。而我國對于卡車與無人機協同配送的模式還在初步研究中，集中在“最后一公里”和農商配送的領域較多，并且主要致力于降低成本這一經濟目標。本文綜合考慮了現有的研究內容，為了進一步優化卡車與無人機協同配送模型，將圍繞以下兩點核心問題展開實證研究：（1）本文的研究對象是對市區內的客戶點配送，擴展了現有研究對象的范圍。（2）本文將時間作為首要目標，對卡車單獨配送和卡車與無人機協同配送分別做路徑規劃，進而對比分析證明卡車與無人機協同配送的高效性。

1 卡車-無人機問題建模

1.1 問題描述

J 公司是一家擁有雄厚的綜合服務實力的第三方物流企業，有關加急配送商品的任務承接是J 公司所有項目中的重要組成之一。然而在城市中，經常會遇到交通擁堵、道路限行、車輛限號等一系列不可控問題，即使加急單的金額高、數量多，能夠提高公司效益，但為了保證服務的標準性J 公司無法承包更多的加急單任務，損失了一大批潛在客戶。

為了解決這類問題，J 公司在無人機方面投入大量的時間、金錢和精力進行研發，目前，J 公司在無人機領域的技術相當成熟，已經獲得相關部門許可能夠進行試運營。然而僅僅采用無人機配送加急貨物，雖然能夠在配送過程中不受路面交通的影響，從而一定程度上降低收貨延誤的風險，但是無人機隨處停放和起飛很容易在市區發生危險。因而J 公司將采取卡車與無人機協同的方式對加急單進行配送。

為了方便研究，對問題進行簡化，根據J 公司的企業實力以及配送中實際存在的問題，做出如下假設：

（1）客戶點坐標需求已知，且卡車物資量滿足需求，所有客戶點均被訪問。

（2）卡車可攜帶多架同質無人機配送，無人機只能當卡車在停靠站點處于停留狀態時被發射和收集。

（3）只要不違反無人機的電量及負載限制，可一次服務多個客戶點。

（4）同一架無人機只能返回搭載其的卡車，即回收無人機的站點與發射站點相同。

（5）無人機返回卡車進行更換物資、電池或充電等工作，卡車僅作為無人機的移動配送中心，不參與配送。

（6）每個站點只能被卡車訪問一次，客戶點也只能被無人機服務一次。

（7）無人機充電、更換電池以及裝卸包裹時間不考慮，裝卸無人機時間也不考慮，但無人機設置最大飛行時間。

（8）無人機只要返回卡車均進行電池更換或充電，保證每次以滿電形式進行配送。根據所提出的研究假設，對模型的符號進行定義，如表1 所示。

表1 模型符號定義

1.2 建立模型

根據問題描述和參數定義，構建以下模型：

目標函數：

式（1）表示完成所有客戶的配送任務后，卡車返回到配送中心的總配送時間最小。

卡車路徑約束：

式（2）表示卡車從配送中心出發并返回，且全程只有一次；式（3）表示車輛路徑的連續性；式（2）和式（3）共同表示卡車在行駛過程中流量平衡。式（4）和式（5）表示卡車到達站點j 的時間等于卡車離開上一個站點i 的時間與i,j 間的旅行時間之和。

無人機路徑約束：

式（6）確保每個客戶點由一架無人機服務；式（7）保證無人機的連續性；式（8）表示無人機的行駛路徑流量平衡；式（9）和式（10）表示無人機到客戶點k 的時間等于無人機離開上一客戶點i 的時間與i,k 間的旅行時間之和；式（11）確保無人機離開客戶點k 前需要為客戶點服務。

卡車與無人機協同約束：

式（12）和式（13）表示無人機在對客戶點進行配送時，只能從車上發射；式（14）表示從站點j 發射的無人機在完成配送后返回卡車的時刻；式（15）保證無人機無法直接飛回配送中心；式（16）保證無人機無法從配送中心發射到客戶點。

卡車去子回路約束：

式（17）和式（18）是為了消除子回路，確保卡車行駛路線正確。

決策變量：

表示變量的取值范圍、二進制和非負性。

1.3 數據處理

J 公司使用一輛卡車搭載三架同質無人機的方式向某區域內的17 個客戶點進行配送。已知客戶點、停靠站點、配送中心的實際坐標，以及每個客戶點所需的貨物重量，數據如表2 所示。其中序號1 表示配送中心坐標，序號2-18 表示客戶點坐標，序號19-27 表示停靠站點坐標。

表2 客戶配送數據

1.4 實驗結果分析

本文所研究的卡車與無人機協同配送問題屬于NP 難問題，為此，將用智能優化算法求解此類約束條件較多的組合優化模型問題。由于遺傳算法的魯棒性強、適用的范圍較廣并且較容易實現，然而其易早熟并且搜索能力較差的缺點也同樣是不可忽略的。因此，針對本文所涉及的范圍以及模型的難易度，將采取單親遺傳算法進行求解，遺傳算子僅包括選擇和變異，由基因個體內部完成進化，不存在交叉算子，提高了計算效率。

以時間最短為目標，分別采取兩種配送方式規劃路徑，即僅由卡車單獨配送的路徑，如圖1 所示，以及由卡車與無人機協同配送的路徑，如圖2 所示，并獲得卡車和無人機協同配送路徑的結果，如表3 所示。

圖1 卡車單獨配送路徑

圖2 卡車與無人機協同配送路徑

表3 卡車與無人機系統配送路徑結果圖

當卡車單獨配送時，在城市內卡車的運行速度為45km/h，在每個客戶點進行配送的時間為4min，遇到紅燈進行等待或其他突發事故的靈活時間可視為15min，計算可得僅由卡車配送所有客戶點至結束的時間為3.38h。

當卡車與無人機協同配送時，由卡車行走至全部的停靠站點，其運行速度仍視為45km/h，由無人機對客戶點進行配送，實驗中所選取的三架同質無人機的運行速度均為60km/h，攜帶包裹重量均不超過5kg，發射和回收無人機的時間均為1min，在客戶點的服務時間均為1min，遇到紅燈進行等待或其他突發事故的靈活時間可視為10min，經過計算可以得出卡車在經過每一站點的時間約為1.37h，無人機對客戶點進行配送的時間約為0.8h，總體配送完成回至倉庫的總時間為2.17h。

經過對比可知，首先，卡車和無人機協同配送后，由于卡車只需要行駛至停靠站點，那么行駛路程變短后的行駛時間降低的同時靈活處理時間也會降低；其次，由無人機派送包裹后，在保證配送準確率的同時提高了配送包裹的效率；最后，在完成配送任務的總時間上共節省了1.21h，符合預期。

2 結束語

本文基于卡車與無人機協同配送的模式，在市區內以J 公司加急物品配送業務為研究對象進行案例分析，目標是盡可能的縮短時間，提高配送效率及降低延誤的可能性。通過單親遺傳算法的求解，研究表明：（1）采取卡車與無人機協同配送的模式比單卡車配送更為省時，并且安全性和可靠性也有一定的保障，一定程度上可以增加企業效益與信任度。（2）以時間最短為主要研究目標的卡車與無人機協同配送路徑得以實現，可以類比與其他情境再做研究。