基于低碳排放的應急物流車輛路徑優化

張靜怡，司夏萌，張 虹

（北京信息科技大學 信息管理學院，北京 100192）

0 引言

近年來，各類突發事件給人們的生命安全帶來了嚴重的威脅。例如，近年在全國各地頻繁發生的洪澇災害、四川地區的地震災害以及在全世界肆虐的新冠疫情等。這類事件會給人們的生命健康帶來嚴峻的威脅，其影響也蔓延到社會與經濟層面，給社會穩定與經濟持續發展造成危害。突發事件發生時，為了減少人員傷亡與財產損失，救援工作對物流的需求極為迫切。因此，有必要組織好應急物流工作，對應急物流車輛路徑優化問題進行研究，在應對突發事件時具有十分重要的意義。

目前，已有眾多學者對應急物流配送路徑優化進行研究。宋英華，等[1]以時間窗懲罰成本最小與駕駛員心理成本最小為目標，建立了雙目標應急物流配送車輛路徑問題的整數規劃模型，并通過加權遺傳算法進行了求解；Li，等[2]以運輸時間最短、受災點滿意度最大為目標，建立了應急物流配送路徑優化模型，采用快速非支配排序遺傳算法求解模型；呂偉，等[3]在軟時間窗與硬時間窗的綜合約束下以總延遲時間最短、軟時間窗懲罰成本最小、硬時間窗不滿足數最少為目標，建立了應急物流車輛配送路徑模型，首先預處理路網數據，然后建模并利用遺傳算法求解模型；楊瀟，等[4]基于需求分級構建了應急物流系統定位-路徑優化模型，并通過改進遺傳算法進行求解，得到了最優選址和路徑方案；康斌，等[5]以最小化最晚車輛服務結束時間、最小化需求未滿足率為目標，建立了應急物流配送路徑優化模型，通過優先鄰點交叉算子改進遺傳算法對模型進行求解；趙建有，等[6]通過K-means聚類算法選擇配送中心并劃分受災點，以救援時間最短、救援費用最小以及受災點緊迫度排序指數最大為目標，構建了應急車輛路徑優化模型，并通過改進的布谷鳥-蟻群組合算法進行求解；彭大江，等[7]引入三角模糊數刻畫模糊需求，提出了模糊需求下的應急物流中心選址-路徑模型，并通過基于Q-學習的超啟發式算法求解模型；Jiang，等[8]以配送時間最短、配送成本最低、未滿足需求量最低為目標建立應急物流調度模型，通過魯棒優化方法進行求解；Oruc，等[9]提出了一個雙目標優化模型，旨在通過提供受影響地區的損害信息來最大化評估道路所增加的總體價值并最大化評估節點的總利潤，可以有效地尋找救援線路；李慧，等[10]綜合考慮道路擁擠情況、救援物資儲備、患者和醫院的地理位置、車輛空閑情況等多維因素，實現了基于改進弗洛伊德算法的救護車應急救援路徑規劃。

總結已有研究文獻可知，當前對應急物流車輛路徑優化的研究多以時間最短、路徑最短、成本最低、需求滿意度最大為目標構建數學模型，較少考慮到配送過程中的碳排放對環境所產生的影響。基于此，本文綜合考慮配送成本、需求滿意度與碳排放量，建立了基于低碳排放的應急物流車輛路徑優化模型。

1 相關理論

1.1 節約算法

節約算法又稱C-W 算法，是將運輸問題中的兩條路徑合并形成一條路徑，大幅縮短合并之后的運輸距離，直到達到一輛車的最大載重限制后，再對下一輛車進行優化。節約算法通常用來獲取車輛路徑優化問題的初始解，以滿足受災點的物資需求與配送車輛的載重限制作為前提條件，將運輸路徑最短的配送方案作為應急物流車輛路徑優化問題的初始解。

1.2 遺傳算法

遺傳算法是模仿生物界選擇和遺傳的機理形成的一種基于種群的隨機全局搜索與優化方法。在遺傳算法中，一條染色體代表問題的一個解，根據設置的適應度函數，計算每一條染色體的適應度值，通過選擇操作保留適應度較高的染色體，并通過交叉、變異等操作保持種群的多樣性，在進行一定次數的迭代后解碼，就得到了問題的最優解。

遺傳算法具有全局搜索能力強、收斂速度快等優點，但遺傳算法通過隨機方法產生初始解，搜索的難度更大，且局部搜索能力也存在不足。

1.3 大規模鄰域搜索算法

大規模鄰域搜索算法是一種主要基于“破壞”和“修復”思想的算法，首先通過破壞算子從目前的解中移除若干需求點，再通過修復算子，將被移除的需求點再度插回已被破壞的解中，從而獲得更高質量的解。

2 問題描述

本文研究中需要解決的應急物流配送路徑優化問題如下：多個配送中心，多個受災點，已知各配送中心與各受災點的位置、各配送中心的倉庫容量、車輛的最大載重量，各受災點的需求量可以用三角模糊函數表示，要求每個受災點僅由一輛車進行配送，且車輛在完成配送任務后返回配送中心。在時間、空間和資源的約束下，建立車輛路徑優化模型，使配送車輛的固定成本、運輸過程中產生的成本、未滿足需求量的懲罰成本以及碳排放成本之和最低。圖1為應急物流車輛路徑優化問題的示例圖。

圖1 應急物流車輛路徑優化問題示例圖

3 基于低碳排放的應急物流車輛路徑優化模型

3.1 模型已知條件

（1）假設每個受災點僅由一輛車配送物資；

（2）假設配送車輛的初始位置在某一配送中心，且在物資配送完畢后返回該配送中心；

（3）假設配送車輛均為同一型號，其最大載重限制相同。

3.2 符號說明

D：配送中心節點集合{i|i=1，2，…，m}；

N：需求點集合{i|i=m+1，m+2，…，n}；

V：車輛集合{k|k=1，2，…，r}；

c1：車輛的固定使用費用；

c2：車輛的單位運輸費用；

c3：未滿足需求的單位懲罰成本；

oi：受災點i最樂觀的需求量；

li：受災點i最有可能的需求量；

pi：受災點i最悲觀的需求量；

Qi：受災點i的需求量；

dij：點i到點j的距離；

μ：車輛滿載時的燃油消耗率；

μ0：車輛空載時的燃油消耗率；

Mk：車輛k能負載的最大重量；

Mijk：車輛k從點i行駛到點j的載重量；

Gi：配送中心i的最大容量；

τ：碳排放量與燃油消耗量之間的轉換系數；

3.3 模型建立

考慮到應急物流的特殊性與環境保護思想，為了在降低運輸成本的同時盡量滿足受災點的物資需求，并減少碳排放，本文以車輛的固定成本、車輛運輸過程中產生的成本、未滿足需求的懲罰成本以及碳排放成本之和作為目標函數構建模型。

（1）配送車輛的固定成本

（2）配送車輛的運輸成本

（3）未滿足需求的懲罰成本。在突發事故中，受災點的需求量具有不確定性。因此，為盡量滿足受災點的需求，保障救援工作的順利進行，本文參考文獻[11]，利用三角模糊函數，通過最樂觀需求、最可能需求和最悲觀需求來估計需求量Qi。它們之間的關系見式（3）、式（4）。

采用加權法將三角模糊數轉化為某個數值，受災點i的需求量Qi可以通過式（5）計算得到。

由于車輛和配送中心的容量限制，車輛運送到受災點的應急物資數量可能會低于預計需求。因此，當受災點的需求沒有得到滿足時，將會產生一定的配送懲罰成本。懲罰成本可以表示為:

（4）碳排放成本。應急物流運輸過程中的碳排放量與燃油消耗呈線性相關，而燃油消耗受到車輛行駛速度、車輛載重量、道路坡度、行駛距離等多種因素的影響。本文參考文獻[12]計算燃油消耗量，可以用以下公式表示：

碳排放成本可以表示為：

（5）目標函數：

約束條件：

式（10）表示各配送中心配送的物資總量不超過配送中心的容量；式（11）表示每個受災點僅由單獨一輛車提供一次配送服務；式（12）表示每輛車在配送中心出發且僅服務于一個配送中心；式（13）表示每輛車在應急物資配送完畢后重新返回配送中心。

4 混合遺傳算法設計

為了提高遺傳算法的搜索效率，利用節約算法得到遺傳算法的初始解。針對遺傳算法在局部搜索能力上的缺陷，采用大規模鄰域搜索算法中“破壞”與“修復”的思想，構造出一種混合遺傳算法，用以求解本文中的應急物流車輛路徑優化問題，混合遺傳算法的流程圖如圖2所示。

圖2 混合遺傳算法流程圖

（1）編碼。采用整數編碼的方法，假設受災點數目為n，配送中心最大車輛使用數目為k，則染色體長度為n+k-1，染色體可表示為(1，2，…，n+k-1)的形式。

（2）種群初始化。采用節約算法構造問題的初始解，高質量的初始解可以在一定程度上降低遺傳算法的搜索難度，假設h是標記第幾大距離節約值的位置，則具體步驟如下：

步驟一：將每個受災點的配送任務分配給一輛單獨的車執行；

步驟二：將每兩條路徑融合并計算距離節約值，將距離節約值依據從高到低的順序排列；

步驟三：更新距離節約值，融合節約值最大的兩條路徑，判斷該路徑上車輛的載重量是否符合車輛容量限制，若不符合，則使h=n+1，執行步驟四，否則重復執行步驟三；

步驟四：融合距離節約值第h大的兩條路徑，判斷是否存在某條路徑上僅有一個受災點的情況，若存在，則重復執行步驟三，否則輸出每輛車所途經的受災點的序號。

通過節約算法得到初始配送方案后，進行種群的初始化。先把初始解按編碼方式轉換為個體，然后將種群的所有個體全部賦值為初始解轉換的個體。

（3）適應度函數。應急物流模型中的目標函數f由配送車輛的固定成本、運輸成本、未滿足需求量的懲罰成本以及碳排放成本之和組成，由此可知，目標函數越小則結果越符合要求，而選擇操作通常保留適應度值較大的個體，因此將適應度函數設為目標函數的倒數，即令：

（4）選擇操作。利用二元錦標賽選擇法進行選擇操作，操作過程就是比較兩個個體，然后選擇適應度值更大的個體進入子代種群。若種群數目為NIND，則循環NIND次，每次循環隨機選出兩個個體，在二者中選擇出適應度值更大的個體。由于新選擇出的NIND個體中可能有重復個體，所以只保留重復個體中的一個個體，然后刪除其他重復個體。

（5）交叉操作。首先在兩個父代染色體上隨機選擇兩個交叉位置，然后截取兩個交叉片段，交錯移動到兩個父代個體之前，最后刪除第2個重復的基因位，構成兩個子代個體。這種交叉方式有利于維護種群的多樣性。具體操作如圖3所示。

圖3 交叉操作流程

（6）變異操作。在父代染色體上隨機選擇兩個變異位置，交換兩個位置上的基因，得到變異后的子代個體，具體操作如圖4所示。

圖4 變異操作流程

（7）局部搜索操作。運用大規模鄰域搜索算法中“破壞”與“修復”的思想，即通過破壞算子按照相似性計算公式（15）從目前的解中移除若干受災點，然后通過修復算子將被移除的受災點插回讓目標函數值增加值最少的位置。

破壞算子：按照式（15）、式（16）移除若干受災點。

式中，為將cij標準化后的值，范圍在區間[0，1]；cij為i與j之間的距離；vij表示i與j是否在同一條路徑上，如果在同一條路徑上則為0，否則為1。由式（15）可知，兩個受災點相互之間的距離越近，則R(i，j)越大；兩個受災點如果位于同一路徑上，則R(i，j)最大。

破壞算子的偽代碼見表1。

表1 破壞算子偽代碼

修復算子：修復算子的偽代碼見表2。

表2 修復算子偽代碼

（8）終止條件。達到最大迭代次數MAXGEN時，停止迭代，輸出問題的最優解。

5 算例分析

5.1 算例說明

本文引用文獻[13]中應急物流路徑問題的分布數據，見表3、表4。存在3個配送中心與20個受災點，各節點的位置信息已知，各節點之間的距離通過平面坐標的歐氏距離簡化表示。混合遺傳算法的參數設置見表5。

表3 配送中心相關數據

表4 受災點相關數據

表5 參數表

5.2 算法比較

利用MATLAB R2018b編程軟件，根據分布數據信息，分別運用遺傳算法與混合遺傳算法求解基于低碳排放的應急物流車輛路徑優化模型。

遺傳算法與混合遺傳算法的優化過程如圖5、圖6所示，求解得到的最優配送方案路線如圖7所示。

圖5 遺傳算法的優化過程

圖6 混合遺傳算法的優化過程

圖7 混合遺傳算法得到的最優配送方案路線圖

遺傳算法與混合遺傳算法的優化仿真結果對比見表6。

表6 仿真結果

5.3 結果比較

通過對比遺傳算法和混合遺傳算法的優化過程可知，利用節約算法求初始解，利用大規模鄰域搜索算法改進局部搜索操作的混合遺傳算法在迭代次數為42 次時達到最優解，而遺傳算法在迭代次數為60次時達到最優解，因此本文中的混合遺傳算法相較于傳統的遺傳算法具有更好的收斂性。對比遺傳算法與混合遺傳算法的優化結果可知，混合遺傳算法在運輸距離、總成本、碳排放成本上都取得了更好的結果。

6 結語

本文基于低碳綠色的思想，針對災害發生前提下的應急物流路徑優化問題進行研究，以配送車輛的固定成本、運輸成本、未滿足需求量的懲罰成本以及碳排放成本之和最小為優化目標，構建了基于低碳排放的應急物流車輛路徑優化模型，并通過混合遺傳算法對模型進行求解。最后利用MATLAB軟件分別通過遺傳算法與混合遺傳算法進行仿真，并對比分析二者的結果。由對比結果可知，混合遺傳算法具有更好的收斂性，且在運輸距離、總成本、碳排放成本上均獲得了更好的結果。因此，基于低碳排放的應急物流車輛路徑優化模型具備實用性且混合遺傳算法具有較高的求解效率，可為應急物流車輛路徑優化問題的應對提供參考。

不過本文對于各受災點需求量的預測方式過于簡單。而在現實生活中，由于次生災害、信息的滯后性等因素，受災點的需求量呈現出更大的不確定性，配送車輛在運輸過程中的交通條件也存在很多不確定因素，這些因素都會對應急物流車輛路徑優化的結果產生影響。因此，未來可更深入研究考慮更多不確定因素的應急物流車輛路徑優化問題。