（系统工程专业论文）实时公交调度专家系统设计与相关算法研究.pdf

摘要 近年来，智能公交调度的发展对传统的手工车辆调度提出了强有力的挑战。 实时公交调度专家系统是人工智能( a i ) 在公交领域的实际应用成果，是公交智 能调度系统的重要组成部分。它将管理信息系统、软件工程、系统工程、神经网 络、遗传算法以及专家系统等理论与公交调度作业有机结合在一起，创造性的应 用对于改善城市公共交通、提高公交作业管理水平以及公交客运智能化调度有着 特殊重要的意义。 在调研当前公交调度专家系统研究现状的基础上，本文对实时公交调度专家 系统相关的基本概念、工作原理、组织机制、相关算法和实现的技术方法等较全 面和系统的研究，继而设计了实时公交调度专家系统模型，最后对模型的可行性 进行了实例验证。 本文的主要研究内容如下； 1 针对静态调度存在的灵活性差、无法适应动态多变的道路环境等弊端，阐 述了研究动态调度的必要性。基于公交调度工作的发车原理，本文从多个 角度分析影响实时调度的诸多因素，彼此之间相互影响结果，继而提出相 应的解决办法和策略。 2 针对公交调度领域知识的特点，在研究不同种类的知识模型和系统推理机 制特点的基础上，设计了公交调度专家系统的知识表示模型一产生式知识 表示与面向对象思想相结合的知识模型。同时提出公交调度专家系统推理 模型，以及相关推理策略。 3 根据公交调度的实际情况，划分了公交状态异常类。为了达到实际公交系 统运行异常的快速诊断以及辅助专家系统建立知识库的需要，设计了一种 聚类算法用以检测公交系统中的异常类别及建立新的异常类。 4 另外在动态实时的生成调度方案方面，本文给出了优化调度的一个数学规 划模型并利用遗传算法可以快速的给出规划模型的近似优化解的优点， 有效的避免了传统算法难以快速收敛的问题，解决了公交调度动态实时性 的问题。 关键词：专家系统实时调度知识库设计异常判别 a b s t r a c t r e a l - t i m eb u sd i s p a t c h i n ge x p e r ts y s t e mo fi s 龃a p p l i c a t i o i lf r u i to fa r t i f i c i a l i n t e l l i g e n c ea n d 姐i n d i s p e n s a b l ep a r to fp u b l i ct r a f f i cd i s p a t c h i n gs y s t e m i th a s i n t e g r a t e dw i t hi n f o r m a t i o nm a n a g e m e n ts y s t e m , s o t t w a r ce n g i n e e r i n g , s y s t e m l ! n g i n e c r i n g , n e u t r a ln e t w o r k , g e n e t i ca l g o r i t l t ml ! x p o r ts y s t e mt h e o r y , p u b l i ct r a f f i c d i s p a t c h i n g t h i sc r e a t i v ea p p l i a n c ei so fh i 咖i m p o r t a n c et ob e t t e ru r b a nt r a f f i c c o n d i t i o n s , i m p r o v et h el e v e lo fp u b l i ct r a f l i em a n a g e m e n t 姐di n t e l l i g e n t ( i i s p a t e h i n g o nt h eb a s i so fd e e pa n dw i d e , r e a dr e s e a r c ho fd o m e s t i ca n df o r e i g nd o c u m e n t , 啪 h a v em a d ea l la l l - r o u n d e la n ds y s t e m a t i cn 络e a “血o nt l a cb a s i cc o n c e p t s ，t h e o r y ， c o n c e p t s ，w o r k i n gp r i n c i p l e sa n dt e e l m i q u e so f e x p e r ts y s t e m r n m a i nc o n t e n t sf l l e 鹪f o l l o w s ： 1 c o n s i d e r i n gt h ed i s a d v a n t a g e so fs t a t i cd i s p a t c h i n gi l k cl o wf l e x i b i l i t ya n d i n a b i l i t yt oa d a p tt oe h a n g e a b l cr o a de n v i r o n m e n t , w ea n a l y z et h en e c 髑s i t yo f t h er e = a r c l ao f d y n a m i cd i s p a t c h i n g b a s e do nt h ep r i n c i p l eo f b u s d i s p a t c h i n g , t h ed i s s e r t a t i o na n a l y z e st h ee f f e c t so ft h ef a c t o r s0 1 1r e a l - t i m e 柚dt h c i r i n t e r a c t i v ea f f e c t i o n s ，t h e np u tf o r w a r dt h er e l a t i n gm e t h o da n ds t r a t e g y 2 a c c o r d i n gt ot h ee l a a r a e t e r i s t i e so f t h ek n o w l e d g eo f t l a eb u sd i s p a t c h i n ga r e a , w ed e s i g nt h ek n o w l e d g em o d e lo ft h eb u sd i s p a t c h i n ge x p e r ts y s t , c m - - t h e m o d e lo f t h ei n t e g r a t i o no f p r o d u c t i o nr u l ea n do b j e c t - o r i e n t a l m e a n w h i l ew e p u tf o r w a r dt h er e a s o n i n gm o d do f t h es y s t e ma n dr e l a t i n gr e a s o n i n gs t r a t e g y 3 b a s e do n t h ep r a c t i c a lc o n d i t i o n so fr e a l - t i m e , l i s p a t e l l i a 舀w ed e s i g n n b n o r r n i t yc l a s s e s i no r d e rt oq u i e l d yd i a g n o s ea b n o r m i t i e sd u r i n gr e a l o p e r a t i o na n dm e e tr e q u i r e m e n t st os e tu pak n o w l e d g cd a t a b a s ef o ra x p e r t s y s t e m ，w cd e s i g nac l u s t e r i n ga l g o r i t h mt oc h e e ka b n o r m i t yd a s s e sa n dc r e a t e i l c , na b n o r m i t yc l a s s e s 4 ht e r m so f d y n a m i c a lc r e a t i n gr e a l - t i m ed i s p a t c h i n gs c h e m e s , w ep u tf o r w a r d am a t h e m a t i c sm o d e lt oo p t i m i z ed i s p a t e h i n g ，w ea l s oe f f e c t i v e l ya v o i ds l o w c o n v e r g e n c eo f t r a d i t i o n a la l g o r i t h mb yt h ew a yo f g e n e t i ca l g o r i t h m k e yw o l d s ：l ! x p e r ts y s t e m , r e a l - t i m ed i s p a t c h i n g , k n o w l e d g ed a t a b a s ed e s i g n a b n o m a i t yc l u s t e r i n g 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特授权北京交 通大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫 描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印 件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：忑了私张 签字日期；p 旬年晓月功日 导师签名： 签字日期：口7 年n 月功 北京交通大学硕士学位论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除 了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得北京交通大学或其他教育机构的学位或证书而使用过的材料与我一同工作的 同志对本研究所傲的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名；专卞粥秘签字日期：w 叼年2 月z o 日 致谢 本论文的工作是在我的导师王喜富教授的悉心指导下完成的，王喜富教授严谨的治学态 度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来王喜富老师对我的关心 和指导。 王喜富教授悉心指导我完成了论文的写作，对于我的科研工作和论文都提出了许多的宝 贵意见。在学习上和生活上都给予了我很大的关心和帮助。在此向王喜富教授表示衷心的谢 意。 在实验室工作及撰写论文期闯，张桥、常光辉等同学对我在论文中的研究工作给予了热 情帮助，在此向他们表达我的感激之情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业 北京交通大学硕士学位论文1 绪论 l 绪论 1 。1 论文研究背景 进入2 l 世纪以来，随着我国城市经济的快速发展和城市化进程逐步推进，城 市规模和人口迅速增长，一些城市问题也逐步尖锐化、表面化，交通问题就是其 中之一。城市汽车保有量的急剧上升，交通拥挤现象日趋严重，并且随之而来的 环境质量下降、臼趋严峻的能源问题、以及由于交通拥堵引起的时间成本严重的 浪费的问题严重困扰着城市健康良性的发展 我国城市交通问题的形成有着独特的社会背景和经济背景。一方面，从2 0 世纪8 0 年代开始，我国进入一个城市化进程步伐加快的时代。城市化是实现农业 社会向工业社会转交的重要机制，是我国实现现代化的登经之路，然而城市化又 导致了我国城市规模的急剧膨胀。城市规模的急剧膨胀和人口的快速增长不可避 免地诱发了许多社会问题的产生。行路是人生存必要需求，这种活动需求使得城 市日常交通量大幅上升，超过了城市交通基础设旌所能承受的范围，“人多车少， 车多路少”的矛盾自然变得日益突出另一方面，改革开放推动了经济的快速发 展。城市经济的发展也不例外。日益频繁的经济活动和城市居民日益增长的出行 需要不仅仅为城市交通提出“量”的要求，同时也提出了“质”的要求。客运需 求层次化突出。既有大批量的快速的需求，又有安全和舒适的需求。出行需求质 的变化促使城市居民的出行方式向个体的交通方式转变。在这种背景下，我国城 市私有的机动车辆快速增加。以北京市为例：2 0 0 6 年年末全市汽车保有量2 1 4 6 万辆，私人汽车保有量达到1 5 4 万辆，其中轿车保有量9 9 2 万辆，每七人拥有一 辆民用车相对于机动车的飞速增长，北京的道路建设则相对滞后。过去的五年 中，北京的城市道路增长了百分之三十，而机动车保有量却增长了一倍【1 1 。城市 快速增长的机动车辆与相对滞后的城市道路建设无疑加剧了城市交通问题恶化， 我国城市交通面临前所未有的挑战 我国城市人口众多，居住密集，城市道路发展空间有限，很显然，以私人汽 车为主的道路交通模式中国是根本行不通的。从全球机动化发展的经验来看，发 展公共交通是解决城市交通问题的有效途径。像日本、巴西、德国和西欧的大部 分国家，家庭轿车7 5 是周末外出旅游用，公交车辆的乘坐率达到7 0 以上，作 为汽车大国和石油能耗大国的美国，也意识到了发展公交的重要性，提出了“聪 明增长”的策略来重建公交系统，通过较小的能源消耗实现经济的增长【2 】。随着 我国经济的不断发展，城市化进程的不断推进，老百姓对出行需求的不断增加， 发展公共交通成为必然趋势。而建立先进的公共交通系统a p t s ，有利于提高道 9 北京交通大学硕士学位论文1 绪论 l 绪论 1 。1 论文研究背景 进入2 l 世纪以来，随着我国城市经济的快速发展和城市化进程逐步推进，城 市规模和人口迅速增长，一些城市问题也逐步尖锐化、表面化，交通问题就是其 中之一。城市汽车保有量的急剧上升，交通拥挤现象日趋严重，并且随之而来的 环境质量下降、臼趋严峻的能源问题、以及由于交通拥堵引起的时间成本严重的 浪费的问题严重困扰着城市健康良性的发展 我国城市交通问题的形成有着独特的社会背景和经济背景。一方面，从2 0 世纪8 0 年代开始，我国进入一个城市化进程步伐加快的时代。城市化是实现农业 社会向工业社会转交的重要机制，是我国实现现代化的登经之路，然而城市化又 导致了我国城市规模的急剧膨胀。城市规模的急剧膨胀和人口的快速增长不可避 免地诱发了许多社会问题的产生。行路是人生存必要需求，这种活动需求使得城 市日常交通量大幅上升，超过了城市交通基础设旌所能承受的范围，“人多车少， 车多路少”的矛盾自然变得日益突出另一方面，改革开放推动了经济的快速发 展。城市经济的发展也不例外。日益频繁的经济活动和城市居民日益增长的出行 需要不仅仅为城市交通提出“量”的要求，同时也提出了“质”的要求。客运需 求层次化突出。既有大批量的快速的需求，又有安全和舒适的需求。出行需求质 的变化促使城市居民的出行方式向个体的交通方式转变。在这种背景下，我国城 市私有的机动车辆快速增加。以北京市为例：2 0 0 6 年年末全市汽车保有量2 1 4 6 万辆，私人汽车保有量达到1 5 4 万辆，其中轿车保有量9 9 2 万辆，每七人拥有一 辆民用车相对于机动车的飞速增长，北京的道路建设则相对滞后。过去的五年 中，北京的城市道路增长了百分之三十，而机动车保有量却增长了一倍【1 1 。城市 快速增长的机动车辆与相对滞后的城市道路建设无疑加剧了城市交通问题恶化， 我国城市交通面临前所未有的挑战 我国城市人口众多，居住密集，城市道路发展空间有限，很显然，以私人汽 车为主的道路交通模式中国是根本行不通的。从全球机动化发展的经验来看，发 展公共交通是解决城市交通问题的有效途径。像日本、巴西、德国和西欧的大部 分国家，家庭轿车7 5 是周末外出旅游用，公交车辆的乘坐率达到7 0 以上，作 为汽车大国和石油能耗大国的美国，也意识到了发展公交的重要性，提出了“聪 明增长”的策略来重建公交系统，通过较小的能源消耗实现经济的增长【2 】。随着 我国经济的不断发展，城市化进程的不断推进，老百姓对出行需求的不断增加， 发展公共交通成为必然趋势。而建立先进的公共交通系统a p t s ，有利于提高道 9 北京交通大学硕士学位论文1 绪论 路通行能力和公交车辆的运营管理水平和运行效率。目前，美国、日本、加拿大、 英国、法国、韩国都投入了大量的人力和物力从事智能公共交通系统的研究，在 国际上处于领先地位，并且卓有成效。我国开始研究智能公共交通系统的时间较 晚，但是由于国家政策资金和技术的大力支持，这些都为智能公共交通系统在我 国的实施提供了有利条件。如今，我国智簏交通系统的实施已经初见成效。上海、 北京等大城市己在部分线路上建成了公交车辆跟踪调度系统，安装了电子站牌、 车载g p s 定位设备，实现了对车辆的实时跟踪、定位，使得调度过程有据可依， 同时提高了车辆的运行正点率和服务水平，吸引了大量客流，总的来讲，智能公 共交通系统在各大城市的实旎，收到良好的经济和社会效益【3 】。然而，城市的不 断发展要求我们必须结合中国城市交通的实际状况，深入地研究智能公共交通系 统的关键理论和实施技术，这对扭转我国在这一领域的研究相对于其它发达国家 相对落后的局面，以及解决我国城市交通存在的实际问题有着重要的科学价值和 现实的意义。 1 2 课题研究意义 目前，我国城市公交车辆运营管理总体现状来看，目前只能做到“一线两调” 的首末站管理，即车队作为运营组织调度实体，车队统辖几条公交线路，每条线 路的首末站均设调度员，并按照行车计划对线路车辆进行调度。这种传统的调度 方式存在明显的弊端：缺乏必要的信息与辅助处理手段，调度员不了解车辆、客 流、道路的实际情况，如车辆在中途各站是否准点、具体位置、是否有意外事故 发生：道路是否有阻塞，是否社会活动等。这就造成了实际的指挥灵活性差、对 突发事件应变能力差，调度质量因调度员的经验不同而不同。 先进的公共交通系统( a p t s ) 的应用很好地解决了以上传统的调度方式所带 来的指挥灵活性差、应变能力差的问题。a p t s 采用先进的车辆自动定位技术、 数据通信技术、传感起技术、g p s 、g i s 等技术，可以采集和处理动态信息，例 如客流量、交通流量、车辆位置、紧急事件的地点等，使得调度者对于道路情况 了如指掌，对于一些突发性事件可以采取及时措施 4 1 。另外，以上技术与信息技 术、计算机技术以及人工智能的结合，使得系统可以模仿人类专家实时地提出调 度方案，从而实现了公交的自动调度和指挥，保证车辆的准点运行，从而达到提 高公交服务承平的目的。 然而，为使公共交通智能化调度系统得以实施，数据采集与处理技术和公共 交通智能调度系统基本理论与技术是两个必须要解决的问题。实施智能公共交通 系统需要用到大量的静态和动态的信息。静态数据包括：公交站点阅距，居民出 行量，居民收入水平等。动态数据如：全球卫星定位系统( g p s ) 定位数据、地 1 0 北京交通大学硕士学位论文 t 绪论 理信息系统( g i s ) 中电子地图上的矢量数据、客流量、动态交通数据、站点问 行程时间数据、公交车发车间隔等等 5 1 现如今，g p s 和g i s 技术已经日趋成熟， 基本可以满足智能公共交通调度对于定位精度和与车辆运营相关数据准确度的要 求，而且随着电子技术和通信技术的发展，公交车辆与分调度中心双向通信的可 靠性是可以保证的。那么如何解决准点行使、到站所需要的技术支持是本文需要 关注的问题，即在依据行车计划的基础上，根据道路车辆的实际运行情况进行实 时调度的问题。这需要我们必须建立一个基于调度知识的专家系统，它可以根据 动态交通信息和车辆定位信息，提出必要的调度方案。然而虽然我国在公交智能 调度系统研究已经有了初步进展，但是由于它们缺乏对许多基础理论的深入研究， 一般没有将动态交通状态信息与车辆定位信息有效融合 6 1 ，使得目前系统智能化 程度大大降低因此，研究公交实时调度专家系统，有利于提高我国公交企业的 智能化水平，是我国智能公交调度系统研究的一个急迫的任务。 1 3 国内外研究现状 从2 0 世纪9 0 年代开始，对于公交调度的研究和探索大都集中在两方面：一 方面是如何应用a f r s ( 先进的公共交通系统，a d v a n c e dp u b l i ct r a n s p o r t a t i o n s y s t 锄) 理论及其相关技术来集成调度系统，实现公交系统的智能化；另一方面是 调度问题优化算法和近似算法的研究，研究关于公交调度专家系统的方面的论文 却少之又少。然而国内外学者在这两方面的有益的探索为公共交通系统的完善奠 定了丰富的实践基础，也为本文实时公交调度专家系统研究提供了很好的思路。 1 3 1 国外研究现状 西方国家在2 0 世纪5 0 年代就己开始对公交调度问题进行深入的系统理论研 究。1 9 8 1 年，c a 缸e r 和s t e m 给出一种以赤字方程为概念的方法，利用不同首末站 问的车辆空驶以减少整个公交系统的车辆总数 7 1 ；1 9 9 3 年英国的m a l a c l yc a r e v 研究了车辆的非准点到站分布，以及不同发车间隔下乘客的到达分布，基于个体 对费用、出行时问等因素的考虑研究了时刻表的制定问题嘲；1 9 9 5 年美国的 a d a m s k i 等运用s i m u l i n k 仿真工具对处于准点控制、发车问隔控制、协同控制 和随机控制四种调度控制模式下的公交线路运营状况进行了仿真研列9 】：1 9 9 8 年 p a o l od e l l es i t e 等研究公交客运的调度优化模型，研究线路在不同的运营模式下 的调度优化问题【l q 。 在技术方面，国外研究的主要精力集中在计算机辅助公交运营方面。最具代 表性的为r rs 技术支持下的公交调度系统。公交调度系统应用g p s 、g i s 、a p c ( 乘 客技术系统) 、通信系统等技术，使公交调度措施更为有效。s b o n o r a 、o k u n i e f f 论述了在车辆自动定位系统a v l 中应用g p s 等技术实现控制中心对公交车辆的 北京交通大学硕士学位论文i 绪论 自动跟踪，并借助无限通信技术建立公交司机与控制中心调度员的通信联系，保 证了调度措施的及时实施n n 。在车辆跟踪的基础上，借助公交实时位置及状态信 息，对公交车内到站显示、公交路口优先、车辆运营中途调度、行车计划的修改、 电子站牌等方面进行了开发。改善了为乘客提供的信息的准确性、实时性。m a l t e d d e s s o u k y 论述了三种自动车辆定位( a 、l r l ) 装置：信标及里程表( s o ) 、全球 卫星定位系统( g p s ) 、无限导航( r a d i on a v i g a t i o n ) 在公交调度中的应用【1 2 l 。 1 3 2 国内研究现状 随着国外先进设备的引进，我国一些大城市相继尝试将g p r s g i s 等新技术 运用于公交调度，如重庆市1 9 9 6 年开始将g i s 技术引入到公共交通管理中，研 究开发了。重庆市公共交通管理信息系统”：1 9 9 8 年3 月北京市公交总公司决定 开展。北京市公交总公司智能化调度系统总体方案设计及示范工程”项目，这是 我国第一个综合性公交i t s 项目：上海市1 9 9 9 年第一条应用g p s 技术进行调度 管理的公交线路9 8 1 路在浦东投入运行；杭州市是我国第一个将g p s 定位技术应 用到公交车辆调度管理中的城市。系统具备一定的车辆监控、管理和查询功能。 系统还具备在电子地图显示车辆运行状态的能力，并且有报警以及运行车辆到达 时刻站台显示等功能。 在理论研究方面，仍以公交线路调度为主： 于海澍”】论述了在实现智能调度系统中采用的调度模型，包括o d 矩阵模型、 实时控制模型、区间车模型。然后分析了实时智能调度需要用到的调度算法，确 定了智能调度系统必须采用定性到定量集成的方法，重点在于综合、集成、协调 和创新 耿金花【1 4 1 综合考虑乘客和公交公司两方面的利益因素，将一天划分为几个时 段，建立了一个分时段等间隔的公交优化调度模型。引入乘客总的等车时间和公 交公司总的发车车次两个目标函数，通过一定的转化加权，将两个目标函数合并 为一个单目标函数。并且提出了利用遗传算法来解决公交调度问题。根据公交的 实际情况设计出了适合该问题求解的具体算法，并给出了算法的实现。 尹相勇【l 习博士在其论文中提出公交行车计划编制是整体优化，公交调度是在 考虑整体因素、原则基础上的局部优化。论文以实际运营与行车计划偏差量最小 为调度目标，提出并分析了发车时问间隔、司售人员工作时间、发车次序、客流 量变化4 类偏差量的特点，建立了基于行车计划的公交区域调度局部优化模型并 设计了算法。论文中还提出公交区域调度系统是弱实时系统，必须具有实时特点 的理论方法进行研究。论文采用具有实时特点的专家系统进行研究，推理采用级 进式推理机制，结合案例推理、规则推理和启发式算法，应用面向对象技术，减 少专家系统搜索的深度和广度，提高实时调度系统的运行效率。 北京交通大学硕士学位论文 1 绪论 盖凌云1 0 6 使用动态规划的方法建立优化模型，对所需车辆趟数及所需车辆数 迸行了估计，得到一个工作日的车辆趟数和车辆数的范围，用d a t a f i t 软件拟合出 上、下行路线各站从0 - - t 时间总的上、下车人数随时间变化曲线，并建立模型， 给出较为理想的调度优化结果。 李煌华【1 】根据乘客到站的密度、下车密度、线路站间运行时间、车载容量、 高低峰平均候车时间，确定该线路所需配车数量以及发车频率。 北京航空航天大学李跃鹏【1 8 1 运用遗传算法，为公交智能调度寻求最优排班方 案：北京理工大学的曹全新等，运用多目标规划方法建立了公交车辆配置模型， 并且生成了可实现计算机仿真的算法 1 4 论文主要的研究内容 结合实际公交系统运营现状和存在的问题，本文计划从理论分析、方法研究、 应用系统构建几个方面对公交智能专家调度系统进行系统化研究，各章研究的主 要内容如下： 第一章绪论。阐述公交调度专家系统在先进的公共交通系统( a p t s ) 的作用， 对于提高智能公交交通系统的智能化水平、改善我国公交事业的管理水平和交通 状况有着现实意义。分析公交调度专家系统的国内外的发展现状的同时，指出结 合我国的交通状况发展公交专家调度系统的意义。 第二章专家系统概述。此部分论述了专家系统研究的现状，辨析专家系统的 重要概念知识，论述了专家系统工作原理和各个组成部分的概念和作用。 第三章采用基于产生式知识和面向对象相结合的知识表示方法设计了公交调 度专家系统。构建了公交调度专家系统的基本架构，划分了关键系统子模块。给 出了公交调度专家系统知识表示与设计，并采用了当前流行的推理机制构建此调 度专家系统的推理机。 第四章对公交实时调度专家系统信息预处理模块中相关数学模型及求解算法 进行研究。根据公交调度的实际情况，划分了公交异常类。为了达到实际公交运 营系统运行异常的快速诊断以及辅助专家系统建立知识库的需要，设计了一种聚 类算法用以检测公交系统中的异常类别；帮助知识库自适应的获取知识、建立规 则：另外在动态实时的生成调度方案方面，本章给出了优化调度的数学规划模型。 由于采用遗传算法这种启发式算法可以快速的给出规划模型的近似优化解，从而 有效的避免了传统算法难以快速收敛的问题，也就解决了动态实时调度的问题。 第五章总结与展望对论文的研究工作进行了总结，提出了本文研究的结论， 并对进一步研究进行了展望。 1 3 北京交通大学硕士学位论文 2 公交实时调度系统相关理论概述 2 公交实时调度系统相关理论概述 2 1 专家系统概述 公交实时专家系统是人工智能在公交调度领域的应用，构建公交调度专家系统 离不开对其相关理论以及知识领域的研究本章在介绍专家系统理论的基础之上， 进而讨论行车计划以及实时调度相关理论，确定了实现本系统必须解决的关键问 题。 2 1 1 专家系统的历史 在上世纪6 0 年代人工智能的产生初期，基本上以一般问题求解为主，采用搜 索技术和计算机逻辑寻找各种问题的解，但是由于实际问题的复杂性，这些搜索 技术虽然很好地解决一些简单的具有良好结构的问题，但无法解决因实际领域的 搜索空间随参数的数目成倍增长的问题，人工智能在实际领域中的应用陷入困境 1 1 9 1 。1 9 6 8 年，美国斯坦福大学教授根鲍姆( f e i g e n b a u m ) 与1 9 6 8 年成功地研制世界 上第一个专家系统d e n d r a l 它很好地克服了人工智能本身存在的缺陷，它创 造性地将通用性的解题策略与算法同特定领域的专家知识与实际经验结合在一 起，实现了人工智能从理论研究走向实际应用，从一般思维方法探讨转入专门知 识运用的重大突破。经过四十多年发展，专家系统已经在多个领域有了广泛的应 用，出现了故障诊断专家系统、控制专家系统、生产专家系统、智能教学专家系 统、和调度专家系统等，在产生巨大的行业经济效益同时，广泛的应用也推动了 a i 的研究得发展，促使应用出现了新的局面目前，专家系统和自然语言理解、 智能机器人一起并列为a i 研究的最活跃的三大领域在世界各国的新一代计算 机研制计划中，专家系统及其研究思想，都是其推理的核心部分正因为这样， 使专家系统成为当前世界上最热门的研究课题之一，它以其独有的特点，引起各 界人士广泛的兴趣。 公交调度专家系统作为人工智能在的公交领域的研究课题，在理论上融合了 公交调度的基本理论，在实现上依赖于信息技术及网络技术的应用，而其智能性 的实现则又依赖于人工智能的发展。公交调度系统中的知识表示和决策推理则集 中地体现了这些应用，它依托于调度知识进行知识表示，在其基础上进行相应的 推理实现，最终在网络环境下实现。 2 1 2 专家系统的定义与功能 专家系统的发明者斯坦福大学教授e a f e i g e n b a u m 于1 9 8 2 年就专家系统给出 以下概念：专家系统是一种智能的计算机程序，这是程序使用知识与推理过程， 求解那些需要杰出人物的专门知识才能求解的高难度问题【2 i 】。根据f e i g e n b a u m 关 北京交通大学顼士学位论文 2 公交实时调度系统相关理论概述 于专家系统的概念，可以概括以下几点： 专家系统是一个智能计算机程序系统； 专家系统具有相关领域内大量的专门经验； 专家系统可以模拟人类专家求解问题的思维过程进行推理，做出判断和决 策，对提出的问题给出满意的解释： 从专家系统的结构角度，本文给出一个由四元组组成的专家系统定义 e s = 妒，s ，l ，k ) 其中p 是要解决的问题，s 为系统的推理控制策略。l 是学习机制，k 为知识库。 一般专家系统的基本结构包括六个部分：用户界面、推理机、解释器、知识库、 知识获取部分和数据库，如图2 - 1 所示 1 、专家系统的重要组成部分知识库 专家系统如果模仿人类专家那样工作，就必须具有专家级的知识，知识越丰 富，质量越高，解决问题的能力就越强，专家系统求解问题的水平在很大意义上 取决于系统知识库所拥有知识的水平，因此知识库是专家系统的核心部分。知识 库是通过舭专家和领域专家的合作，提取并存储该领域特定问题求解所需的知识 的基础上建立的。知识库是领域知识的存储器，其中存放了某个领域众多知识的 集合。知识库中的知识用一种或多种知识表示方法来表示，并将知识形式化、符 号化，通过编码存入知识库。通常，知识库中包括两类知识，一是领域的事实性 知识，这是广泛共有的知识，亦即写在书本上的知识及常识；另一类是启发性知 识，它是在一个专业领域中的正确实践和正确判断的知识这种凭直觉得到的知 识、经验和诀窍，是专家经过多年逐渐积累而掌握的“善于猜想的艺术”专家 系统开发中最重要的任务就是要十分认真细致的对专家的知识进行分析。为此， 在研制专家系统建立知识库的过程中，越专家应与领域专家通力合作，认真听取 领域专家的知识，并根据计算机是如何表示、使用这些知识的要求，从专家大脑 中将这些知识转化为知识库的一个个组成部分。知识库一经建立，即可供系统在 推理判断时使用。 专家系统的知识来源于一个或一组专家。一般情况下，专家系统的知识库是关 于个特定领域或特定问题的若干个专家知识的集合体，因此一个功能完善的知 识库管理系统的解释模型可以向用户提供远远超过一个专家的经验和知识。 2 、数据库 数据库又称为“黑板”或综合数据库，它用于存放用户提供的初始事实、问 题描述以及系统运行过程中得到的中间结果、最终结果、运行信息等的工作存储 器。因为在推理过程中，多数情况下输入的数据要作为有关事实的知识保存在知 识库中。也有不少场合，要推理过程中的有关信息，比如一些案例数据，或是要 北京交通大学碗士学位论文2 公交实时调度系统相关理论概述 保存从外部数据库直接输入的数据。在这种情况下，知识库中就需有一个独立的 数据库 3 、推理机 推理机( 推理机制) 用来控制、协调整个专家系统的程序，使整个专家系统能以 逻辑方式协调地工作，推理机能够根据数据库当前输入的数据，利用知识库中的 知识，按一定的推理策略( 如正向推理、反向推理、正反向混合推理等) ，去求解当 前的问题、解释外部输入的数据或事实，推导出结论并向用户提示，根据要求说 明得出结论的根据等。 4 、解释器 要求专家系统的另一个重要能力是能解释自己的推理过程。专家系统需要能 够合理的说明它自己的判定，它应负责对推理做出必要的解释，为用户解释推理 过程、向系统学习和能为维护系统提供方便，且解释的方式应使用户容易接受， 即对用户是“透明的”。因此，专家系统具有的对自身推理( r e a s o n i n g a b o u ts c l f ) 的这种解释能力通常认为是专家系统的重要特征 5 、知识获取部分 知识获取功能，又称为学习功能，是专家系统提供的一种辅助功能，它为修 改知识库中的原有知识和扩充新的知识提供了手段。实际上，一个专家系统是否 具有知识渐增的功能( 学习功能) ，将影响系统实用的生命力。所以，新近研制的专 家系统大都强调了这种能力的重要性。其实，专家系统成功的关键之处，在于从 专业领域的专家那里获得专业知识。而专家系统的能力，正是取决于这些知识的 质和量。因此，被称之为知识库编辑程序的知识获取部分对于研制具有专家水平 的专家系统具有极其重要的作用。 6 、用户界面 用户界面( 又称用户接口) 是系统同用户的通信和信息交换的接口。专家系统必 须设法使系统具有能方便地与用户进行会话的功能。为此，不但要使系统的输出 信息变换成使用户容易理解的形式，而且还必须使用户能够方便的操作系统的运 行。为实现这一功能而设计的部分，就是用户界面。 综上所述，专家系统与传统的计算机程序( 系统) 有着完全不同的体系结构。通 常最简单、最基本的专家系统是由知识库、数据库、推理机、解释部分、知识获 取部分和用户界面等几个基本的、独立的部分所组成，而且随着专家系统的应用 类型、功能和规模的不同，在体系结构上会有较大的差异。 1 6 北京交通大学硕士学位论文 2 公交实时调度系统相关理论概述 图2 - 1 专寡系统的典型结构 f i 9 2 1t ”i c a ls t r u c t u r eo fe x p e r ts y s t e m 通常一个专家系统具有以下功能： l 洛询功能：回答用户提出的某个专门领域的问题，解释自己的决策过程， 相当于人类的“专家”。 2 学习功能：在专家的训练下，系统能不断地增添和修改自己的知识，相当 于人类的学生 3 教育功能：通过回答有关询闯，向用户提供某个专门领域的知识，达到教 育学生和训练新手的目的，相当于人类的“教师”。 2 1 3 专家系统的分类 按照专家系统所求解问题的性质，可把它分为下列几种类型，即解释专家系 统、预测专家系统、诊断专家系统、设计专家系统、规划专家系统、监视专家系 统、控制专家系统、调试专家系统、教学专家系统、修理专家系统和调度专家系 统等。北京市公共交通总公司的智能化调度系统是一种调度专家系统，这种专家 系统的任务是寻我出某个能够达到给定目标的动作序列或步骤。它具有以下两个 特点： 1 ) 所要调度的目标是动态的，因而需要对未来的动作做出预测； 2 ) 所涉及的问题复杂，要求系统能够抓住重点，处理好各子目标问的关系和 不确定的数据信息，并通过试验性动作得出可行的调度方案。 2 2 动态实时调度 根据我国目前i t s 的发展阶段来看，现在正处于研究公共交通系统改善方法 以及交通信息的阶段。城市公共客运系统尚未或正在引入先迸的高新技术，基本 上还是采用。定点发车、两头卡点”的手工作业的调度方式，导致公交车辆的行 车问隔不均匀等问题，时常出现“串车”“大间隔”现象，严重影响了公交客运的 服务质量。尤其是缺乏现代通信手段，调度人员无法实时了解运营车辆情况，难 以及时有效地采取调度措施。公交车辆调度处于“看不见”摸不着”的落后状况， 1 7 北京交通大学硕士学位论文 2 公交实时调度系统相关理论概述 具有较大的盲目性和滞后性。因此，对公共交通系统运营调度管理的智能化研究 非常必要，它可以加快城市公交系统科学化现代化进程，从而提高城市公共交通 运营的管理水平，改善城市交通拥挤状况。 2 2 1 调度理论的概述 调度是在运行线路的行车现场，调度人员为了使运营车辆运行与客流变化相 适应，根据行车组织实施方案( 如行车作业计划) ，直接对运营车辆及有关人员 下达调度指令的一系列活动。调度的目的根据行车计划方案以及运营线路的现场 的客流信息等各类信息，组织、指挥、调节、监督整个车队的运行，充分利用车 辆的运载能力，保证运行活动的正常运行，完成企业既定的目标。简单的讲就是： 充分合理地利用所有资源，获得经济和社会效益最大化的过程。 现场调度可以分为两种：静态调度和动态调度。静态调度是指行车计划的安 摔，又称为原始调度。公交公司根据线路的客流规律、线路的运行条件、企业的 运输能力和公交企业的社会效益、经济效益的指标编制为乘客服务的行车时刻表 通过执行行车计划表，将分散的各个车组纳入计划运行轨道，使公共交通线路运 行工作有计划、有节奏地进行。动态调度是指根据路况情况和突发事件，在原行 车计划基础上进行调整。 虽然行车计划是公交调度中最根本的依据，是静态调度一次性全局优化的最 优解，而静态调度是在假设公交车辆运行环境是一成不变的情况下进行，无法反 映和适应动态多变的道路环境。首先：在运营调度过程中，行车计划是根据以前 的经验而制定的，在实际运行过程中，推导行车计划的前提条件与实际运营情况 出入较大；其次，在实际的公交车辆运营中，突发事件、交通事故时有发生，行 车计划最终失去了最优性。虽然在理论上存在利用静态调度方法重新生成行车计 划存在可能性，但是静态调度一般需要较长的计算时间，而且实际的运行环境处 在不断的变化过程中，存在诸多的不可测和不确定的因素，重新生成的行车计划 很有可能失去意义。因此动态调度将是本文以后讨论的重点。 2 2 2 车辆调度形式 车辆调度形式，指营运调度措施计划中采取的运输组织形式。基本上有两种 分类，按车辆工作时间的长短与类型可分为【捌： 1 ) 正班车主要指车辆在日问运营连续工作，相当于两个工作班的一种基本 调度形式，所以又称为双班车、大班车。 2 ) 加班车指车辆仅在某种情况下，在某段营业时间上工作，并且每日内工 作累计工作时间相当于一个工作班的一种辅助调度形式，所以又称为单班 车。 1 8 北京交通大学硕士学位论文 2 公交实时调度系统相关理论概述 3 ) 夜班车指车辆在夜间上线工作的一种调度形式。一般城市夜问客运量不 大的线路，夜班车的车辆连续工作时间不足一个工作班，因此常与日问加 班车相兼组织运营，只有夜间客运量较大的线路，夜班车连续工作时间相 当于一个工作班。 车辆调度问题是在已知发车时间表达的条件下将车辆分配到每一条线路中 去。考虑的目标是最小车辆数和最小车辆运营成本，减少车辆运营成本的方法主 要通过减少车辆空驶行程和停留时间。 按车辆运行和停站时问可分为： 1 ) 全乘车指车辆从线路起点发车直到终点站止，必须在沿线固定停车站依 次停靠，按规定时间到达有关站点并驶满全程的一种基本调度形式，因此 又称慢车。 2 ) 区闻车指车辆仅行驶线路某一客流量的高路段或高区段的一种辅助调度 形式。 3 ) 快车是为适应沿线长乘距乘车需要，采取的一种越站快速运行的专线调 度形式，包括大站( 快) 车和直达( 快) 车两种。 4 ) 定班车是为接送有关单位职工上下班或学生上下学而组织的种专线调 度形式。车辆可按定时间、定线路、定班次和定站点的原则进行运输。 5 ) 跨线车是为平衡相邻线路之间客流负荷，减少乘客转乘而组织的一种跨 线运行的调度形式 实践表明，上述调度形式，对平衡车辆及线路负荷，改善拥挤，提高运输生 产率和运输服务质量以及促进客运发展都发挥了积极作用。 2 2 3 传统车辆调度系统的问题 在传统的公共汽车的调度中，调度人员不了解道路、客流量、己发车辆的情 况，但依然按照行车时刻表进行调度，这样往往造成了资源的浪费或者造成乘客 滞留在车站等情况。也就是说，调度人员没有任何关于乘客、车辆和道路的信息， 在调度中只能按照经验进行调度。日前，公共汽车调度中存在的问题可以分为以 下四类： 1 1 对公交车辆来说：调度人员不了解车辆在运行中的情况一在中途各站是 否准点、车辆是否遇到意外事故、车辆的位置等。 2 ) 对道路来说：调度人员不了解道路实际情况( 是否阻塞、发生交通事故等) 、 道路沿线的实际客流分布情况、交叉路口的公交信号优先。 3 ) 对公共汽车的调度来说：由于没有车辆、道路、乘客的任何信息，只有 靠调度员凭经验迸行，造成资源的极大浪费。 4 ) 对乘客来说：没有出行所需的车辆信息，出行不便。 j 9 北京交通大学硕士学位论文2 公交实时调度系统相关理论概述 智能调度管理系统的目的之一就是要解决在调度中如何快速、全面地