模糊需求下綠色同時取送貨問題與算法研究

馬艷芳，應(yīng) 斌，康 凱，欒新鳳

河北工業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，天津 300401

1 引言

目前，全球氣候變暖問題日益突出，溫室氣體排放問題受到廣泛關(guān)注。在1992 年制定的《聯(lián)合國氣候變化框架公約》中建立了應(yīng)對未來數(shù)十年氣候變化的長效機(jī)制。于2005年正式生效的《京都議定書》使得減少溫室氣體的排放量成為了發(fā)達(dá)國家的法律義務(wù)。同時，我國政府承諾到2020 年，我國二氧化碳排放量同比2005年減少50%～60%。十八屆五中全會提出了“創(chuàng)新、協(xié)調(diào)、綠色、開放、共享”的發(fā)展理念，其中綠色是永續(xù)發(fā)展的必要條件。而交通運(yùn)輸業(yè)是溫室氣體的主要來源之一，其中物流運(yùn)輸占交通運(yùn)輸業(yè)碳排放量的比重最大，面臨著巨大的減排壓力。因此，減少物流運(yùn)輸作業(yè)中的碳排放量，實(shí)現(xiàn)綠色物流具有極強(qiáng)的現(xiàn)實(shí)意義。

近幾年，車輛調(diào)度問題的低碳化研究已經(jīng)引起了學(xué)者們的廣泛關(guān)注。Sbihi 等[1]認(rèn)為對傳統(tǒng)車輛調(diào)度問題的研究目標(biāo)不應(yīng)局限于經(jīng)濟(jì)效益，還應(yīng)考慮環(huán)境和社會因素，以有效減少碳排放。Palmer[2]研究速度與二氧化碳排放的關(guān)系，建立運(yùn)輸車輛的集成路徑調(diào)度和碳排放模型。Demir等[3]認(rèn)為運(yùn)輸車輛的油耗量與車速、加速度和載重等多個參數(shù)有關(guān)，進(jìn)而影響碳排放量。Bektas等[4]綜合研究多目標(biāo)車輛調(diào)度問題，包括負(fù)載、油耗、溫室氣體、旅行時間、距離、成本，并權(quán)衡了各目標(biāo)之間的關(guān)系，提出車輛調(diào)度問題有很大的減排空間。張春苗[5]建立低碳-定位車輛調(diào)度模型，并證明該模型能有效減少運(yùn)輸中的碳排放，但會使總成本增加。李順勇等[6]基于多通路時變網(wǎng)絡(luò)研究低碳車輛調(diào)度優(yōu)化。史春陽[7]研究公路運(yùn)輸中油耗與CO2排放量的計(jì)算體系，并在此基礎(chǔ)上重點(diǎn)研究同時取送貨車輛調(diào)度問題（Vehicle Routing Problem with Simultaneous Pickup and Delivery，VRPSPD）中CO2減排因素對調(diào)度規(guī)劃的影響。李進(jìn)等[8]研究低碳環(huán)境下的車輛調(diào)度問題，提出使用中低的車輛速度有利于減少碳排放量。唐金環(huán)等[9]在時變網(wǎng)絡(luò)下對含旅行時間和碳排放的多目標(biāo)車輛調(diào)度優(yōu)化問題進(jìn)行研究。趙燕偉等[10]對多車型VRPSPD 問題進(jìn)行了低碳路徑研究。葛顯龍等[11]研究開放式污染路徑問題，提出碳排放計(jì)算方法，并建立了優(yōu)化模型。以上文獻(xiàn)研究了低碳條件下的車輛調(diào)度問題，促進(jìn)了綠色物流的發(fā)展。然而，目前對綠色物流的研究往往只考慮了傳統(tǒng)車輛調(diào)度問題下的碳排放問題，缺乏對顧客需求不確定性和同時取送貨情況的考慮。

車輛調(diào)度問題是典型的NP 難題，通常采用啟發(fā)式算法求解。符卓等[12]針對需求可離散拆分的車輛調(diào)度問題，提出具有特殊操作的禁忌搜索算法，增強(qiáng)算法搜索性能。謝九勇等[13]設(shè)計(jì)自適應(yīng)禁忌搜索算法以求解帶多軟時間窗的車輛調(diào)度問題。潘雯雯[14]基于路徑優(yōu)化和路徑改進(jìn)，提出兩階段算法。張濤等[15]對蟻群算法進(jìn)行改進(jìn)，引入最大最小螞蟻系統(tǒng)和基于排序的螞蟻系統(tǒng)，并改進(jìn)啟發(fā)因子和初始化，以研究帶車輛行程約束的VRPSPD。陳希瓊等[16]針對多目標(biāo)VRPSPD 問題，構(gòu)造嵌入禁忌表的多目標(biāo)蟻群算法求解。郭海湘等[17]基于單車場多車型提出三種混合算法，通過比較發(fā)現(xiàn)混合蟻群算法性能更優(yōu)。葛顯龍等[11]設(shè)計(jì)并改進(jìn)自適應(yīng)遺傳算法，以求解開放式污染車輛調(diào)度問題。李進(jìn)等[8]對低碳環(huán)境下的車輛調(diào)度問題，設(shè)計(jì)基于路徑劃分的禁忌搜索算法，采用三種鄰域搜索方法。然而，單一算法一般都具有一定的局限性，如遺傳算法易陷入早熟早收斂，禁忌算法對初始解依賴性較強(qiáng)，模擬退火算法對初始參數(shù)設(shè)置較敏感，蟻群算法收斂效率較低。近年來，學(xué)者對混合算法的研究逐漸深入，以克服單一算法的局限性。李陶深等[18]提出遺傳算法與禁忌搜索算法的混合策略，并應(yīng)用于VRPTW（Vehicle Routing Problem with Time Windows）問題。余麗等[19]將遺傳算法與禁忌搜索算法相結(jié)合，以優(yōu)化旅行商路徑問題?；旌纤惴ú呗韵鄬τ趩我凰惴ň哂忻黠@的優(yōu)勢，取得了不錯的效果。

筆者梳理相關(guān)文獻(xiàn)，選取近五年相關(guān)文獻(xiàn)，選擇與車輛調(diào)度主題完全契合文獻(xiàn)，剔除同一作者相近題目，表1總結(jié)了車輛調(diào)度問題中與不確定環(huán)境、同時取送貨和低碳相關(guān)研究。從表1 中可以發(fā)現(xiàn)有較多關(guān)于低碳與同時取送貨的單一研究，關(guān)于模糊需求的研究較少，僅極少的文獻(xiàn)研究了低碳取送貨問題或模糊環(huán)境下的同時取送貨問題。同時取送貨車輛調(diào)度問題在傳統(tǒng)的VRP（Vehicle Routing Problem）中考慮了顧客的取貨需求，同時安排了送貨與取貨，從而降低了車輛的空載行駛里程，以追求成本最小。模糊需求車輛調(diào)度問題（Vehicle Routing Problem with Fuzzy Demand，VRPFD）考慮了客戶需求的模糊性，把客戶的需求量設(shè)置為三角模糊數(shù)，使該問題更符合實(shí)際情況。考慮碳排放的車輛調(diào)度問題（Low-Carbon Routing Problem，LCRP）在傳統(tǒng)的VRP中考慮了社會經(jīng)濟(jì)效益，從經(jīng)濟(jì)車速、交通條件、道路條件、天氣狀況等因素考慮，降低配送過程中油耗和碳排放，實(shí)現(xiàn)低碳運(yùn)輸。本文在同時取送貨問題研究中，考慮了低碳運(yùn)輸和顧客模糊需求，提出了以碳排放、油耗、服務(wù)總成本最低為目標(biāo)的同時取送貨車輛調(diào)度問題。隨后，提出改進(jìn)的混合算法策略，即遺傳禁忌搜索算法（Genetic Algorithm with Tabu Search，GA-TS）求解該問題，以避免單一算法局限性。算法中，將懲罰因子引入適應(yīng)度函數(shù)，處理違反約束的染色體；采用結(jié)合精英策略的選擇算子，加速向最優(yōu)解收斂；提出結(jié)合禁忌搜索算法的變異算子，提高算法的局部搜索能力。

表1 相關(guān)文獻(xiàn)簡明綜述

2 問題描述及模型構(gòu)建

模糊需求下綠色同時取送貨車輛調(diào)度問題描述如下：配送中心使用單一類型的車輛給客戶服務(wù)，同時滿足顧客的取送貨需求，且客戶需求具有一定的模糊性。每輛車必須從配送中心出發(fā)，完成任務(wù)后返回配送中心不再服務(wù)，且每個客戶只能訪問一次。目標(biāo)函數(shù)不僅考慮了與時間相關(guān)的服務(wù)成本，還考慮了油耗、碳排放成本，以此進(jìn)行合理的路徑規(guī)劃，使總成本最小。另外，為了便于建模和求解，進(jìn)行以下條件限制：只有一個配送中心；客戶的具體信息已知，包括客戶位置、服務(wù)時間等；車輛最大裝載量能同時滿足任意客戶的兩種需求；貨車總數(shù)量能滿足所有顧客的總需求；每個顧客有且僅有一次被服務(wù)。

2.1 期望模糊需求

現(xiàn)實(shí)生活中，客戶往往很難給出一個十分精確的需求量及取貨量。相反，客戶往往會依據(jù)經(jīng)驗(yàn)給出一個大致的范圍，在范圍中取一個最可能的值，這帶有很大的模糊性。比如：本月的需求量在1.0 噸到1.5 噸之間，最可能的值是1.3噸。因此，本文引入了模糊變量，把需求設(shè)置為三角模糊數(shù)，將模糊不確定的需求轉(zhuǎn)化為確定的數(shù)值。設(shè)需求最小值為三角模糊數(shù)的下界a，需求的最大值為三角模糊數(shù)的上界b，最可能需求量c為三角模糊數(shù)的中間值。因此，可以將客戶i的需求通過三角模糊數(shù)表示為(ai,ci,bi)。

不確定變量的處理是一個較為復(fù)雜的問題，本文采用期望值處理模糊需求，相關(guān)理論見下文。不妨設(shè)A為三角模糊數(shù)，A=(a,c,b)，其中0 ＜a≤c≤b，其隸屬度函數(shù)如下：

其中，a、b分別為三角模糊數(shù)的下限和上限，c為三角模糊數(shù)最有可能的取值，隸屬函數(shù)圖見圖1。

圖1 隸屬函數(shù)圖

定義1[26]模糊數(shù)A的期望區(qū)間的中心稱為這個數(shù)的期望值EV(A)，即：

引理1[26]設(shè)A是邊為fA和gA的三角模糊數(shù)A=(a,c,b)，區(qū)間隨機(jī)集S∈RI(A)，那么：

由定義1及引理1，本文得出如下推論。

推論 設(shè)A是邊為fA和gA的三角模糊數(shù)A=(a,c,b)，則其期望值表示如下：

證明 由定積分的幾何意義可知，ES1和ES2中的定積分部分分別為三角形Δacd和三角形Δdcb的面積，因此：

進(jìn)而推得：

從而，將模糊需求量轉(zhuǎn)化為期望值。

2.2 碳排放計(jì)算方法

直接測量碳排放量不太現(xiàn)實(shí)，通常人們根據(jù)油耗量估計(jì)碳排放量。根據(jù)Esteves-Booth等[27]研究表明，油耗量與碳排放成正比關(guān)系。假設(shè)CE為碳排放量，F(xiàn)C為油耗量，ε為燃油排放因子（單位油耗的CO2排放量），則可用公式表示為：

其中，不同燃料的燃油排放因子也不相同。本文參考?xì)W洲碳排放計(jì)算標(biāo)準(zhǔn)，取ε=2.62 kg/L。

而車輛的油耗不僅與行駛距離有關(guān)，還與車輛的載重、速度、車型、路況、燃油類型、空氣密度等有關(guān)。對此，考慮不同的影響因素也產(chǎn)生了多種不同的油耗計(jì)算模型。常見的油耗計(jì)算模型有：

（1）瞬時油耗模型[28]。該模型考慮了車輛的質(zhì)量、性能、牽引力、空氣阻力等因素，適用于車輛行駛距離較短、配送規(guī)模較小時的油耗計(jì)算。

（2）四階段模型[29]。該模型根據(jù)車輛不同的行駛狀態(tài)，分別建立了四種模式下的油耗計(jì)算模型——加速模式、減速模式、空轉(zhuǎn)模式、漫游模式，將四階段的油耗分別積分后求和即為總油耗。該模型計(jì)算較為精確，但依然只適用短途運(yùn)輸?shù)挠秃挠?jì)算。

（3）綜合模型[30]。該種模型對車輛參數(shù)進(jìn)行了更為明確的考慮，如發(fā)動機(jī)轉(zhuǎn)速、排量、摩擦系數(shù)，空氣阻力系數(shù)等。因此，該油耗模型的計(jì)算結(jié)果精確度相對較高，具體模型如下：

其中，F(xiàn)R為燃油消耗率；P為發(fā)動機(jī)總牽引功率；Pt為有效功率；ω是燃料與空氣的質(zhì)量比；μ為汽車發(fā)動機(jī)摩擦系數(shù)；η為柴油發(fā)動機(jī)的效率參數(shù)；λ為柴油熱量值；N為發(fā)動機(jī)轉(zhuǎn)速；E為發(fā)動機(jī)排量；θ為貨車的傳動效率；M為貨車的總質(zhì)量（空車質(zhì)量+裝載貨物質(zhì)量）；a為貨車加速度；g為重力加速度；α為道路坡度；Cd為空氣阻力系數(shù)；ρ為空氣密度；A為貨車迎風(fēng)面積；v為車輛行駛速度；Cr為貨車轉(zhuǎn)動阻力系數(shù)；Pacc是貨車其他功率需求，一般取0。各參數(shù)一般取值見表2。

表2 模型參數(shù)值

綜合上述三種模型，進(jìn)行對比分析，綜合模型的應(yīng)用范圍更廣，計(jì)算結(jié)果也更為精確。故本文采用綜合模型計(jì)算油耗量，進(jìn)而計(jì)算碳排放量。

假設(shè)車輛從顧客點(diǎn)i行駛到顧客點(diǎn)j耗時tij，則油耗量計(jì)算公式為：

碳排放量計(jì)算公式為：

其中，ζ為單位轉(zhuǎn)換系數(shù)（將g/s 轉(zhuǎn)換為L/s），通常取值737。

2.3 數(shù)學(xué)模型

模型所需符號如下：

A：顧客和倉庫集合，A={0,1,…,n}，其中0 表示倉庫；

C：顧客集合，C={1,2,…,n}；

V：車輛集合，V={1,2,…,K}；

n：顧客數(shù)量；

Q：車輛最大負(fù)載能力；

Cs：單位時間的服務(wù)成本；

Cf：單位油耗費(fèi)用；

qijk：車輛k訪問完i后在訪問j之前的載貨量；

dij：顧客i與顧客j之間的距離；

ti：車輛對顧客i的開始服務(wù)時間；

si：車輛在顧客i的服務(wù)時間；

tij：從顧客i到顧客j的運(yùn)輸時間；

xkj：0-1變量，若顧客j由車輛k提供服務(wù)，則為1，否則為0；

xijk：0-1變量，若從顧客i到顧客j由車輛k提供服務(wù)，則為1，否則為0。

基于綜合碳排放計(jì)算模型，考慮同時取送貨問題相關(guān)約束，構(gòu)建數(shù)學(xué)模型如下：

約束條件：

目標(biāo)函數(shù)式（1）為總成本最低，包括服務(wù)成本（車輛租用費(fèi)用、司機(jī)薪資）、油耗費(fèi)用和碳排放費(fèi)用。約束條件式（2）為車輛最大負(fù)載限制；式（3）為取貨服務(wù)過程約束，保證每輛車在任何路段上的負(fù)載都不得超過車輛的最大負(fù)載限制，且非負(fù)；式（4）和（5）表示每個顧客有且僅有一次被服務(wù)；式（6）表示顧客j只能被同一輛車服務(wù)；式（7）表示每輛車最多只能使用一次；式（8）表示一輛車可以服務(wù)多個顧客，而一個顧客只能被一輛車服務(wù)；式（9）表示車輛從倉庫出發(fā)時的載貨量等于所服務(wù)的客戶的送貨需求量之和；式（10）表示保證車輛回到倉庫的載貨量為已服務(wù)的客戶的取貨需求量之和；式（11）表示車輛在完成任務(wù)后須回到配送中心；式（12）和（13）表示xkj和xijk為0-1變量。

3 算法設(shè)計(jì)

遺傳算法是一種全局搜索機(jī)制，全局搜索能力強(qiáng)，但局部搜索能力較弱，一般只能求得次優(yōu)解，而非最優(yōu)解。而禁忌搜索算法為局部搜索機(jī)制，局部搜索能力強(qiáng)，具有極強(qiáng)的爬山能力，但對初始解依賴性較強(qiáng)。通過兩種算法的融合，可以取長補(bǔ)短，優(yōu)勢互補(bǔ)。

3.1 解的表示與初始解

初始解的生成方式有兩種——隨機(jī)生成和啟發(fā)式生成。啟發(fā)式生成的初始解相對隨機(jī)生成個體更為優(yōu)良，但個體較為集中，易使算法陷入局部極值點(diǎn)。為保證個體多樣性，使初始解盡可能地分布在整個解空間，本文采用隨機(jī)生成的方式產(chǎn)生初始解。

本文采用自然數(shù)編碼機(jī)制，具體編碼方式如下：

假設(shè)有9 位顧客，3 輛配送車輛。首先生成一個客戶的隨機(jī)向量853762149，然后生成一個車輛的隨機(jī)向量121312233，將兩組向量相互對應(yīng)，客戶向量所對應(yīng)位置的車輛向量值即服務(wù)該客戶的車輛。即：第一輛車服務(wù)客戶8、客戶3、客戶6，第二輛車服務(wù)客戶5、客戶2、客戶1，第三輛車服務(wù)客戶7、客戶4、客戶9，服務(wù)順序依據(jù)隨機(jī)客戶向量中的先后位置進(jìn)行。因此，解碼后得到3條線路，車輛1為8→3→6，車輛2為5→2→1，車輛3為7→4→9。該編碼方式保證了每輛車可服務(wù)多個客戶，且只被安排一次，每個客戶只由一輛車服務(wù)一次。

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的好壞關(guān)系到算法性能的優(yōu)劣，一般通過求解適應(yīng)度值來判別解的優(yōu)劣，進(jìn)而進(jìn)行選擇操作。鑒于VRPSPD 的特點(diǎn)，考慮到車輛的裝載容量限制，為保證各路線總送貨需求以及在各客戶點(diǎn)取貨后的負(fù)載不會超過車輛最大負(fù)載限制，避免產(chǎn)生不可行的路徑，本文在適應(yīng)度函數(shù)上增加了較高的懲罰代價。當(dāng)車輛的載重量超過車輛容量時，每次都會有罰款。因此適應(yīng)度函數(shù)如下所示：

其中，zi為第i條染色體所對應(yīng)的目標(biāo)函數(shù)值，M是當(dāng)車輛超載時所產(chǎn)生的足夠大的懲罰成本，λ為超出的載重（當(dāng)未超載時λ=0），fi為該染色體所對應(yīng)的適應(yīng)度值。計(jì)算目標(biāo)值時考慮從配送中心出發(fā)及返回配送中心的旅途時間，并保證返回載貨量與發(fā)車載貨量分別與客戶取送貨總需求相等，以滿足算法約束條件。根據(jù)適應(yīng)度值來判斷個體的優(yōu)劣，進(jìn)而使適應(yīng)度值較高的個體存活下來，適應(yīng)度值較低的個體死亡，即成本更高的解決方案將從種群中移除，而其他方案將保留下來。

3.3 選擇算子

選擇算子根據(jù)適應(yīng)度值以一定的概率從舊個體中選擇優(yōu)良個體組成新種群。通常，該概率是由個體的適應(yīng)度值與種群所有個體的適應(yīng)度值之和的比例所確定的，適應(yīng)度越高，被選中的概率也就越大。但是這種方法容易導(dǎo)致適應(yīng)度高的個體大量繁殖，從而使算法的搜索范圍過于局限。因此，本文采用改進(jìn)的輪盤賭法[31]結(jié)合最佳保留策略進(jìn)行選擇操作。具體步驟如下：

步驟1 根據(jù)適應(yīng)度值大小對種群進(jìn)行排序，使適應(yīng)度值最大的個體直接進(jìn)入下一代。

步驟2 計(jì)算個體選擇概率Pi=z(1-z)i-1，其中z=為種群中的個體數(shù)目。

步驟3 隨機(jī)生成一個[0，1]之間的選擇數(shù)x，計(jì)算個體i的累積概率：

當(dāng)累積概率為1 時，停止運(yùn)算。此時，若Qi-1＜x≤Qi，則選擇個體i。

步驟4 找出當(dāng)前種群中適應(yīng)度最優(yōu)的個體與迄今最好個體的適應(yīng)度值做比較，若當(dāng)前最優(yōu)個體適應(yīng)度更優(yōu)，則取代原最好個體。而被替換的原最好個體則取代當(dāng)前種群最差個體。

步驟5 重復(fù)步驟3 和步驟4 共n次，選出新的種群為止。

3.4 交叉算子

交叉算子與算法的全局搜索能力密切相關(guān)，是遺傳算法的主要算子，也是種群得以進(jìn)化的基礎(chǔ)。它模擬生物自然進(jìn)化過程，使兩條染色體互換部分基因，從而形成新個體。

本文采用兩點(diǎn)交叉法。同時，為避免兩個父代染色體相同的情況，采用了一種改進(jìn)的交叉策略，以增加種群的多樣性，如圖2所示。具體步驟如下：

步驟1 根據(jù)交叉概率隨機(jī)選出父代1 和父代2，并隨機(jī)選取兩個分界點(diǎn)c1和c2，兩分界點(diǎn)之間即為交叉的基因片段。

步驟2 將第一個父代染色體的基因片段移到第二個父代染色體尾部，將第二個父代染色體移到第一個父代首部。

步驟3 對有誤部分進(jìn)行修正處理，刪除染色體中重復(fù)沖突的基因。

3.5 變異算子

變異算子與算法的局部搜索能力密切相關(guān)，通過改變?nèi)旧w上的部分基因位，形成新的染色體，從而維持種群的多樣性，防止早熟早收斂的狀況，進(jìn)而提高算法的局部搜索能力。通常的變異操作有交換變異、倒位變異、插入變異等，但這些基本的變異操作對提高算法的局部搜索能力有限。而禁忌搜索算法有著獨(dú)特的記憶能力，局部搜索能力強(qiáng)。故本文將禁忌思想引入遺傳算法，采用禁忌搜索算法作為變異算子，進(jìn)一步提高算法的爬山能力。本文采用λ-交換法[32]構(gòu)造鄰域函數(shù)，確定藐視準(zhǔn)則為當(dāng)某個基因移動產(chǎn)生的解優(yōu)于當(dāng)前最好解時，則不論該基因移動是否處于禁忌狀態(tài)，都接受該移動，并將其作為新的當(dāng)前解。具體步驟如下：

圖2 交叉流程圖

步驟1 確定禁忌算法的初始解，選擇交叉操作后生成的較優(yōu)解作為初始解X。

步驟2 鄰域結(jié)構(gòu)設(shè)計(jì)：用鄰域函數(shù)為X產(chǎn)生若干鄰域解，并從中確定候選解集。

步驟3 判斷候選解集是否為空？若否，則選出候選解集中的最優(yōu)解S，轉(zhuǎn)步驟4；若是，則進(jìn)入下一輪迭代。

步驟4 判斷S是否滿足藐視準(zhǔn)則？若滿足，則令X=S，并將S加入禁忌表；若不滿足，則轉(zhuǎn)步驟5。

步驟5 判斷S的禁忌屬性。若S屬于禁忌表，則刪除S，回到步驟3；若不屬于，則令X=S，并將S加入禁忌表。

步驟6 令迭代次數(shù)gen=gen+1，并進(jìn)入下一輪迭代。

本文將禁忌搜索的思想融入遺傳算法，從而提高遺傳算法的局部搜索能力，遺傳禁忌搜索算法具體實(shí)現(xiàn)流程如圖3所示。

4 案例分析

圖3 算法流程圖

案例分析部分，引入了三角模糊數(shù)來描述客戶的需求，使其更符合實(shí)際，并對計(jì)算結(jié)果進(jìn)行了分析。然后，通過不同算法進(jìn)行比較，驗(yàn)證了模型的合理性和算法的有效性。所有啟發(fā)式算法都是在華碩W518 計(jì)算機(jī)上使用MatlabR2012a執(zhí)行的，具體配置為1.70 GHz Inter?CoreTMi5-4210U處理器，4 GB內(nèi)存，64位Windows 8操作系統(tǒng)。本案通過Matlab 隨機(jī)生成了30 個客戶點(diǎn)，客戶的需求量基于三角模糊數(shù)確定。表3 給出了顧客位置坐標(biāo)、服務(wù)時間、取貨量及其送貨需求。根據(jù)實(shí)際情況，決策者確定6 輛車重為2.5 噸，載重量為6 噸的卡車，行駛速度設(shè)為60 km/h。成本部分包括了服務(wù)成本（車輛租用費(fèi)用、司機(jī)薪資）與運(yùn)輸成本（油耗費(fèi)用、碳排放費(fèi)用）。一般情況下，服務(wù)成本為90 元/h。查詢最新柴油價格為6.5 元/L，碳排放價格為0.6 元/kg。

4.1 田口法參數(shù)設(shè)置

算法對于參數(shù)的設(shè)置非常敏感，不同的參數(shù)值能決定算法的有效性，因此需要在運(yùn)行算法之前確定合理的參數(shù)值。遺傳算法作為一種元啟發(fā)式算法，參數(shù)設(shè)置包含迭代次數(shù)、種群大小、交叉概率、變異概率等。依據(jù)以往遺傳禁忌參數(shù)設(shè)置經(jīng)驗(yàn)[18-19]，本文交叉概率設(shè)置為0.85，變異概率設(shè)置為0.15。算法的最優(yōu)迭代次數(shù)與種群大小，本文采用田口設(shè)計(jì)的實(shí)驗(yàn)方法進(jìn)行參數(shù)調(diào)優(yōu)，以確定其值。田口法是一種優(yōu)秀的參數(shù)校準(zhǔn)方法，近年來被許多研究人員所采用。Taguchi 定義了信噪比(S/N)作為變化的度量，這種轉(zhuǎn)換方法也使該參數(shù)設(shè)計(jì)具有很好的魯棒性。此外，田口法的目標(biāo)值分為“越小越好”“越大越好”“名義上最好”三組。由于決策者的目標(biāo)函數(shù)是成本最小化，因此本文選擇“越小越好”的類型，所對應(yīng)的信噪比由Mousavi和Niaki[33]給出，如下：

式中，n為各參數(shù)水平上算法的執(zhí)行次數(shù)，F(xiàn)t為響應(yīng)值，即第t次實(shí)驗(yàn)的目標(biāo)函數(shù)值。

設(shè)置種群大小分別為10、20、30、40、50，迭代次數(shù)為100、200、300、400、500，每種類別分別進(jìn)行10 次實(shí)驗(yàn)，共進(jìn)行250 次測試。隨后，創(chuàng)建田口設(shè)計(jì)，并將產(chǎn)生的250個總成本實(shí)驗(yàn)值作為響應(yīng)值進(jìn)行田口設(shè)計(jì)分析。分析結(jié)果如表4所示，相應(yīng)的信噪比和均值如圖4、圖5所示。從圖4 中可以看出，當(dāng)種群大小為40，迭代次數(shù)為500時，信噪比最大。同樣，在圖5中，當(dāng)種群大小為40，迭代次數(shù)為500 時，總成本均值最小。因此，根據(jù)田口實(shí)驗(yàn)分析所得，參數(shù)種群大小設(shè)置為40，迭代次數(shù)為500次。

表3 顧客信息表

圖4 信噪比交互作用圖

4.2 計(jì)算結(jié)果分析

基于上述數(shù)據(jù)，運(yùn)行算法30次，得到求解結(jié)果中最好的一次路徑優(yōu)化結(jié)果?？偝杀咀钚? 525.3 元、油耗量為254.74 L、碳排放量為667.41 kg，具體求解結(jié)果如表5所示，最優(yōu)路徑如下：

圖5 均值交互作用圖

車輛1：22→9→26

車輛2：3→11→17→30

車輛3：4→23→6→2→18→28

車輛4：21→16→27→19→8

車輛5：29→13→24→5→12→14

車輛6：1→10→25→7→20→15

一般情況下，旅行時間越長，總成本越高。然而，對比車輛1 與車輛2 卻發(fā)現(xiàn)，車輛1 的旅行時間少于車輛2，而總成本卻高于車輛2。不僅如此，車輛1 服務(wù)的客戶數(shù)最少，旅行時間最短，但油耗量與碳排放量卻相較于車輛2、3、4都要高。這是由于車輛1在客戶點(diǎn)的總服務(wù)時間相對較短（占總旅行時間45.42%），而車輛2、3、4 的總服務(wù)時長分別占總旅行時間54.99%、64.52%、56.75%。因此，車輛1 在路上的行駛時間就相對較長，為4.17 h，車輛2 的行駛時長為3.52 h，車輛3 的行駛時長為3.74 h，車輛4的行駛時長為3.94 h，這就導(dǎo)致車輛1的油耗量與碳排放量反而高于車輛2、3、4。因此得出，車輛的總旅行時間與油耗量并非單純的線性關(guān)系。在解決帶碳排放的車輛調(diào)度問題時，不僅要考慮車輛的租用時間，也要考慮車輛在各客戶點(diǎn)的服務(wù)時間（卸貨、取貨等）所帶來的影響。

表4 田口設(shè)計(jì)分析結(jié)果

最后，從服務(wù)各客戶的載重變化情況來看，出庫載重均未超過車輛的允許載重，且車輛3、4、5、6的出庫荷載都充分使用了車輛的裝載能力，體現(xiàn)了該算法的有效性。

表5 最優(yōu)解結(jié)果

4.3 算法對比分析

為驗(yàn)證改進(jìn)的遺傳禁忌算法對于求解模糊需求下綠色同時取送貨車輛調(diào)度問題的性能，本文針對三種不同的案例規(guī)模，分別利用遺傳算法、粒子群算法對本模型再次進(jìn)行求解，對比分析算法的求解效果。各算法參數(shù)設(shè)置如表6 所示，其中P為種群大小，G為迭代次數(shù)，CP為交叉率，MP為變異率，TG為禁忌代數(shù)，CS為候選集，TL為禁忌長度，W為慣性權(quán)重，C為加速因子。每種算法運(yùn)行30次，分別取各算法所求最優(yōu)解，并給出三種算法迭代效果圖。

表6 算法參數(shù)設(shè)置

不同案例規(guī)模下算法計(jì)算結(jié)果對比如表7、表8、表9所示，算法迭代效果對比如圖6所示。

表7 30個客戶算法計(jì)算結(jié)果對比

表8 60個客戶算法計(jì)算結(jié)果對比

表9 90個客戶算法計(jì)算結(jié)果對比

當(dāng)客戶數(shù)量為30 時，從表7 中可以看出，本文算法的最優(yōu)解相較于傳統(tǒng)遺傳算法而言，可使總成本降低1.6%，碳排放量降低2.2%，總旅行時間減少0.82 h；相較于例子群算法而言，可使總成本降低3.4%，碳排放量降低5.0%，減少總旅行時間1.71 h。

圖6 算法迭代對比圖

當(dāng)客戶數(shù)量為60 時，從表8 中可以看出，本文算法的最優(yōu)解相較于傳統(tǒng)遺傳算法而言，可使總成本降低4.8%，碳排放降低6.7%，總旅行時間減少5.28 h；相較于粒子群算法可使總成本降低12.7%，碳排放量降低35.4%，總旅行時間減少4.19 h。

當(dāng)客戶數(shù)量為90 時，從表9 中可以看出，本文算法的最優(yōu)解相較于傳統(tǒng)遺傳算法而言，可使總成本降低31.1%；相較于粒子群算法而言，可使總成本降低60.03%。對比碳排放與旅行時間，三種算法的差別不大。另外，經(jīng)過驗(yàn)算發(fā)現(xiàn)，當(dāng)客戶數(shù)量為90 時，總成本高于正常水平，這是由于車輛的載重超過車輛容量限制，從而產(chǎn)生了較高的懲罰成本，此種情況下可考慮用不同的車型安排取送貨，這將是下一步的研究方向。

綜上，當(dāng)客戶為小規(guī)模及中等規(guī)模時，本文算法求解模糊需求下綠色同時取送貨問題的求解效果均優(yōu)于GA 和PSO。當(dāng)客戶規(guī)模較大時，本文算法的求解效果仍遠(yuǎn)優(yōu)于GA 和PSO。且從圖6 可以看出，粒子群算法的收斂速度最快，但結(jié)果最差；遺傳算法的求解結(jié)果優(yōu)于粒子群算法，但是收斂速度較慢；改進(jìn)的遺傳禁忌算法的求解效果最好，收斂速度僅略低于粒子群算法。故而，認(rèn)為改進(jìn)的遺傳禁忌算法對于求解該問題是實(shí)用且有效的。

5 結(jié)束語

本文以VRPSPD為基本模型，考慮了客戶需求的不確定性以及客戶服務(wù)時間，引入了綜合碳排放計(jì)算方法，建立了模糊需求下的綠色同時取送貨模型，并提出了一種求解該問題的遺傳禁忌搜索算法。通過案例分析驗(yàn)證了模型和算法對于處理模糊需求下的綠色同時取送貨車輛調(diào)度問題的可行性和有效性。結(jié)果表明，車輛的總旅行時間與油耗量并非單純的線性關(guān)系，需要考慮車輛在各客戶點(diǎn)的服務(wù)時間。同時，改進(jìn)的遺傳禁忌搜索算法在求解小規(guī)模及中等規(guī)?？蛻袅繒r，求解效果及收斂性均優(yōu)于傳統(tǒng)的遺傳算法和粒子群算法。當(dāng)客戶規(guī)模較大時，改進(jìn)的遺傳禁忌搜索算法對于總成本的求解效果仍遠(yuǎn)優(yōu)于傳統(tǒng)的遺傳算法和粒子群算法。本文以低碳作為研究目標(biāo)，建立的模型及求解算法對于物流企業(yè)在綠色可持續(xù)發(fā)展的背景下進(jìn)行物流配送提供了優(yōu)化支持，也為政府相關(guān)部門制定節(jié)能減排政策提供了一些參考和借鑒。

當(dāng)然本研究還存在許多不足之處，比如沒有考慮客戶的時間窗要求，以及根據(jù)客戶規(guī)模和客戶需求選用不同的車型，這些將是下一步研究的方向。