考慮三類客戶點的卡車-無人機協同配送模型及混合算法

關鍵詞：卡車-無人機協同配送；遺傳算法；K-means聚類算法；構造算法

中圖分類號：TP3 F252 文獻標識碼：A 文章編號：2096-7934（2024）07-0033-14

一、引言

“最后一公里”配送是物流配送活動中非常重要的一個環節，而傳統的卡車配送模式效率低、成本高。鑒于此，引入無人機與卡車進行協同配送，發揮卡車大載重、長續航以及無人機成本低、速度快的優點，能夠有效提升“最后一公里”配送的配送效率、降低配送成本［1-3］。

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

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

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

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

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

二、問題描述及模型建立

1.問題描述

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

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

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

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

2.符號說明

在模型建立之前，首先對符號和決策變量進行說明，如表1和表2所示。

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

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

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

為防止卡車和無人機原地打轉，做出式（21）—式（22）的約束。

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

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

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

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

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

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

三、算法設計

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

（一）遺傳算法參數設置

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

（二）染色體組成方式

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

（三）算法步驟

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

步驟2：構建初始種群。

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

步驟2.2：在范圍內隨機確定k值，并隨機選取k個客戶點作為一條初始染色體。

步驟3：計算所有染色體適應度fit，適應度最大的染色體記為best。

步驟3.1：根據k值進行K均值聚類。

步驟3.2：用構造算法生成和優化卡車-無人機協同配送路徑。

步驟3.3：輸出所有染色體的目標函數，并將目標函數值的倒數設置為適應度，適應度公式見式（91）。

式中：fit（n）為染色體n的適應度；w（n）為染色體n的目標函數值；

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

式中：fit_sum為種群中染色體適應度總和。

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

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

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

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

（四）構造算法

（1）生成初始路徑。

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

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

（2）優化初始路徑。

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

經過上述優化操作，可以得到一條優化后的卡車-無人機協同配送路徑以及其對應的染色體和目標函數值。

四、算例分析

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

相關參數設置：卡車額定載重量Qc為1500 kg，無人機額定載重量Qm為20 kg，卡車單次最大配送時間Tmax為8 h，無人機額定電量B為3 kWh，單位距離無人機耗電量為0.15 kWh/km，卡車行駛速度v_car為40 km/h，無人機飛行速度v_uav為60 km/h，每臺卡車的啟動成本Ca為100 元，卡車運輸成本為1.5 元/km，更換電池成本為6 元/次。單次無人機發射時間tf為0.04h，每個客戶點服務時間tz為0.05 h，加權系數α1=0.7，α2=0.3。

本文算法均由Matlab編程實現；運行環境為Windows 11操作系統，處理器為13th Gen Intel（R） Core（TM） i9-13900HX 2.20 GHz。

1.算法穩定性驗證

為驗證算法穩定性，對同一算例進行多次運算；由表3可知，算例U-n32的10次運算結果中，k值均確定為2，目標函數平均值為214.79，最大值、最小值與平均值分別相差1.78%，-1.90%；里程平均值為50.13 km，最大值、最小值與平均值分別相差2.47%，-3.65%；由此可知，算法穩定性較強。

表3 算法穩定性驗證

2.優化結果分析

以算例U-n20為例，對收斂前后的目標函數值進行比較。經過計算確定k值上界為2，下界為1，經過運算得到一個k=1的初始解，該初始解的目標函數值為162.802，初始卡車-無人機路徑如圖4所示。

由于在初始解生成過程中，已經通過構造算法對初始解進行優化，所以該初始解質量較高；經過遺傳算法的再優化后，得到最終解的目標函數值為155.948，對比初始解，目標函數優化了4.21%，說明該算法的優化效果較好，最終卡車-無人機路徑如圖5所示。

3.小規模算例驗證

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

表4 小規模算例對比結果

4.大規模算例驗證

與傳統遺傳算法和兩階段算法［26］對比進行大規模算例驗證，其中兩階段算法的第一階段為使用考慮無人機最大飛行半徑的K-means聚類算法對所有客戶點分區，第二階段為使用遺傳算法對每個分區進行優化求解。對比結果如表5所示，其中，L表示卡車里程（單位：km），w表示目標函數值；由對比結果可知，本文提出的混合算法相較于傳統遺傳算法，里程和目標函數值都有較大改進，相較于兩階段算法更優；該對比結果說明本文提出的混合算法在處理大規模問題時也具有較好的求解效果。

表5 大規模算例對比結果

5.與只考慮配送成本或配送時間對比

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

五、結論

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

在實際配送活動中，每個客戶點都有一個可變時間窗，不在時間窗范圍內配送會提高成本；此外，天氣因素會對無人機配送效率產生較大影響。因此，未來將在現有研究的基礎上，增加對時間窗和天氣因素的考慮。

參考文獻：

［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］.系統工程，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］. 中國公路學報， 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］. 工業工程與管理， 2023， 28 （2）： 31-39.

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

［25］孟姍姍， 郭秀萍."卡車-無人機聯合取送貨模式下物流優化［J］. 系統管理學報， 2022， 31 （3）： 555-566.

［26］褚衍昌， 王雪婷."卡車搭載無人機的同時取送貨路徑規劃研究［J］. 計算機應用與軟件， 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