基于用戶激勵(lì)的共享電動(dòng)汽車調(diào)度成本優(yōu)化

王 寧，鄭文暉，劉 向，郭家輝

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

電動(dòng)化、網(wǎng)聯(lián)化、智能化、共享化是汽車行業(yè)正在經(jīng)歷的重大變革.電動(dòng)共享車輛模式對(duì)減少交通擁堵、節(jié)能減排、促進(jìn)共享經(jīng)濟(jì)發(fā)展具有顯著作用，得到政府和企業(yè)的高度重視.北京、上海、深圳等多地正展開(kāi)商業(yè)示范運(yùn)營(yíng)[1].然而客戶出行需求的潮汐性特征引起站點(diǎn)間車輛分配不均，某些時(shí)段無(wú)法有效滿足客戶需求，導(dǎo)致客戶體驗(yàn)較差，制約了該商業(yè)模式的大規(guī)模推廣.

目前,相關(guān)運(yùn)營(yíng)企業(yè)在解決車輛的不均衡配置問(wèn)題上主要采用員工調(diào)度模式[2-3].該模式存在調(diào)度反饋滯后、峰谷時(shí)段拒絕取、還車比率高、人力成本高昂等諸多問(wèn)題.如何對(duì)車輛的不均衡需求匹配做出快速反應(yīng)，解決供需平衡，提高用戶滿意度，擴(kuò)大運(yùn)營(yíng)公司收益并減少調(diào)度成本，成為當(dāng)前研究的熱點(diǎn)及難點(diǎn)問(wèn)題.

汽車共享車輛的調(diào)度按車輛運(yùn)營(yíng)模式分為雙程式共享車輛調(diào)度和單程式共享車輛調(diào)度.本文研究所涉及的內(nèi)容是單程式共享車輛調(diào)度.按照調(diào)度主體可分為員工調(diào)度和用戶調(diào)度兩類.目前大量研究是對(duì)員工調(diào)度的研究，僅有少量涉及用戶調(diào)度的研究.

早期單程式調(diào)度研究主要以企業(yè)成本最優(yōu)為優(yōu)化目標(biāo)，采用線性規(guī)劃模型或混合整數(shù)規(guī)劃模型為主.Fan等[4]提出了一種多級(jí)隨機(jī)線性優(yōu)化模型，將不確定性納入模型的構(gòu)建中，但模型的求解算法需要進(jìn)一步優(yōu)化.Kek等[5]提出三步優(yōu)化法的調(diào)度模型，構(gòu)建車輛調(diào)度與員工再平衡的調(diào)度成本最優(yōu)的線性整數(shù)模型，但算法不適合大規(guī)模求解.Jorge 等[6]以最大企業(yè)收入、最小車輛保養(yǎng)、遷移及折舊成本為優(yōu)化目標(biāo)，構(gòu)建了混合整數(shù)規(guī)劃模型.Nourinejad[7]研究了共享汽車的沿途搭乘路徑規(guī)劃的成本最優(yōu)問(wèn)題.Nourinejad等[8]考慮了車輛遷移的一次調(diào)度與員工再平衡的二次調(diào)度問(wèn)題.其調(diào)度問(wèn)題分解為MP(管理工程)和SP(支撐工程)問(wèn)題,創(chuàng)建基于企業(yè)成本最優(yōu)的混合整數(shù)規(guī)劃模型，并采用CPLEX軟件進(jìn)行混合整數(shù)規(guī)劃求解.Bruglieri 等[9]研究了單程式的電動(dòng)汽車調(diào)度問(wèn)題(E0-VRP),并采用兩種啟發(fā)式遺傳算法進(jìn)行優(yōu)化求解.Saadi等[10]通過(guò)微觀數(shù)據(jù)的代理人模型(Agent-based model)對(duì)需求進(jìn)行分析.

國(guó)內(nèi)目前沒(méi)有大規(guī)?；谟脩粽{(diào)度的研究，Brendel等[11]提出了基于用戶調(diào)度的單程式共享車輛調(diào)度框架模型，但其使用雙程式數(shù)據(jù)來(lái)仿真單程式問(wèn)題，并未能實(shí)現(xiàn)大量數(shù)據(jù)的仿真.Cao等[12]提出對(duì)單一站點(diǎn)的取、還車采用閾值的手段，但只能解決長(zhǎng)時(shí)段缺車問(wèn)題，對(duì)短時(shí)內(nèi)(1 d內(nèi))調(diào)度未能有效解決.Clemente 等[13]提出采用價(jià)格激勵(lì)和閾值作為用戶調(diào)度的DSS(決策支持系統(tǒng))，但未能考慮不同時(shí)間下閾值變化的問(wèn)題，并且其用戶調(diào)度模式僅考慮在用戶還車的情景下.

綜上，目前關(guān)于用戶自適應(yīng)調(diào)度的研究還相當(dāng)缺乏，本文創(chuàng)新之處在于考慮共享單車在共享汽車調(diào)度問(wèn)題中的作用，并提出多時(shí)段可變的上下閾值作為調(diào)度決策的關(guān)鍵變量，引入價(jià)格優(yōu)惠激勵(lì)機(jī)制引導(dǎo)用戶實(shí)現(xiàn)自適應(yīng)調(diào)度.

1 研究模型及算法

目前電動(dòng)共享車輛企業(yè)采取員工調(diào)度策略匹配運(yùn)營(yíng)需求，由于員工調(diào)度具有很大的遲滯性和經(jīng)驗(yàn)性，難以有效應(yīng)對(duì)用戶取、還車的瞬時(shí)波動(dòng)和潮汐現(xiàn)象[14].本文提出通過(guò)價(jià)格變化和共享單車作為激勵(lì)手段，建立調(diào)度成本最優(yōu)的車輛調(diào)度模型，實(shí)現(xiàn)車輛的自適應(yīng)調(diào)度.

1.1 問(wèn)題約定及變量定義

1.1.1問(wèn)題假設(shè)

(1) 共享汽車方面：運(yùn)營(yíng)車輛均為純電動(dòng)汽車,1輛電動(dòng)汽車任何時(shí)刻只能滿足1個(gè)訂單需求,所有車輛均為同一等級(jí)車輛,共享車輛企業(yè)采用單程式運(yùn)營(yíng)模式.

(2) 站點(diǎn)方面：每個(gè)站點(diǎn)停車位均配有相同型號(hào)的充電樁；任意兩站點(diǎn)間距離不得大于車輛最大續(xù)航里程；站點(diǎn)周圍存在共享單車(OFO、摩拜等)，但用戶是否愿意采用此方式取、還車受到優(yōu)惠價(jià)格的影響.

(3) 服務(wù)周期：在進(jìn)行歷史數(shù)據(jù)分析時(shí)，每天0:00～6:00點(diǎn)為車輛維護(hù)時(shí)間，6:00～24:00點(diǎn)為正常運(yùn)營(yíng)時(shí)間；根據(jù)實(shí)際訂單的分配和服務(wù)時(shí)間，將訂單數(shù)據(jù)采集設(shè)定為30 min為1個(gè)周期.

(4) 運(yùn)營(yíng)系統(tǒng)：本研究暫不考慮車輛運(yùn)營(yíng)路徑交通擁堵等異常情況；當(dāng)用戶進(jìn)行取車操作，并且取車站點(diǎn)的車輛過(guò)少(低于閾值)時(shí)，系統(tǒng)會(huì)詢問(wèn)用戶是否接受一定的價(jià)格優(yōu)惠并騎行共享單車到達(dá)系統(tǒng)分配的相鄰站點(diǎn)完成取車；當(dāng)用戶進(jìn)行還車操作，并且還車站點(diǎn)車輛過(guò)多(高于閾值)時(shí)，系統(tǒng)會(huì)詢問(wèn)用戶是否接受一定的價(jià)格優(yōu)惠并還車到系統(tǒng)分配的相鄰網(wǎng)點(diǎn)；用戶通過(guò)共享單車前往某一相鄰的共享汽車站點(diǎn)的時(shí)間不會(huì)超過(guò)10 min，即在下一個(gè)調(diào)度時(shí)間間隔(30 min)內(nèi)，調(diào)度任務(wù)將得以完成.

1.1.2集合、決策變量和參數(shù)定義

(1) 集合

T={1,…,t,…,T}為仿真過(guò)程中時(shí)間步長(zhǎng).

Rtn={0,1,3,…,rtn,…}為各站點(diǎn)請(qǐng)求還車數(shù)目集合.其中每一行如rtn代表1個(gè)時(shí)間間隔的所有站點(diǎn)的請(qǐng)求還車需求信息，每行中的每個(gè)數(shù)字是每個(gè)站點(diǎn)的還車需求數(shù)目.基于歷史數(shù)據(jù)按30 min為間隔獲得的各個(gè)站點(diǎn)、各個(gè)時(shí)間段的請(qǐng)求還車數(shù).

Dtn={1,1,3,…,dtn,…}為各站點(diǎn)請(qǐng)求取車數(shù)目集合.與R類似，Dtn是基于歷史數(shù)據(jù)按30 min為間隔獲得的各個(gè)站點(diǎn)、各個(gè)時(shí)間段的請(qǐng)求取車數(shù).

N={1,…,n,…}為站點(diǎn)編號(hào)集合.

(2) 決策變量

sf tn為站點(diǎn)n在t時(shí)刻的上閾值.

sb tn為站點(diǎn)n在t時(shí)刻的下閾值.

xf n為站點(diǎn)n在每天初始時(shí)刻所需要安置的可用車輛數(shù).

Xtij為t時(shí)刻i站點(diǎn)到j(luò)站點(diǎn)引導(dǎo)用戶異地還車，并用共享單車前往目的地的數(shù)量矩陣.

Ytij為t時(shí)刻i站點(diǎn)到j(luò)站點(diǎn)引導(dǎo)用戶通過(guò)共享單車異地取車的數(shù)量矩陣.

Xf tn為站點(diǎn)n在t時(shí)刻于調(diào)度前取、還車用戶需求預(yù)期統(tǒng)計(jì)(可能為負(fù)值).

Xb tn為站點(diǎn)n在t時(shí)刻在擬調(diào)度完成后的可用車輛數(shù)目(可能為負(fù)值).

Xtn為站點(diǎn)n在t時(shí)刻在調(diào)度完成后的可用車輛數(shù)目.

(3) 參數(shù)

ppark為站點(diǎn)n的最大停車位數(shù)目.

stn為站點(diǎn)n在t時(shí)刻的狀態(tài)指示符.

atn為站點(diǎn)n在t時(shí)刻擬異地用戶還車數(shù).

α為用戶選擇異地還車的比例，該比例與優(yōu)惠價(jià)格有關(guān).

btn為站點(diǎn)n在t時(shí)刻擬異地取車用戶數(shù).

β為用戶選擇異地取車的比例，該比例與優(yōu)惠價(jià)格有關(guān).

dij為由站點(diǎn)i通過(guò)共享汽車騎行到站點(diǎn)j的騎行時(shí)間.

e為用戶異地還車補(bǔ)貼優(yōu)惠金額.

g為用戶異地取車補(bǔ)貼優(yōu)惠金額.

h為拒絕用戶還車潛在損失成本.

k為拒絕用戶取車潛在損失成本.

Xa tn為站點(diǎn)n在t時(shí)刻調(diào)度所用臨時(shí)變量.

re tn為站點(diǎn)n在t時(shí)刻在承擔(dān)調(diào)度任務(wù)后是否車位已滿的指標(biāo)量；re tn為0表示車位未滿，re tn為1表示車位已滿.

rb tn為站點(diǎn)n在t時(shí)刻在承擔(dān)調(diào)度任務(wù)后是否車位已空的指標(biāo)量；rb tn為0表示車位未空，rb tn為1表示車位已空.

ah n為富余車輛站點(diǎn)n的調(diào)度任務(wù)是否分配完畢的指標(biāo)量.

bh n為缺車車輛站點(diǎn)n的調(diào)度任務(wù)是否分配完畢的指標(biāo)量.

ltn為站點(diǎn)n在t時(shí)刻車位數(shù)的臨時(shí)變量.

ptn為站點(diǎn)n在t時(shí)刻的還車請(qǐng)求是否可以分配指示符；當(dāng)ptn為0時(shí)表明周圍網(wǎng)點(diǎn)可以進(jìn)行車輛的還車分配，ptn為1時(shí)表明周圍網(wǎng)點(diǎn)無(wú)法進(jìn)行車輛的還車分配.

qtn為站點(diǎn)n在t時(shí)刻的取車請(qǐng)求是否可以分配指示符;當(dāng)qtn為0時(shí)表明周圍網(wǎng)點(diǎn)可以進(jìn)行車輛的取車分配,qtn為1時(shí)表明周圍網(wǎng)點(diǎn)無(wú)法進(jìn)行車輛的取車分配.

rref tn為站點(diǎn)n在t時(shí)刻拒絕用戶還車數(shù)量.

rreb tn為站點(diǎn)n在t時(shí)刻拒絕用戶取車數(shù)量.

Ra為汽車異地還車的用戶汽車調(diào)度優(yōu)惠成本.

Rb為汽車異地取車的用戶單車調(diào)度優(yōu)惠成本.

Rref為拒絕用戶還車潛在損失成本.

Rreb為拒絕用戶取車潛在損失成本.

1.2 調(diào)度模型邏輯流程

該部分邏輯框架流程分為5個(gè)部分：站點(diǎn)狀態(tài)及站點(diǎn)初值分配,擬調(diào)度汽車單車數(shù)初步分配,調(diào)度分配決策算法,調(diào)度最終分配及車輛終值,調(diào)度成本計(jì)算.

1.2.1站點(diǎn)狀態(tài)及站點(diǎn)初值分配，擬調(diào)度汽車單車數(shù)初步分配

Xf tn是對(duì)用戶的取、還車需求進(jìn)行統(tǒng)計(jì)，其計(jì)算公式為上一時(shí)段的車輛數(shù)與擬取、還車需求訂單的代數(shù)加減.

Xf tn=Xf(t-1)n+Rtn-Dtn

(1)

stn是站點(diǎn)狀態(tài)指示符，通過(guò)現(xiàn)有情況判斷站點(diǎn)處于何種狀態(tài)，指示符2代表目前站點(diǎn)車輛過(guò)多(超過(guò)最大停車位數(shù))，指示符1代表站點(diǎn)車輛偏多(超過(guò)上閾值)，高于閾值sf tn，指示符0代表站點(diǎn)狀態(tài)良好(處于上下閾值之間)，指示符-1代表站點(diǎn)車輛偏少(低于閾值sb tn但高于空車位數(shù))，指示符-2代表站點(diǎn)車輛過(guò)少(低于空車位數(shù)).其計(jì)算式如下:

(2)

atn與btn是擬進(jìn)行調(diào)度分配值.其中atn是擬引導(dǎo)用戶異地站點(diǎn)還車的數(shù)量，btn是擬引導(dǎo)用戶通過(guò)騎行共享單車前往異地取車的數(shù)量.

當(dāng)站點(diǎn)可用車輛超過(guò)停車位或者低于0時(shí)，用戶無(wú)法在當(dāng)前站點(diǎn)進(jìn)行還車(車滿)或取車(車空)，因此所有的取、還車訂單將分配到相鄰站點(diǎn).當(dāng)站點(diǎn)可用車輛高于上閾值或低于下閾值時(shí)，將有一定比例的用戶選擇異地取、還車，該比例與獎(jiǎng)勵(lì)金額有關(guān).其計(jì)算式如下：

(3)

(4)

1.2.2調(diào)度決策分配

算法對(duì)每一個(gè)站點(diǎn)都進(jìn)行訪問(wèn)，若站點(diǎn)狀態(tài)高于上閾值，則通過(guò)價(jià)格優(yōu)惠手段建議并引導(dǎo)用戶異地還車(存在用戶選擇率).若站點(diǎn)處于正常狀態(tài)，則用戶可以在原站點(diǎn)進(jìn)行取、還車操作.

調(diào)度任務(wù)完成情況處理如下：

(1) 當(dāng)分配至其他站點(diǎn)車輛容量均未超過(guò)其正常容量時(shí)，將可用車輛進(jìn)行分配并寫(xiě)入Xij中.

(2) 當(dāng)分配至某一站點(diǎn)的車輛超過(guò)該站點(diǎn)車輛容量時(shí)，以最大分配原則進(jìn)行分配.保留剩余車輛任務(wù)數(shù)，并選擇其他相鄰站點(diǎn)繼續(xù)進(jìn)行分配，將已經(jīng)分配滿的站點(diǎn)置為re tj=1.并選取其他站點(diǎn)繼續(xù)分配.

(3) 當(dāng)分配任務(wù)搜尋結(jié)束后，所有站點(diǎn)均無(wú)法滿足分配任務(wù)，則置ptn為1；若調(diào)度任務(wù)成功完成，則置ptn為0.

對(duì)于通過(guò)共享單車進(jìn)行異地取車也做如上處理，以上部分完成.

1.2.3調(diào)度最終分配及車輛終值

在完成調(diào)度任務(wù)后需要重新計(jì)算站點(diǎn)的實(shí)時(shí)可用車輛數(shù)目，同時(shí)對(duì)于無(wú)法滿足調(diào)度任務(wù)的站點(diǎn)的用戶取、還車請(qǐng)求部分予以拒絕.計(jì)算得Xtn的值.

以stn=2、ptn≠1為例，有

(5)

式中：Ytin為用戶由i站點(diǎn)通過(guò)共享單車取車至n站點(diǎn)的數(shù)量.

不同的stn值與不同的ptn值所獲得的Xb tn計(jì)算公式不同.系統(tǒng)通過(guò)判斷不同站點(diǎn)的狀態(tài)后對(duì)用戶進(jìn)行引導(dǎo)，用戶異地取、還車率受到價(jià)格優(yōu)惠和站點(diǎn)狀態(tài)的影響，在進(jìn)行用戶自適應(yīng)調(diào)度后，站點(diǎn)的可用車輛數(shù)將重新計(jì)算.

1.2.4調(diào)度成本計(jì)算

若Xb tn>ppark，則拒絕還車數(shù)為

rref tn=Xb tn-ppark

(6)

若Xb tn<0，則拒絕取車數(shù)為

rreb tn=-Xb tn

(7)

公式(6)、(7)是當(dāng)周圍站點(diǎn)無(wú)法滿足調(diào)度任務(wù)且取、還車需求過(guò)大時(shí)，對(duì)部分用戶的取、還車需求進(jìn)行部分拒絕.當(dāng)車輛超過(guò)可用停車位數(shù)時(shí)，拒絕部分還車需求.當(dāng)車輛低于0值時(shí)，拒絕部分取車需求.

在完成拒絕取、還車計(jì)算后，將最終的可用車輛數(shù)賦值于Xtn中.

1.3 調(diào)度成本函數(shù)及約束條件

優(yōu)化目標(biāo)是企業(yè)的調(diào)度成本最優(yōu).由于考慮了共享汽車和共享單車兩方面調(diào)度函數(shù)的因素，因此需要將共享汽車的調(diào)度成本Ra和共享單車的調(diào)度成本Rb同時(shí)考慮.但若只單純考慮調(diào)度汽車和調(diào)度單車的成本，容易使得閾值趨向于某一極端，可能會(huì)使某些站點(diǎn)長(zhǎng)期處于車輛過(guò)多或無(wú)車可用的情形.因此，拒絕用戶還車的潛在成本損失Rref和拒絕用戶取車的潛在成本損失Rreb被引入.這兩項(xiàng)成本從用戶體驗(yàn)度出發(fā)，能夠?qū)⒕芙^用戶取車的成本和拒絕用戶還車的成本(發(fā)生這一情況說(shuō)明站點(diǎn)的車輛數(shù)處于極端值)考慮進(jìn)來(lái).最終優(yōu)化目標(biāo)函數(shù)如式(8)所示.

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

(8)

(2) 約束條件

sf tn>sb tn

(9)

sf tn≤ppark

(10)

sb tn≥0

(11)

xf n≤ppark

(12)

xf n≥0

(13)

rtn≥xij≥0，且為整數(shù)

(14)

dtn≥yij≥0，且為整數(shù)

(15)

rtn≥atn≥0，且為整數(shù)

(16)

dtn≥btn≥0，且為整數(shù)

(17)

re tn=(0,1), ?n∈N,t∈T

(18)

rb tn=(0,1), ?n∈N,t∈T

(19)

ptn=(0,1), ?n∈N,t∈T

(20)

qtn=(0,1), ?n∈N,t∈T

(21)

0≤α≤1，且α為任意小數(shù)

(22)

0≤β≤1, 且β為任意小數(shù)

(23)

stn=(-2,-1,0,1,2), ?n∈N,t∈T

(24)

約束條件(9)～(11)是閾值約束條件，保證閾值的范圍在0和站點(diǎn)最大停車位數(shù)之間；約束條件(12)、(13)是站點(diǎn)車位初值約束，保證每天站點(diǎn)初始投放車位數(shù)在運(yùn)營(yíng)合理范圍內(nèi)；約束條件(14)～(17)是異地還車任務(wù)分配數(shù)和共享單車異地取車任務(wù)分配數(shù)的約束，其范圍不能超過(guò)實(shí)際用戶取、還車數(shù)量；約束條件(18)～(21)、(24)是狀態(tài)指示符變量約束；約束條件(22)、(23)是選擇率約束，選擇率是與價(jià)格有關(guān)的概率變量，其范圍僅在0～1之間.

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

對(duì)于調(diào)度問(wèn)題的常用解法主要有線性規(guī)劃法和啟發(fā)式算法兩種思路.在調(diào)度問(wèn)題中本文選取了閾值作為主要的未知量進(jìn)行求解，同時(shí)需要對(duì)大量歷史數(shù)據(jù)進(jìn)行仿真模擬.因此采用啟發(fā)式算法中的遺傳算法進(jìn)行求解是合適的.

遺傳算法求解在大規(guī)?？焖龠\(yùn)算上具有明顯優(yōu)勢(shì).該算法最早由美國(guó)J.H.Holland教授提出.該算法是基于生物進(jìn)化理論的自適應(yīng)隨機(jī)搜索算法，對(duì)于求解車輛的調(diào)度問(wèn)題十分有效[15].

問(wèn)題中需要求解的變量數(shù)目為(2t+1)n+2.其中,t是指在進(jìn)行調(diào)度中將1 d劃分的時(shí)間段個(gè)數(shù)，n是指調(diào)度站點(diǎn)的總個(gè)數(shù).由于站點(diǎn)存在上、下兩個(gè)閾值，且存在著多個(gè)時(shí)間段，因此有2tn個(gè)閾值變量需要求解.站點(diǎn)每天需要在初始時(shí)間停放初始車輛，則有n個(gè)站點(diǎn)初值需要求解.由于引入了價(jià)格和選擇率機(jī)制，故需要求解兩個(gè)變量,即共享汽車優(yōu)惠價(jià)格和共享單車優(yōu)惠金額.其需要求解的變量總數(shù)如下式:

(2t+1)n+2=2tn+n+2

(25)

遺傳算法求解的基本步驟為：編碼操作，產(chǎn)生初始種群，計(jì)算適應(yīng)度函數(shù)，遺傳算子(選擇、交叉和變異)，終止規(guī)則.

1.4.1染色體編碼與解碼

本文采用二進(jìn)制編碼對(duì)車輛調(diào)度問(wèn)題進(jìn)行求解.染色體的基因序列h=(A,B1,B2,B3,B4,B5,C1,C2,C3,C4,C5,D0)，由12部分組成，第1部分(A)是車輛的初始投放數(shù)量，第2～6部分(B1至B5)是車輛的各個(gè)時(shí)段的上閾值，第7～11部分(C1至C5)是各個(gè)時(shí)段的下閾值，第12部分(D0)是車輛調(diào)度的優(yōu)惠金額.

1.4.2初始化種群

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

G={g0,g1,…,gn}

1.4.3約束條件與適應(yīng)度

常見(jiàn)約束處理方法有3種：第1種是直接處理約束條件，在編碼過(guò)程中加入約束條件.第2種是計(jì)算過(guò)程中通過(guò)約束條件校驗(yàn).第3種是通過(guò)懲罰函數(shù)處理約束.根據(jù)模型特點(diǎn)，采用直接處理約束的方法.

采用目標(biāo)函數(shù)作為適度函數(shù)，即以調(diào)度成本最優(yōu)為目標(biāo)函數(shù)，作為種群的適應(yīng)度函數(shù)，適應(yīng)度更優(yōu)的種群將有更大的概率繁衍后代.

1.4.4遺傳操作與終止規(guī)則

遺傳算子中包括選擇算子、交叉算子、異變算子.選擇算子是根據(jù)樣本適應(yīng)度大小在已知種群中選擇一定數(shù)量的個(gè)體，算法中使用select高級(jí)選擇算例進(jìn)行種群選擇篩選.交叉算子是通過(guò)給定的概率重組一對(duì)個(gè)體而產(chǎn)生后代.算法使用高級(jí)重組算子(recombin)實(shí)現(xiàn)種群交叉繁衍.變異算子是按照極低的概率對(duì)基因序列的某一位數(shù)進(jìn)行變異，算法使用離散變異算子(mut)產(chǎn)生種群基因突變.最后終止條件可以按迭代次數(shù)終止或按適應(yīng)度變化幅度終止，最終優(yōu)勢(shì)種群(即能夠更好地適應(yīng)環(huán)境的種群)將獲得生存優(yōu)勢(shì)并獲得繁衍機(jī)會(huì).

2 實(shí)例應(yīng)用與分析

2.1 案例概況

數(shù)據(jù)選取上海市EVCARD公司嘉定區(qū)安亭鎮(zhèn)的14個(gè)站點(diǎn)2017年6月所有訂單數(shù)據(jù)進(jìn)行研究，當(dāng)月1～25日的運(yùn)營(yíng)數(shù)據(jù)進(jìn)行啟發(fā)式算法計(jì)算求解，26～30日的數(shù)據(jù)對(duì)模型進(jìn)行驗(yàn)證分析.數(shù)據(jù)主要包括了用戶取車時(shí)間、用戶還車時(shí)間、用戶訂單總金額等.其數(shù)據(jù)格式如表1所示，還車日期為用戶還車的日期，如20170601對(duì)應(yīng)2017年6月1日；用戶取車時(shí)間為用戶取車的時(shí)分秒時(shí)間，如234853對(duì)應(yīng)為23:48:53；還車網(wǎng)點(diǎn)編號(hào)為用戶還車的網(wǎng)店信息，如1對(duì)應(yīng)還車在1號(hào)網(wǎng)點(diǎn).

針對(duì)用戶異地取還車價(jià)格和比例的接受度，本研究通過(guò)針對(duì)嘉定區(qū)403個(gè)消費(fèi)者進(jìn)行問(wèn)卷調(diào)研獲得，其中63%為男性，37%為女性，52%的被調(diào)查者的年齡在20～25歲之間，71%的受訪者均有駕照.獲得汽車異地還車用戶優(yōu)惠價(jià)格e與選擇率α關(guān)系式如下:

α=0.27+0.15 lne

(26)

表1 仿真時(shí)所用數(shù)據(jù)示例Tab.1 Simulation data for this case

由于優(yōu)惠價(jià)格受到具體情況的限制，在實(shí)際過(guò)程中，將共享汽車優(yōu)惠價(jià)格限定在5～15元.對(duì)于共享單車而言，由于單次使用共享單車的費(fèi)用在0.5～1.0元，用戶選擇率在0.4～0.7，對(duì)于共享單車調(diào)度在實(shí)際中處理為共享單車用戶選擇率β=0.5，用戶異地取車補(bǔ)貼優(yōu)惠金g=2元.

對(duì)于拒絕用戶還車單次成本h，共享汽車企業(yè)平均租車價(jià)格為0.6元·min-1，用戶去往下一個(gè)站點(diǎn)還車額外花費(fèi)時(shí)間約為15 min，因此計(jì)h=9元.對(duì)于拒絕用戶取車單次成本k，根據(jù)歷史訂單數(shù)據(jù)可知平均單次用戶使用金額(不包含優(yōu)惠券優(yōu)惠)為31.12元，因此計(jì)k=31.12元.

選擇上海市同濟(jì)大學(xué)嘉定校區(qū)—嘉亭薈等周圍的14個(gè)站點(diǎn)，并進(jìn)行隨機(jī)編號(hào).這14個(gè)站點(diǎn)的最大停車位數(shù)目為11、13、35、10、13、3、6、10、6、6、40、3、10、4.另外需要注意的是，站點(diǎn)之間的距離是共享自行車的騎行時(shí)間距離.這14個(gè)站點(diǎn)之間的騎行時(shí)間矩陣如表2所示.由表2可知，每個(gè)站點(diǎn)周圍至少存在一個(gè)能夠通過(guò)騎行在10 min以內(nèi)到達(dá)的站點(diǎn)，這為用戶自適應(yīng)調(diào)度提供了條件.

表2 各共享站點(diǎn)騎行時(shí)間Tab.2 Cycling time of each station min

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

本文采用MATLAB 2016b編寫(xiě)程序，計(jì)算機(jī)為64位操作系統(tǒng)，處理器為Intel (R)、Core (TM)i7-6700、CPU @ 3.40GHz，安裝內(nèi)存為8.00 GB.

遺傳模型輸入?yún)?shù)如下：遺傳算法種群數(shù)Nind=80；最大種群繁衍數(shù)MAXGEN=800；需要求解的變量維數(shù)NVAR=155；設(shè)定遺傳代溝參數(shù)GGAP=0.9；變異概率Pm=0.01；交叉概率Pc=0.8，采用離散變異，由函數(shù)mut設(shè)定.適應(yīng)度規(guī)則基于秩的適應(yīng)度篩選機(jī)制；選擇規(guī)則采用高級(jí)選擇算子，由函數(shù)select設(shè)定；交叉規(guī)則采用高級(jí)重組算子，由函數(shù)recombin設(shè)定.

將企業(yè)調(diào)度成本與用戶滿意度潛在損失成本合計(jì)最優(yōu)作為目標(biāo)函數(shù)，對(duì)2017年6月份的數(shù)據(jù)進(jìn)行驗(yàn)證分析.種群在經(jīng)過(guò)300次迭代后開(kāi)始收斂，種群的最小值穩(wěn)定在1.2×104范圍，最終輸出站點(diǎn)各個(gè)時(shí)段的上、下閾值，站點(diǎn)初始時(shí)段的最優(yōu)停放車輛數(shù)量，最佳優(yōu)惠價(jià)格等.經(jīng)過(guò)計(jì)算后結(jié)果如表3所示.

由表3可以得出，初始運(yùn)營(yíng)時(shí)間需要安排的最優(yōu)可用車輛數(shù)，不同時(shí)間段上閾值(一定比例的用戶激勵(lì)異地還車)和下閾值(一定比例的用戶激勵(lì)異地取車)，共享汽車優(yōu)惠獎(jiǎng)勵(lì)紅包金額，共享單車優(yōu)惠獎(jiǎng)勵(lì)補(bǔ)貼金額.

2.3 站點(diǎn)驗(yàn)證實(shí)例

通過(guò)對(duì)1～25日的歷史數(shù)據(jù)進(jìn)行遺傳算法的最優(yōu)求解，在結(jié)果驗(yàn)證中調(diào)用26～30日用車訂單數(shù)據(jù).以任意站點(diǎn)的調(diào)度情況為例，圖1給出了站點(diǎn)8在最優(yōu)初始站點(diǎn)值為5輛，最優(yōu)優(yōu)惠價(jià)格為5元的情況下，未進(jìn)行用戶激勵(lì)調(diào)度的可用車輛數(shù)情況.圖中，中橫線為站點(diǎn)停車位數(shù)為0.由圖中可知,站點(diǎn)在將近一半的時(shí)間內(nèi)均處于車位未能滿足需求的情況，特別是在用車高峰的10：00之后.其負(fù)值產(chǎn)生的原因是因?yàn)檫@是在未進(jìn)行任何人工調(diào)度與用戶自適應(yīng)調(diào)度的情況下產(chǎn)生的，實(shí)際工作中不產(chǎn)生負(fù)值是因?yàn)橛腥斯ふ{(diào)度員的參與和調(diào)度.

圖2是進(jìn)行人工調(diào)度后的8號(hào)站點(diǎn)變化情況.其中,最上端橫線是最大停車位數(shù)目,為10輛;最下端橫線是可用車輛數(shù),為0;中間橫線為各時(shí)段上、下閾值，粗實(shí)線為站點(diǎn)可用車輛數(shù).

由圖2可知，站點(diǎn)的初始停車位最優(yōu)解為5輛，并且站點(diǎn)在各個(gè)時(shí)間段的可用車輛數(shù)上、下閾值分別為：6:00～11:00，[6,3]；11:00～14:00，[8,4]；14:00～17:00，[8,5]；17:00～21:00，[10,2]；21:00～24:00，[6,2]；24:00～6:00為車輛停運(yùn)時(shí)間，進(jìn)行車輛的整備和調(diào)整.在進(jìn)行聯(lián)合調(diào)度后，可用車輛數(shù)長(zhǎng)期處于可用范圍內(nèi).能夠充分滿足用戶的取還車需求.

表3 遺傳算法給出的站點(diǎn)初值、上下閾值及優(yōu)惠金額Tab.3 Initial value of site, upper and lower threshold, and discount price, calculated by the genetic algorithm

圖1 站點(diǎn)8未采用用戶激勵(lì)調(diào)度可用車輛數(shù)Fig.1 Available vehicle number without user incentive relocation at NO.8 site

圖2 站點(diǎn)8采用用戶激勵(lì)調(diào)度可用車輛數(shù)Fig.2 Available vehicle number with user incentive relocation at NO.8 site

由于在調(diào)度過(guò)程中，不能僅僅關(guān)注可用車輛數(shù)目和調(diào)度成本，更應(yīng)該關(guān)注用戶的使用體驗(yàn).如果某一站點(diǎn)的車輛長(zhǎng)期處于0以下或者滿載狀態(tài)，則會(huì)影響到用戶的取、還車體驗(yàn).在這種情況下，可能會(huì)出現(xiàn)拒絕用戶取車、還車訂單的問(wèn)題，這一比例應(yīng)該盡可能降低.

圖3給出了1～25日的允許用戶還車訂單比例、允許用戶取車比例，以及總體允許用戶取、還車比例.相關(guān)數(shù)據(jù)結(jié)果表明，用戶平均取車訂單成功率高于99.5%，峰值取車訂單成功率不低于95%；用戶平均還車訂單成功率高于99.7%，峰值還車訂單成功率不低于95%；總體用戶取、還車成功率比例不低于99.4%，峰值用戶取還車成功率不低于95%.結(jié)果表明，激勵(lì)調(diào)度模型能夠在保證各個(gè)站點(diǎn)良好有序運(yùn)行的基礎(chǔ)上，具有良好的用戶取車體驗(yàn)和還車體驗(yàn).

a 允許用戶還車訂單比例

b 允許用戶取車訂單比例

c 允許用戶取、還車訂單比例圖3 用戶訂單成功率Fig.3 Success rate of user order

2.4 調(diào)度成本分析

成本及利潤(rùn)是企業(yè)最需要考量的指標(biāo).本節(jié)將人工調(diào)度成本定為傳統(tǒng)共享車輛企業(yè)通過(guò)員工調(diào)度所產(chǎn)生的成本費(fèi)用，用戶激勵(lì)調(diào)度成本定為采用用戶自適應(yīng)調(diào)度所產(chǎn)生的成本費(fèi)用.其中人工調(diào)度成本按上海市平均工資的工作時(shí)間進(jìn)行計(jì)算.

圖4為總共14個(gè)站點(diǎn)在第28日的采用員工調(diào)度和用戶激勵(lì)調(diào)度的成本比較圖.由圖可知，在大部分時(shí)間內(nèi)，用戶激勵(lì)調(diào)度所用成本遠(yuǎn)低于員工調(diào)度，僅在某些用車高峰時(shí)段成本略高于員工調(diào)度.但是調(diào)度的靈活性是員工調(diào)度難以媲美的.

圖4 14個(gè)站點(diǎn)的員工調(diào)度-用戶激勵(lì)調(diào)度成本對(duì)比圖Fig.4 Cost contrast figure of stuff relocation and user relocation

經(jīng)過(guò)計(jì)算，采用用戶激勵(lì)調(diào)度，調(diào)度成本僅占人工調(diào)度的30%～40%.表4給出了6月26日～30日的占比計(jì)算結(jié)果，表明基于共享汽車和共享單車的聯(lián)合調(diào)度作為一種用戶激勵(lì)的自適應(yīng)調(diào)度手段，不僅可以快速獲取用戶需求并通過(guò)動(dòng)態(tài)調(diào)度提升用戶的消費(fèi)體驗(yàn)，還能進(jìn)一步降低企業(yè)成本，提升企業(yè)利潤(rùn).

表4 用戶激勵(lì)調(diào)度所占人工調(diào)度成本的比例Tab.4 Cost ratio of user incentive relocation to stuff relocation

3 結(jié)論與展望

本文建立了基于用戶激勵(lì)的自適應(yīng)調(diào)度模型，考慮將共享單車與價(jià)格調(diào)節(jié)引入電動(dòng)汽車調(diào)度中.通過(guò)獲取用戶調(diào)研和企業(yè)實(shí)際取、還車數(shù)據(jù)，建立基于用戶激勵(lì)的電動(dòng)汽車共享調(diào)度成本優(yōu)化模型，并用遺傳算法進(jìn)行仿真求解.求解結(jié)果得到站點(diǎn)初值汽車配置數(shù)、各時(shí)段可變閾值與最優(yōu)價(jià)格優(yōu)惠值，并對(duì)模型結(jié)果進(jìn)行驗(yàn)證與分析，主要得到以下成果：

(1) 通過(guò)本研究，提出了共享汽車價(jià)格優(yōu)惠和共享單車價(jià)格激勵(lì)的自適應(yīng)聯(lián)合調(diào)度模型，并通過(guò)遺傳算法求解該問(wèn)題，設(shè)計(jì)算法流程與思路.

(2) 對(duì)EVCARD電動(dòng)汽車共享公司14個(gè)站點(diǎn)的實(shí)際1個(gè)月運(yùn)營(yíng)數(shù)據(jù)進(jìn)行驗(yàn)證表明，采用用戶激勵(lì)的自適應(yīng)調(diào)度能夠明顯提高運(yùn)營(yíng)公司的收益及車輛利用率，節(jié)約成本并提高用戶滿意度.

(3) 采用分時(shí)段的閾值能夠有效平滑峰谷問(wèn)題.由于用戶取還車需求在時(shí)間-空間上具有短時(shí)間周期的不確定性和長(zhǎng)時(shí)間周期的潮汐現(xiàn)象，因此采用分時(shí)段可變閾值能夠有效預(yù)測(cè)和調(diào)配車輛，實(shí)現(xiàn)平滑過(guò)渡峰谷.

(4) 企業(yè)可以定制針對(duì)性的優(yōu)惠價(jià)格策略，在提升用戶滿意度的同時(shí)實(shí)現(xiàn)車輛調(diào)度成本最優(yōu).本例中最優(yōu)優(yōu)惠價(jià)格為5元，企業(yè)可以根據(jù)自身情況和相關(guān)實(shí)踐進(jìn)行調(diào)整，實(shí)現(xiàn)企業(yè)利潤(rùn)和用戶滿意度之間的平衡.