基于低碳排放的應(yīng)急物流車輛路徑優(yōu)化

張靜怡，司夏萌，張 虹

（北京信息科技大學(xué) 信息管理學(xué)院，北京 100192）

0 引言

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

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

總結(jié)已有研究文獻(xiàn)可知，當(dāng)前對(duì)應(yīng)急物流車輛路徑優(yōu)化的研究多以時(shí)間最短、路徑最短、成本最低、需求滿意度最大為目標(biāo)構(gòu)建數(shù)學(xué)模型，較少考慮到配送過(guò)程中的碳排放對(duì)環(huán)境所產(chǎn)生的影響。基于此，本文綜合考慮配送成本、需求滿意度與碳排放量，建立了基于低碳排放的應(yīng)急物流車輛路徑優(yōu)化模型。

1 相關(guān)理論

1.1 節(jié)約算法

節(jié)約算法又稱C-W 算法，是將運(yùn)輸問(wèn)題中的兩條路徑合并形成一條路徑，大幅縮短合并之后的運(yùn)輸距離，直到達(dá)到一輛車的最大載重限制后，再對(duì)下一輛車進(jìn)行優(yōu)化。節(jié)約算法通常用來(lái)獲取車輛路徑優(yōu)化問(wèn)題的初始解，以滿足受災(zāi)點(diǎn)的物資需求與配送車輛的載重限制作為前提條件，將運(yùn)輸路徑最短的配送方案作為應(yīng)急物流車輛路徑優(yōu)化問(wèn)題的初始解。

1.2 遺傳算法

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

遺傳算法具有全局搜索能力強(qiáng)、收斂速度快等優(yōu)點(diǎn)，但遺傳算法通過(guò)隨機(jī)方法產(chǎn)生初始解，搜索的難度更大，且局部搜索能力也存在不足。

1.3 大規(guī)模鄰域搜索算法

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

2 問(wèn)題描述

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

圖1 應(yīng)急物流車輛路徑優(yōu)化問(wèn)題示例圖

3 基于低碳排放的應(yīng)急物流車輛路徑優(yōu)化模型

3.1 模型已知條件

（1）假設(shè)每個(gè)受災(zāi)點(diǎn)僅由一輛車配送物資；

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

（3）假設(shè)配送車輛均為同一型號(hào)，其最大載重限制相同。

3.2 符號(hào)說(shuō)明

D：配送中心節(jié)點(diǎn)集合{i|i=1，2，…，m}；

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

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

c1：車輛的固定使用費(fèi)用；

c2：車輛的單位運(yùn)輸費(fèi)用；

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

oi：受災(zāi)點(diǎn)i最樂(lè)觀的需求量；

li：受災(zāi)點(diǎn)i最有可能的需求量；

pi：受災(zāi)點(diǎn)i最悲觀的需求量；

Qi：受災(zāi)點(diǎn)i的需求量；

dij：點(diǎn)i到點(diǎn)j的距離；

μ：車輛滿載時(shí)的燃油消耗率；

μ0：車輛空載時(shí)的燃油消耗率；

Mk：車輛k能負(fù)載的最大重量；

Mijk：車輛k從點(diǎn)i行駛到點(diǎn)j的載重量；

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

τ：碳排放量與燃油消耗量之間的轉(zhuǎn)換系數(shù)；

3.3 模型建立

考慮到應(yīng)急物流的特殊性與環(huán)境保護(hù)思想，為了在降低運(yùn)輸成本的同時(shí)盡量滿足受災(zāi)點(diǎn)的物資需求，并減少碳排放，本文以車輛的固定成本、車輛運(yùn)輸過(guò)程中產(chǎn)生的成本、未滿足需求的懲罰成本以及碳排放成本之和作為目標(biāo)函數(shù)構(gòu)建模型。

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

（2）配送車輛的運(yùn)輸成本

（3）未滿足需求的懲罰成本。在突發(fā)事故中，受災(zāi)點(diǎn)的需求量具有不確定性。因此，為盡量滿足受災(zāi)點(diǎn)的需求，保障救援工作的順利進(jìn)行，本文參考文獻(xiàn)[11]，利用三角模糊函數(shù)，通過(guò)最樂(lè)觀需求、最可能需求和最悲觀需求來(lái)估計(jì)需求量Qi。它們之間的關(guān)系見(jiàn)式（3）、式（4）。

采用加權(quán)法將三角模糊數(shù)轉(zhuǎn)化為某個(gè)數(shù)值，受災(zāi)點(diǎn)i的需求量Qi可以通過(guò)式（5）計(jì)算得到。

由于車輛和配送中心的容量限制，車輛運(yùn)送到受災(zāi)點(diǎn)的應(yīng)急物資數(shù)量可能會(huì)低于預(yù)計(jì)需求。因此，當(dāng)受災(zāi)點(diǎn)的需求沒(méi)有得到滿足時(shí)，將會(huì)產(chǎn)生一定的配送懲罰成本。懲罰成本可以表示為:

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

碳排放成本可以表示為：

（5）目標(biāo)函數(shù)：

約束條件：

式（10）表示各配送中心配送的物資總量不超過(guò)配送中心的容量；式（11）表示每個(gè)受災(zāi)點(diǎn)僅由單獨(dú)一輛車提供一次配送服務(wù)；式（12）表示每輛車在配送中心出發(fā)且僅服務(wù)于一個(gè)配送中心；式（13）表示每輛車在應(yīng)急物資配送完畢后重新返回配送中心。

4 混合遺傳算法設(shè)計(jì)

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

圖2 混合遺傳算法流程圖

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

（2）種群初始化。采用節(jié)約算法構(gòu)造問(wèn)題的初始解，高質(zhì)量的初始解可以在一定程度上降低遺傳算法的搜索難度，假設(shè)h是標(biāo)記第幾大距離節(jié)約值的位置，則具體步驟如下：

步驟一：將每個(gè)受災(zāi)點(diǎn)的配送任務(wù)分配給一輛單獨(dú)的車執(zhí)行；

步驟二：將每?jī)蓷l路徑融合并計(jì)算距離節(jié)約值，將距離節(jié)約值依據(jù)從高到低的順序排列；

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

步驟四：融合距離節(jié)約值第h大的兩條路徑，判斷是否存在某條路徑上僅有一個(gè)受災(zāi)點(diǎn)的情況，若存在，則重復(fù)執(zhí)行步驟三，否則輸出每輛車所途經(jīng)的受災(zāi)點(diǎn)的序號(hào)。

通過(guò)節(jié)約算法得到初始配送方案后，進(jìn)行種群的初始化。先把初始解按編碼方式轉(zhuǎn)換為個(gè)體，然后將種群的所有個(gè)體全部賦值為初始解轉(zhuǎn)換的個(gè)體。

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

（4）選擇操作。利用二元錦標(biāo)賽選擇法進(jìn)行選擇操作，操作過(guò)程就是比較兩個(gè)個(gè)體，然后選擇適應(yīng)度值更大的個(gè)體進(jìn)入子代種群。若種群數(shù)目為NIND，則循環(huán)NIND次，每次循環(huán)隨機(jī)選出兩個(gè)個(gè)體，在二者中選擇出適應(yīng)度值更大的個(gè)體。由于新選擇出的NIND個(gè)體中可能有重復(fù)個(gè)體，所以只保留重復(fù)個(gè)體中的一個(gè)個(gè)體，然后刪除其他重復(fù)個(gè)體。

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

圖3 交叉操作流程

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

圖4 變異操作流程

（7）局部搜索操作。運(yùn)用大規(guī)模鄰域搜索算法中“破壞”與“修復(fù)”的思想，即通過(guò)破壞算子按照相似性計(jì)算公式（15）從目前的解中移除若干受災(zāi)點(diǎn)，然后通過(guò)修復(fù)算子將被移除的受災(zāi)點(diǎn)插回讓目標(biāo)函數(shù)值增加值最少的位置。

破壞算子：按照式（15）、式（16）移除若干受災(zāi)點(diǎn)。

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

破壞算子的偽代碼見(jiàn)表1。

表1 破壞算子偽代碼

修復(fù)算子：修復(fù)算子的偽代碼見(jiàn)表2。

表2 修復(fù)算子偽代碼

（8）終止條件。達(dá)到最大迭代次數(shù)MAXGEN時(shí)，停止迭代，輸出問(wèn)題的最優(yōu)解。

5 算例分析

5.1 算例說(shuō)明

本文引用文獻(xiàn)[13]中應(yīng)急物流路徑問(wèn)題的分布數(shù)據(jù)，見(jiàn)表3、表4。存在3個(gè)配送中心與20個(gè)受災(zāi)點(diǎn)，各節(jié)點(diǎn)的位置信息已知，各節(jié)點(diǎn)之間的距離通過(guò)平面坐標(biāo)的歐氏距離簡(jiǎn)化表示。混合遺傳算法的參數(shù)設(shè)置見(jiàn)表5。

表3 配送中心相關(guān)數(shù)據(jù)

表4 受災(zāi)點(diǎn)相關(guān)數(shù)據(jù)

表5 參數(shù)表

5.2 算法比較

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

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

圖5 遺傳算法的優(yōu)化過(guò)程

圖6 混合遺傳算法的優(yōu)化過(guò)程

圖7 混合遺傳算法得到的最優(yōu)配送方案路線圖

遺傳算法與混合遺傳算法的優(yōu)化仿真結(jié)果對(duì)比見(jiàn)表6。

表6 仿真結(jié)果

5.3 結(jié)果比較

通過(guò)對(duì)比遺傳算法和混合遺傳算法的優(yōu)化過(guò)程可知，利用節(jié)約算法求初始解，利用大規(guī)模鄰域搜索算法改進(jìn)局部搜索操作的混合遺傳算法在迭代次數(shù)為42 次時(shí)達(dá)到最優(yōu)解，而遺傳算法在迭代次數(shù)為60次時(shí)達(dá)到最優(yōu)解，因此本文中的混合遺傳算法相較于傳統(tǒng)的遺傳算法具有更好的收斂性。對(duì)比遺傳算法與混合遺傳算法的優(yōu)化結(jié)果可知，混合遺傳算法在運(yùn)輸距離、總成本、碳排放成本上都取得了更好的結(jié)果。

6 結(jié)語(yǔ)

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

不過(guò)本文對(duì)于各受災(zāi)點(diǎn)需求量的預(yù)測(cè)方式過(guò)于簡(jiǎn)單。而在現(xiàn)實(shí)生活中，由于次生災(zāi)害、信息的滯后性等因素，受災(zāi)點(diǎn)的需求量呈現(xiàn)出更大的不確定性，配送車輛在運(yùn)輸過(guò)程中的交通條件也存在很多不確定因素，這些因素都會(huì)對(duì)應(yīng)急物流車輛路徑優(yōu)化的結(jié)果產(chǎn)生影響。因此，未來(lái)可更深入研究考慮更多不確定因素的應(yīng)急物流車輛路徑優(yōu)化問(wèn)題。