碳交易機制下卡車-無人機協同配送問題研究

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

關鍵詞：卡車-無人機協同配送；車輛路徑；碳交易機制；自適應大鄰域搜索算法

中圖分類號：F252；TP18 文獻標志碼：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 引 言

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

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

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

1 模型構建

1.1 問題描述

就本文研究的問題，配送中心要有足夠數量的卡車，且每輛卡車上配備一架小型無人機與之協同，共同為區域內客戶提供服務。配送時，卡車攜帶對應的無人機和包裹從配送中心出發，到達客戶點時，卡車為客戶提供服務，同時可將該客戶點作為無人機的發射節點，將無人機放飛。在無人機單獨配送的同時，卡車繼續前進為剩余客戶提供服務，并將下一客戶點作為無人機的回收節點，等待無人機與之匯合，以進行下一階段的配送。在滿足所有限制條件的前提下，進行客戶點服務工具的合理分配，并規劃卡車和無人機的配送路線，以降低總體配送成本?？ㄜ嚺c無人機協同配送具體如圖1所示。

針對該問題，本文做出以下假設：

一是只有一個配送中心，配送中心有若干輛同型號的配送車輛和無人機；

二是所有客戶的需求和地理位置已知，每個客戶點只能被服務一次；

三是每輛卡車僅搭載一架無人機，且每次發射無人機只能為一個客戶點提供服務；

四是每架無人機起飛、降落和更換電池的時間可以忽略不計；

五是無人機只能在配送中心或客戶點處進行發射和匯合；

六是當無人機從卡車上起飛，需要在卡車路徑的下一個節點處匯合。

1.2 符號說明

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

決策變量xtij表示卡車t是否從節點i行駛節點j，若是則為1，否則為0；ytijk表示卡車t對應的無人機從節點i起飛，為節點j服務后，飛到節點k與卡車匯合，若是則為1，否則為0。

非決策變量sti和分別表示卡車或無人機到達節點i的時間；σtij和分別表示卡車或無人機在邊（i，j）上的行駛時間。

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

1.3 成本分析

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

1.3.1 固定成本

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

1.3.2 運輸成本

運輸成本包括卡車的行駛成本和無人機的飛行成本。運輸成本會隨著運輸距離的增加而改變。因此，建模為與運輸距離線性相關的函數，具體表達式如下。

1.3.3 碳交易成本

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

在計算車輛行駛過程中的油耗時，需考慮行駛距離和車輛載重對油耗的影響。當車輛從節點i行駛到節點j時，其載重量為mij，單位距離的燃油消耗量（升/千米）表示如下。

因此，在配送過程中，車輛從節點i到節點j時所產生的碳排放量Etij如下。

無人機使用電能進行驅動，在飛行過程中不直接產生碳排放，但我國主要采用火力發電。因此，會在發電源頭處間接產生碳排放。本文通過計算無人機在配送過程中的電量消耗來確定源頭發電設施需要產生的電量，進而測算碳排放量。

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

考慮到電力在傳輸過程中的損耗，假設發電廠生產單位電力所產生的二氧化碳排放量為θ，則無人機的碳排放量Edijk如下。

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

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

1.4 模型構建

基于以上對各部分成本的分析，構建出碳交易機制下的卡車-無人機協同配送路徑優化模型，如下所示。

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

2 算法設計

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

2.1 編碼方式

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

2.2 構造初始解

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

2.3 鄰域操作

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

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

互換：交換路徑中編號最大值與最小值的位置。

反轉：選取路徑中的一段序列并水平旋轉。

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

滑動：選取路徑中兩個客戶點，將其中一個插入另一個位置之后。

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

序列移動：將路徑中一段序列移動到另一位置。

反向序列移動：將路徑中一段序列移動到另一位置并水平反轉。

2.4 自適應機制

ALNS算法的自適應機制主要體現在算子的選擇上。本文采用輪盤賭選擇法對8種鄰域操作算子進行隨機選擇，并根據各算子的權重占所有算子總權重的比例來劃分輪盤。

開始時，所有鄰域操作算子均具有相同的權重，且每個算子都有相同的概率被選擇。每次迭代結束時，根據新解的質量好壞來更新所使用算子的權重。算子的權重越大，在輪盤中被選中的概率越大，可用以提高算法的尋優能力。

2.5 解的接受準則和終止條件

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

當算法達到最大迭代次數時，則終止。

2.6 算法流程圖

結合以上內容，ALNS算法流程圖如圖3所示。

3 數值實驗分析

3.1 實驗數據及參數

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

3.2 仿真結果

對本文的模型和算例進行了10次試驗，得到最優解的配送路徑如表2所示。

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

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

該最優解的各項成本和產生的碳排放量如表3所示。

3.3 對比分析

為探究卡車-無人機協同配送模式的優越性，將本文構建的模型（記為P1）與僅使用燃油車配送模型（記為P2）進行比較，求解結果如表4所示。

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

由此可見，為區域內客戶進行配送時，使用無人機與卡車進行協同配送既可以降低配送成本，又可以顯著減少碳排放，可有效解決物流環節成本高、碳污染嚴重等問題，實現經濟效益和環境效益的雙重優化。

4 總結與展望

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

卡車和無人機之間有多種協同方式，本文的研究僅考慮了其中一種，未來的研究可進一步探究其他協同方式下的經濟與環境效益。為求得優化效果更好的解，可嘗試其他啟發式算法，或者嘗試使用精確算法求解此類問題。

參考文獻：

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

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

[3] 范厚明，張躍光，田攀?。畷r變路網下多中心電動車-無人機協同配送路徑優化[J]．管理工程學報，2023，37（2）：131-142.

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

[5] 彭勇，黎元鈞．考慮疫情影響的卡車無人機協同配送路徑優化[J]．中國公路學報，2020，33（11）：73-82.