基于蟻群算法多起點(diǎn)多終點(diǎn)社區(qū)公交路徑規(guī)劃

陸乾杰，陳志平，張林佳，王浩南，劉純璐

(杭州電子科技大學(xué)卓越學(xué)院，浙江 杭州 310018)

?

基于蟻群算法多起點(diǎn)多終點(diǎn)社區(qū)公交路徑規(guī)劃

陸乾杰，陳志平，張林佳，王浩南，劉純璐

(杭州電子科技大學(xué)卓越學(xué)院，浙江 杭州 310018)

摘要：為解決大型社區(qū)的“最后一公里”難問(wèn)題，提出一種根據(jù)不同乘客需求來(lái)確定行車路線的社區(qū)公交系統(tǒng)方案.針對(duì)系統(tǒng)中多乘客在不同起點(diǎn)去往不同終點(diǎn)的現(xiàn)象，結(jié)合蟻群算法構(gòu)建了一種多起點(diǎn)多終點(diǎn)問(wèn)題的路徑規(guī)劃算法.算法通過(guò)引入事件觸發(fā)機(jī)制，解決了節(jié)點(diǎn)的排序問(wèn)題；通過(guò)將兩節(jié)點(diǎn)間固定網(wǎng)絡(luò)抽象成一條最短路徑，縮小了解空間的規(guī)模；通過(guò)構(gòu)建解空間樹(shù)，把多起點(diǎn)多終點(diǎn)問(wèn)題轉(zhuǎn)換成單起點(diǎn)單終點(diǎn)問(wèn)題集，很好地解決了蟻群信息素混淆的問(wèn)題；最后運(yùn)用蟻群算法的啟發(fā)性在解空間樹(shù)上尋優(yōu)，獲得最終路徑.仿真算例表明，該算法效率只與請(qǐng)求數(shù)線性相關(guān)，與實(shí)際網(wǎng)絡(luò)的規(guī)模不相關(guān)，因此能很好地融入到大型社區(qū)網(wǎng)絡(luò)中.經(jīng)社區(qū)實(shí)測(cè)，驗(yàn)證了該路徑規(guī)劃算法應(yīng)用于社區(qū)公交系統(tǒng)的可行性，有望在現(xiàn)代化社區(qū)中推廣應(yīng)用.

關(guān)鍵詞：最后一公里；多起點(diǎn)多終點(diǎn)；路徑規(guī)劃；蟻群算法

0引言

隨著城市化建設(shè)的推進(jìn)，居民區(qū)逐漸趨向聚合，大規(guī)模的社區(qū)不斷產(chǎn)生，然而從社區(qū)到周邊交通樞紐(地鐵口、公交站點(diǎn)等)和消費(fèi)中心(醫(yī)院、超市等)的距離并沒(méi)有縮短.交通樞紐或者消費(fèi)中心到居住區(qū)往往還有很長(zhǎng)一段路，稱為“最后一公里”.若遇到特殊天氣，這“最后一公里”就成為最大的困難和麻煩.面對(duì)現(xiàn)有的社區(qū)公交路線不夠靈活，易引起資源浪費(fèi)等問(wèn)題，本文設(shè)計(jì)了一種利用現(xiàn)有公交路線的社區(qū)微型公交系統(tǒng)，在現(xiàn)有系統(tǒng)中增加了動(dòng)態(tài)路徑規(guī)劃策略，解決了同一時(shí)刻多名居民從不同起點(diǎn)去往不同終點(diǎn)的問(wèn)題，這與已有的“動(dòng)態(tài)出租車拼車問(wèn)題”類似，但情況更復(fù)雜.目前，國(guó)內(nèi)外對(duì)拼出租車問(wèn)題已做過(guò)一些研究，文獻(xiàn)[1]基于“貪婪”方法和時(shí)空網(wǎng)絡(luò)提出了兩種啟發(fā)式算法來(lái)解決動(dòng)態(tài)拼出租車問(wèn)題，文獻(xiàn)[2]使用模擬退火算法對(duì)文獻(xiàn)[1]中的算法進(jìn)行了改進(jìn).但是這些方法僅考慮了從單起點(diǎn)到多終點(diǎn)(One-to-many)和從多起點(diǎn)到單終點(diǎn) (Many-to-one)的問(wèn)題，不適用于復(fù)雜的多個(gè)起點(diǎn)到多個(gè)終點(diǎn)的情況.而文獻(xiàn)[3]基于sufferage提出的多起點(diǎn)多終點(diǎn)的拼車調(diào)度方法從任務(wù)調(diào)度的角度進(jìn)行了車輛調(diào)度，在路徑規(guī)劃方面只是采用簡(jiǎn)單的插入操作，這樣會(huì)造成一些解的丟失，且沒(méi)有采納智能算法.文獻(xiàn)[4]通過(guò)模擬退火算法以基本的方法實(shí)現(xiàn)多源路徑規(guī)劃，在效率上沒(méi)有太多優(yōu)化.

本文基于蟻群的啟發(fā)式搜索算法，引入事件觸發(fā)機(jī)制解決節(jié)點(diǎn)的排序，將其中的部分固定網(wǎng)絡(luò)抽象成一條路徑，縮小解空間的規(guī)模，再將解在空間中以樹(shù)的形式展開(kāi)，構(gòu)建解空間樹(shù)，從而將多起點(diǎn)多終點(diǎn)問(wèn)題轉(zhuǎn)換成單起點(diǎn)單終點(diǎn)問(wèn)題的集合，很好地回避了蟻群信息素的混淆，最后運(yùn)用蟻群算法的啟發(fā)性在解空間樹(shù)上尋優(yōu)，獲得了理想結(jié)果.文中將此算法簡(jiǎn)稱為MSMD(Multi-Sources and Multi-Destinations)算法.

1MSMD算法構(gòu)建

1.1蟻群算法與 MSMD問(wèn)題

蟻群算法是一種基于種群的啟發(fā)式搜索算法，于1996年由意大利學(xué)者M(jìn)ARCO DORIGO 等提出[5].蟻群算法充分利用了蟻群搜索從蟻穴至食物間最短路徑的集體尋優(yōu)特征，并且在求解組合優(yōu)化問(wèn)題中突顯優(yōu)勢(shì).

MSMD問(wèn)題意在求解從某一個(gè)點(diǎn)出發(fā)，先經(jīng)過(guò)多個(gè)起點(diǎn)，到達(dá)多個(gè)終點(diǎn)，完成這些請(qǐng)求的最短路徑.相比于單起點(diǎn)單終點(diǎn)問(wèn)題，有如下特性：

1) 傳統(tǒng)單起點(diǎn)多終點(diǎn)算法只是要求蟻群能最終回到原點(diǎn)，中途點(diǎn)的順序任意，而在MSMD中，中途點(diǎn)的順序有一定要求，起點(diǎn)必須先于終點(diǎn)，其他點(diǎn)之間的順序也是任意的，并且能被多次經(jīng)過(guò)；

2) 一般單起點(diǎn)單終點(diǎn)的路徑搜索問(wèn)題，解空間是有限的.而在MSMD中，路徑可能被往復(fù)，因此解空間無(wú)限；

3) 由于蟻群轉(zhuǎn)移的任意性，存在多次從不同方向經(jīng)過(guò)一個(gè)點(diǎn)的情況，將使這個(gè)點(diǎn)周圍的多個(gè)信息素混合，下一次螞蟻經(jīng)過(guò)這個(gè)點(diǎn)的時(shí)候可能會(huì)被其他信息素所誤導(dǎo)，造成信息素混淆.

1.2MSMD算法構(gòu)建

1) 事件觸發(fā)機(jī)制.算法中若一個(gè)起點(diǎn)有請(qǐng)求，這種請(qǐng)求稱之為該起點(diǎn)的一個(gè)事件.在算法開(kāi)始時(shí)所有的起點(diǎn)作為目標(biāo)點(diǎn)，即蟻群要去往的點(diǎn)，終點(diǎn)和其他點(diǎn)作為非目標(biāo)點(diǎn).當(dāng)蟻群到達(dá)某一個(gè)目標(biāo)點(diǎn)時(shí)，如果該目標(biāo)點(diǎn)是起點(diǎn)，則進(jìn)行事件觸發(fā)操作，即將該起點(diǎn)對(duì)應(yīng)的終點(diǎn)轉(zhuǎn)換成目標(biāo)點(diǎn)，并且將該起點(diǎn)轉(zhuǎn)換成非目標(biāo)點(diǎn)，由此就保證起點(diǎn)和終點(diǎn)的順序，否則會(huì)造成路徑順序倒置.

2) 網(wǎng)絡(luò)路徑抽象.蟻群雖然在地圖上是任意轉(zhuǎn)移的，但是總趨向于某一個(gè)目標(biāo)點(diǎn)前進(jìn)，當(dāng)確定從當(dāng)前點(diǎn)轉(zhuǎn)移到某一個(gè)目標(biāo)點(diǎn)時(shí)，到達(dá)這個(gè)目標(biāo)點(diǎn)的最優(yōu)路徑卻是確定的.因此將起點(diǎn)與終點(diǎn)之間的復(fù)雜網(wǎng)絡(luò)抽象成一條直連的路徑，可以大幅度地減少蟻群的搜索量，其內(nèi)部的網(wǎng)絡(luò)最短路徑計(jì)算就退化成兩點(diǎn)之間求最短距離問(wèn)題.抽象網(wǎng)絡(luò)如圖1所示，圖1中，3個(gè)目標(biāo)站點(diǎn)之間的具體網(wǎng)絡(luò)被抽象成3條路徑，形成簡(jiǎn)單抽象網(wǎng)絡(luò).

圖1　抽象網(wǎng)絡(luò)圖

圖2　解空間樹(shù)

4) 解空間樹(shù)的蟻群搜索.在解空間樹(shù)中，每條分支都獨(dú)立延伸，不存在路徑交叉的情況，路徑規(guī)劃實(shí)際上就是獲得這棵樹(shù)的一條分支.因此不用將蟻群放置到實(shí)際的地圖上進(jìn)行搜索，而是將它放置在解空間樹(shù)的根上，向下搜索到樹(shù)的葉子節(jié)點(diǎn)，從而解決信息素混合的問(wèn)題.從本質(zhì)上看，多起點(diǎn)多終點(diǎn)的問(wèn)題就轉(zhuǎn)換成了單起點(diǎn)單終點(diǎn)的問(wèn)題集合.

圖3　算法流程圖

1.3MSMD算法流程

根據(jù)基本蟻群算法，增加以上策略，設(shè)計(jì)MSMD算法的步驟如圖3所示.

2社區(qū)公交中MSMD算法應(yīng)用

2.1乘客感受系數(shù)和系統(tǒng)目標(biāo)函數(shù)

在社區(qū)公交系統(tǒng)中乘客最關(guān)心的是總花費(fèi)時(shí)間，所以整個(gè)系統(tǒng)不以路徑最短為目標(biāo)，而以乘客感受系數(shù)作為目標(biāo).為此，定義從發(fā)出請(qǐng)求到目的地之間的總花費(fèi)時(shí)間為乘客感受系數(shù).但是由于1個(gè)乘客等待的時(shí)間越久感受會(huì)越差，而且感受與等待時(shí)間的關(guān)系可能不是線性，故設(shè)置感受系數(shù)為k×(時(shí)間)a，構(gòu)造整個(gè)系統(tǒng)的目標(biāo)函數(shù)為：

(1)

式中，k和a表示1個(gè)人隨著時(shí)間變長(zhǎng)而感受變差的快慢系數(shù).Tsi表示第i個(gè)人開(kāi)始等待的時(shí)間，Tei表示第i個(gè)人到達(dá)終點(diǎn)的時(shí)間，n表示乘客的數(shù)量.

2.2多車輛情況下乘客調(diào)度分配算法

當(dāng)1個(gè)社區(qū)的1輛公交無(wú)法滿足需求時(shí)，就需要增加公交數(shù)量，為此需要調(diào)度分配.本文采用Sufferage的算法進(jìn)行請(qǐng)求分配，比如，1個(gè)乘客被分配給某輛車，將造成整個(gè)系統(tǒng)中所有乘客感受系數(shù)增長(zhǎng)的值稱為這種分配的sufferage值.然后判斷比較每種分配的sufferage值，將乘客分配給最小sufferage值的車輛.

3仿真及實(shí)例

編寫(xiě)地圖生成程序和站牌模擬程序，仿真分析主要對(duì)比未優(yōu)化(程序不使用MSMD算法中優(yōu)化策略)和優(yōu)化(采用優(yōu)化的MSMD算法)的情況.兩者采用相同的網(wǎng)絡(luò)狀態(tài)，蟻群均為10只螞蟻50次迭代.

1)仿真實(shí)驗(yàn)1：在100個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)中分別以不同請(qǐng)求數(shù)測(cè)試運(yùn)算時(shí)間.

實(shí)驗(yàn)操作：首先由地圖生成程序隨機(jī)生成擁有100個(gè)節(jié)點(diǎn)120條邊的地圖，然后由站牌模擬程序同時(shí)連接測(cè)試組和對(duì)照組服務(wù)器，發(fā)起隨機(jī)n個(gè)請(qǐng)求，后臺(tái)打印程序運(yùn)行時(shí)間.

實(shí)驗(yàn)結(jié)果與分析：請(qǐng)求數(shù)與運(yùn)算時(shí)間關(guān)系如圖4(a)所示，未優(yōu)化組的運(yùn)行時(shí)間隨著請(qǐng)求數(shù)的增長(zhǎng)不斷增長(zhǎng)，但是由于當(dāng)請(qǐng)求數(shù)達(dá)到一定限度后螞蟻基本上都要走遍所有節(jié)點(diǎn)才能完成，所以在50個(gè)請(qǐng)求之后算法運(yùn)行時(shí)間基本不變；而優(yōu)化算法每增加一個(gè)請(qǐng)求數(shù)，蟻群遍歷時(shí)就多搜索1次，因此運(yùn)算時(shí)間呈線性增長(zhǎng)，圖4(a)中右下圖為優(yōu)化組的圖形放大.

2)仿真實(shí)驗(yàn)2：在不同數(shù)量的網(wǎng)絡(luò)節(jié)點(diǎn)中測(cè)試50個(gè)請(qǐng)求的運(yùn)算時(shí)間.

實(shí)驗(yàn)操作：由地圖生成程序隨機(jī)生成100～500個(gè)節(jié)點(diǎn)不同規(guī)模的地圖，邊數(shù)均為節(jié)點(diǎn)數(shù)的1.5倍.然后由站牌模擬程序同時(shí)連接測(cè)試組和對(duì)照組服務(wù)器，發(fā)起隨機(jī)50個(gè)請(qǐng)求.

實(shí)驗(yàn)結(jié)果與分析：如圖4(b)所示，未優(yōu)化算法隨著網(wǎng)絡(luò)規(guī)模增大螞蟻完成所需要走過(guò)的節(jié)點(diǎn)數(shù)而增長(zhǎng)，因此運(yùn)算時(shí)間也不斷增長(zhǎng)；而優(yōu)化算法通過(guò)路徑抽象忽視了網(wǎng)絡(luò)規(guī)模增大帶來(lái)的影響，其運(yùn)算時(shí)間大致在0.245 s處波動(dòng)，與網(wǎng)絡(luò)規(guī)模無(wú)關(guān)，見(jiàn)圖4(b)右下的局部放大圖.

圖4　請(qǐng)求數(shù)與運(yùn)算時(shí)間關(guān)系圖

把杭州電子科技大學(xué)校園作為1個(gè)大型社區(qū)，進(jìn)行實(shí)際測(cè)試，選取周圍7個(gè)點(diǎn)作為居民常去點(diǎn)，并設(shè)置站牌如圖6所示.

經(jīng)過(guò)實(shí)際測(cè)試，所開(kāi)發(fā)的硬件和軟件系統(tǒng)正常工作，當(dāng)按下實(shí)體站牌按鍵后，服務(wù)器立刻接收到請(qǐng)求，進(jìn)行路徑規(guī)劃，系統(tǒng)響應(yīng)平均時(shí)間為74 ms，規(guī)劃路線均為最優(yōu)路線，并且正確顯示在Android端.圖6為按下2個(gè)實(shí)體站牌后顯示的路徑，其中使用A，B，…，F(xiàn)表示點(diǎn)的順序，車輛起始在A點(diǎn).這說(shuō)明本算法能穩(wěn)定運(yùn)行在該系統(tǒng)中，能有效地完成路徑規(guī)劃任務(wù).

圖5　實(shí)體站牌

圖6　實(shí)際運(yùn)行路徑

4結(jié)束語(yǔ)

本文結(jié)合蟻群算法提出了一種解決社區(qū)公交系統(tǒng)中多起點(diǎn)多終點(diǎn)問(wèn)題的路徑規(guī)劃算法.通過(guò)理論和實(shí)驗(yàn)發(fā)現(xiàn)，本算法具有良好的收斂性和實(shí)時(shí)性，且運(yùn)算效率與網(wǎng)絡(luò)規(guī)模無(wú)關(guān)，能很好地融入到大型的公交網(wǎng)絡(luò)和社區(qū)公交系統(tǒng)中，為智慧小區(qū)建設(shè)提供相應(yīng)的技術(shù)支持.表面上看，此類問(wèn)題僅屬于車輛路徑的一個(gè)分支，但是在現(xiàn)實(shí)生活中，針對(duì)拼車、同城快遞收發(fā)等問(wèn)題，同樣具有現(xiàn)實(shí)指導(dǎo)作用.

參考文獻(xiàn)

[1]TAO C C, CHEN C Y. Heuristic Algorithms for the Dynamic Taxipooling Problem Based on Intelligent Transportation System Technologies[C]//International Conference on Fuzzy Systems and Knowledge Discovery. 2007:590-595.

[2]張瑾,何瑞春.解決動(dòng)態(tài)出租車“拼車”問(wèn)題的模擬退火算法[J].蘭州交通大學(xué)學(xué)報(bào),2008,27(3):85-88.

[3]馮田.基于sufferage的動(dòng)態(tài)出租車拼車調(diào)度算法[J].電腦知識(shí)與技術(shù),2011,7(28):7019-7023.

[4]范麗梅.多源車輛最優(yōu)路徑問(wèn)題研究[J].計(jì)算機(jī)光盤(pán)軟件與應(yīng)用,2012(23):83-84.

[5]DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agents[J]. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 1996, 26(1): 29-41.

DOI：10.13954/j.cnki.hdu.2016.03.017

收稿日期：2015-09-06

基金項(xiàng)目：浙江省新苗人才計(jì)劃資助項(xiàng)目(2014R407038)

作者簡(jiǎn)介：陸乾杰(1993-)，男，浙江嘉興人，本科生，計(jì)算機(jī)科學(xué)與技術(shù).通信作者：陳志平教授，E-mail：chen_zp@hdu.edu.cn.

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001-9146(2016)03-0084-05

Multi-sources and Multi-destinations Route Search in Community Bus Service Based on Ant Colony Algorithm

LU Qianjie, CHEN Zhiping, ZHANG Linjia, WANG Haonan, LIU Chunlu

(SchoolofZhuoyueHonors,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Abstract：In order to solve the embarrassing problem of “the last one kilometer to home”, one kind of community bus system is introduced in this paper. This system aims to search for one optimized route strategy according to different passengers’ starting-points and destinations at the same time. We describe a kind of route search algorithm based on multi-sources and multi-destinations, which is combined with ant colony algorithm. In this new algorithm, we add a series of events’ triggers to solve the order of station-nodes, and then abstract the single path from the two-node fixed network to reduce the solution’s space. We construct one solution’s space tree so that the problem of multi-sources and multi-destinations can be the collections of problems for one-source and one-destination, which can effectively solve the cross problem of ant’s pheromone. Finally we obtain the optimized route by using the heuristic of ant colony algorithm in the solution’s tree to search the routes. Case simulations indicate that the efficiency of this algorithm is related to the number of passengers’ requests, and it doesn’t depend on the size of actual network. So, this algorithm can be well integrated into a large network. The actual experiments show that this algorithm can work well in the community bus system. So it is expected to be applied in the community bus service more and more.

Key words：the last one kilometer to home; multi-sources and multi-destinations; route search; ant colony algorithm