對城市煤炭供應(yīng)過程中煤炭運(yùn)輸車的路徑規(guī)劃

摘 要：針對城市煤炭運(yùn)輸過程中多配送站的車輛路徑規(guī)劃問題，須考慮行駛距離和實(shí)際裝載量對物流配送過程中車輛燃料消耗量和碳排放量的影響。首先，將燃料成本和碳排放成本考慮到總成本中，提出了以最小化物流成本和碳排放量的多目標(biāo)多配送站車輛路徑規(guī)劃問題，建立了該問題的混合整數(shù)規(guī)劃模型。其次，基于該模型特點(diǎn)，設(shè)計(jì)了改進(jìn)的化學(xué)反應(yīng)算法，對問題進(jìn)行求解。該算法采用兩部編碼和矩陣編碼方式，設(shè)計(jì)了基于貪婪搜索策略的種群初始化方法，并進(jìn)一步設(shè)計(jì)了4種化學(xué)反應(yīng)。最后，通過隨機(jī)產(chǎn)生數(shù)據(jù)進(jìn)行數(shù)值實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明：車輛多行駛較短的距離可以降低碳排放量，這為兼顧物流成本和碳排放量的多配送站車輛配送問題提供了方法指導(dǎo)。

關(guān)鍵詞：城市煤炭運(yùn)輸;碳排放;多配送站車輛路徑規(guī)劃問題;貪婪搜索策略;改進(jìn)化學(xué)反應(yīng)算法

中圖分類號(hào)：TP301.6;TD561

文獻(xiàn)標(biāo)識(shí)碼： A

文章編號(hào)"1000-5269（2020）05-0089-06"""DOI：10.15958/j.cnki.gdxbzrb.2020.05.14

煤礦是我國非常重要的能源[1]，城市煤炭供應(yīng)關(guān)乎著城市工業(yè)的發(fā)展。如何調(diào)配車輛進(jìn)行煤炭運(yùn)輸是一個(gè)值得研究的車輛路徑規(guī)劃問題（vehicle routing problem，VRP）。為提高運(yùn)輸系統(tǒng)的運(yùn)行效率和服務(wù)水平，通常會(huì)設(shè)置多個(gè)城市煤炭配送中心。因此，解決多配送站情況下的車輛路徑規(guī)劃問題（multi-depot vehicle routing problem，MDVRP）具有重要的實(shí)際意義。RENAUD等[2]以最小化總物流成本為目標(biāo)，提出以車輛容量和行駛里程為約束條件的MDVRP，并設(shè)計(jì)了禁忌搜索算法進(jìn)行求解。KUO等[3]針對具有裝載成本的MDVRP，設(shè)計(jì)了三階段的變領(lǐng)域搜索算法進(jìn)行求解。RAN等[4]研究了多承運(yùn)商合作情形下的MDVRP，并提出一種兩階段貪婪啟發(fā)式算法。

從現(xiàn)有的研究來看，針對最小化碳排放量的車輛路徑規(guī)劃問題的研究多考慮單個(gè)配送站的情形，而對于多配送站的物流配送系統(tǒng)下的車輛路徑規(guī)劃問題研究較少。多配送站是物流配送系統(tǒng)中普遍使用的配送方式。因此，研究多個(gè)配送站情形下以最小化碳排放量為目標(biāo)的車輛路徑規(guī)劃問題更具有實(shí)際意義?？紤]到車輛的碳排放與行駛里程和實(shí)際載重量具有正相關(guān)關(guān)系[5-6]，將燃料成本和碳排放成本考慮到總物流成本中，提出了以最小化物流成本和行駛距離的多目標(biāo)多配送站車輛路徑規(guī)劃問題，建立了該問題的混合整數(shù)規(guī)劃模型。進(jìn)一步針對問題特點(diǎn)，設(shè)計(jì)了化學(xué)反應(yīng)算法進(jìn)行求解。仿真實(shí)驗(yàn)結(jié)果表明，該算法可以有效地解決所提出的問題。

1"問題描述和模型構(gòu)建

1.1"問題描述

一個(gè)城市煤炭配送系統(tǒng)有m個(gè)配送中心，n個(gè)消耗點(diǎn)。配送車輛的最大載重量為Q，考慮到車輛油耗和司機(jī)工作負(fù)荷的約束，配送車輛的行駛距離不超過L。要求在滿足車輛載重和行駛距離的約束條件下，合理地安排配送車輛和車輛的行駛路徑，從而最小化車輛配送的物流成本和行駛距離。一個(gè)可行的配送方案需要滿足如下條件：

（1）每個(gè)配送中心的車輛數(shù)目均是有限的。

（2）車輛只能從配送中心出發(fā)，沿著1條配送路線將裝載的貨物送達(dá)指定煤炭消耗點(diǎn)，并最終回到原配送中心。

（3）1輛配送車輛可以服務(wù)多個(gè)煤炭消耗點(diǎn)，但每個(gè)煤炭消耗點(diǎn)僅被1輛車服務(wù)1次。

（4）每輛車有容量和最大行駛距離的約束，所有的配送車輛均是同質(zhì)的。為建立該問題的數(shù)學(xué)模型，對符號(hào)定義如下：

1.2"符號(hào)定義

1.3"車輛碳排放量刻畫方法

已有的研究成果表明，車輛的碳排放量與燃料消耗量具有正相關(guān)關(guān)系，因此可以利用燃料消耗量刻畫其碳排放量[7-8]?？紤]到車輛的實(shí)際載重量和行駛距離與燃料消耗量的關(guān)系，本文采用如下的方法計(jì)算燃料消耗量：

其中，F(xiàn)E表示單位燃料消耗釋放的碳排放量。

1.4"多目標(biāo)MDVRP模型

根據(jù)上述符號(hào)定義和碳排放量計(jì)算方法，最小化物流成本和行駛距離的MDVRP模型如下：

其中：目標(biāo)函數(shù)（3）表示最小物流配送成本，包括固定成本、燃料消耗成本、碳排放成本3個(gè)部分;目標(biāo)函數(shù)（4）表示最小化總行駛距離;式（5）和（6）表示1輛車1次只能服務(wù)1個(gè)煤炭消耗點(diǎn);式（7）保證車輛行駛的連續(xù)性，即服務(wù)完消耗點(diǎn)i之后才能為消耗點(diǎn)j提供服務(wù);式（8）和（9）分別表示車輛的容量約束和行駛里程約束;式（10）和（11）表示車輛的可用性限制，即確定車輛k是否被使用;式（12）至（14）表示車輛行駛在邊（i，j）上的載重量限制;式（15）表示0～1變量xijk，當(dāng)車輛k行駛在路徑（i，j）上時(shí)xijk=1，否則為0。

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

VRP是一類典型的NP-hard問題，國內(nèi)外學(xué)者通常采用啟發(fā)式或亞啟發(fā)式算法進(jìn)行求解[9-13]。MDVRP具有多個(gè)配送中心，具有更高的復(fù)雜性，且本文提出的問題具有多目標(biāo)特征，因此，也為NP-hard問題。LAM and LI[14]受到化學(xué)反應(yīng)中分子之間相互作用以尋求勢能面中最低勢能的啟發(fā)，提出了化學(xué)反應(yīng)優(yōu)化算法（chemical"reaction optimization，CRO），已經(jīng)成為求解組合優(yōu)化問題的重要方法。

CRO模擬化學(xué)反應(yīng)中分子碰撞以求達(dá)到穩(wěn)定狀態(tài)的特性，即分子勢能達(dá)到最低。具體來說，化學(xué)反應(yīng)中的分子經(jīng)歷4個(gè)反應(yīng)，分別為單分子無效碰撞、分解反應(yīng)、分子間無效撞擊以及分子合成反應(yīng)，且在反應(yīng)前后遵循能量守恒定律。本文針對所提出的問題特點(diǎn)，采用矩陣編碼法和兩部編碼法兩種編碼方式，設(shè)計(jì)了基于貪婪搜索策略的種群初始化方法，進(jìn)一步設(shè)計(jì)了4種化學(xué)反應(yīng)。所提出的算法設(shè)計(jì)如下：

2.1"解的表達(dá)

2.1.1"兩部編碼法

兩部編碼法中，每個(gè)解的編碼由兩部分組成，其結(jié)構(gòu)為：配送車輛服務(wù)的消費(fèi)者數(shù)量+消費(fèi)者服務(wù)順序序列。如圖1所示，倉庫1中的配送車輛2服務(wù)4個(gè)消費(fèi)者，其服務(wù)的順序?yàn)?→5→8→3;車輛的行駛路線為：倉庫1→2→5→8→3→倉庫1，即來自倉庫1中的2號(hào)配送車從倉庫出發(fā)，依次服務(wù)完消費(fèi)者2、5、8、3，最終回到倉庫1。

2.1.2"矩陣編碼法

矩陣編碼法采用矩陣的形式進(jìn)行編碼。首先將MDVRP轉(zhuǎn)化為多個(gè)VRP，然后分配車輛，設(shè)計(jì)行駛路線。如圖2所示，倉庫1和倉庫2各有2輛配送車，每輛配送車在滿足容量和行駛里程約束的情況下執(zhí)行配送任務(wù)。如倉庫1中的配送車輛1為消耗點(diǎn)4、7提供配送服務(wù)，配送路線為：倉庫1→4→7→倉庫1。

2.2"算法步驟

2.2.1"初始化階段

初始化階段主要分為兩步：算法參數(shù)的初始化及種群個(gè)體的初始化。

步驟1

算法參數(shù)的初始化。關(guān)于CRO的參數(shù)符號(hào)、具體意義以及本文中采用的數(shù)值如表1所示。

步驟2"種群的初始化。為了提高解的質(zhì)量，減少求解時(shí)間，以貪婪搜索策略初始化種群個(gè)體。首先，根據(jù)各個(gè)煤炭消耗點(diǎn)與各配送中心的距離分配消耗點(diǎn)到最近的配送中心;其次，按照掃描法對配送中心的消耗點(diǎn)安排配送車輛;最后，調(diào)整每輛車所服務(wù)的煤炭消耗點(diǎn)先后順序。

2.2.2"單分子無效碰撞

單分子無效碰撞是指單個(gè)分子撞擊容器壁而得到一個(gè)新分子的過程，即ω→ω′。反應(yīng)后，一部分的分子勢能將傳遞到中央能量緩沖器中。求解本文模型時(shí)，單分子無效碰撞采用隨機(jī)插入算子。具體來說，隨機(jī)選中一個(gè)個(gè)體基因，將該基因從基因序列中刪除，然后隨機(jī)將該基因插入到其他位置。如設(shè)基因序列為：1|4|7|2|5|8|3|6|9|，選中基因2，在原基因序列中刪除該個(gè)體基因，得到1|4|7|5|8|3|6|9|，然后將其插入到另一位置。假設(shè)插入到基因3之前，那么得到新的基因序列為：1|4|7|5|8|2|3|6|9|。

2.2.3"分解反應(yīng)

分解反應(yīng)指當(dāng)一個(gè)分子撞擊到容器時(shí)，分子分解為多個(gè)分子（為了簡化，默認(rèn)分解為兩個(gè)分子）。假設(shè)分子撞擊容器后，分解為分子ω′1和分子ω′2，即有：ω→ω′1+ω′2。這里，產(chǎn)生新分子的算子采用交換算子。如設(shè)基因序列為：1|4|7|2|5|8|3|6|9|，隨機(jī)選擇兩個(gè)不同位置的基因，對兩個(gè)基因進(jìn)行交換，如選中基因2和3，那么實(shí)行交換后的基因序列為：1|4|7|3|5|8|2|6|9|。同樣地，分子ω′2也可以得到。

2.2.4"分子間無效撞擊

當(dāng)多個(gè)分子（這里假設(shè)兩個(gè)分子）相互撞擊時(shí)，發(fā)生分子無效撞擊反應(yīng)，即有ω1+ω2→ω′1+ω′2。這個(gè)反應(yīng)與單分子無效撞擊反應(yīng)非常相似，具體有ω′1=N（ω1），ω′2=N（ω2）。這里，分子間無效撞擊采用倒置算子產(chǎn)生新分子。設(shè)基因序列為：1|4|7|2|5|8|3|6|9|，在基因序列中隨機(jī)選擇一段基因子序列，并對其進(jìn)行倒置，如選中2|5|8|3|基因序列，實(shí)行倒置算子后得到的個(gè)體基因序列為：1|4|7|3|8|5|2|6|9|。同樣地，分子ω′2也可以得到。

2.2.5"分子合成反應(yīng)

與化學(xué)反應(yīng)中的合成反應(yīng)類似，化學(xué)反應(yīng)優(yōu)化算法中多個(gè)分子合成一個(gè)新的分子（為了簡化，這里假設(shè)兩個(gè)分子合成一個(gè)分子），即有：ω1+ω2→ω′。顯然，通過允許兩分子ω1和ω2合成一個(gè)分子ω′的形式，使得新分子ω′在分子結(jié)構(gòu)上與兩個(gè)分子ω1和ω2形成了較大的差別，繼而能夠使新分子“探索”一個(gè)新的搜索區(qū)域，避免陷入局部最優(yōu)。本文采用最優(yōu)成本交叉（best cost crossover）反應(yīng)算子。具體來說，隨機(jī)從父代1和父代2中選擇一個(gè)基因，在父代2中刪除選中的父代1的基因，然后將父代1中選中的基因插入到父代2中，其中插入位置為能夠使得父代2的勢能值降低最多的位置，得到子代1。類似地，可得到子代2。最后從兩個(gè)子代中隨機(jī)選擇一個(gè)較優(yōu)的子代作為ω′。

3"實(shí)例分析

本部分隨機(jī)選取初始化數(shù)據(jù)進(jìn)行數(shù)值實(shí)驗(yàn)。假設(shè)有4個(gè)配送中心，每個(gè)配送中心均有2輛配送車，每輛車的最大載重量和最大行駛距離分別為120 kg和400 km，48個(gè)客戶的位置在[-50，50]區(qū)間內(nèi)隨機(jī)產(chǎn)生，消耗點(diǎn)的需求量在[5，25]內(nèi)隨機(jī)產(chǎn)生。配送中心和客戶信息分別如表2、表3所示：

根據(jù)SUZUKI[6]，令ρ0=1，ρ=2;同時(shí)，F(xiàn)ACTS E[15]通過研究指出每升燃料消耗釋放2.32 kg的碳排放量，單位碳排放成本為2元，配送車輛每天的固定成本為500元，車輛配送中單位變動(dòng)成本為7.56元。

3.1"物流成本目標(biāo)求解結(jié)果

為了驗(yàn)證貪婪搜索策略的有效性，并對比兩種編碼方式的優(yōu)劣，基于化學(xué)反應(yīng)算法的基本框架，本文采用3種求解算法求解模型。

如表4所示，在編碼方式上，算法CRO1采用兩部編碼法，算法CRO2和算法ICRO（improve chemical reaction optimization）采用矩陣編碼法;初始化階段，ICRO采用2.2.1提出的貪婪搜索策略，而CRO1和CRO2均采用隨機(jī)初始化方式?？紤]到元啟發(fā)式算法在尋優(yōu)過程中具有一定的隨機(jī)性，每個(gè)算法各運(yùn)行10次，將求解結(jié)果和CPU耗時(shí)匯總在表5中。

由表5可以得到，CRO1和CRO2求解結(jié)果相差不大，CRO2求解均值比CRO1降低了1.4%，而CPU時(shí)間降低了17.5%。這可能是因?yàn)閮刹烤幋a法需要在求解過程中對行駛路線進(jìn)行分割而得到每輛車的行駛路線，而矩陣編碼方式在初始化階段就將多配送站轉(zhuǎn)化為單配送站進(jìn)行求解，降低了問題求解規(guī)模，并且MDVRP經(jīng)過轉(zhuǎn)化后得到的多個(gè)VRP問題能夠?qū)崿F(xiàn)并行求解，節(jié)省了求解時(shí)間。

ICRO算法相比前兩種求解方法，在最小值、最大值、平均值、方差以及CPU時(shí)間5個(gè)維度上均表現(xiàn)出了優(yōu)勢。其中平均值分別提高了32.6%和335%。出現(xiàn)較大差距的原因在于CRO1和CRO2均采用隨機(jī)初始化，車輛使用數(shù)為8輛。而ICRO算法在初始化階段按照車輛的實(shí)際載荷以及消耗點(diǎn)與配送站的距離安排車輛，在這種方式下，ICRO算法得到的求解結(jié)果中，僅使用了7輛車就完成了配送服務(wù)，這樣就減少了1輛配送車的成本支出。顯然，這對于物流公司來說意味著可以通過合理地設(shè)置配送中心的位置，實(shí)現(xiàn)成本費(fèi)用的節(jié)省。另外，可以看到，在CPU時(shí)間上3個(gè)算法求解結(jié)果依次遞減，也說明貪婪搜索策略相比隨機(jī)初始化的求解效率高。最后，從10次求解結(jié)果的標(biāo)準(zhǔn)差也可以發(fā)現(xiàn)，ICRO算法相對來說比較穩(wěn)定，魯棒性較好。

3.2"兩種優(yōu)化目標(biāo)求解結(jié)果對比

由3.1可知，ICRO算法相比前兩種算法，減少了1輛配送車的成本開支，而配送48個(gè)消費(fèi)者至少需要7輛車才能完成配送任務(wù)。另外，注意到碳排放量和燃料消耗量存在一定的比例關(guān)系，燃料消耗量的減少也必然使得碳排放減少，故令目標(biāo)函數(shù)（3）中的參數(shù)Cf=0，φ=0，Cv=1，分別以最小燃料消耗和最短行駛里程為優(yōu)化目標(biāo)，以探討配送路線數(shù)目一定的基礎(chǔ)上最小燃料消耗和最短行駛里程兩種目標(biāo)的差異。同樣地，為了避免算法的隨機(jī)性，算法各運(yùn)行10次（記最小燃料消耗為F′;最短行駛里程為d），最終求解結(jié)果如表6所示。

表6中的第二行、第三行為以最小燃料消耗為目標(biāo)計(jì)算得到的燃料消耗量和行駛里程;類似地，第四行和第五行則為以最短行駛里程為目標(biāo)得到的燃料消耗量和行駛里程;燃料消耗量偏差值和行駛里程偏差值分別定義如下：

其中：SF′表示燃料消耗量偏差;F′*表示在設(shè)定目標(biāo)為最小燃料消耗的情況下所得到的燃料消耗量;F′d表示在設(shè)定目標(biāo)為最短行駛里程的情況下所得到的燃料消耗量;Sd表示行駛里程偏差值;dF′表示設(shè)定目標(biāo)為最小燃料消耗所得到的行駛里程;d*表示設(shè)定目標(biāo)為最短行駛里程所得到的最優(yōu)行駛里程。

由表6可以看到，當(dāng)初始目標(biāo)設(shè)定為最小燃料消耗，10次運(yùn)行結(jié)果的最小值為1 727.49 L;而在最小行駛里程目標(biāo)下，燃料消耗量最小則為1 735.11 L;二者的燃料消耗量偏差值為7.62 L;平均值和最大值分別增加了24.79 L和38.20 L;可以發(fā)現(xiàn)每增加14.26 km的行駛里程，就可以節(jié)省燃料消耗7.62 L;理論上多行駛53.34 km的里程，可以減少2.20%的燃料消耗量。盡管降低幅度有限，但對大型物流配送企業(yè)來說，可以節(jié)約巨大的物流成本。而且，從環(huán)境保護(hù)的角度分析，例如燃料消耗大國美國每年的燃料消耗360億 L，按照碳排放2.32 kg/ L計(jì)算，節(jié)省2.20%的燃料消耗將降低1837億kg碳排放量。

4"結(jié)論

本文在低碳物流快速發(fā)展的背景下，充分考慮燃料消耗和碳排放量，構(gòu)建多目標(biāo)MDVRP模型，并采用改進(jìn)后的化學(xué)反應(yīng)算法對問題模型進(jìn)行求解，完成了以下工作：

（1）構(gòu)建了基于行駛路徑和實(shí)際載重量的燃料消耗模型，并進(jìn)一步建立了碳排放模型，為煤炭配送過程中燃料成本、碳排放量的計(jì)算以及燃料消耗成本的優(yōu)化設(shè)計(jì)提供了工具。

（2）對比分析了兩種優(yōu)化目標(biāo)下的燃料消耗量和行駛里程。研究結(jié)果表明：可以多行駛一定的路徑而降低燃料的使用，為降低燃料成本和低碳物流配送規(guī)劃問題提供方法指導(dǎo)。

（3）構(gòu)建了多配送站的物流配送路徑規(guī)劃模型，應(yīng)用兩部編碼和矩陣編碼兩種編碼方式，設(shè)計(jì)了貪婪搜索策略初始化種群個(gè)體，并進(jìn)一步地設(shè)計(jì)了4種化學(xué)反應(yīng)算法，為求解MDVRP等NP-hard問題提供了參考。

參考文獻(xiàn)：

[1]林川， 武樂飛， 戴家佳. 基于類別關(guān)鍵詞權(quán)重的煤礦安全隱患分類方法[J]. 貴州大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2019， 36（6）： 53-57， 97.

[2]RENAUD J，"BOCTOR F F，"LAPORTE G."An improved petal heuristic for the vehicle routeing problem[J]."Journal of the Operational Research Society，"1996，"47（2）： 329-336.

[3]KUO Y，"WANG C C."A variable neighborhood search for the multi-depot vehicle routing problem with loading cost[J]."Expert Systems with Applications，"2012，"39（8）："6949-6954.

[4]LIU R，"JIANG Z，"FUNG R Y K，"et al."Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration[J]."Computers amp; Operations Research，"2010，"37（5）："950-959.

[5]鄒建城， 路正南. 考慮碳排放的生鮮農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[J]. 物流科技， 2019， 42（8）： 46-52.

[6]SUZUKI"Y."A dual-objective metaheuristic approach to solve practical pollution routing problem[J]."International Journal of Production Economics，"2016，"176： 143-153.

[7]JABIR E，"PANICKER"V V，"SRIDHARAN R."Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem[J]."Transportation Research Part D："Transport and Environment，"2017，"57："422-457.

[8]LI J，"WANG D，"ZHANG J."Heterogeneous fixed fleet vehicle routing problem based on fuel and carbon emissions[J]."Journal of Cleaner Production，"2018，"201："896-908.

[9]GAREY M R，"JOHNSON D S."Computers and intractability[M]."New York："W."H."Freeman，"2002.

[10]H M H，"BOSTEL N，"LANGEVIN A，"et al."An exact algorithm and a metaheuristic for the generalized vehicle routing problem with flexible fleet size[J]."Computers amp; Operations Research，"2014，"43："9-19.

[11]戴冉， 鄭長江， 鄭樹青， 等. 共享?xiàng)l件下的地下物流配送路線優(yōu)化[J]. 貴州大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2018， 35（4）： 117-121.

[12]PODGORELEC V."A survey of genetic algorithms for solving multi depot vehicle routing problem[J]."Applied Soft Computing"Journal，"2015，"27（C）： 519-532.

[13]BAE H，nbsp;MOON I."Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles[J]."Applied Mathematical Modelling，"2016，"13（40）："6536-6549.

[14]LAM A，"LI V."Chemical reaction"optimization："a tutorial[J]."Memetic Computing，"2012，"4（1）： 3-17.

[15]FACTS E."Average"carbon"dioxide emissions resulting"from gasoline and"diesel fuel[R]."Washington："US EPA，"2005.

（責(zé)任編輯：曾"晶）