盧鐳，曾暉，劉陽

摘要：城市公交對城市經(jīng)濟(jì)發(fā)展和人民生活水平的提高起著非常重要的作用。但是隨著城市規(guī)模的不斷擴(kuò)大，很多站點(diǎn)難以直達(dá)，且城市人口流動大，給出行人帶來許多不便。該文根據(jù)影響公交出行的主要因素，得出公交出行的最優(yōu)模型，建立一個(gè)公交換乘系統(tǒng)，可實(shí)現(xiàn)公交線路查詢、站點(diǎn)查詢、站點(diǎn)間換乘查詢以及后臺管理功能，使人們能在較短時(shí)間內(nèi)得出最優(yōu)的換乘方案。

關(guān)鍵詞：最短路徑算法；蟻群算法；C#；B/S結(jié)構(gòu)；數(shù)據(jù)庫

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)02-0494-03

Research of Urban Transit Inquiry System

LU Lei，ZENG Hui, LIU Yang

(Jiangxi College of Applied Technology，Ganzhou 341000, China)

Abstract: City bus plays a very important role to urban economic development and improvement of peoples living standard . But with the expansion of cities, so many people are brought inconvenience. Because many sites difficult to direct and urban floating population are foreigners. Based on the main factors affecting bus travel on existing public transport ,they obtained optimal model of bus travel.

Key words: shortest path algorithm; ant colony algorithm; C#; structure of B/S; database

“公交優(yōu)先”的概念首先產(chǎn)生和應(yīng)用于巴黎[1]。早在30年前，我國政府就發(fā)布了優(yōu)先發(fā)展公共交通的產(chǎn)業(yè)和技術(shù)政策，但是由于我國基礎(chǔ)差、底子薄，在交通結(jié)構(gòu)轉(zhuǎn)變過程中也處于劣勢，有些城市甚至還出現(xiàn)了公交萎縮的尷尬局面[2]。

1蟻群算法

1.1蟻群算法概述

蟻群算法（Ant Colony Algorithm,ACA）是由意大利學(xué)者M(jìn).Dorigo等人于20世紀(jì)90年代提出的[3]，是受自然界螞群的覓食行為發(fā)展起來的隨機(jī)搜索算法。

螞蟻?zhàn)鳛槿后w時(shí)，其高度結(jié)構(gòu)化的集體行為讓蟻群展現(xiàn)出超乎個(gè)體的特殊功能[4]。螞蟻會在其經(jīng)過的路線上釋放一種特有的分泌物——信息素（pheromone）,使得在一定范圍內(nèi)的螞蟻能夠感知它的存在及濃度，進(jìn)而向該物質(zhì)濃度強(qiáng)的方向移動。因此某一路徑上螞蟻越多，信息素也就越多，強(qiáng)度也越強(qiáng)，后來的螞蟻選擇該路徑的概率也就越大。蟻群表現(xiàn)出來的這種特性被學(xué)者們稱為“群集智能”（Swam Intelligence,SI）[5].

1.2蟻群算法模型

初始化相關(guān)參數(shù)信息[6]：m為螞蟻的數(shù)量，p為城市數(shù)量，i為螞蟻出發(fā)的城市，j為螞蟻到達(dá)的城市，τij為邊（i,j）路徑上信息素強(qiáng)度，ηij（t）為城市間的啟發(fā)函數(shù)，ρ為信息素?fù)]發(fā)后的殘留因子，α為在螞蟻選擇路徑時(shí)信息素濃度的相對重要性,β為在螞蟻路徑選擇時(shí)路徑長度的相對重要性，allowedk為螞蟻下一步允許選擇經(jīng)過的所有城市的集合[7]。tabuk為螞蟻已走過的城市。allowedk={0，1，2，…，p-1}-tabuk。

j（t）表示t時(shí)刻第k只螞蟻從城市i轉(zhuǎn)移到城市j的概率

經(jīng)過幾個(gè)時(shí)刻，當(dāng)螞蟻k遍歷完所有城市完成一次循環(huán)，需要用更新規(guī)則來更新相應(yīng)路徑上的信息素濃度。

τij(t+n)=ρ×τij(t)+Δτij(t)

(3)

Δτkij(t)為第k只螞蟻在這次循環(huán)中在i,j城市之間路徑上釋放的信息素。

其中Q表示信息素濃度,LK為螞蟻k所經(jīng)過的城市的路徑總長度。

2相關(guān)技術(shù)綜述

2.1蟻群算法的基本流程

Step 1：設(shè)Nc=0，Nc為循環(huán)迭代次數(shù)，Nc=Nc+1

τij（0）= c，τij為每條路徑上的信息素濃度，c為常數(shù)，Δτij=0。

Step 2：隨機(jī)放置k個(gè)螞蟻到起始點(diǎn)上（m為螞蟻總數(shù)）。

Step 3：螞蟻從起始點(diǎn)出發(fā)。

Step 4：Nc=Nc+1。

Step 5：將出發(fā)點(diǎn)的名稱存入訪問站點(diǎn)集合中的第一項(xiàng)，令k=1。

Step 6：讀取訪問站點(diǎn)集合中的最后一個(gè)站點(diǎn)，從弧段表中依次讀取以該站點(diǎn)為起點(diǎn)弧段的終點(diǎn)。

Step 7：判斷螞蟻k是否走過該站點(diǎn)，即終點(diǎn)是否在螞蟻k的訪問站點(diǎn)集合中，

如果是表明螞蟻k經(jīng)過了該站點(diǎn)，繼續(xù)讀取下一個(gè)弧段信息，

如果否，則將該弧段存入被選弧段中。

Step 8：判斷弧段是否掃描完畢，

如果否，則返回Step 6繼續(xù)掃描弧段。

Step 9：根據(jù)被選弧段中各弧段的概率選擇一弧段。

Step 10：判斷是否所有螞蟻都運(yùn)行完畢k>=m?

若是則根據(jù)公式更新剛剛走過的弧段的信息素；若為否則返回k=k+1繼續(xù)運(yùn)行。

Step 11：根據(jù)公式更新每條路徑上信息素的濃度。

Step 12：若滿足約束條件Nc≥Ncmax則進(jìn)入下一步打印最優(yōu)計(jì)算結(jié)果；若為否則跳轉(zhuǎn)到Step 4。

3系統(tǒng)總體設(shè)計(jì)

3.1系統(tǒng)設(shè)計(jì)

該系統(tǒng)的具體開發(fā)流程如圖1。圖1系統(tǒng)開發(fā)流程圖

一是將需求功能的分析結(jié)果，作為設(shè)計(jì)系統(tǒng)的總體框架的依據(jù)；二是分別設(shè)計(jì)數(shù)據(jù)表和數(shù)據(jù)庫；三是將模塊的開發(fā)設(shè)定為三層B/S結(jié)構(gòu)：設(shè)計(jì)數(shù)據(jù)層、建立業(yè)務(wù)邏輯層、設(shè)計(jì)表示層[8]。3.2系統(tǒng)功能模塊劃分

3.2.1城市公交系統(tǒng)的活動對象相互影響相互制約

1）管理決策者

由政府交通管理局等相關(guān)管理部門構(gòu)成，主要負(fù)責(zé)制定并監(jiān)督實(shí)施公交系統(tǒng)各項(xiàng)政策法規(guī)。2）運(yùn)行者

由公交汽車公司構(gòu)成，主要負(fù)責(zé)日常時(shí)刻表制定、車輛調(diào)度等工作。

3）使用者

乘客可以根據(jù)系統(tǒng)平臺中查詢得到的信息來選擇出行方式。因此，乘客盡可能多的獲得實(shí)時(shí)動態(tài)信息將對出行產(chǎn)生重要影響。

3.2.2系統(tǒng)功能模塊劃分

1）查詢系統(tǒng)模塊

用戶輸入需要查詢的公交線路，系統(tǒng)可查詢出該線路的始發(fā)車、末班車時(shí)間，發(fā)車時(shí)間間隔，途徑的所有站點(diǎn)。

用戶輸入需要查詢的公交站點(diǎn)，系統(tǒng)可查詢出該站點(diǎn)的相關(guān)信息，包括經(jīng)過該站點(diǎn)的所有車次、該站點(diǎn)是否為起始站點(diǎn)等信息。

用戶在系統(tǒng)中輸入任意兩公交站點(diǎn)，系統(tǒng)將以這兩點(diǎn)為起始點(diǎn)和終點(diǎn)按站點(diǎn)距離短優(yōu)先給出可行的換乘路線。

2）管理模塊

新增、編輯：系統(tǒng)具有很好的擴(kuò)展性，允許管理員對線路、站點(diǎn)、車輛參數(shù)等數(shù)據(jù)信息進(jìn)行操作，以保證數(shù)據(jù)的實(shí)時(shí)性，增強(qiáng)系統(tǒng)的可靠性。

495

刪除：允許管理員對車次、站名進(jìn)行操作，以保證數(shù)據(jù)的實(shí)時(shí)性。

4實(shí)現(xiàn)過程

用戶在起點(diǎn)站中選擇輸入出發(fā)點(diǎn)，在終點(diǎn)站輸入終點(diǎn)，起始點(diǎn)和終點(diǎn)站的ID參數(shù)便傳入系統(tǒng)。實(shí)現(xiàn)兩站點(diǎn)查詢過程可分為三步[9-11]，第一步：得出所有可能的途徑車站列表；第二步：從起始點(diǎn)開始遞歸搜尋所有可能線路；第三步：調(diào)用算法求所有線路的權(quán)重并排序。如果這兩個(gè)站點(diǎn)間可以直達(dá)或者通過換乘到達(dá)，則給出相應(yīng)的出行線路，排在前面的線路根據(jù)蟻群算法檢測到距離比其他線路更優(yōu)；如果沒有直達(dá)車，系統(tǒng)則不給出公交出行線路。

參考文獻(xiàn)：

[1]北京公交斥巨資走公益發(fā)展模式[EB/OL].(2007-10-18).http://www.enorth.com.cn.

[2]匡星.城市常規(guī)公共交通服務(wù)水平研究[D].長春:吉林大學(xué),2004.

[3] Dorigo M,Mnaiezzo V,Colonri A.The Ant System: Optimization by A Colony of Coopearting Agents[C]//IEEE Transactions on Systems,Man, and Cybernetics,1996,1(26):29-41.

[4] Dorigo M，Bonabeau E,Theraulaz G.Ant algorithms and stigmergy[J].Future Generation Computer System,2000,16(8):851-871.

[5] Bonabeau E,Dorigo M,Theraulaz G.Swarm intelligence: from natural to artificial systems[M].New York:Oxford University Press,1999.

[6]何勝學(xué),范炳全.公交網(wǎng)絡(luò)最優(yōu)路徑求解算法螞蟻算法[J].交通運(yùn)輸工程與信息學(xué)報(bào),2007,5(1):22-27.

[7]陳業(yè)紅.螞蟻算法的理論模型與收斂性的初步探討[J].山東輕工業(yè)學(xué)院學(xué)報(bào),2006,20(1):77-81.

[8]汪江洪.公交換乘系統(tǒng)研究及其評價(jià)[D].成都:西南交通大學(xué),2006.

[9]徐鋒,杜軍平.改進(jìn)蟻群算法在旅游路線規(guī)劃中的應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用,2009(23).

[10]何勝學(xué),范炳全.公交網(wǎng)絡(luò)最優(yōu)路徑求解算法[J].交通運(yùn)輸工程與信息學(xué)報(bào).2007,5(1):22-27.

[11]張軍,胡曉敏.蟻群優(yōu)化[M].北京:清華大學(xué)出版社,2007.