公交路线查询系统.doc

《公交路线查询系统.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、公交线路查询系统设计摘要本文主要是研究城市公交的线路选择问题。针对此问题，我们根据查询者的不同需求，建立双目标函数的优化模型。在此基础上，我们采用了换乘矩阵算法分析各站点间可达问题。通过矩阵分析，我们可得到任意两点间中转m次的最佳路径。考虑到计算机的速度问题，我们只求到3次。考虑到用户的不同需求，我们设计的转化函数，从而将复杂的线路选择问题清晰化。并通过转化函数，可根据用户的不同需求，将路程花费按参数k转化为时间，从而统一了数量单位，将多目标函数求最佳值转化为求单目标函数的最佳值。然后通过我们所编写的程序，求出了任意两点

2、间的最优解。在公汽与地铁线路中，为了利用问题一所编写的程序，我们统一将所有地铁线路作为公汽线路的一部分，并修改相关部分内容这样。就将问题二转化为问题一。在地铁转化公汽时，将地铁的站点既看成公汽站，又看成公交线路号。使之能充分利用问题一的程序。并优化了第一个问题中的程序算法，使得在综合考虑地铁线的情况下，可求得任意两点间的最优解。针对问题三，综合了所有站点之间的步行时间，我们给出较为一般化的数学模型。使得此模型可以符合实际的要求，用户可以在多方面的需求下，得到满意的最优解。关键词：换乘矩阵，权值，转化函数一、问题的提出我国

3、人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。因此我们主要解决如下问题：1、仅考虑公汽线路，给出任意两公汽

4、站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用设计出的模型与算法，求出以下6对起始站→终到站之间的最佳路线：(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。二、模型假设1．所有公交路线不存在堵塞现象，也不存在超车现象。2．考虑到实际情况，我们断定所有最佳路

5、线最多换乘三次。3．乘客换乘车时，在规定的时间内定能等到车。4．用户在考虑路线选择问题时，总是比较时间与金钱的不同地位，用权值比较他们之间的主次。一、符号约定：相邻公汽站平均行驶时间(包括停站时间)，为3分钟：相邻地铁站平均行驶时间(包括停站时间)，为2.5分钟：公汽换乘公汽平均耗时，为5分钟(其中步行时间2分钟)：地铁换乘地铁平均耗时，为4分钟(其中步行时间2分钟)：地铁换乘公汽平均耗时，为7分钟(其中步行时间4分钟)：公汽换乘地铁平均耗时，为6分钟(其中步行时间4分钟)：i站点到j站点的步行时间：i站点到j站点的步行

6、次数（=0,1）：n阶方阵中的i行j列元素：公汽单一票价1元：公汽分段计价（0～20站：1元；21～40站2元；40站以上：3元；i=1,2,3）：地铁票价3元T：乘客总路程所花的时间S：乘客总路程所花的钱：乘客总路程经过的公交站数（不含起始站）：乘客公汽换乘公汽的次数：乘客总路程经过的地铁站数（不含起始站）：乘客地铁换乘地铁的次数：乘客公汽换乘地铁的次数：乘客地铁换乘公汽的次数：乘客乘坐的单一票价公交路线数：乘客乘坐的分段公交路线数（分三个级别，i=1,2,3）：目标函数的权值三、问题分析1．针对第一问仅考虑公汽线路，

7、我们假设乘客无论经过一个站或多个站，都坐公交（即使相邻两个站很近，也不走路）。为此我们把模型优化为下面双目标函数：MinS=*+MinT=*约束条件为数据文件提供的各公交路线信息。下面介绍我们的矩阵换乘算法：定义公交网络换乘矩阵的初始矩阵H0(h0(i,j))，若从站点i不需换乘即可到达站点j的线路数目为m,则h0(i,j)=m，否则h0(i,j)=0。所以h0(i,j)表示不需换乘，即可从i到j的公交线路数。例如：三阶方阵它表示不换乘从1－>2，2－>3有一条路径，2－>1有两条路径，而0（其中对角线上的“0”无意义）

8、表示不能直达。有线性代数的知识易知，表示从起始站中转m-1次到达目的站的路径数。设H1==，则从1中转1次到达3有一条路径，而3－>1，中转1次还是不可达。对角线上的非0数字表示中转1次的回路，如：1—>1表示这样两条路径：1—>2—〉1,而1直达到2的路经本身就有2条，因次相乘为1—>1的两条路径。因此，我们可以把