数学建模甲组B题资料.docx

1、数学建模甲组B题资料59.67.76.*16楼摘要： 本文是解决奥运会时期“乘公交，看奥运”的线路选择需求问题，实质是一个有向图的最短路径问题。对于公汽网和公汽地铁混合公交网，我们分别建立了两个单目标规划模型，即城市公交查询系统数学模型。为不同需求的乘客寻找不同的最优路线。 首先建立了有向图的邻接矩阵。分别以任意起始站点到任意终点的总时间和总费用为目标约束建立模型。比如对于问题（1）中的最短乘车时间问题，其数学模型为：，为了求解这个模型，我们借鉴了Floyd算法和Dijkstra算法各自的优点，设计了一个新的算法，利用对某站点的邻点集进行搜索，得到最优的出行路线选择。其它情况只要给出了邻接矩阵

2、，那么数学模型和计算方法如上同理可以给出，其结果为： 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乘L0

3、21（或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）经过S0

4、345转乘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算法、邻接权矩阵、最优解 一、 问题提出 随着城市建设的飞速发展及公交系统的不断完善，公交车已成

5、为城市居民出行的主要交通工具。但是由于城市公交线路四通八达，且随着城市扩建而快速发展，即使当地居民也不一定能找到到达目的地的最佳线路，外地游客更是难以获取公交出行的详细路径信息，因此建立适合于公交线路查询特点的公共数据模型、为出行者提供全面准确的数据信息是城市公交建设与发展的迫切需求。 08年奥运会将在北京举行，届时将有大量观众到现场观看比赛，乘坐公共交通工具（简称公交，包括公汽、地铁）将是大多数人的交通选择。近年来北京市的公交线路已达800条以上，为了使观众的出行更加通畅、便利，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。需要解决下列问题： 分别单独考虑公汽和考虑公汽与地

6、铁混合线路，给出任意两站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用已建立的模型与算法，求出以下6对起始站终到站之间的最佳路线，要求有清晰的评价说明。 (1)S3359S1828(2)S1557S0481(3)S0971S0485 (4)S0008S0073(5)S0148S0485(6)S0087S3676 假设又知道所有站点之间的步行时间，建立任意两站点之间线路选择问题的数学模型。 二、问题分析 城市公交（公汽、地铁）线路选择是一个多目标规划问题，从乘客心理角度考虑，他们希望转乘次数尽可能少（多数人希望最多换乘两次车，若乘换车次太多只能说明该市交通网络不够科学），而且还能节

7、省乘车时间，花的车费较少，我们从这几个方面入手建立数学模型，综合考虑以上因素，为广大市民朋友们的出行提出好的建议。 2007-9-24 09:34 回复 59.67.76.*17楼本题本质是一个关于不同权的最短路问题，我们建立公交查询数学模型的理论依据是参考了Floyd算法和Dijkstra算法的思想，并做了改进，建立了一个新型的公交路线查询数学模型。 公交线路问题本身存在一定的复杂性，因此将公交网络的空间结构以图论的方法精确表达。具体步骤如下： 先利用Mathematica软件将数据整合成需要的形式。 根据处理问题的需要，将给定的数据按如下方式进行处理： 1、线路编号不变； 2、线路同一票价

8、用整数1标识，分段记价用整数0标识； 3、上行线与下行线站点完全相同用整数1标识，上行线与下行线站点不完全相同用整数2标识，环形线路用整数3标识。 然后用Mathematica软件对数据进行处理，具体实例(前20条线路)见附录I. 1、建立便于程序使用的矩阵，其中行表示所有的公交线路，其中上行线和下行线完全重合的算为上下两条，环形线路从中间断开，分上行和下行共计算为四条，列表示各条线路依次途径的站点，行列交点表示站点的编号。 2、再建立一个新的分别以所有站点为横、纵坐标的的矩阵，此即为所要讨论的公交网络（作为有向图）的邻接矩阵。转化成表示所有站点权值的矩阵，同理可求出地铁子网任意两站点的权重，

9、同时对线路进行标记。对于3、4中相同的站点的权重取其最小。 3、对2中的矩阵，我们借鉴Floyd算法和Dijkstra算法的基本思想构造了一个新的算法进行计算，求出任意两站点的最短时间。 4、对于任意站点的费用最小可做相同的考虑，然后求其与3的加权平均值。 在满足约束条件的前提下，建立单目标规划模型。利用图论问题的一些知识建立了一个新型的公交路线查询数学模型。建立了两个目标规划模型，即城市公交查询系统数学模型。 三、模型的基本假设 1、为简化问题，作如下基本参数设定 相邻公汽站平均行驶时间(包括停站时间)：3分钟 相邻地铁站平均行驶时间(包括停站时间)：2.5分钟 公汽换乘公汽平均耗时：5分钟

10、(其中步行时间2分钟) 地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘）。 2、假设乘客最多转乘两次，即最多共乘坐了3辆车。如果转乘两次还不能到达目的地，则说明该城市的公交系统本身存在问题。事实上我们在做出模型后验证了最多换乘两次的假设是可行的。 3、假设当任意之间没有直达的公交时，其权（时间、金钱）为无穷大。在计算机中为了

11、方便表示，定义为一个很大的数，设为5000。 4、假设建立的模型不考虑影响交通的自然或非自然因素，如雨雪、大雾、大风等灾害性天气以及政府规定的“无车日”对公汽和地铁的运行情况不会受到干扰。 5、假设北京市交通规划在较长时间内不会变化，公汽和地铁路线、站点不会改变。 6、假设北京市公共交通行业服务质量比较好，乘客对各路车次的喜好程度相差不大，乐于接受服务。 7、假设车不会晚点到达车站、没有堵车、每一辆车的容量也没有限制。 8、在乘客明确起点和终点后，乘客不关心所经过的街道、站点，只关心乘车时间、花费、换乘车次。 四、符号说明 ：第k条公共汽车线路(1=k=520) ：第i号公共汽车站点(1=i=

12、3957) ：第j号地铁站点(1=j= (k-j)*3+2 %保留小的 WT(Path_states(i,j),Path_states(i,k) = (k-j)*3+2; end end endend%情况二：地铁地铁的情况(对应dd)39*39%不能直达，无穷大，能直达，n*2.5+2x,y = size(T_states);for i = 1:x for j = 1:T_num(i)-1; for k = j+1:T_num(i) if WT(T_states(i,j),T_states(i,k) = (k-j)*2.5+2; WT(T_states(i,j),T_states(i,k)

13、= (k-j)*2.5+2; end end endend%情况三：公汽地铁的情况(对应gd)3957*39%公汽i到地铁j对应的公汽k可以直达，则公汽站i可以直达到地铁jx = 3957;x1,y1 = size(D1);x2,y2 = size(D2);for i = 1:x%公汽站jfor j = 1:x1%处理第一条线路地铁j for k = 2:D1_num(j)%地铁站j对应的公汽站k if WT(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)-

14、2+4;%从i到k的直达时间中-公汽和公汽之间的步行时间+公汽和地铁之间的步行时间 end endendfor j = 1:x2%处理第二条线路地铁j for k = 2:D2_num(j)%地铁站j对应的公汽站k if WT(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 endendend%情况四：地铁公汽的情况(对应dg)39*3957%地铁站i对应的公汽站k可

15、以直达到公汽站j，则地铁站i可以直达到公汽站jx1,y1 = size(D1);x2,y2 = size(D2);x = 3957;for i = 1:x1%处理第一条线路地铁i for k = 2:D1_num(i)%地铁站i对应的公汽站k for j = 1:x%公汽站j if WT(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 endendfor i = 1:x2%处理第二条线路地铁i for k = 2:D2_n

16、um(i)%地铁i对应的公汽站k for j = 1:x%公汽站j if WT(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 endend%生成费用矩阵WP = zeros(3996,3996);x,y = size(WP);for i = 1:x for j = 1:y if i = j WP(i,j) = 0; else WP(i,j) = inf; end endend%注意此中讨论没有解决公汽地铁通道公汽这种换乘

17、方式%情况一：公汽公汽的情况(对应gg)%不能直达，无穷大，能直达，直达费用x,y = size(Path_states);for i =1:x for j = 1:Path_num(i) - 1 for k = j+1:Path_num(i) temp = WP(Path_states(i,j),Path_states(i,k);%当前矩阵中的值 %计算出费用 if mod(i,2) = 0%i为双数的时候 if Path_no(i/2,2) = 1%单一票价方式 pay = 1; else%分段计价方式 if k-j = 20 pay = 1; elseif k-j = 21 pay =

18、2; else pay = 3; end end else if Path_no(floor(i/2)+1,2) = 1%单一票价 pay = 1; else if k-j = 20 pay = 1; elseif k-j = 21 pay = 2; else pay = 3; end end end if temp = pay%保留小的 WP(Path_states(i,j),Path_states(i,k) = pay; end end endend%情况二：地铁地铁的情况(对应dd)%不能直达，无穷大，能直达，直达费用x,y = size(T_states);for i = 1:x fo

19、r j = 1:T_num(i)-1 for k = j+1:T_num(i) if WP(T_states(i,j),T_states(i,k) = 3;%当前矩阵中的值大于3时保留小的 WP(T_states(i,j),T_states(i,k) = 3; end end endend%情况三：公汽地铁的情况(对应gd)%公汽i到地铁j对应的公汽k可以直达，则公汽站i可以直达到地铁jx = 3957;x1,y1 = size(D1);x2,y2 = size(D2);for i = 1:3957%公汽站i for j = 1:x1%第一条地铁站j for k = 2:D1_num(j)%地铁站j对应的公汽站k if WP(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 for j = 1:x2%第二条地铁站j for k = 2:D2_num(j