考慮三類客戶點(diǎn)的卡車-無人機(jī)協(xié)同配送模型及混合算法

關(guān)鍵詞：卡車-無人機(jī)協(xié)同配送；遺傳算法；K-means聚類算法；構(gòu)造算法

中圖分類號(hào)：TP3 F252 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-7934（2024）07-0033-14

一、引言

“最后一公里”配送是物流配送活動(dòng)中非常重要的一個(gè)環(huán)節(jié)，而傳統(tǒng)的卡車配送模式效率低、成本高。鑒于此，引入無人機(jī)與卡車進(jìn)行協(xié)同配送，發(fā)揮卡車大載重、長續(xù)航以及無人機(jī)成本低、速度快的優(yōu)點(diǎn)，能夠有效提升“最后一公里”配送的配送效率、降低配送成本［1-3］。

在阿加茨（Agatz）等［4］將無人機(jī)引入經(jīng)典旅行商問題后，許多學(xué)者對(duì)卡車-無人機(jī)協(xié)同配送問題進(jìn)行了深入研究。在研究目標(biāo)方面，多數(shù)學(xué)者以配送成本最小化或配送時(shí)間最小化等作為單一目標(biāo)，如賽義德（Seyed）等［5］以配送成本最小化為目標(biāo)，提出了一種啟發(fā)式算法，降低了“最后一公里”配送成本；馬佰鈺等［6］建立了以配送成本最小化為目標(biāo)，考慮碳排放約束的混合整數(shù)規(guī)劃模型。也有部分學(xué)者構(gòu)建雙目標(biāo)模型來求解此類問題，如羅（Luo）等［7］以配送成本最小化和客戶滿意度最大化為目標(biāo)構(gòu)建模型，結(jié)果表明該目標(biāo)函數(shù)的設(shè)置方式相較于單目標(biāo)的計(jì)算結(jié)果較優(yōu)；周（Zhou）等［8］以客戶覆蓋范圍最大化和卡車?yán)锍套钚』癁槟繕?biāo)建立模型，并使用粒子群算法求解，結(jié)果顯示算法求解結(jié)果優(yōu)于非線性求解器；此外，學(xué)者們也提出了多種配送模式，如彭勇等［9］根據(jù)客戶不同需求，將客戶點(diǎn)分為卡車配送和無人機(jī)配送兩種模式，每架無人機(jī)每次只能配送一個(gè)客戶點(diǎn)；王（Wang）等［10］提出卡車、車載無人機(jī)和獨(dú)立無人機(jī)的三方混合配送模式，并提出一種混合配送算法（Hybrid Truck-Drone Delivery，HTDD）來解決該問題。

為了增大無人機(jī)的配送效率，吳（Wu）等［11］構(gòu)建了考慮能耗的多輛卡車與多架無人機(jī)協(xié)同配送的數(shù)學(xué)模型，以最大限度減少交付時(shí)間；羅（Luo）等［12］允許無人機(jī)單次飛行服務(wù)多個(gè)客戶，并將客戶分為送貨、取貨和取送貨三類；穆倫巴（Mulumba）［13］等為降低運(yùn)營成本，提出在卡車服務(wù)客戶點(diǎn)時(shí)，無人機(jī)可為該客戶點(diǎn)附近的其他客戶點(diǎn)提供服務(wù)；在無人機(jī)執(zhí)行配送任務(wù)時(shí)，卡車也可繼續(xù)在路線上行駛，并在其他點(diǎn)取回?zé)o人機(jī)；薩拉馬（Salama）［14］等允許無人機(jī)在非客戶點(diǎn)位置進(jìn)行發(fā)射回收，提高了無人機(jī)的利用率。

此外，部分學(xué)者研究了無人機(jī)屬性對(duì)配送過程的影響；默里（Murray）［15］等表示使用速度更快的無人機(jī)雖然會(huì)降低無人機(jī)續(xù)航，但可以提高無人機(jī)配送效率；多林（Dorling）等［16］指出無人機(jī)能耗與無人機(jī)載重量和電池重量呈近似線性變化；鄭（Jeong）等［17］在限制無人機(jī)載重和續(xù)航的基礎(chǔ)上，又考慮了天氣和禁飛區(qū)影響，提出一種啟發(fā)式算法進(jìn)行求解，并驗(yàn)證了算法的有效性；岡薩雷斯（Gonzalez）等［18］提出了一種基于破壞和重建的貪婪啟發(fā)式算法，解決了無人機(jī)電池壽命有限、難以確定新舊電池替換節(jié)點(diǎn)等問題對(duì)模型構(gòu)建的限制；拉吉（Raj）等［19］將無人機(jī)飛行速度作為決策變量，并證明采用可變的無人機(jī)速度可縮短卡車運(yùn)行距離、節(jié)省配送時(shí)間；杜（Du）等［20］對(duì)無人機(jī)最大負(fù)載和電池容量進(jìn)行敏感性分析，結(jié)果表明隨著無人機(jī)最大負(fù)載和電池容量的增加，配送成本呈先降低后增加的趨勢。

在解決卡車-無人機(jī)協(xié)同配送問題時(shí)，K均值聚類算法和遺傳算法被廣泛使用；莫雷洛（Mourelo）等［21］使用K均值聚類算法確定無人機(jī)發(fā)射位置，并用遺傳算法確定卡車路線，結(jié)果表明該方法具有一定的優(yōu)勢；常（Chang）等［22］在初始K均值聚類后，移動(dòng)聚類中心的位置使卡車路徑更短，無人機(jī)服務(wù)范圍更大；彭勇等［23］考慮了無人機(jī)最大飛行時(shí)間、最大載重以及最大飛行速度等因素，使用結(jié)合自適應(yīng)K均值聚類算法的變鄰域搜索算法進(jìn)行求解，結(jié)果表明了算法的有效性；許菱等［24］提出先使用K均值聚類算法確定車輛?？奎c(diǎn)，再使用改進(jìn)的遺傳算法求得卡車-無人機(jī)路徑，并通過算例驗(yàn)證了算法的可行性。

綜上所述，目前已有研究存在以下問題：以配送成本或配送時(shí)間作為單目標(biāo)；不考慮無人機(jī)續(xù)航或考慮無人機(jī)續(xù)航但無人機(jī)每次發(fā)射均需更換電池；將客戶點(diǎn)分為無人機(jī)配送與卡車配送兩類；只允許無人機(jī)一次攜帶一件包裹。因此，本文在綜合考慮無人機(jī)載重、無人機(jī)續(xù)航及無人機(jī)可攜帶多件包裹的條件下，提出一種將客戶點(diǎn)分為三類的卡車-無人機(jī)協(xié)同配送路徑優(yōu)化模型，以配送成本和配送時(shí)間的加權(quán)和最小化作為優(yōu)化目標(biāo)，添加時(shí)間約束以收緊無人機(jī)與卡車抵達(dá)同一客戶點(diǎn)的時(shí)間差，添加電量約束以減少電池更換次數(shù)、增大電池利用率，并使用由遺傳算法、K均值聚類算法和構(gòu)造算法共同組成的混合算法對(duì)模型求解，最后通過算例驗(yàn)證了模型和算法在求解卡車-無人機(jī)協(xié)同配送問題上的有效性和可行性，具有一定的參考價(jià)值。

二、問題描述及模型建立

1.問題描述

配送中心和各客戶點(diǎn)之間的距離已知；對(duì)于路況差、交通擁堵、需求量小于等于無人機(jī)額定載重的客戶點(diǎn)、與另一最近的距離不超出無人機(jī)配送范圍的客戶點(diǎn)使用無人機(jī)配送；對(duì)于需求量超過無人機(jī)額定載重的客戶點(diǎn)、與另一最近的距離超出無人機(jī)配送范圍的客戶點(diǎn)使用卡車配送；除上述兩類客戶點(diǎn)外的其余客戶點(diǎn)使用卡車或無人機(jī)配送；因此，可以把客戶點(diǎn)分為三類：只能由無人機(jī)配送點(diǎn)、只能由卡車配送點(diǎn)、卡車和無人機(jī)均可配送點(diǎn)。

根據(jù)卡車是否在某客戶點(diǎn)進(jìn)行無人機(jī)發(fā)射接收工作，以及配送過程中卡車與無人機(jī)的相對(duì)位置關(guān)系，將所有客戶點(diǎn)分為四類。一是無人機(jī)發(fā)射點(diǎn)（需要進(jìn)行無人機(jī)發(fā)射操作的客戶點(diǎn)），如圖1客戶點(diǎn)7。二是無人機(jī)接收點(diǎn)（需要進(jìn)行無人機(jī)接收操作的客戶點(diǎn)），如圖1客戶點(diǎn)9。三是既是無人機(jī)接收點(diǎn)又是無人機(jī)發(fā)射點(diǎn)（簡稱無人機(jī)收發(fā)點(diǎn)），如圖1客戶點(diǎn)8。四是非無人機(jī)發(fā)射點(diǎn)或無人機(jī)接收點(diǎn)：①帶機(jī)配送點(diǎn)：卡車抵達(dá)某點(diǎn)時(shí)攜帶無人機(jī)，如圖1客戶點(diǎn)2；②無機(jī)配送點(diǎn)：卡車抵達(dá)某點(diǎn)時(shí)未攜帶無人機(jī)，如圖1客戶點(diǎn)4。

除上述內(nèi)容外，本文還做出以下六點(diǎn)假設(shè)：①卡車只能在停靠在客戶點(diǎn)時(shí)發(fā)射接收無人機(jī)，每輛卡車攜帶一架無人機(jī)，每個(gè)客戶點(diǎn)最多只能發(fā)射和接收無人機(jī)各一次；②天氣情況良好，無人機(jī)速度恒定；③單個(gè)客戶點(diǎn)的需求量已知；④無人機(jī)起飛后可訪問多個(gè)客戶點(diǎn)，可攜帶多件包裹；⑤無人機(jī)更換電池時(shí)間較短，忽略不計(jì)；⑥無人機(jī)耗電量與飛行距離成正比。

整體配送流程為：卡車攜帶無人機(jī)從配送中心出發(fā)，前往預(yù)定的客戶點(diǎn)進(jìn)行配送，根據(jù)客戶點(diǎn)分類進(jìn)行無人機(jī)發(fā)射接收工作，之后繼續(xù)前往下一客戶點(diǎn)，以此類推，直到配送完所有客戶點(diǎn)后返回配送中心。其中，由卡車進(jìn)行配送的客戶點(diǎn)稱為卡車服務(wù)點(diǎn)，由無人機(jī)進(jìn)行配送的客戶點(diǎn)稱為無人機(jī)服務(wù)點(diǎn)。

2.符號(hào)說明

在模型建立之前，首先對(duì)符號(hào)和決策變量進(jìn)行說明，如表1和表2所示。

為了保證所有客戶點(diǎn)均只能被配送一次，做出式（8）—式（29）的卡車-無人機(jī)協(xié)同配送路徑約束。

式（8）—式（12）表示客戶點(diǎn)流量平衡約束；其中，式（8）—式（10）表示所有卡車服務(wù)點(diǎn)只能由一輛卡車進(jìn)出各一次；式（11）—式（12）表示所有無人機(jī)點(diǎn)只能由一架無人機(jī)進(jìn)出各一次。

式（13）—式（20）表示客戶點(diǎn)的耦合約束；其中，式（13）—式（14）表示無人機(jī)發(fā)射點(diǎn)的耦合約束，即在無人機(jī)單次配送過程中，無人機(jī)發(fā)射點(diǎn)是無人機(jī)本次航線的起點(diǎn)且不是終點(diǎn)；同理，式（15）—式（16）表示無人機(jī)接收點(diǎn)的耦合約束；式（17）—式（18）表示無人機(jī)收發(fā)點(diǎn)的耦合約束；式（19）—式（20）表示無機(jī)配送點(diǎn)的耦合約束。

為防止卡車和無人機(jī)原地打轉(zhuǎn)，做出式（21）—式（22）的約束。

式（23）—式（25）表示配送中心不是無人機(jī)發(fā)射點(diǎn)、無人機(jī)接收點(diǎn)或無機(jī)配送點(diǎn)；式（26）—式（27）表示無人機(jī)發(fā)射點(diǎn)或無人機(jī)接收點(diǎn)不是無人機(jī)配送點(diǎn)；式（28）—式（29）表示若某卡車配送點(diǎn)的前一點(diǎn)為無人機(jī)發(fā)射點(diǎn)或無機(jī)配送點(diǎn)，則該點(diǎn)只能為無機(jī)配送點(diǎn)或無人機(jī)接收點(diǎn)。

為了滿足卡車和無人機(jī)的載重要求，做出式（30）—式（35）的載重約束；其中，式（30）表示卡車載重不能超過卡車額定載重量；式（31）表示卡車駛過某點(diǎn)的載重量減少量為該點(diǎn)需求量以及從該點(diǎn)發(fā)射的無人機(jī)的載重量之和；式（32）表示卡車回到配送中心時(shí)的載重量為0；式（33）表示無人機(jī)載重不能超過無人機(jī)額定載重量；式（34）表示無人機(jī)配送過程中，無人機(jī)飛過某點(diǎn)時(shí)的載重量減少量為該點(diǎn)需求量；式（35）表示無人機(jī)飛至無人機(jī)接收點(diǎn)時(shí)載重量為0。

為了減少整體配送時(shí)間，做出式（36）—式（40）的時(shí)間約束；其中，式（36）表示卡車從配送中心出發(fā)的時(shí)刻為0；式（37）表示卡車離開j點(diǎn)的時(shí)刻；式（38）表示協(xié)同配送時(shí)，無人機(jī)離開j點(diǎn)的時(shí)刻；式（39）表示卡車離開無人機(jī)接收點(diǎn)的時(shí)刻；式（40）表示卡車返回配送中心的時(shí)間限制。

為了減少電池更換次數(shù)，降低電池更換成本，做出式（41）—式（51）的電量約束；其中，式（41）表示判斷無人機(jī)發(fā)射點(diǎn)是否更換電池；式（42）—式（43）表示無人機(jī)離開無人機(jī)發(fā)射點(diǎn)時(shí)的電量；式（44）表示無人機(jī)不會(huì)到達(dá)無人機(jī)配送點(diǎn)；式（45）—式（46）表示無人機(jī)離開和到達(dá)無人機(jī)接收點(diǎn)時(shí)的電量；式（47）表示對(duì)于某個(gè)不是無人機(jī)發(fā)射點(diǎn)、無人機(jī)接收點(diǎn)或無機(jī)配送點(diǎn)的客戶點(diǎn)，無人機(jī)到達(dá)該點(diǎn)時(shí)的電量即為無人機(jī)離開上一點(diǎn)時(shí)的電量；式（48）表示無人機(jī)離開配送中心時(shí)的電量；式（49）—式（50）表示無人機(jī)離開某點(diǎn)時(shí)的電量等于到達(dá)該點(diǎn)時(shí)的電量；式（51）表示無人機(jī)電量隨飛行進(jìn)程減少。

式（52）—式（59）表示該模型所有決策變量約束。

為了提高模型求解效率，將非線性的約束條件轉(zhuǎn)化為線性，以式（13）為例。如果客戶點(diǎn)i是無人機(jī)發(fā)射點(diǎn)（gi=1），則yij=1，即無人機(jī)會(huì)從i點(diǎn)飛至j點(diǎn)，此時(shí)客戶點(diǎn)i不是無人機(jī)配送點(diǎn)（bi=0），且不確定該點(diǎn)是否同時(shí)為無人機(jī)接收點(diǎn)（hi=0或hi=1）；引入M進(jìn)行轉(zhuǎn)化，M（gi-1）=0，此時(shí)1-hi-bi小于等于1，yij=1，M（hi-1）與1-hi-bi的和小于等于yij。如果客戶點(diǎn)i不是無人機(jī)發(fā)射點(diǎn)（gi=0），M（gi-1）是一個(gè)極小的數(shù)，此時(shí)無論yij=0或yij=1，M（gi-1）與1-hi-bi的和均小于等于yij，可得式（13）轉(zhuǎn)化后的公式，即式（60）；

三、算法設(shè)計(jì)

本文采用的混合算法由K均值聚類算法、遺傳算法與構(gòu)造算法混合組成。首先，確定聚類中心數(shù)量（即卡車數(shù)量k）的取值范圍；其次，隨機(jī)選擇范圍內(nèi)的k值，通過K均值聚類算法生成初始聚類，根據(jù)聚類結(jié)果使用構(gòu)造算法生成并優(yōu)化初始卡車-無人機(jī)協(xié)同配送路徑，優(yōu)化后的卡車-無人機(jī)協(xié)同配送路徑的目標(biāo)函數(shù)值為該染色體的目標(biāo)函數(shù)值；最后，通過遺傳算法的交叉、變異操作對(duì)所有染色體的目標(biāo)函數(shù)值和k值進(jìn)行再優(yōu)化，直到滿足遺傳算法停止要求。

（一）遺傳算法參數(shù)設(shè)置

本文基于田口實(shí)驗(yàn)確定遺傳算法的參數(shù)組合，影響本文算法性能的參數(shù)包括種群規(guī)模（N）、交叉概率（Pc）、變異概率（Pm）、最大迭代次數(shù)（max_gen）；本文的問題為望小型問題，所以選擇信噪比（S/N）最小的值作為本文參數(shù)；實(shí)驗(yàn)確定本文參數(shù)選擇為N=100，Pc=0.8，Pm=0.2，max_gen=100。

（二）染色體組成方式

本文以一種配送方案的聚類中心坐標(biāo)集合作為一條染色體，如圖2所示，該染色體共包含4個(gè)聚類中心坐標(biāo)，（Xa，Ya）為其中一個(gè)聚類中心的坐標(biāo)。相較于普遍將卡車-無人機(jī)協(xié)同配送路徑作為染色體，該方式構(gòu)建的染色體在交叉變異過程中能擴(kuò)大解的變化范圍，有利于避免陷入局部最優(yōu)。

（三）算法步驟

步驟1：初始化遺傳算法各項(xiàng)參數(shù)信息如下。種群規(guī)模N=100；交叉概率Pc=0.8；變異概率Pm=0.2；最大迭代次數(shù)max_gen=100；初始迭代次數(shù)gen=1。

步驟2：構(gòu)建初始種群。

步驟2.1：確定K均值聚類算法中k值的下界（總需求量/卡車額定載重量，若不為整數(shù)則向上取整）和上界，為擴(kuò)大k值搜索范圍，取上界為下界的兩倍。

步驟2.2：在范圍內(nèi)隨機(jī)確定k值，并隨機(jī)選取k個(gè)客戶點(diǎn)作為一條初始染色體。

步驟3：計(jì)算所有染色體適應(yīng)度fit，適應(yīng)度最大的染色體記為best。

步驟3.1：根據(jù)k值進(jìn)行K均值聚類。

步驟3.2：用構(gòu)造算法生成和優(yōu)化卡車-無人機(jī)協(xié)同配送路徑。

步驟3.3：輸出所有染色體的目標(biāo)函數(shù)，并將目標(biāo)函數(shù)值的倒數(shù)設(shè)置為適應(yīng)度，適應(yīng)度公式見式（91）。

式中：fit（n）為染色體n的適應(yīng)度；w（n）為染色體n的目標(biāo)函數(shù)值；

步驟4：輪盤賭選擇，產(chǎn)生規(guī)模同樣為N的種群，每條染色體被選中的概率p（n）可由式（92）得出。

式中：fit_sum為種群中染色體適應(yīng)度總和。

步驟5：交叉，根據(jù)交叉概率Pc隨機(jī)選擇兩條父代染色體：父代染色體1和父代染色體2，染色體示意如圖2所示。從選中的父代染色體1和父代染色體2中分別隨機(jī)選擇n1，n2個(gè)聚類中心（n1，n2均小于所在染色體的聚類中心個(gè)數(shù)），交換兩條染色體選中的聚類中心坐標(biāo)，得到子代染色體1和子代染色體2；若交叉過后的子代染色體中存在兩個(gè)聚類中心相同的情況，則重新執(zhí)行交叉操作，如圖3所示。

步驟6：變異，按照變異概率Pm從父代染色體中選擇一個(gè)聚類中心（Xa，Ya）進(jìn)行變異；對(duì)于所有的客戶點(diǎn)，橫坐標(biāo)最大/最小值分別為max_x，min_x；縱坐標(biāo)最大/最小值分別為max_y，min_y；對(duì)選中的聚類中心坐標(biāo)添加一個(gè)隨機(jī)系數(shù)R（0lt;Rlt;2），變異后的聚類中心坐標(biāo)為（RXa，RYa），規(guī)定min_xlt;RXalt;max_x，min_ylt;RYalt;max_y，若變異過后的染色體中存在相同基因，則重新執(zhí)行該操作。

步驟7：重新計(jì)算染色體的適應(yīng)度，若種群中的最大適應(yīng)度大于best適應(yīng)度，則以該適應(yīng)度對(duì)應(yīng)的染色體替代best，更新最大適應(yīng)度。

步驟8：gen=gen+1，如果gengt;max_gen或兩代best誤差符合要求，算法結(jié)束，best表示問題的一個(gè)解，否則返回步驟3。

（四）構(gòu)造算法

（1）生成初始路徑。

假設(shè)聚類中所有客戶點(diǎn)都是卡車服務(wù)點(diǎn)，卡車從配送中心出發(fā)后前往的第一個(gè)點(diǎn)是聚類中距離配送中心最近的點(diǎn)，第二個(gè)點(diǎn)是距離配送中心的次近點(diǎn)，以此類推，直到將該聚類中所有客戶點(diǎn)配送完畢，返回配送中心，形成初始卡車路徑。

將N3中的客戶點(diǎn)轉(zhuǎn)化為無人機(jī)服務(wù)點(diǎn)，將N1和N2中的所有客戶點(diǎn)信息存儲(chǔ)至備選發(fā)射點(diǎn)集合和備選接收點(diǎn)集合中；選中一個(gè)N3中的點(diǎn)i，在已形成的卡車路徑中，尋找與點(diǎn)i最近的兩點(diǎn)，判斷此兩點(diǎn)與點(diǎn)i的距離之和是否滿足無人機(jī)續(xù)航；若滿足，則按照這兩點(diǎn)在卡車路線中的順序分別作為無人機(jī)的發(fā)射點(diǎn)和接收點(diǎn)，并將點(diǎn)i從卡車路徑中刪除，將這兩點(diǎn)從備選集合中刪除；若不滿足，則將該染色體目標(biāo)值設(shè)置為一個(gè)極大值。

（2）優(yōu)化初始路徑。

為了優(yōu)化初始卡車-無人機(jī)協(xié)同配送路徑，借鑒孟姍姍等［25］的操作，將優(yōu)化操作分為四類：單點(diǎn)轉(zhuǎn)化、卡車服務(wù)點(diǎn)插入卡車或無人機(jī)路徑、無人機(jī)服務(wù)點(diǎn)插入無人機(jī)路徑、兩點(diǎn)交換。①單點(diǎn)轉(zhuǎn)化。該步操作可以使無人機(jī)起飛后配送更多客戶，增大無人機(jī)利用率，具體轉(zhuǎn)化操作為：將無人機(jī)發(fā)射點(diǎn)、無人機(jī)接收點(diǎn)、無人機(jī)收發(fā)點(diǎn)以及非無人機(jī)發(fā)射點(diǎn)或無人機(jī)接收點(diǎn)轉(zhuǎn)化為無人機(jī)服務(wù)點(diǎn)。②卡車服務(wù)點(diǎn)插入卡車或無人機(jī)路徑。該步操作可以減小卡車行駛里程，降低卡車運(yùn)輸成本，進(jìn)一步增大無人機(jī)利用率。③無人機(jī)服務(wù)點(diǎn)插入無人機(jī)路徑。通過改變無人機(jī)配送客戶點(diǎn)的先后順序以提高配送效率。④兩點(diǎn)交換。該步驟將客戶點(diǎn)在卡車-無人機(jī)協(xié)同配送路徑中的位置進(jìn)行交換，尋找最優(yōu)路徑，具體交換操作為：兩卡車服務(wù)點(diǎn)交換；兩無人機(jī)服務(wù)點(diǎn)交換；無人機(jī)發(fā)射點(diǎn)、無人機(jī)接收點(diǎn)、無人機(jī)收發(fā)點(diǎn)交換；卡車服務(wù)點(diǎn)和無人機(jī)服務(wù)點(diǎn)交換；卡車服務(wù)點(diǎn)、無人機(jī)服務(wù)點(diǎn)與無人機(jī)發(fā)射點(diǎn)、無人機(jī)接收點(diǎn)、無人機(jī)收發(fā)點(diǎn)交換。

經(jīng)過上述優(yōu)化操作，可以得到一條優(yōu)化后的卡車-無人機(jī)協(xié)同配送路徑以及其對(duì)應(yīng)的染色體和目標(biāo)函數(shù)值。

四、算例分析

本文算例以CVRP標(biāo)準(zhǔn)算例庫中的A-n32-k5，A-n33-k5，A-n36-k6等數(shù)據(jù)集為基礎(chǔ)并改進(jìn)。改進(jìn)方法為：將所有點(diǎn)的橫縱坐標(biāo)縮小10倍，為適應(yīng)卡車載重、無人機(jī)的載重和續(xù)航，將N1中客戶點(diǎn)的需求量隨機(jī)調(diào)整為（3，100）kg，N2中客戶點(diǎn)的需求量隨機(jī)調(diào)整為（3，20）kg，N3中客戶點(diǎn)的需求量隨機(jī)調(diào)整為（3，10）kg，并對(duì)其中某些算例進(jìn)行取舍，以滿足規(guī)模要求；根據(jù)客戶點(diǎn)的總數(shù)，對(duì)改進(jìn)過的算例重新命名為U-n32，U-n33，U-n36等。

相關(guān)參數(shù)設(shè)置：卡車額定載重量Qc為1500 kg，無人機(jī)額定載重量Qm為20 kg，卡車單次最大配送時(shí)間Tmax為8 h，無人機(jī)額定電量B為3 kWh，單位距離無人機(jī)耗電量為0.15 kWh/km，卡車行駛速度v_car為40 km/h，無人機(jī)飛行速度v_uav為60 km/h，每臺(tái)卡車的啟動(dòng)成本Ca為100 元，卡車運(yùn)輸成本為1.5 元/km，更換電池成本為6 元/次。單次無人機(jī)發(fā)射時(shí)間tf為0.04h，每個(gè)客戶點(diǎn)服務(wù)時(shí)間tz為0.05 h，加權(quán)系數(shù)α1=0.7，α2=0.3。

本文算法均由Matlab編程實(shí)現(xiàn)；運(yùn)行環(huán)境為Windows 11操作系統(tǒng)，處理器為13th Gen Intel（R） Core（TM） i9-13900HX 2.20 GHz。

1.算法穩(wěn)定性驗(yàn)證

為驗(yàn)證算法穩(wěn)定性，對(duì)同一算例進(jìn)行多次運(yùn)算；由表3可知，算例U-n32的10次運(yùn)算結(jié)果中，k值均確定為2，目標(biāo)函數(shù)平均值為214.79，最大值、最小值與平均值分別相差1.78%，-1.90%；里程平均值為50.13 km，最大值、最小值與平均值分別相差2.47%，-3.65%；由此可知，算法穩(wěn)定性較強(qiáng)。

表3 算法穩(wěn)定性驗(yàn)證

2.優(yōu)化結(jié)果分析

以算例U-n20為例，對(duì)收斂前后的目標(biāo)函數(shù)值進(jìn)行比較。經(jīng)過計(jì)算確定k值上界為2，下界為1，經(jīng)過運(yùn)算得到一個(gè)k=1的初始解，該初始解的目標(biāo)函數(shù)值為162.802，初始卡車-無人機(jī)路徑如圖4所示。

由于在初始解生成過程中，已經(jīng)通過構(gòu)造算法對(duì)初始解進(jìn)行優(yōu)化，所以該初始解質(zhì)量較高；經(jīng)過遺傳算法的再優(yōu)化后，得到最終解的目標(biāo)函數(shù)值為155.948，對(duì)比初始解，目標(biāo)函數(shù)優(yōu)化了4.21%，說明該算法的優(yōu)化效果較好，最終卡車-無人機(jī)路徑如圖5所示。

3.小規(guī)模算例驗(yàn)證

本文使用交互式的線性和通用優(yōu)化求解器（Lingo）進(jìn)行小規(guī)模算例對(duì)比試驗(yàn)，實(shí)驗(yàn)以5 h為運(yùn)行時(shí)間上限，若5 h仍不能得到精確解，則采用5 h內(nèi)求得的解的下界進(jìn)行對(duì)比。對(duì)于小規(guī)模算例，本文提出的混合算法求得的各項(xiàng)結(jié)果與Lingo計(jì)算結(jié)果十分接近并且能夠大幅縮短運(yùn)算時(shí)間。以U-n23為例，在Lingo計(jì)算5 h時(shí)，目標(biāo)函數(shù)值下界為209.560，對(duì)應(yīng)配送成本為224.80元，配送時(shí)間為1.74 h；混合算法求得目標(biāo)函數(shù)值為177.509，配送成本為174.81 元，配送時(shí)間為1.84 h，運(yùn)行時(shí)間為13.82 s；由上述可知，混合算法在更短的時(shí)間內(nèi)得到了更小的目標(biāo)函數(shù)值，由此可以說明本文提出的算法運(yùn)算效率較高，且求得解的精度較高，詳細(xì)數(shù)據(jù)如表4所示。

表4 小規(guī)模算例對(duì)比結(jié)果

4.大規(guī)模算例驗(yàn)證

與傳統(tǒng)遺傳算法和兩階段算法［26］對(duì)比進(jìn)行大規(guī)模算例驗(yàn)證，其中兩階段算法的第一階段為使用考慮無人機(jī)最大飛行半徑的K-means聚類算法對(duì)所有客戶點(diǎn)分區(qū)，第二階段為使用遺傳算法對(duì)每個(gè)分區(qū)進(jìn)行優(yōu)化求解。對(duì)比結(jié)果如表5所示，其中，L表示卡車?yán)锍蹋▎挝唬簁m），w表示目標(biāo)函數(shù)值；由對(duì)比結(jié)果可知，本文提出的混合算法相較于傳統(tǒng)遺傳算法，里程和目標(biāo)函數(shù)值都有較大改進(jìn)，相較于兩階段算法更優(yōu)；該對(duì)比結(jié)果說明本文提出的混合算法在處理大規(guī)模問題時(shí)也具有較好的求解效果。

表5 大規(guī)模算例對(duì)比結(jié)果

5.與只考慮配送成本或配送時(shí)間對(duì)比

為了驗(yàn)證本文提出的“以配送成本和配送時(shí)間的加權(quán)和最小化為目標(biāo)”（以下簡稱“加權(quán)和最小化”）的優(yōu)勢，將本文目標(biāo)函數(shù)值與“以配送成本最小化為目標(biāo)時(shí)，配送成本與配送時(shí)間的加權(quán)和”（以下簡稱“配送成本最小化”）與“以配送時(shí)間最小化為目標(biāo)時(shí)，配送成本和配送時(shí)間的加權(quán)和”（以下簡稱“配送時(shí)間最小化”）進(jìn)行比對(duì)，對(duì)比結(jié)果如圖6所示。由圖6可知，同一算例，本文提出的“加權(quán)和最小化”比“配送成本最小化”和“配送時(shí)間最小化”的目標(biāo)函數(shù)值均更小，且對(duì)于減少“配送時(shí)間最小化”的目標(biāo)函數(shù)值效果更為明顯，這說明本文目標(biāo)函數(shù)的設(shè)置方式相較于只考慮配送時(shí)間或配送成本更為合理，在求解卡車-無人機(jī)協(xié)同配送問題時(shí)具有較好的效果。

五、結(jié)論

針對(duì)“最后一公里”傳統(tǒng)卡車配送模式效率低、成本高的難題，本文提出了一種將客戶點(diǎn)分成只能由無人機(jī)配送點(diǎn)、只能由卡車配送點(diǎn)、卡車和無人機(jī)均可配送點(diǎn)三類的卡車-無人機(jī)協(xié)同配送模式，建立以配送成本和配送時(shí)間加權(quán)和最小化為目標(biāo)的數(shù)學(xué)模型，并設(shè)計(jì)了一種混合算法對(duì)模型進(jìn)行求解；與Lingo計(jì)算結(jié)果的對(duì)比說明了本文算法的運(yùn)算效率較高，運(yùn)算結(jié)果精度較高；與兩種智能算法的對(duì)比結(jié)果說明該算法在處理大規(guī)模問題時(shí)效果也較好；與以配送成本最小化為目標(biāo)或以配送時(shí)間最小化為目標(biāo)的對(duì)比說明了本文目標(biāo)函數(shù)設(shè)置的合理性；本文為卡車-無人機(jī)協(xié)同配送問題的優(yōu)化提供了新思路，具有一定的借鑒和指導(dǎo)意義。

在實(shí)際配送活動(dòng)中，每個(gè)客戶點(diǎn)都有一個(gè)可變時(shí)間窗，不在時(shí)間窗范圍內(nèi)配送會(huì)提高成本；此外，天氣因素會(huì)對(duì)無人機(jī)配送效率產(chǎn)生較大影響。因此，未來將在現(xiàn)有研究的基礎(chǔ)上，增加對(duì)時(shí)間窗和天氣因素的考慮。

參考文獻(xiàn)：

［1］CAO Q K， ZHANG X F， REN X Y， et al."Path optimization of joint delivery mode of trucks and UAVs［J］. mathematical problems in engineering， 2021：1-15.

［2］WANG X Y， POIKONEN S， GOLDEN B."The vehicle routing problem with drones： several worst-case results［J］. Optimization letters， 2017， 11 （4）： 679-697.

［3］STEFAN P， WANG X Y， GOLDEN B."The vehicle routing problem with drones： extened models and connections［J］. Networks， 2017， 70 （1）： 34-43.

［4］AGATZ N， BOUMAN P， SCHMIDT M."Optimization approaches for the traveling salesman problem with drone［J］. Transportation science， 2018， 52 （4）： 965-981.

［5］SHAVARANI S M， NEJAD M G， RISHMANCHIAN F， et al."Application of hierarchical facility location problem for optimization of a drone delivery system： a case study of amazon prime air in the city of san francisco［J］. International journal of advanced manufacturing technology， 2018， 95 （9）： 3141-3153.

［6］馬佰鈺， 李賀鑫， 馬千里， 等."碳排放約束下無人機(jī)-卡車聯(lián)合配送問題［J］.系統(tǒng)工程，2024，42（2）：60-69.

［7］LUO Q Z， WU G H， JI B， et al.Hybrid multi-objective optimization approach with pareto local search for collaborative truck-drone routing problems considering flexible time windows［J］. IEEE transactions on intelligent transportation systems， 2022， 23 （8）： 13011-13025.

［8］ZHOU L Y， SILVA D F， SMITH A E.Locating drone stations for a truck-drone delivery system in continuous space［J］. IEEE transactions on evolutionary computation， 2023： 1.

［9］彭勇， 黎元鈞.考慮疫情影響的卡車無人機(jī)協(xié)同配送路徑優(yōu)化［J］. 中國公路學(xué)報(bào)， 2020， 33 （11）： 73-82.

［10］WANG D S， HU P， DU J X， et al."Routing and scheduling for hybrid truck-drone collaborative parcel delivery with independent and truck-carried drones［J］. IEEE internet of things journal， 2019， 6 （6）： 10483-10495.

［11］WU G H， MAO N， LUO Q Z， et al."Collaborative truck-drone routing for contactless parcel delivery during the epidemic［J］. IEEE transactions on intelligent transportation systems， 2022， 23 （12）： 25077-25091.

［12］LUO Q Z， WU G H， TRIVEDI A， et al."Multi-objective optimization algorithm with adaptive resource allocation for truck-drone collaborative delivery and pick-up services［J］. IEEE transactions on intelligent transportation systems， 2023， 24 （9）： 1-16.

［13］MULUMBA T， DIABAT A."Optimization of the drone-assisted pickup and delivery problem［J］. Transportation research part e： logistics and transportation review， 2024， 181：103377.

［14］SALAMA M R， SRINIVAS S."Collaborative truck multi-drone routing and scheduling problem： package delivery with flexible launch and recovery sites［J］. Transportation research part e： logistics and transportation review， 2022， 164： 102788.

［15］MURRAY C C， CHU A G."Theflying sidekick traveling salesman problem： optimization of drone-assisted parcel delivery［J］. Transportation research part c： emerging technologies， 2015， 54： 86-109.

［16］DORLING K， HEINRICHS J， MESSIER G G， et al."Vehiclerouting problems for drone delivery［J］. IEEE transactions on systems， man， and cybernetics systems， 2017， 47 （1）： 70-85.

［17］JEONG H Y， SONG B D， LEE S."Truck-drone hybrid delivery routing： payload-energy dependency and no-fly zones［J］. International journal of production economics， 2019， 214： 220-233.

［18］GONZALEZ R P L， CANCA D， ANDRADE P J L， et al."Truck-drone team logistics： a heuristic approach to multi-drop route planning［J］. Transportation research."part c， emerging technologies， 2020， 114： 657-680.

［19］RAJ R， MURRAY C."Themultiple flying sidekicks traveling salesman problem with variable drone speeds［J］. Transportation research."part c， emerging technologies， 2020， 120： 102813.

［20］DU P F， HE X， CAO H T， et al."AI-based energy-efficient path planning of multiple logistics uavs in intelligent transportation systems［J］. Computer communications， 2023， 207： 46-55.

［21］MOURELO F S， HARBISON T， et al."Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm［J］. Journal of industrial engineering and management， 2016， 9 （2）： 374-388.

［22］CHANG Y S， LEE H J."Optimal delivery routing with wider drone-delivery areas along a shorter truck-route［J］. Expert systems with applications， 2018， 104： 307-317.

［23］彭勇， 張永輝， 黎元鈞."考慮無人機(jī)輔助的卡車配送路徑優(yōu)化［J］. 工業(yè)工程與管理， 2023， 28 （2）： 31-39.

［24］許菱， 楊林超， 朱文興， 等."農(nóng)村電商物流下無人機(jī)與車輛協(xié)同配送路徑優(yōu)化研究［J］， 計(jì)算機(jī)工程與應(yīng)用，2024，60（1）： 310-318.

［25］孟姍姍， 郭秀萍."卡車-無人機(jī)聯(lián)合取送貨模式下物流優(yōu)化［J］. 系統(tǒng)管理學(xué)報(bào)， 2022， 31 （3）： 555-566.

［26］褚衍昌， 王雪婷."卡車搭載無人機(jī)的同時(shí)取送貨路徑規(guī)劃研究［J］. 計(jì)算機(jī)應(yīng)用與軟件， 2023， 40 （12）： 56-63.

Truck-drone Collaborative Distribution Model and Hybrid Algorithm

Considering Three Types of Customer Points

DI Wei-min，YANG Wen-hao，ZHANG Wei-feng

（School of Management， Zhengzhou University， Zhengzhou， Henan 450001）

Abstract： In order to improve the efficiency of the last-mile delivery and reduce the delivery cost， a truck-drone collaborative distribution model considering three types of customer points is proposed."This paper establishes a mathematical model with the objective of weighting and minimization of distribution cost and distribution time， and constrains on three types of customer points in terms of truck-drone collaborative distribution paths， truck and drone loads， collaborative time， and drone electric quantity; it also uses hybrid algorithm consisting of genetic algorithm， K-means clustering algorithm together with construction algorithm to solve the model."The results of large-scale and small-scale examples show that the algorithm in this paper has relatively "high solution efficiency and accuracy; the objective of minimizing the weighted sum of distribution cost and distribution time is better than the objective of minimizing distribution cost or distribution time."The results illustrate that the model and algorithm proposed in this paper can effectively solve the truck-drone collaborative delivery problem; it is more reasonable to aim at minimizing the weighted sum of distribution cost and distribution time compared to considering only distribution cost or distribution time.

Keywords： truck-drone collaborative distribution; genetic algorithm; K-means clustering algorithm; construction algorithm