考慮路段充電和時間窗的電動車取送貨問題

摘要：考慮路段充電和時間窗的電動車取送貨問題，以最小化車輛總旅行距離為目標，結合車輛容量約束、時間窗約束和電量約束等限制，決策一組最優的車輛線路。該問題公式化為一個混合整數線性規劃模型，提出一種變鄰域搜索算法求解該問題。數值算例用于驗證模型的性質和算法的性能。結果表明：在小規模算例中，提出的算法只比商業求解器CPLEX差0.08%；但在大規模算例中，算法能求出高質量的可行解而CPLEX在規定時間內無法得到可行解。

關鍵詞：物流工程；取送貨問題；變鄰域搜索算法；電動車輛；充電路段

中圖分類號：U121文獻標志碼：A文章編號：1002-4026（2023）03-0078-12

Abstract∶In this paper， the electric vehicles pickup and delivery problem considering link recharging and time windows was studied. Aims to minimize the total travel distance of vehicles， considering the constraints of vehicle capacity， time windows and battery capacity， etc.， to determine a group of optimal vehicle routes. The problem is formulated as a mixed integer linear programming model; a variable neighborhood search algorithm is proposed to solve it. Numerical instances are used to verify the model properties and algorithm performance. The results show that the proposed algorithm is only 0.08% worse than the commercial solver CPLEX in small scale instances; however， in large scale instances， the algorithm can obtain high quality feasible solutions in the specified time， in contrast to the CPLEX.

Key words∶logistics engineering; pickup and delivery problems; variable neighborhood search algorithm; electric vehicle; recharging link

帶時間窗的取送貨問題（pickup and delivery problem with time windows， PDPTW）是一種組合優化問題，是為一組車輛安排服務客戶需求的訪問順序。每個客戶需求包括一個取貨點和一個送貨點，統稱為需求點，每個需求點都有一個規定的時間窗，場站也有一個最早離開時刻和最晚到達時刻，每輛車都從場站出發，服務完客戶需求后回到場站，場站和需求點必須在時間窗內訪問。PDPTW在現實中有很多應用，如城市快遞配送，小貨車物流運輸等。

近年來，電動車以其低碳、噪聲小等特點受到市場青睞，已有許多學者研究電動車在物流配送中的路徑規劃問題。通常，求解車輛路徑問題的方法分為兩大類，一類是精確算法，另一類是啟發式算法。在前者中，Koc等[1]提出了一種分支剪枝算法求解綠色車輛路徑問題，他們采用了20個客戶的實例來驗證提出的算法，結果表明在40個實例中，可以求出20個實例的最優解。Desaulniers等[2]提出了4種帶時間窗的電動車輛路徑問題，設計了一種分支定價與剪枝算法來求解。他們考慮了線路的充電次數限制和不同的充電策略，提出的算法能求解多達100個客戶和21個充電站的實例。Andelmin等[3]提出了列生成算法求解綠色車輛路徑問題，該算法能求出110個客戶的實例最優解。這些精確算法的優勢在于能求出小規模實例的最優解。在后者中，商麗媛[4]對遺傳算法進行改進，采用分組編碼的思想，求解了PDPTW實例。Schneider等[5]和Keskin等[6]都研究了帶時間窗的電動車輛路徑問題，他們都假設電動車在充電站的充電量與充電時間成正比。不同的是，前者只考慮電動車在充電站充滿電的情況，并設計了一種變鄰域搜索算法和禁忌搜索算法相結合的混合啟發式求解該問題；后者允許電動車在充電站進行部分充電，提出了一種自適應大鄰域搜索算法求解該問題，該算法能自適應地選擇移除和插入操作以獲得更優的解。江玉萍[7]基于變鄰域搜索算法框架，將局部搜索算法和標簽算法相結合求解帶時間窗和充電站的電動物流車的取送貨問題。Goeke[8]考慮電動車在充電站可以選擇兩種充電策略（完全充電或部分充電），創新性地提出一種粒度禁忌搜索算法求解帶時間窗的電動車取送貨問題。

在電動車相關的車輛路徑問題中，由于電池容量的限制，電動車在服務客戶的過程中可能需要電量補給。Chen等[9]介紹了電動車的兩種充電方式，分為靜態充電和動態充電。靜態充電要求電動車在充電站接受充電服務，需要額外的充電時間；動態充電是利用電磁感應原理將電力無線傳輸到汽車的接收器，令電動車在行駛的過程中充電，大大節省了電動車的充電時間[10]。與靜態充電相比，動態充電技術的推廣和應用面臨著一些挑戰，但該技術在未來市場擁有巨大的發展潛力。因此，我們可以展望動態充電技術在未來可以與靜態充電模式互為補充，解決用戶的續航焦慮和充電難題。

上文中列舉的學者們多研究靜態充電的電動車車輛路徑問題。與靜態充電的電動車輛路徑問題相比，本文研究的考慮路段充電和時間窗的電動車取送貨問題更復雜。在靜態充電的電動車輛路徑問題中，考慮的約束有服務約束、容量約束、時間窗約束和電量約束，而本文在此基礎上還考慮了需求的優先約束和配對約束，這增加了問題求解的復雜性。本文以最小化車輛的總旅行距離為目標，建立了混合整數線性規劃模型，提出了一種變鄰域搜索算法求解模型，最后通過數值算例驗證模型性質和算法性能。

1問題描述與數學模型

1.1問題描述

目標函數式（1）是最小化車輛的總旅行距離；式（2）～（4）表示節點的流平衡；式（5）表示每個取貨點只被訪問一次；式（6）表示每個充電弧被同一輛車最多訪問一次；式（7）表示配對約束，即一個需求的取貨點和送貨點被同一輛車訪問；式（8）表示客戶的時間窗約束；式（9）表示節點的開始服務時刻之間的關系，其中M是一個非常大的正實數，當xkij=1時，表示節點j在節點i后立即被車輛服務，并有Tki+si+tij≤Tkj；否則，Tki+si+tij－M≤Tkj恒成立，式（8）和式（9）同時還可以消除子環；式（10）表示車輛服務的優先約束，即先服務取貨點i，再服務送貨點n+i；式（11）表示車輛在非充電弧（i，j）∈Ac上的電量消耗；式（12）表示車輛在充電弧（i，j）∈Ac上充電和耗電約束；式（13）表示滿足節點j∈N的需求；式（14）表示車輛在節點i∈N的容量約束；式（15）表示車輛在節點i∈V′的電量約束；式（16）表示二元決策變量。

2求解算法

2.1變鄰域搜索算法

本文提出一種變鄰域搜索（variable neighborhood search，VNS）算法求解該模型。在VNS算法中，我們設計了3種鄰域操作擾動當前解，并嘗試在局部搜索階段找到更好的解。

VNS算法主要包含構造初始可行解、用鄰域搜索產生擾動和局部搜索。鄰域搜索是用一些鄰域操作對當前解進行擾動，避免陷入局部最優解。局部搜索是在當前的鄰域內搜索更優的解。具體的算法流程如下：

Step 1：生成初始可行解Sinit，令當前解Scur=Sinit，全局最優解Sbest=Sinit。

Step 2：輸入鄰域Nk={1，2，…，kmax}，k=1，最大迭代次數I，迭代計算器c=0。

Step 3：當clt;I時，對當前解Scur在鄰域Nk內進行鄰域搜索，得到鄰域解S′;然后對S′應用局部搜索，得到局部搜索的解S″。

Step 4：若S″優于當前解Scur或者S″被接受，則置當前解Scur=S″，k=1；否則k=（k mod kmax）+1，c=c+1。

Step 5：若當前解Scur優于Sbest，則更新全局最優解Sbest=Scur，重復Step 3～5。

Step 6：直到達到最大迭代次數I，輸出全局最優解Sbest。

2.1.1初始可行解的生成

初始可行解用依次構造可行車輛線路的方法生成。每個需求按取貨點與場站的距離進行非遞減排序，把距離最近的需求添加到線路中，在滿足時間窗約束和容量約束的條件下，按最小的插入成本依次插入需求，當違反電量約束時，貪婪地插入充電路段，直到沒有需求能可行地插入線路中，線路生成結束。重復這一過程，直到所有的需求都被添加到線路中。

2.1.2鄰域搜索

在鄰域搜索階段，我們設計3種不同的鄰域操作交替對當前解進行擾動，增加算法搜索的廣度。為了方便描述，我們用Ne表示使用的第e個鄰域操作，用S′=（Ne，S）表示第e個鄰域操作對解S擾動后得到的解，具體的鄰域操作如下。

鄰域操作N1：該操作是對解S中所有線路服務的需求數量按照非遞減的順序排列，將第一條線路的需求插入到其他線路的可行位置，該操作可能會減少車輛數的使用。如圖2所示，將車輛k1∈K線路中的一個需求（16+，16-）插入到車輛k2∈K的線路中，先將送貨點16-貪婪地插入到線路中，再可行地插入取貨點16+。

鄰域操作N2：該操作隨機選擇兩個不同的車輛k1∈K和k2∈K，在車輛k1的線路中隨機選擇一個需求，隨機插入到車輛k2的線路中的可行位置[8]。為了增加插入的可行性，需要檢查該需求插入線路中的所有可行位置，若沒有可行位置，則重新選擇車輛k2∈K（k1≠k2），重復這一過程，直到找到可行位置或者所有的k2∈K（k1≠k2）都被遍歷仍沒有找到可行的車輛線路。若找到可行位置，則更新線路；否則，置S′=S。如圖3所示，在車輛k1∈K的線路中隨機選擇一個需求（如：5+，5-）插入到車輛k2的線路中，可行的位置有a、b和c，隨機選擇一個可行位置（如b），將該需求插入車輛k2的線路中。

N2 鄰域操作N3：該操作是對當前解S中所有線路的充電路段依次從當前線路中刪除，檢查線路中各節點的電量。若沒有電量為負的節點，則更新線路；否則，在第一個電量為負的節點和前一個節點之間貪婪地插入充電路段，若不能插入可行的充電路段，則以同樣的方式在之前的弧插入充電路段[5]。如圖4所示，將充電路段（S+1，S－1）從車輛k1的線路中刪除，插入充電路段（S+2，S－2）到車輛k1的線路中。

2.1.3局部搜索

本文設計了一種基于線路內部重新定位的操作。該操作是對解S′中的每個線路都進行局部搜索。將線路中的一個需求刪除，再重新貪婪地插入線路中，若線路的成本降低，則更新線路；否則，對線路中的其他需求執行這一過程[11]。如圖5所示，將需求（12+，12-）從車輛k1的線路中移除，再重新插入車輛k1的線路中。

2.1.4接受準則

本文采用模擬退火接受準則接受解。S″表示解S經過擾動和局部搜索后的解。若f（S″）lt;f（S），則接受S″，即置S=S″；否則，用概率公式（17）接受解S″。

2.2遺傳算法

遺傳算法（genetic algorithm，GA）是通過模擬自然進化過程搜索最優解的啟發式方法。在遺傳算法中，一組染色體組成一個種群，種群中的每個染色體表示問題的一個可行解。遺傳算法首先生成一個初始種群并評估每個染色體的適應度值。在每一次迭代中，當代種群中的每個染色體以一定的交叉概率和變異概率分別添加到交叉集合和變異集合中。該算法對交叉集合中的染色體兩兩配對，并對每對染色體選擇交叉算子進行交叉操作；對變異集合中的每個染色體選擇變異算子進行變異操作，根據新得到的染色體和當代種群，采用輪盤賭選擇策略生成下一代種群。當達到最大迭代次數時，算法終止。

2.2.1解的編碼與評估

我們將染色體用一組車輛訪問節點的次序來編碼，每個節點代表一個基因。適應度值被用來評估一個解，用公式（20）計算：

2.2.2初始解的生成

初始解的生成采用了2.1.1中的方法。初始種群中的每個染色體都由該方法生成。

2.2.3選擇操作

算法采用傳統的輪盤賭選擇方法挑選染色體，每個染色體被選中的概率用公式（21）計算：

2.2.4交叉操作

交叉算子的具體思想如下：（1）選擇兩個父代染色體，分別在兩個父代中選擇一個客戶需求作為交叉的基因。（2）將父代1與父代2中選擇的基因進行交叉。（3）為了消除需求重復的情況，將原父代1中與插入的基因相同的需求刪除。（4）將插入原父代2中的需求重新插入原父代1中，這可能會增加使用的車輛數以確保可行性，得到子代1。（5）交換父代角色，重復3～4步，可以得到子代2。

2.2.5變異操作

變異算子的思想如下：在每一個染色體中隨機選擇一個客戶需求，先將需求從染色體中刪除，再將該需求重新貪婪地插入染色體，適當安排新車輛以保證可行性。對于種群中的每一個染色體，采用2.1.2中的鄰域操作N3移除冗余的充電路段或者改變充電路段的訪問順序，這可能會得到一個更優的染色體。

3算例分析

為了驗證提出的VNS算法的性能，本文設計了小規模算例和大規模算例各3組。本文提出的算法用C#編寫，在Intel（R） Core（TM）i9-10900K3.7GHz CPU，內存為32.0 GB的計算機上運行。為了比較，我們使用商業求解器IBM ILOG CPLEX（12.5版）求解小規模算例，CPLEX的時間限制為7 200 s。由于CPLEX在規定的時間內無法求出大規模的算例，我們將提出的VNS算法與GA算法進行對比，驗證VNS算法的性能。

3.1算例的產生

在小規模算例中，取貨點和送貨點的總數分別為8、10和12，充電路段的個數為1，每個充電路段虛擬3個。在大規模算例中，取貨點和送貨點的總數分別為100、200和400，充電路段的個數為4，每個充電路段虛擬3個。每組算例根據客戶需求點和充電節點的位置分布分為3種類型，即隨機分布（R）、集群分布（C）和均勻分布（RC）。節點坐標在[0，100]區間內隨機生成，客戶需求量為[1，5]之間的隨機整數，車輛容量為40，電池容量為100，計劃周期為720 min（從早上7點到晚上7點）。

3.2算法參數設置

變鄰域算法的參數調整主要包括最大迭代次數I、充電系數γ、耗電系數h、冷卻率和初始溫度系數θ。我們以算例R100-0作為測試算例，運行10次，得到表2～3。通過分析實驗結果，將最大迭代次數設為10 000，耗電系數設為0.4，充電系數設為2.0，冷卻率設為0.75，初始溫度系數設為0.04。遺傳算法的參數設置如下：種群規模為100，交叉概率為0.8，變異概率為0.2，最大迭代次數為10 000。

3.3小規模算例結果與分析

在表4中，第1列是算例名稱，如R8-0表示隨機分布的取貨點和送貨點的總數為8，該算例在此規模下的序號為0。第2列表示CPLEX求出的車輛數。CPLEX和VNS算法的求解時間分別為tCPLEX、tVNS，一列VNS算法與CPLEX結果的相對差值為σ0，其計算公式如下：

結果如表4所示，在運行時間上，VNS算法與CPLEX相比，VNS算法可以在較短時間內求出43個與CPLEX相同的解，只有兩個算例，VNS算法的結果稍遜于CPLEX的結果。從平均值來看，VNS算法與CPLEX的平均σ0僅為0.08%，而平均運行時間大約是CPLEX求解時間的1/10，這說明提出的VNS算法在求解的效率上優勢顯著。表5給出了算例R12-0的求解路線，圖6給出了相應的路線圖。

3.4大規模算例結果與分析

在表6中，第2列是VNS算法運行10次平均使用的車輛數。t是VNS算法的平均運行時間，fGA是遺傳算法運行10次求得的平均值，σ1是VNS算法最優值和平均值的相對差值，其計算公式如下：

其中f-VNS，f*VNS分別表示VNS算法結果的平均值和最優值。σ２是VNS算法與遺傳算法的相對差值，其計算公式如下：

結果如表6所示，從相對誤差上，最優值和平均值的相對誤差都低于5%，平均相對誤差為3.18%，這說明VNS算法的魯棒性較好。VNS算法的平均值均優于遺傳算法的平均值，平均相對誤差為4.56%。算例測試表明提出的VNS算法求解大規模算例能夠得到高質量的解。

4結論

本文以最小化車輛總旅行距離為目標，考慮了車輛的容量約束、時間窗約束和電量約束，用混合整數線性規劃模型描述路段充電和帶時間窗的電動車取送貨問題，提出了一種變鄰域搜索算法求解該問題。算例分析表明提出的算法求解小規模算例只比最優解差0.08%，在大規模算例中也能求出高質量的可行解。

本文考慮的電動車動態充電模式可以與靜態充電模式互為補充，動態充電技術目前還不足以在市場上推廣應用，未來考慮兩種充電模式相結合的電動車取送貨問題或許是一個值得研究的問題。

參考文獻：

［1］KOC C， KRRAOGLA N I. The green vehicle routing problem： A heuristic based exact solution approach[J]. Applied Soft Computing， 2016， 39： 154-164. DOI： 10.1016/j.asoc.2015.10.064.

[2]DESAULNIERS G， ERRICO F， IRNICH S， et al. Exact algorithms for electric vehicle-routing problems with time windows[J]. Operations Research， 2016， 64（6）： 1388-1405. DOI： 10.1287/opre.2016.1535.

[3]ANDELMIN J， BARTOLINI E. An exact algorithm for the green vehicle routing problem[J]. Transportation Science， 2017， 51（4）： 1288-1303. DOI： 10.1287/trsc.2016.0734.

[4]商麗媛. 有時間窗裝卸問題的一類改進遺傳算法求解[J]. 太原師范學院學報（自然科學版）， 2009， 8（1）： 26-30. DOI： 10.3969/j.issn.1672-2027.2009.01.010.

[5]SCHNEIDER M， STENGER A， GOEKE D. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science， 2014， 48（4）： 500-520. DOI： 10.1287/trsc.2013.0490.

[6]KESKIN M， ATAY B. Partial recharge strategies for the electric vehicle routing problem with time windows[J]. Transportation Research Part C： Emerging Technologies， 2016， 65： 111-127. DOI： 10.1016/j.trc.2016.01.013.

[7]江玉萍. 帶時間窗和充電站的純電動物流車取送貨路徑優化問題[D]. 南京： 南京大學， 2019.

[8]GOEKE D. Granular tabu search for the pickup and delivery problem with time windows and electric vehicles[J]. European Journal of Operational Research， 2019， 278（3）： 821-836. DOI： 10.1016/j.ejor.2019.05.010.

[9]CHEN Z B， LIU W， YIN Y F. Deployment of stationary and dynamic charging infrastructure for electric vehicles along traffic corridors[J]. Transportation Research Part C： Emerging Technologies， 2017， 77： 185-206. DOI： 10.1016/j.trc.2017.01.021.

[10]鄒云程， 劉昊翔， 龍建成. 考慮出行者異質的多類型充電設施部署優化[J]. 系統工程理論與實踐， 2020， 40（11）： 2946-2957. DOI： 10.12011/1000-6788-2019-2610-12.

[11]NACCACHE S， CT J F， COELHO L C. The multi-pickup and delivery problem with time windows[J]. European Journal of Operational Research， 2018， 269（1）： 353-362. DOI： 10.1016/j.ejor.2018.01.035.