魏雁天

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

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

1 方案分析

1.1 問(wèn)題描述

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

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

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

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

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

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

1.3 挑選候選?？奎c(diǎn)

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

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

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

通勤車路徑上停靠點(diǎn)坐標(biāo)如表2所示。

表2 通勤車路徑上?？奎c(diǎn)坐標(biāo)

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

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

2 算法設(shè)計(jì)

2.1 改進(jìn)的蟻群算法實(shí)現(xiàn)

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

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

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

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

圖1 轉(zhuǎn)移概率計(jì)算的Matlab的實(shí)現(xiàn)過(guò)程

（3）在循環(huán)內(nèi)通過(guò)函數(shù)求解每只ant經(jīng)過(guò)的所有?？奎c(diǎn)之間的路徑長(zhǎng)度，在設(shè)置的變量里保存當(dāng)前最短路徑。

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

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

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

2.2 蟻群算法效果測(cè)試

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

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

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

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

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

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

圖3 路徑長(zhǎng)度變化曲線

3 結(jié)語(yǔ)

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