基于快速非支配排序遺傳算法的共享電單車(chē)歸還策略

王 丹, 韓豐元

(沈陽(yáng)大學(xué) 裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室, 遼寧 沈陽(yáng) 110044)

共享電單車(chē)比普通的自行車(chē)更加快捷省力,騎行體驗(yàn)更加舒適,是城市公共交通系統(tǒng)中重要的一環(huán)。相比其他交通工具而言,最后一公里問(wèn)題得到了完美的解決。近幾年,由于環(huán)境保護(hù)和健康意識(shí)的普及,低碳交通成為了當(dāng)前城市交通系統(tǒng)中的主題,這使得公共交通系統(tǒng)有了巨大的改變,共享電單車(chē)不但緩解了公交車(chē)擁擠的壓力,還使得城市的經(jīng)濟(jì)發(fā)展享受了共享概念的紅利[1]。 然而,共享電單車(chē)在給人們帶來(lái)便利的同時(shí),也因?yàn)檫^(guò)于飽和,給人行道帶來(lái)?yè)矶?嚴(yán)重侵占了城市公共空間,給市政管理和運(yùn)營(yíng)商管理帶來(lái)巨大壓力[2]。有些區(qū)域供給不足導(dǎo)致行人需要花費(fèi)大量時(shí)間找車(chē),有時(shí)由于距離過(guò)遠(yuǎn),剛到達(dá)地圖上顯示的共享電單車(chē)位置,卻發(fā)現(xiàn)車(chē)已被人占用。當(dāng)前調(diào)度方法主要是人工調(diào)度,運(yùn)營(yíng)商雇傭調(diào)度車(chē)進(jìn)行統(tǒng)一的調(diào)度,花費(fèi)大量的人力物力成本,效果差且維持時(shí)間短[3]。

本文主要將共享電單車(chē)歸還問(wèn)題作為研究對(duì)象,通過(guò)預(yù)測(cè)區(qū)域內(nèi)共享電單車(chē)區(qū)域性需求給出相應(yīng)停車(chē)方案[4]。與以往的共享電單車(chē)調(diào)度方案入手角度不同,希望從用戶的角度,采用快速非支配排序遺傳算法(NSGA-Ⅱ)構(gòu)建共享電單車(chē)合理歸還模型[5]。在歸還共享電單車(chē)時(shí)設(shè)計(jì)出1套合理的停車(chē)點(diǎn)推薦方案。使得共享電單車(chē)的飽和問(wèn)題與供給不均的問(wèn)題得到持續(xù)有效解決,促進(jìn)城市的公共交通系統(tǒng)長(zhǎng)久健康發(fā)展。

1 基于多目標(biāo)優(yōu)化模型的共享電單車(chē)歸還模型建立

多目標(biāo)優(yōu)化是多個(gè)目標(biāo)函數(shù)一同優(yōu)化的問(wèn)題,在多限制條件領(lǐng)域廣泛使用。以往的共享電單車(chē)調(diào)度方法通常是運(yùn)營(yíng)商調(diào)用調(diào)度車(chē)進(jìn)行大量的城市統(tǒng)一調(diào)度,這種調(diào)度方式不但要耗費(fèi)大量成本,而且維護(hù)效果持續(xù)時(shí)間短[6]。本文從用戶的角度入手,在根源上解決問(wèn)題。

根據(jù)模型所需參數(shù)的特點(diǎn),針對(duì)運(yùn)營(yíng)商的需求與用戶的體驗(yàn)感,做出以下假設(shè):

1) 人們步行的速度v0保持恒定,共享電單車(chē)的行駛速度v1保持恒定,用戶類(lèi)別具有普遍性;

2) 研究范圍僅為特定時(shí)間段內(nèi)的區(qū)域性研究。用戶每日騎行習(xí)慣不變,目的地不會(huì)改變;

3) 共享電單車(chē)整體運(yùn)營(yíng)正常,每輛共享電單車(chē)都可以正常使用,并且電量滿足用戶騎行至目的地;

4) 每個(gè)停車(chē)點(diǎn)有容量上限,超過(guò)停車(chē)點(diǎn)最大容量時(shí),將產(chǎn)生懲罰成本;

5) 客戶在尋找電單車(chē)時(shí),加入決策范圍的概念,在超出用戶所能接受的尋找范圍時(shí),用戶將放棄繼續(xù)尋找,尋找范圍的半徑為固定值,并且假定所有用戶相同;

6) 在計(jì)算停車(chē)點(diǎn)與目的地之間的初始距離時(shí),不將停車(chē)點(diǎn)的區(qū)域面積算在內(nèi),停車(chē)點(diǎn)僅視為一個(gè)中心點(diǎn)作為研究對(duì)象。

基于上述模型假設(shè),建立以下數(shù)學(xué)模型:

在該模型中:

G——?dú)w還產(chǎn)生的代價(jià)值;

K——區(qū)域供給平衡性;

μ——用戶決策系數(shù);

θ——道路非直線平均系數(shù);

v1——騎行速度;

v0——步行速度;

Y——單位超量所產(chǎn)生的費(fèi)用;

Qj——當(dāng)前區(qū)域所有停車(chē)點(diǎn)最大容量;

H——當(dāng)前區(qū)域容量是否超標(biāo);

Mj——當(dāng)前區(qū)域停車(chē)數(shù)量;

Cj——當(dāng)前進(jìn)入?yún)^(qū)域的電單車(chē)數(shù)量;

L——當(dāng)前區(qū)域共享電單車(chē)的最佳數(shù)量。

式(1)表示這個(gè)區(qū)域一段時(shí)間內(nèi)所有用戶要花費(fèi)的總時(shí)間代價(jià),式(2)表示當(dāng)前區(qū)域停車(chē)點(diǎn)飽和度達(dá)到最優(yōu)的容量大小[7]。

本文優(yōu)化目標(biāo)是通過(guò)對(duì)用戶騎行到停車(chē)點(diǎn)距離x1,停車(chē)點(diǎn)步行到目的地距離x2,一定時(shí)間內(nèi)進(jìn)入?yún)^(qū)域的單車(chē)數(shù)量x3,用戶愿意聽(tīng)從選擇的概率系數(shù)x4,共4個(gè)隨機(jī)變量[8],得出歸還代價(jià)值最小和區(qū)域性供給不平衡性最小,即:

式中,N為正整數(shù)。

以上得出的多目標(biāo)規(guī)劃模型是一個(gè)非線性模型,僅適用于用戶騎行出行的共享電單車(chē)歸還分配研究,為得出最終研究結(jié)果,需要將多目標(biāo)模型轉(zhuǎn)化為單目標(biāo)模型,轉(zhuǎn)化完如式(5),

minF=λ1K(x)+λ2G(x)。

(5)

式中:F為最優(yōu)水平接觸值;λ1、λ2為各目標(biāo)大于0的權(quán)重系數(shù),且滿足λ1+λ2=1。

2 NSGA-Ⅱ算法的雙目標(biāo)優(yōu)化及決策過(guò)程

本文優(yōu)化目標(biāo)函數(shù)G(x1,x2,x3,x4)和K(x1,x2,x3,x4)為加權(quán)均衡值,兩者無(wú)法一同達(dá)到最小值。所以,F不存在同時(shí)最優(yōu)的2個(gè)目標(biāo)解,只能通過(guò)以下步驟得出2個(gè)優(yōu)化目標(biāo)均衡的解集[9]。

1) 求出帕累托最優(yōu)解集;

2) 將解集中的全部元素進(jìn)行評(píng)選的結(jié)果對(duì)比,分別從達(dá)到最優(yōu)水平的帕累托解集中選出與對(duì)應(yīng)的2個(gè)目標(biāo)函數(shù)的解。

目前帶有快速非支配多目標(biāo)優(yōu)化算法有著特殊的精英保留策略,是一種基于帕累托最優(yōu)解的多目標(biāo)優(yōu)化算法,其算法計(jì)算量大。NSGA-II算法使用了快速非支配排序法,將算法的計(jì)算復(fù)雜度由O(mN3)降到了O(mN2),使得算法的計(jì)算時(shí)間大大減少。具體優(yōu)化過(guò)程如圖1所示。

圖1 NSGA-II遺傳算法優(yōu)化過(guò)程Fig.1 NSGA-II genetic algorithm optimization process

由于本文的調(diào)度方案是從用戶的角度入手,歸還點(diǎn)分配選擇中的目標(biāo)優(yōu)化涉及到用戶的自行判斷,而另一個(gè)要優(yōu)化的目標(biāo)則涉及到運(yùn)營(yíng)商考慮的成本問(wèn)題,兩者要考慮的主觀因素占比高,所以,基于優(yōu)化目標(biāo)的特性來(lái)評(píng)估2個(gè)目標(biāo)時(shí),其重要性的大小是關(guān)鍵指標(biāo)[10]。基于COWA算子算出的評(píng)估指標(biāo)的客觀比重,繼而利用博弈論來(lái)組合,修改主觀權(quán)重,進(jìn)而得出的綜合比重會(huì)大幅度削弱最優(yōu)解集中不可靠的解對(duì)客觀權(quán)比的影響[11]。最后利用熵權(quán)法對(duì)解集的各個(gè)元素進(jìn)行評(píng)價(jià)。具體的決策過(guò)程如下:

1) 主觀權(quán)重βn的計(jì)算(專(zhuān)家打分法)。

(6)

式中,Aan為專(zhuān)家a對(duì)指標(biāo)n進(jìn)行評(píng)估[12]。

2) 從最優(yōu)解集的元素i中選出2個(gè)目標(biāo)函數(shù)作為評(píng)估指標(biāo),進(jìn)而得出指標(biāo)矩陣S。

S=(smn)i*2(m=1,2,…,i;n=1,2)。

(7)

3) 將各個(gè)元素進(jìn)行標(biāo)準(zhǔn)化。

(8)

式中,smax為每列的最大元素。

(11)

6) 權(quán)重矩陣D(每個(gè)解都被賦權(quán))。

D=(dmn)t×2(m=1,2,…,t;n=1,2)。

(12)

9) 解出接近最優(yōu)水平指數(shù)Dm,從大到小進(jìn)行排列。

(17)

3 優(yōu)化及決策結(jié)果分析

通過(guò)MATLAB編程對(duì)前文所構(gòu)建的共享電單車(chē)歸還模型進(jìn)行編碼求解。參數(shù)設(shè)定為初始種群300代,迭代次數(shù)為500,如圖2所示。

圖2 帕累托最優(yōu)解集結(jié)果Fig.2 Pareto optimal solution set results

10位專(zhuān)家對(duì)歸還共享電單車(chē)代價(jià)G和區(qū)域供給平衡性K2個(gè)指標(biāo)的重要性進(jìn)行打分(相當(dāng)重要為5分,重要為4分,比較重要為3分,一般重要為2分,不重要為1分),分?jǐn)?shù)見(jiàn)表1。

表1 專(zhuān)家對(duì)2個(gè)指標(biāo)的打分Table 1 Experts’ scores on the two indicators

利用式(6)計(jì)算得到共享電單車(chē)歸還代價(jià)值G和區(qū)域供給平衡性K2個(gè)指標(biāo)的主觀權(quán)重分別是0.445 8與0.554 2。利用式(9)計(jì)算得到共享電單車(chē)歸還代價(jià)值G和區(qū)域供給平衡性K的客觀權(quán)重為0.706 6和0.293 4。其線性組合的系數(shù)為0.656 6和0.343 4,進(jìn)而根據(jù)式(12)在得到了線性組合的系數(shù)后,計(jì)算出綜合權(quán)重分別為0.587 7和0.412 3。

得到以上權(quán)重后,利用熵權(quán)法組合評(píng)估,進(jìn)而得出解集中排名前10的解,見(jiàn)表2。

表2 評(píng)估出最優(yōu)解集中排名前 10 的解Table 2 Top 10 solutions of Pareto optimal solution set obtained by decision

由于要與普通方案進(jìn)行對(duì)比,所以要控制變量。即2種方案用戶騎行到停車(chē)點(diǎn)的距離一致,由于普通方案的優(yōu)化目標(biāo)只有距離最短,導(dǎo)致優(yōu)化方案與普通方案選擇的停車(chē)點(diǎn)不一樣。所以,通過(guò)對(duì)比普通方案選擇的停車(chē)點(diǎn)下的最優(yōu)水平接近值,來(lái)驗(yàn)證優(yōu)化方案是否可行、有效,結(jié)果見(jiàn)表3,普通方案選擇優(yōu)化方案帕累托前10的解的初始距離直接進(jìn)行比照。

表3 對(duì)比普通方案與優(yōu)化方案最優(yōu)水平接近值Table 3 Comparison of approximate value of the optimal level between the general and the optimization

通過(guò)對(duì)比帕累托前10組數(shù)據(jù),普通方案的最優(yōu)水平接近值總和為4.462 3,優(yōu)化后的方案10組最優(yōu)水平接近值總和為7.166 3,優(yōu)化后的方案最優(yōu)水平指數(shù)增加了60.9%,證明優(yōu)化方案推薦的停車(chē)點(diǎn)位置使得這段時(shí)間區(qū)域內(nèi)的最優(yōu)水平指數(shù)大幅度增加,在平衡了區(qū)域的供給性的同時(shí)又減少了停車(chē)點(diǎn)的飽和度,驗(yàn)證了優(yōu)化后的方案有效可行。

4 結(jié) 論

本文基于多目標(biāo)規(guī)劃模型構(gòu)建了平衡狀態(tài)下的共享電單車(chē)歸還模型,同時(shí)分析了優(yōu)化目標(biāo)的有效性。并用NSGA-II確定最平衡狀態(tài)下的歸還點(diǎn)分配,基于熵權(quán)法與博弈論的組合來(lái)求出多目標(biāo)權(quán)重比,再結(jié)合專(zhuān)家打分法從帕累托解集中得出有利的方案。通過(guò)對(duì)比普通方案的歸還點(diǎn)分配下的代價(jià)值,來(lái)驗(yàn)證實(shí)驗(yàn)結(jié)果的有效性,可以有效解決共享電單車(chē)停車(chē)點(diǎn)飽和與區(qū)域性供給不平衡問(wèn)題。