软件工程专业毕业设计-道路信息查询系统设计

道路信息查询系统设计摘要自九十年代初期以来，世界上已有许多国家开始对路线信息查询系统进行了研究和开发。路线信息查询系统是一种迅速查出所在地区某单位或住宅地点，并依照你当前所在地点查出对行人去某地的最佳乘车路线及到达离目的地最近后，如何行走的最佳行走路线，对驾驶员则提供一条从出发地到目的地的时间最短时间和消耗费用综合评价最优的行车路线，而对外地旅客还可提供各类宾馆、旅店、飞机、火车时刻表、购物及旅游场所等服务信息。使用该系统后，方便了广大游客，避免了游客因环境的不熟悉所带来困难。本文对路线信息查询系统进行了研究，并开发了一个路线信息查询RMQS1.0,(RoadMessageQuerySystem）。RMQS1.0系统的主要特点和功能如下1、根椐你掌握的信息迅速查出所在地区某单位或住宅地点2、对地图进行浏览和查出所在地区某单位或住宅地点3、对驾驶员提供一条从出发地到目的地的时间最短时间和消耗费用综合评价最优的行车路线4、为游客找到去某地最佳乘车路线和所经过的站名，并提供下车后如何到目的地的最佳行走路线。5、对骑车人提供一条从出发地到目的地的距离最短的骑车路径。6、为游客提供旅行其他必要的信息。本文研究的重点是路线信息查询系统中的最优乘车路线搜索算法部分、行车路线搜索算法部分。在RMQS1.0系统中用了两种算法。第一种是最优乘车路线搜索算法，用了启发式搜索算法（A*），这种算法应用了启发式知识，使算法执行时所搜索的节点数大大减少，运行速度快；第二种是行车路线搜索算法，用了启发式知识，它是本文提出的应用于对时间最短、距离最短、时间和消耗费用综合评价后产生的最优行车路线搜索算法。本文对数字地图数据库也进行了比较深入的探讨，并参照国外开发数字地图数据库的标准和方法。关键词：RMQS1.0；数据库ABSTRACTSincetheearly1990s,manycountriesintheworldhavebeguntoresearchanddeveloprouteinformationquerysystem.Therouteinformationinquirysystemisamethodtoquicklyfindoutthelocationofaunitorresidenceinthearea,andfindoutthebestrouteforpedestrianstogotoacertainplaceandhowtowalkafterreachingthenearestplacefromthedestinationaccordingtoyourcurrentlocation.Itprovidesthedriverwiththeshortesttimefromthestartingplacetothedestinationandthebestdrivingroutewithcomprehensiveevaluationofconsumptioncost.Forforeignpassengers,itcanalsoprovideallkindsofhotelsHotel,plane,traintimetable,shoppingandtouristplacesandotherserviceinformation.Afterusingthesystem,itisconvenientforthemajorityoftouristsandavoidsthedifficultiescausedbytheunfamiliarenvironment.Thispaperstudiestherouteinformationquerysystem,anddevelopsarouteinformationqueryrmqs1.0(roadmessagequerysystem).Themainfeaturesandfunctionsofrmqs1.0systemareasfollows1.Accordingtotheinformationyouhave,quicklyfindoutthelocationofaunitorresidenceinyourarea2.Browsethemapandfindoutthelocationofaunitorresidenceinthearea3.Providethedriverwiththeshortesttimefromthedeparturetothedestinationandthebestdrivingroutewithcomprehensiveevaluationoftimeandcost4.Findthebestbusroutetoaplaceandthestationname,andprovidethebestwalkingroutetothedestinationaftergettingoff.5.Providecyclistswithacyclingpathwiththeshortestdistancefromthestartingpointtothedestination.6.Providetouristswithothernecessaryinformationfortravel.Thispaperfocusesontheoptimalrideroutesearchalgorithmanddrivingroutesearchalgorithmintherouteinformationquerysystem.Twoalgorithmsareusedinrmqs1.0system.Thefirstistheoptimalbusroutesearchalgorithm,whichusesheuristicsearchalgorithm(a*),whichappliesheuristicknowledgetogreatlyreducethenumberofnodessearchedduringtheexecutionofthealgorithmandrunfast;Thesecondistheroutesearchalgorithm,whichusesheuristicknowledge.Itistheoptimalroutesearchalgorithmproposedinthisthesisafterthecomprehensiveevaluationoftheshortesttime,theshortestdistance,timeandcost.Thispaperalsomakesamorein-depthdiscussiononthedigitalmapdatabase,andreferstothestandardsandmethodsofdevelopingthedigitalmapdatabaseabroad.Keywords:rmqs1.0；database目录TOC\o"1-2"\h\u30057第一章绪言 绪言随着世界经济的不断发展，世界各国不断的对城市建设进行改造，以便使其成为现代化都市，尤其在中国近几年里大中小城市的市政建设都发生了巨大的变化，同时对旧城区也进行了改造。随着经济的繁荣、各种机动车辆与日俱增，以及外出旅游也成为新时尚，人们迫切地需要提供城市的各种道路、旅游服务等信息，以便经济快捷地享受旅行带来的乐趣。路线信息查询系统（RoadMessageQuerySystem，简称RMQS）就是在这种情况下应运而生的一种新的路线查询和导游服务系统。本章将着重介绍路线查询和导游服务系统的一般组成结构，分类以及国内外进展和发展趋势。由于我国在路线信息查询目前还不十分完善，需要做大量的工作，尤其在道路数字地图数据库的构造、数字地图图象处理和最优路线搜索算法方面，还需要进一步改进、提高。对道路数字地图数据库的构造，采用地图矢量化方法进行数字地图数据库的构造；对数字地图图象处理包括：数字地图显示、数字化地图、数字化图象放大和缩小处理。对最优路线搜索算法要从以下三方面考虑：第一、行人的最佳乘车路线及下车后如何走到目的地的最佳行走路线第二、骑车人的距离最短的行车路线第三、驾驶员有以下三种情况的选择：时间最短、路径最短和时间与消耗费用评估分别来进行最优路线搜索1.1路线信息查询系统的结构和分类所谓路线信息查询系统,是指一种新的路线查询和导游服务系统，它利用计算机帮助游客或驾驶员找到一条从出发地到目的地的最优路线，同时向驾驶员提供图形和文字说明的路线引导图，向游客提供乘车路线及所经过的站名的路线引导图，并配以文字说明。使用该系统后，使游客旅游、住宿更加便利，且能适当的减少了交通堵塞的发生，减少车辆在道路上的逗留时间，节约了顾客费用，并在某种程度上实现了交通流量在各条路段的合理再分配。据英国交通和公路研究实验室估计，给司机提供行驶路线信息，可减少行车时间8-12%。此外，应用这种系统，能帮助对地理环境不熟悉的游客或驾驶员准确、快速地到达目的地。路线信息查询系统的一般组成结构如图1.1所示。路线决策模块在整个路线信息查询系统的核心。其功能包括：找出目的地的具体位置、为游客提供一条到目的地的乘车路线及下车。图1.1路线信息查询系统的功能结构图后行走的路线图、对地图进行流览、为驾驶员提供一条到目的地的时间和消耗费用综合评价最优的行车路线引导、以及提供旅游、住宿信息及飞机、火车时刻表等信息。数字地图数据库用来存储道路网络的拓扑信息，以及其它的相关数据。交通流量数据库用来存储道路网络中各个公路在不同时间段内通过该公路的时间和所消耗的费用的综合评估值。单位数据库用来存储所在地区所有单位和住宅楼的指示性图形。站点数字地图数据库用来存储交通路线上各公交车站的具体信息。用户界面以图形文字说明与用户进行交互。路线信息查询系统的运行原理可以总结为：各种数据源把位置、方向、字地图、单位信息、旅游信息、交通流量信息和起止点等数据在计算机中进行处理。计算机利用所获得的信息计算出一条从起点到终点的最优路线并产生引导路线图，并以图形和文字的形式输出。游客或司机根据所得到的信息来决定如何行驶，安全、节约、快速地到达目的地。上面介绍的是路线信息查询系统的一般结构。然而，在不同的国家和不同时期，路线信息查询系统的结构是有区别的。下面我们按不同的标准对路线信息查询系统进行分类。根据路线信息查询系统所使用的数据来源不同，可以把路线信息查询系统分为静态系统和动态系统。静态系统使用静态数据，即数字地图数据库、单位数据库、旅游数据库。动态系统使用的是实时交通信息。静态系统结构简单，而动态系统需要附加动态信息拾取设备和通讯手段，及更复杂的查询算法附加动态信息拾取设备和通讯手段，及更复杂的查询算法。1.2路线信息查询系统发展的历史、现状与趋势1.2.1路线信息查询系统的发展历史人类很早就开始使用路标来指示方向，并且在汽车还未出现前就发明了许多导航设备。据我国古代文献通记载，在汉朝未期就出现了里程计；在公元200—300年，发明了指南车；在公元11世纪，又发明了磁罗盘。利用这些设备可以较准确的确定车子行进的方向和行使的距离。六十年代未，由于科学技术的发展，人们开始对动态引导系统进行研究。在美国，出现了电子引导系统（ElectronicGuidanceSystem），它能接收外部的无线电信号，获得所需的信息。电子引导系统在很大程度上克服了路标和地图的缺点（静态、易过时，有时给出不完整甚至错误的信息）。在英国，有一种传统的行车路线咨询服务。提供此项服务的有AA、RAC等组织。司机只要把起点和终点以及选择路线的标准告诉某一组织，就可以得到路线服务信息。它们提供的服务形式主要有两种：1.行车路线图：在一张地图上，把行车路线用特殊的颜色或高亮度显著地标记出来。2.文字指令表：在表中，用项细的描述告述司机每一步该如何走，包括经过的街道。公路和沿路的建筑物等。起初，这种服务都是用手工完成的。后来，随着计算机技术的发展，手工作业逐步被计算机作业所代替。1.2.2路线查寻系统的发展现状现代计算机和通讯技术的飞速发展，给真正意义上的路线查寻系统的产生创造了条件。美国、日本和欧洲在这方面的研究与开发水平处于领先地位。首先看一看美国的情况。美国在八十年代提出了一个交通战略计划，叫做“智能车辆／公路系统（IVHS）”计划，在IVHS中，一个很重要的组成部分就是路线引导系统。图1.2所示是它们的关系图。图1.2IVHS系统构成图在欧洲也有两个交通战略计划，叫做PROMETHEUS和DRIVE、PROMETHEUS计划的目标是开发公路交通电子系统，参加者是欧洲的大部分汽车制造商。DRIVE计划的目标是建立集成的公路运输环境，它包括很多具体的项目。1.2.3路线查寻系统的未来发展趋势一、路线引导系统和交通控制系统的集成路线引导系统和交通控制系统所需求的数据互有重叠，两个系统相互作用。路线引导的结果影响交通信号的控制，反过来，交通信号的控制又影响对路线的选则。所以两个系统的集成可以共享数据，消除不稳定性和反馈的负作用，提高整个交通网络的性能。两系统的集成有三个不同的成次：（1）互换数据（2）一个系统的输出作为另一个袭用的输出，反之亦然。（3）完全的集成二、预测型引导系统路线引导系统的目标是要提供智能和安全的建议，这就要求不仅中国要考虑当前的交通状况，同时也要考虑在汽车到达目的地的过程中将要发生的情况。在计算最优路线时，使用路段的预测权值，而不是当前权值，这样的系统就叫做预测型引导系统。三、通讯手段不断更新汽车和交通控制中心的通讯可考虑的方式有红外通讯、微波通讯、FM无线通讯、卫星通讯等。在欧洲，蜂窝移动电话网络正在逐步建立起来，以移动电话为通讯手段将会被越来越多的路线引导系统所采纳。九十年代是以来，计算机网络在全世界范围内得到了迅速的普及和应用。可以想象，若把许多车辆组成一个计算机无线通讯网，使每一辆车都成为一个流动的网络站点，则不但车辆可以和网络中心通讯，而且车辆之间也可以互换信息。四、路线引导系统向路线综合查寻系统过度交通路线引导系统只向司机提供路线引导信息。然而，司机却需要更多的信息。现代技术的发展为此提供了可能。未来的交通路线引导系统将发展成为一个路线综合查寻系统。它不仅提供路线信息，而且可以提供其它方面的信息，如有关周围旅馆、饭店的情况等。此外，还可以作为娱乐系统，播放多媒体图象和音乐。五、路线综合查寻系统由个体引导向集群引导转变当安装有路线引导系统的车辆为数不多时，各个车辆在计算最优路线时可以不考虑其它车辆，而只根据所获得的当前交通信息计算即可。然而，若许多车辆都安装了路线引导设备，个体引导可能会出现这种情况：许多车辆离开某一交通拥挤路段，都驶向某一畅通地区，从而造成新的交通堵塞。为了避免这一情况，在计算最优路线时，必须统筹考虑，实现集群引导。1.3我国研究和建立路线综合查寻系统的必要性和现实性公路运输对于一个国家来说是不可缺少的交通动脉，要想搞好交通除了作好宣传教育外，还要着手解决交通堵塞现象，减少交通堵塞及交通事故的发生，避免对国家会造成巨大的经济损失。公路运输的发展水平也是衡量一个国家经济发展程度的标志。我国是世界上人口最多的国家，特别是在大城市，人口密度非常大。随着经济的发展，城市内的各种车辆也急剧增加。同时，道路新建、扩建、对新旧城区的建设、改造，使城市的道路网络状况发生了极大的变化。然而，我国在路线查询系统方面研究不多，于国外有很大的差距。我国应借鉴国外已有的理论和技术，研究和开发符合我国国情的路线综合查寻系统，尽快方便广大的顾客的需要，在不远的将来，在此基础上对交通进行管理和控制，进而实现路线综合查询系统。1.4已有工作基础和本论文的研究内容本人对数字地图信息的矢量化图象处理，以及启发式搜索算法，曾经做了大量的学习和研究工作；并且对道路状况（掌握单行线、各个时间段中道路的车流量情况及所需要的花费）、交通规则、公交车线路及车站位置等特定信息做大量的调查与分析工作。在此基础上，本文主要研究如何利用计算机内的各种信息，对行人提供最佳乘车路线及下车后如何走到目的地的最佳行走路线；对骑车人提供距离最短的骑车路线；对驾驶员有以下三种情况的选择：时间最短、路径最短和时间与消耗费用评估分别来进行最优行车路线。它利用计算机帮助游客或驾驶员找到一条从出发地到目的地的最优路线，同时向驾驶员提供路线引导地图，向游客提供最优乘车路线及所经过的站名的引导地图，以及游客下车后到目的地的最优行走路线。应用这种系统，能帮助对地理环境不熟悉的游客或驾驶员准确、快速地到达目的地。它包括内容如下：(1)如何将道路地图信息转化为数字地图数据库，来存储道路网络的拓扑信息，以及其它的相关数据信息。(2)如何根据道路上的具体情况，根据不同用户的要求时实计算出最优路线。(3)如何将所在地区所有单位、住宅楼的具体信息和与其有关的相关信息，建造单位数据库。(4)如何将存储公交车站顶点网络的拓扑信息，及相关数据，建立公交电汽车车站地图数据库。(5)如何利用用户所掌握的某单位的具体信息（如地址、电话、单位类别等）来查找该单位的具体位置及信息。(6)如何向用户提供常用服务信息（飞机时刻表及售票地点、火车时刻表及售票地点、宾馆、旅店、名胜古迹、购物场所、医院、派出所、银行及出租车汽车公司等）。(7)如何将计算得出的信息，直观的显示给用户。其核心内容是建立数字地图数据库和启发式路线搜索算法。小结：本章主要讨论了路线综合查寻系统的概念、结构和分类，路线综合查寻系统的发展、现状和趋势。路线综合查寻系统作为一种新生事物，它在人们现实生活中所起的作用已经开始被人们所重视。计算机和通讯技术近几年来发展十分迅速，人们的生活也随着它们的发展而改变。路线综合查寻系统正是靠这两项技术发展起来的。在不远的将来为司机提供了大量的路线和交通信息，使司机在自己的车内就能知道所有道路网络的交通状况，而可以迅速的到达目的地是我们以后最终要实现的目标。路线综合查寻系统组成及实现技术本人开发了一个路线信息查询系统RMQS1.0系统。在RMQS1.0系统中，对最优路线搜索做了比较深入的研究，并提出了一个新的路线搜索算法启发式搜索算法。本章将对RMQS1.0系统的设计与实现过程进行了详细描述。2.1系统总体设计2.1.1路线信息查询系统结构和功能路线信息查询系统结构如图3.1所示。图2.1为路线综合查询系统组成的总体模块结构图查询系统所具有的特点和功能如下：1)地图的局部放大、缩小显示。2)按不同类别、单位地址、单位电话和地图查询等情况进行查询。3)按照时间最短、路径最短和时间与消耗费用评估来进行最优路线搜索，也就是说，用户可以按照自己的需要选择不同的路线行驶。并向用户提供图形、文字两种说明。该系统向用户提供多种形式的引导信息，使用户及时准确的掌握所需的信息，满足顾客的要求。4)方便的起止地址输入。路线信息查询系统向用户提供一个起止地址的输入窗口，用户需在地址列表中用鼠标进行选择或直接由键盘输入，即可输入出发地和目的地名称。5)在最优乘车路线在地图上的显示并配以文字说明。6)能对沈阳市所有单位、住家进行查询。该系统向用户提供多种形式的地点查询，使用户迅速找到所查单位或住家的地址。7)能对沈阳市所有宾馆、飞机和列车时刻表、旅游和购物场所等进行查询。使用户及时准确的掌握所需的信息。2.1.2路线信息查询系统运行的系统平台1、路线信息查询系统运行的硬件环境为：·586微机：586主板，PENTIUM200的CPU，64M内存，2G硬盘。路线信息查询系统的开发和运行都是在上述硬件平台上进行的。·数字化仪：型号为SummagraphicBitPadOneMode11。数字化仪包括数字化图形输入板和点收取设备（游标或触笔）。数字化仪用来把纸张地图转化为数字地图存到计算机中。2、路线信息查询系统运行的软件环境是：·中文Windows95Windows95操作系统是路线信息查询系统运行的操作系统。·AutoCAD利用该软件和数字化仪，可以形成数字地图数据库。·PowerBuilder5.0PowerBuilder5.0是系统应用的开发工具。PowerBuilder5.0是优秀的可视化编程语言，它采用事件驱动编程方法，开发效率高。PowerBuilder5.0提供ODBC（开放数据库互连）支持，可以访问Access、Foxpro等多种类型的数据库。PowerBuilder5.0可以直接调用WindowsAPI函数，从而大大提高PowerBuilder5.0的功能和灵活性。正因为PowerBuilder5.0具有这些优点，所以本系统全部采用PowerBuilder5.0语言进行开发。2.1.3路线信息查询系统的开发过程路线信息查询系统的各个功能模块是一个统一的整体，整个系统的开发可以分为五个步骤来进行：建立数字地图数据库和各种类型的数据库主要的任务是将纸张地图进行数字化，得到数字地图数据。数字地图数据库和建立好的各种类型的数据库就成为地图显示、路线搜索和路线引导的数据源。2、显示数字地图和文字说明以图形方式显示数字地图并配以文字说明，是向司机提供最直接的方式之一。它的主要任务是利用数字地图数据库的数据，创建图元文件，并在屏幕上显示出来。3、最优行车路线搜索最优行车路线搜索模块是本文研究的重点。主要是针对道路网络的实际情况，根据顾客的要求找出从起点到终点的最优路线的算法。最优路径的算法指的是速度快、节约、所得的结果是接近或等于最优值，并生成图形、文字的路线引导图。4、最优乘车路线搜索在路线信息查询系统中，提供给旅客的乘车路线是按经过最少站点的数量找出从起点到终点的最优乘车路线，并提供图形、文字的乘车路线引导图。5、设计用户界面好的软件系统必须具备好的用户界面，界面的好坏直接影响软件性能的发挥。把设计用户界面作为系统开发最后阶段，就是要把前面所做的工作集成到一起，使各个功能模块之间能够相互协调，给用户提供一个舒适的使用环境。下面各节将按照上面所述的顺序详细地阐述每个步骤中使用地算法，所遇到地问题和解决方法，以及所得结论。2.2系统模块路线综合查寻系统是由系统维护模块、单位查询模块、路线决策模块和服务区、服务查询四大功能模块组成。各模块之间相互关联，互通信息，协同完成整个系统的功能。下面将分别对四个模块的实现方法和技术进行介绍。2.2.1系统维护模块系统维护模块提供了对数字地图数据库、单位地图数据库、交通流量数据库和车站地图数据库进行增加、删除、修改的功能，当道路、单位、交通流量、公交汽车站及车次发生变化时，能够随时进行增加、删除、修改，以便更好地为顾客服务。一、数字地图数据库的维护当城市道路网络发生修改后，数字地图数据库也应相应的进行修改，考虑到有时在一张白纸上临时画上含有路线与代表大楼、机关、单位等“最小点”的示意性草图。利用多用户操作过程可形成该草图的临时性电子地图数据文件。由于所给出的两点坐标不可能精确，及草图不可能符合比例尺要求，而系统在输出显示时是以“电子地图”叠加在原来的电子地图上面的方式，如不加以修正，就会引起混乱。为了克服这种现象，系统利用其已形成的标准电子地图数据库，按新输入的电子草图的道路名称、“最小点”名称自动核对并进行位置修正，结果实际显示的结果是在原电子地图上精确地标出了他要画出的那些内容(全部以高亮度或特殊颜色出现)。对若干临时性的“最小点”很可能原电子地图不存在，经上述修正过程之后，该“最小点”的位置相对于草图上道路(两侧)的位置关系而获得了一定程度的修正，程序操作员用鼠标对该点位置稍加修正，就会出现满意的结果。在屏幕上电子地图为背景或通过输入经、纬度获得代表不同对象的“最小点”位置，作为鼠标触发对象，实现对该点实际对象的信息输入或输出。“最小点”显示图标由用户指定，其在屏幕上出现时占有的“面积”不受图形放大或缩小的影响。二、单位地图数据库的维护当某单位所在地发生变化、单位已经不存在、有新的单位产生时，要对数据库进行增加、修改和删除，以保持数据库的完整性和一致性。图2.2为路线综合查询系统中系统维护模块结构图三、车站地图数据库的维护当某公交车站的位置发生变化、有新的公交车线路产生、某路公交线路取消时，要对车站数据库进行增加、修改和删除，以保持数据库的完整性。交通流量数据库的维护（一）如何维护当某段公路的交通流量，在某以时间段发生变化、某条道路发生改变（如该为单行线）、新的道路产生等情况时，要对交通流量数据库进行增加、修改和删除，以保持数据库的实时性、完整性。（二）对未来的展望近十几年来，科学技术有了迅速的发展，尤其体现在通讯技术和计算机技术。在通讯方面，移动通讯被受关注。移动通讯的一个在重要应用领域是在车辆、船只和飞机上。在车辆上安装移动电台（车台），就可以和交通中心进行通讯，获取实时交通信息和向交通中心反馈信息。前面两节简述了射频通讯和红外通讯，下面将介绍其它几种已经获得应用或正在研究的移动通讯方式。1）数字蜂窝移动通讯蜂窝移动通讯自其80年代问世以来，发展十分迅速。目前，第一代模拟蜂窝移动电话系统正在被第二代数字蜂窝移动电话系统所取代。当前国际上正在开发和已进入商用的数字蜂窝移动系统有三种制式：第一种是欧洲电信标准协会（CEPT）建议的泛欧数字移动通讯系统（GSM），第二种是美国电信工业协会（TIA）提出的DAMPS（IS-54）系统，第三种是日本的JDC（DNTT）系统。GMS系统是当前发展最成熟的一种数字系统，具有频率利用率高，成本低，保密性好，可以全欧漫游等优点。蜂窝移动电话通讯系统以若干个相邻的蜂房式（正六边形）小区覆盖范围组成服务的大中容量移动电话通讯系统。蜂窝移动电话通讯系统由移动业务交换中心、基站、移动台（车载台、手持台等）及传输电路组成。图2.4所示为数字蜂窝移动通讯示意。这种系统除了能提供话音外，还可以提供多种非话业务（数据业务等），可用于车辆和交通控制中心进行通讯。卫星移动通讯卫星移动通讯系统是指以卫星为基础，在广泛地理区域内，为行驶中的车辆、船等移动物体提供多种业务的系统，即通过卫星实现移动台与固定台、移动台与移动台以及移动台或固定台与公共网用户之间的通讯。它既有卫星通讯的覆盖面又有移动通讯的灵活务。移动卫星通讯系统主要由卫星转发器、主站（网络控制中心）、基站、网间转接站、网络协调站和远程移动站组成。数据广播数据广播是利用数字编码传输技术通过无线信道向多用户传输信息的方式。它的基本原理是：运用调制解调技术，将信息转换为数字信号发射出去，再通过接收机对信号解调，还原为原来的数据。调频解调占有较宽的频带，所以可以在不影响调频广播的前提下，利用空闲的频带（SCA副信道）传输信号，同调频广播一起发送出去。美国各大中城市中，已由80%以上的调频广播台开展SCA业务。日本已成功研制出调频副信道固定接收信息的系统设备，移动接收信息的系统已完成了基础实验，除了用于传输时交通信息外，还传输股市行情等数据。数据广播作为信息传输的新方式具有速度快、传输成本低，可移动接收和多用户接收等特点，可弥补其它传输方式的不足，尤其在我国通讯尚不十分发达的情况下，普及应用数据广播对有效提高信息利用率、扩大信息传播范围、提高信息共享程度具有十分重要的意义。我国现有调频台4000多个，其中4千瓦以上的大功率调频台1000多个，每个调频台都有SCA复信道可利用，因此我国的SCA资源十分丰富。由于复信道是利用调频台原有的发射设备和天线，与调频广播同时发送的，这样就为副信道的利用提供了便利。2.2.2查询模块查询模块主要是为了让用户根据其所掌握的部分不完备的信息，迅速查取用户所想了解的相关所有详细信息，它包括单位类别查询、单位名称查询、单位地址查询、单位电话查询和单位名称尾字查询，也可在地图上任意点中某一位置就能反映出该位置的单位，及相关的其它应信息。单位类别查询是根据单位的行业（如厂矿、邮电、机电、卫生等）来实现。单位地点查询是根据单位的邮政编码和所在区、街道等信息来实现。单位名称查询是根据单位的名称，也可以是单位的尾字来实现。单位电话号码查询是根据单位的电话号码来实现。以上四种查询可以是与的关系，若所掌握的单位信息不详细则把符合该条件的所有单位都列出来共顾客来选择。地图查询是顾客知道所查询的单位在地图上的位置时，通过把光标移到该位置时，击打鼠标左键后系统自动显示出该单位的信息来实现。单位查询模块利用存储在单位地图数据库中的信息，能迅速、有效地查出所需单位的信息。单位查询模块结构图如下：图2.3路线综合查询系统中单位查询模块结构图2.2.3决策支持模块决策支持模块的功能包括最优乘车线路的查询、骑车路线查询、时间和消耗费用综合评价最优的行车路线查询及相关信息的显示。此模块接收驾驶员或游客的输入数据，再根据计算机中所包含的有关道路、乘车的信息和出发地、目的地的位置数据，计算出最优或准最优路线。然后，将最优路线引导信息等显示在屏幕上，配以文字说明并打印出来。决策支持模块是本文研究的重点，利用数字地图数据库和交通流量数据库来计算出最佳路线。决策支持模块结构图如下：图2.4路线综合查询系统中路线决策模块结构图目前，有很多最优路线搜索算法，如比较典型的图论中的Dijkstra算法，人工智能中的启发式搜索算法等。对于算法的选择，主要看其运行效率计算时间的长短，所得路线得最优化程度。本文将在第四章进行详细的讨论。一、乘车路线查询模块这是路线信息查询系统系统的一个主要部分。在进行搜索之前，首先由用户输入目的地。然后，乘车路线查询模块对游客计算出一条从出发点到达目的地，所经过车站站点最少的最佳乘车路线。二、骑车路线查询模块骑车路线查询模块对骑车人提供一条从出发点到达目的地，所经过的距离最短的最佳骑车路线。本文采用了人工智能中的启发式搜索算法思想来实现。三、行车路线查询模块这是路线信息查询系统系统的一个关键部分，对驾驶员计算出一条从出发点到达目的地的时间和消耗费用综合评价最优的行车路线。本文采用了人工智能中的启发式搜索算法，建立了一个关于时间、距离和消耗费用的功能评价函数来实现。四、路线引导图路线引导图就是在路线搜索结束后，把路线图打印出来并配以文字说明，引导旅客或驾驶员下一步的路线如何走。对驾驶员提供行车路线引导图，在地图上把所经过的路口以亮点的形式显示出来，并在所经过的道路中，标出有明显标志的单位和所要经过的街道名。对游客提供乘车路线引导图，在地图上把乘车所经过的车站以点的显示出来，并用文字说明该站点的站名和所乘的车次，如果要转车，则提供如何转车的说明。2.2.4服务查询模块服务信息查询是为顾客提供了飞机时刻表及售票地点、火车时刻表及售票地点、宾馆、旅店、名胜古迹、购物场所、特殊服务（包括医院、派出所、银行及出租车汽车公司等信息）等查询功能。此功能为顾客更好的、合理的安排游览时间和先后次序提供了保障。图2.5路线综合查询系统中服务查询模块结构图2.2.5人机界面人机界面是用户与系统联系的窗口。人机界面的好坏，决定着路线查询系统能否被用户接受，决定着系统的性能能否有效地发挥。人机界面的硬件组成一般包括：彩色显示器、喇叭等输出设备，键盘、鼠标等输入设备。通过人机界面，用户可以查询所需的信息（出发地、目的地等），并得到声音提示和图文并茂的信息显示。随着计算机性能的不断提高和软件技术的不断发展，以WINDOWS为代表的多窗口图形用户界面正在成为应用的主流。在图形用户界面下，用户只要用鼠标点几下就可以完成大部分的操作。人机界面对于一个应用系统来说是十分重要的。应用系统只有具备好的人机界面，才容易被用户所接受，才能使其功能得到比较充分的发挥。在路线信息查询系统中,实现了多文档图形用户界面。容许用户在一个应用中使用多个文件。小结：路线信息查询系统由查询模块、系统维护模块、决策支持模块、服务信息查询模块组成。本章对查询模块、系统维护模块、服务信息查询模块的功能进行了较为详细的论述，对决策支持模块只进行了简单说明。数字地图数据库是路线引导系统中使用的最重要的数据源，它在三大模块中都要用到。下一章将对数字地图数据库的内容、数字地图数据库标准和创建数字地图数据库的步骤进行说明。决策支持模块是本文研究的重点，这方面的内容将在后面的章节进行详细的讨论。数据库的设计与实现数据库的设计和具体实现是开发道路查询系统的基础，良好的数据库设计对图形的快速显示、提高搜索数据和运算时间都占有重要的地位。随着科学技术的进步，探索、研究和实现数据库的设计是我们的追求。3.1建立数字地图数据库3.1.1数字地图数据库总体概述道路数字地图数据库是路线综合查寻系统的基础。所谓数据库就是相关数据的集合。一般道路数字地图数据库存储的数据分为动态和静态两种。例如，路线的位置、长度是静态数据，而交通流量是动态数据。道路网络可以看作为图论中的图。所有道路相当于图中的边,或叫做链；所有路口相当于图的顶点，或叫做节点。节点和链组成的图是实际地图的一种向量表示。道路数字地图数据库是节点和链的数据的集合。节点和链都以记录的形式存储在数据库中。节点的记录包括以下数据项：节点号、节点名、位置坐标、所在链号、转弯限制等。链记录中的数据项有：链号、链名、起止节点、链长、车辆通过该链各个时刻的行驶时间等。地图数据在逻辑组织时一般分为若干层，即有一个基本层和多个附加层。基本层中存储的是组要街道的数据，附加层中是有关某类实体的数据，如旅馆、飞机场、火车站、单位等。各个附加层可以透明的叠加到基本层上。这种组织形式便于对地图上的内容进行人为控制。为了减少冗余，有最大限度的灵活性，地图数据在物理组织时一般分为多个文件。每个文件存储一类数据，各个文件之间通过共同的数据项连接起来。1、数字公路地图标准整个公路网络由主公路网（BasicRoadNetwork）和全公路网（AllRoadNetwork）组成。主公路网由国家级和省级高速公路以及宽度对于等于5.5米的公路组成。全公路网包括非主公路网覆盖下的全部道路且宽度大于3米的公路。2、位置和道路表示用正规化坐标（X：0-10000；Y：0-10000）来表示实体的位置。道路网络由节点和链组成。为了精确的说明高速公路和汽车专用公路在不同方向上表示为两条独立的公路。节点可以是交叉路口、路尾、道路属性变化点。主公路网使用四位数字的节点号码，全公路网使用五位数字的节点号码。链号由其端点节点号组合而成。3、数据库的结构数据库由一组文件组成，每个文件包含表3.1所列的数据。表3.1数据库层次4、数据来源获取数据的来源有：a）1：25000的地形图。对郊区、农村用1：50000的地形图b）公路交通管理局所提供的数据c）市城市建设地名办公室所提供各单位地址及道路的名称d）其它参考资料和数据道路数字地图数据库所包含的数据量大，数据类型多，需要大量的人力、物力来完成。开发数据库一般包括四个步骤：数据准备、数据输入、数据校验和数据维护。数据准备即获取原始的数据。一般从有关公路管理机构、城市建设机构、地名管理机构和交通信息。数据输入就是把原始数据输入到计算机的过程。此过程要用数字化仪、扫描仪等设备。数据校验的主要任务是将输入到计算机中的数据和原始数据相比较，并修正出现的错误。数据校验是十分必要和关键的一步。一般在数据输入过程的重要环节都要进行数据校验，以确保数据的正确性和完整性。数据维护，指的是数据库建成之后的后期工作，主要是数据的更新。这一阶段工作量也很大，因为每年都会有旧路改建和新路建成。道路数字地图数据库的最主要的应用是路线查询系统。路线搜索，路线引导，地图显示等都需要道路数字地图数据库的支持。但是，随着道路数字地图数据库的发展，它将开始应用到越来越多的领域：交通事故分析系统环境管理系统公路检测系统等。不同的国家地区，不同的开发者，根据当地的特殊情况，针对不同的目的数据库的内容和组织形式也不尽相同。这就为数据库间的数据共享和判断数据库的质量好坏提出了麾题。为此，世界上一些发达国家制定了相应的数据库标准来解决这个问题。3.1.2数字地图数据库具体设计在建立数据库之前，首先要进行数据库设计。这里主要指数据库概念设计和逻辑设计。数据库概念设计就是根据需求分析得到的材料，绘制出数据库的初步设计。进行概念设计通常所使用的概念数据模型是实体-关系模型，即E-R图。数据库逻辑设计的任务是根据设计的结果，设计数据库的概念模式和外模式。采用自顶向下的设计方法，进行概念设计，得到如图3.2的E-R图。图3.1对数字地图数据库进行概念设计所得到的E-R图把E-R图转换为关系数据模型后，有如下两种关系：节点（节点号、节点横坐标、节点纵坐标）2)链（链号、链名、链长、起始节点号、终止节点号、禁行标志节点、道路属性）经过综合分析，将上面两个关系转化为Node和Link两个表。它们的结构如下：表3.2Node表的结构3.1.3地图矢量化1、矢量交通地图的自动生成方法为：①彩色扫描仪对交通地图的扫描输入。在分块扫描时则依据不同情况进行(按分块区域坐标数据)自动拼接或插入②道路特征指定(颜色或宽度)与提取，矢量交通路线图的自动生成③路名与路况、总长、交叉点等信息的计算机辅助输入与基本数据库建立。④精确位置修正。包括区域两点式坐标定位，比例尺竖向或横向线性补偿，局部路线修正等⑤允许在包括道路属性的子功能上，由用户增添对该条道路特定的信息标题并输入信息内容，形成扩展数据库点信息生成方法为：①以屏幕上电子地图为背景或通过输入经、纬度获得代表不同对象的“最小点”位置，作为鼠标触发对象，实现对该点实际对象的信息输入或输出。“最小点”显示图标由用户指定，其在屏幕上出现时占有的“面积”不受图形放大或缩小的影响②点信息包括名称、属性等文字信息，并自动进行数据格式转化形成压缩形式的信息数据库③点信息修改。实时打开相应的Windows应用软件进行再编辑，形成修改后的信息数据库文件。另外也可换位置修改。④允许对不同的点增加不同的信息标题与信息内容。当然，将来输出显示该点信息时亦为相应标题与内容3、临时性点、路线草图叠加考虑到有时在一张白纸上临时画上含有路线与代表大楼、机关、单位等“最小点”的示意性草图。显然，利用上述第⒈点的多用户操作过程可形成该草的临时性电子地图数据文件。由于所给出的两点坐标不可能精确，及草图不可能符合比例尺要求，而系统在输出显示时是以“电子地图”叠加在原来的电子地图上面的方式，如不加以修正，就会引起混乱。为了克服这种现象，系统利用其已形成的标准电子地图数据库，按新输入的电子草图的道路名称、“最小点”名称自动核对并进行位置修正，结果实际显示的结果是在原电子地图上精确地标出了他要画出的那些内容(全部以高亮度或特殊颜色出现)。对若干临时性的“最小点”很可能原电子地图不存在，经上述修正过程之后，该“最小点”的位置相对于草图上道路(两侧)的位置关系而获得了一定程度的修正，在用鼠标对该点位置稍加修正，就会出现满意的结果。4、实时信息叠加与立即使用，以及新信息的添加规则对已经形成的矢量电子地图及相应的文字信息数据库文件是作为永久性存储并利用备份、纠错等功能对已形成的“精确地图”严加维护。区域地图显示时用以形成显示屏上的主体背景。对临时性的草图总是先形成临时性的以矢量电子地图为核心(和索引文件)的信息数据文件，并当即调用原有“永久性”数据库对新的“临时性”数据文件进行自动修正(如上述第条所述)与叠加显示。系统将自动提取出临时数据文件中的新信息，并添加进“永久性”数据库。两种情况下，实时信息均可被使用。5、辅助决策功能系统使用户在电子地图显示屏前用鼠标随时打开任一条道路、任一“最小点”图标，在相应的弹出窗口子菜单上提取所要求的各种信息，这是系统输出时的基本功能。系统的辅助决策功能不是指这种功能，而是直接分为一般询问、高级决策与用户指定决策三种形式的决策子菜单功能。一般询问包括询问任一点位置、任两点距离、任一方块面积、任一区域内的特种对象信息(例如报警单位电话救护单位地址、电话等)。高级决策指带有一定寻优规划，由系统实时按照已安排好的决策计算步骤，根据用户所指点或路的输入信息，从系统信息数据库提取相关信息并经计算显示告诉用户的有关“实时决策”结果，例如封闭指定点的所有交通要道列表，离指定点最近的救护单位信息，去该指定点的最优路线等。用户指定决策与高级决策类似，但系统必须按照用户安排好的决策计算步骤来进行决策并显示相应决策参考信息。数字化仪是进行图纸数字化的专用设备。AutoDesk公司的AutoCAD软件是进行计算机辅助设计的专用软件，功能强大。提供一种数字化仪接口。通过此接口，可以实现地图数据的计算机输入。本系统在进行地图数字化时，所使用的数字化仪为SummagraphicBitPadOneModel11。该数字化仪图形输入板面积为420*330MM，有两个定位器（点拾取设备），一个是四按钮游标，另一个是类似笔的触笔。数字化仪通过电缆连接到计算机的一个串行输入/输出口上（缺省值为COM1）。重新配置。配置过程如下：（1）启动AutoCAD，进入主菜单。0.ExitAutoCAD1.BeginaNewDrawing2.EditanExistingDrawing3.PlotaDrawing4.PrinterPlotaDrawing5.ConfigureAutoCAD6.FileUnlashes7.CompileShape/FontDescriptionfile8.ConvertOldDrawingFile9.RecoverDamagedDrawingEnterSelection:选择5，进入AutoCAD配置菜单。0.ExitToMainMenu1.ShowCurrentConfiguration2.AllowDetailedConfiguration3.ConfigureVideoDisplay4.ConfigureDigitizer5.ConfigurePlotter6.ConfigurePrinterPlotter7.ConfigureSystemConsole8.ConfigureOperatingParametersEnterSelection:0选择4（配置数字化仪），屏幕出现可用的数字化仪一览表。从列表中选择SummagraphicBitPad，然后回车，从型号列表中选择OneModel11。保存配置，退出AutoCAD。再次启动AutoCAD，配置生效。在启动配置好的AutoCAD后，从菜单中选择“1”，进入图形编辑窗口。此刻还不能马上进行数字化工作，必须首先用TABLET命令重新配置数字化仪图形输入板并进行校准。在一般情况下，数字化图形板有效区域的大部分都用作AutoCAD的菜单区使用。现在要把整个有效区域用作图形数字化之用，所以需要重新配置数字化图形板。否则，就不能拾取屏幕指点区以外的点。这时，图形板的校准工作完成。再次执行TABLE命令，从“Option”中选择“On”，打开图形输入板方式，这时就可以进行正子真正的数字化工作。在数字化时，对于线状实体（公路、铁路、河流等）使用“LINE”命令，对于点状实体（建筑物等）使用“POINT”命令。在数字化完成后，以图形交换文件格式把数据存储到计算机中。由于所使用的图形输入板比较小，地图比较大，一次无法完成全部地图的数字化。解决的方法是，把整个地图分成几个小块，对每个小块分别进行数字化。在更换数字化区域时，必须重新使用TABLE命令，使地图坐标和屏幕坐标对应起来。3.1.4数据转换用AutoCAD把地图数字化之后，生成图形交换文件。图形交换文件中存储的时点的坐标。现在的任务是要把图形交换文件中有用的数据转换PowerBuilder数据库中。下面说明一下图形交换文件的结构。图形交换文件是ASCII文件，扩展名为DXF。它由五个段组成：标题段、表段、块段、实体段、和文件结束。标题段由描述图形信息的一组标题变量组成，标题变量的值确定图形的参数设置和当前状态。表段包含了若干个表，每个表又包含可变数目的表项块段包括所有的块定义，它记录了当前的图层名、块的种类、块的插入基点和组成块的所有成员。实体段记录了每个实体的名称、图层名、线型名、基面高度、厚度和有关的几何数据。文件的最小组成单元是组（Group），每组占两行。第一行为组代码，第二行是组值，组值的数据类型取决于组代码的值。组代码与组值之间的关系列于表3.4中。表3.5组代码和组值对应关系表3.6组代码的意义根据组代码的值，可以容易地从图形转换文件中读出需要的数据。在已知图形转换文件格式和要转换成的数据库文件格式的情况下，可按如下步骤进行转换：1、打开准备接收图形转换文件中的信息数据库。2、打开图形转换文件，准备读取数据。3、从图形转换文件中读取一行数据，赋给变量TEMPDATA。如果其值不等于ENTITIES，则循环，直到相等为止，即找到实体段的开始。4、按照第三步的方法，从实体段中找到值为LINE的行，它标志着一条直线的开始。5、读取数据，直到等于10。组代码为10时，它的组值是直线端点X坐标值。在X坐标后面一行是组代码20，它的组值是直线端点的Y坐标值。6、读取直线另一端点的坐标。7、将得到的直线坐标数据写入数据库文件中。其中，点的坐标值写入NODES表中，而把直线的起点和终点信息记录在LINK表中。8、重复执行4-7步，TEMPDATA=“ENDSEC”。9、关闭所有的文件，然后结束在把图形转换文件中的数据全部输入数字地图数据库之后，数据库并没有完全建好，还需要进一步的处理，以满足整个系统的需要。还要做以下的工作：·输入节点类型信息。因为在图形转换文件中没有记录有关节点类型的数据，必须手工处理。·清除NODES表中的冗余记录。一条直线有两个端点，两条直线相交则有一个公共端点。在数据转换过程中，只是把所有的点都写入数据库中，这样公共端点接被存储多次，造成空间浪费，必须清除。·填充LINK表的POINTONLINK字段。在数据转换时，在LINK表中只记录了路段的起点和终点，而没有记录路段的形节点。·输入其它信息。如道路的长度、宽度、地址、时间表等。上面的工作全部完成之后，一个比较完整的数字地图数据库就建成了。系统的其它模块都是以这个数据库作为基本的数据来源，是以后工作的基础。3.1.5显示地图与文字说明路线信息查询系统向用户提供图形化地图并且能在地图上显示各种文字信息说明。通常，在屏幕上显示数字地图的方法是：从数据库中读取路段的起点和终点的坐标，然后在屏幕上画线，直到整幅地图画完。但是，这种方法的致命弱点是速度太慢，不能满足应用要求。为此使用一种新的方法（图元文件法）事在必行。一、图元文件的建立图元文件是建立所需文本或图象的GDI命令的集合。图元文件是用二进制编码的GDI函数集，通过产生一个图元文件设备环境来产生一个图元文件，这些GDI调用实际上并不做任何工作，而是把它们存放在图元文件中。在关闭图元文件设备环境时，得到图元文件的一个句柄，然后可以在实际设备环境上操作图元文件时，WINDOWS将图元文件分解为记录并使用每个记录中的参数执行合适的函数。图元文件和位图文件相比，有几个显著的优点：占用内存空间小，比位图具备更大的设备独立性，可以进行无级放大而不失真。图元文件不及位图文件的一点是显示速度稍慢。通过在中直接调用函数，大大增强了自身功能和编程的灵活性。使用函数的另一个优点是可以是程序执行速度明显加快。二、图元文件的显示图元文件建立好后，如何将其显示在屏幕，在给出具体的显示之前，首先要了解WINDOWS的坐标系统和映射方式。为了保持设备无关性，在WINDOWSGDI函数中，所使用的坐标都是以“逻辑单元”为单位的。WINDOWS必须把这些逻辑单元转换成设备单元，即象素。这种转换是由映射方式、窗口和视口原点及窗口和视口限度控制的，映射方式也影响原点和X轴及Y轴的定位。映射方式定义了WINDOWSGDI如何将函数中给出的逻辑坐标映射成设备坐标。其中，MM_TEXT为缺省的映射方式。在这种方式下，逻辑单元和物理单元相等，可以直接以象素为单位进行工作。MM_TEXT映射方式所使用的坐标系如图3.3所示：左上角为坐标原点(0,0)，X轴的坐标自左向右增加，Y轴坐标自上而下递增。这种坐标系统符合人们的习惯。第八种映射方式为MM_ANISOTROPIC，它是一种“不受限制”方式，可以改变窗口和视口的限度值，使X轴和Y轴上的逻辑单位具有不同的物理量纲。在后面的地图显示子程序中，将用到这种方式。WINDOWS使用下面的两组公式进行逻辑坐标和设备坐标的相互转换。表3.7大表在大多数映射方式中，限度值是由映射方式隐含的并且不能改变，每个限度值本身意义，但由它构成的四个比值（xViewExt/xWinExt、yViewExt/yWinExt、xWinExt/xViewExt、yWinExt/yViewExt）是用来对逻辑单位进行扩展或压缩的比例因子。在地图数字化时所采用的坐标系如图所示的坐标系。图3.2图标所以在显示地图时，还必须使用同样的坐标系，即左下角为坐标原点（0,0）,x轴坐标向右增加，y轴坐标向上增加。所以，必须把Windows默认映射方式所使用的坐标系转换成图3.4所示的坐标系。在完成坐标系转换之后，调用函数即可把图元文件中的内容重放出来。在上面的程序中，Soure是一个图片框对象的名称。在连续调用SetMapMode（设置映射方式）、SetWindowExt（设置窗口限度值）、SetViewportExt（设置视口限度值）、SetViewportOrg（设置视口原点）四个函数之后，图片框被置于正确的坐标系之下。图片框的左下角为坐标原点（0,0）右上角坐标为（MapWidth,MapHeight），如图3.5所示。通过调用PlayMetaFile函数，整幅地图在图片框中完整的重画出来。图3.3图片框在坐标系的位置（MapWidth,MapHeight）三、地图浏览与缩放功能的实现在路线信息查询系统中，提供了地图浏览和局部放大功能。实现此功能的基本方法是：在屏幕工作区放置两个大小不同的显示“窗口”（实际是两个图片框，分别叫做Picture1和Picture2,Picture1为较小的图片框）；在较小的窗口中显示整幅地图，在较大的窗口中显示地图的一个局部；用鼠标单击较小窗口的一点，则用了一个缩放因子来动态调整地图的放大倍数。实现地图浏览与缩放功能所依据的基本原理是：1、图元文件的放大不失真特性。2、Windows映射方式及坐标系变换原理。图3.4地图浏览与放大原理示意图按照地图流览与放大功能的基本实现思路，用鼠标单击Picture1中任意一点P1(x1,y1)，则P1点应该显示在Picture2的中心位置P2(x2,y2)点处。也就是说，点p1和点p2的逻辑坐标是一样的。Picturel中的某一点和Picture2的中心点的这种约束对应显示关系，可分为以下几步来实现：所使用的符号意义如表3.8所示。表3.8表数整幅地图显示于图3.6所示的虚拟图片框内，但只有落在实线框中的部分是可见的。前面所述的变换过程，实际是在改变虚拟图片框的大小，从而使实线框中可见部分的放大比例得到改变：图3.5图四、地图信息的文字显示对于乘车路线，则在地图上把所经过的车站的位置显示出来，并把所经过的站点在图的下方配以文字说明；对于行车路线，则把所经过的道路口，以一个点的形式显示出来，在图的下方把两点之间所经过的街道名称显示出来。3.1.6建立单位地图数据库对单位地图数据库要求包括单位的邮政编码、电话号码、地址、行业类别、在地图上的坐标等信息。数据库的结构如下：表3.9单位表的结构3.1.7建立车站地图数据库对车站地图数据库包括各个车站的站点及每个站点所经过的车次、名称和站名等信息。采用自顶向下的设计方法，进行概念设计，得到如图3.2的E-R图。图3.7对车站站点进行概念设计所得到的E-R图把E-R图转换为关系数据模型后，有如下三种关系：1)节点（节点号、节点横坐标、节点纵坐标、经过该点的所有车次）。2)链（链号、起始节点号、终止节点号）3)转车（编号、节点号、下车车次、下车站名、上车车次、上车站名、转车说明）经过综合分析，将上面两个关系转化为CNode、CLink和Change三个表。它们的结构如下：表3.10CNode表的结构表3.11Clink表的结构3.1.8建立交通流量数据库对交通流量数据库，则把每条道路按一天24小时的交通流量的变化划分为一个个的时间段，计算出每段时间车辆通过该道路的时间。当以后通讯条件改善时，把这个数据库变成时实的交通流量数据库采用自顶向下的设计方法，进行概念设计，得到如图3.2的E-R图图3.8对交通流量进行概念设计所得到的E-R图把E-R图转换为关系数据模型后，有如下两种关系：时间（链号、各时间段通过该道路的时间）费用（链号、各时间段通过该道路所需费用）经过综合分析，将上面两个关系转化为Timecost、Change两个表。因为它们结构类似，所以只写一个表，表的结构如下：表3.13交通流量Timecost表的结构小结：本章对路线信息查询系统中数据库的设计和开发过程进行了详细论述，在下一章将对最优路线搜索算法作了重点讨论。建立数字地图数据库是整个系统开发的基础。建库过程包括数据库设计、地图数字化和数据输入等步骤。利用建立好的数字地图数据库在路线信息查询系统中实现了数字地图的显示及浏览放大功能。第四章路线搜索算法本节主要讨论应用于路线搜索子系统中的算法。路线搜索子系统是路线信息查询系统的一个关键部分。它必须要满足一定的实时性要求，既在给定的时间内能够找出一条最优或准最优路线。道路网络可以抽象成图论中的图。道路的交叉路口可看作是图的顶点（或称为节点），两个交叉路口之间的路段可看作图的边（后称为链）。这样，道路网络中求解最优路线的问题就转化为图论中的最短路径问题。目前，已经有许多较成熟的算法来解决图的搜索问题。其中，最著名的算法是Dijkstra算法。此外，深度优先算法和广度优先算法也被广泛应用。这些算法有个共同的缺点，就是计算时间随节点数的增加而呈指数增长。本节在对启发式搜索算法进行实验研究的基础上，结合神经网络中的遗传算法，提出了一个新的方法，称做启发式遗传算法。在讨论具体算法之前，先说明一下数据库中的数据在内存中是如何存储的。为了快速方便的读取数据库中的数据，定义了如下的记录结构存储每个节点的信息。通过访问相应节点记录的各个域就可以得到所需的数据。4.1启发式算法启发式搜索是人工智能领域中一种基本的问题解决方法。这种方法使用启发式知识来改善搜索算法的性能。在启发式算法中，启发式知识通过评价函数f(n)来表示。f(n)的值等于经过节点n的最优路径的实际权值。f(n)可看作是两部分相加的和F(n)=g(n)+h(n)其中，g(n)是从起始位置到节点n的最优路径权值。h(n)是从节点n到目标节点的权值。如果定义f’(n)、g’(n)和h’(n)分别为f(n)、g(n)和h(n)的估计值。那么f’(n)=g’(n)+h’(n)其中，g’(n)可以正确地计算出来，即g’(n)=g(n)。h’(n)是从节点n到终点的估计权值。如果对于图中任意一个节点，h’(n)小于等于h(n)均成立，那么称启发式算法为A*算法。A*算法已经被证明是可采纳的。即只要存在一条从起点到终点的最优路径，A*设法就可以找到它。启发式搜索算法比传统的Dijkstra算法所扩展的节点数要少的多。在此算法的每一步，都是选择“最好”的节点进行扩展。所谓“最好”是指其f’(n)的值最小。当到达目标节点时，最优路径也就找道了。4.2改进的启发式算法双向Dijkstra算法：双向算法已用于操作查找分析，见[LR89.Ma]。双向查找算法有两部分。第一阶段我们交替两个无向查找：一个从S开始，生长成S的一组点，这组点到S的最小路径是已知的；第二个包括d的一组点D，D中的点到d的最小距离是已知的。交替地给S和D加入结点，直至S到D的边产生。因此最短路径位于S和D地查找树中和S到D的边。算法的几何意义如下：我们在s和t上产生两个球，每一步，球增加一个单元。当两个球撞破时，算法结束：即存在一顶点是两个球的公共顶。路径s~v~t为s到t的最短路径，v是公共顶。引理：①s到t的最短路径至多有一条从S到D集合的边。②w(s-k-t)≤2w(s-t)证明：①w(s-k-t)是s到t过k的最短路径的权。让P=s~x-a-y~t表示最短路径含另一条边。从Dijkstra算法可得到不等式：w(s-x)+w(xa)≥w(s,k)。w(t-y)+w(y-a)≥w(y,k)。因此，w(s-x)+w(x-a)+w(ty)+w(y-a)≥w(s,k)+w(y,k),矛盾。②令s到t的最短路径为s~x-y~t,x∈S,y∈D.可得以下不等式w(s,k)≤w(s-x)+w(x-y)；w(y,k)≤w(t-y)+w(y-x)。∴w(s,k)+w(k,y)≤w(s-x)+w(x-y)+w(t-y)+w(y-x)≤2w(sx-y-t)定理8.2让a,b,c的常量定义n结点有向图的一组可能分配。边(i,j)有可能(alogn)/b被表示。对这些边，边长度le对可能分布是独立的，密度函数fe界于b,c之间。查找s-t的最短路径的双向Dijkstra时间为O(√n)。小结：本章对最优路线搜索算法作了重点讨论。第五章建立符合我国国情的路线信息查询系统国外已经有了较成熟的路线信息查询系统。但是，如果把这些系统直接拿到我国使用，不一定适合我国国情。因为我国的交通有其自己的特点，在建立路线信息查询系统时必须考虑我国交通状况。本章将对我国的交通现状及特点进行分析，然后提出对如何建立合适我国国情的路线信息查询系统的一些观点和看法。5.1我国路线查询形状和特点分析改革开放十几年来，我国的经济发展取得了举世瞩目的成就。与此同时，我国的城市和交通建设也获得了很大的发展。国家投入巨资于市政建设、建设公路、铁路等交通基础设施，使路线查询系统为人们所需。同时，在各大中城市，由于各种机动车辆迅速增加，尤