離散差分進(jìn)化算法求解共享單車調(diào)度問題

汪慎文 ， 楊 鋒， 徐 亮， 李美羽

(1.河北地質(zhì)大學(xué) 信息工程學(xué)院，河北 石家莊 050031； 2.河北地質(zhì)大學(xué) 人工智能與機(jī)器學(xué)習(xí)研究室，河北 石家莊 050031； 3.北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044)

0 引言

作為共享經(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ù)水平.

1 離散差分進(jìn)化算法原理及步驟

1.1 離散差分進(jìn)化算法原理

離散差分進(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ǔ)操作.

1.2 個(gè)體編碼設(shè)計(jì)

考慮到所使用的區(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í)間最小值.

1.3 變異操作設(shè)計(jì)

與傳統(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

1.4 修補(bǔ)算子設(shè)計(jì)

相比其他優(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

1.5 DDE算法流程

通過以上對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.

2 共享單車調(diào)度模型

2.1 問題描述

通常，在早高峰期，居住區(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ù)量.

2.2 調(diào)度過程

調(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

2.3 調(diào)度規(guī)則

當(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)

3 實(shí)驗(yàn)及結(jié)果

3.1 參數(shù)設(shè)置

總調(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)完成.

3.2 實(shí)驗(yàn)結(jié)果及分析

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

3.3 與其他算法對比

(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

4 結(jié)論

筆者針對共享單車調(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í)生活.