魏雁天

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

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

1 方案分析

1.1 問題描述

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

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

1.2 數(shù)據(jù)采集

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

表1 數(shù)據(jù)收集格式

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

1.3 挑選候選?？奎c

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

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

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

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

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

1.4 數(shù)學(xué)建模

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

2 算法設(shè)計

2.1 改進的蟻群算法實現(xiàn)

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

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

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

轉(zhuǎn)移概率的Matlab的實現(xiàn)過程如圖1所示。

圖1 轉(zhuǎn)移概率計算的Matlab的實現(xiàn)過程

（3）在循環(huán)內(nèi)通過函數(shù)求解每只ant經(jīng)過的所有停靠點之間的路徑長度，在設(shè)置的變量里保存當前最短路徑。

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

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

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

2.2 蟻群算法效果測試

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

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

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

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

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

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

圖3 路徑長度變化曲線

3 結(jié)語

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