数学建模甲组B题资料.docx
《数学建模甲组B题资料.docx》由会员分享，可在线阅读，更多相关《数学建模甲组B题资料.docx（16页珍藏版）》请在冰点文库上搜索。
数学建模甲组B题资料
59.67.76.*
16楼
摘要：
本文是解决奥运会时期“乘公交，看奥运”的线路选择需求问题，实质是一个有向图的最短路径问题。
对于公汽网和公汽地铁混合公交网，我们分别建立了两个单目标规划模型，即城市公交查询系统数学模型。
为不同需求的乘客寻找不同的最优路线。
首先建立了有向图的邻接矩阵。
分别以任意起始站点到任意终点的总时间和总费用为目标约束建立模型。
比如对于问题
（1）中的最短乘车时间问题，其数学模型为：
，为了求解这个模型，我们借鉴了Floyd算法和Dijkstra算法各自的优点，设计了一个新的算法，利用对某站点的邻点集进行搜索，得到最优的出行路线选择。
其它情况只要给出了邻接矩阵，那么数学模型和计算方法如上同理可以给出，其结果为：
S3359乘L484（或L324）到达S1746转乘L485到达S1784再转乘L127（或L167）到达S1828
S1557乘L363（或L084）到达S1919转乘L189到达S3186再转乘L460到达S0481
S0971乘L013 到达S2517转乘L290到达S2159再转乘L469到达S0485
S0008乘L463（或L043或L198）到达S1383 转乘L290（或L296）到达S2184再转乘L345到达S0073
S0148乘L308到达S0036转乘L156到达S2210再转乘L047到达S0485
S0087乘L021（或L206或L454）到达S0088 转乘L231（或L381）到达S0427再转乘L097或L429到达S3676
对于问题
（2）则是在问题
（1）的基础上要同时考虑公汽网和地铁网，不同的车转乘时间不同，我们经过分析，提出了一种合理性的假设，使时间计算更方便。
只考虑地铁的邻接矩阵时任意两站点邻接矩阵的权值都是加3，然后更新公汽网和地铁网的混合矩阵，建立的数学模型为：
；
结果为：
S3359 乘L469 经过S0304 转乘L217到达S1828
S1557乘L084 经过S0028 转乘L348再经过S3970转乘L447到达S0481
S0971 乘L013（或L024或L094或L119）经过S0345 转乘L140再经过S2654转乘L469到达S0485
S0008 乘L159 经过S0291 转乘L058到达S0073
S0148 乘L308 经过S0036 转乘L157再经过S1406转乘L045到达S0485
S0087 乘L021（或L206或L454） 经过S0088 转乘L381再经过D36转乘L462到达S3676
？
？
问题（3）是假设又知道所有站点之间的步行时间 ，可建立一个新的邻接矩阵，利用类似的模型和算法也能求出相应的结果。
关键词：
公交查询数学模型、有向图、Floyd算法、Dijkstra算法 、邻接权矩阵、最优解
一、问题提出
随着城市建设的飞速发展及公交系统的不断完善，公交车已成为城市居民出行的主要交通工具。
但是由于城市公交线路四通八达，且随着城市扩建而快速发展，即使当地居民也不一定能找到到达目的地的最佳线路，外地游客更是难以获取公交出行的详细路径信息，因此建立适合于公交线路查询特点的公共数据模型、为出行者提供全面准确的数据信息是城市公交建设与发展的迫切需求。
08年奥运会将在北京举行，届时将有大量观众到现场观看比赛，乘坐公共交通工具（简称公交，包括公汽、地铁）将是大多数人的交通选择。
近年来北京市的公交线路已达800条以上，为了使观众的出行更加通畅、便利，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。
需要解决下列问题：
分别单独考虑公汽和考虑公汽与地铁混合线路，给出任意两站点之间线路选择问题的一般数学模型与算法。
并根据附录数据，利用已建立的模型与算法，求出以下6对起始站→终到站之间的最佳路线，要求有清晰的评价说明。
（1）S3359→S1828
（2）S1557→S0481 （3）S0971→S0485
（4）S0008→S0073 （5）S0148→S0485 （6）S0087→S3676
假设又知道所有站点之间的步行时间，建立任意两站点之间线路选择问题的数学模型。
二、问题分析
城市公交（公汽、地铁）线路选择是一个多目标规划问题，从乘客心理角度考虑，他们希望转乘次数尽可能少（多数人希望最多换乘两次车，若乘换车次太多只能说明该市交通网络不够科学），而且还能节省乘车时间，花的车费较少，我们从这几个方面入手建立数学模型，综合考虑以上因素，为广大市民朋友们的出行提出好的建议。
∙2007-9-2409:
34
∙回复
59.67.76.*
17楼
本题本质是一个关于不同权的最短路问题，我们建立公交查询数学模型的理论依据是参考了Floyd算法和Dijkstra算法的思想，并做了改进，建立了一个新型的公交路线查询数学模型。
公交线路问题本身存在一定的复杂性，因此将公交网络的空间结构以图论的方法精确表达。
具体步骤如下：
先利用Mathematica软件将数据整合成需要的形式。
根据处理问题的需要，将给定的数据按如下方式进行处理：
1、线路编号不变；
2、线路同一票价用整数 1标识，分段记价用整数0标识；
3、上行线与下行线站点完全相同用整数1标识，上行线与下行线站点不完全相同用整数2标识，环形线路用整数3标识。
然后用Mathematica软件对数据进行处理，具体实例（前20条线路）见附录I.
1、建立便于程序使用的矩阵，其中行表示所有的公交线路，其中上行线和下行线完全重合的算为上下两条，环形线路从中间断开，分上行和下行共计算为四条，列表示各条线路依次途径的站点，行列交点表示站点的编号。
2、再建立一个新的分别以所有站点为横、纵坐标的的矩阵，此即为所要讨论的公交网络（作为有向图）的邻接矩阵。
转化成表示所有站点权值的矩阵，同理可求出地铁子网任意两站点的权重，同时对线路进行标记。
对于3、4中相同的站点的权重取其最小。
3、对2中的矩阵，我们借鉴Floyd算法和Dijkstra算法的基本思想构造了一个新的算法进行计算，求出任意两站点的最短时间。
4、对于任意站点的费用最小可做相同的考虑，然后求其与3的加权平均值。
在满足约束条件的前提下，建立单目标规划模型。
利用图论问题的一些知识建立了一个新型的公交路线查询数学模型。
建立了两个目标规划模型，即城市公交查询系统数学模型。
三、模型的基本假设
1、为简化问题，作如下基本参数设定
相邻公汽站平均行驶时间（包括停站时间）：
3分钟
相邻地铁站平均行驶时间（包括停站时间）：
2.5分钟
公汽换乘公汽平均耗时：
5分钟（其中步行时间2分钟）
地铁换乘地铁平均耗时：
4分钟（其中步行时间2分钟）
地铁换乘公汽平均耗时：
7分钟（其中步行时间4分钟）
公汽换乘地铁平均耗时：
6分钟（其中步行时间4分钟）
公汽票价：
分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：
0～20站：
1元；21～40站：
2元；40站以上：
3元
地铁票价：
3元（无论地铁线路间是否换乘）。
2、 假设乘客最多转乘两次，即最多共乘坐了3辆车。
如果转乘两次还不能到达目的地，则说明该城市的公交系统本身存在问题。
事实上我们在做出模型后验证了最多换乘两次的假设是可行的。
3、 假设当任意之间没有直达的公交时，其权（时间、金钱）为无穷大。
在计算机中为了方便表示，定义为一个很大的数，设为5000。
4、 假设建立的模型不考虑影响交通的自然或非自然因素，如雨雪、大雾、大风等灾害性天气以及政府规定的“无车日”对公汽和地铁的运行情况不会受到干扰。
5、 假设北京市交通规划在较长时间内不会变化，公汽和地铁路线、站点不会改变。
6、 假设北京市公共交通行业服务质量比较好，乘客对各路车次的喜好程度相差不大，乐于接受服务。
7、假设车不会晚点到达车站、没有堵车、每一辆车的容量也没有限制。
8、 在乘客明确起点和终点后，乘客不关心所经过的街道、站点，只关心乘车时间、花费、换乘车次。
四、符号说明
：
第k条公共汽车线路（1<=k<=520）
：
第 i号公共汽车站点（1<=i<=3957）
：
第 j号地铁站点（1<=j<=39）
：
从任意站点 到站点 坐直达车所需要的时间
：
从任意站点 到站点 坐直达车所需要的钱数
五、模型进一步分析与建立
本题变量较多，数据量较大，是一个复杂的交通网络问题，即是图论中的有向图问题。
在有关图结构中的最短路问题有著名的Floyd算法和Dijkstra算法。
我们参考了Floyd算法和Dijkstra算法，并做了改进，建立了一个新型的公交路线查询数学模型。
该算法对估价函数予以加权处理，得到矩阵，通过对表示有向图的邻接矩阵做迭代计算，解决了该数学模型的有向图中任意一对顶点之间的最短路径问题。
在本题解答中，我们参考了Floyd算法和Dijkstra算法的思想，并做了改进，建立了一个新型的公交路线查询数学模型。
1、只考虑公汽线路网
数据准备：
对于以下要研究的模型，经计算共有3957个公交站点；共有1084条公汽线路（其中上行线和下行线完全重合的算为上下两条，环形线路从中间断开，分上行和下行共计算为四条）；对所有线路，每条线路最多要经过86个站点。
5.1.1 先考虑单目标规划模型：
从始点到终点所用时间最少
只研究公共汽车线路网时，以所有站点（S0001-S3957）分别为横、纵坐标，建立有向邻接矩阵，在填写矩阵的权时只考虑直达的情况。
矩阵内的元素 表示在同一条线路上的直达汽车从站点 到站点 所需要的时间，为方便以后计算行车、转乘总时间，统一将直达线路上汽车从站点 到站点 行驶的时间 规定为 =（经过的站点数-1）*3+5 ， 此规定的解释：
5是公汽换乘公汽平均耗时5分钟，3是相邻公汽站点之间的平均行驶时间（包括停站时间）为 3分钟，无论直达还是换乘，在汽车的行驶时间都为 -5，可以使问题达到统一。
这样构造的邻接矩阵如下：
其中,
219.242.96.*
20楼
我是用递进的思想解决这个问题的。
思路就是：
先求由起点能直接到达的站点，并检查目的站是否在这些站点里，若在，则结束；若不再，则进而求由起始站出发转乘一辆车后能到的站点，并检查----就这样一直下去直至目的站被到达位置。
然后再反向追踪可到达目的站的路径。
再从这些路径中筛选出最优的（换车最少或耗时最少或费用最低）。
当然达到这个目的的关键是设计好的表达方式，我是通过引进几种矩阵的概念实现这种朴素的想法的。
运算结果表明第一问中的只有2和5需要换两辆车，其他只需换一次车。
在第二问中，我是通过在地铁站和汽车站之间引进‘步行’这种交通工具而把第二问的问题转化为第一问那样的问题的。
第三问也是同样。
只是在计算个站之间步行时间时需编一个专门的函数去求。
不过我发现，我们的程序在换车（当然也包括‘步行’）次数超过5次时程序运行时间好长，不知是我们的算法不够精炼还是问题的规模就是那么大。
想请教诸位。
222.171.12.*
21楼
很高兴，我跟你的思路差不多，结果也是2和5需要换两次车，1，3，4需要换一次车，但6的两个车站刚好位于T2周围的公汽站上，认为可以直达。
不同的是，第一问我们就考虑了地铁站和汽车站之间引进‘步行’，第二问再考虑到地铁的运行。
∙2007-9-2912:
05
∙回复
∙
∙woliuchao
∙0位粉丝
∙
25楼
我成功的用matlab编出了程序,有二十多个调用子程序.
思路开始和20楼一样,但程序出来后发现运算时间太久太久,于是不用两头搜寻,而是只从起点开始向终点搜索.只做到两次换乘,三次的话机子耗时很久.可惜的是虽然做完了,但论文没时间写好.而且另外一队竟然是老师代做,用VB完成,可以用完美来形容他们B题的质量.结果我们这对什么奖都没有.实在郁闷啊.不知道7楼用向量图是如何解的.
可惜我们对没有学计算机的.数据库都是转换成EXCEL表处理.
MATLAB的功能真强大.
∙
∙平明之恋
∙0位粉丝
∙
28楼
因为在实际生活中，极少有人愿意为省1、2块钱而换乘2次以上车的情况，所以我们可以限定换乘次数在2次以内，就是说：
我们只要考虑换乘1次、2次、不换乘的3中情况。
首先，产生一个以从一个站点到其他站点所要经过的站点数为元素产生一个直达矩阵，然后用在起点站与终点站之间插入所需换乘站点的情况，进行循环，最终得到结果，把时间与费用通过某一原则合成，作为权数。
整个程序约25行，得出结果时间在20秒之内。
我运行成功了。
2007年数学建模竞赛“乘公交，看奥运”程序（续）
2008-10-0321:
40
%该成语用于生成模型二的时间邻接矩阵和费用邻接矩阵（直达矩阵）
%WT：
时间邻接矩阵
%WP：
费用邻接矩阵
%WC：
换乘邻接矩阵
%生成时间权重矩阵
WT=zeros（3996,3996）;
[x,y]=size（WT）;
fori=1:
x
forj=1:
y
ifi==j
WT（i,j）=0;
else
WT（i,j）=inf;
end
end
end
%注意此中讨论没有解决公汽—地铁通道—公汽这种换乘方式
%情况一：
公汽—公汽的情况（对应gg）3957*3957
%不能直达，无穷大，能直达，n*3+2分钟步行时间
[x,y]=size（Path_states）;
fori=1:
x
forj=1:
Path_num（i）-1
fork=j+1:
Path_num（i）
ifWT（Path_states（i,j）,Path_states（i,k））>=（k-j）*3+2%保留小的
WT（Path_states（i,j）,Path_states（i,k））=（k-j）*3+2;
end
end
end
end
%情况二：
地铁—地铁的情况（对应dd）39*39
%不能直达，无穷大，能直达，n*2.5+2
[x,y]=size（T_states）;
fori=1:
x
forj=1:
T_num（i）-1;
fork=j+1:
T_num（i）
ifWT（T_states（i,j）,T_states（i,k））>=（k-j）*2.5+2;
WT（T_states（i,j）,T_states（i,k））=（k-j）*2.5+2;
end
end
end
end
%情况三：
公汽—地铁的情况（对应gd）3957*39
%公汽i到地铁j对应的公汽k可以直达，则公汽站i可以直达到地铁j
x=3957;
[x1,y1]=size（D1）;
[x2,y2]=size（D2）;
fori=1:
x%公汽站j
forj=1:
x1%处理第一条线路地铁j
fork=2:
D1_num（j）%地铁站j对应的公汽站k
ifWT（i,D1（j,k））~=inf&WT（i,D1（j,1））>=WT（i,D1（j,k））-2+4%从i到k能直达，同时保留小的
WT（i,D1（j,1））=WT（i,D1（j,k））-2+4;%从i到k的直达时间中-公汽和公汽之间的步行时间+公汽和地铁之间的步行时间
end
end
end
forj=1:
x2%处理第二条线路地铁j
fork=2:
D2_num（j）%地铁站j对应的公汽站k
ifWT（i,D2（j,k））~=inf&WT（i,D2（j,1））>=WT（i,D2（j,k））-2+4%从i到k能直达，同时保留小的
WT（i,D2（j,1））=WT（i,D2（j,k））-2+4;%从i到k的直达时间中-公汽和公汽之间的步行时间+公汽和地铁之间的步行时间
end
end
end
end
%情况四：
地铁—公汽的情况（对应dg）39*3957
%地铁站i对应的公汽站k可以直达到公汽站j，则地铁站i可以直达到公汽站j
[x1,y1]=size（D1）;
[x2,y2]=size（D2）;
x=3957;
fori=1:
x1%处理第一条线路地铁i
fork=2:
D1_num（i）%地铁站i对应的公汽站k
forj=1:
x%公汽站j
ifWT（D1（i,k）,j）~=inf&WT（D1（i,1）,j）>=WT（D1（i,k）,j）-2+4%从k能知道到j，同时保留小的
WT（D1（i,1）,j）=WT（D1（i,k）,j）-2+4;
end
end
end
end
fori=1:
x2%处理第二条线路地铁i
fork=2:
D2_num（i）%地铁i对应的公汽站k
forj=1:
x%公汽站j
ifWT（D2（i,k）,j）~=inf&WT（D2（i,1）,j）>=WT（D2（i,k）,j）-2+4%从k能知道到j，同时保留小的
WT（D2（i,1）,j）=WT（D2（i,k）,j）-2+4;
end
end
end
end
%生成费用矩阵
WP=zeros（3996,3996）;
[x,y]=size（WP）;
fori=1:
x
forj=1:
y
ifi==j
WP（i,j）=0;
else
WP（i,j）=inf;
end
end
end
%注意此中讨论没有解决公汽—地铁通道—公汽这种换乘方式
%情况一：
公汽—公汽的情况（对应gg）
%不能直达，无穷大，能直达，直达费用
[x,y]=size（Path_states）;
fori=1:
x
forj=1:
Path_num（i）-1
fork=j+1:
Path_num（i）
temp=WP（Path_states（i,j）,Path_states（i,k））;%当前矩阵中的值
%计算出费用
ifmod（i,2）==0%i为双数的时候
ifPath_no（i/2,2）==1%单一票价方式
pay=1;
else%分段计价方式
ifk-j<=20
pay=1;
elseifk-j<=40&k-j>=21
pay=2;
else
pay=3;
end
end
else
ifPath_no（floor（i/2）+1,2）==1%单一票价
pay=1;
else
ifk-j<=20
pay=1;
elseifk-j<=40&k-j>=21
pay=2;
else
pay=3;
end
end
end
iftemp>=pay%保留小的
WP（Path_states（i,j）,Path_states（i,k））=pay;
end
end
end
end
%情况二：
地铁—地铁的情况（对应dd）
%不能直达，无穷大，能直达，直达费用
[x,y]=size（T_states）;
fori=1:
x
forj=1:
T_num（i）-1
fork=j+1:
T_num（i）
ifWP（T_states（i,j）,T_states（i,k））>=3;%当前矩阵中的值大于3时保留小的
WP（T_states（i,j）,T_states（i,k））=3;
end
end
end
end
%情况三：
公汽—地铁的情况（对应gd）
%公汽i到地铁j对应的公汽k可以直达，则公汽站i可以直达到地铁j
x=3957;
[x1,y1]=size（D1）;
[x2,y2]=size（D2）;
fori=1:
3957%公汽站i
forj=1:
x1%第一条地铁站j
fork=2:
D1_num（j）%地铁站j对应的公汽站k
ifWP（i,D1（j,k））~=inf&WP（i,D1（j,1））>=WP（i,D1（j,k））%如果i和k连通，同时保留最小的
WP（i,D1（j,1））=WP（i,D1（j,k））;%i到j的直达费用等于i到k的直达费用
end
end
end
forj=1:
x2%第二条地铁站j
fork=2:
D2_num（j
升级会员 