摘 要：在“雙碳”背景下，為探究卡車-無人機(jī)協(xié)同配送模式的經(jīng)濟(jì)和環(huán)境效益，文章以總成本最小化為目標(biāo)，構(gòu)建了碳交易機(jī)制下的卡車-無人機(jī)協(xié)同配送路徑優(yōu)化模型，并針對(duì)問題特性設(shè)計(jì)自適應(yīng)大鄰域搜索算法進(jìn)行求解，通過具體的數(shù)值算例驗(yàn)證模型的有效性。結(jié)果表明，與傳統(tǒng)情況下僅使用燃油車的配送模式相比，卡車-無人機(jī)協(xié)同配送模式能夠顯著降低碳排放和總成本，為物流企業(yè)選擇綠色經(jīng)濟(jì)的配送方式提供參考。

關(guān)鍵詞：卡車-無人機(jī)協(xié)同配送；車輛路徑；碳交易機(jī)制；自適應(yīng)大鄰域搜索算法

中圖分類號(hào)：F252；TP18 文獻(xiàn)標(biāo)志碼：A DOI：10.13714/j.cnki.1002-3100.2024.20.022

Abstract： In order to investigate the economic and environmental advantages of the truck-UVA cooperative distribution model in the "dual carbon" context， this paper constructs a optimization model for the truck-UVA cooperative distribution path under the carbon trading mechanism with the objective of minimizing the total cost， uses the adaptive large neighborhood search to solve the problem based on the characteristics of the problem， and verifies the effectiveness of the model through specific numerical examples. The results show that compared with the traditional distribution mode using only fuel trucks， the truck-UVA cooperative distribution model can significantly reduce the carbon emission and total cost， which provides logistics enterprises with a reference for selecting green and economical distribution schemes.

Key words： truck-UVA cooperative distribution; vehicle routing; carbon trading mechanism; adaptive large neighborhood search

0 引 言

隨著全球變暖等氣候問題日益嚴(yán)重，控制溫室氣體排放已成為各國(guó)關(guān)注的焦點(diǎn)。為此，我國(guó)提出實(shí)現(xiàn)碳達(dá)峰和碳中和的綠色發(fā)展目標(biāo)。碳交易機(jī)制是我國(guó)實(shí)現(xiàn)“雙碳”目標(biāo)的重要手段之一，旨在通過經(jīng)濟(jì)市場(chǎng)促進(jìn)各行業(yè)和企業(yè)采取措施降低碳排放。在碳交易機(jī)制下研究物流配送，不僅是對(duì)國(guó)家政策的積極響應(yīng)，也有助于推動(dòng)物流行業(yè)的綠色轉(zhuǎn)型。侯躍等[1]探究碳交易機(jī)制對(duì)運(yùn)輸成本的影響，構(gòu)建了多車型路徑優(yōu)化模型，證明企業(yè)可以從碳交易中獲得經(jīng)濟(jì)效益，并降低碳排放。陳婉茹等[2]基于碳交易政策，建立了燃油車和電動(dòng)車構(gòu)成的混合車隊(duì)多中心配送路徑優(yōu)化模型，并研究了車隊(duì)配置、碳交易機(jī)制、速度優(yōu)化對(duì)配送方案的影響。

近年來，無人機(jī)逐漸進(jìn)入物流配送領(lǐng)域。2013年，亞馬遜率先嘗試使用無人機(jī)進(jìn)行商品配送。隨后，谷歌、UPS、順豐、JD等企業(yè)也開始積極探索無人機(jī)配送新模式。無人機(jī)具有靈活高效、不受地面交通限制等優(yōu)點(diǎn)，但是其續(xù)航和載重能力有限，難以滿足長(zhǎng)途運(yùn)輸和大規(guī)模貨物配送的需求。因此，結(jié)合無人機(jī)和車輛運(yùn)輸?shù)膬?yōu)勢(shì)，一些學(xué)者提出卡車與無人機(jī)協(xié)同配送包裹的概念并對(duì)此展開研究。范厚明等[3]用電動(dòng)汽車與無人機(jī)協(xié)同，以總成本最小化為目標(biāo)建立時(shí)變路網(wǎng)下多配送中心的路徑優(yōu)化模型，并設(shè)計(jì)遺傳大鄰域搜索混合算法進(jìn)行求解。楊雷博等[4]針對(duì)現(xiàn)實(shí)中存在限飛區(qū)和限行區(qū)的情況，以最小化服務(wù)時(shí)間優(yōu)化目標(biāo)構(gòu)建雙層規(guī)劃模型并求解。彭勇等[5]借鑒無人機(jī)在特殊環(huán)境下的物流配送，構(gòu)建服務(wù)時(shí)間最短的卡車-無人機(jī)協(xié)同配送路徑優(yōu)化模型?，F(xiàn)有研究大多關(guān)注卡車-無人機(jī)協(xié)同配送的經(jīng)濟(jì)性和時(shí)效性，對(duì)其環(huán)境效益的探討比較有限。

基于上述背景和已有研究的不足，本文從碳排放角度進(jìn)一步對(duì)卡車-無人機(jī)協(xié)同配送模式展開研究。通過碳交易機(jī)制將碳排放量轉(zhuǎn)化為成本，并將其納入目標(biāo)函數(shù)中，以總配送成本最小為目標(biāo)建立數(shù)學(xué)模型，設(shè)計(jì)自適應(yīng)大鄰域搜索算法對(duì)算例求解，得到優(yōu)化后的配送方案，同時(shí)通過對(duì)比實(shí)驗(yàn)證明模型的有效性，進(jìn)一步豐富路徑優(yōu)化問題的現(xiàn)有研究，為物流行業(yè)降本降碳提供參考。

1 模型構(gòu)建

1.1 問題描述

就本文研究的問題，配送中心要有足夠數(shù)量的卡車，且每輛卡車上配備一架小型無人機(jī)與之協(xié)同，共同為區(qū)域內(nèi)客戶提供服務(wù)。配送時(shí)，卡車攜帶對(duì)應(yīng)的無人機(jī)和包裹從配送中心出發(fā)，到達(dá)客戶點(diǎn)時(shí)，卡車為客戶提供服務(wù)，同時(shí)可將該客戶點(diǎn)作為無人機(jī)的發(fā)射節(jié)點(diǎn)，將無人機(jī)放飛。在無人機(jī)單獨(dú)配送的同時(shí)，卡車?yán)^續(xù)前進(jìn)為剩余客戶提供服務(wù)，并將下一客戶點(diǎn)作為無人機(jī)的回收節(jié)點(diǎn)，等待無人機(jī)與之匯合，以進(jìn)行下一階段的配送。在滿足所有限制條件的前提下，進(jìn)行客戶點(diǎn)服務(wù)工具的合理分配，并規(guī)劃卡車和無人機(jī)的配送路線，以降低總體配送成本?？ㄜ嚺c無人機(jī)協(xié)同配送具體如圖1所示。

針對(duì)該問題，本文做出以下假設(shè)：

一是只有一個(gè)配送中心，配送中心有若干輛同型號(hào)的配送車輛和無人機(jī)；

二是所有客戶的需求和地理位置已知，每個(gè)客戶點(diǎn)只能被服務(wù)一次；

三是每輛卡車僅搭載一架無人機(jī)，且每次發(fā)射無人機(jī)只能為一個(gè)客戶點(diǎn)提供服務(wù)；

四是每架無人機(jī)起飛、降落和更換電池的時(shí)間可以忽略不計(jì)；

五是無人機(jī)只能在配送中心或客戶點(diǎn)處進(jìn)行發(fā)射和匯合；

六是當(dāng)無人機(jī)從卡車上起飛，需要在卡車路徑的下一個(gè)節(jié)點(diǎn)處匯合。

1.2 符號(hào)說明

本文問題定義在一張無向圖G=（N，A）上。其中，點(diǎn)集合N={C∪0∪c+1}表示配送網(wǎng)絡(luò)中所有節(jié)點(diǎn)，C={1，2，...，c}表示客戶點(diǎn)集合，0和c+1代表配送中心；N0={0，1，2，...，c}為可離開的節(jié)點(diǎn)集合，N+={1，2，3，...，c，c+1}為可到達(dá)的節(jié)點(diǎn)集合；T={1，2，3，...，t}表示卡車-無人機(jī)組合的集合；A={（i，j）：i∈N0，j∈N+，i≠j}為邊集合；元組＜i，j，k＞表示無人機(jī)飛行路徑，即從節(jié)點(diǎn)i處起飛，服務(wù)客戶j后飛到節(jié)點(diǎn)k處與卡車匯合；Cd表示由無人機(jī)服務(wù)的客戶點(diǎn)集合。

決策變量xtij表示卡車t是否從節(jié)點(diǎn)i行駛節(jié)點(diǎn)j，若是則為1，否則為0；ytijk表示卡車t對(duì)應(yīng)的無人機(jī)從節(jié)點(diǎn)i起飛，為節(jié)點(diǎn)j服務(wù)后，飛到節(jié)點(diǎn)k與卡車匯合，若是則為1，否則為0。

非決策變量sti和分別表示卡車或無人機(jī)到達(dá)節(jié)點(diǎn)i的時(shí)間；σtij和分別表示卡車或無人機(jī)在邊（i，j）上的行駛時(shí)間。

模型中所使用的其他參數(shù)說明如表1所示。

1.3 成本分析

本文所研究模型的成本由三部分組成，分別是固定成本、運(yùn)輸成本、碳交易成本。

1.3.1 固定成本

固定成本包括卡車的固定成本和無人機(jī)的固定成本兩部分?？ㄜ嚨墓潭ǔ杀緝H與車輛的使用數(shù)量有關(guān)，主要包括司機(jī)工資、車輛的折舊費(fèi)用、維修費(fèi)用等。無人機(jī)的固定成本與無人機(jī)的放飛次數(shù)有關(guān)，主要包括在節(jié)點(diǎn)處操作者裝卸無人機(jī)、更換電池的費(fèi)用、無人機(jī)的損耗等。固定成本計(jì)算公式如下。

1.3.2 運(yùn)輸成本

運(yùn)輸成本包括卡車的行駛成本和無人機(jī)的飛行成本。運(yùn)輸成本會(huì)隨著運(yùn)輸距離的增加而改變。因此，建模為與運(yùn)輸距離線性相關(guān)的函數(shù)，具體表達(dá)式如下。

1.3.3 碳交易成本

在計(jì)算碳交易成本時(shí)需要先確定二氧化碳排放量。本文模型中的二氧化碳排放主要考慮兩個(gè)方面：一是卡車行駛過程中燃油消耗產(chǎn)生的碳排放；二是無人機(jī)配送過程中所消耗電量在上游發(fā)電源頭所產(chǎn)生的碳排放。

在計(jì)算車輛行駛過程中的油耗時(shí)，需考慮行駛距離和車輛載重對(duì)油耗的影響。當(dāng)車輛從節(jié)點(diǎn)i行駛到節(jié)點(diǎn)j時(shí)，其載重量為mij，單位距離的燃油消耗量（升/千米）表示如下。

因此，在配送過程中，車輛從節(jié)點(diǎn)i到節(jié)點(diǎn)j時(shí)所產(chǎn)生的碳排放量Etij如下。

無人機(jī)使用電能進(jìn)行驅(qū)動(dòng)，在飛行過程中不直接產(chǎn)生碳排放，但我國(guó)主要采用火力發(fā)電。因此，會(huì)在發(fā)電源頭處間接產(chǎn)生碳排放。本文通過計(jì)算無人機(jī)在配送過程中的電量消耗來確定源頭發(fā)電設(shè)施需要產(chǎn)生的電量，進(jìn)而測(cè)算碳排放量。

在飛行路徑＜i，j，k＞中，無人機(jī)消耗的總電量如下。

考慮到電力在傳輸過程中的損耗，假設(shè)發(fā)電廠生產(chǎn)單位電力所產(chǎn)生的二氧化碳排放量為θ，則無人機(jī)的碳排放量Edijk如下。

因此，配送過程中總碳排放量EM可由公式（7）計(jì)算。

綜上，碳交易成本F3的計(jì)算公式如下。

1.4 模型構(gòu)建

基于以上對(duì)各部分成本的分析，構(gòu)建出碳交易機(jī)制下的卡車-無人機(jī)協(xié)同配送路徑優(yōu)化模型，如下所示。

式（9）表示配送總成本最小的目標(biāo)函數(shù)；式（10）約束每個(gè)客戶只能被卡車或無人機(jī)訪問一次；式（11）保證無人機(jī)無法服務(wù)的客戶僅由一輛卡車進(jìn)行服務(wù)；式（12）是卡車在配送中心的出發(fā)與返回約束；式（13）表示卡車從配送中心出發(fā)后不得直接返回配送中心；式（14）是在客戶點(diǎn)處的進(jìn)出流量平衡約束；式（15）表示無人機(jī)的起降節(jié)點(diǎn)必須被配對(duì)的卡車訪問；式（16）表示無人機(jī)不允許服務(wù)只能由車輛服務(wù)的客戶點(diǎn)；式（17）和式（18）分別表示每輛卡車在各節(jié)點(diǎn)處最多只能發(fā)射和接收一次無人機(jī)；式（19）表示卡車路徑上的無人機(jī)發(fā)射節(jié)點(diǎn)和匯合節(jié)點(diǎn)需相鄰；式（20）和式（21）分別為卡車和無人機(jī)的載重約束；式（22）為無人機(jī)的最大飛行距離約束；式（23）—（29）對(duì)卡車和無人機(jī)在各節(jié)點(diǎn)處的時(shí)間一致性進(jìn)行約束；式（30）和式（31）分別表示車輛和無人機(jī)在配送中心的初始化時(shí)間為0；式（32）和式（33）是決策變量的取值范圍約束；式（34）和式（35）是非決策變量的取值范圍約束。

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

自適應(yīng)大鄰域搜索（ALNS）算法自提出以來，在解決復(fù)雜車輛路徑問題上有較好的表現(xiàn)，具有快速收斂特性、不易陷入局部最優(yōu)等特性。因此，本文選擇該算法對(duì)模型進(jìn)行求解。本節(jié)介紹ALNS算法的主要內(nèi)容及流程圖。

2.1 編碼方式

考慮研究問題的特性，采用整數(shù)編碼的方式，將染色體分為兩個(gè)部分（見圖2）：第一部分表示服務(wù)節(jié)點(diǎn)的順序，其中“0”代表配送中心，非零值則表示對(duì)應(yīng)的客戶節(jié)點(diǎn)；第二部分與第一部分的編碼長(zhǎng)度相同，表示服務(wù)該客戶點(diǎn)的運(yùn)輸工具，用二進(jìn)制數(shù)表示，其中0表示該客戶點(diǎn)由卡車服務(wù)，1表示該客戶點(diǎn)由無人機(jī)進(jìn)行服務(wù)。

2.2 構(gòu)造初始解

求解復(fù)雜的路徑問題時(shí)，一個(gè)質(zhì)量較好的初始解能在一定程度上提升后續(xù)迭代優(yōu)化的效率。本文采用一種兩階段的方式構(gòu)造初始解。首先根據(jù)最近鄰思想生成一個(gè)只有車輛配送的路徑解，接著考慮無人機(jī)的載重和距離等限制，并對(duì)客戶點(diǎn)的服務(wù)工具進(jìn)行分配，生成一條完整的染色體。

2.3 鄰域操作

在得到一組解后，ALNS算法會(huì)對(duì)當(dāng)前解進(jìn)行鄰域搜索，并使用不同的鄰域算子擴(kuò)大解空間的搜索范圍，以找到更優(yōu)的解。為了增加解的多樣性，避免算法陷入局部最優(yōu)，本文采用8種不同的鄰域操作算子。

位置交換：交換路徑中任意兩個(gè)客戶的位置。

互換：交換路徑中編號(hào)最大值與最小值的位置。

反轉(zhuǎn)：選取路徑中的一段序列并水平旋轉(zhuǎn)。

插入：隨機(jī)選擇路徑中的某一客戶，插入另一位置。

滑動(dòng)：選取路徑中兩個(gè)客戶點(diǎn)，將其中一個(gè)插入另一個(gè)位置之后。

序列交換：交換路徑中兩段序列的位置。

序列移動(dòng)：將路徑中一段序列移動(dòng)到另一位置。

反向序列移動(dòng)：將路徑中一段序列移動(dòng)到另一位置并水平反轉(zhuǎn)。

2.4 自適應(yīng)機(jī)制

ALNS算法的自適應(yīng)機(jī)制主要體現(xiàn)在算子的選擇上。本文采用輪盤賭選擇法對(duì)8種鄰域操作算子進(jìn)行隨機(jī)選擇，并根據(jù)各算子的權(quán)重占所有算子總權(quán)重的比例來劃分輪盤。

開始時(shí)，所有鄰域操作算子均具有相同的權(quán)重，且每個(gè)算子都有相同的概率被選擇。每次迭代結(jié)束時(shí)，根據(jù)新解的質(zhì)量好壞來更新所使用算子的權(quán)重。算子的權(quán)重越大，在輪盤中被選中的概率越大，可用以提高算法的尋優(yōu)能力。

2.5 解的接受準(zhǔn)則和終止條件

采用模擬退火思想作為新解的接受準(zhǔn)則。在算法的每次迭代過程中，如果通過鄰域操作后新生成可行解的總成本小于當(dāng)前解的總成本，則將新解直接更新到當(dāng)前可行解的解集中；若新解的總成本高于當(dāng)前可行解的總成本，則根據(jù)模擬退火思想，該劣解有一定的概率被接受。

當(dāng)算法達(dá)到最大迭代次數(shù)時(shí)，則終止。

2.6 算法流程圖

結(jié)合以上內(nèi)容，ALNS算法流程圖如圖3所示。

3 數(shù)值實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)及參數(shù)

本文選取Solomon算例作為模型求解的數(shù)據(jù)來源，采用Solomon算例中R201數(shù)據(jù)，生成30個(gè)客戶點(diǎn)的案例，并在MATLAB中將各節(jié)點(diǎn)坐標(biāo)具體化，如圖4所示。結(jié)果顯示，每輛卡車的最大載重量設(shè)為150 千克，固定成本設(shè)為300 元，單位距離行駛成本為2.3 元/千米，計(jì)算卡車碳排放的相關(guān)參數(shù)為ρ0=1升/千米，ρ*=2 升/千米，β=2.65千克CO2/升。所搭載的無人機(jī)自重為10千克，最大載重為10千克，協(xié)調(diào)成本為5元，單位距離運(yùn)輸成本為0.87元/千米，計(jì)算無人機(jī)碳排放的相關(guān)參數(shù)為：g=9.8，（s）=3，η=0.73，ηb=0.9，ηr=0.956，θ=1.058×10-4kgCO2/J。單位碳排放成本為0.03元/千克CO2，碳配額Tq設(shè)為300千克，交易價(jià)格設(shè)為0.05元/千克。使用Matlab 2018b對(duì)算法進(jìn)行編碼和實(shí)驗(yàn)，最大迭代次數(shù)設(shè)為300，連續(xù)運(yùn)行10次。

3.2 仿真結(jié)果

對(duì)本文的模型和算例進(jìn)行了10次試驗(yàn)，得到最優(yōu)解的配送路徑如表2所示。

由表2可知，配送中心派出三輛卡車與三架無人機(jī)共同為區(qū)域內(nèi)所有客戶提供服務(wù)。第一輛卡車依次為客戶15、13、14、30、8、27、29、12服務(wù)。最后返回配送中心，與之協(xié)同的無人機(jī)1為客戶6、21、10、16、18服務(wù)，并在路徑相鄰節(jié)點(diǎn)處進(jìn)行起飛和降落。

同理，第二輛卡車依次為客戶24、25、11、4、7服務(wù)；無人機(jī)2為客戶22服務(wù)。第三輛卡車依次為客戶26、9、19、20、2、1、3、23服務(wù)；無人機(jī)3為客戶5、28、17服務(wù)。

該最優(yōu)解的各項(xiàng)成本和產(chǎn)生的碳排放量如表3所示。

3.3 對(duì)比分析

為探究卡車-無人機(jī)協(xié)同配送模式的優(yōu)越性，將本文構(gòu)建的模型（記為P1）與僅使用燃油車配送模型（記為P2）進(jìn)行比較，求解結(jié)果如表4所示。

由表4可以看出，與僅使用燃油車進(jìn)行配送相比，卡車與無人機(jī)協(xié)同配送情況下降低了7.08%的總成本，使用無人機(jī)會(huì)增加固定成本，但運(yùn)輸成本和碳交易成本分別降低了23.72%和60.09%，碳排放量降低了40.25%。

由此可見，為區(qū)域內(nèi)客戶進(jìn)行配送時(shí)，使用無人機(jī)與卡車進(jìn)行協(xié)同配送既可以降低配送成本，又可以顯著減少碳排放，可有效解決物流環(huán)節(jié)成本高、碳污染嚴(yán)重等問題，實(shí)現(xiàn)經(jīng)濟(jì)效益和環(huán)境效益的雙重優(yōu)化。

4 總結(jié)與展望

結(jié)合我國(guó)現(xiàn)階段實(shí)行的碳交易政策，本文對(duì)卡車-無人機(jī)協(xié)同配送進(jìn)行了深入研究，構(gòu)建了碳交易機(jī)制下的卡車-無人機(jī)協(xié)同配送路徑優(yōu)化模型，以使固定成本、運(yùn)輸成本、碳交易成本之和最小。針對(duì)問題特性設(shè)計(jì)ALNS算法求解，并通過具體的數(shù)值算例驗(yàn)證本文模型的有效性。實(shí)驗(yàn)結(jié)果表明，與僅使用燃油車的配送模式相比，無人機(jī)與卡車進(jìn)行協(xié)同配送能夠顯著降低碳排放和總成本。本文為物流企業(yè)在碳交易市場(chǎng)下選擇合適的運(yùn)輸工具、制定合理的配送策略提供參考。

卡車和無人機(jī)之間有多種協(xié)同方式，本文的研究?jī)H考慮了其中一種，未來的研究可進(jìn)一步探究其他協(xié)同方式下的經(jīng)濟(jì)與環(huán)境效益。為求得優(yōu)化效果更好的解，可嘗試其他啟發(fā)式算法，或者嘗試使用精確算法求解此類問題。

參考文獻(xiàn)：

[1] 侯躍，楊斌，許波桅，等．考慮碳交易的多車型運(yùn)輸車輛配送路徑優(yōu)化[J]．遼寧工程技術(shù)大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，34（5）：647-652.

[2] 陳婉茹，徐光明，張得志，等．碳交易機(jī)制下多中心混合車隊(duì)配送路徑和速度優(yōu)化研究[J]．系統(tǒng)工程理論與實(shí)踐，2023，43（11）：3320-3335.

[3] 范厚明，張躍光，田攀俊．時(shí)變路網(wǎng)下多中心電動(dòng)車-無人機(jī)協(xié)同配送路徑優(yōu)化[J]．管理工程學(xué)報(bào)，2023，37（2）：131-142.

[4] 楊雷博，周?。拗茀^(qū)下貨車聯(lián)合無人機(jī)配送路徑問題研究[J]．計(jì)算機(jī)工程與應(yīng)用，2023，59（12）：326-332.

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