何康佳，何 玲，馮 磊，張光星

( 貴州大學 現(xiàn)代制造技術教育部重點實驗室，貴州 貴陽 550025)

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

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

1 問題描述和模型構建

1.1 問題描述

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

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

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

(3)1輛配送車輛可以服務多個煤炭消耗點，但每個煤炭消耗點僅被1輛車服務1次。

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

1.2 符號定義

(1)集合

C：消耗點索引集合，C={c1,c2,…,cn}，n個消耗點數(shù)量；

D：配送中心索引集合，D={d1,d2,…,dm}，m個配送站數(shù)量；

N：配送站和消耗點索引集合，N=C∪D；

K：配送車輛索引集合，K={k1,k2,…,km}。

(2)參數(shù)

qi：消耗點i的需求量(0≤qi≤Q)；

dij：任意兩點i和j之間的歐式距離，i,j=1,2,…,n,…,m+n；

ω：配送車輛空車凈重；

Q：配送車輛的最大裝載量；

L：配送車輛的最大行駛距離；

Cf：每輛車的固定成本(包括車輛租賃費、車輛保險費以及司機工資等)；

Cv：車輛單位燃料成本；

φ：單位碳排放的成本。

(3)決策變量

xijk：如果車輛k經(jīng)過(i,j)值為1，否則為0；

fijk：配送車輛k經(jīng)過(i,j)時的貨物裝載量。

1.3 車輛碳排放量刻畫方法

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

(1)

其中：ρ*和ρ0分別為車輛滿載和空載時的燃料消耗率；Fij表示車輛經(jīng)過路徑(i,j)的燃料消耗量。因此，根據(jù)碳排放量與燃料消耗量之間的關系，車輛的碳排放量計算方法如下：

Eij=FE·Fij。

(2)

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

1.4 多目標MDVRP模型

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

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

fijk≤(Qk-qi)xijk，?i∈N,?j∈D,?k∈K；

(14)

xijk∈{0,1}。

(15)

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

2 算法設計

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

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

2.1 解的表達

2.1.1兩部編碼法

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

圖1 兩部編碼示意圖Fig.1 Schematic diagram of two encodings

2.1.2矩陣編碼法

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

2.2 算法步驟

2.2.1初始化階段

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

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

圖2 矩陣制編碼示意圖Fig.2 Schematic diagram of matrix coding

表1 化學反應算法的參數(shù)設置Tab.1 Parameter setting of chemical reaction algorithm

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

2.2.2單分子無效碰撞

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

2.2.3分解反應

2.2.4分子間無效撞擊

2.2.5分子合成反應

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

3 實例分析

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

表2 配送中心信息Tab.2 Distribution center information

表3 消耗點信息(需求量/kg)Tab.3 Consumption point information (quantity demanded kg)

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

3.1 物流成本目標求解結果

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

表4 3種算法的詳細信息Tab.4 Details of the three algorithms

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

表5 3種算法得到的求解結果對比Tab.5 Comparison of solution results obtained by the three algorithms

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

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

3.2 兩種優(yōu)化目標求解結果對比

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

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

SF′=F′*-Fd；

Sd=dF′-d*。

表6 兩種優(yōu)化目標下的求解結果Tab.6 Results of the two optimization objectives

由表6可以看到，當初始目標設定為最小燃料消耗，10次運行結果的最小值為1 727.49 L；而在最小行駛里程目標下，燃料消耗量最小則為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)境保護的角度分析，例如燃料消耗大國美國每年的燃料消耗360億 L，按照碳排放2.32 kg/ L計算，節(jié)省2.20%的燃料消耗將降低18.37億kg碳排放量。

4 結論

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

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

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

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