吳會叢 王 敬

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

0 引 言

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

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

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

1 需求分析及預(yù)測

1.1 調(diào)度需求分析

共享單車的使用情況會受到季節(jié)、星期、時(shí)間等因素的影響[8]。在天氣較惡劣的情況下，用戶對共享單車的使用意愿會下降，共享單車的利用率也會大大降低，此時(shí)，管理者就可以從擁有共享單車數(shù)量充足或者富余的租賃點(diǎn)中調(diào)一部分單車到有需要的租賃點(diǎn)中，以免造成資源的浪費(fèi)。在春季或者溫度適中的情況下，共享單車的使用率會大大增加，此時(shí)，應(yīng)該適當(dāng)?shù)卦黾訉蚕韱诬嚨呐伤土?，以滿足用戶的使用需求。

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

表1 預(yù)測車輛數(shù)與各相關(guān)因素之間的相關(guān)系數(shù)

1.1.1時(shí)間對共享單車數(shù)量的影響

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

圖1 時(shí)間點(diǎn)對共享單車數(shù)量的影響

1.1.2季節(jié)對共享單車數(shù)量的影響

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

圖2 季節(jié)對共享單車數(shù)量的影響

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

1.2 基于XGBoost的需求預(yù)測

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

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

2 共享單車任務(wù)調(diào)度

共享單車的調(diào)度問題，主要發(fā)生在擁有自行車數(shù)量過多或者過少的租賃點(diǎn)中，此時(shí)需要對租賃點(diǎn)進(jìn)行合理的調(diào)度配送，以解決租賃點(diǎn)“無車可借，無處可還”的欠佳狀態(tài)。

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

2.1 問題描述

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

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

1) 配送路線上各個(gè)租賃點(diǎn)的配送量之和不能超過配送車輛的最大負(fù)載量。

2) 配送路線上各個(gè)租賃點(diǎn)的需求必須都滿足。

3) 配送路線中，每個(gè)租賃點(diǎn)有且只能訪問一次。

4) 配送車輛都是由調(diào)度中心出發(fā)，最后返回調(diào)度中心。

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

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

2.3 數(shù)學(xué)描述

共享單車配送調(diào)度的目標(biāo)函數(shù)為配送路線的最短距離：

minf=total_distance

(1)

式中：f為目標(biāo)函數(shù);total_distance為配送距離總長度。

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

(2)

該實(shí)驗(yàn)還有很多約束條件：在同一條配送路線上，各個(gè)租賃點(diǎn)需要配送的車輛總和不能超過配送車輛的最大負(fù)載重量，即：

(3)

式中：bi為各個(gè)租賃點(diǎn)實(shí)際需要配送的共享單車數(shù)量，T為配送車輛的最大負(fù)載量，本文中T=200。

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

(4)

(5)

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

根據(jù)當(dāng)前各個(gè)租賃點(diǎn)已有共享單車數(shù)量與預(yù)測出的需求量，得到實(shí)際需要的配送量bi。bi為已有單車數(shù)與單車需求量的偏差值：當(dāng)bi>0時(shí)，供大于求，此時(shí)需要將bi輛共享單車裝上貨車；當(dāng)bi<0時(shí)，供不應(yīng)求，此時(shí)需要卸下配送車中|bi|輛共享單車，以供用戶使用。

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

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

目前已經(jīng)有許多啟發(fā)式算法應(yīng)用于路徑調(diào)度問題中，其中蟻群算法尤為顯著。本文采用基于蟻群的啟發(fā)式算法對共享單車的配送調(diào)度進(jìn)行調(diào)度。

3.1 規(guī)定參數(shù)

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

3.2 獲取禁忌列表

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

3.3 輪盤賭選擇租賃點(diǎn)

在螞蟻的覓食過程中，螞蟻選擇下一個(gè)租賃點(diǎn)的方式多種多樣，本文實(shí)驗(yàn)采用典型的輪盤賭方法[14]來進(jìn)行選擇。

螞蟻選擇每個(gè)租賃點(diǎn)的概率采用兩個(gè)租賃點(diǎn)之間的距離與當(dāng)前路徑上信息素濃度的比值來計(jì)算：

(6)

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

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

3.4 信息素衰減

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

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

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

(7)

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

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

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

temp_pheromone[start][end]+

Q/ant.total_distance

(8)

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

通過式(7)和式(8)對路徑上的信息素濃度進(jìn)行更新，達(dá)到一定的迭代次數(shù)時(shí)可以得到較優(yōu)的路徑解。

本文主要從路徑上信息素的濃度進(jìn)行改進(jìn)。首先設(shè)置信息素的初始濃度為一個(gè)較大值，然后對新迭代的信息素濃度進(jìn)行修改，實(shí)驗(yàn)發(fā)現(xiàn)每只螞蟻在其路徑上留下的信息素與螞蟻?zhàn)哌^此次路徑所攜帶的信息素濃度的相對殘留度和信息素的增量有關(guān)。通過將新迭代的信息素以及初始信息素濃度都進(jìn)行適當(dāng)衰減后，能夠在更加少的迭代次數(shù)時(shí)得到最優(yōu)的配送路線，如算法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(租賃點(diǎn))：

15. for(租賃點(diǎn))：

16. pheromone_graph[i][j]←pheromone_graph

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

3.5 計(jì)算距離

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

算法2計(jì)算總行駛距離

輸入：各個(gè)租賃點(diǎn)之間的距離。

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

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

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

4 實(shí) 驗(yàn)

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

從百度地圖中的拾取坐標(biāo)系統(tǒng)中獲得某學(xué)校內(nèi)選定的15個(gè)租賃點(diǎn)(包括配送中心)所對應(yīng)的經(jīng)緯度，然后再根據(jù)經(jīng)度和緯度計(jì)算得到在畫布中相對應(yīng)的橫、縱坐標(biāo)，如表2所示。

表2 租賃點(diǎn)的橫、縱坐標(biāo)

本文采用的調(diào)度算法是對蟻群算法的改進(jìn)，因此基本蟻群算法中的各個(gè)實(shí)驗(yàn)參數(shù)在該實(shí)驗(yàn)中同樣適用。參數(shù)設(shè)置如表3所示。

表3 實(shí)驗(yàn)參數(shù)表

為了保證后期能夠準(zhǔn)確地對15個(gè)租賃點(diǎn)的需求進(jìn)行配送調(diào)度，本文采用基于XGBoost的預(yù)測模型對各個(gè)租賃點(diǎn)進(jìn)行需求預(yù)測，其中最大深度為3，學(xué)習(xí)步長為0.1，迭代次數(shù)為100次。然后與當(dāng)前各個(gè)租賃點(diǎn)已經(jīng)擁有的共享單車數(shù)量作比較，得到需要配送的車輛數(shù)bi如表4所示。

表4 各租賃點(diǎn)需要配送共享單車的數(shù)量

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

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

圖3 改進(jìn)蟻群算法的調(diào)度路線

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

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

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

4.2.1初始信息素濃度為1時(shí)的情況

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

圖4 初始信息素濃度為1時(shí)的情況

可以看出，當(dāng)初始信息素濃度為1時(shí)，基本的蟻群算法得到的最短距離為2 952 m，其迭代次數(shù)為10次左右;改進(jìn)蟻群算法迭代114次，得到的最短距離為2 922 m，這個(gè)距離在基本蟻群算法中是短時(shí)間內(nèi)無法得到的。

4.2.2初始信息素濃度為100時(shí)的情況

當(dāng)初始信息素濃度為100時(shí)，改進(jìn)前和改進(jìn)后的蟻群算法得到最優(yōu)配送距離如圖5所示。

圖5 初始信息素濃度為100時(shí)的情況

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

4.2.3算法對比

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

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

可以看出，在本實(shí)驗(yàn)中，蟻群算法比遺傳算法得到的結(jié)果更好，蟻群算法的結(jié)果依次遞減，而遺傳算法并沒有得出一個(gè)比較好的配送結(jié)果，并且結(jié)果具有波動性。改進(jìn)后的蟻群算法又比基本的蟻群算法有所改善，當(dāng)信息素的濃度有一個(gè)較大的數(shù)值時(shí)，考慮到螞蟻在覓食過程中信息素濃度的揮發(fā)，由此得到最優(yōu)路徑的迭代次數(shù)要小很多。這是因?yàn)槁窂缴闲畔⑺貪舛茸銐虼髸r(shí)，隨著時(shí)間的增加，信息素的濃度還會存在一定的量，不會在多次訪問后，完全淡化。此外，改進(jìn)后的蟻群算法也能得到更短的配送距離。

通過以上實(shí)驗(yàn)得到以下幾點(diǎn)結(jié)論：

1) 各個(gè)租賃點(diǎn)的實(shí)時(shí)需求對于動態(tài)調(diào)度是非常有必要的，具有及時(shí)性。

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

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

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

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

表5 不同算法的配送距離與迭代次數(shù)對比結(jié)果

5 結(jié) 語

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

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