新能源移動充電車路徑優化問題研究

陳 萍， 董文哲， 于信堯

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

0 引言

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

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

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

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

1 模型建立

1.1 問題描述

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

本文研究靜態的移動充電車路徑問題(Mobile Recharging Vehicle Routing Problem, MRVRP)，即，假設在一次規劃過程中不會有新的顧客需求產生。此外，移動充電車本身也是新能源汽車，但其自身運行所消耗的電能由車輛自身電池所提供，供給客戶需求的電能由車載電池提供，來源不同，即移動充電車行駛所消耗電量不影響所能提供的最大充電量。MRVRP問題的目標是如何安排車輛對顧客需求進行服務，使得在滿足各項約束的條件下總收益最大。需要指出的是，由于充電車數量固定，客戶時間窗以及充電車自身續航里程等約束，同一時刻產生的客戶需求不一定能夠全部滿足。基于以上考慮，本文將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的最佳服務時間窗；[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：表示移動充電車的續航時間；Qmax：表示移動充電車的最大服務量；xijk：表示第k輛車是否經過弧(i,j)：若經過則取1，否則為0；yik：表示第k輛車是否訪問客戶點i：若訪問則取1，否則為0。

1.3 模型構建

本文將MRVRP問題建模如下：

(1)

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

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

(11)

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

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

c2max((tai-li),0)

(12)

2 最大最小蟻群優化算法

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

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

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

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

2.1 可行解構造

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

(13)

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

2.2 啟發式信息

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

η(i,j)=sj/cij

(14)

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

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

(15)

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

(16)

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

2.3 信息素的更新

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

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

(17)

(18)

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

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

(19)

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

(20)

(21)

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

(22)

3 仿真實驗與分析

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

3.1 算例描述

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

3.2 算例結果與分析

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

表1 算例結果

圖3 節點選擇與路線圖

圖4 迭代收斂過程

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

表2 硬時間窗TOPTW基準測試算例結果

表3 軟時間窗TOPTW基準測試算例結果

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

4 結語

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