第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
2007年全国大学生数学建模竞赛B题论文及程序.doc
2007年全国大学生数学建模竞赛 B 题论文及程序(网络转载)
(2007-09-29 11:33:30)
转 载 ▼
标签：
知 识
/ 探
索
一.摘要:
公交查询系统的模拟
我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运
比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年
来，城市的公交系统有了很大发展，城市的公交系统的发展带给人们便利的同时也带来了路
线选择的问题，针对这一情况，本文从公交线路出发,将时间问题与费用问题转化为换乘次
数和站点数问题,着重考虑公交线路的换乘次数和站点数，讨论始末站点所在线路的重合、
相交等各种不同情况，运用统计的思想和集合的概念标识站点和线路,并通过寻找集合间的
交集的形式查找线路中转站，并将这些站点及其所在线路构成换乘矩阵，给出换乘的具体算
法，同时还运用等效的方法将地铁线路衍变为公交线路，从而简化模型。文章最后还考虑了
乘客可以步行小段距离再转车的实际情况，提出了基于最少换乘次数的城市公交网络的最佳
路径算法。由此系统乘客在一个查询系统里直接输入起始点与目标点之后，系统会自动生成
最优的出行路径。
关键词：公交网络 最佳路径 最少换乘次数
二、引言
到一个城市，如北京，上海，首先遇到的一个困难是去该城市的交通问题。作为首都城市的
北京，全国人民以及世界人民翘首企盼的第29届奥运会明年将在此举行。在这种情况下，外
国游客大量地涌入中国，其中大部分人将会乘坐公共交通工具(简称公交，包括公汽，地铁
等)，这样他们从居住地(酒店旅游等)，到奥运会场所及各个参观景点就面临一个问题：如
何选择乘车路线，才可以方便而且较快地到达目的地，即,公交网络换乘问题。
三、问题的提出与假设
在城市电子地图中，公共交通信息模块是必不可少的，它为各种交通信息的搜索查询，统计
提供方便直观的手段，公共交通信息的查询倍受用户的关注。在现有的公交线路与站点的情
况下，设计合理的交通网络查询模型有助于人们确定出发的时间，出行线路和换乘方案。即
当乘客在一个查询系统里直接输入起始点与目标点之后，系统会自动生成最优的出行路径。
文献[1]对乘客的出行心理进行了研究。其结果是“换乘次数”是大部分公交乘客在选择出
行时首先考虑的因素，其次是出行时间和距离的长短，而出行耗费的时间与换乘的次数及距
离的长短密切相关。对公交车换乘问题的研究，我们做出如下假设。
1、由题目给出的参数假设可知：任一条公交线路上，公交在相邻两点之间的行驶时间为一
常数。
2、出行者只考虑时间问题，也就是选择最少公交站点数作为起点至目的地的最优线路。在
一般情况下，出行者特别是旅游者，费用并不是他们所首先考虑的因素。因此为了简化模型，
把考虑站点数的便捷性放在第一位,也就是把时间作为第一要素。
3、若乘客可直接到达目的地，就不再换乘，这也符合乘客的一般心理，与实际相符。
4、换乘次数最多为两次，这是由于可换乘所用的次数越多，耗费的时间越长，费用也越多，
当一个交通系统的换乘次数多达三次时,就说明这个交通系统有待于改进。因此为了模型的
进一步的简化,就讨论最多只换乘两次这种情况。
四、数学模型
<一>公汽情形
1.公汽网络的描述
一个公交网络是由一组不同的公交线路组成的，且每条线路上分布有若干个上下乘客的站
点，把每条公交线看作一条公交流线，用表示(可以是闭合的，也可以是重复的，或是不闭
合也不重复的)，则由 i 条公汽流线组成了个公汽网络；且每条公汽流线是它所经过的所有
站点的集合，即可表示为：，对于所有公汽站点的集合，当时，表示第一条线路下所有的站
点编号所组成的集合，任一公汽站点所对应的经过此站点的公交线的集合记为 ( 表示公交
线路，表示站点)。这样可以通过统计的思想把经过网络中的两点(标为结果)所对应的公交
流线作为一个集合，记为，其次把每条公交流线所对应的站点用集合表示。
2、路径选择原则
(1)公交线路是单一的(即往返同线)
在系统中，输入起始点以及目标点。，为了实现个目标且能使花费的时间最短，则可按如下
步骤进行搜索；(若公汽在一站点有停车，则为1，否则为0，用表示)
①计算是否存在 ，使得流线 同时经过 与 两种结果。若为 =1，则说明只要乘车一次就可
以到达目的地，乘车路线可为
Si Sj
此时若有多条途径，则可选择站点数最少为最优路径。
②若①种情况不成立，则需要换车，搜索集合 与看是否存在，满足，如果存在则说明需要
换车一次则可到达目的地，乘车路线为：
若只有一种搜索结果显示，从 的乘车线路就是这种最佳。
若不是唯一的，而有多种选择换乘一次可达目的地，则此时可有 K 种途径可以到达目的地，
此时就进一步对此 K 种中转站进行扫描，输出站点数最少的一种方式，进而显示乘坐次种最
佳的途径到达目的地。
③如果②都不存在时，说明乘车至少要换两次，搜索集合：
是否存在两个中转站站点，以及满足若存在，则说明只需换车两次即可到达目的地。
④若换乘两次未能到达，则需要换乘至少三次才能实现，根据以上同样的方法，仍然可以搜
索出最佳的出行线路。
不过出于对人们的可承受的心理限度的考虑，再基于较优质的交通网络，换乘次数在此设定
时不应大于两次。
⑤对题中6对起始站到终点站的解答:
S3359到 S1828,从 S3359出发乘第436路车到 S1784下车转乘第167路车到终点 S1828
S1557到 S481,从 S1557出发乘第363路车到 S1919下车转乘第189路车到 S3186下车转乘460
路车到 S481
S971到 S485,从 S971出发乘第13路车到 S2184下车转乘第417路车到终点站 S485
S8到 S73,从 S8出发乘第463路车到 S2083下车转乘第57路车到终点 S73
S148到 S485,从 S148出发乘第308路车到 S36下车转乘第156路车到 S3351下车转乘417路车到
S485
S87到 S3676,从 S87出发乘第454路车到 S3496下车转乘第209路车到终点 S3676
<二>.公汽与地铁
上面论述了乘客出行只考虑公汽的最短路线问题。在现实生活中，北京公交除了公汽之外，
地铁也是整个交通网路中不可缺少的一部分。在这种情况下，乘客的选择就更多了。然而最
优路径永远是乘客出行首选的，但不排除特例。
对于已知的两条地铁线路,可以把它新增为公汽网络中的两条流线,设两地铁所经过的站点
的集合分别为：
由于就，有23个地铁站点与外面的公汽网络相连。则可做如下处理，即有经过地铁站的23
个地铁站与其相对应附近的公汽站作为一个新的公交网络中的结点，并且给这新的结点赋予
新的标记，则通过这新的公交站点的所有公汽流线所组成的集合用表示,如下图所示
此时在给定起始点的时候,人们有以下几种选择
(公汽)
(先公汽后地铁)
(先地铁后公汽)
(先公汽，然后地铁，再是公汽)
(先地铁，然后公汽，再是地铁)
1、当输入线路为： 时，系统先作出如下初步判断
或
则此时同时进行着 型与 T 型这两个途径。
在执行 型时，就只有执行公汽模型并得出最佳的线路。
在执行 T 型时，线路图如下所示
由于是地铁站点，同时又是新的公汽站点，即此是可认为乘换次数为2。
由于前面假设，公汽的换乘次数不超过两次，即可到达目的地。
若在，该模型的换乘次数就为4次，那么这公交网络系统就是其本身设计问题了，则可设公
汽与地铁交叉的换乘方式的换乘次数应小于等于4。
①若存在 Si∈ ， 则可选出，此为公汽换乘情况
②若 =1，2，3…}，而，则公汽间换乘一次，此时可转化为 ，由于此时可以把地铁站等
效为公汽站点，只是等同后的公汽站不再是原网络的一个单纯的结点，而是由多个单纯的结
点组成了新的组合结点，表示为。（由于公交站是在地铁站周围，该等效符合实际。则转换
为一个多对一的映射，即
这样可回到公汽模型来分别比较 中到达 的最少结点数
③若 =1，2，3…}，而 =1，2，3…}，则可为引入中间站点 Sz 来实现，的最少结点的公
汽流线，这又转化为公汽系统。只是系统事先确定的流线。
④若公汽有转乘两站，根据公汽只转乘一站时的算法，则只要输入起迄站，系统就只需与23
个新标识的结点进行计算，算出 Si 的最小结点以及 的最小结点，搜索结果即为最优途径。
2、①当输入 （j 23）时，即可等效公汽间的算法，此时可能会有好几个可行的路径 K 条，
这些可行的路径中再进行进一步地筛选，可根据第一目标为时间
筛选方法为：每条途径所对应的换乘次数 3，（满足公汽最大换乘次数不大于3），公汽结点
数为，地铁结点数有；则时间 t=min f（ ， ， ）=min（2 +3 +5 ）（其中 i=1，2，…，k）。
②对于输入 （j>23时）
即 （如下图）
对于输入 ，可进行分步
则取 的两个时间取最小值。
③当是 时也可由前面①②的方法所得。
2.当输入的是之间的转乘时，可根据在与两站点转乘的最少站点数，得出最佳转乘路线。
3.对于的模式时，索引自动会把它跳跃至的关系。出于一般人的心理，该模式较符合人的思
维模式。在经济上只要支付地铁的费用，而时，则增加了公汽的费用，也许在时间上并不是
最佳，但可以不予考虑。
<三>、模型的补充
以上两个模型对涉及到费用的问题，都只以时间作为第一要素来考虑，而费用只是隐含在站
点数中并作为第二要素，没有充分考虑。此时对此模型进行修补。考虑经济因素对人们转乘
的影响。不过在模型的假设里考虑时间是最主要的，则在时间为主要因素的前提下考虑费用
问题。
(1).此时可在系统增设一个来处理站点的费用问题，在系统已确定的可行路线为 K 条时，系
统对每条线路进行提取节点数 n,转乘数为 N 且，以及 N+1条换乘流线段上节电集合。
若 ，则输出费用
若 ，则输出费用
判断 ，若 中有个是在20~40之间，个是在大于四十，个是在小于20，则有
此即计算费用的一般通式。
为了满足不同人群的对目标实现的方式不同，取两条分别以钱与时间为最佳出行线路，即为
四条可选择路线，在此四条可红选择的路线上，除了分别标识所需发费的时间与费用的同时，
也标识转乘情况。
在间以及地铁与公汽间，由于有上地铁其费用就已固定。此时即可用（1）来实现满足人们
的要求。
<四>. 对已知的公交网络，给定的任两点间的距离，则可用附权图来表示，每两节点间的
权表示为步行所需要的时间！则可采用迭代法求出从的最少时间！根据前面所得出的公交路
线模型中的最优方案，此时所要实现的就是把所求的最短步行时间与公交系统有效的结合，
使得显示三种最优路径，分别是最少费用：有两种优解；最少时间：有两种优解，以及步行
的最优解！这样的系统则又增多了人们的选择，不再是只限制在公交系统上。比如在某些站
点，步行则很快到达，而乘坐公交即没有时间上的优惠，也浪费金钱，因此此种情况下，在
人们可接纳的步行长度（也就是步行时间），则给人们新的选择方向，此种情况下的模型，
又是公交系统的重大的补充，使其更具有人性化！
由于该模型只考虑了时间与费用两个问题，而现实生活中公交先线路的选择不仅仅是这两个
问题，它还与上下班时间段、是否为空调车、站点所在线路的车流量等方面的因素，以上所
列举的因素涉及概率方面内容，需要建立微分方程模型，再与前文所述内容综合考虑，模型
的可靠性就更高、适用性更好。由于公交线路选择需要考虑的因素较多，需要认真调查，认
真思考，同时还要多方面听取意见，进行多次讨论，按照多方面的要求统一协调，综合考虑，
要根据实际乘客的心理进行分析判断。
五.模型评价
在以上的公交模型能够在不换乘以及换乘一次、二次情况下能够较好的提供较复杂人群的需
求。在以上的公交系统模型中，由于数据量很大，所算出的最优线路采用的是最小换乘法，
在具体的算法上随着换乘次数的增多，使得系统对这些数据计算的复杂度与烦琐度大大的增
大，这不仅对搜索系统性能的要求大大的提高，同时这系统执行命令后的运行的时间也大大
的延长，这不符合出行者的要求！由于在程序发面的笔者较为陌生，只能在单独公汽情行下,
在考虑到公汽与地铁相结合时只给出了模型思想,未能在程序里得到验证!
六.模型应用
由于本模型同时涉及到时间的最优解以及费用的权衡,是同时综合了最少费用与最短路的两
个模型,因此此模型可使用于中国邮路问题,交通运输等!
参考文献:
[1]王莉等.公共交通系统最佳路径法[J].东南大学学报,2004,34(2):256-267
附录:单纯公汽模式的 MATLAB 实现
function y=findline(x)
%x is a busstation
%aim is to find all busline through x
load busstation
[l_a,t]=find(A==x);
y=l_a(find(t>3));
function y=findstation_come(b,x)
%b is a goal station
%x is the busline through b
%the aim is to find all station going to b
load busstation
last_b=max(find(A(x,:)==b));
y=A(x,4:last_b);
function y=findstation_to(a,x)
%a is a starting station
%x is the busline through a
%the aim is to find all station coming from a
load busstation
head_a=max(4,min(find(A(x,:)==a)));
%min column
last_a=max(find(A(x,:)~=0));
%max column
y=A(x,head_a:last_a);
function y=nochange(a,b)
l_a=findline(a);
l_b=findline(b);
y.line=intersect(l_a,l_b);
y.connecting=[];
function y=changeone(a,b)
x=[];
for i=1:length(l_a)
for j=1:length(l_b)
x_a=findstation_to(a,l_a(i));
x_b=findstation_come(b,l_b(j));
cap=intersect(x_a,x_b);
if ~isempty(cap)
t=cap;
select_line_a=l_a(i);
select_line_b=l_b(j);
select=[select_line_a,select_line_b,t];
x(i,j).line=[select_line_a,select_line_b];
x(i,j).connecting=t;
end
end
end
y=x;
function y=changetwo(a,b)
t=[];
l_a=findline(a);
%l_b=findline(b);
for i=1:length(l_a)
x_a=findstation_to(a,l_a(i));
for j=1:length(x_a)
select=changeone(x_a(j),b);
if ~isempty(select(1).line)
t=[t,select];
end
end
end
y=t;
function y=changethree(a,b)
t=[];
l_a=findline(a);
%l_b=findline(b);
for i=1:length(l_a)
x_a=findstation_to(a,l_a(i));
for j=1:length(x_a)
select=changetwo(x_a(j),b);
if ~isempty(select(1).line)
t=[t,select];
end
end
end
y=t;
function y=kexingjie(a,b)
x1=nochange(a,b);
if ~isempty(x1(1).line)
y=x1;
elseif 1
x2=changeone(a,b);
if ~isempty(x2(1).line)
y=x2;
end
elseif 1
x3=changetwo(a,b);
if ~isempty(x3(1).line)
y=x3;
end
else 1
x4=changethree(a,b);
if ~isempty(x4(1).line)
y=x4;
end
end
备注:当换乘次数0和1时,用 x=kexingjie(a,b)调出命令 x.line 输出可行解的线路
x.connect 输出可行解的中转站
当换乘次数为2时，用 x=changetwo(a,b) 调出命令 x.line 输出可行解的线路 x.connect 输
出可行解的中转站
当换乘次数为3时，用 x=changethree(a,b) 调出命令 x.line 输出可行解的线路 x.connect
输出可行解的中转站
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
