基于改進蟻群算法的通勤車智慧路線研究

魏雁天

（三門峽職業技術學院，河南三門峽 472000）

近年來，國家對職業教育支持力度的加大，較多城市建設了職教園區，但園區距離市區較遠，原本居住在市區的教工們的日常通勤問題凸顯，有效減少通勤車數量、降低不必要成本、提高通勤車服務質量和效率、減少教師出行時間，可以改善新園區的位置偏遠給教師的工作和生活帶來不便，降低通勤車接送成本，提高園區建設智能化。本文研究實際情況約束條件下的班車路線優化，以期獲得最優通勤車路線方案。

1 方案分析

1.1 問題描述

通勤車路線規劃：在某些時間段，通勤車經過停靠點，接載分布在相應站點的所有教師到職教園區；在另外一些時間段，通勤車負責將教師從職教園區送回相應的站點。

通勤車路線規劃的智慧化程度決定了通勤車數量、運營次數、運營時間以及教師出行時間。

1.2 數據采集

選取三門峽市職教園區兩所大學為例，搜集兩所大學教工數據，整理成一張二維表，字段為本校教師的職工號、乘通勤車意愿和家庭住址，如表1所示。

表1 數據收集格式

在優化通勤車路線方案之前，設定一些通勤車運行規則：每輛通勤車的限載30人；以0.5 km標準作為教師從家出發抵達站點的距離，選停靠點接教師上通勤車；平衡站點的負載，舍棄一些明顯距離較遠的站點，將此站的教師合并到合適的停靠點，保證教師的正常出行時間；通勤車滿時，直接開往職教園區，不再途經其他站點；盡量避開人流密集的地方，如大型百貨量販、需要家長接送孩子的幼兒園和小學門前的道路。

1.3 挑選候選停靠點

根據教師的家庭住址數據和道路數據篩選通勤車站點。由于教師家庭住址較為分散，放棄一些距離較遠的，保證教師的正常上下班時間，設置0.5 km標準作為教師抵達站點的距離，并平衡好站點的密集程度，通勤車行駛路線上共設置30個停車點。

通過百度地圖生成事先統計好的各個停靠點經緯度坐標，各個站點的距離相較于偌大的區塊劃分，距離很近導致在地圖上各點的經緯度相近，為了更直觀使用MATLAB的繪圖功能顯示仿真結果，對各個停靠點的經緯度進行處理。

去掉停靠點經度的整數部分，保留經度小數點后的3、4、5、6位，生成千位數字橫坐標；去掉停靠點緯度的整數部分，保留緯度的小數點后的2、3、4、5位生成千位數字縱坐標。使用MATLAB編程前，將30個停靠點在百度地圖上的經緯度坐標，使用上述方法加大坐標的辨識度，轉換成如下標注（X，Y）坐標的數據，導入MATLAB，為通勤車路線方案優化提供基礎數據。

通勤車路徑上停靠點坐標如表2所示。

表2 通勤車路徑上停靠點坐標

1.4 數學建模

在進行算法設計之前，需要針對通勤車路線優化進行數學建模，先期量化部分參數指標，設置ant為50個，通勤車停靠點的數量為30個，把前期能夠確定的參數映射到蟻群算法中。

2 算法設計

2.1 改進的蟻群算法實現

基于改進的蟻群算法相較于基本蟻群算法的突出特征是，對蟻群的啟發參數采用混合參數，即每只螞蟻的啟發參數均不同，以期更好地發揮蟻群算法的優勢。

（1）在MATLAB中初始化已優化蟻群算法的參數，如設置ant的個數為50個，通勤車停靠點的數量為30個，每一只ant隨機挑選30個停靠點中的任一地點作為出發地。

（2）使用迭代構建此次項目停靠點的次序，在這一項目中每個ant可隨機選擇一個停靠點作為其遍歷所有車站的出發點，并時刻更新一張路徑記憶列表，用以存放該ant當前時刻之前依次經過的停靠點，以免重復訪問。ant在構建路徑的每一步中，按照(t)值的大小選擇下一個要到達的停靠點。(t)是在t時刻antk從通勤路線上的停靠點i移動到下一停靠點j的隨機概率。

轉移概率的Matlab的實現過程如圖1所示。

圖1 轉移概率計算的Matlab的實現過程

（3）在循環內通過函數求解每只ant經過的所有停靠點之間的路徑長度，在設置的變量里保存當前最短路徑。

（4）每一輪過后更新路徑上信息值，一輪過后本項目中的所有路徑上的信息值通過程序設定都會相應自動減少，所有的ant根據自己構建的路徑，在本輪經過的路徑上釋放信息增加該值。

（5）程序判斷迭代次數，本項目中設定可迭代的次數是150次，通過循環變量計數，達到次數即認為達到終止條件，若滿足條件，則轉到下一步，反之重復。

（6）輸出當前最優路徑。

2.2 蟻群算法效果測試

根據針對蟻群算法運行參數的設定，借助MATLAB軟件對教師通勤車路線進行仿真實試驗，得到的串聯兩所高校的校通勤車優化路線。

設定職教園區2號站為校車的終到站，不設置通勤班車的出發點，根據提前設置好的交通規則和總路徑長度最短的目的。

設置螞蟻數量為50個，這樣每次迭代都會產生50種不同的路徑分配計劃，程序設定一次迭代完成后，通過比較都會挑選出一個當前最優路徑向量方案，通過程序設定增加該方案的信息值，以確保下一次迭代中，其他螞蟻選擇該路徑走向方案的概率較高。并且還使用一定比例的螞蟻采用隨機分配策略來尋找更好的解決方案。

優化路線結果如圖2所示。

圖2 優化路線的結果

經過大約30次迭代后，出現了全局最優路徑長度變化曲線，如圖3所示。

圖3 路徑長度變化曲線

3 結語

選取三門峽市職教園區兩所高校通勤車路線案例，使用百度地圖轉換停靠點的地理坐標，采用改進的蟻群算法結合MATLAB根據設置的交通規則和實際情況模擬真實的通勤車路線，進行最短路線計算，使用蟻群算法解決通勤車路線優化問題實用、高效。