考慮電量消耗的車輛調(diào)度優(yōu)化研究

王 澤，楊信豐，劉蘭芬

(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070)

隨著社會(huì)經(jīng)濟(jì)不斷進(jìn)步，電商的發(fā)展極大地促進(jìn)了快遞行業(yè)的發(fā)展。“綠色物流”也逐漸受到更多快遞企業(yè)的重視，國(guó)內(nèi)一些快遞公司開始逐步嘗試使用純電動(dòng)汽車作為配送車輛，來完成從配送中心到客戶的配送任務(wù)。相較于傳統(tǒng)燃油汽車，新能源電動(dòng)車具有環(huán)保、節(jié)能、噪聲污染小等優(yōu)勢(shì)，新能源電動(dòng)汽車可以更好地為整個(gè)社會(huì)創(chuàng)造經(jīng)濟(jì)效益和社會(huì)效益。但是電動(dòng)車在配送過程中需要考慮載重量、里程、充電需求等約束，使得配送問題更加復(fù)雜。

國(guó)內(nèi)外部分學(xué)者對(duì)電動(dòng)車調(diào)度進(jìn)行研究，并取得了一定的成果，如Schneider等[1]考慮電池容量、服務(wù)時(shí)間等約束，提出成本最優(yōu)的電動(dòng)車路徑規(guī)劃和調(diào)度模型，采用混合啟發(fā)式算法對(duì)模型進(jìn)行求解，計(jì)算結(jié)果能較好地反映出電動(dòng)車的行駛路徑和充電決策。Haghain等[2]利用遺傳算法求解時(shí)間依賴型車輛調(diào)度問題，將求得結(jié)果與精確算法計(jì)算結(jié)果進(jìn)行比較。Desaulniers等[3]對(duì)電動(dòng)商用車(ECV)車隊(duì)進(jìn)行路徑規(guī)劃時(shí)，考慮4種情況下帶時(shí)間窗的電動(dòng)車輛路徑規(guī)劃問題，結(jié)合算例驗(yàn)證算法的優(yōu)越性。Bruglieri等[4]利用可變鄰域搜索分支的算法解決帶有時(shí)間窗的電動(dòng)汽車路徑問題。高升[5]采用遺傳算法解決以總配送成本最小為目標(biāo)的考慮客戶時(shí)間窗的電動(dòng)汽車路徑優(yōu)化問題模型。楊珺等[6]設(shè)計(jì)禁忌搜索?改進(jìn)clarke-wright節(jié)省的兩階段啟發(fā)式算法，研究基于電動(dòng)汽車物流配送網(wǎng)絡(luò)的換電站選址與路徑優(yōu)化問題。邵塞等[7]以費(fèi)用最小化為目標(biāo)，考慮電動(dòng)汽車的里程、載重、時(shí)間窗等約束，用遺傳算法解決電動(dòng)汽車集散貨一體化車輛路徑問題模型。張艷偉等[8]以總成本最小為目標(biāo)，建立純電動(dòng)汽車運(yùn)營(yíng)的考慮貨物類別的路徑優(yōu)化問題。揭婉晨等[9]利用列生成的分支定價(jià)算法解決基于時(shí)間窗的電動(dòng)車車輛路徑問題。王永聰[10]在研究車輛路徑問題的基礎(chǔ)上，建立以城市配送為目標(biāo)的純電動(dòng)汽車車輛路徑模型，并應(yīng)用最鄰近算法和蟻群算法對(duì)其模型進(jìn)行求解研究。劉蘭芬等[11]在考慮時(shí)間網(wǎng)絡(luò)的基礎(chǔ)上，建立以客戶滿意度最高、配送時(shí)間最短等多目標(biāo)物流車輛調(diào)度模型，并用遺傳算法求解該模型。陶胤強(qiáng)等[12]以最小費(fèi)用為目標(biāo)，研究基于時(shí)間窗的多車型多費(fèi)用非滿載的車輛路徑問題。梁鳳婷等[13]研究低碳環(huán)境下電動(dòng)汽車的車輛路徑問題，以低碳、節(jié)能環(huán)保和低成本為目標(biāo)，建立燃油車和電動(dòng)車的車輛路徑模型，并用遺傳算法對(duì)模型進(jìn)行分析和求解。

從研究現(xiàn)狀可知，國(guó)內(nèi)外學(xué)者對(duì)純電動(dòng)汽車調(diào)度方案的研究成果相對(duì)較少,針對(duì)具有時(shí)間窗的車輛調(diào)度問題研究較多，主要采用智能算法求解車輛調(diào)度方案，如遺傳算法、蟻群算法、模擬退火算法等。鑒于此，本文著重考慮單向車輛調(diào)度模型，重點(diǎn)考慮時(shí)間窗約束、里程約束及充電需求，提出電動(dòng)汽車基于電量消耗的車輛調(diào)度模型，合理規(guī)劃包括配送方案、車輛行駛路徑、車輛發(fā)車時(shí)間及車輛充電計(jì)劃在內(nèi)的車輛調(diào)度方案。

1 問題描述

由于電動(dòng)汽車是靠電能驅(qū)動(dòng)，故充電是電動(dòng)汽車在行駛過程中必須面對(duì)的問題之一。當(dāng)電池電量不足以完成剩余的配送任務(wù)時(shí)，電動(dòng)車需要進(jìn)入到鄰近的充電站進(jìn)行充電，以供其完成剩余的配送任務(wù)。在本文中，充電站采用的是快速充電方式，使電動(dòng)車在30 min左右就可以完成充電。但是由于充電站可能不位于車輛既定的行駛線路上，車輛會(huì)發(fā)生行駛偏移，因而帶來配送中心總成本的增加。

由于電動(dòng)車配送過程需要考慮電動(dòng)車的續(xù)駛里程、電池電量、充電站位置、客戶服務(wù)的時(shí)間窗和車輛額定載重等諸多因素，為使問題更加簡(jiǎn)潔明了，預(yù)先進(jìn)行以下假設(shè)。

1) 只有一個(gè)配送中心，所有車輛從配送中心出發(fā)最后返回原配送中心；

2) 客戶的數(shù)量、客戶的位置、客戶服務(wù)的時(shí)間窗及每個(gè)客戶的需求量均已知，且車輛的總載重不得超過車輛的額定載重；

3) 配送車輛從配送中心出發(fā)，電池為滿電狀態(tài)，且在貨物裝卸過程中不存在電量的消耗；

4) 貨物流向?yàn)閱蜗?，只進(jìn)行配送貨物不進(jìn)行收集貨物；

5) 電動(dòng)車的額定續(xù)駛里程和充電時(shí)間均已知。

2 模型建立

2.1 符號(hào)及變量定義

C0為總費(fèi)用；

Cfk為車輛k的固定費(fèi)用；

Ctk為車輛k的行駛費(fèi)用；

Cmk為車輛k的充電費(fèi)用；

Cpk為車輛k的早到或晚到產(chǎn)生的懲罰費(fèi)用；

O為配送中心；

K為車輛集合；

M為充電站集合；

N為客戶點(diǎn)集合；

L為配送中心、充電站、客戶點(diǎn)的集合，L=O∪M∪N；

speed為車輛額定行駛速度；

P為電動(dòng)車額定電量；

為車輛k到達(dá)集合點(diǎn)i時(shí)電量，i∈L；

為車輛k離開集合點(diǎn)i時(shí)電量，i∈L；

ei為客戶點(diǎn)i的最早服務(wù)時(shí)間；

li為客戶點(diǎn)i的最晚服務(wù)時(shí)間；

epu為表示車輛早于時(shí)間窗到達(dá)造成的等待懲罰成本；

lpu為表示車輛晚于時(shí)間窗到達(dá)的懲罰成本；

為車輛到達(dá)集合點(diǎn)i的時(shí)刻，i∈L；

為車輛離開集合點(diǎn)i的時(shí)刻，i∈L；

為車輛在集合點(diǎn)i卸貨、充電時(shí)間，i∈L；

為車輛在客戶點(diǎn)處等待服務(wù)時(shí)間，i∈N；

Djk為車輛k到達(dá)點(diǎn)j時(shí)的剩余電量里程；

di j為客戶點(diǎn)i和j之間的距離；

Wmax為車輛額定載重量；

Dmax為車輛最大行駛距離；

Ed為電動(dòng)車電量單位里程消耗；

Wi為車輛載重量；

2.2 配送過程分析

1) 總成本分析?？偱渌统杀景?部分。

(1) 車輛固定成本。固定成本主要包括車輛折舊費(fèi)，司機(jī)勞務(wù)費(fèi)，餐飲費(fèi)等。

(2) 車輛行駛費(fèi)用。行駛費(fèi)用與行駛距離相關(guān)，車輛單位行駛成本為

(3) 充電費(fèi)用。充電費(fèi)用的多少與電池剩余電量相關(guān)，剩余電量越高，則充電費(fèi)用越少，充電時(shí)的單位充電成本為c2，Cmk=EdS c2，S為勻速行駛里程。

(4) 懲罰成本。懲罰成本主要由車輛早于或晚于客戶服務(wù)時(shí)間窗而引起，車輛早于服務(wù)時(shí)間窗到達(dá)需等待，等待時(shí)間為ei?，車輛晚于服務(wù)時(shí)間窗到達(dá)，客戶需要等待的時(shí)間為?li，則總懲罰成本為

2) 電量分析。

假設(shè)該電動(dòng)車行駛過程為勻速狀態(tài)，那么，根據(jù)文獻(xiàn)[14]提出的能耗經(jīng)濟(jì)性評(píng)價(jià)指標(biāo)，本文提出純電動(dòng)汽車在勻速行駛狀態(tài)下電池電量的單位里程能耗為

其中，G為 車輛重量；t為純電動(dòng)車勻速行駛時(shí)間；b為道路坡度；u為車速； ηt為傳動(dòng)系統(tǒng)效率；f為滾動(dòng)阻力系數(shù)；R為空氣阻力系數(shù)；A為汽車迎風(fēng)面積。電動(dòng)車從點(diǎn)i到達(dá)點(diǎn)j(i,j∈L)的剩余電量為Pik=P?Eddij。

3) 車輛在各點(diǎn)停留時(shí)間分析。

，i∈L。若i表示客戶點(diǎn)，則其表示車輛在該點(diǎn)的卸貨時(shí)間；若i表示充電站，則其表示車輛在充電站的充電時(shí)間；若i表示配送中心，則停留時(shí)間為0。

4) 車輛等待時(shí)間分析。

，i∈N。若車輛提早到達(dá)客戶點(diǎn)N，則要等待，等待時(shí)間為若在規(guī)定時(shí)間內(nèi)到達(dá)，則不需要等待，等待時(shí)間為0。

5) 車輛到達(dá)客戶點(diǎn)時(shí)刻分析。

電動(dòng)車輛從客戶點(diǎn)i離開，到達(dá)客戶點(diǎn)j的時(shí)刻為電動(dòng)車離開客戶點(diǎn)i的時(shí)刻加上車輛在客戶點(diǎn)i和j之間的行駛時(shí)間，即

2.3 數(shù)學(xué)模型

根據(jù)上述分析，構(gòu)建考慮電量消耗的電動(dòng)汽車調(diào)度優(yōu)化模型如下。

式(4)為模型的目標(biāo)函數(shù)，保證總成本最?。皇?5)~式(15)均為模型的約束條件。其中，式(5)保證每一位顧客都只被服務(wù)1次；式(6)保證車輛開始完成配送任務(wù)從配送中心出發(fā)和結(jié)束；式(7)保證在客戶點(diǎn)卸貨過程中不消耗電量；式(8)表示電量足夠到達(dá)集合L中 的任意點(diǎn)；式(9)表示車輛在點(diǎn)i和點(diǎn)j之間的行駛時(shí)間；式(10)表示車輛離開集合點(diǎn)i的時(shí)間；式(11)表示車輛到達(dá)集合點(diǎn)j的時(shí)間；式(12)表示車輛實(shí)際載重量不超過額定載重量；式(13)表示車輛若提早到達(dá)集合點(diǎn)i的等待時(shí)間；式(14)表示決策變量是0?1變量；式(15)表示懲罰成本函數(shù)。

3 算法設(shè)計(jì)

車輛路徑問題屬于NP-hard問題，該問題約束條件繁多，規(guī)模較大。遺傳算法具有強(qiáng)大的搜索能力和自適應(yīng)性，因此遺傳算法對(duì)于求解較為復(fù)雜的大型網(wǎng)絡(luò)車輛調(diào)度問題具有較好的效果。本文選用遺傳算法求解電動(dòng)汽車調(diào)度方案模型。

3.1 染色體結(jié)構(gòu)設(shè)計(jì)

本文采用自然數(shù)編碼的方式[5]，將染色體長(zhǎng)度定義為足夠大(2n+1)，其中，n為顧客的個(gè)數(shù)；m表示充電站的個(gè)數(shù)；k表示配送中心的車輛數(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輛車從配送中心出發(fā)，先后經(jīng)過客戶點(diǎn)3、4，然后進(jìn)入充電站6進(jìn)行充電，充電完成后返回配送中心，第2輛車經(jīng)過客戶點(diǎn)1、2、5返回配送中心。

圖 1 路徑染色體路徑Figure 1 Path of chromosome

3.2 種群初始化

首先將所有客戶與充電站的編號(hào)進(jìn)行隨機(jī)排列，設(shè)wi表示各點(diǎn)的需求量，然后考慮每輛汽車的載重約束，若則在染色體第γ 位后插入編號(hào)0，重復(fù)計(jì)算直至考慮完所有客戶的需求量約束，再考慮充電需求，若里程不足需求充電時(shí)，在該客戶點(diǎn)后插入最近的充電站編號(hào)，直至判斷完所有客戶的里程約束。最后在起點(diǎn)和終點(diǎn)分別插入配送中心代碼0，即構(gòu)成1條染色體。重復(fù)多次計(jì)算，即構(gòu)成初始種群popsize。

3.3 適應(yīng)度評(píng)價(jià)

對(duì)種群中的每條染色體進(jìn)行解碼，解碼后可得到每條染色體下的路徑，但是車輛的發(fā)車時(shí)間沒有確定，再用遍歷法選出各輛車最適宜的發(fā)車時(shí)刻。具體思路如下。在配送中心的運(yùn)營(yíng)時(shí)間6:00~21:00內(nèi)，按每間隔10 min發(fā)車，計(jì)算總配送成本。最小配送成本的發(fā)車時(shí)刻即為最優(yōu)的發(fā)車時(shí)刻。若存在多個(gè)最優(yōu)發(fā)車時(shí)刻，選取本時(shí)間段內(nèi)時(shí)間最小的時(shí)刻為發(fā)車時(shí)刻。根據(jù)上述求得每條路徑的總配送成本，可將目標(biāo)值的倒數(shù)定義為對(duì)應(yīng)染色體的適應(yīng)值：Zi=1/C0。適應(yīng)度值作為個(gè)體性能的評(píng)價(jià)指標(biāo)，其值越大，配送總成本越低，越接近最優(yōu)解。

3.4 種群更新

1) 選擇。

本文采用最佳個(gè)體保存和適應(yīng)度比例相結(jié)合的方式來對(duì)染色體進(jìn)行選擇[15]，將每代個(gè)體中的H個(gè)染色體按其適應(yīng)度值從大到小依次排列，排在第1位的即是適應(yīng)度值最大的，將其直接復(fù)制到下一代當(dāng)中，對(duì)于下一代中其余的H-1個(gè)染色體則采用輪盤賭的方式來產(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。可從圖2(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，具體過程如圖2所示。

3) 變異。

本文采用基因片段反轉(zhuǎn)變異的變異策略[16]，此策略在排序問題方面性能較優(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í)即可得到該車輛調(diào)度問題的近似最優(yōu)解，又可同時(shí)得到配送中心車輛的配送路線和配送中心總成本。

4 案例及結(jié)果分析

設(shè)某配送案例中，有1個(gè)配送中心，4個(gè)充電站，充電時(shí)間為0.3 h，5輛相同型號(hào)的配送車輛共服務(wù)50個(gè)客戶。且配送中心、充電站、客戶的坐標(biāo)、客戶點(diǎn)需求和服務(wù)時(shí)間窗均已知。車輛從配送中心出發(fā)，考慮到有充電需求，所以應(yīng)合理安排路徑，完成配送任務(wù)。車輛詳細(xì)參數(shù)如表1所示，配送過程中各項(xiàng)成本如表2所示，實(shí)例中各客戶的信息如表3所示。

表 1 某電動(dòng)貨車能耗計(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)過計(jì)算，車輛的最佳配送路徑和遺傳算法迭代圖如圖4、圖5所示，成本及路線結(jié)果如表4所示。此時(shí)，線路上最優(yōu)成本為2 266.158元，5輛車共6次進(jìn)入充電站進(jìn)行充電，其中充電成本共計(jì)80元，車輛固定成本為500元，車輛行駛成本為1 686.158元，得到最優(yōu)配送路徑后，再用枚舉法考慮顧客的服務(wù)時(shí)間窗，計(jì)算在配送中心運(yùn)營(yíng)時(shí)間內(nèi)各車輛的最佳發(fā)車時(shí)間。求得第1輛配送車輛的發(fā)車時(shí)間為6:00，懲罰成本為208.38元；第2輛配送車輛的發(fā)車時(shí)間為6:00，懲罰成本為364.21元；第3輛配送車輛的發(fā)車時(shí)間為6:00，懲罰成本為170.18元；第4輛配送車輛的發(fā)車時(shí)間為6:00，懲罰成本為148.41元；第5輛配送車輛的發(fā)車時(shí)間為9:30，懲罰成本為4.65元。此時(shí)配送中心考慮懲罰成本后的總配送成本為3 161.99元。每輛車的最佳發(fā)車時(shí)間及到達(dá)顧客和充電站的時(shí)間如表5所示。

表 2 配送過程各項(xiàng)成本Table 2 Cost of the distribution process元

5 結(jié)論

本文基于電動(dòng)車電量特性，充分考慮電動(dòng)車電量消耗、里程約束、載重約束、顧客服務(wù)約束等，建立以配送總成本最小為目標(biāo)的基于電量消耗帶時(shí)間窗的電動(dòng)汽車路徑規(guī)劃問題模型，對(duì)模型中配送中心總成本、電動(dòng)車電量的單位里程能耗、電動(dòng)車停留時(shí)間、電動(dòng)車行駛時(shí)間等進(jìn)行分析；采用遺傳算法首先求解出該模型中配送車輛的最佳配送方案，該配送方案包括車輛的行駛路線和行駛過程中的充電計(jì)劃，再結(jié)合枚舉法在配送中心運(yùn)營(yíng)時(shí)間內(nèi)以10 min為時(shí)間間隔，優(yōu)選出配送車輛懲罰成本最小時(shí)的最優(yōu)發(fā)車時(shí)刻，從而得到車輛到達(dá)每一客戶點(diǎn)及充電站的時(shí)刻。最后結(jié)合算例，計(jì)算出最佳配送路線、充電方案、最優(yōu)發(fā)車時(shí)刻以及最小總配送成本，驗(yàn)證了該模型和算法的有效性和正確性。但本文只研究了基于時(shí)間窗的電動(dòng)汽車調(diào)度問題，而現(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 車輛配送路徑Figure 4 Vehicle delivery path

圖 5 遺傳算法迭代過程示意圖Figure 5 The iteration process diagram of genetic algorithm

表 4 計(jì)算結(jié)果Table 4 Results of calculation

表 5 客戶配送時(shí)刻表Table 5 Customer delivery schedule