魏 睿， 李鳳媛， 李科贊， 葛志金

(桂林電子科技大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，廣西 桂林 541004)

隨著我國高等教育的普及，每年的大學(xué)招生規(guī)模也在不斷擴(kuò)大，許多大學(xué)校園在不斷地擴(kuò)建，出現(xiàn)了教學(xué)設(shè)施分布較散的現(xiàn)象。隨著校園規(guī)模的擴(kuò)大，教學(xué)區(qū)與宿舍區(qū)、食堂、運動區(qū)之間的距離增大，老師和學(xué)生步行上下課路途遠(yuǎn)、耗時長，為校園出行帶來不便。許多同學(xué)有了自己的電動車，方便自己的同時也易發(fā)生交通事故，同時給校園交通造成一定的壓力，亂停亂放也給學(xué)校的管理帶來一定的考驗。

為了緩解校園交通壓力，給師生帶來便利的出行方式，許多學(xué)校引進(jìn)了校園公交系統(tǒng)這種集約化的公共交通方式[1-3]。雖然現(xiàn)在有許多文獻(xiàn)對校園公交的運營及規(guī)劃有一定的研究和探討，但大部分內(nèi)容都缺少理論知識，未給出實際的設(shè)計算法。鑒于此，以桂林電子科技大學(xué)校園為例，采用0-1規(guī)劃和蟻群算法，針對目前仍存在一些公交站點、公交線路規(guī)劃不合理，學(xué)生使用體驗感差以及使用率低等缺陷，對公交線路、公交站點等進(jìn)行優(yōu)化，使得優(yōu)先資源最大化使用，給師生帶來最大方便的同時，創(chuàng)造一個節(jié)約型校園出行新方式。

1 校園公交系統(tǒng)現(xiàn)狀

1.1 校園環(huán)境現(xiàn)狀

本次研究以桂林電子科技大學(xué)花江校區(qū)為例，校園地圖如圖1所示。

圖1 桂林電子科技大學(xué)花江校區(qū)校園地圖

花江校區(qū)校園面積較大，現(xiàn)有師生25 000人左右。校園仍有許多區(qū)域等待開發(fā)，目前有多棟教學(xué)樓、多個宿舍區(qū)、圖書館、籃球場、足球場、食堂等，分布較散，道路復(fù)雜交錯，對于師生出行產(chǎn)生不便。桂林每年雨季較多，校園易產(chǎn)生積水，這也是一種出行障礙。

該校區(qū)也引進(jìn)了校園公交，但是目前運營模式不穩(wěn)定，沒有固定公交站點，沒有固定的運行時間，且只有2條公交線路，這些導(dǎo)致了學(xué)生不清楚公交運營狀況，使用率低下。公交司機(jī)也不能掌握學(xué)生上下課分布情況，僅憑經(jīng)驗運行，有時公交數(shù)量分布不均，浪費了有限資源。

1.2 學(xué)生出行現(xiàn)狀調(diào)查

為了解學(xué)生的基本出行現(xiàn)狀，對不同年級進(jìn)行分層抽樣，調(diào)查結(jié)果表明，44%的同學(xué)選擇步行，31%的同學(xué)使用共享單車，19%的同學(xué)使用電動車，6%的同學(xué)使用校園公交等其他方式。同時對學(xué)生校園公交使用意愿進(jìn)行調(diào)查，有60%的同學(xué)比較愿意采用校園公交的出行方式，由此可見，校園公交在校園內(nèi)還是有很大的市場有待發(fā)掘。

2 公交站點設(shè)計

2.1 數(shù)據(jù)整理

對校園內(nèi)主要的教學(xué)樓、宿舍區(qū)、路口等進(jìn)行編號，編號數(shù)據(jù)如表1所示。通過實地測量，得到各個編號之間的實際距離，如表2所示。根據(jù)表1和表2數(shù)據(jù)得到校園各地點編號及路線分布圖，如圖2所示。

表1 校園主要地點部分編號

表2 各編號之間直線距離

圖2 校園主要地點編號及路線圖

2.2 0 -1整數(shù)規(guī)劃模型

公交站點設(shè)計需要考慮師生的出行是否便利，一般情況下，如果師生想去某個地點，那么這個地點就需要設(shè)置成站點，這是最優(yōu)方案。但在實際中，有些地點距離很近，這樣設(shè)計會使得資源浪費，因此應(yīng)該盡量設(shè)計較少的公交站點，達(dá)到最優(yōu)的公交站點覆蓋范圍。根據(jù)調(diào)查，大部分學(xué)生可以接受的目的地到公交站點距離范圍在100 m以內(nèi)，故以100 m作為公交站點最大的覆蓋范圍進(jìn)行研究。此問題是一類選址問題，需建立0-1整數(shù)規(guī)劃模型[4]，根據(jù)各個地點之間距離的情況，安排盡可能少的公交站點，實現(xiàn)最大的區(qū)域覆蓋。

首先通過Floyd算法[5]更新各個地點到其他地點之間的最短路線。在此基礎(chǔ)上，判斷公交站點能否同時覆蓋這些地點。以設(shè)置最小的公交站點為目標(biāo)函數(shù)，即

(1)

其中，

假設(shè)各個地點之間的最短距離為dij，zij表示在i地建立公交站，能否覆蓋點j，若可以覆蓋，則zij=1，否則zij=0。 由此可得以下約束條件：

(2)

將實際測量數(shù)據(jù)代入式(2)進(jìn)行求解，得到所需建立數(shù)量最少時的站點為1、4、5、6、9、10、15、17、18、19、20、21、22、23、24、26、27、28、30。以這19個站點作為擬定公交站點，示意圖如圖3所示。

圖3 擬定公交站點示意圖

3 公交路線最優(yōu)規(guī)劃

按上述問題求解的結(jié)果對公交線路進(jìn)行規(guī)劃，最佳公交線路是每個站點都要經(jīng)過且只經(jīng)過一次的最短路徑，由此可將此問題轉(zhuǎn)化為一個旅行商(TSP)問題。旅行商問題就是從一個點出發(fā)，找出一條可以經(jīng)過所有點且每個站點只經(jīng)過一次的最短回路。目前對于旅行商問題的求解有許多方法，貪心算法是其中一種，但是這種方法只能求解局部的最優(yōu)解，對于全局來說很難得到最優(yōu)解[6]。

蟻群算法作為一種智能算法在旅行商問題上有很好的應(yīng)用，有許多成功案例[7-8]。蟻群算法的基本原理來源于自然界中螞蟻覓食的最短路徑原理，螞蟻在尋找食物源時，在其走過的路徑上釋放一種螞蟻特有的信息素，使得在一定范圍內(nèi)的其他螞蟻可以察覺到并由此影響它們后續(xù)的行為。當(dāng)一些路徑上通過的螞蟻越來越多時，其留下的信息素也越來越多，以致信息素強(qiáng)度增大，螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強(qiáng)度，這種選擇過程被稱為螞蟻的自催化行為。

(3)

在遍歷各地點的過程中，蟻群釋放信息素的同時，各地點之間連接路徑上的信息素的強(qiáng)度也在通過揮發(fā)等方式逐漸消失。為了描述這個特征，設(shè)ρ為信息素?fù)]發(fā)程度。所有螞蟻走完一遍所有地點后，各個地點連接路徑上的信息素濃度為

(4)

一般情況下，

(5)

其中：Q為信息素常數(shù)；Lk為第k只螞蟻經(jīng)過的路徑總長度；ij表示從地點i到地點j的路徑。

蟻群算法流程如圖4所示。

圖4 蟻群算法流程圖

根據(jù)表2數(shù)據(jù)可得各地點之間的距離情況，在螞蟻數(shù)為50，最大迭代次數(shù)為500時，蟻群算法求得的距離最短路線如圖5所示。

圖5 蟻群算法所求的最佳路線

圖5中路線產(chǎn)生的最短回路長為4 805 m。在校園內(nèi)車輛行駛速度不超過20 km/h的情況下，至少需要15輛車才可以滿足大多數(shù)學(xué)生時間上的需求。

4 公交系統(tǒng)仿真模擬實驗

為了解公交系統(tǒng)實際的載客及運輸能力，對公交系統(tǒng)進(jìn)行了模擬實驗。目前每輛車最大可供40人同時使用，公交到達(dá)每個站點都會有人上車，有人下車，這些都是隨機(jī)的。

(6)

其中：Ni為當(dāng)前站點一分鐘內(nèi)的人流量；p為學(xué)生愿意乘坐公交的比例，根據(jù)之前的調(diào)查可將其定為

為愿意乘坐公交的學(xué)生真正上車的概率。

(7)

同時要求上車人數(shù)跟車內(nèi)總?cè)藬?shù)不能超過40人，下車人數(shù)不能使車內(nèi)人數(shù)低于0，此時每輛公交車在行駛一圈后，整個過程所搭載的乘客數(shù)量為

(8)

為了解學(xué)生上下課時主要分布及各地點的人流量大小，按不同時間段對所有地點進(jìn)行統(tǒng)計，得到每分鐘各地點人流量，如表3所示。將表3數(shù)據(jù)代入式(6)～(8)，得到一輛公交車?yán)@行校園一圈所能搭載的人數(shù)模擬數(shù)據(jù)，如表4所示。

表3 每分鐘各個地點通過人數(shù)

表4 每輛車行駛一圈搭載人數(shù)

從表4可看出，每輛車在行駛一圈所能裝載的學(xué)生量為400人左右，根據(jù)此數(shù)據(jù)，15輛車行駛一圈的裝載能力為6 000人左右。每輛車行駛一圈的時長大約是15 min，學(xué)生課間時間為30 min，在30 min內(nèi)，15輛車能搭載的最大人數(shù)為12 000人，已知花江校區(qū)師生總?cè)藬?shù)為25 000人，在60%的乘坐意愿情況下，實驗結(jié)果表明，這些公交能夠滿足大部分師生的出行需求。若公交開啟雙向通道運行模式，隨著投入的車輛數(shù)增加，可以滿足整個學(xué)校的乘車需求。

5 結(jié)束語

針對現(xiàn)有校園公交運營中的站點路線不固定和使用效率低的缺點，提出了一種理論化的研究方法，該方法通過使用0 -1整數(shù)規(guī)劃確定站點的合理分配，使其滿足大部分學(xué)生的需求，同時將公交線路轉(zhuǎn)化為TSP問題，用蟻群算法進(jìn)行求解，得到最優(yōu)的校園公交行駛路線。最后，對校園公交的運載能力進(jìn)行實驗仿真模擬。本方法為校園公交系統(tǒng)的站臺選址、線路優(yōu)化等提供了一種理論參考，同時可推廣至各個領(lǐng)域的相關(guān)問題。由于此方法僅考慮了公交線只有一條的情況，對于中小型的校園有很好的適用性，對于大型企業(yè)、科技園等來說需要擬定多條線路，后續(xù)還需做進(jìn)一步改進(jìn)。