電動汽車共享站點間車輛人工調度策略

王 寧， 張文劍， 劉 向， 左 靜

(1. 同濟大學 汽車學院，上 海 200092； 2. 同濟大學 交通運輸工程學院， 上海 200092)

城市道路資源和停車資源緊張、環境污染等問題使人們不得不關注機動車的使用.電動汽車共享是一種新興交通模式，發展前景巨大，通過多人共享的使用方式能有效提高車輛使用率并有望改變人們的出行觀念從而減少私家車的保有量，此外，電動汽車在節能減排和環保方面相對燃油車有較大的優勢.但是，電動汽車共享作為一種新興用車模型進入國內，尚處于用戶推廣階段，加之用戶用車需求的潮汐性和不均衡性導致站點間車輛失衡從而無法滿足用車需求、降低了用戶體驗，這是電動汽車共享運營公司亟待解決的問題，也是電動汽車共享能否大規模推廣的關鍵因素.

目前，電動汽車共享站點車輛、車位不平衡的主要原因是用戶用車時間不確定且存在早晚高峰.部分站點車輛閑置，占用站點停車位導致用戶無法還車；部分站點車輛不足導致用戶無車可用.如何平衡供需，增加車輛的利用率，使得運營公司的收益最大化成為當前研究的熱點.

目前國內針對電動汽車共享站點間的調度研究相對較少，主要是效果分析，可行性等宏觀研究.國外汽車共享出現的時間較早，對于汽車共享車輛調度問題的主要研究如下： Dror Moshe[1]將拖車引入單程電動汽車共享調度模型中，將拉格朗日松弛方法應用到混合整數線性規劃模型，計算單程電動汽車共享的車輛調度最優路徑.Hafez Nevine[2]在Dror Moshe研究基礎上，采用3種啟發式算法計算調度耗時最少方案.LI Xiaopeng和MA Jiaqi[3]等根據電動汽車共享特點，基于連續逼近模型，優化了電動汽車共享調度系統，包括站點分布，站點車輛充電限制，減少綜合系統成本(包括站點建設投資、車輛維修、交通運輸和車輛平衡).WANG Hongman和LI Zhaohan[4]以葡萄牙里斯本市政府的電動汽車共享為研究對象，建立基于汽車共享運營公司利潤最大的混合整數規劃模型，分析比較3種不同的出行方式對公司收益的影響.Febbraro Angela Di[5]研究考慮了用戶和工作人員對車輛的重新定位，用離散系統的復雜動態，模擬不同的方案，以減少所需的工作人員數量，并減少共享的車輛數量，以滿足系統需求目標.Worley Owen[6]等研究電動汽車共享充電站站點布置和電動車輛調運的行車路徑，構造以最少站點建設成本和調度成本的線性規劃模型.

從文獻來看，大多數研究都基于已知調度需求或假設的用車需求條件下求解和優化調度路徑，較少對實際用車需求導致站點車輛不平衡進而產生的調度需求進行研究，缺乏完整的車輛人工調度策略.因此，本文根據電動汽車共享的特點設計電動汽車共享站點間的完整調度策略.首先，建立基于用戶需求全滿足的調度成本最低調度需求模型，采用遺傳算法求解模型，針對模型特點提出染色體編碼、交叉、變異等方面的具體設計思路，通過該模型求出調度需求.在此基礎之上，提出在站點間采用調度員駕駛電動自行車通行的方式進行車輛調度，并建立調度員路徑優化混合整數規劃模型，采用分支定界法求解調度路徑模型，生成基于收益最大化的調度路徑方案.最后，以“EVCARD”位于上海市嘉定區5個站點的實際訂單作為輸入，進行人工調度策略優化分析，驗證該模型的有效性.

1 研究模型和算法

國內電動汽車共享公司從小規模開始摸索試驗并積累經驗，在站點少、規模小的初期，隨著用戶數量的逐步增加，必然會出現站點間車數失衡的現象，這種情況會影響用戶的預約成功率，從而損害用戶體驗，這對一種新興交通模式的推廣是極為不利的.因此，本文基于電動汽車共享站點間車輛失衡情況構建一套完整的調度方法，在有限運營車輛的前提下，如何通過站點間調度來最大滿足用戶需求，建立調度需求模型，求得最優的調度方案.再根據調度方案，建立調度路徑優化模型，生成優化路徑，以達到減少調度成本的目的.

1.1 電動汽車共享調度需求模型

對于電動汽車共享運營公司而言，滿足用戶需求前提下，運營成本也是公司需要考慮的重要因素.因此，調度需求模型是在已知周期內訂單前提下，滿足全部用車需求情況下指定的調度成本最低的調度方案.

1.1.1問題約定和假設

在建立模型前，對問題進行約定和假設：

(1) 車輛維度：所有電動汽車均為同一型號，一輛車在任何時刻只能服務一個任務需求；車輛在站點時，默認與充電樁連接充電；車輛任何時刻續航里程已知，并且充電時單位時間增加續航相同，不受外部因素如溫度、濕度的影響；車輛循環使用，即在完成一個任務之后，如果續航滿足要求，可以繼續完成下一個任務.

(2) 站點維度：站點每個停車位均配備相同屬性的充電樁.

(3) 服務周期：在一個周期內，用戶的用車需求是隨機的，不能確定用戶用車需求時間，因此，為了簡化模型，將服務時間段劃分成若干周期.比如將1 d的24 h劃分成24個時段，每個時段1h.將用戶的取還車時刻都近似看作該時段開始時刻，比如用戶12:10分取車，則近似看作12:00取車.

1.1.2模型建立

1.1.2.1 目標函數

目標函數為最大收益函數，可轉換為最小調度需求的成本函數，即

式中：t表示服務周期，將一個運營周期等為M段，每段的開始為時間結點，時間結點t={1，2，3，4，…，M}；n表示網點個數；cij表示從i調運至j單位里程調運成本，不同站點之間道路交通狀況不同，調運過程中單位距離調運成本相同；dij表示站點i到站點j距離；xtij表示站點空移車數，，?i≠j,xtij為非負整數變量.

1.1.2.2 約束條件

(1) 在任何時刻車輛續駛里程均大于零：

lvk(t)≥0

式中:lvk(t)表示t時刻車輛k的續航里程.t時刻，車輛有兩種狀態：lvk0(t)停在站點充電；lvkij(t)從站點i行駛至站點j(包括用戶用車和空車調配).

(2) 整個運營系統中，各時段各站點車輛總數守恒，即

?i≠jj∈1,…,n

式中:Ati={ati1，ati2，ati3，…,atij，…,atin}，atij表示有載客需求從站點i到站點j并且在t時段起運的任務數；sit表示站點i在t時刻車輛集合,sit={v1,v2,…,vk}，且初始時刻站點i所停車輛已知.

(3) 在本系統中，車輛最大續航里程大于任意兩站點之間的距離，即

L>dij?i≠ji,j∈1,…,n

式中:L表示車輛最高續航里程.

(4) 各時段各站點車輛數目小于該站點停車位容量pi為

Card(sit)

式中：Card(sit)表示在t時刻停在站點i車輛數目.

(5) 車輛在站點之間通行的時間為

?i≠ji,j∈1,…,n

(6) 車輛從站點i到達站點j時，保證站點j有足夠的可用停車位ptj，即

?i≠ji,j∈1,…,n

(7) 車輛在行駛時，車輛續航里程的表達式為

?i≠ji,j∈1,…,n

lvk0(t)=lvk0(t-1)+e×Δt, 0≤lvk0(t)≤lmax

對于本模型而言，車輛的用車決策是無法約束的,為簡化計算，做如下假設：用戶用車時優先使用滿電車輛，車輛被使用后，若站點車數目大于Δk，則車輛充電至滿電后方可使用；若站點車輛數小于Δk，則需充電至車輛續航里程能夠覆蓋任意站點間距離且有一定余量后方可使用，保證站點有一定車輛，避免站點出現無車的情況.例如，當初始時刻，車輛k從站點1到站點2后，車輛k續航減少d12，站點2多一輛續航為L-d12的車輛，此時站點2滿電車輛足夠，則車輛k充電至滿電后方可再次使用.若站點2無足夠滿電車輛，則充電至續航為L-Δl方可使用，并且優先使用滿電車輛.該假設能夠保證用戶所駕駛車輛續航足夠，減緩駕駛過程中駕駛員的續航焦慮，并且符合用戶使用習慣.

因此，補充約束條件如下：

(1) 系統中車輛續航大于可用續航L-Δl方可成為可使用車輛，且可用續航需大于系統中任意兩站點距離，即

lvk(t)≥L-Δl

L-Δl≥dij?i≠ji,j∈1,…,n

(2) 車輛被使用后，再次成為可用車輛所需時間如下：

根據電動汽車共享用車模式以及車輛調配特點可知，在服務周期內各時段的車輛調配相互影響，調配方案需要從全局考慮，確定車輛調配方式，并且電動汽車續航有限，以及充電時間等因素，所以該模型是一個前后關聯的多階段決策問題.通過該模型求出最優化的調度方案，給出成本最低的調度需求.

1.2 遺傳算法設計與實現

對于該車輛調度問題，求解復雜程度較高，求解存在不確定性，并且隨著車輛規模的增加，求解難度程幾何級增長，通常這類問題被認為是NP-Hard難解問題，而針對此類問題，目前尚無明確的求解算法.根據電動汽車調度問題的特征和對算法計算速度的高要求，本文采用遺傳算法求解該問題.

遺傳算法(Genetic Algorithm，GA)是起源于生物進化理論.最早由美國密西根大學的Holland教授的學生于1967年博士論文中提出，基本思想是模擬達爾文的遺傳選擇和自然界優勝劣汰的生存法則，在此基礎上構建計算模型，是一種迭代搜索算法.遺傳算法的搜索過程是基于群體的，GA搜索開始時，會首先產生一個隨機群體，稱為“種群(population)”.并且，遺傳算法求解過程不依賴梯度信息，通過模擬自然界的進化過程來搜索最優解，是一種高效、并行、全局的搜索方法.遺傳算法的運算過程如圖1所示.

圖1 遺傳算法流程

1.2.1染色體編碼與解碼

根據車輛調度特點，本文中染色體編碼包括被優化參數.染色體的基因序列g=(V,VC，D,DT,DN,DB,DE)，基因由7部分構成，其中，V表示車輛的平均行駛速度；VC表示車輛平均充電速度；D表示站點距離；DT表示空車調配啟動時刻；DN表示空車調配啟動數量；DB表示空車調配起始站點；DE表示空車調配的目的站點.

1.2.2初始化種群

在滿足編碼的前提下，隨機產生n個個體，組成初始種群，記為

G={g0,g1,…,gn}

1.2.3約束處理與適度函數

常見約束處理方法有3種：① 直接處理約束條件，在編碼過程中加入約束條件；② 計算過程中通過約束條件進行校驗；③ 通過懲罰函數處理約束.根據模型特點，本文采用直接處理約束的方法，以目標函數作為適度函數.

1.2.4遺傳操作

(1) 選擇

(2) 交叉

采用啟發式的交叉算子.設置交叉概率pc,在父代種群中隨機產生兩個個體，然后在區間(0,1)中生成隨機數p.若p>pc，父代染色體不進行交叉，反之，染色體交叉.在交叉過程中，隨機確定一個交叉點k，(1≤k≤n)，則在片段k之后，父代染色體進行交叉，k之前染色體保持不變.該交叉方法指只改變了染色體n-k的部分，保留了k片段，既能繼承父代的優良基因，也體現了種群進化的思想.

(3) 變異

采用的是單片段變異方法.設種群的變異概率是pm，然后在區間(0,1)中生成隨機數p′，若p′>pm，父代染色體不進行變異，不會產生新個體，反之，染色體變異.產生一個隨機整數f(1≤f≤n)，表示染色體的第f個片段進行變異.將染色體的第f個片段重新進行編碼，通過替換原來染色體片段而產生新染色體.

1.2.5終止準則

遺傳算法計算前必須設計終止算法準則，遺傳算法是一種隨機并行搜索算法，需要設計終止準則來終止循環，停止迭代，常見的終止算法有3種：① 達到預先設定目標；② 種群中最優個體在迭代中沒有改進；③ 達到預先設定的進化代數.預先設定進化代數能夠很好地控制算法的求解精度和運行時間.綜合考慮，本文采用預先設定進化點數，循環達到最大代數即停止迭代.

1.3 電動汽車共享調度優化模型

根據電汽車共享的特點，提出區域調度的模式，調度員采用折疊電動自行車在站點之間通行，在調度空車過程中將折疊電動自行車放置在后備箱中.建立以運營公司收益最大為目標函數的混合整數規劃模型，優化模型，并采用分支定界法求解模型.

1.3.1問題約定和假設

(1) 調度員任何時刻只能服務一個調度需求任務需求.

(2) 調度員在駕駛電動汽車停車到站點后，取折疊電動自行車的時間忽略不計.

(3) 模型不考慮車輛和折疊電動自行車發生故障等意外情況.

1.3.2模型建立

1.3.2.1 目標函數

目標函數為運營公司最大收益函數，有

式中：i∈P表示某站點i在某時間需要調離電動汽車至別的站點；j∈D表示某站點j在某時間需要調配電動汽車到該站點；s為調度員編號，S表示調度人員數量；Rer表示每個調度任務的收益；xijs=1表示調度員s從取車點i取車前往送車點j，否則xijs=0；O表示調度中心；C表示每班每個調度人員的工時費.

1.3.2.2 約束條件

(1) 調度員s從集合點出發，一個調度員只能有一個調度路徑，即

?s=1,…,S

(2) 每個調度任務只能執行一次，即

?i∈P∪D

(3) 站點的訪問時間是由其上一站點的訪問時間加上調度時間的總和，即

tis+cijxijs≤tjs+W(1-xijs) ?i∈P,

?j∈D, ?s=1,…,S

式中：W表示每班調度人員的工作時長.

(4) 調度員取送車時間約束為

tis≥τi?i∈P, ?s=1,…,S

tjs≥τj?j∈D, ?s=1,…,S

式中：tis為連續時間變量；τi表示取車任務站點i的服務時間；τj表示送車任務點j的服務時間.

(5) 電動汽車在行駛過程中，行駛距離與所耗電量呈線性關系：

dijxijs≤L(ρi+e(tis-τi))

?i∈P, ?j∈D, ?s=1,…,S

ρi+e(tis-τi)≤1

式中：ρr表示調度任務r所需電量；e表示電動汽車充電時單位時間增加的電量.

(6) 調度員在調度過程中電動汽車電量滿足續航要求，有

ρj-e(tjs-τj)-(ρj+1)(1-xijs)

?i∈P, ?j∈D, ?s=1,…,S

1.4 調度路徑模型優化和求解

1.4.1模型優化

該模型是一個混合整數線性規劃模型，根據調度需求可以求解調度人員調度路徑.但是，在該模型中每個調度員的路線可以與其他調度員的路線交換，因此，該混合整數線性規劃模型在可行域中包含多個最優解，對應不同xijs和tis的值，不易求解，并且CPU會耗費更多的時間來求最優解.為了防止出現這種情況，對目標函數增加約束條件：

(1) 指定路線分配給調度人員，不允許調度員之間交換路線，則

?s′,s″∈1,…,S;s′

(2) 顯示最大滿足需求的上限，則

1.4.2分支定界法求解模型

通過分析，關于調度人員的調度路徑優化問題是一個混合整數規劃模型，通常采用分支定界法(Branch and Bound)求解該模型.分支定界法最早由Dakin于1964年提出，經過50多年的發展，目前分支定界法多被用于求解整數規劃和混合整數規劃問題.

分支定界法的核心思想是將求解問題分解成若干子問題，再將子問題分解，直到無法對子問題進行分解，分解子問題的過程稱為分支.分支的過程是估算目標值的界限，這個過程稱為定界，定界可以預測解的趨勢，判定分支的有效性和求出不能判定的分支.將超出已知可行解集目標值的子問題刪除，這個過程稱為剪支，剪支可提高計算效率，加速收斂速度.分支定界法的步驟包含分支、定界、再到剪支，將該過程循環進行，就是分支定界法的基本步驟.

分支定界法的計算前提是以深度優先為目標，估算目標函數在分支結點的上、下界.再將該估算的解與已求得的最優解進行比較，刪除超過最優解的決策，從而提高最優解的求解速度.對于分支定界法而言，決策變量的先后順序和對目標函數的估值精度決定了計算效率和精度.

分支定界法能夠在計算過程中保證精度的前提下加快計算速度，減少計算量，通過剪支舍去沒有希望的解從而求得問題的最優解，方便計算求解.

2 案例應用與分析

2.1 案例概況

采用“EVCARD”位于上海市嘉定區的5個站點的實際運營數據作為案例進行研究分析，以實際訂單作為輸入，進行人工調度策略優化分析，同時對比采用人工調度方案和擴大車輛、車位規模的成本投入.表1為選取的5個站點之間的距離.

表1 各共享站點間距離

由于用戶出行的目的各不相同，各站點間的距離不能直接作為實際行駛距離.根據這5個站點在一個月內的運營數據進行篩選出的3 289條有效運營數據計算出各站點間的平均行駛時間，再通過高德地圖統計1 d內站點所在區域道路平均行駛速度為30 km·h-1，則可換算出各站點間的實際行駛距離，見表2.站點初始時刻車輛和車位數如表3所示.

通過上一年同期的運營數據可知，5個站點平均51單·d-1，平均每輛車1.5單·d-1，通過增加車輛和車位數， 5個站點訂單數增加至平均104單·d-1，平均每輛車2.1單·d-1，雖然訂單數量增加一倍，但車輛利用率顯然沒有明顯的提高.

表2 各共享站點間實際行駛距離

表3 初始時刻車輛、車位數量

2.2 調度需求模型實例模擬

取車輛最高續航里程L=120 km；車輛充電速度e=18 km·h-1；站點之間單位里程調度成本cij=1元·km-1；用戶用車時，每公里收益wij=1元·km-1；取L-Δl=30 km；站點車輛數目限制Δk=2.

將30 min劃分為一個周期，1 d共計48個周期，根據這5個站點的運營數據，訂單主要集中在7:00 am～10:00 pm之間，占總訂單數的95.9%，為簡化計算，忽略10:00 pm～7:00 am之間的訂單.因此，1 d共計30個周期，M=30.

根據數據規模，取群體個數為20，最大遺傳代數100，設置不同的交叉概率值和變異概率值，運行結果顯示，交叉概率Pc=0.8，變異概率Pm=0.01計算結果最優.根據模型求出空車調度需求方案如表4所示，該模型是基于在周期內全部滿足用戶104個訂單的求解結果，共調度25次.若不采用調度方案，從M=5時刻開始站點B就會出現用戶無法還車的情況.

表4 空車調度需求方案

2.3 調度路徑優化模型實例模擬

調度路徑優化模型采用Lingo 11編寫程序，計算機為64位操作系統，處理器為Intel (R), Pentium (R), CPU, G2030 @ 3.00 GHz，安裝內存為9.00GB.模型輸入參數：

假設調度員駕駛折疊電動自行車的行駛速度為v″=20 km·h-1；車輛最高續航里程L=120 km；調度員月工資為8 000元，故每個調度員1 d的工時費C=267元；折疊電動自行車成本C′=1 000元；每個調度任務的收益Rer=15.6元.

根據表4所示調度需求方案，通過計算，采用2個調度員可以完成調度任務的88%，同時滿足收益最大化要求.兩個調度員的具體調度路徑分別為：

(1) O-A-C-C-A-D-A-E-A-C-A-B-A-B-C-C-A-D-A-C-A-O

(2) O-B-D-A-D-B-A-D-A-D-A-D-A-B-A-C-B-C-A-B-C-O

2.4 收益分析

通過對比采用調度策略和擴大車輛、車位規模這兩種方式，分析成本投入，以及各自帶來的收益變化，均以年作為計算投入與收益的時間范圍.相關參數說明及取值見表5.

表5 相關參數說明

通過計算，得到了增設車輛和車位、采用調度策略以及保持原狀3種策略下的成本支出與訂單收益，如圖2所示.

圖2 3種策略下的支出與收益對比

在用戶用車需求增長的情況下，不增設停車位和車輛數目而采用人工調度優化策略，同比可以提升60%的訂單服務量，訂單收入增加89.4%，雖然訂單收入較增設停車位和車輛數目后的實際情況略有減少12%，但是相比增設停車位和車輛數目可以節約62.4%的成本投入.由此可見，運營公司采取人工調度策略的方式，而非增設停車位和車輛數目的方式可為運營公司節約成本，增加公司收益.

3 結論與展望

目前，國內外出現了多家電動汽車共享運營公司，但因為用戶用車時間、空間的不均衡性，在運營之中仍不可避免的出現某些時間站點車輛和車位的供需不平衡狀況，車輛的利用率不能達到理想的水平，影響運營公司收益.本文通過對電動汽車共享中車輛調度問題的研究，不同于以往研究基于已知調度需求或基于相對穩定的用車需求條件下求解和優化調度路徑，對實際用車需求導致站點車輛不平衡進而產生的調度需求進行研究，從而得到一整套完整的車輛人工調度策略，主要得出以下成果：

(1) 建立了需求全滿足前提下的調度成本最小目標函數，構建調度需求模型，并通過遺傳算法求解該NP-hard難解問題，設計算法流程和思路.

(2) 在求出調度需求的基礎上，提出了調度員采用折疊電動自行車在站點間通行的方法，構建基于收益最大化的調度路徑優化模型，采用分支定界法求解模型，生成調度路徑方案.

(3) 以“EVCARD”電動汽車共享運營公司5個站點的實際運營數據為例，進行人工調度策略優化分析，通過收益分析發現，相比增設車輛和車位數量，采用人工調度策略能明顯提高運營公司收益及車輛利用率，節省車輛、車位的投入成本.

研究結論說明了車輛人工調度策略的有效性，對當前汽車共享行業在運營過程中面臨的車輛失衡問題的解決和改善是有益的.但不足之處在于建立的調度路徑模型是基于收益最大化的調度方案，因此在一些情況下并不能完全滿足出現的調度需求，即無法滿足所有的訂單的用車需求.在未來的研究中可以考慮采用激勵用戶的方法進行基于用戶激勵的自適應調度策略，作為對調度員人工調度的補充，進一步提高車輛利用效率和降低調度成本.此外，未來研究可基于運營數據，建立電動汽車用車需求預測模型，根據預測數據，提前規劃共享站點位置、配置車輛和車位數.