一種用于公共自行車調度的改進GA-SA算法

趙紅夢，姜志俠，曾 坤

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

0 引 言

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

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

1 模型建立

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

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

根據以上條件建立數學模型(PBVSP)：

(1)

(2)

(3)

(4)

(5)

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

2 算法設計

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

2.1 算法的變異操作

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

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

2.2 算法的交叉操作

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

(1)基于關聯度的兩點交叉法。

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

判斷X,Y之間關聯度的公式如下：

(6)

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

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

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

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

(7)

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

2.3 算法的解碼操作

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

圖1 染色體解碼流程

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

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

(8)

2.4 算法的選擇操作

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

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

(9)

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

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

圖2 算法流程

3 實例分析

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

表1 原始數據

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

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

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

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

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

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

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

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

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

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

表2 算法結果對比

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

表3 算法的成本減少率

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

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

H0:μGA-SA-μGA=0

H1:μGA-SA-μGA≠0

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

計算檢驗統計量為：

(10)

表4 兩樣本檢驗

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

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

4 結束語

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