低碳經(jīng)濟(jì)下考慮多車型冷鏈路徑優(yōu)化模型對比

程元棟,強(qiáng)子玲

（安徽理工大學(xué)經(jīng)濟(jì)管理學(xué)院,安徽淮南232000）

隨著人民生活水平的不斷提高和社會經(jīng)濟(jì)的飛速發(fā)展,越來越多的人在飲食和食品方面的重視程度與投入日益增加,這也使得國內(nèi)各行電子商務(wù)與物流運(yùn)輸業(yè)不斷發(fā)展.近年來我國物流運(yùn)輸業(yè)發(fā)展迅猛,2021 年快遞行業(yè)量完成1 083.0 億件,物流運(yùn)輸作為一門高污染和高能耗的行業(yè),為了降低廢氣排放與天然能源消耗,自上世紀(jì)末至現(xiàn)今,新能源汽車不斷受到各企業(yè)的追捧.一是由于純電動物流車具有相對于以前汽油車不具有的低能耗和零排放等的特點(diǎn),切實(shí)符合了目前現(xiàn)代物流行業(yè)的發(fā)展需求[1];二是多地出臺幫扶政策以此加大新能源貨車的市場占有率,在諸多因素的推動下,越來越多地使用新能源貨車完成城市物流支線的配送任務(wù).2022 年1-7 月,新能源物流車?yán)塾嬩N量邁上新臺階,突破10 萬輛,達(dá)到101 348 輛（不含交叉乘用車）.

從現(xiàn)代物流系統(tǒng)的總體管理結(jié)構(gòu)組成來看,當(dāng)下物流管理存在的主要問題是配送車路徑規(guī)劃以及車輛節(jié)能減排.特別是在互聯(lián)網(wǎng)電商交易發(fā)達(dá)和物流產(chǎn)業(yè)飛速發(fā)展的今天,如何高效、動態(tài)、實(shí)時地合理安排生鮮品運(yùn)輸和及時有效地規(guī)劃行車路徑所帶來最低總成本一直是各界共同關(guān)注的焦點(diǎn).其作為運(yùn)籌學(xué)中具有典型代表的組合優(yōu)化問題,經(jīng)過眾多專家學(xué)者半個多世紀(jì)的深入研究,該問題已不是早期的那種純靜態(tài),已經(jīng)逐漸發(fā)展成為多目標(biāo)、動態(tài)的、多類型配送車輛、帶復(fù)雜約束條件等類型的路徑規(guī)劃問題.物流公司的路徑規(guī)劃問題一般表現(xiàn)為車輛種類以及配送車輛路徑問題（Vehicle Routing Problem,VRP）[2-3],約束條件為每個客戶點(diǎn)都有且僅被經(jīng)過一次,生鮮冷鏈運(yùn)輸車輛在完成配送任務(wù)需要返回配送中心,它的終極目標(biāo)就是:客戶拿到高品質(zhì)生鮮以提高企業(yè)市場競爭力,同時可以減少對環(huán)境的污染.1959 年運(yùn)輸車輛路徑問題（VRP）概念是由Dantzig 和Ramser[4]首次提出的.Siam 最開始注意到配送車輛的最大載荷是有限的,所以其規(guī)定所有客戶點(diǎn)的需求量應(yīng)小于等于所有運(yùn)輸車輛總的荷載量[5].李冰和黨佳俊構(gòu)建了多配送中心車輛路徑模型,理論上模型中任意配送中心均可向所有客戶進(jìn)行運(yùn)輸[6].高治佳、李星梅等提出一種基于已有充電站調(diào)整的電動車充電站選址,經(jīng)過非線性函數(shù)驗(yàn)證可知已有充電站調(diào)整類型和新建充電站選擇方案與規(guī)劃者對充電距離和成本的偏好程度有關(guān)[7].畢軍等總結(jié)出2014 年整年的運(yùn)輸電動車輛充放電數(shù)據(jù),大多數(shù)城市物流配送車輛的使用者在下午2 點(diǎn)至4 點(diǎn)且此時車輛的剩余電量在30%至50%時就近充電站充電[8].鄧友均和李明等以時間成本為基礎(chǔ),以配送車輛快速充電成本、電池?fù)p耗成本和排隊(duì)等候時間成本之和的最小化為優(yōu)化目標(biāo),建立電動運(yùn)輸車輛充電導(dǎo)航模型和路徑規(guī)劃,證明實(shí)時感知信息可以緩解充電壓力同時還可以降低企業(yè)物流總成本[9].金珈輝等提出電動配送車輛路徑模型,由于電動車的特性,其必須考慮充電以及時間窗這不可避免的問題[10].在此之后,VRP演變出許多種類及其擴(kuò)展被應(yīng)用于社會各個場景,其中研究最為廣泛的兩個擴(kuò)展為:一是約束車輛的運(yùn)輸能力;二是一種客戶必須在指定時間間隔內(nèi)到達(dá)的帶時間窗約束模型的VRP[11].

據(jù)上述分析表明,大多數(shù)國內(nèi)外學(xué)者研究重點(diǎn)是電動汽車的車輛路徑與充換電的選址,又或者單獨(dú)研究純?nèi)加团渌蛙囕v, 而針對電動汽車的智能充電策略和純?nèi)加团渌蛙囕v在時間窗等約束條件下的對比研究相對較為薄弱,智能安排充電位置作為其中一種優(yōu)化手段,能夠提高運(yùn)輸車輛的電池電能的利用率,從而降低電動運(yùn)輸車的配送成本.以往很多學(xué)者在對兩種運(yùn)輸汽車進(jìn)行路徑優(yōu)化或者選址優(yōu)化時,多數(shù)是將電動汽車的充電行為進(jìn)行最好設(shè)想處理, 如假設(shè)這些車輛離開配送中心時為滿電量狀態(tài)或采取換備用電池操作等,這些假設(shè)以及處理方式可能不太符合現(xiàn)實(shí)情況,降低結(jié)果在社會的普適性;或不考慮兩種車型路上所有意外情況,都進(jìn)行最好預(yù)處理.因此,本文以電動汽車和純?nèi)加蛢煞N物流配送車輛為研究對象,對兩種運(yùn)輸車輛的配送過程進(jìn)行分析,建立了分別考慮車輛的固定成本、運(yùn)輸成本以及其他成本[12]的兩種物流配送車輛的優(yōu)化目標(biāo),本文還根據(jù)所研究問題的特點(diǎn),設(shè)計了一種改進(jìn)的遺傳算法對其進(jìn)行求解,最后通過數(shù)值分析對所建立的仿真模型和算法進(jìn)行驗(yàn)證.

1 模型構(gòu)建分析

1.1 問題描述

通過對消費(fèi)者、冷鏈企業(yè)和社會環(huán)境的三方立場進(jìn)行分析,可以得出消費(fèi)者對生鮮產(chǎn)品最為關(guān)注的是其新鮮度,企業(yè)希望通過降低成本提升競爭力,社會需要減少冷鏈物流產(chǎn)生的碳排放量.為確保生鮮產(chǎn)品的質(zhì)量,同時降低產(chǎn)品損耗,需要在采摘后迅速將生鮮產(chǎn)品進(jìn)行預(yù)冷處理,最大化保留產(chǎn)品新鮮度.對冷鏈物流建設(shè)來說,在配送中心需要通過多臺配送車輛向下游各個客戶點(diǎn)及時有效地按需調(diào)度和配送.本文構(gòu)建以冷鏈物流配送車輛類型和配送路徑優(yōu)化問題的仿真模型, 其中包括綜合考慮純電動運(yùn)輸車和燃油運(yùn)輸車在配送過程中產(chǎn)生的總成本,燃油車的總成本包括車輛產(chǎn)生的固定成本、運(yùn)輸成本、制冷成本、碳排放成本以及因生鮮貨物新鮮度下降所帶來的損耗成本[13],與此同時新能源車還需考慮配送過程中因充電所增加的成本,平衡環(huán)境與企業(yè)經(jīng)濟(jì)效益兩者之間的影響.在求解最優(yōu)方式的配送路徑問題過程中,綜合考慮消費(fèi)需求、社會環(huán)境和企業(yè)發(fā)展三方立場,以滿足消費(fèi)者全面性需求、減少環(huán)境污染和提高企業(yè)競爭力為最終目標(biāo),從冷鏈系統(tǒng)角度,構(gòu)建了以冷鏈運(yùn)輸總成本最小為目標(biāo)的配送中心路徑優(yōu)化模型[12].在對現(xiàn)有冷鏈配送模式、已有冷鏈配送路徑優(yōu)化方法分析基礎(chǔ)上,本文將生鮮冷鏈配送過程中碳排放對環(huán)境造成的負(fù)面影響進(jìn)行量化并作為外部成本考慮在內(nèi),探索顧客滿意度、環(huán)境和經(jīng)濟(jì)效益三者間的平衡點(diǎn),探索最優(yōu)車種總成本最低的最佳配送路徑.

1.2 假設(shè)條件

由于考慮燃油運(yùn)輸車輛和純充電策略的汽車物流配送問題較為復(fù)雜,因此,在仿真模型構(gòu)建之前,需要做出如下假設(shè):

（1）本文研究的是多個客戶由一個配送中心運(yùn)輸?shù)穆窂絻?yōu)化問題;

（2）單輛配送車輛的最大裝載容量應(yīng)大于等于單個客戶點(diǎn)的最大需求量,且單個客戶點(diǎn)的需求量不可由多輛運(yùn)輸車進(jìn)行配送;

（3）新能源運(yùn)輸車輛和燃油運(yùn)輸車輛的裝載量以及車型均相同;

（4）新能源車的電池容量相同;

（5）新能源冷鏈運(yùn)輸車輛從配送中心出發(fā)時電池沒有消耗;

（6）配送車輛（燃油車和新能源汽車）的電量消耗與距離成正比;

（7）每個充電站點(diǎn)僅且只能被訪問一次;

（8）配送車輛（燃油車和新能源汽車）在完成配送任務(wù)時都要返回配送中心;

（9）在整個運(yùn)輸過程中,交通擁堵、車輛故障、司機(jī)狀態(tài)等一些其他特殊因素的影響不考慮;

（10）兩種冷鏈運(yùn)輸車輛在進(jìn)行配送服務(wù)過程中的速度是恒定不變的;

（11）所有配送車輛都配備了冷藏室和制冷設(shè)備,且配送的產(chǎn)品均為生鮮品[13];

（12）客戶的坐標(biāo)位置、需求貨物量以及能接收貨物到達(dá)時間范圍條件均為已知[13];

（13）假設(shè)兩種配送車輛駛離配送中心的時間均為0 時刻.

1.3 參數(shù)符號和變量的定義

Hi= {h= 0,1,2,3,… ,n} :配送中心和客戶點(diǎn)集合;i=0 表示配送中心;i= 1,2,3… ,25表示所有客戶點(diǎn)集合;

Kf={f=1,2,3}:燃油車配送車輛的數(shù)量;

Ke= {e=1,2,3}:新能源配送車輛的數(shù)量;

ne為新能源車車型的車輛數(shù),e 為新能源車車型的第e 輛車;

nf為燃油車車型的車輛數(shù),f為燃油車車型的第f 輛車;

Mm={m=1,2}:新能源汽車充電樁的數(shù)量;

Qh:配送中心h的最大容量;

qi:客戶點(diǎn)i 的需求量;

qe:新能源車輛最大荷載量;

qf:燃油車最大荷載量;

fe:新能源車的單位運(yùn)輸費(fèi)率;

Ff:燃油車的單位運(yùn)輸費(fèi)率;

B:新能源車電池容量;

r:新能源的電池消耗速率;

:新能源車離開i 點(diǎn)后的載質(zhì)量;

:燃油車離開i 點(diǎn)后的載質(zhì)量;

bij:新能源車經(jīng)過i后的電池使用量;

:新能源車到達(dá)i點(diǎn)時的電量;

:新能源車離開i點(diǎn)時的電量;

:燃油車輛經(jīng)過弧(i,j)的運(yùn)行時間;

:新能源車經(jīng)過弧(i,j)的運(yùn)行時間;

:新能源車到達(dá)i點(diǎn)的時間;

:新能源車離開i點(diǎn)的時間;

:燃油車到達(dá)i 點(diǎn)的時間;

:燃油車離開i點(diǎn)的時間;

:新能源汽車經(jīng)過弧(i,j)電池使用量;

:燃油車經(jīng)過弧(i,j)的碳排放量;

:汽車經(jīng)過(i,j)的長度;

Fk:新能源汽車和燃油汽車的固定成本;

twi:在客戶點(diǎn)i 處的等待時間;

fi:在客戶點(diǎn)i 處的服務(wù)時間;

ei:客戶要求的最早服務(wù)時間;

li:客戶要求的最遲服務(wù)時間;

tij:汽車從i點(diǎn)到j(luò) 點(diǎn)的時間;

Cc:單位充電時間的費(fèi)用.

決策變量定義:

1.4 建立數(shù)學(xué)模型

根據(jù)對問題描述的分析以及燃油運(yùn)輸車輛和新能源運(yùn)輸車輛在實(shí)際冷鏈物流配送過程中的應(yīng)用,燃油冷鏈運(yùn)輸車輛以建立包括生鮮產(chǎn)品損耗成本、固定成本、軟時間窗的懲罰成本、運(yùn)輸成本以及碳排放成本最小化的優(yōu)化目標(biāo)函數(shù)[14],而新能源車在燃油車成本考慮基礎(chǔ)上增加電車配送過程的充電成本,兩種車型的進(jìn)一步研究,以尋找冷鏈配送過程中既能保證顧客滿意度又能實(shí)現(xiàn)低碳排放的總成本最低的最優(yōu)路徑方案.

1.4.1 固定成本 假定燃油冷藏車和新能源冷藏車的固定成本相同,配送過程中的總固定成本可以表示為

1.4.2 運(yùn)輸成本 車輛在運(yùn)輸過程中的耗能都與行車速度和載重相關(guān),燃油車和新能源車由于不同車型會導(dǎo)致不同的能耗,則運(yùn)輸成本可以表示為

fe、ff分別表示新能源車和燃油車的單位運(yùn)輸費(fèi)率;和分別為新能源冷藏車、燃油冷藏車的單位里程能耗.

1.4.3 生鮮貨物損耗成本 車輛k 從配送中心出發(fā)到達(dá)客戶點(diǎn)i 時,其新鮮度降低為,運(yùn)輸過程中和卸貨過程中的貨損成本可以表示為

1.4.4 時間懲罰成本 若到達(dá)客戶點(diǎn)的時間早于或晚于期望時間窗,則要接受一定的懲罰成本,其與客戶訂購的產(chǎn)品的價格數(shù)量呈線性關(guān)系,考慮到提前送達(dá)和延遲送達(dá)兩種狀態(tài)對客戶的影響不同,因此運(yùn)用不同的懲罰函數(shù)權(quán)重表示,函數(shù)如下

1.4.5 碳排放成本 碳排放成本主要包括運(yùn)輸和制冷過程中產(chǎn)生的碳排放,但是由于車型不同,使用的動力能源不同,導(dǎo)致不同車型的碳排放也會有所不同,這里用εe和εf分別表示新能源車以及燃油車的車輛動能碳排放系數(shù),和分別表示新能源車以及燃油車的單位里程能耗,碳排放成本表示如下

1.4.6 充電成本 由于新能源配送車在配送中心滿電出發(fā)時的最大里程為160 km,在不足以從i 點(diǎn)配送到j(luò) 點(diǎn)時,就必須就近尋找充電樁進(jìn)行充電,此處用CC表示單位充電時間的費(fèi)用,單次配送車輛充電成本表示如下

綜上所述,新能源車和燃油車?yán)滏溑渌吐窂絻?yōu)化模型的目標(biāo)函數(shù)如下

式（10）（11）表示新能源車和燃油車的目標(biāo)函數(shù),即車輛運(yùn)輸成本最小,其約束條件為:式（12）表示配送過程中使用的冷藏車輛總數(shù)不超過配送中心車輛總數(shù);式（13）（14）表示各客戶需求總量的質(zhì)量和容量不能超過當(dāng)前冷藏車的最大載質(zhì)量和最大容量約束;式（15）表示單個仿真模型中每個客戶點(diǎn)僅且只能被一輛冷鏈運(yùn)輸車輛進(jìn)行配送服務(wù);式（16）表示冷鏈運(yùn)輸車輛完成單輛車任務(wù)后最終需返回起始配送中心;式（17）表示對任一客戶,有且僅只能有一輛配送車輛到達(dá)客戶點(diǎn)完成配送任務(wù)后再次離開;式（18）表示配送過程的連續(xù)性,即車輛在一個顧客點(diǎn)的服務(wù)開始時間必須要大于其在上一個顧客的服務(wù)開始時間加等待時間和兩者之間的行駛時間,其中M 表示一個足夠大的數(shù).

2 改進(jìn)遺傳算法

燃油車輛路徑問題（Fuel Vehicle Routing Problem,FVRP）和新能源車輛路徑問題（Electric Vehicle Routing Problem,EVRP）,作這兩類配送運(yùn)輸問題是傳統(tǒng)運(yùn)輸車輛路徑問題的一類變種,同時這也屬于比較突出典型的NP-Hard 問題.一方面這一類問題很難通過精確算法得到其精確解,特別是對于一些數(shù)據(jù)規(guī)模比較龐大的具體算例;另一方面通過對當(dāng)前這一類文獻(xiàn)的收集、整理和研究發(fā)現(xiàn),大多數(shù)國內(nèi)外的專家學(xué)者采用智能啟發(fā)式算法對這一類問題進(jìn)行求解,此類方法不但對求解的可信度品質(zhì)和運(yùn)行效率非常好,同時其對求解大規(guī)模的具體實(shí)例有著明顯的優(yōu)勢,帶時間窗約束的配送車輛路徑問題（Transport Vehicle Routing Problem with Time Windows,TVRPTW）相較于一般的EVRP 問題,其求解的約束條件以及環(huán)境更多且復(fù)雜,同時其對算法求解的質(zhì)量要求和時效性更為嚴(yán)格,所以這里采用了并行尋優(yōu)能力較強(qiáng)的改進(jìn)遺傳算法對其進(jìn)行運(yùn)算求解.遺傳算法（Genetic Algorithm,GA）是一種模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型,同時也是一種通過模擬自然進(jìn)化過程搜尋局部最優(yōu)解的方法[15-16],該算法在求解過程中,首先是將問題中有關(guān)參數(shù)編碼為染色父本,染色體對應(yīng)各個數(shù)據(jù)或數(shù)據(jù)組,通常表示為一組結(jié)構(gòu)數(shù)據(jù)串,串上各個位置對應(yīng)基因的雙值,染色體就是這些基因組成的串,也被稱為個體（Individuals）,因此很多數(shù)量的染色體個體就可以組成一個種群（Population）,種群的個體數(shù)目又被稱為種群規(guī)模（Population Size）或種群大小,同時使用一定的運(yùn)算法則計算染色體個體的適應(yīng)度值（Fitness）,再利用選擇、交叉以及變異等進(jìn)行設(shè)置的代數(shù)迭代以及計算種群中染色體的信息,最終生成符合優(yōu)化問題目標(biāo)函數(shù)值的染色體個體,即為問題的最優(yōu)解.與此同時,為了避免算法過早地陷入局部最優(yōu)解,這里采用錦標(biāo)賽選擇法和移民操作[12].

2.1 染色體編碼

對于多車型配送車輛路徑規(guī)劃模型,本文運(yùn)用整數(shù)編碼的形式對染色體進(jìn)行整體編碼,用于選擇總成本最低的最優(yōu)車型路徑優(yōu)化.當(dāng)車輛使用數(shù)為m 且顧客數(shù)目為n 時,此時染色體長度為m+n-1,例如冷鏈配送服務(wù)的車輛允許最多使用2 輛, 而有服務(wù)需求的顧客數(shù)目為6, 則有以下兩種情況的路徑:12ab3456,其中12ab3456 中的a 和b 代表配送中心,a 和b 將顧客123456 劃為2 條配送路徑,配送中心用0 表示,分別為:0-1-2-0 以及0-3-4-5-6-0;另一種可行的染色體表達(dá)為123456ab,此時這個染色體表示1 條配送路徑:0-1-2-3-4-5-6-0.

2.2 種群初始化

配送車輛路徑規(guī)劃模型的初始化,首先需要構(gòu)造問題的初始解,因此設(shè)定客戶點(diǎn)顧客數(shù)量為 {1 ,2,...n},從設(shè)定的所有顧客中任意挑選一個顧客α∈{1， 2， 3，…n} ,同時初始化冷鏈運(yùn)輸車輛所使用的車輛數(shù)目,生成一個遍歷顧客的序列s= {1,… ,j?1,j,j+1,… ,n} , 遍歷序號為1 一直遍歷到n 即為所生成的初始解.按照遍歷順序s 遍歷顧客s(i),根據(jù)約束條件,此時將顧客添加至第k 條冷鏈配送路徑中,緊接著更新k.此方法所得出的初始解即為一條完整的運(yùn)輸方案,假設(shè)有6 個顧客,最多能使用2 輛車,那么一個可行的配送方案就可以表示為:0-1-2-0 和0-3-4-5-6-0; 然后再將這個配送方案中的路徑進(jìn)行合并.為1203456,其中0 代表配送中心,此時用a 和b 替換1203456 中的0,結(jié)果表示為12ab3456,代表為一個染色體個體:重復(fù)當(dāng)前操作直到種群規(guī)模達(dá)到初始大小,完成初始種群[17].

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

在遺傳算法中種群中各個染色體個體的優(yōu)劣程度是用適應(yīng)度值來衡量的[17].為避免目標(biāo)函數(shù)在數(shù)值上過大,通常采用倒數(shù)形適應(yīng)度函數(shù)表達(dá)式,這里對求解中的適應(yīng)度函數(shù)設(shè)置為

式（20）中：c(s) 為配送車輛路徑規(guī)劃模型中目標(biāo)函數(shù)的通用表達(dá)式;ω(x)為模型的約束條件進(jìn)行懲罰函數(shù)處理后的表達(dá)式.這樣設(shè)置以后既能保證懲罰函數(shù)值和目標(biāo)函數(shù)值綜合較小的染色體個體的適應(yīng)度值較高,使得其能被遺傳到下一代種群中的概率變高.

2.4 遺傳操作

2.4.1 選擇 錦標(biāo)賽選擇法是遺傳算法中流行的選擇策略,其簡單高效,因此這里采用錦標(biāo)賽選擇法.所謂的錦標(biāo)賽選擇法,是從已有的所有種群個體中隨機(jī)選擇若干個,比較被選中個體的適應(yīng)度值,適應(yīng)度值大的個體被挑選出來進(jìn)行后續(xù)的交叉、變異,具體步驟如下:

（1）首先確定每次選擇的樣本個體數(shù)量N;

（2）從已有的所有種群個體中隨機(jī)選擇設(shè)定的N 個個體（單個個體被選中的概率相同）構(gòu)成小種群,根據(jù)小種群中單個個體的適應(yīng)度值大小,選擇出適應(yīng)度值最大的個體優(yōu)先進(jìn)入下一代種群;

（3）步驟（2）重復(fù)多次（重復(fù)次數(shù)為種群的大小）,直到新的種群大小規(guī)模和最開始的種群規(guī)模一樣[18].

2.4.2 交叉 交叉主要是模仿生物進(jìn)化中的交配重組,根據(jù)交叉概率P 對兩個父代染色體在某些位置以某種規(guī)則進(jìn)行基因重組的操作,此操作過后可以產(chǎn)生新一代染色體.交叉算子中的進(jìn)行頻率由交叉概率決定,其概率過大或過小都不利于產(chǎn)生更優(yōu)秀的染色體.

本文采用部分匹配交叉算子（Partially-matched crossover,PMX）進(jìn)行操作,部分匹配交叉不僅保證了在一個染色體上始終不會出現(xiàn)重復(fù)的基因, 同時還保證了每個染色體中的基因僅出現(xiàn)一次.其實(shí)PMX與兩點(diǎn)交叉有點(diǎn)類似,其做法是在染色體上隨機(jī)挑選兩個交叉點(diǎn)以此確定其交叉范圍,操作之后一般會出現(xiàn)一個無效的染色體組,同時新的無效染色體組中可能有極個別基因會出現(xiàn)重復(fù)的情況,因此為了修復(fù)該染色體,可以建立起交叉區(qū)域內(nèi)每個染色體之間的一一對應(yīng)關(guān)系,最后對重復(fù)基因應(yīng)用此匹配關(guān)系在區(qū)域外消除沖突.具體操作步驟如圖1～4 所示.

圖1 父代基因圖Fig.1 Paternal gene diagram

圖2 父一代基因圖Fig.2 Paternal generation gene diagram

（1）在染色體中任意挑選（父代）兩個基因點(diǎn)作為始末位置（兩父代染色體挑選位置相同）.

（2）兩組基因的位置相互交換.

（3）沖突染色體檢測.根據(jù)b 操作中所得的兩組染色體基因建立一個一一對應(yīng)的映射關(guān)系[19],如圖3所示,以2-8-5 這一映射關(guān)系為例,可以看出第二步結(jié)果中子代1（child1）存在重合基因2,這時候需要通過對應(yīng)關(guān)系將其轉(zhuǎn)變?yōu)? 基因,以此類推直至染色體基因中沖突沒有為止,所有有沖突的基因都會經(jīng)過映射,最終形成的新一代中不存在沖突基因.

圖3 基因映射關(guān)系圖Fig.3 Gene-mapping relationship diagram

圖4 子一代基因圖Fig.4 Genetic plots of the subgeneration

最終結(jié)果為

2.4.3 變異 經(jīng)過交叉操作之后得到新個體,其具有一定基因突變的概率,此操作與選擇一樣是基于概率的,這個變異概率為Pm,一般來說變異概率設(shè)置得很小,將變異引入遺傳算子的目的有兩個:一是維持樣本多樣性,預(yù)防收斂現(xiàn)象在未成熟前就發(fā)生;二是使遺傳算法具有一定的局部隨機(jī)搜索能力,當(dāng)該算法通過交叉算子已接近最優(yōu)解鄰域時,利用變異算子的這種局部隨機(jī)搜索能力可以加速向最優(yōu)解收斂.本文運(yùn)用的操作是基本位變異法.基本位變異法是指個體編碼中以變異概率Pm 隨機(jī)指定的一個或幾個基因座上的基因值作變異運(yùn)算[20-21].操作過程如下所示:

（1）對編碼個體的每一個基因座,指定其為變異點(diǎn)且概率為Pm;

（2）對指定變異點(diǎn)進(jìn)行變異操作.

2.5 移民操作

設(shè)定閾值并由此判定當(dāng)前的算法是否陷入了早熟收斂,如若是,就施行“移民策略”引入外部個體,此種操作可以增強(qiáng)種群局部搜索能力,從而可以使種群的多樣性增加.由于遺傳算法容易“早熟”,即容易局部收斂,算法停止而得到錯誤解.為了解決這一問題,本文采用“移民策略”,就是將目前保留的群體中移植部分較為優(yōu)秀的個體以增加種群多樣性,進(jìn)而提高算法搜索的效率.首先需要判斷當(dāng)前的算法是否出現(xiàn)了早熟收斂現(xiàn)象,假設(shè)發(fā)生早熟收斂時,進(jìn)一步表明目前群體中個體適應(yīng)度非常高,因此可以根據(jù)各群體的適應(yīng)度方差來判斷算法是否陷入了早熟收斂.為了便于計算,令E=.式中:fi為第i個個體的適應(yīng)度;為群體的平均適應(yīng)度;N為種群規(guī)模.當(dāng)E 小于之前設(shè)定的閾值時,當(dāng)即就可確定算法出現(xiàn)早熟收斂現(xiàn)象,就要對其實(shí)施“移民操作”[12].

2.6 大規(guī)模領(lǐng)域搜索算法（LNS）局部搜索操作

本文首先采用當(dāng)前解并采用相似性公式計算,以及破壞算子移除若干相似客戶和刪除若干客戶,接著在滿足此前設(shè)定的各約束條件前提下, 最后再利用修復(fù)算子將之前被移除的客戶點(diǎn)重新加入被破壞的解中,使其盡可能多地將移除的客戶插回到使目標(biāo)成本最小的位置.

2.7 終止

迭代終止條件,路徑規(guī)劃模型中設(shè)置當(dāng)種群中個體進(jìn)化代數(shù)達(dá)到設(shè)定迭代次數(shù)的終止條件時,停止迭代.

3 算例研究

3.1 算例介紹

本文描述的是生鮮品冷鏈物流配送模型,為了檢驗(yàn)本文中所構(gòu)建模型以及算法的有效性,案例模型的數(shù)據(jù)來源于文獻(xiàn)[22].其主要包含的內(nèi)容如下:以三輛新能源汽車和三輛燃油車分別作為單次配送車輛,對于在一定區(qū)域內(nèi)時間窗約束已知且均勻分布的25 個客戶點(diǎn)提供配送服務(wù),同時單個客戶點(diǎn)只能被一輛冷鏈配送車進(jìn)行服務(wù),此外,當(dāng)正在執(zhí)行配送任務(wù)的新能源車電池電量不足以完成剩余配送任務(wù)時,此配送車輛需要進(jìn)入到鄰近的充電站進(jìn)行半個小時的充電,以支撐其完成剩余配送任務(wù),所以在模型設(shè)定的有效區(qū)域內(nèi)設(shè)置2 處可供配送車輛進(jìn)行充電的充電站,在此過程中所采用的是快速充電的方式,使得電動配送車輛充滿一次電需要30 min 左右.本文采用的是改進(jìn)的遺傳算法,此模型中的相關(guān)參數(shù)設(shè)置如表1 所示,生鮮物流的配送過程中共使用了2 種冷藏車車型,具體參數(shù)如表2 所示.

表1 相關(guān)參數(shù)信息Tab.1 Related parameter information

表2 兩種冷藏車具體參數(shù)Tab.2 Specific parameters of the two kinds of refrigerated vehicles

仿真模型案例的坐標(biāo)系統(tǒng)（X,Y）采用的是平面直角坐標(biāo)系,坐標(biāo)的單位是公里（km）;其中0 代表配送中心;1、2、3、…25 表示的是客戶點(diǎn);26、27 表示充電站.每個服務(wù)點(diǎn)需求量的單位是噸（t）; 最早服務(wù)時間和最晚服務(wù)時間是基于倉庫0 為起始時間的偏移量,單位小時（h）,“100”代表不限制;服務(wù)時間的單位是小時（h）,詳細(xì)信息如表3 所示.

表3 各節(jié)點(diǎn)詳細(xì)信息Tab.3 Each node details

算法中涉及的參數(shù):迭代次數(shù)MAXGEN=1 000,種群規(guī)模A=300,交叉率pc=0.9,變異率pm=0.05,代溝GGAP=0.9,違反限質(zhì)量懲罰系數(shù)ALPHA=10 000.采用MATLAB 2022a 實(shí)現(xiàn)并運(yùn)行上述算法,根據(jù)上述實(shí)例的具體數(shù)據(jù)對燃油車和新能源車分別進(jìn)行考慮碳排放以及不考慮碳排放的模型進(jìn)行求解, 得到局部最優(yōu)配送路線、配送路徑的各項(xiàng)具體成本以及配送車輛行駛總距離,如表4 所示[13].

表4 車輛路徑規(guī)劃結(jié)果Tab.4 Vehicle Path Planning Results

從表4 可以看出:（1）新能源車考慮碳排放和不考慮碳排放的總成本分別為3 378.8 元和3 449.6 元,相對于燃油車考慮碳排放和燃油車不考慮碳排放兩種情況其成本減少1 020.9 元和961 元,下降比例分別為23.20%和21.79%,對比結(jié)果可知使用新能源車執(zhí)行配送任務(wù)企業(yè)可以有效節(jié)約運(yùn)營成本;（2）燃油車考慮碳排放和不考慮碳排放配送生鮮所產(chǎn)生的運(yùn)輸成本分別高于新能源運(yùn)輸車同類型1 142.040 8元和1 260.500 3 元,使用新能源車后成本下降61.74%和64.41%.運(yùn)輸成本不僅會增加客戶和企業(yè)的成本負(fù)擔(dān),而且會增加環(huán)境負(fù)擔(dān),因此需要加強(qiáng)生鮮品冷鏈物流的配送管理和人員降低車輛運(yùn)輸成本.從長遠(yuǎn)來看,新能源車可以減少天然燃料的使用和大氣污染物的產(chǎn)生,更符合當(dāng)前社會需求與形勢[13];（3）燃油配送車輛考慮碳排放比新能源配送車輛考慮碳排放所產(chǎn)生的碳排放成本增加99.10%,使用新能源車更符合低碳環(huán)保的當(dāng)今發(fā)展趨勢;（4）由于新能源車在配送過程中充電是一個不可避免的問題,同時充電站可能不在既定配送線路上,這使得新能源車的配送總路程較燃油車有所增加,分別增加91.080 3km 和44.160 2km,總路程的增加使得生鮮貨物的路上時間增加,進(jìn)而貨損成本增加-9.43%和36.19%.

3.2 算例結(jié)果分析

仿真模型分析的是新能源車和燃油車考慮碳排放以及不考慮碳排放的四種情況.經(jīng)過結(jié)果對比可知,新能源配送車輛考慮碳排放的總成本最低最具成本優(yōu)勢,較其他三種情況總成本分別減低2.10%、30.54%和30.21%.由于目前生鮮品的物流配送過程較為繁雜,需求配送點(diǎn)和貨運(yùn)種類逐漸增加,車輛交通路線錯綜復(fù)雜,同時顧客對生鮮品的品質(zhì)要求提高,在市場經(jīng)濟(jì)的大環(huán)境下,無形中增加了生鮮品的市場競爭需求.

仿真模型的四種路徑規(guī)劃中,時間懲罰成本和貨損成本約占總成本的36.76%、35.22%、49.74%和54.26%,因此針對對時間要求嚴(yán)格的生鮮貨物,軟時間窗約束以及損耗函數(shù)的引用,使得模型更加貼合實(shí)際情況,縮短運(yùn)輸逾期帶來的成本費(fèi)用的同時也能增加客戶滿意度,這對現(xiàn)代物流業(yè)發(fā)展具有重要的推動力和促進(jìn)作用[13].

4 結(jié)論

冷鏈配送物流產(chǎn)業(yè)是當(dāng)下高能耗領(lǐng)域,低碳經(jīng)濟(jì)是可持續(xù)發(fā)展的重要方向,因此低溫配送是冷鏈物流走向低碳經(jīng)濟(jì)的關(guān)鍵環(huán)節(jié).文中將冷鏈運(yùn)輸車輛路徑優(yōu)化問題作為研究方向,目的是對比燃油車和新能源車作為配送車輛以達(dá)到配送總成本最小、環(huán)境最友好。為了改善傳統(tǒng)遺傳算法容易早熟收斂和陷入局部最優(yōu)解的不足[23],運(yùn)用錦標(biāo)賽選擇算法和移民策略進(jìn)行改進(jìn),通過改進(jìn)遺傳算法對仿真冷鏈物流配送案例進(jìn)行求解,驗(yàn)證了本文設(shè)計的改進(jìn)遺傳算法能夠使求解結(jié)果更優(yōu),為解決相關(guān)冷鏈物流配送路徑優(yōu)化問題提供了參考[24].

針對生鮮品配送路徑規(guī)劃問題進(jìn)行研究,在滿足各個客戶點(diǎn)的各種需求的前提下,來對比燃油配送車輛和新能源配送車輛總成本之和最小的優(yōu)化目標(biāo),燃油車總共成本包括生鮮品的貨損成本、運(yùn)輸成本、固定成本、以及碳排放成本和時間窗約束所造成的懲罰成本[12],與此同時新能源車還需要增加一個充電成本因素,構(gòu)建了時間窗約束下的生鮮品配送路徑規(guī)劃模型,并為此設(shè)計出改進(jìn)的遺傳算法,最后借助MATLAB 軟件結(jié)合仿真算例,對兩種運(yùn)輸車輛模型的結(jié)果進(jìn)行比對.（1）采用改進(jìn)遺傳算法設(shè)計出來的方案不僅在進(jìn)化過程中能更早地搜尋到最優(yōu)解,同時還能使求解結(jié)果更好;（2）本文所構(gòu)建的生鮮品配送路徑規(guī)劃模型具有一定的通用性且此處改進(jìn)的遺傳算法在求解模型時更具有高效性, 能為解決當(dāng)前生鮮品配送路徑規(guī)劃問題提供一定的科學(xué)決策依據(jù).對于高速發(fā)展的現(xiàn)代社會,不論是對企業(yè)、社會環(huán)境還是消費(fèi)者,新能源車輛進(jìn)行配送較燃油車更具有未來發(fā)展優(yōu)勢.