陳 萍， 董文哲， 于信堯

(1.南開大學 商學院，天津 300071; 2.倫敦大學 巴特萊特學院，倫敦 WC1E 6BT)

0 引言

由于能源緊張和環(huán)境污染問題日益突出，以及未來城市發(fā)展要朝向“綠色化”的趨勢，近年來國家大力發(fā)展并推廣新能源汽車在城市的應(yīng)用。截至2017年底，我國新能源汽車累計保有量達153萬輛，占汽車總數(shù)的0.7%[1]。隨著新能源汽車行業(yè)的快速發(fā)展，充電服務(wù)的需求急劇增長，但目前充電基礎(chǔ)設(shè)施還不夠完備，尤其是充電樁的數(shù)量和布局難以滿足電動汽車充電的需求，成為阻礙新能源汽車發(fā)展的瓶頸之一。在這種背景下，提供上門充電服務(wù)的移動充電平臺應(yīng)運而生。移動充電能夠避免充電等待排隊、停車費等問題，節(jié)省時間，解決“里程焦慮”等問題，成為城市充電服務(wù)網(wǎng)絡(luò)的有力補充。

移動充電平臺企業(yè)擁有若干新能源移動充電車，接收到車主請求后，派出車輛在約定時間內(nèi)到指定地點為車主提供移動充電服務(wù)，并收取一定的費用。如何安排車輛對車主進行服務(wù)，使得獲得盡可能高的利潤成為企業(yè)關(guān)注的目標。移動充電車一般為電動車，其投入和運營成本相對固定，考慮到電費價格相對低廉，因此，在本研究中對其自身的電量消耗成本忽略不計。

根據(jù)問題特點，本文將移動充電車的調(diào)度和路徑優(yōu)化問題抽象為團隊定向問題(Team Orienteering Problem，TOP)[2～4]。定向問題(Orienteering Problem, OP)是一種特殊的路徑優(yōu)化問題，最早由Chao等[2]學者于1996年提出，該問題可簡單描述為給定一些節(jié)點，對應(yīng)不同的得分，要求運動員在給定時間內(nèi)收集盡可能多的得分并返回出發(fā)點。TOP是多條路徑的OP問題，近年來學者對該問題進行了廣泛了研究，并提出了求解問題的智能優(yōu)化算法，如禁忌搜索算法[3,5]，迭代局部搜索算法[4]和蟻群優(yōu)化算法[6]等。在經(jīng)典團隊定向問題中，車輛只需要考慮最大行駛里程的約束，而Archetti等學者[7]首先提出帶車輛容量限制約束的團隊定向問題。Luo等[8]構(gòu)建了一個基于兩種優(yōu)先規(guī)則的多樣化機制自適應(yīng)策略解決帶容量限制的TOP。Vidal等[9]研究了帶有隱性客戶選擇的以最大化利潤為目標的車輛路徑問題，并給出了一種鄰域搜索算法。此外，時間窗約束是路徑規(guī)劃問題中重要的考慮因素之一。Righini和Salani[10]首次在定向問題中引入了時間窗約束。Montemanni和Gambardella[11]提出了帶時間窗的TOP (TOPwith time windows, TOPTW)。Ke等[12]提出一種蟻群算法來解決TOPTW。Souffriau等[13]加入多重時間窗約束與車輛數(shù)目、運行時間等約束，提出了帶時間窗的多約束團隊定向問題，并提出了一種高效的鄰域搜索算法。Tricoire等[14]研究了多時間窗的多周期定向問題，并提出一種可變鄰域搜索算法。Mei等[15]研究了與時間相關(guān)的多目標定向問題(MOTDOP), 并提出了兩種用于解決MOTDOP的元啟發(fā)式方法：多目標模因算法(MOMA)和多目標蟻群系統(tǒng)(MACS)。Sun等[16]提出了與時間相關(guān)的具有時間窗口和優(yōu)先約束的考慮利潤的旅游商問題，并開發(fā)了一種定制的標記算法，以找到最佳的方案。

本文將移動充電車路徑問題抽象為帶軟時間窗和最大服務(wù)量約束的團隊定向問題，并提出一種最大最小蟻群優(yōu)化算法對模型進行求解，最后通過數(shù)值實驗驗證了本文模型和算法的有效性。

1 模型建立

1.1 問題描述

本文研究問題可描述為：某移動充電平臺企業(yè)擁有m輛同類車型的新能源移動充電車，可以為新能源汽車車主提供移動充電服務(wù)。假設(shè)在某一時刻有n個車主預約充電請求，平臺需派出車輛在預約時間內(nèi)到指定地點為車主提供服務(wù)，早到需支付一定的停車費用，超出預約時間將給予車主一定的價格折扣，要求每輛移動充電車從車庫出發(fā)，完成服務(wù)后返回車庫，且里程不得超過充電車的續(xù)航里程。

本文研究靜態(tài)的移動充電車路徑問題(Mobile Recharging Vehicle Routing Problem, MRVRP)，即，假設(shè)在一次規(guī)劃過程中不會有新的顧客需求產(chǎn)生。此外，移動充電車本身也是新能源汽車，但其自身運行所消耗的電能由車輛自身電池所提供，供給客戶需求的電能由車載電池提供，來源不同，即移動充電車行駛所消耗電量不影響所能提供的最大充電量。MRVRP問題的目標是如何安排車輛對顧客需求進行服務(wù)，使得在滿足各項約束的條件下總收益最大。需要指出的是，由于充電車數(shù)量固定，客戶時間窗以及充電車自身續(xù)航里程等約束，同一時刻產(chǎn)生的客戶需求不一定能夠全部滿足。基于以上考慮，本文將MRVRP問題抽象為帶軟時間窗和容量約束的團隊定向問題。圖1給出了本文研究問題的一個示例，該例子中有3輛充電車，11個客戶充電需求，但只能滿足其中8個需求使得總利潤最大。

圖1 移動充電車路徑問題示例

1.2 符號說明

V：表示頂點集合，包括車庫O及客戶的集合，V=(0,…,n)；Vc：表示客戶集合，Vc=V{0}；E：表示所有弧的集合，E={(i,j)│i,j∈V}；[ei,li]：表示客戶點i的最佳服務(wù)時間窗；[sei,sli]：表示客戶點i的可接受時間窗，其中sei≤ei≤li≤sli；M：表示移動充電車集合，包含m輛車，M={1,2,…,m}；v：表示移動充電車的平均行駛速度；p：表示單位充電時間的費用；si：表示客戶i的充電時間，即客戶需求；cij：表示i與j之間的距離；tij：表示i與j之間的行程時間，tij=cij/v；tai：表示車輛到達客戶i的時間；Cmax：表示移動充電車的續(xù)航時間；Qmax：表示移動充電車的最大服務(wù)量；xijk：表示第k輛車是否經(jīng)過弧(i,j)：若經(jīng)過則取1，否則為0；yik：表示第k輛車是否訪問客戶點i：若訪問則取1，否則為0。

1.3 模型構(gòu)建

本文將MRVRP問題建模如下：

(1)

其中，目標函數(shù)(1)表示是使得服務(wù)收益最大化，即服務(wù)收益與未能在最佳時間窗內(nèi)服務(wù)客戶產(chǎn)生的等待或懲罰成本之差；約束(2)表示每輛移動充電車必須從車庫出發(fā)并且最終返回車庫；約束(3)保證了路線的連通性；約束(4)保證了每個客戶點最多被訪問一次；約束(5)-(6)保證了移動充電車必須在可接受時間窗內(nèi)訪問客戶；約束(7)保證了移動充電車的續(xù)航里程約束；約束(8)表示移動充電車的最大服務(wù)電量約束；約束(9)和(10)表示0-1決策變量。

在MRVRP中，假設(shè)每個顧客點都有一個最佳服務(wù)時間窗[ei,li]和可接受時間窗[sei,sli]，即車輛在[sei,ei]內(nèi)到達也可接受，但會產(chǎn)生等待成本；在[li,sli]內(nèi)到達會產(chǎn)生懲罰成本。二者之和Pubi的具體計算如式(11)所示。

(11)

其中，c1為早到等待成本系數(shù)，c2為遲到懲罰系數(shù)，本文中均假設(shè)為已知常數(shù)。因此，式(1)中的懲罰成本部分可表示為：

Pubi=c1max((ei-tai),0)+

c2max((tai-li),0)

(12)

2 最大最小蟻群優(yōu)化算法

MRVRP可看作是帶軟時間窗和容量約束的TOP問題，由于OP問題是NP-難問題[17]，傳統(tǒng)的優(yōu)化方法難以對其進行求解。本文設(shè)計一種蟻群優(yōu)化算法(Ant Colony Optimization, ACO)對其求解。ACO是一種基于種群的智能優(yōu)化算法，最初的靈感來源于真實螞蟻搜尋食物的行為——以信息素作為媒介間接進行信息交換[18]。最大最小蟻群算法(Min-maxant system, MMAS)是在基本蟻群優(yōu)化算法的基礎(chǔ)上，通過限定信息素濃度的上下閾值，從而避免信息素過早集中產(chǎn)生算法停滯。目前，蟻群優(yōu)化算法已經(jīng)成功應(yīng)用于電動汽車旅行商問題[19]、選址-路徑問題[20]以及定向問題[21]等組合優(yōu)化問題。

本文設(shè)計一種最大最小蟻群優(yōu)化算法對MRVRP問題進行求解，算法步驟如圖2所示。

算法1最大最小蟻群算法1: 計算距離矩陣;初始化信息素濃度和啟發(fā)式信息;2:WHILE 算法停止條件不滿足DO3:k=1;4:FOR k?naDO5:構(gòu)造可行解s;6:計算解s的目標函數(shù)值f(s);7:ENDFOR8:更新迄今最優(yōu)解sb9:更新信息素;10:END WHILE11:輸出sb,算法結(jié)束。

圖2 最大最小蟻群算法流程

2.1 可行解構(gòu)造

車輛從O點開始，選擇一個節(jié)加入當前路徑，直到可行點集為空返回原點O，至此完成一條路徑；重復該過程直到所有客戶點都已在路徑中，或m輛車輛已全部用完，至此完成了一個可行解的構(gòu)造。選擇節(jié)點的依據(jù)如下：假設(shè)當前路徑上的最后一個點i，可行點集合為Ci，則選擇j作為路徑上下一個訪問顧客點的概率為：

(13)

其中，路徑τ(i,j)是弧(i,j)上的信息素濃度，η(i,j)是弧(i,j)的啟發(fā)式信息，α和β是參數(shù)，分別決定信息素濃度和啟發(fā)式信息的重要程度。本文中，設(shè)定η(i,j)與客戶j點收益的高低和弧(i,j)的長度直接相關(guān)(詳見3.2節(jié))，因此，當客戶j在可選點集合中時，車輛從客戶i處選擇客戶j作為下一個訪問點的概率既取決于客戶i與j之間的信息素濃度，又取決于客戶j收益的高低和弧(i,j)的長度。

2.2 啟發(fā)式信息

假設(shè)當前路徑上的最后一個點是i，所有可行未覆蓋點的集合中的節(jié)點j，對于不帶時間窗的路徑規(guī)劃問題來說，對于弧(i,j),我們通常將對啟發(fā)信息進行如下定義：

η(i,j)=sj/cij

(14)

即，在距離相等的情況下，收益越大的顧客點被選擇的概率越高；在收益相等的情況下，距離越遠的顧客點被選擇的概率越低。

由于本問題中帶有時間窗約束，啟發(fā)式信息的定義也要做出相應(yīng)調(diào)整。當點不滿足約束(5)或(6)時，則點j不屬于可行解，不失一般性，我們在此假定j點可行。設(shè)該路徑已經(jīng)耗時Lki，通過弧(i,j)的時間則為：

(15)

本文將考慮時間窗約束的啟發(fā)式信息定義如下：

(16)

即，在距離相等的情況下，收益越大的顧客點被選擇的概率越高；在收益相等的情況下，訪問后的累計總時間越長的顧客點被選擇的概率越低。其中γ為參數(shù)，決定了時間因素的重要性。

2.3 信息素的更新

MMAS中只使用最優(yōu)解sbest來更新信息素sbest可以是當前最優(yōu)解sgb或當代最優(yōu)解sib。對于弧(u,v)，信息素更新方式定義如下：

τ(u,v)l+1=ρτ(u,v)l+Δτ(u,v)

(17)

(18)

其中，ρ為信息素保持度，是大于0小于1的常數(shù)；τ(u,v)l為弧(u,v)在第l代的信息素濃度；Δτ(u,v)為當前代信息素濃度增加量；τmin和τmax分別為信息素濃度的上下閾值。

對于當前代信息素濃度增加量定義如式(19)所示：

(19)

本文將信息素濃度的上下閾值定義如下：

(20)

(21)

其中Pbest是參數(shù)，通常取值為0.05，F(xiàn)(x)為可選點集合中所有點對應(yīng)的收益之和總收益之比，即所有未被訪問點的收益之和。當F(x)為0時，說明所有點均被訪問或已無可用車輛，算法終止。即：

(22)

3 仿真實驗與分析

為驗證模型與算法的有效性，在調(diào)研北京市“e約充電”的基礎(chǔ)上，本文構(gòu)造了一個仿真算例進行測試。本文算法用matlab實現(xiàn)，運行環(huán)境為Interl Core i7 3540M CPU。相關(guān)算法參數(shù)設(shè)置如下：螞蟻數(shù)量na=100，信息素因子α=1，啟發(fā)函數(shù)因子β=1，信息素揮發(fā)因子ρ=0.15，最大迭代次數(shù)maxgen=100，信息素更新參數(shù)γ=15，貪婪概率Pbest=0.05。

3.1 算例描述

基于調(diào)研數(shù)據(jù)，本文構(gòu)造算例描述如下：充電服務(wù)覆蓋范圍抽象為270km*270km的區(qū)域，車庫和所有潛在客戶分布于該區(qū)域。車隊當前共有可用移動充電車15輛，待處理客戶需求點200個，移動充電車的平均時速為v=48km/h，最長續(xù)航里程為Tmax=400km，能提供的最大充電量為Qmax=500min，單位服務(wù)時間收入為p=1；早到和遲到懲罰系數(shù)分別為c1=0.3和c2=0.4。車庫O點位置坐標為(130,130)?？蛻酎c坐標、充電需求時長、最佳時間窗與可接受時間窗均假設(shè)為已知。

3.2 算例結(jié)果與分析

利用本文提出的最大最小蟻群系統(tǒng)算法，求解算例的結(jié)果如表1所示，服務(wù)節(jié)點選擇與路線圖如圖3所示。從結(jié)果中可以看出，200個客戶中，提供服務(wù)的客戶有61個，總收益為1798.78。經(jīng)分析發(fā)現(xiàn)，移動充電車隊未能服務(wù)的客戶大部分為時間窗比較緊的客戶。與客戶距離遠近相比，時間窗在移動充電車隊對顧客進行取舍時具有更大的影響力。

表1 算例結(jié)果

圖3 節(jié)點選擇與路線圖

圖4 迭代收斂過程

程序運行時間為324秒，迭代收斂過程如圖4所示，從圖上可以看出，本文設(shè)計的最大最小蟻群算法對于求解帶時間窗及最大服務(wù)量約束的團隊定向問題具有良好的求解效果，可以有效避免陷入局部最優(yōu)的現(xiàn)象，達到了運行時間和計算精度的平衡。為了進一步驗證算法的有效性，本文利用Montemanni and Gambardella[13]提出的TOPTW算例集進行測試。該算例集是在Solomon的帶時間窗車輛路徑問題(Vehicle Routing Problem with Time Windows, VRPTW)算例集的基礎(chǔ)上產(chǎn)生，包括27個算例，其中可使用的車輛數(shù)可以為2，3或4。為了符合本文問題軟時間窗的限定，對該算例集做以下修正：將原算例中的時間窗設(shè)為最佳時間窗[ei,li]，可接受時間窗[Ei,Li]設(shè)為[0.8*ei,1.2*li]。為了測試軟時間窗總收益的影響，本文分別對硬時間窗和軟時間窗條件下進行實驗，結(jié)果分別如表2和3所示，算例運算平均用時422秒。

表2 硬時間窗TOPTW基準測試算例結(jié)果

表3 軟時間窗TOPTW基準測試算例結(jié)果

從表2和表3可以看出，本文算法能夠有效求解帶軟硬時間窗的團隊定向問題。當車輛數(shù)少時(m=2)，客戶分布聚集情況(如算例C2XX等)下比客戶分散分布(如算例R2XX和RC2XX等)能夠服務(wù)更多的客戶，獲取更多的收益。當車輛數(shù)增多(m=4)，這一差別不再明顯。另外，軟時間窗條件下(表2所示)，無論是從服務(wù)的客戶數(shù)還是總收益，所有算例的結(jié)果都優(yōu)于硬時間窗條件下的結(jié)果(表3所示)。這表明，適當放寬時間窗的設(shè)置，即使予以一定的懲罰代價，仍夠?qū)偸找鎺磔^大的提高。

4 結(jié)語

本文對新能源移動充電這一新興業(yè)態(tài)的路徑優(yōu)化問題首次進行了定量研究。以總收益最大為目標，綜合考慮了客戶時間窗要求、移動充電車續(xù)航里程以及電池最大電量等約束，將問題抽象為帶軟時間窗和容量約束的團隊定向問題，并建立數(shù)學模型。針對該問題的NP-難特性，提出了一種最大最小蟻群算法對問題進行求解，設(shè)計了考慮時間窗的信息素，并通過最大最小信息素濃度的設(shè)置避免算法過早收斂。基于實際平臺企業(yè)調(diào)研，構(gòu)建算例進行仿真實驗。實驗結(jié)果驗證了本文模型和算法的有效性，并揭示出客戶時間窗過緊會對平臺總收益帶來較大的影響，因此，平臺企業(yè)可通過設(shè)立激勵機制鼓勵顧客放寬時間窗，以實現(xiàn)提高充電服務(wù)收益的目標。后續(xù)研究將繼續(xù)探討懲罰成本參數(shù)對軟硬時間窗總收益差別的影響。