帶時(shí)間窗和充電問(wèn)題的電動(dòng)車路徑優(yōu)化及實(shí)現(xiàn)

孫屹飛，蔣洪偉，張軼蘭

(北京信息科技大學(xué) 信息管理學(xué)院，北京 100192)

0 引言

從現(xiàn)代物流管理系統(tǒng)的總體構(gòu)成來(lái)看，路徑規(guī)劃問(wèn)題是物流管理當(dāng)中的核心問(wèn)題之一。尤其在互聯(lián)網(wǎng)電商交易和物流產(chǎn)業(yè)快速發(fā)展的今天，如何實(shí)時(shí)、動(dòng)態(tài)、高效地調(diào)度車輛并合理規(guī)劃行車路徑一直是學(xué)界和業(yè)界共同關(guān)注的焦點(diǎn)。作為運(yùn)籌學(xué)中一類典型的組合優(yōu)化問(wèn)題，經(jīng)過(guò)國(guó)內(nèi)外專家和學(xué)者半個(gè)多世紀(jì)的研究，路徑規(guī)劃問(wèn)題已由早期的靜態(tài)問(wèn)題發(fā)展成為動(dòng)態(tài)的、帶復(fù)雜約束條件、多目標(biāo)、多車場(chǎng)等類型的路徑規(guī)劃問(wèn)題。

物流公司的路徑規(guī)劃問(wèn)題一般表現(xiàn)為車輛路徑問(wèn)題[1](vehicle routing problem,VRP)，它的目標(biāo)為最小化物流公司的運(yùn)輸成本，條件為每個(gè)客戶點(diǎn)都只被訪問(wèn)一次，路線的開(kāi)始和結(jié)束在同一倉(cāng)庫(kù)。最初的VRP是由Dantzig等[2]提出的。在此之后，VRP的許多變種和擴(kuò)展被應(yīng)用于各種場(chǎng)景。研究最廣泛的2個(gè)擴(kuò)展為：約束車輛的運(yùn)力；帶時(shí)間窗的VRP，一種客戶必須在指定時(shí)間間隔內(nèi)到達(dá)[3]的約束模型。之后，Erdogan等[4]提出了綠色VRP(green-vehicle routing problem，G-VRP)，一種電動(dòng)汽車的車輛路徑模型，其考慮到車輛的電池容量有限，以及必須在充電站充電，對(duì)于每次充電以及訪問(wèn)客戶，都要考慮固定的服務(wù)時(shí)間。本文在基本的G-VRP基礎(chǔ)上，還考慮了有限的車輛運(yùn)輸能力和客戶時(shí)間窗，這是現(xiàn)實(shí)世界物流應(yīng)用中最重要的限制因素。由于模型參數(shù)過(guò)多無(wú)法精確求解，我們?cè)O(shè)計(jì)了鄰變域禁忌搜索算法(variable neighborhood search/tabu search, VNS/TS)用于模型求解。

1 電動(dòng)汽車運(yùn)輸路徑優(yōu)化模型構(gòu)建

1.1 參數(shù)定義

為了更加清晰準(zhǔn)確地描述模型，本文對(duì)模型中使用到的符號(hào)進(jìn)行如下定義：

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

K:車輛集合；

M:充電站集合；

O:配送中心，o為起點(diǎn)，o′為終點(diǎn)；

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

C:運(yùn)輸成本；

dij:點(diǎn)i到點(diǎn)j的路徑長(zhǎng)度，i,j∈V；

Q:車輛的載重量；

c:用電價(jià)格；

P:車輛的電池容量；

qi:點(diǎn)i∈N的需求

ei:客戶點(diǎn)i要求的最早服務(wù)時(shí)間，i∈N；

li:客戶點(diǎn)i要求的最晚服務(wù)時(shí)間，i∈N；

tij:車輛從點(diǎn)i到點(diǎn)j所需要的時(shí)間，i,j∈V；

v:車輛在配送過(guò)程中的行駛速度；

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

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

(1)

約束條件：

同一車輛只經(jīng)過(guò)客戶點(diǎn)一次的約束為

(2)

保證進(jìn)出客戶點(diǎn)的車輛數(shù)目相等的約束為

(3)

保證車輛到達(dá)客戶點(diǎn)的時(shí)間小于離開(kāi)的時(shí)間約束為

(4)

保證車輛起點(diǎn)、終點(diǎn)都是配送中心的約束為

(5)

(6)

車輛的載重約束為

(7)

車輛離開(kāi)客戶點(diǎn)i的時(shí)間等于到達(dá)客戶點(diǎn)i的時(shí)間、服務(wù)時(shí)間、等待時(shí)間三者之和：

(8)

電動(dòng)汽車到達(dá)點(diǎn)j的時(shí)間等于電動(dòng)汽車離開(kāi)其前一點(diǎn)i的時(shí)間加上其從點(diǎn)i行駛到點(diǎn)j所需要的時(shí)間[5]，即：

(9)

(10)

在客戶點(diǎn)停留過(guò)程中不消耗電動(dòng)汽車自身電能的約束為

(11)

2 求解E-VRP的VNS/TS算法

2.1 預(yù)處理階段

刪除不滿足時(shí)間窗和車載容量約束的邊，即將滿足式(12)、(13)、(14) 的邊(i,j)移除：

i,j∈V∧qi+qj≥Q

(12)

(13)

(14)

2.2 生成初始解

首先，按角度劃分，將客戶點(diǎn)和配送中心連線，排列連線和水平線的夾角大小[5]，從最小的角度開(kāi)始，沿著角度增大的方向，畫(huà)出一個(gè)扇形，扇形覆蓋的客戶點(diǎn)定義為一個(gè)“群”，直到“群”中客戶點(diǎn)的需求超過(guò)車輛車容量限制，則停止。當(dāng)一個(gè)“群”的客戶點(diǎn)總需求超過(guò)車載容量限制后，取出臨界客戶點(diǎn)，再通過(guò)相同的方法，以該臨界點(diǎn)為起點(diǎn)，另起一個(gè)“群”。也就是說(shuō)，這個(gè)本文定義的“群”本質(zhì)上是每輛車的路徑。重復(fù)運(yùn)用上述方法，直到所有的客戶點(diǎn)都被分到了對(duì)應(yīng)的“群”中；然后，對(duì)“群”進(jìn)行操作，將客戶點(diǎn)的最晚可行時(shí)間從小到大排序，使每個(gè)“群”的點(diǎn)形成一條路徑，配送中心為路徑的兩端，然后以“群”中最晚可行時(shí)間最小的客戶點(diǎn)作為該“群”路徑的第一個(gè)客戶點(diǎn)，即路徑的第二個(gè)點(diǎn)。接下來(lái)根據(jù)式的目標(biāo)函數(shù)值，從小到大依次插入路徑中[10]，即

f(S)=C+Ltw(S)+Lcap

(15)

式中：Ltw(S)為時(shí)間窗懲罰函數(shù)；Lcap為載重量懲罰函數(shù)，為常數(shù)。

2.3 VNS算法及其結(jié)構(gòu)

為了使搜索過(guò)程跳出局部最優(yōu)[6]，靠近全局最優(yōu)，VNS算法隨機(jī)地改變解鄰域結(jié)構(gòu)。本文采用4種不同的算子進(jìn)行求解。分別是or-opt鄰域、swap鄰域、 2-opt*鄰域[7]和cross鄰域。

swap鄰域操作將當(dāng)前解S中同一條路徑上的2個(gè)客戶或分別來(lái)自不同路徑上的2個(gè)客戶互換得到的新解定義為鄰域解。or-opt[11]鄰域操作將當(dāng)前解S中一條路徑上順序相連的一些客戶移到同一條路徑上的其他位置或不同路徑上后得到的新解定義為鄰域解。2-opt*鄰域結(jié)構(gòu)是求解旅行商問(wèn)題的2-opt鄰域結(jié)構(gòu)在路徑間交換的一個(gè)擴(kuò)展。2-opt*鄰域[9]操作首先在當(dāng)前解S中2個(gè)不同路徑中分別移走2條邊，然后針對(duì)這2條邊對(duì)應(yīng)的4個(gè)客戶進(jìn)行操作，將第1條路徑上的第1個(gè)客戶與第2條路徑上的第2個(gè)客戶 相連，第1條路徑上的第2個(gè)客戶與第1條路徑上的第1個(gè)客戶相連，得到的新解作為鄰域解。

2.4 TS算法

通過(guò)VNS算法，得到鄰域解S′后，將進(jìn)一步通過(guò)TS算法進(jìn)行優(yōu)化。TS算法使用的目標(biāo)函數(shù)為式(15)，算法的流程如下：

第一步定義算法初始參數(shù)，包括最大迭代次數(shù)及禁忌表長(zhǎng)度等。輸入鄰域解S′，將初始解賦值到當(dāng)前解S″和TS算法的第一階段的全局最優(yōu)解S，禁忌表置空，并構(gòu)造鄰域結(jié)構(gòu)集N。

第二步依據(jù)TS算法的條件，判斷算法是否滿足TS算法終止規(guī)則，若滿足，則S″←S″*，否則轉(zhuǎn)第三步。

第三步選擇鄰域Nk∈N，基于當(dāng)前解S″產(chǎn)生鄰域解集Nk(S″)，從中隨機(jī)選擇一些解構(gòu)成候選解集，從候選解中選擇最優(yōu)的解，判斷其是否被禁忌，如果被禁忌且不滿足特赦規(guī)則，則選擇候選解集中的次優(yōu)解，再次進(jìn)行判斷；否則轉(zhuǎn)入第四步。

2.5 VNS/TS算法流程

VNS/TS算法是VNS與TS的混合啟發(fā)式算法，在國(guó)內(nèi)外的多個(gè)組合優(yōu)化問(wèn)題上得到了較好的結(jié)果。Schneider等[7]首先使用VNS/TS求解電動(dòng)汽車的帶時(shí)間窗的車輛路徑問(wèn)題。

VNS/TS算法分為3個(gè)階段。首先是初始化階段，該階段的目的是降低網(wǎng)絡(luò)復(fù)雜度，使之后的計(jì)算變得簡(jiǎn)便；然后，通過(guò)一個(gè)兩階段的算法求解問(wèn)題得到初始解：使用VNS算法處理初始解，根據(jù)定義的鄰域結(jié)構(gòu)，求得初始解的鄰域解，VNS算法確立鄰域解之后TS算法將根據(jù)這個(gè)解進(jìn)行進(jìn)一步的優(yōu)化；最后，通過(guò)基于模擬退火[8]的評(píng)估機(jī)制來(lái)評(píng)估算法有效性。如果新解得到了有效性評(píng)估，則代替上一步的解成為當(dāng)前解。VNS/TS算法的具體實(shí)施步驟如下：

Step1通過(guò)初始化階段，處理網(wǎng)絡(luò)中的非可行解并且簡(jiǎn)化問(wèn)題網(wǎng)絡(luò)。

Step2通過(guò)VNS和TS兩階段算法得到路徑問(wèn)題的初始解：

Step2.1在忽略電池里程的前提下，求解車輛路徑的初始解S0。

Step2.2基于上一步，找出不滿足電池里程約束的路徑。

Step2.3在不滿足電池里程約束的路徑上迭代插入充電站，使該路徑滿足電池里程約束。

Step2.4重復(fù)Step2.3直至所有路徑都滿足電池里程約束，更新初始解S0。

Step3將所得初始解S0記為當(dāng)前解S，迭代次數(shù)t設(shè)為0。

Step4更新t：t←t+1。

Step5判斷迭代次數(shù)是否達(dá)到VNS/TS 算法預(yù)設(shè)最大迭代次數(shù)，若是，則停止算法，并輸出當(dāng)前解S，否則繼續(xù)。

Step6使用VNS算法優(yōu)化當(dāng)前解S。

Step6.1定義鄰域結(jié)構(gòu)Nk。

Step6.2定義k←1。

Step6.3根據(jù)所選鄰域結(jié)構(gòu)和選擇方法，求得當(dāng)前解的鄰域解S′←Nk(S)。

Step7使用TS算法優(yōu)化VNS階段的解S′，得優(yōu)化解S″。

Step8比較S″和當(dāng)前解S，如果S″通過(guò)了基于模擬退火的評(píng)價(jià)機(jī)制，則S←S″，轉(zhuǎn)回Step4; 否則K←(KmodKmax)+1轉(zhuǎn)至Step6.3。VNS/TS算法流程如圖1所示。

圖1 VNS/TS算法流程

2.6 新解的評(píng)價(jià)

為擴(kuò)大搜索空間，不陷入局部最優(yōu)，VNS/TS算法在追求不斷優(yōu)化新解的同時(shí)，也一定程度上接受惡化解。VNS/TS的新解評(píng)價(jià)機(jī)制基于模擬退火的思想[12]，模擬退火算法能夠以一定的概率通過(guò)當(dāng)前的惡化解。用S″表示從TS算法得到的新解，S為當(dāng)前解，則新解S″被通過(guò)的概率根據(jù)式(16)計(jì)算：

p(S″)=e-(f(S″)-f(S))/T

(16)

式中T的初始值為T0，并在每次迭代后根據(jù)更新函數(shù)Tn=v·Tn-1更新，更新函數(shù)中的v∈(0,1)為一個(gè)提前定義的常數(shù)。

3 實(shí)驗(yàn)結(jié)果分析

本文運(yùn)算的測(cè)試環(huán)境為英特爾I5處理器，內(nèi)存4 GB的臺(tái)式電腦。VNS/TS算法是通過(guò)單線程JAVA實(shí)現(xiàn)。算例為隨機(jī)構(gòu)造而來(lái)，名稱的含義為客戶點(diǎn)-充電站，以K50-6為例，為50個(gè)客戶點(diǎn)，6個(gè)充電站點(diǎn)構(gòu)成的網(wǎng)絡(luò)。使用CPLEX和VNS/TS算法對(duì)所構(gòu)造的6個(gè)算例進(jìn)行求解。其中，VNS/TS算法對(duì)每個(gè)算例執(zhí)行20次，取最優(yōu)結(jié)果。根據(jù)常見(jiàn)做法，對(duì)CPLEX的運(yùn)算時(shí)間設(shè)置2 h的上限。所得實(shí)驗(yàn)數(shù)據(jù)如表1所示。從表中可以看出，VNS/TS算法的精確性良好，其計(jì)算結(jié)果與CPLEX算法所得的最優(yōu)解在小規(guī)模問(wèn)題上沒(méi)有誤差。同時(shí)，VNS/TS算法在運(yùn)算速度上大大優(yōu)于CPLEX，當(dāng)CPLEX無(wú)法在2 h的運(yùn)算時(shí)間上限內(nèi)完成K75-10和K100-10的計(jì)算時(shí)，VNS/TS可以在2 s以內(nèi)求得可行解。

表1 測(cè)試算例運(yùn)算結(jié)果

4 結(jié)束語(yǔ)

本文提出了一種求解E-VRP的有效算法。不僅在小規(guī)模數(shù)據(jù)集上可以得到與CPLEX相同的結(jié)果，還可在CPLEX無(wú)法計(jì)算的大規(guī)模數(shù)據(jù)集上得到有效解。算法首先應(yīng)用兩階段方法產(chǎn)生初始解，再根據(jù)變鄰域搜索算法機(jī)制應(yīng)用4種不同搜索范圍的局域搜索算子對(duì)初始解進(jìn)行改進(jìn)，之后通過(guò)禁忌算法對(duì)解進(jìn)行再次優(yōu)化。實(shí)驗(yàn)結(jié)果表明，VNS/TS算法在不同規(guī)模數(shù)據(jù)集上都有良好表現(xiàn)。