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

魏雁天

（三門峽職業(yè)技術學院，河南三門峽 472000）

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

1 方案分析

1.1 問題描述

通勤車路線規(guī)劃：在某些時間段，通勤車經過?？奎c，接載分布在相應站點的所有教師到職教園區(qū)；在另外一些時間段，通勤車負責將教師從職教園區(qū)送回相應的站點。

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

1.2 數據采集

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

表1 數據收集格式

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

1.3 挑選候選?？奎c

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

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

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

通勤車路徑上?？奎c坐標如表2所示。

表2 通勤車路徑上?？奎c坐標

1.4 數學建模

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

2 算法設計

2.1 改進的蟻群算法實現

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

（1）在MATLAB中初始化已優(yōu)化蟻群算法的參數，如設置ant的個數為50個，通勤車?？奎c的數量為30個，每一只ant隨機挑選30個?？奎c中的任一地點作為出發(fā)地。

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

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

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

（3）在循環(huán)內通過函數求解每只ant經過的所有?？奎c之間的路徑長度，在設置的變量里保存當前最短路徑。

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

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

（6）輸出當前最優(yōu)路徑。

2.2 蟻群算法效果測試

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

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

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

優(yōu)化路線結果如圖2所示。

圖2 優(yōu)化路線的結果

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

圖3 路徑長度變化曲線

3 結語

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