汪慎文 , 楊 鋒, 徐 亮, 李美羽
(1.河北地質(zhì)大學(xué) 信息工程學(xué)院,河北 石家莊 050031; 2.河北地質(zhì)大學(xué) 人工智能與機(jī)器學(xué)習(xí)研究室,河北 石家莊 050031; 3.北京交通大學(xué) 交通運(yùn)輸學(xué)院,北京 100044)
作為共享經(jīng)濟(jì)的一種新形態(tài),共享單車不僅解決了市民“最后一公里”出行的問題[1],更以無樁、便捷等優(yōu)勢,在一定程度上改變了人們的出行方式,緩解了城市交通擁堵.但是,由于在高峰時(shí)段,公司、居民區(qū)等客流量高發(fā)區(qū)域的潮汐現(xiàn)象[2],容易出現(xiàn)共享單車的積聚或者短缺問題,因此需要快速構(gòu)建出一種最佳的共享單車的調(diào)度方案,對共享單車進(jìn)行調(diào)度.共享單車調(diào)度[2]是根據(jù)整個(gè)區(qū)域的單車分布情況以及各區(qū)域的需求信息,依靠調(diào)度算法來使得整個(gè)區(qū)域的單車數(shù)目趨向于合理,即將共享單車從積聚區(qū)域及時(shí)運(yùn)送到短缺區(qū)域.既不會(huì)因?yàn)閱诬嚨倪^多聚集而影響其他交通方式,也不會(huì)因?yàn)槿鄙賳诬嚩鴮?dǎo)致人們的出行困難,是一個(gè)將整個(gè)區(qū)域的共享單車數(shù)量和布局進(jìn)行調(diào)整的過程.良好的調(diào)度算法不僅能夠使共享單車調(diào)度體系正常運(yùn)轉(zhuǎn),同時(shí)也能有效提升整個(gè)共享單車系統(tǒng)的服務(wù)水平.
離散差分進(jìn)化算法[3-4](discrete differential evolution, DDE)框架與傳統(tǒng)的進(jìn)化算法[5](differential evolution, DE)相同,首先在問題的定義域內(nèi)隨機(jī)產(chǎn)生第0代種群作為初始種群[6];然后通過將每一個(gè)個(gè)體進(jìn)行變異,變異的方式為在每一個(gè)個(gè)體上加上或者減去隨機(jī)兩個(gè)個(gè)體的差分量的縮放值,并將此個(gè)體作為變異個(gè)體,如有非法解則需要進(jìn)行修補(bǔ);然后對此變異個(gè)體與當(dāng)前個(gè)體進(jìn)行雜交操作,生成實(shí)驗(yàn)個(gè)體;最后將實(shí)驗(yàn)個(gè)體與當(dāng)前個(gè)體進(jìn)行競爭,較優(yōu)者保留下來[7].通過迭代,逐漸將種群引導(dǎo)到最優(yōu)解位置.主要步驟如圖1所示[8].
圖1 DDE算法主要步驟Fig.1 Main steps of DDE algorithms
不同之處在于,將其個(gè)體編碼、變異算子和修補(bǔ)算子重新設(shè)計(jì),使其適合求解共享單車調(diào)度問題.每個(gè)區(qū)域的編號作為每個(gè)個(gè)體的元素,將傳統(tǒng)變異算子改造成可以進(jìn)行離散變異的變異算子,同時(shí),一旦產(chǎn)生非法解,則進(jìn)行修補(bǔ)操作.
考慮到所使用的區(qū)域編號為整數(shù),筆者擬采用整數(shù)進(jìn)行個(gè)體編碼[9].
每條可行線路編碼成長度為l的個(gè)體{x1,1(G),x1,2(G),…,x1,l(G)},其中,xi,k(G)表示第G代種群中的第i個(gè)個(gè)體的第k個(gè)分量.其中,分量表示的是區(qū)域的編號.如個(gè)體為5→2→3→4→2→5→3表示從配送中心1出發(fā),最后又返回配送中心1的一條調(diào)度路線.個(gè)體編碼長度l由式(1)表示.
(1)
式中:T表示整個(gè)高峰期的時(shí)間;shortest(u,v)表示任兩區(qū)域之間通行時(shí)間最小值.
與傳統(tǒng)的差分進(jìn)化算法的變異操作不同,本文設(shè)計(jì)的簡單的變異算子如下[8].
vi(G)=xr1+F(xr2(G)-xr3(G)),
(2)
式中:F為縮放因子且F∈{1,2,…,n}.在本實(shí)例中,選取F=1,示意圖如圖2所示[10].
圖2 變異操作示例圖Fig.2 Variation operation diagram
相比其他優(yōu)化問題,共享單車調(diào)度問題對解的限制有所不同[2]:①相鄰兩個(gè)變量不能相同;②個(gè)體中的每一維取值都必須在區(qū)域列表中.因此,修補(bǔ)操作設(shè)計(jì)步驟如下.
輸入:item為個(gè)體,n為染色體個(gè)數(shù),Rlower為定義域下界,Rupper為定義域上界
1:function REPAIR(item,n,Rlower,Rupper)
2: fori=1→ndo
3:item[i]←(item[i]-Rlower) mod (Rupper-Rlower+1)+Rlower
4: end for
5: fori=2→n-1 do
6: whileitem[i]=item[i-1] oritem[i]=item[i+1] do
7:item[i]=Random(Rlower,Rupper)
8: end while
9: end for
10: returnitem
11:end function
通過以上對DDE算法各個(gè)操作的描述,DDE算法的流程如下.
步驟1 初始化:確定編碼方式后,選擇合適的種群大小,種群規(guī)模、CR、F值,種群代數(shù)G=0,初始化第0代隨機(jī)種群,并計(jì)算每個(gè)個(gè)體的適應(yīng)度值.
步驟2 變異操作:種群代數(shù)G=G+1,根據(jù)新設(shè)計(jì)的變異操作對X(G)中的每個(gè)個(gè)體進(jìn)行變異操作,操作方式如上述變異操作所示.
步驟3 修補(bǔ)操作:根據(jù)新設(shè)計(jì)的修補(bǔ)算子對變異后的每個(gè)個(gè)體進(jìn)行修補(bǔ)操作,使得每個(gè)個(gè)體能夠滿足之前問題的兩個(gè)限制條件.
步驟4 雜交操作:使用“bin”雜交方式對原本個(gè)體與變異個(gè)體進(jìn)行操作,生成實(shí)驗(yàn)個(gè)體.
步驟5 選擇操作:通過新設(shè)計(jì)的適應(yīng)度函數(shù),選擇適應(yīng)度值更大的個(gè)體,從而得到下一代種群.
步驟6 中止判斷:如果條件滿足,則中止當(dāng)前算法執(zhí)行,并輸出最優(yōu)路徑,否則,轉(zhuǎn)步驟2.
通常,在早高峰期,居住區(qū)域?qū)蚕韱诬囆枨罅枯^大,工作區(qū)域則單車到達(dá)量較多;在晚高峰期則相反.這種出行量和到達(dá)量的差異決定了各區(qū)域存在調(diào)度需求,具體來看,這種需求分為兩種[2]:調(diào)入需求和調(diào)出需求.因此共享單車的調(diào)度問題可描述為:在早晚高峰期,存在一定數(shù)量具有調(diào)度需求的區(qū)域,從調(diào)度中心出發(fā)的一輛調(diào)度車在已知各區(qū)域位置、區(qū)域單車分布、調(diào)度車容量、各區(qū)域租還速率等信息,要求在一定的約束條件下,完成調(diào)度區(qū)域間的單車調(diào)度,計(jì)算出調(diào)度路線和各區(qū)域的調(diào)度車輛數(shù)量.
調(diào)度區(qū)域分為3種類型:調(diào)度中心、出行區(qū)域以及到達(dá)區(qū)域.調(diào)度中心無法存放單車,也無單車調(diào)度需求,t=0時(shí)刻調(diào)度車從調(diào)度中心空車出發(fā),前往各個(gè)區(qū)域進(jìn)行調(diào)度;出行區(qū)域的單車數(shù)量會(huì)隨時(shí)間均勻減少,當(dāng)調(diào)度車抵達(dá)出行區(qū)域時(shí),按照一定的調(diào)度規(guī)則卸下一定數(shù)量的單車;到達(dá)區(qū)域的單車數(shù)量會(huì)隨時(shí)間均勻增多,當(dāng)調(diào)度車抵達(dá)到達(dá)區(qū)域時(shí),按照一定的規(guī)則裝走一定數(shù)量的單車.
如果抵達(dá)某一區(qū)域時(shí)尚未超出調(diào)度時(shí)間段的范圍,則按照一定的調(diào)度規(guī)則完成對該區(qū)域的單車調(diào)度,然后調(diào)度車前往下一區(qū)域;如果超出調(diào)度時(shí)間段的范圍,則終止整個(gè)調(diào)度過程并返回調(diào)度中心.
鑒于主目標(biāo)是滿足用戶需求,所以優(yōu)化目標(biāo)確定為實(shí)現(xiàn)最大限度的調(diào)度量,因?yàn)樵谙到y(tǒng)規(guī)模一定的情況下,經(jīng)過最大量的調(diào)度可實(shí)現(xiàn)較高的利用率,因此調(diào)度目標(biāo)是使在調(diào)度時(shí)間段內(nèi)調(diào)度車的總裝卸量Q盡可能大.
為了表達(dá)更簡潔,本文引入一些符號,其含義如表1所示.
表1 符號說明Tab.1 Symbol declaration
當(dāng)?shù)趈次調(diào)度調(diào)度車抵達(dá)i區(qū)域時(shí),首先計(jì)算i區(qū)域的當(dāng)前單車數(shù)目ni,j,計(jì)算方法為:
(4)
然后計(jì)算i區(qū)域?qū)诬嚨男枨螅?jì)算方法為:
(5)
當(dāng)Bi,j<0時(shí),表示該區(qū)域車輛短缺,需要補(bǔ)充單車.若調(diào)度車上的單車數(shù)量不足以滿足該區(qū)域的需求,則將調(diào)度車上所有車卸下;若調(diào)度車上的車輛足以滿足該區(qū)域的需求,則從調(diào)度車上卸下-Bi,j輛單車,如式(6)所示.
bj=max{-Cj,Bi,j}.
(6)
當(dāng)Bi,j>0時(shí),表示該區(qū)域車輛過剩,需要裝走多余單車.若調(diào)度車上的剩余空間不足,則將調(diào)度車裝滿;若調(diào)度車的剩余空間足夠,則將Bi,j輛單車裝上調(diào)度車,如式(7)所示.
bj=min{C-Cj,Bi,j}.
(7)
總調(diào)度時(shí)間T=60 min,調(diào)度車容量C=20,裝卸一輛單車的時(shí)間td=0.2 min.一共有5個(gè)區(qū)域,區(qū)域1為調(diào)度中心,區(qū)域2、3為出行區(qū)域,區(qū)域4、5為到達(dá)區(qū)域.各個(gè)區(qū)域間的最短通行時(shí)間如表2所示.各區(qū)域的初始車輛變化如表3所示.
表2 各區(qū)域最短通行時(shí)間Tab.2 Shortest passage time between different zones
*注:本文的雙向距離相同
表3 各區(qū)域初始車輛數(shù)和車輛變化Tab.3 The initial number of vehicles and vehicle changes in each zone
設(shè)置種群規(guī)模NP為30,每個(gè)個(gè)體表示一條調(diào)度路徑,維度D設(shè)置為15,縮放因子F為1,雜交概率CR為0.6,迭代次數(shù)為100次.執(zhí)行過程中會(huì)判斷每個(gè)個(gè)體的有效長度,保證調(diào)度路徑可以在規(guī)定時(shí)間內(nèi)完成.
DDE算法收斂曲線如圖3所示.圖3表明,種群在第2代左右得到最優(yōu)解,在50代左右所有個(gè)體收斂到最優(yōu)值,最終平均調(diào)度量為85.9,收斂速度較快.
最優(yōu)的調(diào)度路線、調(diào)度車輛數(shù)量和調(diào)度時(shí)間節(jié)點(diǎn)如表4所示,其中,調(diào)度順序?yàn)檎{(diào)度次數(shù),
圖3 DDE算法收斂曲線圖Fig.3 The convergence curve of DDE algorithm
0表示初始狀態(tài),區(qū)域編號為當(dāng)前調(diào)度次數(shù)下調(diào)度車輛所在的區(qū)域,調(diào)度量為此次調(diào)度下調(diào)度車輛的裝卸量,正數(shù)表示裝車,負(fù)數(shù)表示卸車,總調(diào)度量表示截至當(dāng)前次數(shù)下已經(jīng)調(diào)度的車輛總和,包括裝車和卸車,最終得到的路徑為1→5→2→4→3→2→4→5→1,總調(diào)度量Q=86.
DDE算法得到的解所模擬的調(diào)度過程如圖4所示.其中,紅色方框表示每一時(shí)刻小車所在的區(qū)域,方框內(nèi)的數(shù)表示當(dāng)前時(shí)刻調(diào)度車輛的裝載量.紅色線段表示調(diào)度車輛的路徑變化,即行駛路徑.其中左上角圖例中的ni,j和Bi,j的含義與表1中的變量說明一致.每個(gè)子圖下方標(biāo)示了該子圖所處的時(shí)間點(diǎn)t和總調(diào)度量Q.該圖的每一張子圖都為一個(gè)時(shí)間點(diǎn),如第一張子圖表示初始狀態(tài),當(dāng)前時(shí)刻t=0,總調(diào)度量Q=0,調(diào)度車輛當(dāng)前所處的區(qū)域?yàn)檎{(diào)度中心1,每個(gè)區(qū)域的當(dāng)前單車數(shù)目ni,j和需求量Bi,j在其下方顯示.
表4 DDE算法調(diào)度過程Tab.4 The scheduling process of DDE algorithm
(1) 應(yīng)用貪心算法,貪心策略為每次選擇使單位時(shí)間調(diào)度數(shù)量最大的區(qū)域作為前往的下一個(gè)區(qū)域,所得結(jié)果如表5所示,最終的調(diào)度量Q=84.
表5 貪心算法調(diào)度過程Tab.5 The scheduling process of greedy algorithm
(2) 應(yīng)用蟻群算法[11],重復(fù)運(yùn)行50次,所得解的平均質(zhì)量同DDE算法的對比如表6所示;其中兩種算法一次運(yùn)行的情況對比如圖5所示.圖5的橫縱坐標(biāo)以及圖的各項(xiàng)說明與圖4相同.
表6 蟻群算法與DDE算法得到的平均調(diào)度量對比Tab.6 Comparison of average scheduling volume of ant colony optimization and DDE algorithm
圖6表明,在相同的較小規(guī)模問題下,蟻群算法得到的最優(yōu)解與DDE算法相同,但相比蟻群算法,DDE算法得到的解的平均質(zhì)量更高,且收斂速度更快.表6表明,蟻群算法和DDE算法均能穩(wěn)定求解共享單車調(diào)度問題,圖6的情況具有一般性和代表性.
綜合比較之下,DDE算法在這個(gè)問題中具有收斂快、解的質(zhì)量高的優(yōu)點(diǎn).
圖4 DDE算法模擬調(diào)度過程Fig.4 The specific route finding process of DDE algorithm
圖5 蟻群算法與DDE算法收斂曲線對比圖Fig.5 Comparison of convergence curves of ant colony optimization and DDE algorithm
筆者針對共享單車調(diào)度問題,設(shè)計(jì)了相應(yīng)的DDE算法進(jìn)行求解.實(shí)驗(yàn)結(jié)果表明,DDE算法可以穩(wěn)定求解共享單車調(diào)度問題,相比貪心算法和蟻群算法,DDE算法在較小規(guī)模下求解共享單車調(diào)度問題時(shí)解的質(zhì)量更優(yōu)、收斂速度更快.下一步的工作將優(yōu)化本身的調(diào)度模型,并逐步將問題的規(guī)模擴(kuò)大,使得模型更符合現(xiàn)實(shí)生活.