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

(1. 同濟(jì)大學(xué) 汽車學(xué)院，上 海 200092； 2. 同濟(jì)大學(xué) 交通運(yùn)輸工程學(xué)院， 上海 200092)

城市道路資源和停車資源緊張、環(huán)境污染等問(wèn)題使人們不得不關(guān)注機(jī)動(dòng)車的使用.電動(dòng)汽車共享是一種新興交通模式，發(fā)展前景巨大，通過(guò)多人共享的使用方式能有效提高車輛使用率并有望改變?nèi)藗兊某鲂杏^念從而減少私家車的保有量，此外，電動(dòng)汽車在節(jié)能減排和環(huán)保方面相對(duì)燃油車有較大的優(yōu)勢(shì).但是，電動(dòng)汽車共享作為一種新興用車模型進(jìn)入國(guó)內(nèi)，尚處于用戶推廣階段，加之用戶用車需求的潮汐性和不均衡性導(dǎo)致站點(diǎn)間車輛失衡從而無(wú)法滿足用車需求、降低了用戶體驗(yàn)，這是電動(dòng)汽車共享運(yùn)營(yíng)公司亟待解決的問(wèn)題，也是電動(dòng)汽車共享能否大規(guī)模推廣的關(guān)鍵因素.

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

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

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

1 研究模型和算法

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

1.1 電動(dòng)汽車共享調(diào)度需求模型

對(duì)于電動(dòng)汽車共享運(yùn)營(yíng)公司而言，滿足用戶需求前提下，運(yùn)營(yíng)成本也是公司需要考慮的重要因素.因此，調(diào)度需求模型是在已知周期內(nèi)訂單前提下，滿足全部用車需求情況下指定的調(diào)度成本最低的調(diào)度方案.

1.1.1問(wèn)題約定和假設(shè)

在建立模型前，對(duì)問(wèn)題進(jìn)行約定和假設(shè)：

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

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

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

1.1.2模型建立

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

目標(biāo)函數(shù)為最大收益函數(shù)，可轉(zhuǎn)換為最小調(diào)度需求的成本函數(shù)，即

式中：t表示服務(wù)周期，將一個(gè)運(yùn)營(yíng)周期等為M段，每段的開(kāi)始為時(shí)間結(jié)點(diǎn)，時(shí)間結(jié)點(diǎn)t={1，2，3，4，…，M}；n表示網(wǎng)點(diǎn)個(gè)數(shù)；cij表示從i調(diào)運(yùn)至j單位里程調(diào)運(yùn)成本，不同站點(diǎn)之間道路交通狀況不同，調(diào)運(yùn)過(guò)程中單位距離調(diào)運(yùn)成本相同；dij表示站點(diǎn)i到站點(diǎn)j距離；xtij表示站點(diǎn)空移車數(shù)，，?i≠j,xtij為非負(fù)整數(shù)變量.

1.1.2.2 約束條件

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

lvk(t)≥0

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

(2) 整個(gè)運(yùn)營(yíng)系統(tǒng)中，各時(shí)段各站點(diǎn)車輛總數(shù)守恒，即

?i≠jj∈1,…,n

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

(3) 在本系統(tǒng)中，車輛最大續(xù)航里程大于任意兩站點(diǎn)之間的距離，即

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

式中:L表示車輛最高續(xù)航里程.

(4) 各時(shí)段各站點(diǎn)車輛數(shù)目小于該站點(diǎn)停車位容量pi為

Card(sit)

式中：Card(sit)表示在t時(shí)刻停在站點(diǎn)i車輛數(shù)目.

(5) 車輛在站點(diǎn)之間通行的時(shí)間為

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

(6) 車輛從站點(diǎn)i到達(dá)站點(diǎn)j時(shí)，保證站點(diǎn)j有足夠的可用停車位ptj，即

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

(7) 車輛在行駛時(shí)，車輛續(xù)航里程的表達(dá)式為

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

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

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

因此，補(bǔ)充約束條件如下：

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

lvk(t)≥L-Δl

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

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

根據(jù)電動(dòng)汽車共享用車模式以及車輛調(diào)配特點(diǎn)可知，在服務(wù)周期內(nèi)各時(shí)段的車輛調(diào)配相互影響，調(diào)配方案需要從全局考慮，確定車輛調(diào)配方式，并且電動(dòng)汽車?yán)m(xù)航有限，以及充電時(shí)間等因素，所以該模型是一個(gè)前后關(guān)聯(lián)的多階段決策問(wèn)題.通過(guò)該模型求出最優(yōu)化的調(diào)度方案，給出成本最低的調(diào)度需求.

1.2 遺傳算法設(shè)計(jì)與實(shí)現(xiàn)

對(duì)于該車輛調(diào)度問(wèn)題，求解復(fù)雜程度較高，求解存在不確定性，并且隨著車輛規(guī)模的增加，求解難度程幾何級(jí)增長(zhǎng)，通常這類問(wèn)題被認(rèn)為是NP-Hard難解問(wèn)題，而針對(duì)此類問(wèn)題，目前尚無(wú)明確的求解算法.根據(jù)電動(dòng)汽車調(diào)度問(wèn)題的特征和對(duì)算法計(jì)算速度的高要求，本文采用遺傳算法求解該問(wèn)題.

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

圖1 遺傳算法流程

1.2.1染色體編碼與解碼

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

1.2.2初始化種群

在滿足編碼的前提下，隨機(jī)產(chǎn)生n個(gè)個(gè)體，組成初始種群，記為

G={g0,g1,…,gn}

1.2.3約束處理與適度函數(shù)

常見(jiàn)約束處理方法有3種：① 直接處理約束條件，在編碼過(guò)程中加入約束條件；② 計(jì)算過(guò)程中通過(guò)約束條件進(jìn)行校驗(yàn)；③ 通過(guò)懲罰函數(shù)處理約束.根據(jù)模型特點(diǎn)，本文采用直接處理約束的方法，以目標(biāo)函數(shù)作為適度函數(shù).

1.2.4遺傳操作

(1) 選擇

(2) 交叉

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

(3) 變異

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

1.2.5終止準(zhǔn)則

遺傳算法計(jì)算前必須設(shè)計(jì)終止算法準(zhǔn)則，遺傳算法是一種隨機(jī)并行搜索算法，需要設(shè)計(jì)終止準(zhǔn)則來(lái)終止循環(huán)，停止迭代，常見(jiàn)的終止算法有3種：① 達(dá)到預(yù)先設(shè)定目標(biāo)；② 種群中最優(yōu)個(gè)體在迭代中沒(méi)有改進(jìn)；③ 達(dá)到預(yù)先設(shè)定的進(jìn)化代數(shù).預(yù)先設(shè)定進(jìn)化代數(shù)能夠很好地控制算法的求解精度和運(yùn)行時(shí)間.綜合考慮，本文采用預(yù)先設(shè)定進(jìn)化點(diǎn)數(shù)，循環(huán)達(dá)到最大代數(shù)即停止迭代.

1.3 電動(dòng)汽車共享調(diào)度優(yōu)化模型

根據(jù)電汽車共享的特點(diǎn)，提出區(qū)域調(diào)度的模式，調(diào)度員采用折疊電動(dòng)自行車在站點(diǎn)之間通行，在調(diào)度空車過(guò)程中將折疊電動(dòng)自行車放置在后備箱中.建立以運(yùn)營(yíng)公司收益最大為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型，優(yōu)化模型，并采用分支定界法求解模型.

1.3.1問(wèn)題約定和假設(shè)

(1) 調(diào)度員任何時(shí)刻只能服務(wù)一個(gè)調(diào)度需求任務(wù)需求.

(2) 調(diào)度員在駕駛電動(dòng)汽車停車到站點(diǎn)后，取折疊電動(dòng)自行車的時(shí)間忽略不計(jì).

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

1.3.2模型建立

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

目標(biāo)函數(shù)為運(yùn)營(yíng)公司最大收益函數(shù)，有

式中：i∈P表示某站點(diǎn)i在某時(shí)間需要調(diào)離電動(dòng)汽車至別的站點(diǎn)；j∈D表示某站點(diǎn)j在某時(shí)間需要調(diào)配電動(dòng)汽車到該站點(diǎn)；s為調(diào)度員編號(hào)，S表示調(diào)度人員數(shù)量；Rer表示每個(gè)調(diào)度任務(wù)的收益；xijs=1表示調(diào)度員s從取車點(diǎn)i取車前往送車點(diǎn)j，否則xijs=0；O表示調(diào)度中心；C表示每班每個(gè)調(diào)度人員的工時(shí)費(fèi).

1.3.2.2 約束條件

(1) 調(diào)度員s從集合點(diǎn)出發(fā)，一個(gè)調(diào)度員只能有一個(gè)調(diào)度路徑，即

?s=1,…,S

(2) 每個(gè)調(diào)度任務(wù)只能執(zhí)行一次，即

?i∈P∪D

(3) 站點(diǎn)的訪問(wèn)時(shí)間是由其上一站點(diǎn)的訪問(wèn)時(shí)間加上調(diào)度時(shí)間的總和，即

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

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

式中：W表示每班調(diào)度人員的工作時(shí)長(zhǎng).

(4) 調(diào)度員取送車時(shí)間約束為

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

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

式中：tis為連續(xù)時(shí)間變量；τi表示取車任務(wù)站點(diǎn)i的服務(wù)時(shí)間；τj表示送車任務(wù)點(diǎn)j的服務(wù)時(shí)間.

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

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

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

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

式中：ρr表示調(diào)度任務(wù)r所需電量；e表示電動(dòng)汽車充電時(shí)單位時(shí)間增加的電量.

(6) 調(diào)度員在調(diào)度過(guò)程中電動(dòng)汽車電量滿足續(xù)航要求，有

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

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

1.4 調(diào)度路徑模型優(yōu)化和求解

1.4.1模型優(yōu)化

該模型是一個(gè)混合整數(shù)線性規(guī)劃模型，根據(jù)調(diào)度需求可以求解調(diào)度人員調(diào)度路徑.但是，在該模型中每個(gè)調(diào)度員的路線可以與其他調(diào)度員的路線交換，因此，該混合整數(shù)線性規(guī)劃模型在可行域中包含多個(gè)最優(yōu)解，對(duì)應(yīng)不同xijs和tis的值，不易求解，并且CPU會(huì)耗費(fèi)更多的時(shí)間來(lái)求最優(yōu)解.為了防止出現(xiàn)這種情況，對(duì)目標(biāo)函數(shù)增加約束條件：

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

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

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

1.4.2分支定界法求解模型

通過(guò)分析，關(guān)于調(diào)度人員的調(diào)度路徑優(yōu)化問(wèn)題是一個(gè)混合整數(shù)規(guī)劃模型，通常采用分支定界法(Branch and Bound)求解該模型.分支定界法最早由Dakin于1964年提出，經(jīng)過(guò)50多年的發(fā)展，目前分支定界法多被用于求解整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問(wèn)題.

分支定界法的核心思想是將求解問(wèn)題分解成若干子問(wèn)題，再將子問(wèn)題分解，直到無(wú)法對(duì)子問(wèn)題進(jìn)行分解，分解子問(wèn)題的過(guò)程稱為分支.分支的過(guò)程是估算目標(biāo)值的界限，這個(gè)過(guò)程稱為定界，定界可以預(yù)測(cè)解的趨勢(shì)，判定分支的有效性和求出不能判定的分支.將超出已知可行解集目標(biāo)值的子問(wèn)題刪除，這個(gè)過(guò)程稱為剪支，剪支可提高計(jì)算效率，加速收斂速度.分支定界法的步驟包含分支、定界、再到剪支，將該過(guò)程循環(huán)進(jìn)行，就是分支定界法的基本步驟.

分支定界法的計(jì)算前提是以深度優(yōu)先為目標(biāo)，估算目標(biāo)函數(shù)在分支結(jié)點(diǎn)的上、下界.再將該估算的解與已求得的最優(yōu)解進(jìn)行比較，刪除超過(guò)最優(yōu)解的決策，從而提高最優(yōu)解的求解速度.對(duì)于分支定界法而言，決策變量的先后順序和對(duì)目標(biāo)函數(shù)的估值精度決定了計(jì)算效率和精度.

分支定界法能夠在計(jì)算過(guò)程中保證精度的前提下加快計(jì)算速度，減少計(jì)算量，通過(guò)剪支舍去沒(méi)有希望的解從而求得問(wèn)題的最優(yōu)解，方便計(jì)算求解.

2 案例應(yīng)用與分析

2.1 案例概況

采用“EVCARD”位于上海市嘉定區(qū)的5個(gè)站點(diǎn)的實(shí)際運(yùn)營(yíng)數(shù)據(jù)作為案例進(jìn)行研究分析，以實(shí)際訂單作為輸入，進(jìn)行人工調(diào)度策略優(yōu)化分析，同時(shí)對(duì)比采用人工調(diào)度方案和擴(kuò)大車輛、車位規(guī)模的成本投入.表1為選取的5個(gè)站點(diǎn)之間的距離.

表1 各共享站點(diǎn)間距離

由于用戶出行的目的各不相同，各站點(diǎn)間的距離不能直接作為實(shí)際行駛距離.根據(jù)這5個(gè)站點(diǎn)在一個(gè)月內(nèi)的運(yùn)營(yíng)數(shù)據(jù)進(jìn)行篩選出的3 289條有效運(yùn)營(yíng)數(shù)據(jù)計(jì)算出各站點(diǎn)間的平均行駛時(shí)間，再通過(guò)高德地圖統(tǒng)計(jì)1 d內(nèi)站點(diǎn)所在區(qū)域道路平均行駛速度為30 km·h-1，則可換算出各站點(diǎn)間的實(shí)際行駛距離，見(jiàn)表2.站點(diǎn)初始時(shí)刻車輛和車位數(shù)如表3所示.

通過(guò)上一年同期的運(yùn)營(yíng)數(shù)據(jù)可知，5個(gè)站點(diǎn)平均51單·d-1，平均每輛車1.5單·d-1，通過(guò)增加車輛和車位數(shù)， 5個(gè)站點(diǎn)訂單數(shù)增加至平均104單·d-1，平均每輛車2.1單·d-1，雖然訂單數(shù)量增加一倍，但車輛利用率顯然沒(méi)有明顯的提高.

表2 各共享站點(diǎn)間實(shí)際行駛距離

表3 初始時(shí)刻車輛、車位數(shù)量

2.2 調(diào)度需求模型實(shí)例模擬

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

將30 min劃分為一個(gè)周期，1 d共計(jì)48個(gè)周期，根據(jù)這5個(gè)站點(diǎn)的運(yùn)營(yíng)數(shù)據(jù)，訂單主要集中在7:00 am～10:00 pm之間，占總訂單數(shù)的95.9%，為簡(jiǎn)化計(jì)算，忽略10:00 pm～7:00 am之間的訂單.因此，1 d共計(jì)30個(gè)周期，M=30.

根據(jù)數(shù)據(jù)規(guī)模，取群體個(gè)數(shù)為20，最大遺傳代數(shù)100，設(shè)置不同的交叉概率值和變異概率值，運(yùn)行結(jié)果顯示，交叉概率Pc=0.8，變異概率Pm=0.01計(jì)算結(jié)果最優(yōu).根據(jù)模型求出空車調(diào)度需求方案如表4所示，該模型是基于在周期內(nèi)全部滿足用戶104個(gè)訂單的求解結(jié)果，共調(diào)度25次.若不采用調(diào)度方案，從M=5時(shí)刻開(kāi)始站點(diǎn)B就會(huì)出現(xiàn)用戶無(wú)法還車的情況.

表4 空車調(diào)度需求方案

2.3 調(diào)度路徑優(yōu)化模型實(shí)例模擬

調(diào)度路徑優(yōu)化模型采用Lingo 11編寫程序，計(jì)算機(jī)為64位操作系統(tǒng)，處理器為Intel (R), Pentium (R), CPU, G2030 @ 3.00 GHz，安裝內(nèi)存為9.00GB.模型輸入?yún)?shù)：

假設(shè)調(diào)度員駕駛折疊電動(dòng)自行車的行駛速度為v″=20 km·h-1；車輛最高續(xù)航里程L=120 km；調(diào)度員月工資為8 000元，故每個(gè)調(diào)度員1 d的工時(shí)費(fèi)C=267元；折疊電動(dòng)自行車成本C′=1 000元；每個(gè)調(diào)度任務(wù)的收益Rer=15.6元.

根據(jù)表4所示調(diào)度需求方案，通過(guò)計(jì)算，采用2個(gè)調(diào)度員可以完成調(diào)度任務(wù)的88%，同時(shí)滿足收益最大化要求.兩個(gè)調(diào)度員的具體調(diào)度路徑分別為：

(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 收益分析

通過(guò)對(duì)比采用調(diào)度策略和擴(kuò)大車輛、車位規(guī)模這兩種方式，分析成本投入，以及各自帶來(lái)的收益變化，均以年作為計(jì)算投入與收益的時(shí)間范圍.相關(guān)參數(shù)說(shuō)明及取值見(jiàn)表5.

表5 相關(guān)參數(shù)說(shuō)明

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

圖2 3種策略下的支出與收益對(duì)比

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

3 結(jié)論與展望

目前，國(guó)內(nèi)外出現(xiàn)了多家電動(dòng)汽車共享運(yùn)營(yíng)公司，但因?yàn)橛脩粲密嚂r(shí)間、空間的不均衡性，在運(yùn)營(yíng)之中仍不可避免的出現(xiàn)某些時(shí)間站點(diǎn)車輛和車位的供需不平衡狀況，車輛的利用率不能達(dá)到理想的水平，影響運(yùn)營(yíng)公司收益.本文通過(guò)對(duì)電動(dòng)汽車共享中車輛調(diào)度問(wèn)題的研究，不同于以往研究基于已知調(diào)度需求或基于相對(duì)穩(wěn)定的用車需求條件下求解和優(yōu)化調(diào)度路徑，對(duì)實(shí)際用車需求導(dǎo)致站點(diǎn)車輛不平衡進(jìn)而產(chǎn)生的調(diào)度需求進(jìn)行研究，從而得到一整套完整的車輛人工調(diào)度策略，主要得出以下成果：

(1) 建立了需求全滿足前提下的調(diào)度成本最小目標(biāo)函數(shù)，構(gòu)建調(diào)度需求模型，并通過(guò)遺傳算法求解該NP-hard難解問(wèn)題，設(shè)計(jì)算法流程和思路.

(2) 在求出調(diào)度需求的基礎(chǔ)上，提出了調(diào)度員采用折疊電動(dòng)自行車在站點(diǎn)間通行的方法，構(gòu)建基于收益最大化的調(diào)度路徑優(yōu)化模型，采用分支定界法求解模型，生成調(diào)度路徑方案.

(3) 以“EVCARD”電動(dòng)汽車共享運(yùn)營(yíng)公司5個(gè)站點(diǎn)的實(shí)際運(yùn)營(yíng)數(shù)據(jù)為例，進(jìn)行人工調(diào)度策略優(yōu)化分析，通過(guò)收益分析發(fā)現(xiàn)，相比增設(shè)車輛和車位數(shù)量，采用人工調(diào)度策略能明顯提高運(yùn)營(yíng)公司收益及車輛利用率，節(jié)省車輛、車位的投入成本.

研究結(jié)論說(shuō)明了車輛人工調(diào)度策略的有效性，對(duì)當(dāng)前汽車共享行業(yè)在運(yùn)營(yíng)過(guò)程中面臨的車輛失衡問(wèn)題的解決和改善是有益的.但不足之處在于建立的調(diào)度路徑模型是基于收益最大化的調(diào)度方案，因此在一些情況下并不能完全滿足出現(xiàn)的調(diào)度需求，即無(wú)法滿足所有的訂單的用車需求.在未來(lái)的研究中可以考慮采用激勵(lì)用戶的方法進(jìn)行基于用戶激勵(lì)的自適應(yīng)調(diào)度策略，作為對(duì)調(diào)度員人工調(diào)度的補(bǔ)充，進(jìn)一步提高車輛利用效率和降低調(diào)度成本.此外，未來(lái)研究可基于運(yùn)營(yíng)數(shù)據(jù)，建立電動(dòng)汽車用車需求預(yù)測(cè)模型，根據(jù)預(yù)測(cè)數(shù)據(jù)，提前規(guī)劃共享站點(diǎn)位置、配置車輛和車位數(shù).