王 澤,楊信豐,劉蘭芬
(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院,甘肅 蘭州 730070)
隨著社會(huì)經(jīng)濟(jì)不斷進(jìn)步,電商的發(fā)展極大地促進(jìn)了快遞行業(yè)的發(fā)展?!熬G色物流”也逐漸受到更多快遞企業(yè)的重視,國(guó)內(nèi)一些快遞公司開(kāi)始逐步嘗試使用純電動(dòng)汽車(chē)作為配送車(chē)輛,來(lái)完成從配送中心到客戶的配送任務(wù)。相較于傳統(tǒng)燃油汽車(chē),新能源電動(dòng)車(chē)具有環(huán)保、節(jié)能、噪聲污染小等優(yōu)勢(shì),新能源電動(dòng)汽車(chē)可以更好地為整個(gè)社會(huì)創(chuàng)造經(jīng)濟(jì)效益和社會(huì)效益。但是電動(dòng)車(chē)在配送過(guò)程中需要考慮載重量、里程、充電需求等約束,使得配送問(wèn)題更加復(fù)雜。
國(guó)內(nèi)外部分學(xué)者對(duì)電動(dòng)車(chē)調(diào)度進(jìn)行研究,并取得了一定的成果,如Schneider等[1]考慮電池容量、服務(wù)時(shí)間等約束,提出成本最優(yōu)的電動(dòng)車(chē)路徑規(guī)劃和調(diào)度模型,采用混合啟發(fā)式算法對(duì)模型進(jìn)行求解,計(jì)算結(jié)果能較好地反映出電動(dòng)車(chē)的行駛路徑和充電決策。Haghain等[2]利用遺傳算法求解時(shí)間依賴型車(chē)輛調(diào)度問(wèn)題,將求得結(jié)果與精確算法計(jì)算結(jié)果進(jìn)行比較。Desaulniers等[3]對(duì)電動(dòng)商用車(chē)(ECV)車(chē)隊(duì)進(jìn)行路徑規(guī)劃時(shí),考慮4種情況下帶時(shí)間窗的電動(dòng)車(chē)輛路徑規(guī)劃問(wèn)題,結(jié)合算例驗(yàn)證算法的優(yōu)越性。Bruglieri等[4]利用可變鄰域搜索分支的算法解決帶有時(shí)間窗的電動(dòng)汽車(chē)路徑問(wèn)題。高升[5]采用遺傳算法解決以總配送成本最小為目標(biāo)的考慮客戶時(shí)間窗的電動(dòng)汽車(chē)路徑優(yōu)化問(wèn)題模型。楊珺等[6]設(shè)計(jì)禁忌搜索?改進(jìn)clarke-wright節(jié)省的兩階段啟發(fā)式算法,研究基于電動(dòng)汽車(chē)物流配送網(wǎng)絡(luò)的換電站選址與路徑優(yōu)化問(wèn)題。邵塞等[7]以費(fèi)用最小化為目標(biāo),考慮電動(dòng)汽車(chē)的里程、載重、時(shí)間窗等約束,用遺傳算法解決電動(dòng)汽車(chē)集散貨一體化車(chē)輛路徑問(wèn)題模型。張艷偉等[8]以總成本最小為目標(biāo),建立純電動(dòng)汽車(chē)運(yùn)營(yíng)的考慮貨物類別的路徑優(yōu)化問(wèn)題。揭婉晨等[9]利用列生成的分支定價(jià)算法解決基于時(shí)間窗的電動(dòng)車(chē)車(chē)輛路徑問(wèn)題。王永聰[10]在研究車(chē)輛路徑問(wèn)題的基礎(chǔ)上,建立以城市配送為目標(biāo)的純電動(dòng)汽車(chē)車(chē)輛路徑模型,并應(yīng)用最鄰近算法和蟻群算法對(duì)其模型進(jìn)行求解研究。劉蘭芬等[11]在考慮時(shí)間網(wǎng)絡(luò)的基礎(chǔ)上,建立以客戶滿意度最高、配送時(shí)間最短等多目標(biāo)物流車(chē)輛調(diào)度模型,并用遺傳算法求解該模型。陶胤強(qiáng)等[12]以最小費(fèi)用為目標(biāo),研究基于時(shí)間窗的多車(chē)型多費(fèi)用非滿載的車(chē)輛路徑問(wèn)題。梁鳳婷等[13]研究低碳環(huán)境下電動(dòng)汽車(chē)的車(chē)輛路徑問(wèn)題,以低碳、節(jié)能環(huán)保和低成本為目標(biāo),建立燃油車(chē)和電動(dòng)車(chē)的車(chē)輛路徑模型,并用遺傳算法對(duì)模型進(jìn)行分析和求解。
從研究現(xiàn)狀可知,國(guó)內(nèi)外學(xué)者對(duì)純電動(dòng)汽車(chē)調(diào)度方案的研究成果相對(duì)較少,針對(duì)具有時(shí)間窗的車(chē)輛調(diào)度問(wèn)題研究較多,主要采用智能算法求解車(chē)輛調(diào)度方案,如遺傳算法、蟻群算法、模擬退火算法等。鑒于此,本文著重考慮單向車(chē)輛調(diào)度模型,重點(diǎn)考慮時(shí)間窗約束、里程約束及充電需求,提出電動(dòng)汽車(chē)基于電量消耗的車(chē)輛調(diào)度模型,合理規(guī)劃包括配送方案、車(chē)輛行駛路徑、車(chē)輛發(fā)車(chē)時(shí)間及車(chē)輛充電計(jì)劃在內(nèi)的車(chē)輛調(diào)度方案。
由于電動(dòng)汽車(chē)是靠電能驅(qū)動(dòng),故充電是電動(dòng)汽車(chē)在行駛過(guò)程中必須面對(duì)的問(wèn)題之一。當(dāng)電池電量不足以完成剩余的配送任務(wù)時(shí),電動(dòng)車(chē)需要進(jìn)入到鄰近的充電站進(jìn)行充電,以供其完成剩余的配送任務(wù)。在本文中,充電站采用的是快速充電方式,使電動(dòng)車(chē)在30 min左右就可以完成充電。但是由于充電站可能不位于車(chē)輛既定的行駛線路上,車(chē)輛會(huì)發(fā)生行駛偏移,因而帶來(lái)配送中心總成本的增加。
由于電動(dòng)車(chē)配送過(guò)程需要考慮電動(dòng)車(chē)的續(xù)駛里程、電池電量、充電站位置、客戶服務(wù)的時(shí)間窗和車(chē)輛額定載重等諸多因素,為使問(wèn)題更加簡(jiǎn)潔明了,預(yù)先進(jìn)行以下假設(shè)。
1) 只有一個(gè)配送中心,所有車(chē)輛從配送中心出發(fā)最后返回原配送中心;
2) 客戶的數(shù)量、客戶的位置、客戶服務(wù)的時(shí)間窗及每個(gè)客戶的需求量均已知,且車(chē)輛的總載重不得超過(guò)車(chē)輛的額定載重;
3) 配送車(chē)輛從配送中心出發(fā),電池為滿電狀態(tài),且在貨物裝卸過(guò)程中不存在電量的消耗;
4) 貨物流向?yàn)閱蜗?,只進(jìn)行配送貨物不進(jìn)行收集貨物;
5) 電動(dòng)車(chē)的額定續(xù)駛里程和充電時(shí)間均已知。
C0為總費(fèi)用;
Cfk為車(chē)輛k的固定費(fèi)用;
Ctk為車(chē)輛k的行駛費(fèi)用;
Cmk為車(chē)輛k的充電費(fèi)用;
Cpk為車(chē)輛k的早到或晚到產(chǎn)生的懲罰費(fèi)用;
O為配送中心;
K為車(chē)輛集合;
M為充電站集合;
N為客戶點(diǎn)集合;
L為配送中心、充電站、客戶點(diǎn)的集合,L=O∪M∪N;
speed為車(chē)輛額定行駛速度;
P為電動(dòng)車(chē)額定電量;
為車(chē)輛k到達(dá)集合點(diǎn)i時(shí)電量,i∈L;
為車(chē)輛k離開(kāi)集合點(diǎn)i時(shí)電量,i∈L;
ei為客戶點(diǎn)i的最早服務(wù)時(shí)間;
li為客戶點(diǎn)i的最晚服務(wù)時(shí)間;
epu為表示車(chē)輛早于時(shí)間窗到達(dá)造成的等待懲罰成本;
lpu為表示車(chē)輛晚于時(shí)間窗到達(dá)的懲罰成本;
為車(chē)輛到達(dá)集合點(diǎn)i的時(shí)刻,i∈L;
為車(chē)輛離開(kāi)集合點(diǎn)i的時(shí)刻,i∈L;
為車(chē)輛在集合點(diǎn)i卸貨、充電時(shí)間,i∈L;
為車(chē)輛在客戶點(diǎn)處等待服務(wù)時(shí)間,i∈N;
Djk為車(chē)輛k到達(dá)點(diǎn)j時(shí)的剩余電量里程;
di j為客戶點(diǎn)i和j之間的距離;
Wmax為車(chē)輛額定載重量;
Dmax為車(chē)輛最大行駛距離;
Ed為電動(dòng)車(chē)電量單位里程消耗;
Wi為車(chē)輛載重量;
1) 總成本分析??偱渌统杀景?部分。
(1) 車(chē)輛固定成本。固定成本主要包括車(chē)輛折舊費(fèi),司機(jī)勞務(wù)費(fèi),餐飲費(fèi)等。
(2) 車(chē)輛行駛費(fèi)用。行駛費(fèi)用與行駛距離相關(guān),車(chē)輛單位行駛成本為
(3) 充電費(fèi)用。充電費(fèi)用的多少與電池剩余電量相關(guān),剩余電量越高,則充電費(fèi)用越少,充電時(shí)的單位充電成本為c2,Cmk=EdS c2,S為勻速行駛里程。
(4) 懲罰成本。懲罰成本主要由車(chē)輛早于或晚于客戶服務(wù)時(shí)間窗而引起,車(chē)輛早于服務(wù)時(shí)間窗到達(dá)需等待,等待時(shí)間為ei?,車(chē)輛晚于服務(wù)時(shí)間窗到達(dá),客戶需要等待的時(shí)間為?li,則總懲罰成本為
2) 電量分析。
假設(shè)該電動(dòng)車(chē)行駛過(guò)程為勻速狀態(tài),那么,根據(jù)文獻(xiàn)[14]提出的能耗經(jīng)濟(jì)性評(píng)價(jià)指標(biāo),本文提出純電動(dòng)汽車(chē)在勻速行駛狀態(tài)下電池電量的單位里程能耗為
其中,G為 車(chē)輛重量;t為純電動(dòng)車(chē)勻速行駛時(shí)間;b為道路坡度;u為車(chē)速; ηt為傳動(dòng)系統(tǒng)效率;f為滾動(dòng)阻力系數(shù);R為空氣阻力系數(shù);A為汽車(chē)迎風(fēng)面積。電動(dòng)車(chē)從點(diǎn)i到達(dá)點(diǎn)j(i,j∈L)的剩余電量為Pik=P?Eddij。
3) 車(chē)輛在各點(diǎn)停留時(shí)間分析。
,i∈L。若i表示客戶點(diǎn),則其表示車(chē)輛在該點(diǎn)的卸貨時(shí)間;若i表示充電站,則其表示車(chē)輛在充電站的充電時(shí)間;若i表示配送中心,則停留時(shí)間為0。
4) 車(chē)輛等待時(shí)間分析。
,i∈N。若車(chē)輛提早到達(dá)客戶點(diǎn)N,則要等待,等待時(shí)間為若在規(guī)定時(shí)間內(nèi)到達(dá),則不需要等待,等待時(shí)間為0。
5) 車(chē)輛到達(dá)客戶點(diǎn)時(shí)刻分析。
電動(dòng)車(chē)輛從客戶點(diǎn)i離開(kāi),到達(dá)客戶點(diǎn)j的時(shí)刻為電動(dòng)車(chē)離開(kāi)客戶點(diǎn)i的時(shí)刻加上車(chē)輛在客戶點(diǎn)i和j之間的行駛時(shí)間,即
根據(jù)上述分析,構(gòu)建考慮電量消耗的電動(dòng)汽車(chē)調(diào)度優(yōu)化模型如下。
式(4)為模型的目標(biāo)函數(shù),保證總成本最??;式(5)~式(15)均為模型的約束條件。其中,式(5)保證每一位顧客都只被服務(wù)1次;式(6)保證車(chē)輛開(kāi)始完成配送任務(wù)從配送中心出發(fā)和結(jié)束;式(7)保證在客戶點(diǎn)卸貨過(guò)程中不消耗電量;式(8)表示電量足夠到達(dá)集合L中 的任意點(diǎn);式(9)表示車(chē)輛在點(diǎn)i和點(diǎn)j之間的行駛時(shí)間;式(10)表示車(chē)輛離開(kāi)集合點(diǎn)i的時(shí)間;式(11)表示車(chē)輛到達(dá)集合點(diǎn)j的時(shí)間;式(12)表示車(chē)輛實(shí)際載重量不超過(guò)額定載重量;式(13)表示車(chē)輛若提早到達(dá)集合點(diǎn)i的等待時(shí)間;式(14)表示決策變量是0?1變量;式(15)表示懲罰成本函數(shù)。
車(chē)輛路徑問(wèn)題屬于NP-hard問(wèn)題,該問(wèn)題約束條件繁多,規(guī)模較大。遺傳算法具有強(qiáng)大的搜索能力和自適應(yīng)性,因此遺傳算法對(duì)于求解較為復(fù)雜的大型網(wǎng)絡(luò)車(chē)輛調(diào)度問(wèn)題具有較好的效果。本文選用遺傳算法求解電動(dòng)汽車(chē)調(diào)度方案模型。
本文采用自然數(shù)編碼的方式[5],將染色體長(zhǎng)度定義為足夠大(2n+1),其中,n為顧客的個(gè)數(shù);m表示充電站的個(gè)數(shù);k表示配送中心的車(chē)輛數(shù)。將配送中心的編號(hào)設(shè)定為0,n位客戶的編號(hào)分別設(shè)定為1,2,3,···,n,可以將m個(gè)充電站的編號(hào)分別設(shè)定為n+1,n+2,···,n+m。最后在起點(diǎn)和終點(diǎn)分別插入配送中心代碼0,即構(gòu)成1條染色體。例如,某配送中心為5位顧客提供服務(wù),配送區(qū)域有1個(gè)充電站,假如其中1條如圖1所示,則該染色體表示的路徑為第1輛車(chē)從配送中心出發(fā),先后經(jīng)過(guò)客戶點(diǎn)3、4,然后進(jìn)入充電站6進(jìn)行充電,充電完成后返回配送中心,第2輛車(chē)經(jīng)過(guò)客戶點(diǎn)1、2、5返回配送中心。
圖 1 路徑染色體路徑Figure 1 Path of chromosome
首先將所有客戶與充電站的編號(hào)進(jìn)行隨機(jī)排列,設(shè)wi表示各點(diǎn)的需求量,然后考慮每輛汽車(chē)的載重約束,若則在染色體第γ 位后插入編號(hào)0,重復(fù)計(jì)算直至考慮完所有客戶的需求量約束,再考慮充電需求,若里程不足需求充電時(shí),在該客戶點(diǎn)后插入最近的充電站編號(hào),直至判斷完所有客戶的里程約束。最后在起點(diǎn)和終點(diǎn)分別插入配送中心代碼0,即構(gòu)成1條染色體。重復(fù)多次計(jì)算,即構(gòu)成初始種群popsize。
對(duì)種群中的每條染色體進(jìn)行解碼,解碼后可得到每條染色體下的路徑,但是車(chē)輛的發(fā)車(chē)時(shí)間沒(méi)有確定,再用遍歷法選出各輛車(chē)最適宜的發(fā)車(chē)時(shí)刻。具體思路如下。在配送中心的運(yùn)營(yíng)時(shí)間6:00~21:00內(nèi),按每間隔10 min發(fā)車(chē),計(jì)算總配送成本。最小配送成本的發(fā)車(chē)時(shí)刻即為最優(yōu)的發(fā)車(chē)時(shí)刻。若存在多個(gè)最優(yōu)發(fā)車(chē)時(shí)刻,選取本時(shí)間段內(nèi)時(shí)間最小的時(shí)刻為發(fā)車(chē)時(shí)刻。根據(jù)上述求得每條路徑的總配送成本,可將目標(biāo)值的倒數(shù)定義為對(duì)應(yīng)染色體的適應(yīng)值:Zi=1/C0。適應(yīng)度值作為個(gè)體性能的評(píng)價(jià)指標(biāo),其值越大,配送總成本越低,越接近最優(yōu)解。
1) 選擇。
本文采用最佳個(gè)體保存和適應(yīng)度比例相結(jié)合的方式來(lái)對(duì)染色體進(jìn)行選擇[15],將每代個(gè)體中的H個(gè)染色體按其適應(yīng)度值從大到小依次排列,排在第1位的即是適應(yīng)度值最大的,將其直接復(fù)制到下一代當(dāng)中,對(duì)于下一代中其余的H-1個(gè)染色體則采用輪盤(pán)賭的方式來(lái)產(chǎn)生。這樣的選擇方式既能保證適應(yīng)度最大地進(jìn)入下一代,也能使適應(yīng)度值較大的有機(jī)會(huì)進(jìn)入下一代。
2) 交叉。
本文采用部分匹配交叉(PMX重組)方式,先對(duì)群體隨機(jī)配對(duì),產(chǎn)生1對(duì)染色體(父代),2個(gè)染色體被選的位置相同,交換這2組基因的位置,最后進(jìn)行沖突檢測(cè),刪除染色體中重復(fù)的基因,保證基因不重復(fù)。該方式能較好地保持群體多樣性。選取2個(gè)父代染色體A和B并隨機(jī)生成2個(gè)交叉點(diǎn),把2個(gè)交叉點(diǎn)之間的基因片段替換為對(duì)方染色體,得到A1和B1??蓮膱D2(b)中看出基因之間的對(duì)應(yīng)關(guān)系:基因3、5和4相互對(duì)應(yīng);基因1和6相互對(duì)應(yīng)。然后再替換掉交叉點(diǎn)之前和交叉點(diǎn)之后基因片段中重復(fù)的基因,如將染色體A1中交叉點(diǎn)后重復(fù)的基因1、5分別替換為與其對(duì)應(yīng)且不重復(fù)的基因6、4,對(duì)染色體B1同樣處理,即可得到染色體A2和B2,具體過(guò)程如圖2所示。
3) 變異。
本文采用基因片段反轉(zhuǎn)變異的變異策略[16],此策略在排序問(wèn)題方面性能較優(yōu),優(yōu)于傳統(tǒng)的對(duì)換變異等策略。選取任意染色體A并在該染色體上隨機(jī)生成2個(gè)交叉點(diǎn),把2個(gè)交叉點(diǎn)之間的基因片段進(jìn)行翻轉(zhuǎn)即可得到變異后的染色體A',具體如圖3所示。
圖 2 染色體交叉示意圖Figure 2 Chromosome for crossover
圖 3 染色體變異示意圖Figure 3 Chromosome for mutation
4) 終止策略。
若此時(shí)的迭代次數(shù)小于初始規(guī)定的總次數(shù),則返回至上述步驟,繼續(xù)進(jìn)行迭代;若此時(shí)迭代次數(shù)等于初始規(guī)定的迭代總次數(shù),則對(duì)最后一代的染色體進(jìn)行解碼操作。此時(shí)即可得到該車(chē)輛調(diào)度問(wèn)題的近似最優(yōu)解,又可同時(shí)得到配送中心車(chē)輛的配送路線和配送中心總成本。
設(shè)某配送案例中,有1個(gè)配送中心,4個(gè)充電站,充電時(shí)間為0.3 h,5輛相同型號(hào)的配送車(chē)輛共服務(wù)50個(gè)客戶。且配送中心、充電站、客戶的坐標(biāo)、客戶點(diǎn)需求和服務(wù)時(shí)間窗均已知。車(chē)輛從配送中心出發(fā),考慮到有充電需求,所以應(yīng)合理安排路徑,完成配送任務(wù)。車(chē)輛詳細(xì)參數(shù)如表1所示,配送過(guò)程中各項(xiàng)成本如表2所示,實(shí)例中各客戶的信息如表3所示。
表 1 某電動(dòng)貨車(chē)能耗計(jì)算相關(guān)參數(shù)Table 1 Relevant parameters of energy consumption calculation of the electric truck
終止條件為Genmax=1 000,種群大小NP=40,交叉概率pc=0.8,變異概率pm=0.3。為避免結(jié)果出現(xiàn)偶然性,本文直接使模型重復(fù)計(jì)算10次,選取10次中配送總成本最小的作為最優(yōu)值。經(jīng)過(guò)計(jì)算,車(chē)輛的最佳配送路徑和遺傳算法迭代圖如圖4、圖5所示,成本及路線結(jié)果如表4所示。此時(shí),線路上最優(yōu)成本為2 266.158元,5輛車(chē)共6次進(jìn)入充電站進(jìn)行充電,其中充電成本共計(jì)80元,車(chē)輛固定成本為500元,車(chē)輛行駛成本為1 686.158元,得到最優(yōu)配送路徑后,再用枚舉法考慮顧客的服務(wù)時(shí)間窗,計(jì)算在配送中心運(yùn)營(yíng)時(shí)間內(nèi)各車(chē)輛的最佳發(fā)車(chē)時(shí)間。求得第1輛配送車(chē)輛的發(fā)車(chē)時(shí)間為6:00,懲罰成本為208.38元;第2輛配送車(chē)輛的發(fā)車(chē)時(shí)間為6:00,懲罰成本為364.21元;第3輛配送車(chē)輛的發(fā)車(chē)時(shí)間為6:00,懲罰成本為170.18元;第4輛配送車(chē)輛的發(fā)車(chē)時(shí)間為6:00,懲罰成本為148.41元;第5輛配送車(chē)輛的發(fā)車(chē)時(shí)間為9:30,懲罰成本為4.65元。此時(shí)配送中心考慮懲罰成本后的總配送成本為3 161.99元。每輛車(chē)的最佳發(fā)車(chē)時(shí)間及到達(dá)顧客和充電站的時(shí)間如表5所示。
表 2 配送過(guò)程各項(xiàng)成本Table 2 Cost of the distribution process元
本文基于電動(dòng)車(chē)電量特性,充分考慮電動(dòng)車(chē)電量消耗、里程約束、載重約束、顧客服務(wù)約束等,建立以配送總成本最小為目標(biāo)的基于電量消耗帶時(shí)間窗的電動(dòng)汽車(chē)路徑規(guī)劃問(wèn)題模型,對(duì)模型中配送中心總成本、電動(dòng)車(chē)電量的單位里程能耗、電動(dòng)車(chē)停留時(shí)間、電動(dòng)車(chē)行駛時(shí)間等進(jìn)行分析;采用遺傳算法首先求解出該模型中配送車(chē)輛的最佳配送方案,該配送方案包括車(chē)輛的行駛路線和行駛過(guò)程中的充電計(jì)劃,再結(jié)合枚舉法在配送中心運(yùn)營(yíng)時(shí)間內(nèi)以10 min為時(shí)間間隔,優(yōu)選出配送車(chē)輛懲罰成本最小時(shí)的最優(yōu)發(fā)車(chē)時(shí)刻,從而得到車(chē)輛到達(dá)每一客戶點(diǎn)及充電站的時(shí)刻。最后結(jié)合算例,計(jì)算出最佳配送路線、充電方案、最優(yōu)發(fā)車(chē)時(shí)刻以及最小總配送成本,驗(yàn)證了該模型和算法的有效性和正確性。但本文只研究了基于時(shí)間窗的電動(dòng)汽車(chē)調(diào)度問(wèn)題,而現(xiàn)實(shí)生活中,道路實(shí)際情況,以及顧客的服務(wù)需求都是動(dòng)態(tài)變化的。如何根據(jù)實(shí)際的動(dòng)態(tài)要求,將是今后進(jìn)一步研究的內(nèi)容。
表 3 算例數(shù)據(jù)1)Table 3 Data of example
圖 4 車(chē)輛配送路徑Figure 4 Vehicle delivery path
圖 5 遺傳算法迭代過(guò)程示意圖Figure 5 The iteration process diagram of genetic algorithm
表 4 計(jì)算結(jié)果Table 4 Results of calculation
表 5 客戶配送時(shí)刻表Table 5 Customer delivery schedule