基于改進蟻群算法的共享單車配送調度研究

吳會叢 王 敬

(河北科技大學信息科學與工程學院 河北 石家莊 050018)

0 引 言

當今城市發展迅速，為了解決城市交通問題，共享單車應運而生。隨著共享單車的使用率逐步增加，其在各個租賃點之間的配送調度問題也隨之產生[2]。各個租賃點的共享單車不能完全滿足用戶的需求，或者很容易造成極大的資源浪費，因此需要管理者對共享單車進行合理地調度并及時進行配送，最大限度滿足用戶的使用需求。如何均衡共享單車在不同租賃點的分布，滿足用戶使用共享單車的需求量，尋找調度配送路徑的最短距離，對完善公共交通體系，提升交通服務水平，保護城市環境具有非常重要的意義。

目前，對于調度問題已經有了許多研究。文獻[3]提出了一種以基于斥候蟻實現的動態局部搜索為核心策略，城市分類、加大信息素濃度差和繼承式的信息素清零等三種策略進行輔助改進的蟻群算法。文獻[4]在蟻群算法中引入遺傳算法中一些遺傳算子的內容，經過對循環次數分組后，對組內、組外進行操作，以加快搜索出最優解的速度。文獻[5]通過BP神經網絡對單車的初始量進行預測，完成之后以期望調度次數最少為目標，建立整數規劃模型，利用lingo進行求解，并得出期望調度次數。文獻[6]使用兩個約束函數來評估并提供有關性能和預算成本的反饋，這兩個約束函數使改進的蟻群算法根據反饋情況及時調整解決方案的質量，以實現最優解。文獻[7]對區域化管理給出了一種基于P-中值模型的聯營區劃分方法，實驗證明該方法靈活方便。對于高峰時的調度需求，建立以加權移動平均法為基礎的模型，最后采用遺傳算法進行模型求解。

上述算法存在一些問題，如：只適合空間復雜度較小的情況；只考慮調度次數而沒有考慮配送距離；沒有采用實際運營數據做支撐而難以判斷優化性。因此，本文提出一種既適合較大空間范圍又考慮到配送距離，具有運營數據支撐的租賃點之間螞蟻殘留信息素濃度的計算方法。通過該方法能夠在一定的時間內得到一段較合理的配送路線，實驗結果表明，該方法能夠得到行駛距離較短的配送調度路線。

1 需求分析及預測

1.1 調度需求分析

共享單車的使用情況會受到季節、星期、時間等因素的影響[8]。在天氣較惡劣的情況下，用戶對共享單車的使用意愿會下降，共享單車的利用率也會大大降低，此時，管理者就可以從擁有共享單車數量充足或者富余的租賃點中調一部分單車到有需要的租賃點中，以免造成資源的浪費。在春季或者溫度適中的情況下，共享單車的使用率會大大增加，此時，應該適當地增加對共享單車的派送量，以滿足用戶的使用需求。

本文實驗所需的數據集包含日期、季節、是否節假日、是否工作日、天氣、濕度、溫度和風速等相關因素。值得注意的是，日期時間特征由年、月、日和具體小時組成，還可以根據日期計算其星期，因此可以將日期時間拆分成年、月、日、時和星期5個特征。計算得出預測車輛數與各相關因素之間的相關系數，如表1所示。

表1 預測車輛數與各相關因素之間的相關系數

1.1.1時間對共享單車數量的影響

在工作日或者周末時，某租賃點共享單車的使用率有所不同，而且在不同的時間段內也不盡相同。工作日每天都有兩個高峰期，分別是臨近八點和十七點三十分左右，這個時間段正好是工作日的上、下班的時間點，因此，共享單車的需求量會大大增加，而介于這兩個時間段之間的單車使用量則比較少。在周末時，用戶的普遍用車量主要集中在上午十點至晚上七點的時間段里，但最高的使用量仍舊達不到上、下班高峰時的使用量。時間對共享單車數量的影響如圖1所示。

圖1 時間點對共享單車數量的影響

1.1.2季節對共享單車數量的影響

通過對某地共享單車使用情況的分析，可以知道季節對某一租賃點共享單車的使用量存在一定的影響。在天氣較寒冷的冬季，共享單車的使用量相對較少，在天氣較好的夏季和秋季，其使用量明顯增加。季節對共享單車數量的影響如圖2所示。

圖2 季節對共享單車數量的影響

此外，溫度、濕度、風速等原因也會對共享單車的租用情況有一定的影響。

1.2 基于XGBoost的需求預測

通過上述分析，可以知道共享單車的使用需求會隨著時間、季節、星期、溫度、風速等因素的改變而改變。本文通過將這些影響因素作為自變量輸入到XGBoost預測模型[9]中，得到各個租賃點的實時需求，然后根據實時需求量與當前租賃點的實際數量的差值，為各個租賃點配送對應數量的共享單車，以滿足用戶的需求。

本文采用的XGBoost模型是基于Scikit-learn接口的分類，它采用線性回歸模型，基于樹的模型進行提升計算。實驗所用到的每一組數據樣本都包含日期、季節、是否節假日、是否工作日、天氣、濕度、溫度和風速等相關因素。根據特征因素的特性，將這些因素與已有的標簽因素匹配對應，從而得到比較準確的預測數據，即根據以往同樣或相似的前提條件，預測此時可能需要的共享單車的數量，以此達到及時配送的可能。

2 共享單車任務調度

共享單車的調度問題，主要發生在擁有自行車數量過多或者過少的租賃點中，此時需要對租賃點進行合理的調度配送，以解決租賃點“無車可借，無處可還”的欠佳狀態。

目前，城市公共自行車系統一般都具有成百上千個租賃點，這是非常龐大的。本文采用小范圍內的地區進行實例驗證，同時采用單一車輛進行調度配送。根據各個租賃點的配送量和各個租賃點之間的距離，通過改進蟻群算法中初始信息素濃度和路徑中信息素的更新方法在較短時間內求得更優配送路線[10]。

2.1 問題描述

在某學校內選擇具有代表性的15個租賃點(?？奎c)，規定其中一個租賃點為配送中心，將其設置為配送路線的出發點，亦是終點。根據各個租賃點的配送量和距離信息，對其余14個租賃點進行合理的配送。首先從配送中心出發，用一輛負載量足夠大的配送車輛為該區域內的14個租賃點配送共享單車，各個租賃點的地理位置是固定不變的，但是各個租賃點的需求量是隨著時間、天氣等外界因素的變化而實時變化的，由此可知時刻調度是非常有必要的[11]。

配送車輛的負載量是已知且固定的，將所有租賃點的相對位置以坐標的形式顯示在畫布上，其數據是從百度地圖中的坐標拾取系統中得到的。要求在不重復訪問各個租賃點，且滿足所有租賃點的需求并符合各個約束條件的情況下，制定出合理的車輛配送路線，以實現配送距離最短的目標[12]。要求滿足以下條件：

1) 配送路線上各個租賃點的配送量之和不能超過配送車輛的最大負載量。

2) 配送路線上各個租賃點的需求必須都滿足。

3) 配送路線中，每個租賃點有且只能訪問一次。

4) 配送車輛都是由調度中心出發，最后返回調度中心。

2.2 參數設置

租賃點集合S={1，2，…，m}，各租賃點的需求量C=[c0，c1，…，cm]，租賃點的橫、縱坐標分別為distance_x=[x0，x1，…，xm]，distance_y=[y0,y1,…,ym]，配送車最大負載量Maxbike和決策變量xij。

2.3 數學描述

共享單車配送調度的目標函數為配送路線的最短距離：

minf=total_distance

(1)

式中：f為目標函數;total_distance為配送距離總長度。

total_distance由三大部分組成，分別是從配送中心到租賃點i的距離d0i、各個租賃點之間的距離dij和租賃點j返回到配送中心的距離dj0，其計算公式如下：

(2)

該實驗還有很多約束條件：在同一條配送路線上，各個租賃點需要配送的車輛總和不能超過配送車輛的最大負載重量，即：

(3)

式中：bi為各個租賃點實際需要配送的共享單車數量，T為配送車輛的最大負載量，本文中T=200。

在配送共享單車的路線中，各個租賃點能且只能訪問一次，公式如下：

(4)

(5)

根據XGBoost模型預測出每個租賃點的需求量，即c1，c2，…，cm。預測模型中的輸入為影響租賃數量的各個特征因素，輸出為租賃點的實時需求量。將必要的特征因素輸入到XGBoost模型中，采用上述參數進行預測，得到比較符合實際的需求量ci。

根據當前各個租賃點已有共享單車數量與預測出的需求量，得到實際需要的配送量bi。bi為已有單車數與單車需求量的偏差值：當bi>0時，供大于求，此時需要將bi輛共享單車裝上貨車；當bi<0時，供不應求，此時需要卸下配送車中|bi|輛共享單車，以供用戶使用。

共享單車的調度問題，主要是為了滿足人們平時的需求。如果想對現在或者未來某時間段內各個租賃點所需的共享單車進行配送，可以與之前已知數據中同樣的時間段、天氣、月份、溫度、濕度和風速等特征因素進行匹配，由此預測出當前或者未來時段內租賃點可能需要的單車數量。然后根據預測出來的數量以及距離等相關因素，對配送的調度路線進行合理有效的劃分，并派出調度員進行調度配送，及時滿足人們的出行需求，從而達到對單車的合理利用并促進社會的和諧發展。

3 基于信息素衰減的蟻群算法

目前已經有許多啟發式算法應用于路徑調度問題中，其中蟻群算法尤為顯著。本文采用基于蟻群的啟發式算法對共享單車的配送調度進行調度。

3.1 規定參數

基本蟻群算法中涉及許多的參數，主要有信息啟發式因子、期望啟發式因子、蟻群數量、信息揮發因子等重要參數，同時還包括配送車量的最大負載量、信息素的初始濃度等。

3.2 獲取禁忌列表

對于一條需要配送的路徑來說，所有的租賃點能且只能訪問一次，以免獲得多余的行程，因此需要將訪問過的租賃點存儲到禁忌表中[13]，避免重復訪問。在所有可以訪問的租賃點中，還要考慮當前配送數量的正負情況：配送數量為正，且當前配送車上已擁有的數量與配送數量的和仍不超過最大負載量Maxbike，或者配送數量為負，且當前配送車上已擁有的數量與該配送數量的和大于等于零時，該租賃點才可以加入配送調度路線中。

3.3 輪盤賭選擇租賃點

在螞蟻的覓食過程中，螞蟻選擇下一個租賃點的方式多種多樣，本文實驗采用典型的輪盤賭方法[14]來進行選擇。

螞蟻選擇每個租賃點的概率采用兩個租賃點之間的距離與當前路徑上信息素濃度的比值來計算：

(6)

式中：Pi為選擇概率;α為信息啟發式因子;β為期望啟發式因子;τij為信息素濃度;dij為租賃點i到租賃點j之間的距離。

通過式(6)得到各個租賃點被選中的概率，將這些概率求和得到總的概率值，然后得到到達各個租賃點真正的概率。雖然得到了到達每一個租賃點的概率，但由于蟻群算法的多樣性，因此也要保證其他租賃點有被選中的機會。否則，如果只選擇概率最大的租賃點，就會變成貪心算法。因此用輪盤選擇的方法，獲得每個租賃點的概率值，即隨機產生一個0到總概率范圍之間的隨機浮點數，然后輪次相減到各個租賃點的概率值，直至為負數，此時得到下一個租賃點的序號。重復同樣的操作，直到所有的租賃點全部遍歷結束。

3.4 信息素衰減

信息素的更新[15]在蟻群算法中是一個需要解決的難點。蟻群算法將初始信息素濃度設置為一個比較小的值，在所有螞蟻進行一次完整的行走后，環境中的信息素就需要進行更新。信息素的變化主要受到兩個因素的影響：每只螞蟻在走過的路徑中留下的信息素；環境信息素的自然減少，即原有的路徑上信息素濃度會隨著時間的增加而有適當的揮發。因此，信息素濃度包括整條路徑上殘留的初始信息素濃度以及在整條路徑上新迭代產生的信息素濃度如下：

pheromone_graph[i][j]=pheromone_graph[i][j]×

(1-ρ)+temp_pheromone[i][j]

(7)

式中：temp_pheromone[i][j]為新迭代的信息素濃度;pheromone_graph[i][j]為總的信息素濃度。

而新迭代產生的信息素濃度又包括螞蟻在其路徑上留下的信息素以及當前兩個租賃點之間殘留的信息素，如式(8)所示。在螞蟻搜索的過程中，租賃點之間的信息素不斷減少，會在一定程度上影響到螞蟻的選擇。

temp_pheromone[start][end]=(1-ρ)×

temp_pheromone[start][end]+

Q/ant.total_distance

(8)

式中：ρ為信息揮發因子;Q為信息素的初始濃度;ant.total_distance為配送的總路徑。

通過式(7)和式(8)對路徑上的信息素濃度進行更新，達到一定的迭代次數時可以得到較優的路徑解。

本文主要從路徑上信息素的濃度進行改進。首先設置信息素的初始濃度為一個較大值，然后對新迭代的信息素濃度進行修改，實驗發現每只螞蟻在其路徑上留下的信息素與螞蟻走過此次路徑所攜帶的信息素濃度的相對殘留度和信息素的增量有關。通過將新迭代的信息素以及初始信息素濃度都進行適當衰減后，能夠在更加少的迭代次數時得到最優的配送路線，如算法1所示。

算法1初始信息素和路徑信息素的更新

輸入：路徑和初始信息素信息。

輸出：更新后的信息素。

1. for ant in self.ants:

2. ant.search_path()

3. if ant.total_distance

4. self.best_ant ←copy.deepcopy(ant)

5. //信息素更新：

6. for ant in self.ants:

7. for 1 to m：

8. start, end ← ant.path[i-1], ant.path[i]

9. temp_pheromone[start][end]

10. ←(1-ρ)×temp_pheromone[start][end]+

11. Q/ant.total_distance

12. temp_pheromone[end][start]

13. ←temp_pheromone[start][end]

14. for(租賃點)：

15. for(租賃點)：

16. pheromone_graph[i][j]←pheromone_graph

17. [i][j]×(1-ρ)+temp_pheromone[i][j]

3.5 計算距離

本實驗中螞蟻行駛的路徑長度，不考慮道路的實際情況，僅考慮兩租賃點之間的最短距離。首先需要將這15個租賃點根據其經緯度在畫布中畫出相對應的位置，然后采用歐氏距離求解任意兩個租賃點之間的距離，并求和得到總的配送距離，如算法2所示。

算法2計算總行駛距離

輸入：各個租賃點之間的距離。

輸出：配送路線的總距離。

1. for i in range(city_num):

2. for j in range(city_num):

3. temp_distance←pow((distance_x[i]-

4. distance_x[j]), 2)+pow((distance_y[i]-

5. distance_y[j]),2)

6. temp_distance←pow(temp_distance,0.5)

7. distance_graph[i][j]←float(int(temp_

8. distance+0.5))

與現有解決路徑調度問題的蟻群算法和遺傳算法相比，本文提出的租賃點之間螞蟻殘留信息素濃度的計算方法可以更有效地調度共享單車的配送，同時得到更短的調度路線。

4 實 驗

本文通過設定初始信息素濃度以及信息素的更新方法對基本的蟻群算法進行改進，使調度路線能夠在較短的時間內得到。為了減少得到最短配送路線的迭代次數，本文對信息素濃度進行合理的衰減，以在短時間內得到配送路線與最短距離。

4.1 實驗設計

從百度地圖中的拾取坐標系統中獲得某學校內選定的15個租賃點(包括配送中心)所對應的經緯度，然后再根據經度和緯度計算得到在畫布中相對應的橫、縱坐標，如表2所示。

表2 租賃點的橫、縱坐標

本文采用的調度算法是對蟻群算法的改進，因此基本蟻群算法中的各個實驗參數在該實驗中同樣適用。參數設置如表3所示。

表3 實驗參數表

為了保證后期能夠準確地對15個租賃點的需求進行配送調度，本文采用基于XGBoost的預測模型對各個租賃點進行需求預測，其中最大深度為3，學習步長為0.1，迭代次數為100次。然后與當前各個租賃點已經擁有的共享單車數量作比較，得到需要配送的車輛數bi如表4所示。

表4 各租賃點需要配送共享單車的數量

4.2 實驗結果及分析

由于人們對共享單車的需求是隨著一些外界因素而改變的，因此需要時時刻刻了解共享單車的使用情況。首先根據以前時間段得到的數據對其影響因素進行大致分析，然后通過XGBoost模型對未來時刻的共享單車的需求量進行分析，并與當前已有數量進行對比，得到真正需要配送的單車數量。最后通過改進的蟻群算法對各個租賃點進行車輛配送，以及時滿足人們的滿意度。利用本文獲取到的某學校內的15個租賃點進行實驗，它們所需共享單車的配送路線如圖3所示，其配送路線為：0-4-14-2-10-13-7-8-11-1-12-9-5-3-6-0。

圖3 改進蟻群算法的調度路線

基本蟻群算法參數設置見表3，初始信息素的濃度為1。在沒有設置較高的初始信息素濃度和改進信息素的更新方法前，在迭代20 000次以前，始終無法達到圖3所示的最優路徑，但是在迭代10次左右時可以得到次優的配送路線：0-6-4-14-2-10-13-7-8-11-1-12- 9-5-3-0，此路線的配送距離為2 952 m。

考慮到最大最小螞蟻系統[16]中，對初始信息素的濃度有設定，因此，將初始信息素濃度設置為一個較大的數值，防止在搜索路途中，初始信息素濃度淡化以影響螞蟻的判斷。

與基本蟻群算法相比，當改進信息素的更新方法和初始信息素濃度之后，能夠得到更短距離的配送路線，其迭代次數也比較小。在改進的算法中，初始信息素濃度為100時，僅需要迭代26次就可以獲得配送距離為2 922 m的行駛路線。而采用遺傳算法求解該問題時，發現很難達到以上這兩種短距離的配送路線，其達到的最短距離為3 774 m。雖然得到該結果的迭代次數并不是很高，但是經過實驗對比發現該結果的可行性比較低，因此舍棄該算法。為了更加直觀地顯示該內容，用圖表示它們之間的關系。對于不同的初始信息素濃度，本文提出的基于信息素衰減的更新方法也有一定的作用。

4.2.1初始信息素濃度為1時的情況

當初始信息素濃度為1，基本蟻群算法和改進的蟻群算法分別得到不同的最短配送距離，如圖4所示。

圖4 初始信息素濃度為1時的情況

可以看出，當初始信息素濃度為1時，基本的蟻群算法得到的最短距離為2 952 m，其迭代次數為10次左右;改進蟻群算法迭代114次，得到的最短距離為2 922 m，這個距離在基本蟻群算法中是短時間內無法得到的。

4.2.2初始信息素濃度為100時的情況

當初始信息素濃度為100時，改進前和改進后的蟻群算法得到最優配送距離如圖5所示。

圖5 初始信息素濃度為100時的情況

可以看出，初始信息素濃度為100時，基本蟻群算法仍舊無法在短時間內獲得2 922 m這個較短的配送距離，而改進后的算法僅在迭代26次時便可以獲得2 922 m的配送路線。

4.2.3算法對比

基本蟻群算法、遺傳算法和改進的蟻群算法所得到的最短配送距離的關系如圖6所示。

圖6 三種算法行駛距離的比較

可以看出，在本實驗中，蟻群算法比遺傳算法得到的結果更好，蟻群算法的結果依次遞減，而遺傳算法并沒有得出一個比較好的配送結果，并且結果具有波動性。改進后的蟻群算法又比基本的蟻群算法有所改善，當信息素的濃度有一個較大的數值時，考慮到螞蟻在覓食過程中信息素濃度的揮發，由此得到最優路徑的迭代次數要小很多。這是因為路徑上信息素濃度足夠大時，隨著時間的增加，信息素的濃度還會存在一定的量，不會在多次訪問后，完全淡化。此外，改進后的蟻群算法也能得到更短的配送距離。

通過以上實驗得到以下幾點結論：

1) 各個租賃點的實時需求對于動態調度是非常有必要的，具有及時性。

2) 影響共享單車需求的因素主要是季節、時間等因素。

3) 不改變初始信息素濃度時，僅改進信息素更新方法得到的配送距離比基本蟻群算法和遺傳算法要小。

4) 本文提出的改進蟻群算法可以獲得更短的配送距離，并且迭代次數也比較小。

本文對初始信息素濃度以及信息素的更新方法進行了設計。由此得到的最優配送共享單車的調度路線為：0-4-14-2-10-13-7-8-11-1-12-9-5-3-6-0，最短距離為2 922 m，迭代次數為26次，此最短距離比基本蟻群算法的最短距離縮短了約1%，比遺傳算法縮短了約22%，而且迭代次數也相對較少，如表5所示。改進的蟻群算法可以獲得更優的配送距離，同時大大減少了程序運行時間和計算時間，使管理員能夠在短時間內得到最優的配送路線，及時為各個租賃點配送適量的共享單車，以滿足人們的需求，因此該算法具有一定的實用性與可行性。

表5 不同算法的配送距離與迭代次數對比結果

5 結 語

本文針對共享單車調度路線問題，首先確定需要進行配送的租賃點，然后根據XGBoost模型求出各個租賃點的需求量，通過需求量來判斷需要如何安排調度路線，并根據需求約束和距離約束等因素，采用改進后的蟻群算法設計調度方案，得到比基本蟻群算法更短的配送距離，迭代次數也比較小，同時也減少了計算時間，具有一定的現實意義。

對于路徑調度問題，蟻群算法是非常有效且實用的算法之一。目前已經有很多人對其進行了改進，并得到了相當可觀的結果。本文改進方法只是其中的一方面，可能考慮得還不是很全面，使用的數據也是自己收集到的數據，后續還需要繼續閱讀大量的文獻，以對該算法有更加全面、新穎的了解與認識?？s短得出最優路線的時間，對于實時配送共享單車是非常有必要的，這樣能夠給配送共享單車留出更加充足的時間，防止配送過程中出現意外。