智能体技术在公交调度系统中的应用
王向华1, 2，陈特放1, 3
(1. 中南大学 交通运输工程学院，湖南 长沙，410013；
2. 湖南工学院 计算机信息与科学学院，湖南 衡阳，421002；
3. 中南大学 信息科学与工程学院，湖南 长沙，410013)
摘要：基于智能体(Agent)作为一个有意识的计算主体，具有个体的自治性和群体的社会性等特点，能处理不可预测的、动态变化的环境中的问题，将智能体技术引入公交调度系统中以解决公共交通中的调度难题。首先，通过对城市公共交通调度的实际运行环境进行分析和抽象，设计出智能公交调度系统的概念模型；然后，应用Agent的建模思想对概念模型中相关实体进行抽象，建立智能公交调度系统的多Agent系统模型，并给出DispatchAgent，BusAgent和StopAgent的建模方法以及知识库的构建、推理和学习的流程；最后，使用JADE开发工具实现Agent系统。
关键词：Agent；智能公交；调度系统；建模
中图分类号：U495 文献标志码：A 文章编号：1672-7207(2013)08-3539-07
Application of intelligent public transportation dispatch system based on agent
WANG Xianghua1, 2, CHEN Tefang1, 3
(1. School of Transportation Engineering, Central South University, Changsha 410013, China;
2. School of Computer Information and Science, Hunan Institute of Technology, Hengyang 421002, China;
3. School of Transportation Engineering, Central South University, Changsha 410013, China)
Abstract: As a conscious computing object, Agent has autonomy and social characteristics, that can deal with the problems in the unpredictable and dynamical environment, and the public transportation system is a complex system. Therefore, the agent technology was used to solve the dispatching problem of public transportation system. Firstly, according to the actual operating environment of the urban public transportation system, a concept model of the intelligent public transportation dispatch system was designed; And then, by applying the modeling theory of the agent to abstract the related entities in the concept model, a multi-agent system model of the intelligent public transportation dispatch system including the DispatchAgent, BusAgent and StopAgent, and described the construction of the knowledge base, reasoning and learning process was established; At last, the system implementation was finished by JADE.
Key words: Agent; intelligent public transportation; dispatch system; modeling
公交调度实质上是一个多目标规划问题，要求满足乘客的行车成本越低越好、乘客满意度最高越好以及运营成本越低越好[1-2]。国内对其的研究主要分为3个阶段：第1阶段，主要基于静态模型，对乘车成本和运营成本进行优化，确定发车时刻表等[3-5]；第2阶段，由于上述模型不能反映客流分布的不均匀性，为了节省运营成本和改善服务质量，基于站点客流量预测，对发车频率和间隔进行动态调整等[6-8]；第3阶段，公交优先政策的提出，其目的是为了提高公交系统对出行者的吸引力，从而提高公交出行分担率，此时，乘客满意度在调度中占的权重就越来越高。因此，除了动态发车调度之外，还需要综合考虑路网状况、司机驾驶偏好等随机因素的对公交运行的影响，此外，还需要对公交线路上运行中的公交车辆进行动态行车诱导控制，减少大串车、大间隔的发生，提高公交的准点率[9-10]。尽管人们对公交调度的理论研究很多，但由于实际运行中的公交系统是一个复杂系统，其运行环境多变，经常会受到各种随机不确定的因素的影响，某一次的最优调度并不一定适用于下一调度情况，因此，这些研究成果并不能很好地应用于现实生活中，直到目前，我国的公交调度系统大多数还是采用“定点发车、两头卡点”的手工作业调度方式，经常导致“大间隔”和“大串车”现象的出现，严重影响了公交服务质量。为此，本文作者从软件工程的角度，提出一种基于Agent的解决方法。
1 Agent和多Agent系统
Agent自Minsky在1986年提出以来，在人工智能、分布计算、人机交互、CSCW(computer supported collaborative work，计算机支持协调工作)、虚拟现实、数据挖掘以及软件工程等领域得到了很大的发展。虽然人们从社会智能、知识处理、拟人性等角度给予了Agent 不同的定义[11-13]，到迄今为止学术界尚未给出有关 Agent 的统一而确切的概念。尽管不同领域对Agent 理解存在一定的区别，但大多数研究者认为Agent 是一种计算实体(entity)，它能够为了某个意图持续、自主地进行操作，具有学习能力并且与其他Agent 并存和相互作用。多个Agent通过相互协调合作而构成的生态系统叫多Agent系统(multi-Agent system)，它可以解决由单个Agent无法解决的复杂问题，被认为是解决复杂系统的一种有效方式。图1所示为一个多Agent系统示意图。
图1 多Agent系统示意图
Fig. 1 Multi-Agent system diagram
从本文所探讨的角度来说，Agent 代表的是存在于公交调度环境中的真实或抽象的实体，每个 Agent都能够主动、自治地活动，各Agent 可以在一定的环境中相互合作，共同完成公交运输服务。
2 公交调度系统的概念模型
通过对城市公共交通的运行情况极其调度流程进行调研，对主体进行抽象，设计了如图2所示的概念模型。
图2 城市公共交通调度的概念模型
Fig. 2 Concept model of urban public transportation
整个城市公共交通调度系统包括GPS导航监控系统、3G无线网络信息支撑平台、智能化的公交车辆系统、智能化的站台系统、交通指挥中心、智能化的公交调度中心等几个模块。
(1) GPS导航监控系统，由车载GPS终端和管理控制中心的GIS系统(geographic information system，地理信息系统)组成。通过GIS系统能够实时监控运行中的公交车辆，能将车辆运行情况动态的显示在数字地图之中，并保存于数据库中。
(2) 3G无线网络，为公交调度系统各模块提供无线通信服务。
(3) 智能化的公交车辆系统，主要包括GPS定位终端、3G通信模块、车载摄像头、电子显示屏、自动报站设备、自动乘客计数器、IC读卡器和各类传感器。其主要实现如下功能如下：1) 实时传输GPS采集的位置信息给公交调度中心，以便调度中心的GIS系统就能动态地显示该车辆的运行状态，如位置、速度、方向、时间等；2) 采集行车状况，如车外道路是否拥堵及车内的乘客的拥挤程度；3) 提供自动报站服务和自动乘客计数计数服务；4) 车辆故障检测。车载计算机能将这些采集的数据，传送给公交调度中心作为智能调度的实时数据输入。
(4) 智能化的站台系统，主要包括电子站牌、站台摄像头、3G通信模块和其他传感器等。本模块主要负责站点客流量的数据采集和提供便民服务，如：站台摄像头主要用于采集公交站点的客流量、站点乘客拥挤度以及站点的路况信息；站台传感器用于测量气温、湿度、风向等数据，并将数据显示于电子站牌的显示屏上；电子站牌能够接受公交调度中心信息，显示下一趟公交车的预计到达时间和车厢拥挤度，为乘客提供公交转乘等查询服务。另外，电子站牌还能发布政府通知，交通信息、天气信息以及广告等便民服务。这些采集的数据将通过3G通信模块上传到公交调度中心作为智能调度的实时数据输入。
(5) 交通指挥中心，是政府的交通管理部门，通过无线传感网络、路口线圈以及摄像头采集的数据，实时发布路网交通流量信息，设置公交专用道，控制交通信号灯，对城区重点路段、公交客流量较大的主干道进行公交优先信号配置，减少公交车辆在交叉口的延误，提高公交车辆的通行速度。
(6) 智能化的公交调度中心，能够根据季节、天气气候、每日高峰时段、节假日、路网信息、交通管制信息、站点客流量、车厢拥挤度等，对公交车辆进行动态调度和实时行车诱导。
智能化的公交调度系统是整个城市公共交通系统的核心部分，没有智能化的公交调度系统的支持，各个模块将会是一个个信息孤岛，不能发挥智能公交系统的优势。
3 公交调度系统的建模与实现
城市公交系统是由公交车辆、公交站点和调度中心等组成的复杂系统，具有随机性影响因素多、分布式和开放性等特点，用传统的数学建模方式只能解决其发车的问题，使用集中式监控和诱导。
Agent是比对象更高一级的抽象，它是一个主动(Active)对象，有自己信念和意愿[14-15]，多个Agent可以相互合作，组成一个社会，从而可以解决由单个Agent无法解决的问题。
面向Agent的建模是一种自下而上的建模方法，其建模流程如下：首先，识别系统中所有反映问题域和系统责任的Agent。定义Agent的结构与特征，包括内部状态(数据、变量)和行为规则(函数、方法等)。然后，确定组成多Agent系统的Agent群体所采用的体系结构，即Agent之间的通信与协调等问题。
Agent抽象的基本原则是：从系统的物理结构出发，围绕着系统的目标来对系统进行抽象。以系统的物理结构作为抽象的基本点，就意味着可根据物理世界的实际构成来划分Agent。根据这抽象原则，将上节的调度系统的中的实体抽象成为4个主要Agent，即BusAgent，StopAgent，DispatchAgent和InterfaceAgent。其中：Interface Agent用于和外界系统的数据传输和转换；BusAgent，StopAgent和DispatchAgent三者相互协调合作完成公交调度以及运营的整个流程。
为了满足车辆调度实时性的要求，对调度过程分解为发车调度和路上实时行车控制，分别由DispatchAgent和BusAgent各自负责相应的任务。建立公交智能调度系统的用例模型如图3所示。
图3 公交智能调度系统的用例模型
Fig. 3 Use case model of intelligent dispatch system
本系统中DispatchAgent处于主导地位，负责根据实时采集的数据制订与发车相关的调度操作，并在发车的同时将该车的BusAgent 注册到Multi-Agent系统中；StopAgent 负责站点客流量采集以及车辆到站时间预告；Bus Agent负责车辆满载率以及车辆在线路中的运行的交通信息等数据的采集，Bus Agent之间协同合作完成公交车辆行驶的动态控制。
3.1 StopAgent 的建模
由于StopAgent的功能比较简单，只需要实现采集该客流量、交通状况等信息和根据公交的运行情况，发布公交到站信息的功能，不需要特定知识和推理，因此，采用带状态的反应型Agent模型。其模型结构见图4。
其行为主要有2个：一个是定时驱动的，定时查询某线路将到达车辆的信息更新车辆到达时间，定时更新站点客流量信息；另外一个是事件驱动，当车辆到站上、下车服务完成后，更新自己站点客流量信息。
图4 StopAgent 的结构模型
Fig. 4 Structure model of StopAgent
3.2 DispatchAgent的建模
DispatchAgent 是整个公交调度系统的核心部分，是实现公交调度任务的主要承担者。它的作用主要是从StopAgent和BusAgent得到实时的客流量和交通状态信息，进行发车控制，确定发车时间和发车间隔，注册新发车的BusAgent到系统中。
由于调度需要大量的计算，但实时性要求不是很强，因此，采用慎思型Agent模型(BDI Agent)。该类模型具有信念(belief，即情景模式)、愿望(desire，即任务目标)、意图(intention，即为实现愿望而想做的事情)和知识库的特点。针对公交调度的实际情况，设计DispatchAgent如图5所示。
图5 DispatchAgent 的结构模型
Fig. 5 Structure model of DispatchAgent
各部分的功能如下。
(1) 信念库用于情景模式的设定，如上班早高峰、平常时段、下班早高峰、下班高峰、低谷时段、节假日、站点客流量以及季节、气温等模式的定义。
(2) 愿望库即公交调度的任务目标，各情景模式下乘客期望的最少候车时间。这些数据可来源于问卷调查和行政指标；同时也反映公交运营公司经济效益的要求。
(3) 意图库即为各种调度方案，如对于A方案，每5 min发车1趟；对B方案，每3 min发车1趟。
知识库存储公交调度所需各种知识，包括2部分:一部分是成功案例，若当前的情景在成功案例里面有，则直接提取案例进行决策而不需重新推理，从而加快Agent的推理过程；一部分是推理规则即信念到意图的匹配规则。
本文采用产生式(production rule)规则来进行知识表示，其基本形式如下：
P→Q 或 IF P THEN Q
其中：P是产生式的前提或条件，用于指出该产生式是否是可用的条件；Q是一组结论或动作，用于指出该产生式的前提条件P被满足时，应该得出的结论或应该执行的操作。由于产生式具有自然性、模块性、有效性、清晰性的优点，目前产生式表示法已成为人工智能中应用最多的一种知识表示方法。
下面用成功案例是否存在来说明DispatchAgent的决策和自学习过程。DispatchAgent 的决策和自学习流程见图6。
图6 DispatchAgent 的决策和自学习流程
Fig. 6 Flow of decision and study of DispatchAgent
(1) 功案例存在情况：IF (春秋常日AND上班早高峰AND常温AND各站点客流量正常) THEN (选择A方案)。
(2) 功案例不存在情况：IF (春秋常日AND上班早高峰 AND 酷热AND某站点客流量超量) THEN (根据情景，计算发车间隔)。这个案例完成后，对效用进行评估，计算此次决策的乘客满意度和运营经济效益，并给该案例评估打分，若满足要求，则将该案例存入备选案例，当下次遇到同样的情景时，则在备选方案上优化。经多次优化之后，选择1个最优秀的方案存入成功案例库。这就是DispatchAgent的学习 过程。
3.3 BusAgent的建模
BusAgent 是根据实际公交线路中公交车辆的驾驶行为而抽象出来的智能实体，用于获取外界环境的信息，并且拥有自己的知识和决策判断能力，可根据周围的环境实时调整自己的驾驶行为。由于公交车辆在线运行，需要的计算能力要求不高但是实时性要求比较高，针对一些特定的事件需要进行快速反应，因此，BusAgent采用混合型Agent模型。该模型是在慎思型Agent结构的基础上增加了快速反应功能，各部分的功能见图7。
图7 BusAgent的结构模型
Fig. 7 Structure model of BusAgent
其中信念库用于公交车辆行驶模式的设定，如跟驰模型、超车模型以及让车模型等。
愿望库即本次行车的任务目标，发车时由DispatchAgent注册BusAgent时获得，本文主要指本车到达各站点的预定时间以及和前车的到站时间间隔，其中保证公交车辆到站时间的先后间隔是防止串车和大间隔的关键。
意图库即为各种行驶模式的具体行驶操作，例如：方案A要求加速；方案B要求减速。
反应器用于对一些紧急事件的处理，如车辆故障、车祸等需要进行应急处理的情况。
其知识库的构建方式与DispatchAgent的构建方式类似。
3.4 Agent之间通信语言的选择
Agent之间常见的通信主要有2种：一种是KQML(knowledge query and manipulation language)；另一种是FIPA(foundation for intelligent physical Agents)[16]协会制定的FIPA-ACL。FIPA-ACL在构建新的原语方面具有很强的能力，并且FIPA-ACL的开发者通过SL(semantic language，SL)形式语言来表示一个Agent的信念、愿望和意图，以及这个Agent执行的动作，故本文采用FIPA-ACL。
通信实例：
(inform
: sender DispatchAgent1
: receiver BusAgent2
: content Bus schedule
: language s1
)
DispatchAgent1调度Bus2发车时，将Bus2的发车时刻以及预计到达在各站点的时刻表发给BusAgent2，按时刻表运行就是BusAgent运行的意图。
3.5 Agent之间协作模式的选择
由于Agent之间信念、目标不同或者同时共享有限资源都有可能造成冲突，因此，需要采用一种协调的方式来消除冲突。多Agent系统中Agent的协作模式主要有合同网、市场机制以及黑板模型等几种。
本文选择黑板模型，其基本思想是：黑板是一个共享的问题求解工作空间，各BusAgent都能看到黑板。StopAgent将问题和初始数据如前方站点客流量信息记录到黑板上，求解开始，后方BusAgent通过看自身状态和知识推理一个解决方法，当它无法解决时，由后方的BusAgent继续求解。重复这一过程，直到问题彻底解决，获得最终结果。下面是1个基于黑板模型的超车实例。
提出问题：站点k，提出问题，本站客流量。
求解过程：Bus i根据本车状况(满载率等)，查询知识库，能否满足站点的运输任务，能则答复ok；否则，答复no。
Bus j，根据本车状况，查询知识库能否满足站点的运输任务，若能则答复ok，发出超车动作。
处理结果：超车完成后，i和j的位置信息互换，信念更新。每一趟车过站后，站点Agent更新状态信息。
3.6 开发工具的选择
选择TILAB(telecom Italia LAB)发布的开放源代码软件JADE(Java Agent development framework)[17]作为公交调度系统的开发工具。
JADE是一个纯Java实现的符合FIPA智能体规范的多Agent系统软件开发框架，它由2部分组成：FIPA兼容的平台(platform)与开发软件包(package)。使用JADE可以方便快捷地进行Agent系统的开发和部署。
公交调度系统是一个分布式系统，DispatchAgent运行在调度中心的服务器上，BusAgent运行在车载JVM上，StopAgent则运行在电子站牌的终端上。
3.7 公交调度系统体系结构
公交调度系统的体系结构设计见图8。
图8 公交调度系统的体系结构图
Fig. 8 Architecture of bus dispatch system
公交调度系统的体系结构包括如下3层：
(1) 硬件层。包括硬件及其上运行的JVM。
(2) JADE平台层。1个平台可以有多个容器，而且这些容器可以分布在不同的主机上。在1个平台中，有且仅有1个主容器，当其他的容器启动时，必须在主容器中注册。
(3) Agent应用层。由容器上运行的各种Agent应用组成。AMS(agent management system)和DF(directory facilitator)是主容器中运行的特殊Agent，分别提供Agent管理和黄页服务。DispatchAgent，BusAgent，StopAgent以及Interface Agent都在这一层运行。
4 基于Agent的公交调度系统与传统方式的比较
Agent系统的建模理论反映了人们在观察客观事物时从世界观上的转化，即从绝对到相对，从封闭到开放，从集中到分布，这符合人类的客观认识规律，而传统的数学模型或逻辑模型强调总体、集中，很难对复杂系统进行建模与分析。
Agent建模方法有利于将复杂系统的分解，Agent作为自治主体，可有效减小系统部分之间的耦合，保证了Agent通过对内的调整和对外的协调，适应不断变化的动态环境。
其主要优点见表1。
表1 基于Agent的公交调度系统和传统方式的比较
Table 1 Comparison of characteristics between Agent-based system and traditional system
5 结论
(1) Agent系统具有分布性、并行性、自适应性以及协作性等特性，能处理不可预测的、动态变化的环境问题，将多Agent系统技术引入到公交调度系统中，能有效解决公共交通的复杂性、并发性和多样性等问题。尽管多Agent系统技术早就引入智能交通系统的研究与应用中，但将其用于智能公交调度是一种新的探索。
(2) 具体根据城市公共交通调度的实际运行环境，对其进行抽象，得出了智能公交调度的概念模型。
(3) 使用Agent的建模思想对该系统模型中的实体进行建模，建立了包括DispatchAgent，BusAgent，StopAgent和Data Interface Agent 在内的智能公交调度系统的多Agent系统模型，并重点探讨了StopAgent，BusAgent和DispatchAgent的功能结构和系统实现以及Agent中知识库的构建、推理和学习的过程。
(4) 对公交调度任务进行有效的分解，由DispatchAgent对公交调度进行宏观调控，BusAgent对运行中公交车辆的进行微观控制，比传统的集中式公交调度系统具有更高的准确性、灵活性和鲁棒性，能更好地适应复杂多变的公共交通运行环境。
参考文献：
[1] 杨兆升. 城市智能公共交通系统理论与方法[M]. 北京: 中国铁道出版社, 2004: 179-206.
YANG Zhaosheng. Theories and methods of urban intelligent public transportation system[M]. Beijing: China Railway Publishing House, 2004: 179-206.
[2] 万先进. 城市常规公交调度问题的研究[D]. 长沙: 中南大学交通动输工程学院, 2011: 7-13.
WAN Xianjin. Research on urban public transit scheduling problem[D]. Changsha: Central South University. School of Transportation Engineering, 2011: 7-13.
[3] 张飞舟. 公交车辆智能调度研究[J]. 交通运输系统工程与信息, 2001(2): 76-80.
ZHENG Feizhou. Research on intelligent scheduling for public traffic vehicles[J]. Journal of Transportation Systems Engineering and Information Technology, 2001(2): 76-80.
[4] 宋瑞, 何世伟, 杨永凯, 等. 公交时刻表设计与车辆运用综合优化模型[J]. 中国公路学报, 2006, 19(3): 70-76.
SONG Rui, HE Shiwei, YANG Yongkai, et al. China Journal of Highway and Transport, 2006, 19(3): 70-76.
[5] 王庆荣, 朱昌盛, 梁剑波, 等. 基于遗传算法的公交智能排班系统应用研究[J]. 计算机仿真, 2011, 28(3): 345-348.
WANG Qingrong, ZHU Changsheng, LIANG Jianbo, et al. Research on application of intelligence schedule of pubic traffic vehicles based on genetic algorithm[J]. Computer Simulation, 2011, 28(3): 345-348.
[6] 朱金寿, 朱琪, 杨勇刚, 等. 公交车调度方案的研究[J]. 武汉理工大学学报: 交通科学与工程版, 2002, 26(2): 169-171.
ZHU Jinshou, ZHU Qi, YANG Yonggang, et al. On bus-dispatch program[J]. Journal of Wuhan University of Technology: Transportation Science & Engineering, 2002, 26(2): 169-171.
[7] 李发智, 肖蕾, 杨东援. 公交发车间隔模型研究[J]. 武汉理工大学学报: 交通科学与工程版, 2013, 37(1): 92-96.
LI Zhifa, XIAO Lei, YANG Dongyuan. Optimal departure timetables for bus line[J]. Journal of Wuhan University of Technology: Transportation Science & Engineering, 2013, 37(1): 92-96.
[8] 王建平, 加玛力汗·库马什. 公交发车频率优化问题研究[J]. 计算机应用与软件, 2010, 27(12): 277-279.
WANG Jianping, Jiamalihan·Kuhi. Research on optimization of public transport headway[J]. Computer Applications and Software. 2010, 27(12): 277-279.
[9] 牟峰. 车辆调度问题的研究现状及发展趋势[J]. 西华大学学报: 自然科学版, 2012, 30(5): 37-40.
MOU Feng. Research status and development tendence of vehicle scheduling issues[J]. Journal of Xihua University:Natural Science, 2012, 30(5): 37-40.
[10] 姚俊, 吕智林, 叶嫣. 基于满意度的公交车调度模型研究[J]. 交通信息与安全, 2009, 27(4): 67-69.
YAO Jun, L
Zhilin, YE Yan. Model for bus dispatching based on satisfaction[J]. Journal of Transport Information and Safety, 2009, 27(4): 67-69.
[11] Wooldridge M. An Introduction to multi-Agent systems[M]. United Kingdom: John Wiley & Sons Ltd, 2009: 15-25.
[12] Jiming L. Autonomous Agents and multi-Agent systems: Explorations in learning, self-rganization and adaptive computation[M]. Singapore: World Scientific Publishing Co Pte Ltd, 2001: 1-8.
[13] Adler J L, Satapathy G, Manikonda V. A multi-agent approach to cooperative traffic management and route guidance[J]. Transportation Research Part B: Methodological, 2005(4): 297-318.
[14] 高波, 费奇. 从现实世界到多Agent系统世界[J]. 科学学研究, 2005, 23(2): 180-193.
GAO Bo, FEI Qi. Mapping realworld into multi-Agent system world[J]. Studies in Science of Science, 2005, 23(2): 180-193.
[15] 毛新军, 胡翠云, 孙耀坤, 等. 面向Agent程序设计的研究[J]. 软件学报, 2012, 23(11): 2285-2904.
MAO Xinjun, HU Cuiyun, SUN Yaokun, et al. Research on agent-oriented programming[J]. Journal of Software, 2012, 23(11): 2285-2904.
[16] Foundation for Intelligent physical Agents, FIPA application specifications[EB/OL]. [2002-12-03]. http://www.fipa.org/ specs/fipa00061/SC00061G.html.
[17] Java Agent development framework[EB/OL]. [2013-03-29]. http://jade.tilab.com.
(编辑 陈灿华)
收稿日期：2013-01-10；修回日期：2013-03-05
基金项目：国家自然科学基金资助项目(60674003)
通信作者：陈特放(1957-)，男，湖南涟源人，博士，教授，从事智能交通、软件工程、机车故障诊断研究；电话：0731-882656800；E-mail：ctfcyt@163.com
