（计算机应用技术专业论文）航空旅行路径规划问询系统的研究与实现.pdf

沈刚i 业人学硕i j 学位论文 摘要 随着国民经济的不断增长、人民生活水平的逐步提高以及国际间交往的日益频繁， 出门旅行已经成为人们日常生活中的重要组成部分。交通状况的改进，一方面给人们出 行带来了更多的方便与选择空间，同时也产生了许多相关问题。例如，怎样在众多的交 通方式里边选择在各方面都令旅行者满意的路线、中转接续地点、时间安排等等，即成 为摆在人们面前急待解决的新课题。 本文就是基于人工智能领域中的知识表示、知识库理论、机器学习等方面的相关知 识、技术，通过对不同的最短路径规划算法分析、对比与研究基础上，利用b o r l a n d c + + b u i l d e r 开发平台对航空旅行路径规划f u 询系统c a r q s ( c i v i la v i a t i o nr o u t i n g q u e r ys y s t e m ) 进行的研制与开发。其根本目的就在于，首先在民航范围内按照某种既定 评价准则，给出符合客户要求的最佳航线、航班、中转接续指导，最大限度地使旅行者 既方便、快捷，又安全、舒适、节省费用。 本文首先在研讨当前相关软件的基础上，通过对系统整体的设计构思、框架结构， 以及各功能模块的职能划分等进行了细致、深入的分析、研究之后，提出了符合自己特 性且切实可行的技术路线与实施策略。 经过对知识库相关理论的分析、研究，以及知识库与数据库各自特性的对比，提出 利用数据库技术和方法来组织、管理c a r q s 中的知识。在分别对知识表示、机器学习 研究探讨的基础上，经过对多种知识表示方法进行分析、比较，最终确定利用框架表示 法表示c a r q s 中的知识，用c + + 语言对数据结构进行了定义，并针对系统设计目标， 选择机械学习作为性能改进途径。 在第四章，通过对d i j k s t r a 算法的深入学习和研究后，针对d i j k s t r a 算法进行了若 干改进。首先引入了启发式信息，依此求得对航线进行剪枝，然后引入规划结果信息， 使得规划的速度更为迅速、快捷。 在第五章，对整个系统和各功能模块的设计与实现细节作了较为详尽介绍，并给出 了系统运行结果。 关键词：路径规划，机器学习，知识表示 沈阳【：业人学硕士学位论文 t h e r e s e a r c h & i m p l e m e n t a t i o n o fc i v i la v i a t i o n r o u t i n gq u e r ys y s t e m a b s t r a c t w i t ht h ei n c r e a s i n go f n a t i o n a le c o n o m y ，t h ei m p m v i n go f t h ep e o p l e sl i v i n gs t a n d a r d a n dt h ef r e q u e n ti n t e r n a t i o n a li n t e r c o u r s e ，i th a sb e c o m ea ni m p o r t a n tp a r tt og oo u tf o r t r a v e l i n g i f lt h ed a i l yl i f e w h i l et h ei m p r o v e m e n to f t r a f f i cs t a t u sb r i n g s p e o p l e c o n v e n i e n c e sa n dc h o i c e s al o to fp r o b l e m sa c c o m p a n y i n g 谢血i tt o o ，f o re x a m p l e ，h o wt os e l e c tas a t i s f i e dr o u t e ， t r a n s f e rs t a t i o na n ds c h e d u l e re t c c i v i la v i a t i o n r o u t i n gq u e r ys y s t e m ( c a r q s ) w a sd e v e l o p e db ya n a l y z i n g ， c o n t r a s t i n ga n dr e s e a r c h i n gt h ed i v e r s i f i e ds h o r t e s t - p a t ha l g o r i t h m s ，b a s e do nt h ek n o w l e d g e e x p r e s s i o n k n o w l e d g el i b r a r yt h e o r y a n dm a c h i n e l e a r n i n g mt h ef i e l do fa r t i f i c i a l i n t e l l i g e n c e t i f f se n q u i r ys y s t e mc a ng i v et r a v e l e rt h eg r e a t e s ti n t r o d u c t i o na b o u tl a n e ，f l i g h t a n d m i d t u m i n ga c c o r d i n gt os o m ee v a l u a t i n gc r i t e r i o n i nt h e r a n g eo f c i v i la v j 觚o i la n d m a k e t h et r a v e l e rf e e lc o n v e n i e n t ，f a s t ，s a f e ，c o m f o r t a b l ea n d e c o n o m y ad i s f i n c t i v ea n df e a s i b l es t r a t e g yw a s p r o p o s e db ya n a l y z i n ga n dr e s e a r c h i n g t h ew h o l e d e s i g n o f t h e s y s t e m ，t h ef r a n l e ，a n dt h ef u n c t i o nm o d u l e sc a r e f u l l y a t e c h n o l o g ya n dm e t h o do f d a t a b a s ew a sp u tf o r w a r dt oo r g a n i z ea n d m a n a g et h e k n o w l e d g eo fc a r q sv i ai n v e s t i g a t i n ga n da n a l y z i n gt h er e p o s i t o r ya n dr e l a t e dt h e o r y ， c o m p a r i n g t h ec h a r a c t e r i s t i co f r e p o s i t o r ya n dd a t a b a s e af r a m er e p r e s e n t a t i o nw a s c h o s e nt o e x p r e s st h ek n o w l e d g eo fc a r q s ，a n dc + + w a su s e dt od e f i n et h ed a t as t r u c t u r e a i m i n ga t t h ed e s i g no b j e c t i v eo f s y s t e m ，r o t e l e a r n i n g w a sc h o s e nt oi m p r o v et h e p e r f o r m a n c e c h a p t e rf o u rd i s c u s s e dh o w t h ed i j k s t r a sa r i t h m e t i cw a sa m e l i o r a t e d a t f i r s t ，h e u r i s t i c i n f o r m a t i o nw a su s e dt op r u n el a n ea n dt h e np l a n n i n gr e s u l ti n f o r m a t i o nw a si n t r o d u c e dt o i m p r o v e t h es p e e d o f p l a n n i n g c h a p t e r f i v ei n t r o d u c e dh o wt h ef u n c t i o nm o d u l e sw e r ed e s i g n e da n d r e a l i z e di nd e t a i l ， a n dt h er u nr e s u l t so f t h eo p e r a t i o n s y s t e mw e r ep r e s e n t e d k e yw o r d s ：r o u t i n g ，m a c h i n el e a r n i n g ，k n o w l e d g ee x p r e s s i o n 2 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名：2 二女篮：三珀期：五鲨之! 圭! 关于论文使用授权的说明 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 签名 型! 主：工 弘。 沈队l 业人学硕士学位论文 第一章绪论 1 1 交通运输在当代社会中的地位与作用 交通运输是当今社会的支柱性产业，同时也是各个其它行业得以f 常运营的基础和 前提。在现代市场经济情况下，无论人们的日常生活，还是大、小不等规模生产的顺利 进行，缺少交通运输的协助几乎是不可想象的。一方面，伴随社会分工与生产专业化程 度的不断提高，加剧了不同行业与部门间的物质交换；另一方面，对时效性、舒适性的 追求和对安全保障的要求等，都给交通运输部门提出了更高的要求和标准。 当前，交通运输业的规模与自动化水平已经成为衡量一个国家综合国力的基本参数 和发达程度的标志。甚至，连人们的职业、社会稳定性等都在相当大程度上同运输业的 发展紧密相关。 首先，在当前这种以市场经济为主体的社会里，生产、生活资料的流动是空前的， 没有完善的交通运输作为后盾，是不可想象的。 其次，种种事实表明：交通运输业的发展并不是单纯是行业发展，它常从根本上决 定了某些相关产业能否得以生存与发展。我国很多地区的贫穷、落后就是由于该地区长 期以来交通运输业的不发达造成的。 最后，交通运输业的发展，也促进了人员流动，使个人的才智得以发挥，职业构成 趋于合理。同时也给大多数人带来实惠，从而保证了社会安定的局面。从很多发达国家 的发展历程看，它们的强盛无一例外地全部都是由交通运输的长足发展起步的。 交通运输现代化主要体现在基础设施建设、管理、调控自动化水平和基于前两者的 合理、有效利用等三个方面。要使交通运输能力得到提高，基础设施建设是根本，没有 基础设施做支持其它势必成为空中楼阁。然而，基础设施建设的最大特点是投资大、见 效慢。近年来，很多人已经开始认识到管理、调控自动化在交通运输中的重要性。不 过，欲取得理想的效果仍然需投入大量的人力、物力和资金，而且并非短期内能够凑 效。同前两种形成对照，对于现有资源的合理、有效利用相对而言实现起来却要容易得 多，而且投入的资金也不构成沉重负担，短期内还会产生巨大的效益。 沈阳r 业大学硕士学位论文 1 2 我国交通运输发展现状 鉴于交通运输业在国民经济中的特殊地位与作用，从建国以来，我国各级政府一直 致力于交通基础设施建设。尤其是自改革开放以来，更加大了投资力度。目前，我国已 经初步建成了包括铁路、公路、水运和航空等在内的比较完善的交通运输网络。 1 2 1 铁路运输发展现状 我国铁路运输虽然仍存在种种不尽人意之处，但在诸种运输方式的构成体系中， 铁路运输始终处于骨干地位，对国家经济进步扮演着至关重要的角色。据有关资料介绍 2 1 ，截止1 9 9 7 年底，我国铁路营业里程达6 4 3 万公里，其中国家铁路营业里程为5 7 6 万公里，地方铁路营业里程o 6 7 万公里。除西藏外，各省、市、自治区都为铁路所联 通，初步形成了以“九纵十横”为主体的、较为完整的全国铁路网络系统。 1 2 2 公路运输发展现状 自改革开放以来，我国公路运输进入了一个新的高速发展阶段，公路里程、公路运 输量和民用汽车保有量均有大幅度的增长。到1 9 9 7 年底，全国公路通车里程达1 2 2 6 4 万公罩。目前我国公路网已覆盖所有省、自治区和直辖市，而且全国9 7 的乡镇通了公 路【2 】口 以国道为主干线，省道、县乡级道路为支线的全国公路网络已经初步形成。我国公 路建设的快速发展，给公路运输在综合运输体系中发挥基础性作用奠定了良好的基础。 近些年来，我国公路客货运输业发展得异常迅猛，尤其是公路客运，现已在整个客 运体系中占有非常重要的地位。由于我国区域性经济发展的特点决定了地区间发展的不 平衡，加上产业布局存在的地理位置上的差异，地区间各类物资的交流仍呈不断增长趋 势，公路货运将以其小批量、快速、“门到门”和地域覆盖广阔等优势，在追求高价 值、高时效的当今占有其它运输手段难以替代的有利位置。 1 2 3 水路运输发展现状 水路运输也是我国运输业的重要组成部分。目前，我国已拥有沿海和内河重要港口 1 7 0 多个，其中主要大型沿海港口2 9 个，大型内河港口2 8 个。保有泊位数目总计6 4 2 4 2 沈f i tv _ 业大学硕士学位论文 个，其中沿海主要港口泊位为1 2 8 2 个、深水泊位4 4 9 个。可通航内河航道总里程为 1 0 9 8 万公里，其中水深l 米以上航道6 4 32 - 公里 2 】0 在我国，水上客运由内河客运、沿海客运和远洋客运三部分组成。因水上客运速度 较慢，所以在与其它运输方式的竞争中不免居于劣势境地，近几年水上客运量呈逐年下 降趋势。不过，由于水运业对基础性设施要求比较低，加上经营成本相对不高以及对环 境的破坏微不足道等因素，这种客运方式在短期内不会消亡。 水上货运。我国水运货运由远洋运输、近海运输和内河运输组成。水上货运主要承 担外贸进出口货物运输和国内能源( 主要是煤炭) 、矿建材料、粮食等的运输，具有其 他运输方式所不可替代的作用。 1 2 4 民用航空运输发展现状 在我国，民用航空运输事业是建国后才逐步发展起来的新兴运输方式，自从改革开 放以来，该行业进入了一个日新月异的高速发展时期。民用航空运输的最大特性就是可 以满足人们在超长距离旅行时对时间、舒适性等等的要求，以及近似苛刻的极决速货物 运输需求。现在，中国民航航线的总数已经达到1 0 0 0 多条，现在直接开通民航航线的 城市达1 8 6 个，其中国内城市1 2 7 个，国际城市5 9 个。国内省会城市、沿海开放城 市、重点旅游城市、重要经济城市及大多数其他运输方式不易通行的边远地区城市均丌 通了民航航线。民航部门拥有各种类型飞机5 0 0 多架，每年完成的客货运量分别为 6 0 0 0 多万人和2 4 0 多万吨【z j 。 经过多年的高速发展，我国民航业已经具有了相当的规模，拥有较强的客货运输能 力。即便如此，我国的民航运输业仍然处于高速发展阶段，除客货运量每年以保持不低 于1 8 的速度增长外，大型民用机场、民用飞机等均保持非常高的发展速度。 1 3 智能交通( i t s ) 技术现状与趋势 从以上介绍可以看出，我国的交通运输业正处于蓬勃发展之中，然而，即便如此， 交通运输业仍然无法完全满足人民群众不断增长着的需要。对于这种现状，我们每个人 都是深有体会的。比如说，城市的街道由于交通拥挤而排起了汽车长龙，在旅游旺季和 3 沈阳工业人学硕士学位论文 节假日购买车船票依然是难上加难，等等。所有这一切都集中地反映了这样一个事实： 虽然我们的交通事业得到了长足发展，但距离完全满足社会需求仍然相差甚远。 其实，当今世界各国都存在着类似的问题。美国从1 9 7 6 一1 9 9 7 年，年车辆公罩数 以7 7 的速度上升，可是同期的道路里程建设增长幅度却仅为2 ，在城市交通的高峰时 期，5 4 的车辆处于拥挤状态。由于交通拥挤，人们每天消耗在上下班的时间比往常平 均多出了1 5 h 。同时，由此导致商业车辆的时间延误，极大地增加了运输成本。 针对诸如此类的问题，最简便的方法就是拓宽路面、延长里程和增加航班架次以及 铁路车次等。然而有限的土地面积与环境制约关系等，使得道路、机场建设不可能做到 随心所欲，怎样在不扩张路网规模的前提下，大幅度地提高交通路网通行能力便摆在了 人们面前。综合运用现代信息与通讯技术等手段来改善交通运输效率就是一种比较好的 解决方案。智能交通运输系统i t s ( i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ) 就是在这 种情况下应运而生的。 i t s 是一个多学科、跨领域、综合化、高新特征异常明显的综合性工程体系。它是 将先进的信息技术、数据传输技术、电子感知技术、电子控制技术以及计算机处理技术 等有效地融合在一起，并运用于各类交通网络，进而建立起一种可以在大范围、全方位 地发挥作用的高度实时、准确、有效的综合管理系统。 1 9 9 5 年3 月美国交通部正式出版了“国家智能交通系统项目规划”，明确地规定 了智能交通系统的7 大领域和2 9 个用户服务功能，并确定了到2 0 0 5 年的年度开发计 划。其7 大领域包括：出行和交通管理系统、出行需求管理系统、公共交通运营系统、 商用车辆运营系统、电子收费系统、应急管理系统、先进的车辆控制和安全系统等等。 1 3 1i t s 在改善交通状况及国民经济中所起的作用 据估测，在未来的1 0 年当中，公路负荷会急剧地变得更加沉重，因此人们对i t s 的需求将显得日益迫切。目前，一辆汽车总价值的1 0 一1 2 是由电子配件创造的，有 关人士经分析后认为：近几年内这个百分数将逐步地提升到2 0 ，其中，相当大部分是 由于汽车内嵌i t s 的增长。不管交通管理与控制系统的供应商，还是收费公路的建造 商，都可望得到更可观的商业回报1 3 。 4 一 沈1 j r r l i 业大学硕士学位论文 除此之外，根据美国高速公路交通安全管理局的不完全统计，美国1 9 9 4 年因交通 事故造成的经济损失达1 5 0 0 亿美元。另据0 e c d 组织估计，道路拥挤每年给欧洲共同体 造成的损失达1 0 0 0 亿欧洲货币单位，这项损失约占欧共体国民生产总值的2 。采用了 先进的i t s 之后，既可以保持车速稳定或增长，而且还能够有效地减少事故发生。据初 步预测本项技术采用后可望获得降低事故发生率6 0 9 6 的成效，其社会、经济收益是可想 而知的。 i t s 已经开始给早期应用者创造出巨大的经济利益，并且还正在逐步地发展成非常 诱人的新兴产业。 1 3 2i t s 在我国的研究、发展状况 近几年，我国的交通运输事业发展得非常迅猛，尤其是民用航空和高速公路更是如 此，比如说中国的高速公路里程已经进入了世界前列。但是，不得不正视的是我们i t s 的研究与应用还处于起步阶段。这种残酷的现实既给我们形成了巨大的压力，同时也为 实现跳越式发展提供了良机。 最近几年，我国政府十分重视i t s 的研究和发展，2 0 0 0 年科技部会同国家计委、 经贸委、公安部、铁道部、交通部等十多个相关部委联合成立了发展i t s 的政府协调领 导机构全国智能交通系统协调小组及办公室，共同推动中国交通系统的智能化发展 1 4 1 。 目前，在我国的交通运输管理当中，应用通信、电子等先进技术已经十分普遍。随 着畅通工程的逐步深入，全国1 0 0 多个城市逐步地设立了信号控制系统，并建立了交通 指挥中心。 在城市公共交通方面，人们也从不同角度做起了很多富有实用价值的工作。例如， 在青岛、广州、深圳等大中城市的公交车上开始安装预付费i c 卡；在北京的多辆公交 车上安装了g p s 卫星定位系统；以及在上海、北京、厦门、深圳等城市的出租车上安装 了g p s 跟踪设备，并提供叫车和安全服务等多项便民措施 4 1 。 在公路路况和运输管理方面，交通部一直致力于建设全国的交通信息网 ( c t i n e t ) ，该网目前已经实现了与各省、厅级网络连在一起：各省、厅级信息化办公网 - 5 一 沈r 1 t 业大学硕士学位论文 络已经初步形成，办公自动化正逐步地变成现实；部分运政业务已经网络化和计算机 化，普通公路运政、路政管理开始使用远程监控手段，等等。 在铁路方面，现在已经建立起来了全国联网售票系统。在水运方面，一些航运企业 和许多港口，已经实现了内外贸集装箱运输电子信息处理和交换( e d i ) ；一些主要港 口，已建立起了水运客票系统，实现了电子售票。 1 3 3i t s 的前景展望 在未来社会中，i t s 的研究、应用必将获得更高速和更广泛的发展，作为- - i 3 新兴 科学，其发展也必将对其它相关领域产生巨大的推动作用，尤其是通讯、控制和智能等 领域将更加如此。 实事求是地说，i t s 的发展同样也面临着下面几类难题的困扰。第一个问题是系统 投资过大。第二个问题是i t s 发展直接受制于人工智能技术的进步。 此外，i t s 的进一步发展还有赖于以下几个关键技术的圆满解决：g p s 定位系统： 车辆位置、状态感知技术；导航技术；地理信息库技术，等等。 中国在i t s 的研究和开发上，由于起步较晚、基础性技术比较薄弱，加上工业、社 会等方面的种种困难，因此与国外还有相当大的差距。不过，应该看到：在我国一些大 城市，由于人口密度大、道路条件差，交通拥挤程度其实早已超过了发达国家。这种客 观实际迫使政府部门不得不下决心优先发展i t s 技术，从某种角度看这又是一种契机。 令人兴奋的是，我国目前已有越来越多的交通运输研究人员正将精力投入到i t s 研究和 应用之中。可以预见：在不久的将来，我国的i t s 研究、开发与实用化必将迎来充满生 机的春天。 1 4 课题研究目的与主要内容 1 4 1 课题研究目的 虽然随着科技的发展、政府投资于基础设施建设的力度加大。我国的交通运输行业 取得了空前的发展，但是随着社会的进步、国民经济的发展和人民生活水平的提高，人 们对出门旅行的要求也越来越高，交通状况虽然得到改善，但依然在很多方面还难以满 足人们同益增长的各种需求。 6 沈阳1 ：业大学硕士学位论文 当前，人们的出门旅行还存在着相当大程度的盲目性。首先，旅行者往往不清楚怎 样合理地安排自己的路线以及日程。其次，不知道怎样选择最佳的交通工具、中转地 点、车次、航班，以及如何将旅行同沿途景观欣赏、人文了解紧密地结合在一起。另 外，在对于旅行的舒适性，安全性等方面也没有一个明确的选择。由于对路线安排的盲 目性、车次、航班选择的随机性，不可避免地给旅行者带来了各种问题，增加了旅行者 在费用和时间等方面额外的开支。这种局面不仅加重了旅行者的负担，同时也给交通部 门造成巨大的压力，这种现状还直接地制约着相关产业的健康发展。 由于当前我国的i t s 研究还主要集中在公路网络管理和交通网络指导等几个主要方 面，对于怎样有效地解决个人出行指导、出行需求管理等还尚未提到议事日程上来。 本课题即是基于这种情况提出来的，从本质上说，它并非主动地改变现有的交通运 输状况，而是被动地进行适应以达到快、省等目的。就整个课题而言，其首要目的是开 发出- , e e 具备跨越不同交通方式、不同地域，并能给出具体的中转接续地点、时间和换 乘迁移等详细指导在内的个性化咨询。其次，所给指导必须将人们对里程、时间、经 费、安全性、舒适性、服务质量和沿途景观欣赏等等不同要求融合在一起，并且实现某 种综合评价指标下的最佳化。最后，还应该提交替补的不同出行方案供应用者选择，另 外，仍需保留现有辅助系统对于旅行知识介绍的功能。 在相当长的一段时间内，社会上虽然也曾出现过很多交通旅行查询软件，但那充其 量也只能算做电子时刻表。因为它们除旅行常识、交通工具的停靠地点、时间外，实在 给不出更多的有用信息。非但无法实现不同交通工具的最佳组合使用，就连最最基本的 单一交通方式下的实用化中转建议也提交不出。 纵观社会需求与技术发展现状，不管由哪个角度审视，尽快地开发一种实用化的、 能够实现跨越各种交通方式，并且具备智能中转接续功能和基于不同评价准则规划能力 的旅行路线问询系统都是极其富有现实意义和经济价值的。 1 4 2 课题设计目标 由于本课题的最终目标是研制出一种能够同时跨越各种交通方式与地域，并具有智 能中转接续功能和基于不同评价准则的路线规划能力的问询系统。为达到本目标，简单 7 沈盯r 业大学硕士学位论文 的体系结构与系统实现策略是无法满足要求的。首先，从理论上说，该系统的使用范围 不能局限在中国境内，而应该包括世界各个国家的每个地方。如此宏大的地域广度，不 认真解决好各种数据表示、压缩、快速提取、学习和一致性、合法性检验，最终必然要 归于失败。此外，规划系统面对这么庞大的环境空间，不寻求高效、实用化的启发指导 消息，欲意做到快速收敛并保证满足某种评价准则下的最优几乎是不可能的。最后，不 管交通基础设施还是运营规则全都存在一定的时变性，公路在延伸、铁路在不断地新 建、航线在开辟，基础性设施变了自然应该立即利用起来，再说，我国每年还存在春秋 两季行车、航班时刻调整。如何在最短的时间内将变化信息纳入系统也是必须严肃对待 的。这就要求建立完善的系统信息维护工具。诸如此类问题的解决全都寄托于人工智能 相关理论的帮助。 本系统的直接应用对象是各个旅行者，但也可以为政府、交通部门提供服务。第 一，通过该系统的使用能够将相当部分客流引导到运营压力稍轻的支线，减轻基础设施 建设不足带来的被动性。第二，通过客流引导，有利于不同运输方式间的竞争趋于良性 化，最后达到相互补充。第三，可以为国家价格合理制定提供最直接的资料。 按照前述目标，本系统设立七大功能模块：旅行任务建立功能模块、铁路子模块、 公路子模块、水运子模块、民航子模块、地理信息管理子模块和相关常识、信息咨询子 模块。 1 5 课题研究的理论基础 本课题研究的主要理论基础是人工智能，在此需要对与课题开展密切相关的人工智 能技术予以简要分析、介绍。 1 知识表示： 无论人工智能还是其衍生新学科一知识工程，知识表示全都是它们得以发展与建 立实用化系统的先决条件。其实，说到底知识表示就是将人类认识、解决客观现实问题 时表现出来的技能、技巧形式化，并且以人们容易理解和系统高效利用、更新维护的方 式表示出来。它至少应该包含四部分内容知识成份揭示、知识的概念化、形式化和 知识表示方法 1 3 。 8 沈i ；l i ： 业大学硕士学位论文 由于人工智能与知识工程涉及的知识主要局限在事实、经验、控制和元知t h 几大 类，而该系统的基本特点又决定了所角的知识为事实与控露性知识，因诧经分析、对比 后确定知识表示方法以框架为主，语义网络为辅。其实，樵架本来就建立在语义网络基 础之上，倾为整体理解方便着想还是明确地引入了语义网络表示方法。 2 ，知识库与知识库管理 知识靡概念来自于人工智能与传统数据库这两个不同的领域。知识库说至0 底就是知 识戆集合，它惫摇您谖本蹇、生l 谈熬存德掰在( 毯据逻辑续擒或稚浚模式帮物理存诺实 体) 9 1 。 稚谈霹管理系统是管疆知识洋中知识扮软俘，它主要包括以下渤靛：翔谖静获敬、 知识的演绎、知识的操纵( 包括对知识库中知识的删除、捅入和修改，以及知识库的相 释性、一散性、合法性与冗余性检测等问题) 及其知识的建模等等。 知识疼发展经历了若干个阶段，近年来对基予非经典逻辑的知识库系绞以及非糙确 推理的知识库研究已经成为该领域主导方向。不过，这类知识库目前尚缺芝严密、系统 懿理论，残栗与鸯效瞧等蠢德严撂稔验。 基于本课题所涉及知识的特点，在知识库与知识库管理方面采用当前比较成熟的数 据痒技术。由于系统静主黉信息燕航空公蠲、靛线、航班等等内容，两它稍同数据露中 的数据又不存在本质性差鼎，所咀借用数据库技术是完全可以现实的。 3 机器学习 学习是人积人造系统提高问题求解能力的重要途径，间时也是本系统快速改进性能 的关键手段。在人工智能和知识工程中，机器学习是它们研究的核心性内容，它的根本 嚣熬裁是探素学习的诗舅疆论、建立学习鹣计算撬攘型，以及馒诗舞凝具蠢鑫学霹敬能 力【1 4 】。 尽警，现有鹣橇器学习方法缀多，毽宅柩全都是赞对不蔺静闫越类墅与实际系统结 构提出来的，其完美性、可信赖性、快速性、对系统建造者的依赖蚀和产生的效果铸等 辫互不桷间。本颟研究需要结合自已的实际特征，探索并寻找实用化的高效学习方法。 9 沈阳工业大学硕士学位论文 1 6 本人研究重点 由于该课题本身是一个庞大的系统工程，作为一个人在短短的时间内是很难全面完 成的，鉴于此，本人只对该课题的一部分内容进行研究与实现。具体地说，就是负责并 完成了民航子系统的研究和设计工作。在完成的工作里边，包含了下面一些内容： 规划算法的分析改进以及基于此的航线规划研究； 启发式信息的获取与利用的研究； 民航航线规划相关知识表示的研究： 民航航班与航线网络信息管理的设计与实现； 民航相关信息管理的设计设计与实现； 民航航线规划方法的研究、设计与实现； 1 0 沈阳工、i k 大学硕十学位论文 第二章系统实现方案设计与c a r q s 系统设计构思 2 1 当前相关软件分析 2 1 1 相关软件分析 目前，我们可以查找到的与交通路线规划相关的软件极其稀少，即便能够找到的 几个还限定在停靠地点、时间等信息查阅水平上面。确切地说，现有的交通咨询系统 尚仅仅停留在电子时刻表层次。相对来说，关于铁路车次的查询系统要多于关于民航 的查询系统，在公路和水运方面几乎还处于空白状态。现有的交通查询系统大多是在 网上实现的，在这些系统当中普遍地存在着下列一些问题： 信息不全现在的查询系统基本上都是服务当地用户的地方性色彩特别强列 的区域性信息查询软件。对于列车信息只能给出经过本地的相关车次，对于民航 也仅仅限定在与其直接关联的进出港航班和中途停靠地点。外国航空、铁路、公 路和水运的路线、班次与时间分布，在现有系统上压根找不到。这种现状对经常 出国的旅行者来说，显然是极大的障碍。 缺少中转接续功能据截止目前了解所知，现在的查询软件根本不具备自动 中转接续能力。如果说某些系统具有勉强地具有接续功能，那还是在人为地指定 了中转地点之后，才给出一种模糊的交通工具换乘。即便这样，还要严格地限定 在不超过一次中转。 2 1 ，2 路径规划软件应具有的特征 路径规划软件应具备以下一些特征： 快速规划路径规划系统欲做到实用化，首先应达到快速性。如果一个路 径规划系统不能在可容忍的时间内给出有效结论。那么即便其规划结果非常圆满 也没有人会使用它； 健壮性好由于路径规划软件是面向各个层次的广大旅行者，而在这种技 术水平严重参差不齐的一大群人当中，不免存在相当部分属于非专业化，所以如 沈阳r 业大学硕十学位论文 何有效地防止、避免因经验不足带来的操作错误，以及因此导致的不良后果就显 得十分重要。换句话说，客观实际要求系统具有很强的健壮性； 友好的人机界面由于应用本系统的大部分人员是非专业化人士，作为系 统与外界沟通的主要途径一人机界面，即必须拥有非常友善的特征。人机界面 应该最大限度地适应各类非计算机人员的要求，不仅需要把系统输出转换为用户 十分易于理解的形式，而且还应使用户方便地操纵系统，必要时给出即时帮助； 2 2 系统总体方案设计 2 2 1 系统总体能力制定 本系统所要完成的主要功能是在客户发布出行任务后，根据设定的出发地点、终到 地点和可能必经的地点等等信息，选择相应的评价准则、规划模块与接续方式，按要求 进行规划并最后给出满足客户要求的合理旅行路线。在所给规划结果罩边，应依据客户 需求指明要乘坐的交通工具、所属交通公司、服务质量、换乘时间、地点以及整个行程 大致所花时间、费用等资料。 2 2 2 系统功能模块划分 根据以上系统总体能力分析，我们得出下列设计思路： 在系统中，将主要包括七个组成部分，分别为旅行任务建立模块、地理信息管理模 块、铁路模块、公路模块、水运模块、民航模块和相关常识、信息咨询模块。经过对这 七个部分进行整合，最后形成完整的具有整体规划与咨询能力的完整系统。而对于铁 路、公路等各个模块来说，在它们自己的领域内，全都应该具有实现不同评价基准下的 规划能力。 2 2 - 3 系统实施策略确定 如前所述，由于本课题属于庞大的系统工程，所以不可能由一个人在短期内将其全 面予以实现，为此，本人首先承担了民航子系统的研究与设计。铁路子系统由本科生毕 业实施，其它部分除地理信息模块之外，暂时尚未进行。在民航子系统中，首先集中力 量开展了以距离最优为评价基准的路径规划。在各方面条件允许的情况下，再在此基础 1 2 沈阳1 ：业大学硕士学位论文 上逐步补充基于时间、费用、安全性、服务质量和舒适性等为评价准则的路径规划内 容。 2 - 3 系统模块简介 为了对本系统有一个整体性的了解，需要简要地介绍一下其中包含的各个模块的主 要功能，以及它们的设计主导思想。 2 3 1 旅行任务建立模块功能简介 旅行任务建立是各个功能模块得以顺利进行的先决条件。由于公路、铁路、水运和 民航对基础设施的要求性质不同，而不同种类的基础设施对应的编码规则即互不相同。 公路、铁路与水运依其各自对应的干、支线分布关系进行编码，民航则必须无条件地遵 从统一的国际代码分配。实际上，不同的编码方式是出于方便熟悉各种交通方式的人群 和系统高效推理设立的，它们最终还必须统一在现存的行政隶属地域之下。所以旅行任 务建立模块至少应该完成下列几项功能： i 按照公路、铁路、水运、民航或地理行政依从关系，获取出发地点、终到地 点和可能的中间必经地点； i i 检验设定的旅行任务是否合理、合法，比如出发地不能是目的地，军事重地 不是任何人都可任意前往： i i i 对设定任务进行初步的不同交通方式分割( 高层宏观规划) ； 2 3 2 铁路、公路及水运模块功能简介 【习为铁路、公路、水运子系统的任务求解方式十分近似，于是在此一并予以简要介 绍。 这三个子系统的共同作用就是依据各自的任务，基于为它们建立的各自交通路线网 络，通过分析、搜索和比较之后找出满足某种评价准则下最优的旅行路线、中转接续地 点和交通工具等。在这里，必须重点解决好下列几类关键问题： i 规划结果确实符合客户要求； i i 规划结果应该自动加入客户在任务设定时遗漏、但又必须顾及的相关要求： i i i 系统的工作速度是迅捷的，至少是能够容忍的： 一1 3 沈刚r 业大学硕士学位论文 v 所给规划结果的信息是全面的； 在中转接续时需要将晚点、办理相关手续等时间耗费因素计算在内； 应该将机器学习引进来，只有这样系统才能不断获得改进与性能提高； i 不同模块之间应能够实现彼此通讯和信息交换； 2 3 3 地理信息管理模块功能简介 地理信息管理模块是除常识、信息咨询模块之外所有功能模块赖以发挥正常作用的 基础。它起码要完成三类任务： i 地理行政代码及相关信息的分级管理； i i 地理邻接关系的分级管理； i 地理连通关系的分级管理； 无论哪个规划模块，尽管它们使用的编码规则不同，但在地域概念上全都一样，于 是必须由地理信息管理部分把它们有机地融合在一起。 2 3 3 1 地理信息编码 前已述及，地理信息编码的主要目的就是为各规划模块提供基本依据，因此它是整 个系统得以i t l 哽n 发挥效能的基础。因为只有将不同交通运输方式的代码映射到同一地理 位置，才能将它们有机地结合，成为完整系统。另外，惟有通过地理信息编码，方能够 有效地避免地理重名带来的混乱，刚氐系统实现复杂度。 1 地理信息编码思想 地理信息编码的设计思想是把所有的地域、地名依照其所在的行政隶属级别逐层递 阶地划分成不同的等级，每个等级的每个个体赋予唯一的区分代码，不同等级代码综合 在一起最终构成了它的标识代码。地理信息大体上分割成五个级别，它们分别是外国的 洲( 或洲的分区、合并) 与国内的省、自治区、直辖市、特区市；外国的国家与国内的 地级市；国外的省、州与国内的县、区；国外的主要城市与国内的乡镇、城市小区；国 外的县、区与国内的村庄、街道。在此，之所以将国内的省、市、自治区提升得与国外 的洲( 或洲的分区、合并) 同级，其根本原由是由于国内环境是本系统服务的主要范 - 1 4 沈刚工业人学硕十学位论文 豳。国内人士出国旅行的主要方式是民航和铁路，而在国外的停靠地点是那样的有限， 潋趸于经常是著名的太中城市，予是降低描述细腻性不会弓 起大的溉乱和谖解。 2 地理信息编码基本规则 在本系统中，对于不阐地理级别的编码规则制订如下： 一级编码由于圈内匏雀、鱼治躐、直辖泰、特区枣总数为3 4 个，鸯鞋上世器 的六个大洲( 南极暂时未考虑在内) ，这样如聚将总数限定在6 2 以内，于是一个符 号经鼗霹鞋满足。妥测、欧溯秘# 渊f 冬匿家数鳗霹l 超懑6 2 个，对诧鬟要遗 亍缨 分，而南北美洲的国家数较少又可以归并为美洲。例如，亚洲就能够细分成西亚、 东南戴帮j 耍等。因为区分大小写静英文字符帮数字总计为6 2 个，这萃申编码方式鬣 有效地压缩了数据量，同时又便于系统灾现。 二级编码参照一级编码规则，在本级地域范围内按照区分大小写的英文字符 和数字总计不超过6 2 个原受4 避行代码编摊。 三级编码参照一级编码规则，程本级地城范围内按照区分大小写的英文字符 窝数字总计不超过6 2 个暴显l 遴褥代码缡撵。 四级编码参照一级编码规则，程本级地城范围内按照区分太小写的英文字符 释数字慧计不趣遘6 2 夺磊簧l 遴孪亍找璐编捧。 五级编码参照一级编码规则，在本级地域范围内按照区分大小写的英文字符 和数字总计不超过6 2 个原员q 进行代码编排。 基予以上编褥规则，可以得至n 下面完熬的地理馈患代鹕： t f 工弋匠 一级编弱 二级编码 三级编褐 四级编码 矗缓绩鲻 隰2 1 撼理信崽擦玛 1 5 - 沈5 h 工业人学硕士学位论文 2 4 系统总体框架 通过对系统各个模块的功能划分，可以得出下列总体结构示意图。 用 户 图2 2 系统总体构架图 从图2 1 可以清楚地看出，各个信息库和黑板对整个系统的功能实现是至关重要 的。图2 1 未明确标示各模块问的调度、协调。 2 5c a r q s 的功能研究与设计 c a r q s 是总系统中四个具有旅行路线规划能力的子系统之一，也是本人研究、工 作的重点所在。本人对其中的知识表示，知识库管理和路线规划算法等相关内容进行了 研究、改进，并在计算机上进行了具体实现与检验。 2 5 1c a r q s 功能介绍 c a r q s 的基本作用就是管理、维护和生成航空旅行过程将要用到的相关信息。这 些信息主要包括国内和国外航空港数目、每个航空港的自然信息、航班信息、航线信 1 6 沈阳l 业人学硕十学位论文 息、不同航空港之间的里程信息、不同航班在不同航空港之间飞行的路线信息、不同航 空港在不同时期的客运吞吐信息、不同航线的客流量信息等等。 系统应该具有针对上述信息进行有效管理、维护的能力，具有对航班、航线、航程 等信息基于不同条件的查询能力。除此之外，最重要的是还应该具备在民航系统内基于 不阿评价准则的路径规划能力，以及同其他子系统之间进行信息交互的功能。 2 5 1 1c a r q s 设计 从前述分析可知，c a r q s 系统设计要满足规划速度快、健壮性好以及人机界面友 好等项要求。 首先，c a r q s 应实现航线规划，这是本系统的基本要素，其它功能都是在这个基 本要素实现之后逐步完成的。对于c a r q s 航线规划功能的实现，最主要的条件是具备 大量的航班、航线、航空港等方面的事实性知识。如何得到这些知识，以及怎样对这些 知识进行完善的管理和有效地利用，则是需要认真对待的。 关于这些信息的获得和管理，首先必须建立一个知识库管理系统，籍此对有相关事 实性知识进行录入。只有录入相应的知识之后，系统才能进行航线规划等等。 怎样有效地对知识进行管理、维护，将是本课题重点研究的内容之一。 如何有效地利用既得知识进行快速的航线规划，给出用户提交规划任务的解则是本 系统的最终目的所在因此航线规划是课题随后将要研究的核心问题。 对于旅行目的地的有关介绍也是用户感兴趣的，以及对于旅行中的各种相关知识的 介绍则是系统要完成的第三个任务。 所以，c a r q s 系统最少应由三部分构成，即，信息管理与维护、航线规划和相关 知识咨询。 首先，最基础部分就是对知识库的管理。我们知道，知识库是知识的集合，在知识 库中存放有用来求解问题的领域知识，知识库的信息量一般都是非常庞大的，对于知识 库的有效管理就构成了整个系统正常运行的关键。 1 7 沈阳t 业大学硕士学位论文 互墨 离图圉 1 8 - 沈阡11 ：业大学硕士学位论文 经过以上分析、细化后，c a r q s 的最终框架体系如图2 4 所示 c ar q s 航线 网络 优化 模块 基于任 务信息 的航线 网络剪 枝