胡巧麗，蘭建義（河南理工大學(xué) 工商管理學(xué)院，河南 焦作 454000）

0 引 言

隨著當(dāng)前世界經(jīng)濟(jì)環(huán)境污染和全球能源供應(yīng)枯竭的雙重問題日益嚴(yán)重，低碳、綠色和環(huán)保發(fā)展問題日益得到了社會人們的密切關(guān)注。在2015年召開的旨在降低碳排放的巴黎會議上，我國政府承諾到2030年單位GDP二氧化碳排放比2005年下降60%～65%。要實(shí)現(xiàn)十四五計(jì)劃的節(jié)約式綠色經(jīng)濟(jì)，重點(diǎn)就要強(qiáng)調(diào)綠色低碳經(jīng)濟(jì)的發(fā)展，十年內(nèi)碳排放量達(dá)頂峰，2060年前實(shí)現(xiàn)碳中和，它揭示了低碳經(jīng)濟(jì)模式是人類社會可持續(xù)發(fā)展的必然趨勢。近幾年物流服務(wù)行業(yè)發(fā)展快，已成為我國能源消耗及碳排放量大戶。企業(yè)要在減少經(jīng)濟(jì)成本的同時(shí)，考慮到經(jīng)濟(jì)利益和社會環(huán)境的約束，優(yōu)化物流網(wǎng)絡(luò)總體設(shè)計(jì)結(jié)構(gòu)，實(shí)現(xiàn)雙贏互利。

1959年，Dantzig和Ramser首次提出了車輛路線問題（Vehicle Routing Problem，VRP）指滿足某種經(jīng)濟(jì)限制條件下達(dá)到一定的目標(biāo)。關(guān)于物流運(yùn)輸路徑優(yōu)化的文章不少，例如Roberto等建立VRP模型以減少碳排放，加入汽車速度、坡度等變量，在增加額外運(yùn)營成本情況下，實(shí)現(xiàn)碳減排。Moghaddam等研究了在不確定需求情況下VRP問題，有助于確定可靠計(jì)劃及運(yùn)輸線路，增加客戶滿意度?；赩RP在物流配送領(lǐng)域的廣泛性和應(yīng)用價(jià)值，考慮距離和燃油因素時(shí)再重點(diǎn)關(guān)注帶時(shí)間窗的低碳VRP。硬時(shí)間窗雖能準(zhǔn)時(shí)完成配送，但剛性作用過強(qiáng)，會直接造成低貨車裝載率、長距離高速迂回行駛等不良情況。而軟時(shí)間窗有利于柔性配送與運(yùn)輸成本的降低。本文重點(diǎn)研究帶軟時(shí)間窗的VRPTW。例如Qureshi在時(shí)間窗懲罰約束基礎(chǔ)上提出軟時(shí)間窗約束，由于配送過程的不確定性導(dǎo)致任務(wù)在所需時(shí)間范圍內(nèi)不一定完成，如果提前或超過規(guī)定時(shí)間配送，則直接設(shè)置懲罰函數(shù)來解決時(shí)間因素的相關(guān)問題。由于該類問題是典型的NP-hard問題，求解算法有精確和啟發(fā)式算法。精確算法適用于規(guī)模較小的組合優(yōu)化問題。啟發(fā)式算法可求得問題的次優(yōu)解或以一定的概率求最優(yōu)解，其穩(wěn)定、通用及快速收斂是目前衡量的主要標(biāo)準(zhǔn)，包括節(jié)約法、模擬退火法、禁忌搜索法、遺傳算法、蟻群算法等。遺傳算法運(yùn)算速度雖快，但實(shí)現(xiàn)其通用編程語言較復(fù)雜，節(jié)約法會存在組合點(diǎn)混亂的問題。上述算法單獨(dú)使用會早熟且求解質(zhì)量不高。即本文將全局求解質(zhì)量高的遺傳算法與局部求解質(zhì)量高的模擬退火算法結(jié)合，對遺傳算法求出的解多次模擬退火尋優(yōu)，構(gòu)造一種混合遺傳算法求解帶時(shí)間窗的低碳VRP。

1 物流配送路徑優(yōu)化問題數(shù)學(xué)模型

1.1 構(gòu)建帶軟時(shí)間窗的車輛路徑問題模型

1.1.1 問題描述

帶時(shí)間窗限制的VRP問題相對于基本VRP問題要額外考慮運(yùn)送時(shí)間約束，若未在客戶規(guī)定的時(shí)間窗內(nèi)完成配送會產(chǎn)生經(jīng)濟(jì)損失，包括早到閑置等待機(jī)會成本和晚到懲罰成本。假設(shè)僅有一個(gè)配送中心，多輛車向多家配送服務(wù)點(diǎn)送貨，每個(gè)配送點(diǎn)的地理坐標(biāo)和平均運(yùn)貨量一定，每輛車的平均載重量也一定，配送中心在滿足客戶的需求及可接受服務(wù)時(shí)間的條件下，要求有效實(shí)現(xiàn)汽車運(yùn)行線路的合理安排，使總運(yùn)輸距離最短，最終車輛服務(wù)完每個(gè)客戶后返回配送中心。

鑒于實(shí)際問題的復(fù)雜及不確定性，對帶軟時(shí)間窗的VRP做出基本假設(shè)：（1）配送中心有且僅有一個(gè)，且能滿足所有客戶的貨物裝載；（2）車輛從配送中心出發(fā)服務(wù)完所有客戶，最終返回配送中心；（3）車輛為同種運(yùn)輸車型，其運(yùn)輸總量不能超出其承載容量限制且每位客戶的需求量小于車輛承載容量；（4）每位客戶的位置坐標(biāo)、需求量和服務(wù)時(shí)間和接受服務(wù)時(shí)間都是已知的；（5）到達(dá)和離開某個(gè)客戶點(diǎn)的車輛都只能是同一輛車；（6）所有車輛必須在規(guī)定的時(shí)間內(nèi)返回配送中心；（7）每位客戶必須且只能被訪問一次；（8）城市路網(wǎng)完全通聯(lián)，不考慮交通堵塞或交通管制等不可通行情況。

1.1.2 模型中符號和決策變量

表1 變量定義

1.1.3 模型建立

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

以總成本最小為目標(biāo)函數(shù)，其中第一項(xiàng)為配送車輛的運(yùn)輸成本，第二項(xiàng)和第三項(xiàng)為時(shí)間窗約束的定量表示。

1.2 構(gòu)建帶軟時(shí)間窗的低碳VRP模型

1.2.1 問題描述

本節(jié)研究的軟時(shí)間窗的低碳VRP是建立在前一節(jié)基礎(chǔ)上，考慮車輛固定用途、燃油消耗、碳排放等費(fèi)用，求解目標(biāo)函數(shù)總成本。對碳排放量計(jì)算，本文考慮了燃油消耗和運(yùn)輸距離的關(guān)系，假設(shè)二氧化碳排放與油耗成正比，不考慮行駛速度、路況等因素的影響，得出燃油總的消耗量，再通過燃油轉(zhuǎn)換系數(shù)轉(zhuǎn)化為該次二氧化碳的排放量，通過對每單位二氧化碳環(huán)境成本進(jìn)行定義，得到最終的二氧化碳的碳排放成本。

1.2.2 模型中符號和決策變量

表2 變量定義

1.2.3 模型建立

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

第一項(xiàng)為車輛配送的固定成本，第二項(xiàng)為車輛配送的運(yùn)輸費(fèi)用，第三項(xiàng)和第四項(xiàng)為時(shí)間窗的定量表示，第五項(xiàng)為配送車輛的燃油消耗費(fèi)用，第六項(xiàng)為二氧化碳排放的環(huán)境費(fèi)用。

（b）約束條件

2 帶軟時(shí)間窗的低碳VRP的遺傳算法設(shè)計(jì)

2.1 帶軟時(shí)間窗的低碳VRP的遺傳算法分析

2.1.1 算法流程分析

遺傳算法由美國Michigan大學(xué)Holland教授基于“優(yōu)勝劣汰、適者生存”原則對目標(biāo)函數(shù)進(jìn)行優(yōu)化，本質(zhì)是一種高效全局性搜索智能算法，具有強(qiáng)大的魯棒性和全局尋優(yōu)能力，適合求解多極值和組合性的問題。如圖1為遺傳算法的工作流程圖。

圖1 遺傳算法流程圖

2.1.2 算法實(shí)現(xiàn)的具體步驟如下：

（1）改進(jìn)染色體編碼。采用直接編碼方式，有個(gè)客戶，將1～（+ 1）自然數(shù)隨機(jī)排列，0表示配送中心，將-1個(gè)0隨機(jī)插入該排列中，由輛車向按1,2,…,編號的客戶送出，最后返回配送中心。根據(jù)客戶的需求安排路徑子串，在首尾加0，形成染色體。例如染色體“01402350”表示用2輛運(yùn)輸車輛從配送中心出發(fā)給5個(gè)客戶進(jìn)行配送，共形成兩條路徑的配送。路線1：0→1→4→0；路線2：0→2→3→5→0。

（2）種群初始化。種群生物初始系統(tǒng)是遺傳算法的一個(gè)起點(diǎn)，它會對生物進(jìn)化后的結(jié)果產(chǎn)生很大的直接影響。上述隨機(jī)程序生成的染色體序列構(gòu)成一條新的染色體，考慮到實(shí)際情況，將初始種群規(guī)模設(shè)定為100。

（3）計(jì)算適應(yīng)度值。染色體的好壞用適應(yīng)度值來衡量，適應(yīng)度值代表最優(yōu)解的優(yōu)良程度，在交叉、變異等算子和約束條件下，形成一個(gè)個(gè)體適應(yīng)度函數(shù)。本文的研究目標(biāo)是最小配送路徑，可對目標(biāo)函數(shù)取倒數(shù)，實(shí)現(xiàn)最大值與最小值之間的轉(zhuǎn)換，目標(biāo)函數(shù)值越小，適應(yīng)度函數(shù)值越大，適應(yīng)性越強(qiáng)，個(gè)體就越優(yōu)秀，反之個(gè)體越差，即：

（4）迭代判斷與局部搜索。設(shè)置最大進(jìn)化代數(shù)，判斷迭代次數(shù)達(dá)到預(yù)設(shè)進(jìn)化代數(shù)時(shí)，則停止迭代；否則將迭代次數(shù)加1繼續(xù)迭代。再選取最優(yōu)個(gè)體進(jìn)行局部搜索，直至獲得最佳解。

（5）遺傳選擇操作。同時(shí)采取最優(yōu)個(gè)體保留戰(zhàn)略和輪盤賭法。將最優(yōu)個(gè)體即適應(yīng)度最高個(gè)體直接復(fù)制到下一代。再用輪盤賭，將該種群的所有可用染色體累加得∑F，再計(jì)算每條染色體適應(yīng)度值在體中占比即F/∑F,即為該染色體選中概率。

（6）交叉操作。在遺傳算法中，交叉操作是將兩個(gè)隨機(jī)的染色體交換某些基因，產(chǎn)生兩個(gè)新的基因組合，從而產(chǎn)生兩個(gè)新個(gè)體。除第一條直接復(fù)制的最優(yōu)染色體以外，其余均以交叉概率為基礎(chǔ)進(jìn)行配對。由于一個(gè)客戶只能由一輛運(yùn)輸車輛完成配貨，即染色體的編碼中不會產(chǎn)生重復(fù)基因代碼。例如：本文對種群中個(gè)體交叉采用隨機(jī)交叉方式，設(shè)有9個(gè)配送點(diǎn)，有兩個(gè)染色體（0620954078310）和（ 0510793082460）。去掉配送中心0變?yōu)椋?29547831）和（517938246），再隨機(jī)產(chǎn)生交叉位置，將父代中間部分放在對方前面，如果有重復(fù)基因則刪除本身重復(fù)數(shù)字，從而產(chǎn)生兩個(gè)新染色體。例如隨機(jī)選擇第二位和第五位為交叉點(diǎn)，則染色體分別為=62|954|7831，=51|793|8246，將染色體中間交配區(qū)域加到染色體前面，同理將染色體中間交配區(qū)域加到染色體前面：得到=793|629547831，=954|517938246；再分別刪除、交配后與交配區(qū)域相同的自然數(shù)編碼，得到最終的下一代染色體為：=793625481,=954173826。最終在原有位置重新加載四個(gè)0，即最后（=0790362054810，=0950417038260）此法即使是父代相同，也可以產(chǎn)生新的子代。

（7）變異操作。變異操作是指在種群中隨機(jī)選擇個(gè)體的變異位置，對該基因串的某些個(gè)體進(jìn)行改變，染色體中的一部位發(fā)生相應(yīng)變化，另一部位也會發(fā)生相應(yīng)變化，保證了種群的多樣性與算法收斂性。例如：染色體793625481上的6發(fā)生了變異，變?yōu)?，則1位上也發(fā)生變異，變?yōu)?，即得到新染色體793125486。

2.2 帶軟時(shí)間窗的低碳VRP的混合遺傳算法分析

模擬退火算法避免了局部最優(yōu)，可確保全局最佳解的可靠度，通用且適應(yīng)于并行處理，但運(yùn)行時(shí)間長、收斂速度慢。遺傳算法雖可在更大概率下搜索出最優(yōu)解，但易早熟、局部搜索能力差、控制變量多。若將模擬退火引入遺傳算法的交叉運(yùn)作中，使兩種算法結(jié)合形成一種混合遺傳算法，使遺傳算法能接收所有解，包括優(yōu)良解和劣質(zhì)解，避免在“早熟”解中陷入困境，增強(qiáng)遺傳算法整體收斂性，還可提高進(jìn)化速度，求得全局最精確解，同時(shí)將遺傳算法的迭代次數(shù)作為模擬退火算法的退火時(shí)間。

2.2.1 算法實(shí)現(xiàn)步驟

（1）首先確定種群規(guī)模大小，交叉概率P，變異概率P，初始退火溫度，降溫系數(shù)θ；

（2）對個(gè)體進(jìn)行編碼，隨機(jī)產(chǎn)生個(gè)個(gè)體，計(jì)算個(gè)體的適應(yīng)度值；

（3）對個(gè)體進(jìn)行選擇操作；

（4）分別對個(gè)體進(jìn)行交叉操作和模擬退火工作；

（5）對個(gè)體進(jìn)行變異操作；

（6）降溫，θ,θ為一個(gè)［0,1 ］之間的常數(shù)，為迭代次數(shù)；

（7）判斷個(gè)體是否達(dá)到進(jìn)化代數(shù)，若達(dá)到則終止運(yùn)算，否則轉(zhuǎn)回步驟3；

（8）計(jì)算結(jié)束，得最優(yōu)解。

2.2.2 混合遺傳算法的構(gòu)造

（1）編碼。采用1,2,3,…,的自然數(shù)編碼。

（2）適應(yīng)度函數(shù)。

適應(yīng)度代表最優(yōu)解的優(yōu)良程度，在函數(shù)運(yùn)算中只有交叉、變異等函數(shù)算子和時(shí)間等約束條件與目標(biāo)函數(shù)共同作用條件下，才能構(gòu)造出個(gè)體適應(yīng)度函數(shù)。在本文設(shè)計(jì)的混合遺傳分析算法中可將退火罰因子加入到適應(yīng)度函數(shù)中：

其中：min為目標(biāo)函數(shù)，α為退火罰因素，隨著混合遺傳系統(tǒng)運(yùn)作，溫度逐漸下降，目標(biāo)函數(shù)值越小，適應(yīng)度函數(shù)值越大，適應(yīng)性越強(qiáng)，個(gè)體越優(yōu)秀，反之越差，而適應(yīng)度函數(shù)值越大的則有更多機(jī)會繁殖新子代，使優(yōu)秀的混合基因組有更強(qiáng)的遺傳適應(yīng)性。

（3）選擇算子。采用最佳個(gè)體保留方法。

（4）交叉算子。采用類似OX法的交叉方法。

（5）模擬退火算法。

（6）變異算子。為保證個(gè)體多樣性，采用連續(xù)多次對換變異法。

（7）求取最優(yōu)解。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文假設(shè)有21個(gè)配送點(diǎn)，中心坐標(biāo)為（23,5）。對遺傳算法和模擬退火混合遺傳算法均取迭代數(shù)為200次，種群大小為100。配送客戶信息如表3所示。

3.2 實(shí)驗(yàn)參數(shù)設(shè)定

3.3 與模擬退火混合遺傳算法的比較

根據(jù)表4所示參數(shù)，種群大小為100，迭代次數(shù)為200，分別對遺傳算法和模擬退火混合遺傳算法進(jìn)行仿真實(shí)驗(yàn)對比。將模擬退火算法嵌入原始算法之后，依次用原始方案與新方案對表3數(shù)據(jù)進(jìn)行10次求解得兩種方案的對比結(jié)果，兩種結(jié)果的對比圖如圖2所示。

圖2 兩種算法的對比圖

表3 配送客戶信息

表4 實(shí)驗(yàn)參數(shù)設(shè)置表

遺傳算法所得最優(yōu)路徑為： ［0-7-9-18-5-10-17-15-8-21-19-20-3-14-13-1-2-12-4-11-16-6-0 ］，總成本2 095.204元。

加入模擬退火后的混合遺傳算法的最優(yōu)路徑為： ［0-9-14-3-1-18-10-7-17-6-19-20-13-4-15-8-12-11-5-21-2-16-0 ］，總成本1 813.970元。

通過圖2可以看出算法迭代過程，遺傳算法要迭代143次左右達(dá)到穩(wěn)定，而加入模擬退火后的混合遺傳算法只需迭代67次左右，說明混合遺傳算法大大提高了收斂速度，最終的路徑優(yōu)化也比單純使用遺傳算法的成本減少281.234元。圖3、圖4分別為兩種方法所得的路徑示意。

圖3 遺傳算法路線圖

圖4 混合遺傳算法路線圖

運(yùn)用MatlabR2014b版本編程求解帶軟時(shí)間窗的低碳VRP。為了盡可能減少隨機(jī)因素的影響，本文對算例重復(fù)測試10次，選取測試中得到的最好解和運(yùn)行結(jié)果對比如表5至表8所示。

表5 遺傳算法的最優(yōu)解和具體配送方案

表8 實(shí)驗(yàn)最優(yōu)解對比

由以上實(shí)驗(yàn)數(shù)據(jù)對比可以得出，使用混合遺傳模擬退火算法計(jì)算的最佳解、最差解、平均解及標(biāo)準(zhǔn)差在兩種算法中都是最小的，達(dá)到最優(yōu)解時(shí)的進(jìn)化代數(shù)也是最小的，因此使用混合遺傳模擬退火算法能有效提高對線路優(yōu)化問解的求解精確度。

4 結(jié) 論

本文基于遺傳算法，嵌入模擬退火算法操作，全面提高了遺傳算法性能，增強(qiáng)了遺傳算法在解決配送路徑優(yōu)化問題時(shí)的收斂速度和計(jì)算精度，避免陷入最優(yōu)解的局部，減少了搜索時(shí)間，使混合遺傳算法的功效大大提高。實(shí)驗(yàn)結(jié)果顯示，該算法是求解帶時(shí)間窗低碳物流車輛路徑優(yōu)化問題的有效方案。

表6 混合遺傳算法的最優(yōu)解和具體方案方案

表7 各算法10次運(yùn)行結(jié)果比較