毕业设计（论文）-地铁线路智能查询系统的设计与实现.doc

北京理工大学硕士学位论文 I 摘摘 要要 我国城市地铁的智能查询系统发展处于一个较落后的水平，广大乘客可以 获得信息的方式很少，为了解决这种问题，加快发展城市地铁信息化，设计了 这个城市地铁线路智能查询系统。地铁线路智能查询系统是 MAS 技术和 Web 技术相结合的产物，利用基于地铁线路智能查询系统可以很方便的查询地铁站 点线路信息以及站与站之间的最优换乘路线的查询，从而方便了人们的出行选 择。论文主要研究基于 MAS 构建地铁线路智能查询系统的有关技术以及结合蚁 群算法设计了地铁线路智能算法。蚁群算法的应用是近些年人工智能领域的研 究热点，在工程应用、计算机仿真等领域都解决了大量的实际问题。在设计过 程中，作者首先介绍了蚁群算法的原理、特性，同时分析了我国城市地铁乘客 信息系统的发展现状。其次，在介绍、研究前人研究成果的基础上，结合各智 能算法，研究了在智能系统中的应用，包括构件、规则修改、信息素更新、收 敛测试、样本数据修改等几个重要步骤。同时，分析了地铁乘客出行的心理特 征，并在此基础上，融合乘客选择地铁线路决策的因素，建立了基于换乘次数 和时间长短的地铁线路选择模型，并完成了系统的设计。系统运用了动态缓存 技术对常用地铁线路进缓存，能获得很高的运算速度。设计的软件较为符合地 铁运营的实际情况，充分考虑了不同地铁乘客的实际要求，有较强的实际应用 价值。实验结果标明，该算法可以使专家系统准确有所保证。但是鉴于智能算 法中参数选择的复杂性，可以在以后的实践检验中通过继续优化规则和参数设 置，取得更加完美的成果。 关键词：关键词：地铁线路；智能查询；设计与实现 北京理工大学硕士学位论文 II Abstract The intelligent query system development of urban subway in a relatively backward level,the passengers can get information way very few, in order to solve this problem, speed up the development of urban subway informatization, the city subway line intelligent query system is designed. Subway line intelligent query system is the combination of the MAS technology and Web technology, based on the subway line intelligent query system can easily subway stations route information query and the optimal transfer between station and station route query, which facilitates peoples travel choice. Paper mainly studies based on MAS building subway lines of the intelligent query system about technology and the subway line intelligent algorithm combined with ant colony algorithm design. The application of ant colony algorithm is a hot research topic in the field of artificial intelligence in recent years, in the field of engineering application, the computer simulation, etc are solved a lot of practical problems. In the design process, the author firstly introduces the principle, characteristics of ant colony algorithm, and analyzes the development situation of urban subway passenger information system. Secondly, in the introduction, the research on the basis of predecessors research results, combined with the intelligent algorithm, in the application of intelligent system is studied, including the component, rule changes, pheromone update, convergence test, the sample data modification and so on several important steps. At the same time, the paper analyzes the psychological characteristics of subway passengers, and on this basis, the fusion of passengers choose subway line decision factors, based on the transfer number and duration of the subway route choice model, and complete the design of the system. System using the technique of dynamic cache to common metro lines into the cache, can get very high speed. Software design more accord with the actual situation of metro operation, give full consideration to the actual requirements of different subway passengers, has the strong practical application value. The experimental results indicate that the algorithm can make the expert system to ensure accurately. But because of the complexity of the parameter selection in intelligent algorithm, can be in the later practice inspection rules and parameters were optimized by continuing to set, more perfect results. Key Words: Subway lines; Intelligent query; Design and implementation 北京理工大学硕士学位论文 III 目录目录 第 1 章 绪论1 1.1 课题研究的目的和意义 1.2 现有地铁查询现状及国内外换乘算法研究分析 1.2.1 美国 APTS 研究 1.2.2 日本 APTS 研究 1.2.3 欧洲 APTS 研究 第 2 章 地铁线路智能查询系统分析 2.1 地铁信息查询系统结构分析 2.2 乘客出行心理分析 2.3 地铁信息查询系统工作流程分析 2.4 地铁系统分析 2.4.1 地铁站点分析 2.4.2 地铁线路分析 2.4.3 地铁网络的抽象 2.5 换乘方案的分析 2.6 本章小结 第 3 章 蚁群算法 3.1 蚁群算法的发展历程 3.2 蚁群算法的基本原理 3.3 蚁群算法模型及其参数选择 3.3.1 蚁群算法的模型 3.3.2 蚁群算法的参数选择 3.3.3 蚁群算法的改进 3.4 蚁群优化算法模型 3.5 本章小结 第 4 章 系统的设计 4.1 系统的设计目标 4.2 地铁线路智能优化数学模型 4.3 系统的平台与结构设计 4.3.1 系统的平台 4.3.2 系统概要结构设计 4.3.3 系统数据库的设计与实现 4.3.4 系统查询详细实现 4.4 结合蚁群算法计算地铁网络最短路径 北京理工大学硕士学位论文 IV 4.5 查询决策过程 4.6 本章小结 第 5 章 系统实现和测试 5.1 用户界面设计的原则 5.2 地铁线路智能蚁群算法实现 5.3 数据库查询过程 5.4 地铁线路智能算法查询结果分析 5.5 系统测试 5.6 本章小结 第 6 章 总结与展望 参考文献 致 谢 北京理工大学硕士学位论文 V 第第 1 1 章章 绪论绪论 1.11.1 课题研究的目的和意义课题研究的目的和意义 城市发展日新月异，城市规模与面积不断的扩大，公交线路也日渐增多， 给人们出行带来了极大的便利，但是公交线路的增加，也给人们选择最佳的出 行线路造成一定的困难，因此，开发智能化的城市公交线路信息查询系统非常 的必要，它不仅可以给市民游客的乘车提供向导，节省大量的时间，减少拥堵， 同时可以体现出一个城市公交信息数字化和信息化的发展水平。 1.2 现有地铁查询现状及国内外换乘算法研究分析 随我国城市地铁乘客信息系统的发展处于一个落后的水平,广大乘客可以获 得信息的方式很少,地铁信息的完整性和准确性得不到保证,而且还没有专门的 机构负责信息的发布和管理。除去在北京等少数大城市,乘客可以通过某些站点 的电子站牌获得一些地铁车辆的信息以外,其它中小城市“出行中”的乘客不能 得到任何实时信息。总而言之,我国乘客在出行中无论是“静态线路信息”还是 “动态实时信息”都很难获得。我国城市交通虽然以“地铁优先”为发展的指 导思想，出台并实施了一系列的交通发展战略和政策，但是我国城市的公共交 通系统还是存在着诸多的问题与失误。以北京市和上海市为代表，作为全国率 先推进地铁优先发展策略的城市， “地铁低吸引率”的现象，让地铁优先这一策 略的实现面临着考验。 城市的公共交通为何难以让出行的居民满意？“地铁优先”这一符合我国 城市交通发展规律、符合国情政策，为何难以实现？究其原因，当前城市公共 交通现状的表现是难以让出行者放心选择。目前，国内外都极其重视智能公共 交通系统(APTS)的发展，APTS 已经进入了综合管理的时代，这个时代的特点是 十分强调 APTS 的信息采集、处理、集成和输出的服务。传统地铁系统中出现 北京理工大学硕士学位论文 VI 的道路和车辆状况不明、靠经验调度、缺乏乘客信息服务等问题在近年开发的 新一代智能公共交通系统(APTS)中已经得到了很大的改善。 1.2.11.2.1 美国美国 APTSAPTS 研究研究 美国城市公共交通管理局(UMTA, Urban Mass Transportation Administration)率先开展了智能公共交通系统(APTS)的研究。经过现场的试验， UMTA 关于 APTS 的评价是：“APTS 可以显著提高公共交通的服务水平，吸引 更多的出行者采用公交和合乘的出行模式，从而带来了减少交通拥挤，空气污 染和能源消耗等一系列的社会效益” 。根据 1998 年美国运输部的联邦公共交通 管理局(FTA)出版的“APTS 发展现状” ，美国的 APTS 主要研究基于动态公共交 通信息的实施调度理论和实时信息 5 现一个网上地铁线路查询系统，并结合所 学知识撰写毕业论文。该系统可以提供多条地铁线路和多个地铁站点之间的路 线查询服务，而且可以根据需要提供最短路线、最少换乘路线等线路规划。整 个课题可分为五个阶段： 第一阶段，查阅各方面的资料，对系统的需求进行分析，明确系统的功能 需求并形成需求分析。同时明确换乘算法，对蚁群算法进行改进，并进行实验 分析，使之适合本系统的需要。 第二阶段，提出系统的设计方案，对系统进行概要设计。查阅资料，对比 分析当前的各种技术，并结合自己的能力和系统的需求找到合适的开发技术。 然后，再在这个基础上构建系统的开发环境，并对构建好的开发环境进行测试 和调整配置，使之能高效、正常地运行，为以后的顺利开发奠定基础。 第三阶段，本阶段一个重要的任务是设计和分析查询的算法，分析系统在 各个层次上的数据流程，完成系统的查询系统功能的设计和后台管理的设计， 并对这个设计进行评审。根据设计好的系统结构和数据流，设计系统的数据。 分析各阶段的结果，设计数据库模型实现数据库，在数据库中录入少量测试用 数据。 第四阶段，主要完成整个系统代码的编写，并完善其中最重要的最佳路径 选择算法，并对其进行优化处理，提高系统的执行效率。然后根据这个阶段对 系统的测试情况适当的增加或者减少系统的功能，增加系统的易用性。建立一 个网络环境下的智能地铁查询系统，确定本系统建设总目标如下： 建立动态页面，使用户能通过网络查询 建立智能地铁系统，使之能够查询出两点之间地铁线路的最优方案，包括路 北京理工大学硕士学位论文 VII 程的长短、具体时间段内道路的畅通情况、所需花费等。 借鉴国内外的先进做法，研究动态问题，即在某具体时间段内所花费时间最 短的换乘方案 第五阶段，这个阶段是系统设计的最后一个阶段，本阶段的主要任务是美 化系统的界面，增加系统界面的友好性和易用性，并对系统的功能进行全面的 测试，修改设计中的错误。总结整个系统的设计和实现的整个过程，并撰写毕 业论文，准备论文答辩。2 发布理论，以及使用先进的电子、通讯技术提高地 铁效率和服务水平的实施技术。具体包括地铁管理、出行者信息、电子收费和 交通需求管理等几方面的研究。其中地铁管理主要研究通信系统、地理信息系 统、自动车辆定位系统、自动乘客计数、地铁运营软件和交通信号优先。 1.2.21.2.2 日本日本 APTSAPTS 研究研究 日本城市公共交通智能化的发展经历的了三个阶段：上世纪七十年代末开 始应用公共汽车定位系统公共汽车接近现实系统；上世纪八十年代末开始 应用公共交通运行管理系统，其中包括乘客自动统计，运行监控；进入上世纪 九十年代，由于机动车数量的增长和严重交通拥挤的影响，要保持正常的行车 速度是十分困难的，由此引起的公共交通的不便性和不可靠性导致乘客数量的 急剧减少。因此，东京都交通局开发了城市公共交通综合运输控制系统(CTCS) ，旨在改进公共汽车的服务，重新赢得乘客。在 CTCS 中，公共交通运营管理 是一个基本的框架，其目的是通过掌握运行的状况以及积累乘客数据而实现平 稳的公共交通运营服务。他将运营中的公共汽车和控制室之间建立信息交换， 并利用诱导和双向通讯的方法，将服务信息提供给公共汽车运营人员和驾驶人 员，同时这些信息也通过进站汽车指示系统和地铁与铁路接驳信息系统提供给 乘客。公共交通综合管理系统包括累计运行数据、乘客数据、监控公共汽车运 营和乘客服务等功能，其中乘客服务功能中包括进站汽车指示、信息查询和公 共交通与铁路接驳信息提示。 1.2.31.2.3 欧洲欧洲 APTSAPTS 研究研究 欧洲许多的国家同我国一样具有悠久的历史，老城市的街道一般都比较狭 窄。但是，他们通过实施地铁优先策略，设立地铁专用道，为地铁车提供优先 通行信号，布设智能地铁监控与调度系统等措施，提高地铁车辆的运行速度和 地铁服务质量以吸引公众乘坐地铁为出行模式，从而有效的缓解了城市交通压 北京理工大学硕士学位论文 VIII 力，解决了城市交通问题，并取得了明显的社会经济效益，这些经验尤为值得 我国借鉴。地铁车、地铁等公共运输工具已经成为人们重要的出行手段，城市 地铁体系是城市交通的主导力量，是城市交通结构中的重要组成部分，发展公 共交通对维持城市经济的正常运转、社会发展、方便城市居民生活有重要的全 局和先导性作用。随着城市化进程的加快，地铁半径进一步扩大，不同的路段 地铁工具的收费、发车间隔、拥挤程度等各不相同。这些因素给人们出行路径 的选择造成了一定的影响。这种情况在大城市尤为突出1，不合理的出行方案 白白浪费乘客的时间，后果是人们对地铁系统怨声载道。 第第 2 2 章章 地铁线路智能查询系统分析地铁线路智能查询系统分析 目前国际上比较流行和领先的是由 Google 提供的 Google Map 线路查询。 Google 对其 Google Maps route-finding project 并未披露过多算法细节。但 大部分人都猜测其使用的是改良过的以 A*搜索算法为基础的 Contraction hierarchies 算法，这是一种在图形平面上，有多个节点的路径，求出最低通 过成本的算法。A*搜索算法像 Dijkstra 算法一样，可以找到一条最短路径；也 像 BFS 一样，进行启发式的搜索。在此算法中，g(n)表示从起点到任意顶点 n 的实际距离，h(n)表示任意顶点 n 到目标顶点的估算距离。 因此，A*算法的公 式为：f(n)=g(n)+h(n)。 这个公式遵循以下特性：如果 h(n)为 0，只需求出 g(n)，即求出起点到任意顶点 n 的最短路径，则转化为单源最短路径问题，即 Dijkstra 算法。如果 h(n)=“n 到目标的实际距离” ，则一定可以求出最优解。 而且 h(n)越小，需要计算的节点越多，算法效率越低。可以看出，这种算法也 和 Dijkstra 算法有类似的运算量大的问题，但 Google 结合自身的 MapReduce 分布计算系统，可以利用庞大的计算服务集群迅速完成运算，从而保证在海量 地图数据的基础上提供便捷的线路查询功能。而根据选取的成本不同：以时间 为成本、以距离为成本、以换乘次数为成本、以车资为成本等等，该算法可以 提供多功能查询的能力 另一方面，Google 依托其强大的信息收集和检索能力，可以近实时的修改 地图数据中的道路通畅与拥堵数据，这样结合启发式搜索的参数，可以优化线 路查询的结果。这种动态查询结果大大优于传统的静态线路查询系统。 地铁信息查询系统属于智能交通系统(Intelligent Transportation 北京理工大学硕士学位论文 IX ystem，简称 ITS 系统)的子系统-先进的出行者信息系统(Advanced Traveler Information Systems，简称 ATIS)的范畴，发展此系统的一个最重要的目的是 通过为出行者提供准确、及时的地铁乘坐信息查询服务，从而方便出行者的出 行。地铁信息查询系统可以帮助用户进行地铁线路、站点信息、地理位置信息 的查询，同时，用户可以通过输入出发点和目的地，查询到地铁乘坐方案，从 而为用户的出行提供了帮助。 2.12.1 地铁信息查询系统结构分析地铁信息查询系统结构分析 2.1.12.1.1 时刻表查询时刻表查询 2.1.1.12.1.1.1 首末班车时刻表查询首末班车时刻表查询 图 1 如图 1 所示，地铁运营时刻表每日都在变化，并且新时刻表会提前一周左 右的时间确定，用户可通过登录该系统，选择“首末班车时刻表查询”选项来 查询一周内最新的首班车时间和末班车时间。 2.1.1.22.1.1.2 当日整条线路时刻表查询当日整条线路时刻表查询 在该模块，用户可以查询当日任何一个时段的时刻表。例如：从鼓楼乘坐 地铁到新街口，预算在 9 点 06 分之前到，用户只需要在起始站与终点站选项框 内分别选择一号线鼓楼站以及一号线新街口站，其次在周一至周日之间选择具 体时间，并点击查询，随后便可查询出所选当日一号线鼓楼站至一号线新街口 站的时刻表。此时时刻表显示 9 点 01 分 10 秒钟鼓楼站有一班地铁，到达新街 口站是 9 点 05 分 44 秒，用户则可以选择乘坐 9 点 01 分 10 秒钟的这班车，并 北京理工大学硕士学位论文 X 且在 9 点 01 分之前进入鼓楼站站台等候。 2.1.22.1.2 换乘查询换乘查询 2.1.2.12.1.2.1 地铁线路换乘查询地铁线路换乘查询 地铁目前三条线路，分别为一号线、南延线及二号线，换乘车站分别为安 德门车站、新街口车站及元通车站。用户可通过输入起始站与终点站查询换乘 方式。 2.1.2.22.1.2.2 公交换乘查询公交换乘查询 图 2 如图 2 所示，用户可通过选择线路及站点来查询站点周边的公交换乘线路。 以地铁一号线元通站为例，查询结果如图 3 所示： 图 3 2.1.32.1.3 票价查询票价查询 北京理工大学硕士学位论文 XI 图 4 如图 4 所示，用户可在此功能模块输入起始站及终点站，查询此路程的地 铁票价。以地铁一号线奥体中心站至二号线孝陵卫站为例，查询结果如图 5 所 示： 图 5 2.1.42.1.4 地铁线路查询地铁线路查询 2.1.4.12.1.4.1 地铁已有线路便民查询（充值业务点及无障碍助残通道）地铁已有线路便民查询（充值业务点及无障碍助残通道） 北京理工大学硕士学位论文 XII 图 6 如图 6 所示，由于地铁车站部分站点设有金陵通充值业务点与综合业务办 理点，在此功能模块内，用户可以查询已有线路包含哪些站点及站点周边情况， 并且可以查询哪些车站提供金陵通 IC 卡充值业务，哪些站点设有金陵通综合业 务点。通过此在线查询的方法，免去了用户去现场咨询的麻烦。 另外地铁开通的爱心助残无障碍通道服务，是帮助残疾人士及需要帮助的 乘客乘坐残疾电梯（直达电梯）使用的，每个车站的电梯设置位置不同，通过 残疾电梯乘坐地铁的购票方式与普通乘客的购票方式不同。用户可通过在线查 询系统查询要乘坐站点的残疾电梯位置及服务电话。或者通过注册用户名及手 机号码的方式在乘坐地铁之前点击相关选项，对应的地铁车站则可接收到此信 息，在乘客预定的乘坐时间提供一对一的服务。例如：鼓楼站残疾电梯通道为 4 号 A 出入口旁的广场中央。用户注册后通过点击鼓楼站，选择我要今日乘坐 残疾电梯即可。鼓楼地铁站的工作人员会收到该信息并与此乘客联系，提供服 务。 2.1.4.22.1.4.2 已有线路实施拥堵情况查询已有线路实施拥堵情况查询 另外包括线路拥堵情况查询模块，在此模块下，用户选择站点后，系统根 北京理工大学硕士学位论文 XIII 据实时客流和未来时间段的客流历史数据，结合客户端返回的查询数,计算出未 来特定时间段客流最少的路径与时间。服务器后台运行的数据分析 JOB 会每隔 特定时间段全局查询一次是否有线路节点的信息素超过预定上限,如果超过则表 示该线路发生了拥堵,此时系统会自动将线路标记为拥堵状态,此后如果有用户 查询的线路包含该拥堵线路,客户端会通过 JS 在 Map 平台上用红色做出标记。 2.1.4.32.1.4.3 地铁在建线路与规划线路介绍地铁在建线路与规划线路介绍 图 7 图 8 如图 7 与图 8 所示，南京地铁目前 57 个站点，在 2014 年将新增 4 条，未 来规划 17 条线路。在此功能模块用户可以浏览到地铁目前的规划方案及即将开 北京理工大学硕士学位论文 XIV 通线路的周彪情况等。可以掌握最新的地铁规划信息。 将系统的功能用模块化的方式划分为 7 个模块：客户端模块、服务器端模 块、地铁线路查询模块、地铁站点查询模块、地铁线路智能查询模块、地理位 置查询模块、数据库端模块。 1. 客户端模块 客户端是地铁信息查询系统与用户之间的接口，负责接收用户的查询请求， 对用户请求的关键字（如站点名称等）进行初步的匹配，然后将请求发送给服 务器地铁线路查询地铁线路智能查询模块地铁站点查询模块（户端模块客用户 浏览器）服务器端模块提出查询请求，最后接受服务器返回的查询结果，并将 结果显示在用户浏览器上。 2. 服务器端模块 服务器端模块负责接收客户端模块提交的用户查询请求，并对请求的关键 字进行进一步的匹配，例如将用户输入的地点名匹配为确切的站点名称以方便 地铁换乘方案的查询以及分析用户的查询请求，将用户的请求分配到相应的任 务模块来执行，同时协调各任务模块的通信和协作以及各任务模块与数据库端 模块的连接与交互。 3. 地铁线路查询模块 地铁线路查询模块负责用户对某一条地铁线路信息的查询。这个模块通过 接受用户提交到服务器端的查询请求中提出的线路名称关键字(如 100 路)，与 相应的数据库端模块进行交互，从而查询地铁线路数据以及相应空间信息数据， 随后将查询结果发送回服务器端，最后经过服务器端返回到客户端模块，客户 端模块在用户浏览器界面上显示该地铁线路途径各站点的详细信息，然后根据 返回的空间信息数据，将该线路显示在相关的电子地图上。 4. 地铁站点查询模块 地铁站点查询模块负责用户对经过某一地铁站点信息的查询。用户通过输 入出发地点信息(如新模范马路)或者地铁站点名称（如鼓楼站）后，首先客户 端模块对用户输入的关键字进行初步的匹配，随后将请求发送到服务器端，服 务器端继续对关键字进行匹配，得到确切的地铁站点名称，然后发送给地铁站 点查询模块，然后该模块通过调用数据库端模块查询地铁站点数据，返回通过 该站点的所有公交线路列表，最后客户端模块将所有线路信息显示用户浏览器 上。 北京理工大学硕士学位论文 XV 5. 地铁线路智能查询模块 地铁线路智能查询模块通过让用户进行选择起始地点或站点和目的地点或 站点，同样的通过客户端模块与服务器端模块先后对用户输入的起始地点（或 起始站点）进行匹配，得出确切的站点名称后，首先地铁线路智能查询模块通 过调用数据库端模块访问地铁线路智能缓存数据库，如果命中则直接返回给服 务器端模块，否则地铁换乘查询模块通过调用地铁站点查询模块查询到经过起 始站点的所有地铁线路信息，随后根据地铁线路智能算法得出地铁乘坐方案返 回客户端模块，同时将得出的换乘方案写入地铁线路智能缓存数据库，随后客 户端模块在用户浏览器上依次显示出直达的方案，以及一次换乘方案，二次换 乘方案等，同时显示出每条换乘方案的详细信息（比如经过站点信息，估计乘 坐时间等） 。 6. 地理位置查询模块 地理位置查询模块通过用户输入需要查询的地点名称，然后通过客户端模 块和服务器端模块的地名匹配，得出附近的地铁站点名称，然后调用数据库端 模块访问空间数据库，将用户查询的地点以及附近的地铁站点信息通过客户端 模块显示在用户浏览器中。 7. 数据库端模块 负责与所有数据库，其中包括空间数据库、属性数据库、Web 数据库、以 及地铁线路智能缓存数据库的交互操作。 2.22.2 乘客出行心理分析乘客出行心理分析 在研究地铁线路智能查询模型和相关的算法时，换乘问题是首先必须要考 虑的问题。对于一般人来说，超过两次换乘的出行路径一般乘客都不会采纳； 另外由于换乘不同的车次或者是换乘不同类型的车辆的过程会耗费大量的时间； 再有大部分公共交通工具是按次数计费，所以过多的换乘会使得出行费用增加 17。乘客选择出行路线时往往考虑以下因素: “出行耗时” 、 “出行费用” 、 “出行距离” 、 “换乘次数” 。出行耗时是指乘客在一次出行过程中所需要的时 间，包括地铁车行驶时间、乘客换乘步行时间和在车站等车时间。出行费用指 的是乘客在完成一次出行过程中所花的车费。出行距离包括地铁车行驶距离和 乘客为换乘而步行的距离。换乘次数指乘客在完成一次出行过程中所需换车的 次数。本文依据文献18中的一个地铁乘客出行心理调查统计结果，这个调查 北京理工大学硕士学位论文 XVI 主要包括对以下三个因素的调查： 出行耗时、换乘次数、出行距离。从图 2-2 中可以看到有接近半数的乘客在选择出行路径时首先考虑的是换乘次数最少， 其次是考虑时间最短。地理位置查询 Agent 接到查询任务，根据用户输入的地 点关键字以及附近地铁站点信息，通过协调 Agent 调用数据库访问 Agent 查 询空间数据库，最后界面 Agent 根据查询结果将该地点以及附近的地铁站点显 示在电子地图中。查询结束，界面 Agent 等待用户下一次查询操作。 图 2-3 地铁信息查询系统运行流程图 2.32.3 地铁信息查询系统工作流程分析地铁信息查询系统工作流程分析 (3)部分路段是单行线的线路。本文中将此类线路抽象成部分路段是双向的， 部分路段是单向的，如图 所示。 2.42.4 地铁系统分析地铁系统分析 城市地铁系统包含两个最基本的元素：地铁路线和地铁站点，本论文中的 所有交通工具都包含这两个元素，并且具有相同的基本特征: 每条线路由一系 列按一定次序经过的站点组成，任意一条线路上的任意站点用名字唯一标识； 每个站点程序启动初始化程序界面 Agent 协调 Agent 根据关键字判断查站点 查询 ent 通过站点的路线线路查询 Agent 地铁线路智能查询 Agent 地理位置查 询 gent 空间数据库 Web 数据库属性数据库是否已缓存没有缓存时查询数据写 入缓在地图上显示地点获得乘坐方案对方案进行择优排序是否包含空间路径信 息包含路信息的情况下在地图上显示路径界面 Agent 显示线路信息查询结束站 点和地理 位置名称数据库访问 Agent 界面 Agent 接收用户关键字界面 Agent 加载地图 数据，初始化搜索框和搜索列表户端模块客数据库端块务器端服块模 11 都有若 干条地铁线路经过，并用名字唯一标识站点内的这些线路。路径搜索的结果应 该是站点和路径的集合，是建立在线路和站点的关系上的，表示如何乘车和怎 样经过各个站点。从这个抽象层次上看，可以将不同种类的交通工具(如地铁车、 地铁)统一起来，将地铁网络用线路和站点的集合来表示。下面详细分析这种网 络 的特点和表示方法。 北京理工大学硕士学位论文 XVII 2.4.12.4.1 地铁站点分析地铁站点分析 (1)在不同地点的同名站点19在交通比较繁忙的地段或在具有交通枢纽位置的 地段，会有很多地铁线路经过，一般会在相隔不远的几个地方建几个车站分别 停靠不同的线路来分流线路密集的压力，避免同一个站点停靠太多的地铁车而 阻塞交通，如图 2-4 所示，这些站点之间距离不远并有相同的名字，本文中认 为在它们之间步行是可以接受的，这点在路径搜索时尤其重要。(在交通拥挤的 路口有可能站点 a，b，c，d 名字相同) 图 2-4 同名但不同位置的站点 (2)紧邻的不同名站点 两个站点同一道路上紧邻，但有不同的名字，如两个站点可以通过步行 1-2 分钟就可到达，或相邻站点的位置相隔 100 米左右，如图 2-5 所示。 图 2-5 不同名但位置紧邻的站点 (3)地铁站点的其他属性 常常人们在进行地铁查询时只是关心起始或目的站点周围的标志建筑物，如 具体的单位名称，相关景点等而并不知道具体的站点名。 2.4.22.4.2 地铁线路分析地铁线路分析 经过对 2.1 中大模块进行分析，得出基于 MAS 的地铁信息查询系统各模块中 Agent 工作流程如下（如图 2-3 所示）： 1. 用户打开浏览器启动地铁信息查询界面，客户端模块初始化界面 Agent，加 载电子地图数据，加载搜索框和搜索列表。 2. 用户在浏览器界面输入关键字，界面 Agent 接受用户的关键字，同时对用 户的输入给予提示。 3. 界面 Agent 将用户的查询请求发送到服务器端模块的接口 Agent，接口 Agent 通过管理 Agent 创建协调 Agent。 4. 协调 Agent 根据用户查询关键字信息进行判断，将查询任务分配给相应的 任务 Agent（站点查询 Agent，线路查询 Agent，地铁线路智能 Agent，地理 位置查询 Agent） 。 5. 站点查询 Agent 接到查询任务后，获取用户提交的站点名称，通过访问 Web 服务器查询地铁站点数据库得出经过该站点所有的线路名称信息，然后通过协 调 北京理工大学硕士学位论文 XVIII Agent 将查询结果发送给线路查询 Agent，线路查询 Agent 通过访问 Web 服 务器查询地铁线路数据库，得到地铁线路查询结果，然后根据查询结果判断是 否要通过数据库访问 Agent 查询空间数据库，然后将查询结果发送给协调 Agent，然后协调 Agent 将查询结果返回给界面 Agent，界面 Agent 判断查询 结果中是否有空间路径信息，如果有则将各条线路显示在电子地图上，同时在 用户浏览器界面显示出各条线路的详细信息（包括途中经过站点名称等） 。 6. 地铁线路智能查询 Agent 接到查询任务，首先根据获得的始末站点名称信 息通过 Web 服务器查询地铁线路智能缓存数据库，如果缓存数据库已经存有换 乘方案，则地铁线路智能查询 Agent 通过数据库访问 Agent 读取换乘方案相 关的空间信息数据，随后返回给界面 Agent，最后界面 Agent 直接将乘车路线 显示在电子地图上，同时将乘车方案显示在用户浏览器界面中，如果没有命中， 则需要通过协调 Agent 调用站点查询 Agent 查询到通过始末站点所有线路详 细信息，然后将查询结果根据最地铁线路智能算法得出相应最优乘车方案（包 含直达方案和换乘方案） ，随后将得出的换乘方案写入换乘缓存数据库，同时发 送回界面 Agent，随后界面 Agent 将所得乘车路线显示在电子地图上，同时将 乘车方案显示在用户浏览器界面中。 7. 线路查询 Agent 接到查询任务，根据用户输入的地点关键字，通过协调 Agent 调用数据库访问 Agent 查询空间数据库，同时通过 Web 服务器访问 Web 数据库，随后将查询到的线路信息数据和空间信息数据返回给界面 Agent，最后界面 Agent 根据查询结果将该条线路详细信息显示在电子地图中。 2.4.32.4.3 地铁网络的抽象地铁网络的抽象 在建地铁网络模型时，必须考虑地铁站点的表达和对整个网络的影响，因 为它们在地铁系统中是非常重要的点状元素，是网络图中顶点。具体处理时， 由于不同地铁线路上的站点和同一条地铁线路上两个方向的站点分布情况较为 复杂，所以有必要对地铁站点进行一定的分析，抽象成网络中的节点，这样有 利于网络的拓扑表达。下面将对一些情况分别进行说明。 (1)同一地铁线路两个方向上的同名站点的抽象在同一条地铁线路上，两个方向 上的同名站点的空间位置是不重合的，如图 2-9(a)，在网络模型中将同一条线 路两个方向上的同名站点抽象成一个节点。 (a)实际地铁线站点示意图 (b)抽象成一个节点 北京理工大学硕士学位论文 XIX 图 2-9 地铁线路上两个方向的同名站点的抽象 (2)不同地铁线路的紧邻站点的抽象不同地铁线路的站点分布情况较为复杂， 以两条不同地铁线路为例来说明。 点位置完全重合，即站点名字不同但地理位置重合(图 2-10(a)； 两个站点不重合，但在同一道路上紧邻，比如两个站点的位置相隔 30 米左右(图 2-10(b)； 在两条道路交叉口的各自道路上紧邻。 (a)站点重合 (b)同一道路上站点紧邻 (c)不同道路上站点紧邻 图 2-10 不同线路的紧邻站点的分布情况 12 根据对南京地铁状况的分析，地铁线路是比较复杂的，一般可以分为三类: (1)完全双向线路（对开线路） 。这种是最常见的线路，如图 2-6 所示，地铁 车在两个终点站之间双向行车，而且两个方向上的行车路线是相同的，经过同 样 的站点序列和街道序列，但是线路上相同名称的站点都是位于道路的两边，因 此 同一个名称对应道路两边的不同站点。这种线路一般来说在两个方向上的交通 状 况是不同，因为他们分别在左行线和右行线上行驶。 (2)单向环形线路。这种线路的行车路线是单向的环形的，如图 2-7 所示，线 路上的任意一个站点名称都唯一对应地理位置上的站点，这种线路的表示比较 简 单。 (3)部分路段是单行线的线路。如图 2-8 所示，在个别比较窄或者比较拥挤的 路段会实行单行道，但有些在两个端点站之间双向行车的线路，在其他的路段 跟(1)中介绍的双向线路的特点是一样的，因此在这样的线路的总体特点跟完全 的双向线路类似，但两个方向的站点序列和街道序列会有部分不同。地铁线路 智能查询问题都可以归结为是最短路径问题，最短路径问题是指在一个带权图 的 2 个顶点之间找出一条具有最小权的路径，是图论研究中的一个重要问题。 目前，对最短路径求解的方法有很多，主要可以分为 2 类： 基于遗传算法的智能搜索算法。这些算法都是从节约存储空间，提高运 算速度的角度出发，进行算法的优化与实现； 北京理工大学硕士学位论文 XX Dijkstra 算法及基于该算法的优化算法。在实际应用中，不仅仅需要一个 好的算法来解决计算，还需要考虑其他一些客观因素，如：网络的拓扑关系和 地铁线路地理网络的复杂性以及乘客的心理需求等。 本章对于求解最短路径的的蚁群算法的原理以及应用进行了介绍，最后介 绍了蚁群算法在求解最短路径上的应用。 2.52.5 换乘方案的分析换乘方案的分析 公共汽车的最优换乘，很多学者都作了一些研究。从前文的地铁乘客出行 心 理调查统计表可以看出，换乘次数最少是地铁乘客出行时考虑的第一因素，所 以 换乘次数最少是本系统应考虑的首要因素。虽然出行耗时最少乘客考虑的第二 因 素，但因能影响耗时的因素太多并且难以预测，所以准确测算出行时间是不可 行 的20。因而相对固定的出行行距离最短考虑的次要因素。在本文将出行距离 最短用经过站点最少来代替。考虑一般人的出行习惯，在选择两个站点间的行 车线路时，可以分为以下几种情况: 1)直达的情况 首先会先看两个站点之间是否有直达车，如果有，马上会选择此路线，如图 2-16(a)，如果存在多条直达线路，再考虑地铁车行驶的远近，选择距离最近的 乘车方案。 2)换乘一次车的情况 如果没有直达车，就会考虑换一次车的方案:即经过 A 站与经过 B 站的车是否 有公共站点 C，如果有，则可以在公共站点 C 处转车，如图 2-16(b)如果有多 种可 14 站点重合的情况最简单，多个重合站点视为同一点，抽象成一个顶点。 对具有紧邻关系的站点的抽象是非常关键的，它的目的是模拟人们在不同线路 之间换车的真实情况，以提高路径查询的正确性。因为在实际的换车情况中， 一定范围内的步行是乘客允许的也是必须的。将紧邻的站点抽象成一个节点， (3)地铁站点其他属性的抽象。很多情况下，人们在地铁查询时只知道站点周 围的标志性建筑或大概位置，因而在抽象地铁网络时要考虑站台周围的标志性 北京理工大学硕士学位论文 XXI 建 筑、景点及一些有名的单位。具体来说，就是把这些相关因素与其周围最近的 站 台名联系在一起，抽象成一个节点。如图所示：可以以站台为圆点，可以接受 的 步行距离为半径所画的圆形区，抽象为一个节点，如图 2-12 所示。 图 2-12 周围相关建筑抽象成一个节点 地铁线路在抽象的地铁网络中可以抽象成连接各节点的有向边。根据实际分 为以下 3 类: (1)完全的双向线路。地铁车两个方向上的行车路线是相同的，经过的站点和 街道顺序也相同，所以可以抽象成由一条双向边连接的各站点，如图 2-13 所 示。 图 2-13 双向线路的抽象 (2)单向环形线路。可以抽象成一个单向的环形，因为这种线路的行车路线是 单向的环形的，如图 2-14 所示。13 综上所述，在设计时，地铁线路不能简单的用一个字段表示。同时，在存储 时应以上行或下行以示地铁线路来回所经过的站点，以使各地铁线路所经过的 站 点信息更加准确。 2.62.6 本章小结本章小结 本章首先对地铁查询系统进行了分析，结合乘客出行心理，设计了地铁查 询系统的工作流程，在此基础上提出了本文所用的换乘方案。初始化置禁忌表 S=1; 并将起点城市加入各自禁忌表中。 3 3、蚁群算法蚁群算法 3.13.1 蚁群算法的发展历程蚁群算法的发展历程 本文的整个服务器主要功能包括 5 个部分： A、用户系统：所有用户的注册、登录、资料等