数据结构课程设计报告

数据结构课程设计报告

姓名：郭秋雷 学号：200630351149

公交信息管理系统

前言：

做这个公交系统的想法也是由来已久的的。我自己本身是个路痴，出行又不喜欢看地图找公交。后来中国移动推出了一个12580出行公交行路质询服务，让我对它产生了浓厚的兴趣，自己也想做一个类似的软件系统。后来看到一道数学建模题中也是有类似问题，大意是北京奥运期间大量乘客来北京观光奥运，人生地不熟出行肯定会不大方便，所以公交线路查询是必不可少的。再加上到时候游客数量激增，依靠人工来管理公交调度肯定会出现不足，一个完善公交管理系统的是迫在眉睫的。

因为我对数学建模有兴趣，我自己也对这些问题思考了很久，查了些资料，发现现有的公交查询系统，就拿中国移动的12580查询来讲，我个人认为就是有很多缺点的，不适合投放到市场，甚至不适合在北京奥运期间采用。比如中国移动现有的公交查询，它往往只会告诉你一条方案，你甚至不知道它和别的其他方案有什么优缺点，因为有些乘客赶时间需要的是时间最快方案，有些乘客因为经济困难希望得到最省钱方案，有些乘客因为行动不方便或者喜欢舒适就希望得到换乘次数尽量少甚至直达的路线。而且因为有时候人流集中，比如奥运期间鸟巢或水立方里某场超热门的比赛，如果比赛结束后大家出来后都

选那么一两条路线，就会造成一两条线路拥挤，大家上不了车，这就需要查询系统能够提供多几条时间较快的，较省钱的线路让大家选择。这些人性化的需求在中国移动现有的12580公交查询里的得不到的。所以我希望能够建一个能满足各种乘客需求的更加完善的公交查询系统。

和公交查询匹配的是对于公交公司的公交车调度问题，奥运期间，如何更加好的安排公交调度，让大家出行方便，也是公交公司的当务之急，我的公交调度里，就可以根据每条公交路线采集到的数据来进行合理的调度，使得奥运期间大家的出行更加方便。

(一) 摘要：

设计解决公交线路选择问题的自主查询计算机系统系统，其核心是 线路选择的模型与算法，特别是满足不同乘客的查询需求。传统的 Dijkstra 算法无疑是解决一般最短路径问题的最优算法，但接下来 我们会看到传统的Dijkstra 算法在公交查询系统是不适合的。而我 依据对公交乘客出行心理调查的统计结果,指出换乘次数最少是乘客 出行时考虑的首要因素，所以这里提出一种基于换乘次数最少的公交 最短路径算法，并根据公交系统的特点，以图的邻接表作为数据结构。

至于公交车的调度，需要同时考虑到公车公司和乘客的利益，必须尽量在满足双方的利益上做出合理的调度。所以这是一个多目标最优的问题，一是公车公司的成本低，即提高每辆车的满载率，或者说发车的车次尽量少；二是等待时间过长的乘客所占的比例尽量少；三是超载的情况尽量不发生，让乘客尽量感到舒适。因为一天里有些时间段里乘客人流的情况的相近的，比如早上平峰期，高峰期，中午平峰期，傍晚高峰期和晚上平峰期，我可以分别对这5个时间段分别求解。这样我们就可以求解各个时段的满载率，等待超时乘客所占比例和超载的乘客所占比例这三个目标函数。因为分别求解三个目标函数有困难也没有必要，所以我按公交公司效益和乘客利益同样重要和公交公司本着为乘客服务的理念愿意合理的牺牲一些效益这两个思想，对每个因素取一个适当的权重因子，最后得出最优调度。

关键词：公交路线网络化，图的邻接表，公交查询，乘客的需求，换乘次数，广度搜索，公交调度，分时段调度，公交公司与乘客的利益关系

(二) 问题描述：

乘客的查询系统：我国人民翘首企盼移动的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公交出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，

使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求， 需设计这样一个系统，其核心是线路选择的模型与算法，从实际情况出发考虑，考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。满足查询者的各种不同需求。

公交的调度系统：公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。为了建立一个有效的公交调度，我需要采集需要调度的线路的相关数据。根据采集到的数据，我的公交调度系统就可以为这条线路设计一个全天的公交调度方案。这里我的测试数据来自北京某条公交线路的客流调查和运营资料。 并根据常规设客车在该线路上运行的平均速度为20公里/小时。运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过 120%，一般也不要低于50%。根据这些资料和要求，为线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等。

(三) 系统模型的分析与建立

下面分公交查询和公交调度两个问题分别建立数学模型求解。 公交查询：

本文来源：https://www.bwwdw.com/article/ma7d.html