趙紅夢，姜志俠，曾 坤

(長春理工大學(xué) 理學(xué)院，吉林 長春 130022)

0 引 言

隨著中國經(jīng)濟的快速發(fā)展以及居民生活水平的不斷提高，交通擁堵問題日益嚴(yán)重，為了更好地響應(yīng)黨中央綠色出行的號召，緩解城市交通壓力，城市公共自行車應(yīng)運而生。隨著公共自行車的高效發(fā)展，一系列問題也逐漸顯現(xiàn)，如由于調(diào)度不平衡導(dǎo)致租還車難的問題大大降低了用戶對于公共自行車使用的滿意度，對公共自行車進行調(diào)度優(yōu)化的研究迫在眉睫；考慮到車輛的容量要求，如何設(shè)計節(jié)約成本的調(diào)度方案，最大程度地提高市民對公共自行車使用的滿意度是亟待解決的問題。

目前學(xué)者對公共自行車單調(diào)度問題的研究主要分為調(diào)度模型和調(diào)度方法兩大類。2005年任傳祥等[1]提出混合遺傳模擬退火算法解決公交車輛行車計劃模型；2011年Mike Benchimo等[2]重點研究以調(diào)度運輸費用最小為目標(biāo)函數(shù)的車輛靜態(tài)調(diào)度優(yōu)化模型；2013年Daniel Chemla[3]用禁忌搜索算法解決靜態(tài)公共自行車問題；2017年Fábio Cruz等[4]提出一種基于局部迭代的啟發(fā)式算法解決單調(diào)度靜態(tài)無時間窗優(yōu)化模型；同年Aritra Pal[5]等提出了一種求解靜態(tài)完全再平衡問題的混合整數(shù)線性規(guī)劃模型，利用混合嵌套的大鄰域搜索與可變鄰域下降算法解決公共自行車調(diào)度問題；2017年欒英杰[6]提出一種GA-SA算法解決公共自行車調(diào)度問題?；诖?，文中主要研究靜態(tài)公共自行車調(diào)度問題，以成本最小化為目標(biāo)建立調(diào)度模型，并利用改進的遺傳模擬退火算法進行求解。

1 模型建立

文中要研究的單車場無時間窗調(diào)度問題可以描述為:在已知各租賃點之間的距離和調(diào)度需求的前提下，如何合理地安排調(diào)度車的調(diào)度路線，使行駛成本和車輛的固定成本最小。用有向圖G=(N,E)表示公共自行車的調(diào)配網(wǎng)絡(luò)，其中N={0,1,…,n}表示租賃點的集合，0表示調(diào)度中心，n為租賃點數(shù)目，E={(i,j)|i,j∈N,i≠j}表示相連租賃點的邊集;V={1,2,…,K}表示調(diào)度車的集合，K為調(diào)度車輛總數(shù)目；用最大載重量Q的調(diào)度車,從調(diào)度中心出發(fā)，并且最終返回調(diào)度中心;其中租賃點i和租賃點j之間的距離dij和租賃點i的調(diào)度需求qi已知。

C0為調(diào)度車輛的固定成本，C1為單位距離配送費，調(diào)度車輛k被使用時記二進制變量ξk等于1，否則為0；xijk表示車輛路線安排，當(dāng)車輛k在服務(wù)完i后再服務(wù)j時，xijk取1，否則xijk取0。

根據(jù)以上條件建立數(shù)學(xué)模型(PBVSP)：

(1)

(2)

(3)

(4)

(5)

目標(biāo)函數(shù)為成本最小化，成本包括行駛成本和車輛的固定成本，其中約束(1)表示從調(diào)度中心(車場)出來的車輛數(shù)量最大不超過K，約束(2)確保每個路線在調(diào)度中心開始或結(jié)束，約束(3)、(4)表示規(guī)定每個租賃點只能由一輛車進行訪問，約束(5)表示每輛車上自行車的量不大于調(diào)度車輛的容量。

2 算法設(shè)計

遺傳算法[7]具有強大的全局最優(yōu)解搜索能力，并且收斂速度較快[8]，但是存在局部搜索能力差和早熟收斂等問題[9]；模擬退火算法具有擺脫局部最優(yōu)解的能力，但算法運行效率不高，進化速度較慢；文中算法思想是基于這兩種算法的特點，將其結(jié)合使用增強算法運行效率。針對公共自行車單調(diào)度問題(PBVSP)設(shè)計一種GA-SA算法，具體操作流程如下：

2.1 算法的變異操作

在進行染色體變異之前，首先對染色體進行編碼，n個租賃點編碼長度為n，染色體為1至n之間的隨機整數(shù)排列，例如n為6，染色體可能為[1 3 4 5 6 2]。

變異的主要目的是保持群體的多樣性，采用兩兩交換變異的方法，按變異概率pm選擇需要變異的染色體，隨機產(chǎn)生兩個自然數(shù)n1和n2，交換第n1位和第n2位所對應(yīng)的基因。例如n1等于2，n2等于5，初始染色體為[1 6 3 4 5 2]，經(jīng)過變異后的染色體為[1 5 3 4 6 2]。

2.2 算法的交叉操作

文中提出基于經(jīng)典兩點交叉操作方法的三種改進方式，具體如下：

(1)基于關(guān)聯(lián)度的兩點交叉法。

在進行兩點交叉操作之前對其基因間的關(guān)聯(lián)進行判斷，兩個染色體X={x1,x2,…,xn}，Y={y1,y2,…,yn}，xi,yi∈{1,2,…,n}，n為租賃點數(shù)目，引入二進制變量δi。

判斷X,Y之間關(guān)聯(lián)度的公式如下：

(6)

(2)修正重復(fù)元素的兩點交叉法。

兩點交叉首先隨機產(chǎn)生兩個父代染色體，如f1=[1 6 3 4 5 2]，f2=[4 3 2 6 5 1]，隨機產(chǎn)生兩個自然數(shù)n1和n2，對兩個父代染色體n1至n2之間的基因片段進行交換，如n1等于2，n2等于4，得到兩個子個體分別為[1 3 2 6 5 2]，[4 6 3 4 5 1]；對其進行修正：若交叉片段與非交叉片段中出現(xiàn)相同元素，則利用缺失元素去替換交叉部分重復(fù)元素，修正后的染色體為[1 3 4 6 5 2]，[4 6 3 2 5 1]。

(3)基于自適應(yīng)的兩點交叉法。

一般遺傳算法兩點交叉概率pc是設(shè)定好的，基于此，根據(jù)種群適應(yīng)度的情況提出自適應(yīng)交叉法。主要思想是對高適應(yīng)度值的個體降低交叉概率，對較低適應(yīng)度的個體提高交叉概率，以避免發(fā)散和陷入局部最優(yōu)，并保持種群中較好的個體。文中提出自適應(yīng)交叉的公式如下：

(7)

其中，α為自適應(yīng)參數(shù)，fmax為個體最大適應(yīng)度值，favg為個體平均適應(yīng)度值；之后進行經(jīng)典兩點交叉。

2.3 算法的解碼操作

在使用GA-SA算法解決PBVSP問題時，需要對一個編碼F(染色體)進行解碼，以便滿足載重等約束條件，并得到多個子路徑。具體方法見圖1。

圖1 染色體解碼流程

舉例分析，若公共自行車租賃點編碼F為[1 3 4 5 6 2]，第一條路線，嘗試將F中第一個點1加入路線S1，若加入后滿足約束條件，S1變?yōu)镾1=[0 1]，刪除F中的1，將其第二個點3加入S1，若滿足約束，S1=[0 1 3]，否則，開始第二條路線S2，依次類推直到F為空集時終止解碼操作。

染色體進行解碼后，計算適應(yīng)度函數(shù)值，目標(biāo)Z為求最小成本問題，染色體適應(yīng)度函數(shù)設(shè)置為其倒數(shù)，如公式(8)所示。

(8)

2.4 算法的選擇操作

模擬退火算法[10]是一種基于概率的算法，該算法模擬了固體降溫的過程[11]。它的出發(fā)點是結(jié)合物理退火與組合優(yōu)化問題的相似性；基于此，文中將模擬退火算法引入到遺傳算法的選擇之中。

采用經(jīng)典的輪盤賭選擇方法，它是一種基于比例的選擇方法，若某個個體i適應(yīng)度為fi，種群大小為NP，則被選擇的概率如公式(9)：

(9)

個體適應(yīng)度越小，被選擇的機會也就越小，反之亦然。

文中所提出的算法是以遺傳算法為主體，融入模擬退火算法優(yōu)化群體的選擇，算法的具體流程如圖2所示。

圖2 算法流程

3 實例分析

研究的仿真數(shù)據(jù)[12]為紐約市公共自行車系統(tǒng)的運營公開數(shù)據(jù)，Citi Bike NYC網(wǎng)站上公布的紐約市公共自行車出行數(shù)據(jù)中的每個站點對應(yīng)一個ID編號，選擇400～423之間的21個ID號作為租賃點，其中400為調(diào)度中心0。各個租賃點調(diào)度需求與經(jīng)緯度坐標(biāo)見表1，其中正數(shù)表示本租賃點有多余的自行車數(shù)量，負(fù)值表示該租賃點需要供入自行車，調(diào)度車初始裝載量為20。

表1 原始數(shù)據(jù)

首先對參數(shù)進行設(shè)置，調(diào)度車固定成本C0為18，單位距離配送費C1為1，調(diào)度車容量Q為25，調(diào)度車總數(shù)目K為5，遺傳算法種群數(shù)NP為100，遺傳算法迭代次數(shù)maxgen為200，變異概率pm為0.1。

問題要求調(diào)度車從調(diào)度中心出發(fā)去租賃點取送公共自行車，并且最終返回調(diào)度中心。針對文中提出的GA-SA算法對PBVSP問題進行調(diào)度分析，其中交叉操作分別采用三種形式進行計算：基于關(guān)聯(lián)度的兩點交叉法、修正重復(fù)元素的兩點交叉法、基于自適應(yīng)的兩點交叉法，具體三種調(diào)度結(jié)果如下：

基于文中算法，其中交叉操作選擇基于關(guān)聯(lián)度的兩點交叉法，經(jīng)MATLAB軟件計算可得最小成本為131.649元(保留三個有效數(shù)字)，需要調(diào)度車輛4個，具體調(diào)度車路徑為：第一個車輛調(diào)度的租賃點路徑為：0-3-19-20-9-2-0，第二個車輛調(diào)度路徑為0-8-12-5-11-0，第三個車輛調(diào)度路徑為0-15-1-6-0，第四個車輛調(diào)度路徑為0-4-16-18-7-17-13-14-10-0。算法的收斂曲線見圖3。

圖3 第一種交叉方法迭代曲線

當(dāng)算法交叉步驟選擇第二種方法：修正重復(fù)元素的兩點交叉法，經(jīng)MATLAB軟件計算可得最小成本為127.944元(保留三個有效數(shù)字)，需要4個調(diào)度車，具體調(diào)度車路徑為：第一個車輛調(diào)度的租賃點路徑為：0-8-9-2-3-14-10-0，第二個車輛調(diào)度路徑為0-6-1-0，第三個車輛調(diào)度路徑為0-5-12-20-19-0，第四個車輛調(diào)度路徑為0-7-17-13-18-16-4-11-15-0。算法的收斂曲線見圖4。

圖4 第二種交叉方法迭代曲線

當(dāng)算法交叉步驟選擇基于自適應(yīng)的兩點交叉法，計算可得最小成本為135.093元(保留三個有效數(shù)字)，需要4個調(diào)度車，具體調(diào)度車路徑為：第一個車輛調(diào)度的租賃點路徑為0-2-12-1-6-8-0，第二個車輛調(diào)度路徑為0-3-19-20-9-7-17-13-18-0，第三個車輛調(diào)度路徑為0-15-11-14-10-0，第四個車輛調(diào)度路徑為0-5-4-16-0。算法的收斂曲線見圖5。

圖5 第三種交叉方法迭代曲線

通過三種交叉方法對PBVSP進行計算，可知針對紐約市公共自行車數(shù)據(jù)，文中提出的GA-SA算法具有可行性并且效果良好。接下來對GA-SA算法(交叉選擇修正重復(fù)元素的兩點交叉法)和GA算法，以及文獻[6]中的GA-SA算法進行對比分析。

利用三種算法分別對紐約市公共自行車出行數(shù)據(jù)進行10次計算，得出的結(jié)果見表2(結(jié)果保留三位有效數(shù)字)。

表2 算法結(jié)果對比

可以看出文中算法所得的平均成本為132.109 2，最優(yōu)解為127.944，均小于其他兩種算法的目標(biāo)值，基于文中算法，GA算法和GA-SA算法的目標(biāo)成本減少率見表3。

表3 算法的成本減少率

根據(jù)表3可看出基于文中算法，GA算法的目標(biāo)值成本平均優(yōu)化率達到了12.17%，文獻[6]GA-SA算法平均優(yōu)化率為52.11%，再一次驗證文中算法適用于解決公共自行車調(diào)度問題。

另外利用t檢驗[13]來判斷文中算法與GA算法、文獻[6]算法之間是否存在統(tǒng)計上的顯著差異，以文中算法和GA算法比較為例，采用t檢驗中的雙總體檢驗法，給出原假設(shè)H0和備擇假設(shè)H1分別為：

H0:μGA-SA-μGA=0

H1:μGA-SA-μGA≠0

其中，μGA-SA表示文中算法的均值，μGA為GA算法的均值。

計算檢驗統(tǒng)計量為：

(10)

表4 兩樣本檢驗

通過表4可以看出，顯著性檢驗均為0<0.05,因此拒絕原假設(shè)，接受備擇假設(shè)，文中提出的GA-SA算法和GA算法、文獻[6]中算法在統(tǒng)計學(xué)上有顯著差異。

通過以上分析研究，文中提出的算法在公共自行車調(diào)度問題上有較優(yōu)的可行性。

4 結(jié)束語

建立了基于成本最小的公共自行車靜態(tài)調(diào)度模型，采用改進的遺傳混合模擬退火的GA-SA算法進行求解，通過實例分析表明：該算法的優(yōu)化效果較好，有較強的可行性和有效性。伴隨著路徑優(yōu)化問題的需求增大，在該研究的基礎(chǔ)上綜合考慮軟時間窗[14]、多車場[15]等具體背景約束[16]，求解公共自行車調(diào)度問題是接下來的研究方向之一。