基于混合遺傳算法的低碳物流配送路徑優(yōu)化

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

0 引 言

隨著當(dāng)前世界經(jīng)濟(jì)環(huán)境污染和全球能源供應(yīng)枯竭的雙重問(wèn)題日益嚴(yán)重，低碳、綠色和環(huán)保發(fā)展問(wèn)題日益得到了社會(huì)人們的密切關(guān)注。在2015年召開(kāi)的旨在降低碳排放的巴黎會(huì)議上，我國(guó)政府承諾到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ì)模式是人類(lèi)社會(huì)可持續(xù)發(fā)展的必然趨勢(shì)。近幾年物流服務(wù)行業(yè)發(fā)展快，已成為我國(guó)能源消耗及碳排放量大戶(hù)。企業(yè)要在減少經(jīng)濟(jì)成本的同時(shí)，考慮到經(jīng)濟(jì)利益和社會(huì)環(huán)境的約束，優(yōu)化物流網(wǎng)絡(luò)總體設(shè)計(jì)結(jié)構(gòu)，實(shí)現(xiàn)雙贏互利。

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

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

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

1.1.1 問(wèn)題描述

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

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

1.1.2 模型中符號(hào)和決策變量

表1 變量定義

1.1.3 模型建立

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

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

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

1.2.1 問(wèn)題描述

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

1.2.2 模型中符號(hào)和決策變量

表2 變量定義

1.2.3 模型建立

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

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

（b）約束條件

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

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

2.1.1 算法流程分析

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

圖1 遺傳算法流程圖

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

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

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

（3）計(jì)算適應(yīng)度值。染色體的好壞用適應(yīng)度值來(lái)衡量，適應(yīng)度值代表最優(yōu)解的優(yōu)良程度，在交叉、變異等算子和約束條件下，形成一個(gè)個(gè)體適應(yīng)度函數(shù)。本文的研究目標(biāo)是最小配送路徑，可對(duì)目標(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)略和輪盤(pán)賭法。將最優(yōu)個(gè)體即適應(yīng)度最高個(gè)體直接復(fù)制到下一代。再用輪盤(pán)賭，將該種群的所有可用染色體累加得∑F，再計(jì)算每條染色體適應(yīng)度值在體中占比即F/∑F,即為該染色體選中概率。

（6）交叉操作。在遺傳算法中，交叉操作是將兩個(gè)隨機(jī)的染色體交換某些基因，產(chǎn)生兩個(gè)新的基因組合，從而產(chǎn)生兩個(gè)新個(gè)體。除第一條直接復(fù)制的最優(yōu)染色體以外，其余均以交叉概率為基礎(chǔ)進(jìn)行配對(duì)。由于一個(gè)客戶(hù)只能由一輛運(yùn)輸車(chē)輛完成配貨，即染色體的編碼中不會(huì)產(chǎn)生重復(fù)基因代碼。例如：本文對(duì)種群中個(gè)體交叉采用隨機(jī)交叉方式，設(shè)有9個(gè)配送點(diǎn)，有兩個(gè)染色體（0620954078310）和（ 0510793082460）。去掉配送中心0變?yōu)椋?29547831）和（517938246），再隨機(jī)產(chǎn)生交叉位置，將父代中間部分放在對(duì)方前面，如果有重復(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è)體的變異位置，對(duì)該基因串的某些個(gè)體進(jìn)行改變，染色體中的一部位發(fā)生相應(yīng)變化，另一部位也會(huì)發(fā)生相應(yīng)變化，保證了種群的多樣性與算法收斂性。例如：染色體793625481上的6發(fā)生了變異，變?yōu)?，則1位上也發(fā)生變異，變?yōu)?，即得到新染色體793125486。

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

模擬退火算法避免了局部最優(yōu)，可確保全局最佳解的可靠度，通用且適應(yīng)于并行處理，但運(yùn)行時(shí)間長(zhǎng)、收斂速度慢。遺傳算法雖可在更大概率下搜索出最優(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）對(duì)個(gè)體進(jìn)行編碼，隨機(jī)產(chǎn)生個(gè)個(gè)體，計(jì)算個(gè)體的適應(yīng)度值；

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

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

（5）對(duì)個(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ī)會(huì)繁殖新子代，使優(yōu)秀的混合基因組有更強(qiáng)的遺傳適應(yīng)性。

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

（4）交叉算子。采用類(lèi)似OX法的交叉方法。

（5）模擬退火算法。

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

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

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

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

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

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

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

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

圖2 兩種算法的對(duì)比圖

表3 配送客戶(hù)信息

表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元。

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

圖3 遺傳算法路線(xiàn)圖

圖4 混合遺傳算法路線(xiàn)圖

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

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

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

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

4 結(jié) 論

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

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

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