基于MAS的智能公交調(diào)度系統(tǒng)的建模與實現(xiàn)*

王向華，陳特放

(中南大學(xué)交通運(yùn)輸工程學(xué)院，湖南 長沙 410013)

基于MAS的智能公交調(diào)度系統(tǒng)的建模與實現(xiàn)*

王向華，陳特放

(中南大學(xué)交通運(yùn)輸工程學(xué)院，湖南 長沙 410013)

城市公共交通具有結(jié)構(gòu)復(fù)雜、并發(fā)性和分布性等特點(diǎn)，使用數(shù)學(xué)建模的方法很難有效解決其調(diào)度問題，而多Agent系統(tǒng)MAS是一種解決復(fù)雜系統(tǒng)問題的有效方式，因此應(yīng)用MAS來解決公交調(diào)度問題。首先，建立了城市公交系統(tǒng)的概念模型；然后，根據(jù)MAS的建模思想對公交調(diào)度相關(guān)實體進(jìn)行抽象，建立了智能公交調(diào)度系統(tǒng)的MAS模型，并給出了Dispatch Agent、Bus Agent和Stop Agent的建模方法以及知識庫的構(gòu)建、推理和學(xué)習(xí)的流程；最后，完成系統(tǒng)實現(xiàn)。

MAS；智能公交調(diào)度系統(tǒng)；建模；JADE

1 引言

城市化作為重塑現(xiàn)代社會的三大力量之一[1]，在推動社會進(jìn)步的同時，也帶來交通擁堵的城市病。交通擁堵導(dǎo)致交通運(yùn)輸效益降低、市民出行困難、汽車燃料消耗增加和環(huán)境污染日益加劇。智能公交系統(tǒng)APTS(Advanced Public Transportation System)作為智能交通系統(tǒng)ITS(Intelligent Transportation System)在城市交通管理上的具體應(yīng)用，被認(rèn)為是解決城市交通擁堵的一種有效方式[2]。APTS是應(yīng)用全球定位技術(shù)、無線通信技術(shù)、地理信息技術(shù)和計算機(jī)等技術(shù)，實現(xiàn)公交車輛運(yùn)營調(diào)度的智能化和可視化，同時，為乘客提供完整的出行信息服務(wù)。然而，城市公共交通系統(tǒng)具有結(jié)構(gòu)復(fù)雜性、并發(fā)性和調(diào)度方式多樣性等諸多特點(diǎn)，很難有效解決其調(diào)度問題。目前，我國的公交調(diào)度智能化程度還很低，對公交車輛的調(diào)度還停留在兩點(diǎn)一線上，對公交調(diào)度的應(yīng)用研究還停留在靜態(tài)公交調(diào)度時刻表編制、發(fā)車頻率的優(yōu)化上，這種方式并不能適應(yīng)動態(tài)多變的公交運(yùn)行情況。MAS(Multi-Agent System)具有很強(qiáng)的自治性和適應(yīng)性，能處理不可預(yù)測的、動態(tài)改變的環(huán)境中的問題[3～6]。因此，將MAS技術(shù)引入到公交調(diào)度系統(tǒng)來解決公交調(diào)度問題，針對我國城市公共交通的特點(diǎn)，設(shè)計了一種基于MAS的城市公交智能調(diào)度系統(tǒng)，該系統(tǒng)具有良好的自適應(yīng)能力，能根據(jù)外部環(huán)境的變化，對運(yùn)行中的公交車輛進(jìn)行動態(tài)調(diào)度和實時誘導(dǎo)，從而提高公交車輛的運(yùn)行效益，減少交通擁堵。

2 Agent和MAS

Agent自Minsky在1986年提出以來，在人工智能&分布式人工智能AI&DAI(Artificial Intelligence& Distributed Artificial Intelligence)、分布計算、人機(jī)交互、計算機(jī)支持協(xié)同工作CSCW(Computer Supported Collaborative Work)、虛擬現(xiàn)實、數(shù)據(jù)挖掘以及軟件工程等領(lǐng)域得到了很大的發(fā)展。雖然人們從社會智能、知識處理、擬人性等角度給予了Agent 不同的定義[4～6 ]，到目前為止學(xué)術(shù)界尚未給出有關(guān) Agent 的統(tǒng)一而確切的概念。盡管不同領(lǐng)域?qū)gent 理解存在一定的區(qū)別，但大多數(shù)研究者都認(rèn)為Agent 是一種計算實體(Entity)，它能夠為了某個意圖持續(xù)、自主地進(jìn)行操作，具有學(xué)習(xí)能力并且與其它Agent 并存和相互作用；多個Agent通過相互協(xié)調(diào)合作而構(gòu)成的系統(tǒng)就叫多Agent系統(tǒng)MAS, MAS的問題求解能力可以大于各個 Agent個體所具有的問題求解能力的簡單相加。從本文所探討的角度而言，Agent 代表的是存在于公交調(diào)度環(huán)境中的真實或抽象的實體，每個 Agent都能夠主動、自治地活動，各Agent 可以在一定的環(huán)境中相互合作，共同完成公交運(yùn)輸調(diào)度服務(wù)。

3 城市公共交通的概念模型

城市交通系統(tǒng)是由人和交通工具等組成的動態(tài)復(fù)雜系統(tǒng)，具有影響因素多、開放性強(qiáng)、隨機(jī)及不確定因素多等特點(diǎn)。根據(jù)城市公共交通的實際運(yùn)行環(huán)境，設(shè)計出如圖1所示的概念模型。

整個城市公共交通系統(tǒng)包括如下幾個模塊：(1)GPS導(dǎo)航監(jiān)控系統(tǒng)；(2)3G無線網(wǎng)絡(luò)信息支撐平臺；(3)智能化的公交車輛系統(tǒng)； (4)智能化的站臺系統(tǒng)；(5)交通指揮中心；(6)智能化的公交調(diào)度中心。其中涉及公交調(diào)度的主要有調(diào)度系統(tǒng)、智能公交車和智能站臺這三部分。

Figure 1 Concept model of urban public transportation圖1 城市公共交通系統(tǒng)的概念模型

4 基于MAS的公交調(diào)度系統(tǒng)建模

城市公交系統(tǒng)是由公交車輛、公交站點(diǎn)和調(diào)度中心等組成的復(fù)雜系統(tǒng)，具有隨機(jī)性影響因素多、分布式和開放性等特點(diǎn)，用傳統(tǒng)的方式很難對其進(jìn)行有效的建模。而Agent是比對象更高一級的抽象，它是一個主動(Active)對象，有自己信念和意愿[4～6]，多個Agent可以相互合作，組成一個社會，可以解決單個Agent無法解決的問題。

基于MAS的建模是一種自下而上的建模方法，其建模流程如下：(1)識別系統(tǒng)中所有反映問題域和系統(tǒng)責(zé)任的Agent；(2)定義Agent的結(jié)構(gòu)與特征，包括內(nèi)部狀態(tài)(數(shù)據(jù)、變量)和行為規(guī)則(函數(shù)、方法等)；(3)確定組成MAS的Agent群體所采用的體系結(jié)構(gòu)，即Agent之間的通信與協(xié)調(diào)等問題。

Agent抽象的基本原則是：從系統(tǒng)的物理結(jié)構(gòu)出發(fā)，圍繞著系統(tǒng)的目標(biāo)來對系統(tǒng)進(jìn)行抽象。以系統(tǒng)的物理結(jié)構(gòu)作為抽象的基本點(diǎn)，即根據(jù)物理世界的實際構(gòu)成來劃分Agent邊界。根據(jù)這個抽象原則，將上節(jié)的調(diào)度系統(tǒng)中的實體抽象成為三個主要Agent，即Bus Agent、Stop Agent和Dispatch Agent。建立公交智能調(diào)度系統(tǒng)的MAS模型如圖2所示。

Figure 2 MAS model of intelligent dispatch system圖2 公交智能調(diào)度系統(tǒng)的MAS模型

為了滿足車輛調(diào)度實時性的要求，對調(diào)度過程分解為實時發(fā)車和路上實時行車誘導(dǎo)，分別由Dispatch Agent和Bus Agent負(fù)責(zé)各自的任務(wù)。本系統(tǒng)中Dispatch Agent處于主導(dǎo)地位，它負(fù)責(zé)某一公交線路上與發(fā)車相關(guān)的調(diào)度操作，每次發(fā)車的同時將該車的Bus Agent 注冊到MAS中；Stop Agent 負(fù)責(zé)站點(diǎn)客流量采集以及車輛到站時間預(yù)告；Bus Agent負(fù)責(zé)車輛滿載率以及車輛在線路中運(yùn)行的交通信息等數(shù)據(jù)的采集，Bus Agent之間協(xié)同合作完成公交車輛的動態(tài)誘導(dǎo)。

4.1 Dispatch Agent建模

Dispatch Agent 是整個公交調(diào)度系統(tǒng)的核心部分，是實現(xiàn)公交調(diào)度任務(wù)的主要承擔(dān)者。由于調(diào)度需要大量的計算，因此采用慎思型Agent模型(BDI Agent), 該類模型具有信念(Belief，即情景模式)、愿望(Desire，即任務(wù)目標(biāo))、意圖(Intention，即為實現(xiàn)愿望而想做的事情)和知識庫的特點(diǎn)。針對公交調(diào)度的實際情況，設(shè)計的Dispatch Agent結(jié)構(gòu)如圖3所示。

Figure 3 Structure model of Dispatch Agent圖3 Dispatch Agent 的結(jié)構(gòu)模型

各部分的功能如下：

信念庫：用于情景模式的設(shè)定，如上班早高峰、平常時段、下班早高峰、下班高峰、低谷時段、節(jié)假日以及季節(jié)、氣溫等模式的定義。

愿望庫：即公交調(diào)度的任務(wù)目標(biāo)，各情景模式下乘客期望的最少候車時間，這些數(shù)據(jù)可來源于問卷調(diào)查和行政指標(biāo)；同時也有公交運(yùn)營公司經(jīng)濟(jì)效益的要求。

意圖庫：即為各種調(diào)度方案，例如：A方案，每5分鐘發(fā)車一趟；B方案，每3分鐘發(fā)車一趟。

知識庫：包括兩部分，一部分是成功案例，一部分是推理規(guī)則即信念到意圖的匹配原則。

本文采用產(chǎn)生式(Production Rule)規(guī)則來進(jìn)行知識表示，其基本形式如下：

P→Q或 IFPTHENQ

其中，P是產(chǎn)生式的前提或條件，用于指出該產(chǎn)生式是否是可用的條件；Q是一組結(jié)論或動作，用于指出該產(chǎn)生式的前提條件P被滿足時，應(yīng)該得出的結(jié)論或應(yīng)該執(zhí)行的操作。由于產(chǎn)生式具有自然性、 模塊性、有效性、清晰性的優(yōu)點(diǎn)，目前產(chǎn)生式表示法已成為人工智能中應(yīng)用最多的一種知識表示方法。

Dispatch Agent的決策和自學(xué)習(xí)流程如圖4所示。

Figure 4 Decision and study of the Dispatch Agent圖4 Dispatch Agent 的決策和自學(xué)習(xí)流程

(1)成功案例存在情況(即情景模式匹配)：IF(春秋常日AND上班早高峰AND各站點(diǎn)客流量正常)THEN(選擇A方案)。

(2)成功案例不存在情況：IF(春秋常日AND上班早高峰 AND 某站點(diǎn)客流量超量)THEN(根據(jù)超量程度，計算發(fā)車間隔)。這個案例完成后，進(jìn)行效用評估，計算此次決策的乘客滿意度和運(yùn)營經(jīng)濟(jì)效益，并給該案例評估打分，如果滿足要求則將該案例存入備選案例，當(dāng)下次遇到同樣的情景，則在備選方案上優(yōu)化，多次優(yōu)化之后，選擇一個最優(yōu)秀的方案存入成功案例庫，這就是Dispatch Agent的學(xué)習(xí)過程。

4.2 Bus Agent建模

Bus Agent 是根據(jù)實際公交線路中公交車輛的駕駛行為而抽象出來的智能實體，能獲取外界環(huán)境信息，并且擁有自己的知識和決策判斷能力，可根據(jù)周圍的環(huán)境變化實時調(diào)整自己的駕駛行為。由于公交車輛在線運(yùn)行，需要的計算能力要求不高但實時性要求比較高，針對一些特定的緊急事件需要進(jìn)行快速反應(yīng)，因此Bus Agent采用混合型Agent模型，如圖5所示。該模型是在慎思型Agent結(jié)構(gòu)的基礎(chǔ)上增加了快速反應(yīng)功能。

Figure 5 Structure model of the Bus Agent圖5 Bus Agent 的的結(jié)構(gòu)模型

各部分的功能如下：

信念庫：用于公交車輛行駛模式的設(shè)定，如跟車模型、超車模型以及讓車模型等的定義。

愿望庫：即本次行車的任務(wù)目標(biāo)，發(fā)車時從Dispatch Agent處獲得，本文主要指本車到達(dá)各站點(diǎn)的預(yù)定時間以及與前車到站時間間隔，其中保證公交車輛到站時間的先后間隔是防止串車和大間隔的關(guān)鍵。

意圖庫：即為各種行駛模式的具體行駛操作，例如：方案A，加速；方案B，減速。

反應(yīng)器：用于對一些緊急事件的處理，例如：車輛故障等需要進(jìn)行應(yīng)急處理的情況。

其知識庫的構(gòu)建、推理和學(xué)習(xí)流程和Dispatch Agent類似。

4.3 Stop Agent建模

由于Stop Agent的功能比較簡單，只需要采集客流量、交通狀況等信息，再根據(jù)公交的運(yùn)行情況，發(fā)布公交到站信息，不需要知識也不需要推理，因此采用帶狀態(tài)的反應(yīng)型Agent模型。其模型結(jié)構(gòu)如圖6所示。

Figure 6 Structure model of Stop Agent圖6 Stop Agent 的結(jié)構(gòu)模型

其行為主要有兩個：一個是定時驅(qū)動的，查詢某線路將到達(dá)車輛的信息，更新到達(dá)時間；另外一個是事件驅(qū)動，當(dāng)車輛到站上下車服務(wù)完成后，更新自己的站點(diǎn)客流量信息。

5 基于MAS公交調(diào)度系統(tǒng)的實現(xiàn)

5.1 Agent之間的通信語言選擇

Agent之間常見的通信語言主要有兩種，一種是KQML(Knowledge Query and Manipulation Language)；另一種是FIPA(Foundation for Intelligent Physical Agents)[7]協(xié)會制定的FIPA-ACL (Agent Communication Language)。FIPA-ACL在構(gòu)建新的原語方面具有很強(qiáng)的能力，而且FIPA-ACL的開發(fā)者可通過語義語言SL(Semantic Language)形式語言來表示一個Agent的信念、愿望和意圖，以及這個Agent執(zhí)行的動作。本文采用FIPA-ACL作為Agent之間的通信語言。

一個通信實例：

(inform

:sender DispatchAgent1

:receiver BusAgent2

:content Bus schedule

:language SL

)

DispatchAgent1調(diào)度Bus2發(fā)車時，將Bus2的發(fā)車時刻以及預(yù)計到達(dá)在各站點(diǎn)的時刻表發(fā)給BusAgent2，按時刻表運(yùn)行就是Bus Agent運(yùn)行的意圖。

5.2 MAS中各Agent之間協(xié)作模式的選擇

由于Agent之間信念、目標(biāo)不同或者同時共享有限資源都有可能造成沖突，因此我們需要采用一種協(xié)調(diào)的方式來消除沖突。MAS中Agent的協(xié)作模式主要有合同網(wǎng)、市場機(jī)制以及黑板模型等幾種。

本文選擇黑板模型，其基本思想是：黑板是一個共享的問題求解工作空間，各Bus Agent都能看到黑板。當(dāng)問題和初始數(shù)據(jù)記錄到黑板上，如前方站點(diǎn)客流量信息，求解開始，即將到來的Bus Agent通過看自身狀態(tài)(當(dāng)前滿載率)和知識推理一個解決方法，當(dāng)它無法解決時，由其后方的Bus Agent繼續(xù)求解，重復(fù)這一過程直到問題徹底解決，獲得最終結(jié)果。

下面是一個基于黑板模型的超車實例：

提出問題：站點(diǎn)i，提出問題，本站客流量。

求解過程：Bus Agentj，根據(jù)本車狀況(滿載率等)，查詢知識庫，能否滿足站點(diǎn)的運(yùn)輸任務(wù)，能則答復(fù)ok，否則答復(fù)no。

Bus Agentj+1，查看到前車的答復(fù)為no，根據(jù)本車狀況能否滿足站點(diǎn)的運(yùn)輸任務(wù)，能則答復(fù)ok，同時和前車協(xié)商，發(fā)出超車信號。

結(jié)果：超車完成后，i、j的位置信息互換，信念更新。每一趟車過站后，Stop Agent更新狀態(tài)信息。

5.3 開發(fā)工具的選擇

本文選擇TILAB(Telecom Italia LAB)發(fā)布的開放源代碼軟件JADE(Java Agent Development Framework)[8]作為公交調(diào)度系統(tǒng)的開發(fā)工具。

JADE是一個純Java實現(xiàn)的符合FIPA智能體規(guī)范的MAS軟件開發(fā)框架，它提供了與FIPA兼容的Agent平臺與開發(fā)Agent的軟件包。

公交調(diào)度系統(tǒng)是一個分布式的系統(tǒng)，Dispatch Agent運(yùn)行在調(diào)度中心的服務(wù)器上，Bus Agent運(yùn)行在車載JVM上，Stop Agent則運(yùn)行在電子站牌的JVM上。使用JADE可以方便快捷地進(jìn)行系統(tǒng)的開發(fā)和部署。

5.4 公交調(diào)度系統(tǒng)體系結(jié)構(gòu)

公交調(diào)度系統(tǒng)的體系結(jié)構(gòu)如圖7所示。

Figure 7 Architecture of bus dispatch system圖7 公交調(diào)度系統(tǒng)的體系結(jié)構(gòu)

包括如下三層：

(1)硬件層。包括硬件及其上運(yùn)行的Java虛擬機(jī)JVM(Java Virtual Machine)。

(2)JADE平臺層。一個平臺可以有多個容器，而且這些容器可以分布在不同的主機(jī)上，在一個平臺中，有且僅有一個主容器，當(dāng)其他的容器啟動時，必須在主容器中注冊。

(3)Agent應(yīng)用層。由容器上運(yùn)行的各種Agent應(yīng)用組成，AMS(Agent Management System)、DF(Directory Facilitator)是主容器中運(yùn)行的特殊Agent，分別提供Agent管理和黃頁服務(wù)，Dispatch Agent、Bus Agent、Stop Agent以及Interface Agent都在這一層運(yùn)行。

6 結(jié)束語

交通系統(tǒng)是由道路、交通車輛、人以及相關(guān)設(shè)備等組成的動態(tài)復(fù)雜的系統(tǒng)，MAS理論的出現(xiàn)和發(fā)展為交通系統(tǒng)調(diào)度的研究提供了一種新的思路和方法，盡管將MAS技術(shù)引入智能交通系統(tǒng)進(jìn)行仿真研究早就有了。但是，將MAS計算用于現(xiàn)實應(yīng)用還少有成功案例，將MAS用于解決智能公交調(diào)度的現(xiàn)實問題是本研究的一種新的探索。

本文研究的基于MAS的智能公交調(diào)度系統(tǒng)具有一定的自適應(yīng)和自學(xué)習(xí)能力，其采用自然建模的方式能較好地解決公交調(diào)度模型的抽象和表示，比傳統(tǒng)的數(shù)學(xué)建模方式具有更好的靈活性和適應(yīng)性；將調(diào)度任務(wù)分解并由分布環(huán)境中不同的Agent來完成各自的任務(wù)，比集中式的調(diào)度方式具有更好的準(zhǔn)確性和魯棒性。

[1] Borja J, Castells M. Local and global management of cities in the information age[M]. London:Earthscan, 1997.

[2] Yang Zhao-shing. Theories and methods of urban intelligent public transportation system[M]. Beijing:China railway Publishing House,2004. (in Chinese)

[3] Yao Jun,Lü Zhi-lin,Ye Yan.Model for bus dispatching based on satisfaction[J].Journal of Transport Information and Safety, 2009,27(4):67-69. (in Chinese)

[4] Mao Xin-jun, Hu Cui-yun, Sun Yao-kun, et al. Research on agent-oriented programming[J]. Journal of Software, 2012,23(11):2285-2904. (in Chinese)

[6] Wooldridge M. An introduction to multi-agent systems[M]. United Kingdom:John Wiley & Sons Ltd,2009.

[7] Foundation for intelligent physical agents, FIPA application specifications[EB/OL].[2013-03-02]. http://www.fipa.org/repository/applicationspecs.php.

[8] Java agent development framework[EB/OL]. [2013-03-28].http://jade.tilab.com/.

附中文參考文獻(xiàn):

[2] 楊兆升.城市智能公共交通系統(tǒng)理論與方法[M]. 北京:中國鐵道出版社,2004.

[3] 姚俊，呂智林，葉嫣.基于滿意度的公交車調(diào)度模型研究[J].交通信息與安全,2009,27(4):67-69.

[4] 毛新軍，胡翠云，孫耀坤，等.面向Agent程序設(shè)計的研究[J].軟件學(xué)報,2012,23(11):2285-2904.

WANGXiang-hua,born in 1979,PhD candidate,his research interests include software engineering，and intelligent transportation.

陳特放(1957 -),男,湖南漣源人，博士，教授，研究方向為鐵路運(yùn)輸、自動化技術(shù)和智能交通。E-mail:ctfcyt@163.com

CHENTe-fang,born in 1957 ,PhD,professor,his research interests include railway transportation, automation technology, and intelligent transportation.

ModelingandimplementationofintelligentbusdispatchsystembasedonMAS

WANG Xiang-hua，CHEN Te-fang

(School of Transportation Engineering,Central South University,Changsha 410013,China)

Urban public transportation system features complex structure,concurrent processing and diversity, so it is difficult to solve the dispatching problem effectively.MAS is an effective method to solve complex system problems so that it is used to solve the bus dispatching problem.Firstly, a system framework of intelligent bus dispatch system is designed.Secondly,a MAS model is abstracted from the intelligent bus dispatch system framework,and the modeling method of dispatch agent, bus agent and stop agent is introduced,and the process of construction, reasoning,and learning of knowledge base. Finally,the system is implemented.

multi-agent system;intelligent bus dispatch system;modeling;JADE

1007-130X(2014)05-0986-05

2013-03-13;

：2013-07-05

國家自然科學(xué)基金資助項目(60674003)

TP182

：A

10.3969/j.issn.1007-130X.2014.05.033

王向華(1979-),男,湖南漣源人，博士生，研究方向為軟件工程和智能交通。E-mail:wxh105@sina.com

通信地址：410013 湖南省長沙市中南大學(xué)交通運(yùn)輸工程學(xué)院

Address:School of Transportation Engineering,Central South University,Changsha 410013,Hunan,P.R.China