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

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

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

中圖分類號：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 引 言

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

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

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

1 模型構(gòu)建

1.1 問題描述

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

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

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

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

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

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

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

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

1.2 符號說明

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

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

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

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

1.3 成本分析

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

1.3.1 固定成本

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

1.3.2 運輸成本

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

1.3.3 碳交易成本

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

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

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

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

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

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

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

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

1.4 模型構(gòu)建

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

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

2 算法設(shè)計

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

2.1 編碼方式

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

2.2 構(gòu)造初始解

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

2.3 鄰域操作

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

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

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

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

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

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

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

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

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

2.4 自適應(yīng)機制

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

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

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

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

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

2.6 算法流程圖

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

3 數(shù)值實驗分析

3.1 實驗數(shù)據(jù)及參數(shù)

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

3.2 仿真結(jié)果

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

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

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

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

3.3 對比分析

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

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

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

4 總結(jié)與展望

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

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

參考文獻：

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

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

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

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

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