邱玉琢，張 磊

(南京財(cái)經(jīng)大學(xué) 營銷與物流管理學(xué)院，江蘇 南京 210023)

一、 引言與文獻(xiàn)綜述

近年來，我國生鮮農(nóng)產(chǎn)品供應(yīng)鏈已經(jīng)得到較大的改善，但是與歐美發(fā)達(dá)國家相比，我國每年因果蔬損耗造成的損失超出世界平均水平5～6倍。隨著生活質(zhì)量的提高，人們開始追求高品質(zhì)的服務(wù)，對(duì)新鮮、健康的農(nóng)產(chǎn)品的需求大大提高。各大生鮮配送企業(yè)相繼尋找快速配送農(nóng)產(chǎn)品的方法，然而，隨之快速增加的配送成本限制了配送的發(fā)展。當(dāng)前配送過程環(huán)境復(fù)雜，如何將更多因素納入規(guī)劃中使決策更貼合實(shí)際成為企業(yè)主關(guān)心的問題。此外，隨著國家越發(fā)強(qiáng)調(diào)“低碳物流”，降低運(yùn)輸過程的碳排放也成為配送企業(yè)不得不關(guān)注的重中之重。

生鮮農(nóng)產(chǎn)品配送優(yōu)化的核心是車輛路徑優(yōu)化問題。自Dantzig and Ramser[1]于1959提出車輛路徑問題開始，主要目的是降低運(yùn)輸成本和距離。近年來越來越多學(xué)者從不同的角度豐富了車輛路徑問題的研究?jī)?nèi)容。在綜合車隊(duì)方面，Krajewska and Kopfer[2]首次考慮自有車隊(duì)和外包方式的綜合運(yùn)輸規(guī)劃問題(ITTP)，他們認(rèn)為自有車隊(duì)與外部承運(yùn)人結(jié)合的運(yùn)輸規(guī)劃方式在應(yīng)對(duì)波動(dòng)的需求時(shí)更有優(yōu)勢(shì)。Gahmetal.[3]在此基礎(chǔ)上，從貨主角度出發(fā)，解決交貨計(jì)劃問題，完善前人各類型車隊(duì)的成本計(jì)算過程，使成本更加合理。在碳排放因素方面，Bektaand Laporte[4]首次引入影響碳排放量多少的各種因素，提出污染路徑問題，揭示了車輛負(fù)載、速度和總成本各參數(shù)之間的關(guān)系，進(jìn)一步貼合實(shí)際。Ko?etal.[5]考慮車隊(duì)規(guī)模、多車場(chǎng)位置和碳排放因素的影響，其目標(biāo)是實(shí)現(xiàn)倉庫、車輛和配送路徑的成本最小化。Eshtehadietal.[6]保留了需求不確定性因素，補(bǔ)充需求不確定下的污染路徑問題，在需求端更加貼合市場(chǎng)變化，從時(shí)點(diǎn)研究變?yōu)闀r(shí)段研究。Wang and Li[7]引入時(shí)空距離的概念，考慮時(shí)間窗懲罰成本和倉庫成本因素，在多目標(biāo)多因素條件下解決具有異構(gòu)車隊(duì)、同時(shí)取貨和時(shí)間窗的路徑問題。Micheli and Mantella[8]對(duì)現(xiàn)有的碳排放政策做細(xì)致分析，考慮非均質(zhì)車隊(duì)，將不同的碳控制政策的經(jīng)濟(jì)和環(huán)境影響納入模型，考慮成本最小化和碳排放量最低，對(duì)比分析了不同政策對(duì)路徑優(yōu)化的影響。在各因素被考慮到模型中前提下，Lietal.[9]進(jìn)一步完善因素分析，指出燃料燃燒是碳排放產(chǎn)生的主要來源，降低燃料消耗對(duì)降低成本和碳排放起主要作用?？梢钥闯?，前人的研究對(duì)多種因素的考慮逐漸完善，但是對(duì)碳排放政策影響下的綜合運(yùn)輸車隊(duì)問題研究較少，本文在此基礎(chǔ)上，考慮異構(gòu)車隊(duì)、時(shí)間窗、碳排放等因素，目的是降低配送總成本，不同于單獨(dú)的異構(gòu)車隊(duì)污染路徑問題，進(jìn)一步研究租賃車隊(duì)增加的碳排放權(quán)是否對(duì)新的最優(yōu)配送路徑有影響，租賃碳排放權(quán)不增加配送公司成本，在控制碳排放權(quán)變化范圍的前提下，尋求成本和碳排放的平衡。

解決異構(gòu)車隊(duì)和污染路徑問題的模型和算法已經(jīng)被很多學(xué)者提出和改進(jìn)，其中禁忌搜索算法和遺傳算法受到眾多學(xué)者關(guān)注，也有部分學(xué)者采用混合元啟發(fā)式算法解決該問題，越來越多的研究表明混合算法在計(jì)算效率和結(jié)果上均優(yōu)于單一算法。禁忌搜索算法的變種有很多，Krajewska and Kopfer[2]首次提出該問題，設(shè)計(jì)了一種用四種移動(dòng)類型促進(jìn)解空間的搜索，不嚴(yán)格的禁忌表得到更多可能的解，使獲得的解更豐富更好。Gahmetal.[3]提出那種基于變量鄰域搜索的元啟發(fā)式算法，結(jié)果表明該算法能獲得更好的解。此外遺傳算法的發(fā)展也備受學(xué)者關(guān)注。Baietal.[10]結(jié)合虛擬編碼策略、多子代方法、異族交叉策略和禁忌搜索機(jī)制相結(jié)合，設(shè)計(jì)一種多種群遺傳算法，具有協(xié)同進(jìn)化的性能。從算法自身改進(jìn)出發(fā)，Costaetal.[11]結(jié)合局部和種群搜索啟發(fā)式的元素，實(shí)現(xiàn)了減排的結(jié)果。從混合算法出發(fā)，Tohidifardetal.[12]結(jié)合粒子群和遺傳算法，優(yōu)化染色體的排列順序，對(duì)尋找更好的解做出貢獻(xiàn)。Wang and Li[7]利用遺傳算法對(duì)客戶點(diǎn)聚類，并用模擬退火的思想提高變鄰域搜索算法的全局優(yōu)化能力，凸顯了混合算法的優(yōu)勢(shì)。近期有文獻(xiàn)表明混合算法結(jié)果優(yōu)于單一算法結(jié)果，較優(yōu)的初始解能快算法收斂，交叉方式的多樣化保證解的多樣化。本文基于上述分析，設(shè)計(jì)一個(gè)結(jié)合最近鄰啟發(fā)式算法和改進(jìn)遺傳算法的混合遺傳算法，該算法采用最近鄰法產(chǎn)生更好的初始解，從遺傳算法本身，參考禁忌搜索的鄰域搜索機(jī)制，設(shè)計(jì)三種交叉規(guī)則提高算法搜索效率，同時(shí)，為了測(cè)試算法的有效性，本文做了數(shù)據(jù)分析，探索算法本身的有效性和模型的敏感性。

本文的主要貢獻(xiàn)在于：(1)針對(duì)生鮮農(nóng)產(chǎn)品配送過程成本優(yōu)化問題，結(jié)合運(yùn)輸過程中亟待控制的重要因子—碳排放，考慮了多種成本影響因素，著重引入了租賃增加的碳排放權(quán)因素，構(gòu)建了相應(yīng)的數(shù)學(xué)模型，分析成本、時(shí)間窗、碳排放因素對(duì)配送決策的影響，確定最優(yōu)配送車輛組合和路徑。(2)設(shè)計(jì)了混合遺傳算法對(duì)模型進(jìn)行求解，優(yōu)于單一算法的計(jì)算結(jié)果，而且較優(yōu)的初始解能加快算法收斂，交叉方式的多樣化也保證了解的多樣化。(3)通過案例分析驗(yàn)證了模型和算法的有效性和實(shí)用性。

二、 混合整數(shù)規(guī)劃模型

(一) 問題描述

給定完全圖G=(V,E)，其中V表示圖上的節(jié)點(diǎn)集，其中0表示生鮮配送中心，1,2，…,n表示n個(gè)客戶點(diǎn)，每一個(gè)顧客需求量為qi，E={(i,j)|i,j∈V，i≠j}表示節(jié)點(diǎn)之間的邊構(gòu)成的集合,dij表示車輛從節(jié)點(diǎn)i到節(jié)點(diǎn)j經(jīng)過的距離。具有碳排放約束和時(shí)間窗的異構(gòu)車隊(duì)車輛問題，即自有車輛和租賃車輛均從生鮮配送中心出發(fā)，滿足所有顧客后回到配送中心，在碳排放和時(shí)間窗約束的條件下，使包括自有車隊(duì)固定成本、運(yùn)輸成本、租賃成本、懲罰成本、制冷成本和碳排放成本的總成本最小化。

假設(shè)配送中心自身擁有一定的車輛數(shù)固定為m，每一輛車的載重限制為Q。在自身擁有車輛數(shù)不足以滿足配送需求時(shí)，需租賃專業(yè)運(yùn)輸車隊(duì)用于配送，假設(shè)租賃方式有兩種，一種是根據(jù)車輛行駛距離收費(fèi)，單位距離的租賃費(fèi)用為c2；另一種是按日收費(fèi)，單天的租賃費(fèi)用為c3，假設(shè)租賃的車輛與自有車隊(duì)完全一致，具有相同的載重限制Q。需要強(qiáng)調(diào)當(dāng)選擇按日租賃方式時(shí)，必須支付整數(shù)天的費(fèi)用，即不足一天仍以一天計(jì)費(fèi)，租賃車輛在每天開始配送之前統(tǒng)一調(diào)配到配送中心，由配送中心統(tǒng)一安排，即每一輛車都是從配送中心出發(fā)最終又回到配送中心。

生鮮農(nóng)產(chǎn)品配送時(shí)間過長(zhǎng)會(huì)腐爛變質(zhì)，為了提高客服滿意度，必須在規(guī)定的時(shí)間范圍內(nèi)將貨物送到顧客手中，假設(shè)配送中心與客戶約定最早送貨時(shí)間為ei，最遲送貨時(shí)間為li，本文假設(shè)節(jié)點(diǎn)i服務(wù)時(shí)間窗為[ei，li]，如果車輛早于時(shí)間ei到達(dá)，則需要等待交貨，因此需要支付懲罰成本μ1，如果晚于時(shí)間li到達(dá)，則可能會(huì)引起客戶不滿，因此需要支付懲罰成本μ2。假設(shè)車輛到達(dá)客戶點(diǎn)i的時(shí)間為ti,在規(guī)定時(shí)間內(nèi)可以即時(shí)交貨，不考慮交貨時(shí)間，則客戶點(diǎn)i的軟時(shí)間窗懲罰函如下：

G(i)=μ1max(ei-ti,0)+μ2max(ti-li,0)，?i∈V

(1)

冷藏車的制冷成本和碳排放成本是配送成本的重要組成部分，制冷的能量來源是燃油，因此采用燃油消耗成本來衡量制冷成本。另外在配送貨物過程中，配送車輛會(huì)排放大量的尾氣，尾氣中包括甲烷、一氧化碳和二氧化碳等溫室氣體，但是其中二氧化碳還是占大部分，因本文主要是為了得出最優(yōu)的生鮮農(nóng)產(chǎn)品配送路徑，故僅估算二氧化碳的排放量及成本。Zhangetal.[13]優(yōu)化了油量消耗模型，考慮車輛增加一定負(fù)載的時(shí)候增加多少油耗的油量消耗計(jì)算模型。Wangetal.[14]進(jìn)一步結(jié)合滿載計(jì)算車輛行駛過程中的油耗。據(jù)此，車輛k從客戶點(diǎn)i到客戶點(diǎn)j的油耗函數(shù)如下：

Fijk= (f1+θijk(f2-f1) )dij，?i,j∈V,?k∈K

(2)

參數(shù)：

G=(V,E)，表示物流配送網(wǎng)絡(luò)；

V={1,2,…,n}，表示節(jié)點(diǎn)集，V′={0,1,2,…,n}，0表示生鮮農(nóng)產(chǎn)品配送中心；

E={(i,j)|i,j∈V，i≠j}是節(jié)點(diǎn)之間的連接??；

δ={1,2，…，m}表示自有車隊(duì)的車輛集合；

δ′={m+1，…，m′}表示按日租賃的車輛集合；

δ″={m′+1，…，m″}表示按距離租賃的車輛集合；

K=δ+δ′+δ″表示所有可用車輛集合；

qi表示客戶點(diǎn)i的需求量；

c1表示自有車輛的成本均攤到每一天得到其固定成本；

c0表示自有車輛的單位運(yùn)輸成本；

Q表示車輛載重限制；

dij表示車輛從節(jié)點(diǎn)i到節(jié)點(diǎn)j經(jīng)過的距離；

c2表示按距離租賃的車輛單位距離的租賃費(fèi)用；

c3表示按日租賃的車輛每日的租賃費(fèi)用；

dmax表示按日租賃的車輛最大配送距離；

ei表示節(jié)點(diǎn)i可以接受的最早配送時(shí)間；

li表示節(jié)點(diǎn)i可以接受的最晚配送時(shí)間；

f1表示車輛空載每千米的油耗，當(dāng)車輛已知時(shí)，它的值是常數(shù)；

f2表示車輛滿載每千米的油耗，當(dāng)車輛已知時(shí)，它的值是常數(shù)；

θijk表示車輛k從i到j(luò)的裝載率；

μ1表示配送車輛早于約定時(shí)間到達(dá)的懲罰成本系數(shù)；

μ2表示配送車輛晚于約定時(shí)間到達(dá)的懲罰成本系數(shù)；

ti表示車輛到達(dá)節(jié)點(diǎn)i的時(shí)間；

ψ表示生鮮農(nóng)產(chǎn)品隨時(shí)間變質(zhì)因子；

φ表示允許的最大變質(zhì)率；

OWNco2表示自有的碳排放權(quán)；

RENTco2表示因租賃車輛所增加的碳排放權(quán)；

σ表示配送車輛的制冷成本系數(shù)；

ω表示政府征收的碳排放稅；

決策變量：

(3)

(4)

(5)

(二) 模型建立

給定上述參數(shù)和決策變量，具有碳排放約束和時(shí)間窗的異構(gòu)車隊(duì)車輛問題模型如下

Minm·c0

(6)

(7)

(8)

(9)

(10)

s. t.

(11)

(12)

(13)

(14)

(15)

(16)

(17)

Qijk≥Q(i-1)ik+pj-M(1-xijk)，?i∈V′,?j∈V,?k∈K

(18)

Qijk≤Q(i-1)ik+pj-M(1-xijk)，?i∈V′,?j∈V,?k∈K

(19)

(20)

ti+tij-M(1-xijk)

(21)

(22)

xijk∈{0,1},?i,j∈V′，?k∈K

(23)

zik∈{0,1},?i∈V′，?k∈K

(24)

yk∈{0,1},?k∈δ″

(25)

Qijk≥0,?i,j∈V′，?k∈K

(26)

目標(biāo)函數(shù)中(6)是自有車隊(duì)固定成本，(7)是運(yùn)輸成本，(8)是租賃成本，(9)是懲罰成本，(10)是制冷成本和碳排放成本。載重限制(11)對(duì)自有車隊(duì)和租賃車輛都適用。限制(12)是按日租賃車輛是否被使用。限制(13)～(16)使得配送車輛從配送中心出發(fā)最后回到配送中心，且每一個(gè)節(jié)點(diǎn)僅被訪問一次。限制(17)表示按日租賃車輛最大配送距離。限制(18)～(19)表示供需平衡。限制(20)表明配送中心0到客戶點(diǎn)i的第k輛車的裝載量不超過總負(fù)載限制。限制(21)是滿足客戶約定的軟時(shí)間窗限制。限制(22)是為了使碳排放量低于限定值，限制(23)～(26)表示xijk、yk和zik是0,1變量，車輛負(fù)載Qijk必須大于等于0。

三、 混合遺傳算法描述

圖1 混合GA流程

遺傳算法(GA)是模擬達(dá)爾文的生物進(jìn)化論遺傳學(xué)機(jī)理設(shè)計(jì)的一種算法模型，模擬大自然中自然選擇和進(jìn)化的過程。本文結(jié)合最近鄰法構(gòu)建初始解和以此跳出局部最優(yōu)的方式設(shè)計(jì)了混合遺傳算法，算法流程見圖1。

(一) 初始種群

混合遺傳算法利用最近鄰法得到初始解，隨機(jī)一個(gè)客戶點(diǎn)作為初始點(diǎn)，然后在剩余的點(diǎn)中尋找與初始點(diǎn)最近的點(diǎn)，直到被選擇的點(diǎn)需求總和大于車輛最大負(fù)載時(shí)，再重新隨機(jī)一個(gè)初始點(diǎn)，直到所有客戶點(diǎn)全部被選擇為止，該算法所得到的解比較接近最優(yōu)解，產(chǎn)生的初始種群本身即是最優(yōu)種群，不管選擇哪些個(gè)體作為父代，均可能快速產(chǎn)生較優(yōu)的解，加快算法的收斂速度。

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

本文采用的適應(yīng)度函數(shù)是傳統(tǒng)遺傳算法的適應(yīng)度函數(shù)設(shè)置，以f=1/F為個(gè)體的適應(yīng)度，F(xiàn)為目標(biāo)函數(shù)的值，它的倒數(shù)為個(gè)體的適應(yīng)度值，記為f。

(三) 輪盤對(duì)賭選擇

本文采用輪盤對(duì)賭選擇法選擇保留的個(gè)體，根據(jù)適應(yīng)度大小選擇個(gè)體，個(gè)體的適應(yīng)度越大，則被選中的概率越高，輪盤對(duì)賭選擇法使得每一個(gè)個(gè)體都有一定的概率可以被選擇，提高解的豐富性，輪盤對(duì)賭選擇法的步驟如下：

第一步：計(jì)算個(gè)體被遺傳到下一代群體的概率；

第二步：計(jì)算累積概率；

第三步：在[0,1]之間產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)r，若r小于個(gè)體1被遺傳概率，則選擇個(gè)體1，否則選擇個(gè)體k，使r在第k-1個(gè)個(gè)體被遺傳概率和第k個(gè)個(gè)體被遺傳概率之間。

(四) 染色體交叉

染色體交叉規(guī)則是遺傳算法能否快速找到最優(yōu)解的關(guān)鍵，本文采用強(qiáng)強(qiáng)交叉的原則，綜合多篇文獻(xiàn)，本文設(shè)計(jì)了三種交叉規(guī)則，如下：

片段交叉：隨機(jī)兩個(gè)點(diǎn)(i,j)，將染色體1與染色體2中位于兩點(diǎn)之間的部分置換，如(1→2→3→4→5→6)與(6→5→4→3→2→1)在第2到第4的位置進(jìn)行置換得到(1→5→4→3→5→6)和(6→2→3→4→2→1)，然后消除重復(fù)點(diǎn)，即得到新的染色體。

連續(xù)點(diǎn)交叉：在染色體中隨機(jī)一個(gè)點(diǎn)i，i不是最后一個(gè)點(diǎn)，將兩個(gè)染色體連續(xù)的兩個(gè)點(diǎn)i和i+1位置相互置換，如(1→2→3→4→5→6)與(6→5→4→3→2→1)在第2到第3的位置進(jìn)行置換得到(1→5→4→4→5→6)和(6→2→3→3→2→1)，然后消除重復(fù)點(diǎn)，即得到新的染色體。

兩點(diǎn)交叉：隨機(jī)兩個(gè)點(diǎn)i和j,將染色體1的i位置與染色體2的j位置置換，然后消除重復(fù)點(diǎn)，即得到新的染色體。

(五) 變異

本文采用簡(jiǎn)單的三次2變換變異，使算法不會(huì)陷入局部最優(yōu)。當(dāng)隨機(jī)數(shù)小于變異概率時(shí)，則開始變異，隨機(jī)三組變異位，交換三組變異位上的顧客點(diǎn)形成新解，并與父代做比較，如果變異后產(chǎn)生的子代優(yōu)于父代，則用子代替代父代，否則放棄，循環(huán)直到被選擇的個(gè)體全部進(jìn)行變異步驟為止。

(六) 重組新種群

在進(jìn)行交叉和變異操作之后，新種群由部分父代和全部子代共同組成，為了保證快速尋找到最優(yōu)解，選擇父代適應(yīng)度排名前十的個(gè)體與子代形成新種群，新種群既保留了父代優(yōu)秀個(gè)體，也產(chǎn)生了新的優(yōu)秀子代，通過調(diào)整保留父代優(yōu)秀個(gè)體的個(gè)數(shù)和產(chǎn)生子代的個(gè)數(shù)可以提高種群收斂速度。此外，設(shè)置一個(gè)跳出最優(yōu)解的機(jī)制，即當(dāng)某一最優(yōu)解連續(xù)次數(shù)超過10次時(shí)，利用最近鄰法產(chǎn)生一個(gè)解替代原種群中的最差的解，使得算法進(jìn)一步搜索全局。

(七) 終止條件

終止條件設(shè)置為算法循環(huán)達(dá)到一定的迭代次數(shù)之后，將此時(shí)所得的最優(yōu)的解作為模型的最優(yōu)解，輸出最優(yōu)配送和最優(yōu)總成本，終止算法。

四、 計(jì)算分析

為了研究混合GA的有效性和數(shù)學(xué)公式的有效性，本文設(shè)置了一個(gè)數(shù)據(jù)集，并采用混合GA和傳統(tǒng)TS算法計(jì)算結(jié)果比較，在一臺(tái)具有Intel 2.40GHz，安裝內(nèi)存4GB的電腦上，運(yùn)用MATLAB R2018b軟件計(jì)算的結(jié)果。

(一) 數(shù)據(jù)描述

本文選取10客戶點(diǎn)、25客戶點(diǎn)、50客戶點(diǎn)、75客戶點(diǎn)和100客戶點(diǎn)做案例驗(yàn)證，0代表配送中心，其他點(diǎn)坐標(biāo)、需求數(shù)據(jù)如表1，所有自有車隊(duì)和租賃車隊(duì)的最大載重量限制相同為60，參考Krajewska and Kopfer[2]文中設(shè)置自有車輛持有成本為c1=100，按距離租賃車輛單位距離收費(fèi)c2=2.25，按日租賃的車輛每日收費(fèi)c3=200且有最大配送距離限制為dmax=120公里，所有車輛空載時(shí)單位距離運(yùn)費(fèi)為0.58元，車輛滿載時(shí)單位距離運(yùn)費(fèi)為1.68元，本文使用的一般車輛的運(yùn)行平均速度設(shè)置為60公里/小時(shí)。

表1 0～100節(jié)點(diǎn)需求、位置和時(shí)間窗數(shù)據(jù)

表1(續(xù))

生鮮產(chǎn)品配送有時(shí)間窗限制，表1中給出了每個(gè)客戶點(diǎn)的時(shí)間需求限制，配送車輛均從早晨5點(diǎn)開始配送，如果提前到達(dá)顧客點(diǎn)，需要承擔(dān)懲罰成本u1=10元/小時(shí)，如果遲到顧客點(diǎn)，需要承擔(dān)懲罰成本u2=20元/小時(shí)。生鮮配送車輛在行駛過程中不僅需要支付運(yùn)輸成本和固定成本等，還需要為產(chǎn)品保鮮付出制冷成本，假設(shè)自有車輛的制冷系數(shù)為0.068，Wang and Li[7]文中給出碳排放系數(shù)為0.0025，假設(shè)碳排放成本為1元/千克，配送中心可用于運(yùn)輸消耗的碳排放權(quán)為30千克。每一輛承擔(dān)配送任務(wù)的車輛均從配送中心出發(fā)，完成配送任務(wù)后回到配送中心。

經(jīng)過多次試驗(yàn)測(cè)試，混合GA的參數(shù)設(shè)置見表2。

表2 混合GA參數(shù)設(shè)置

表3 混合GA和傳統(tǒng)TS對(duì)比

(二) 混合GA與傳統(tǒng)TS比較

為了研究混合遺傳算法的性能，本文進(jìn)行了一個(gè)實(shí)驗(yàn)來驗(yàn)證混合GA的有效性和穩(wěn)定性，該實(shí)驗(yàn)中配送任務(wù)均由自有車隊(duì)承擔(dān)。計(jì)算結(jié)果如表3所示，從表3中可知，與傳統(tǒng)禁忌搜索算法相比，本文設(shè)計(jì)的混合遺傳算法在客戶點(diǎn)逐漸增加的過程中提高了最優(yōu)解的質(zhì)量，在客戶點(diǎn)為10時(shí)，與傳統(tǒng)禁忌搜索算法相似為566.8。當(dāng)客戶點(diǎn)為25和50時(shí)，混合遺傳算法獲得更好的解，對(duì)最優(yōu)解的優(yōu)化率分別為12.8%和2.5%，客戶點(diǎn)為75和100時(shí)，混合遺傳算法的優(yōu)化率也達(dá)到了達(dá)到3.6%?？蛻酎c(diǎn)為10時(shí)，混合遺傳算法能夠很快得到最優(yōu)值，偶爾會(huì)陷入局部最優(yōu)，客戶點(diǎn)增多時(shí)，混合遺傳算法獲得的解更好，且所使用的車輛數(shù)更少。表4是混合遺傳算法運(yùn)行10次的計(jì)算結(jié)果，從表4中可知，混合遺傳算法的計(jì)算結(jié)果較為平穩(wěn)，最優(yōu)值為2579.9，最差值為2613.1，平均函數(shù)值為2597.7，最佳運(yùn)輸車輛數(shù)為13,可知該算法的魯棒性較好，能夠獲得較好的解。

表4 混合GA計(jì)算結(jié)果

圖2 迭代過程對(duì)比

為了更直觀地看到混合遺傳算法的優(yōu)化效果，本文在這一部分進(jìn)行了迭代過程對(duì)比實(shí)驗(yàn)，結(jié)果如圖2，很明顯可以看出，采用了最近鄰元啟發(fā)式算法產(chǎn)生的初始種群獲得較優(yōu)的初始解，混合遺傳算法和緊急搜索算法均在較短時(shí)間得到最優(yōu)解并趨于穩(wěn)定，而不管是從所得最優(yōu)解還是迭代過程相比混合遺傳算法均優(yōu)于傳統(tǒng)禁忌搜索算法。

(三) 自有車隊(duì)數(shù)量變化分析

為了觀察自有車隊(duì)和租賃車隊(duì)對(duì)成本的影響，本文變換自有車隊(duì)數(shù)量進(jìn)行了試驗(yàn)，計(jì)算結(jié)果如表5所示。從表5中可知，持有少量的自有車隊(duì)，在總需求不變前提下，租賃車輛可以降低配送中心總成本，客戶點(diǎn)為50時(shí)，完全使用自有車隊(duì)最低成本為2579.7，自有車隊(duì)持有數(shù)量降低過程中，總成本和碳排放成本逐漸降低，當(dāng)自有車隊(duì)數(shù)量為9時(shí)，目標(biāo)函數(shù)值反而高于自有車隊(duì)數(shù)量為10時(shí)，當(dāng)自有車輛極少時(shí)，總成本函數(shù)值并非一直持下降趨勢(shì)，而是逐漸趨于平緩，在持有車輛數(shù)為3時(shí)，成本升高，這與Krajewska and Kopfer[2]的結(jié)論是一致的。從碳排放成本變化知，如果單從配送企業(yè)來看，租賃車輛對(duì)減少自身的碳排放權(quán)消耗是有效的，但是還得進(jìn)一步觀察對(duì)總體碳排放量是否產(chǎn)生影響?？梢园l(fā)現(xiàn)，在需求不穩(wěn)定時(shí)，選擇自有車隊(duì)的持有規(guī)模是必要的，合理的自有車隊(duì)規(guī)模這給生鮮配送中心管理者提供了一定的借鑒。另一方面，從計(jì)算數(shù)據(jù)來看，租賃車輛用于補(bǔ)充自身運(yùn)力的不足，此種方式對(duì)懲罰成本沒有顯著性影響，從表5中可知，完全由自有車隊(duì)完成配送任務(wù)時(shí)總的懲罰成本為238.5144，隨著自有車隊(duì)規(guī)模的減少，懲罰成本呈現(xiàn)不規(guī)則變動(dòng)，在持有3輛車時(shí)，懲罰成本低于自有車隊(duì)配送，其他時(shí)候均高于自有車隊(duì)配送。本文介紹了兩種不同的租賃方式，在自有車隊(duì)規(guī)模變化時(shí)，合理選擇不同的租賃方式對(duì)成本有一定的影響。

表5 自有車隊(duì)不同規(guī)模下成本計(jì)算數(shù)據(jù)

(四) 碳排放量變化趨勢(shì)分析

圖3 碳排放量變化趨勢(shì)對(duì)比

本文不僅考慮了經(jīng)濟(jì)因素，同時(shí)考慮了環(huán)境因素，計(jì)算結(jié)果如圖3所示，現(xiàn)有文獻(xiàn)中考慮碳排放成本基本從社會(huì)出發(fā)，將碳排放成本計(jì)算在生鮮配送廠商自身總成本之內(nèi)，因租賃車輛少消耗的碳排放權(quán)未考慮在限制之內(nèi)。從圖3可以看出隨著降低自有車隊(duì)規(guī)模，生鮮配送企業(yè)自身的碳排放量會(huì)逐漸遞減，如圖3中線條1，租賃所帶來的碳排放權(quán)逐漸增加，如線條2，總體碳排放量基本處于穩(wěn)定，如線條3?？紤]各種碳排放量的變化可知，租賃車輛對(duì)碳排放量的整體影響較小，但是由此所帶來的成本影響較大，這進(jìn)一步表明在需求非常不穩(wěn)定時(shí)，使用外部車隊(duì)是配送企業(yè)優(yōu)化自身成本的重要手段，且對(duì)降低碳排放有適當(dāng)?shù)淖饔谩?/p>

綜合上述分析，驗(yàn)證了混合遺傳算法的有效性和實(shí)用性，該算法在實(shí)際應(yīng)用中優(yōu)于傳統(tǒng)算法，具有一定的實(shí)際意義。其次，通過上述案例分析，也為生鮮配送企業(yè)提供了幾點(diǎn)管理啟示：一是不可提前預(yù)測(cè)需求時(shí)，自身持有一定車隊(duì)，在必要時(shí)向周邊租賃公司租賃類似車輛配送可以降低配送企業(yè)的總成本，因此配送企業(yè)在選址時(shí)應(yīng)充分考慮與周邊汽車租賃企業(yè)合作的因素，以備不時(shí)之需；二是在配送企業(yè)自身碳排放權(quán)不足時(shí)，除了在碳交易市場(chǎng)購買碳排放權(quán)，也可以采用租賃車輛的方式，將運(yùn)輸過程的碳排放轉(zhuǎn)移到汽車租賃企業(yè)，以此彌補(bǔ)自身碳排放權(quán)；三是租賃車隊(duì)雖然可以在一定程度上降低配送企業(yè)成本，但是對(duì)顧客滿意度影響并不明顯，因此需要和租賃企業(yè)協(xié)商，在降低成本的同時(shí)保證顧客滿意度。

五、 結(jié)論與展望

本文研究了具有碳排放約束和時(shí)間窗的異構(gòu)車隊(duì)車輛問題，為生鮮農(nóng)產(chǎn)品配送企業(yè)降低成本，響應(yīng)國家低碳號(hào)召提供借鑒。本文提出了一個(gè)混合遺傳算法來解決具有碳排放約束和時(shí)間窗的異構(gòu)車隊(duì)車輛問題，計(jì)算實(shí)驗(yàn)證明該算法有較強(qiáng)的魯棒性。本文還對(duì)自有車隊(duì)與租賃車隊(duì)的成本和碳排放進(jìn)行了敏感性分析，可為生鮮配送企業(yè)提供管理啟示。計(jì)算分析表明，考慮外部車隊(duì)對(duì)降低碳排放和成本是有效的，異構(gòu)車隊(duì)能夠降低本企業(yè)的碳排放，通過不同的租賃方式和選擇能夠使總碳排放量變化較小，在對(duì)環(huán)境友好的前提下，降低企業(yè)配送成本。

未來可能的研究方向之一包括考慮需求的隨機(jī)性等因素，使問題更貼合實(shí)際。另一個(gè)研究方向是根據(jù)問題特點(diǎn)，開發(fā)基于分支—割平面或分支—定價(jià)等確切算法的數(shù)學(xué)啟發(fā)式算法，使問題的求解更加高效。