《数学建模论文-公交查询系统的数学模型.doc》由会员分享，可在线阅读，更多相关《数学建模论文-公交查询系统的数学模型.doc（31页珍藏版）》请在三一文库上搜索。
1、科院6组：鲁成、蔡光达、王奇公交查询系统的数学模型摘要本文针对公交线路选择问题，建立了多目标动态规划模型，运用MATLAB软件实现了整个流程和迭代，最终求出全局近似最优解，即换乘次数最少的情况下耗时最短，费用最低的乘车路线。并分别提供了转乘次数最少、耗时最短、费用最低三种线路满足不同需求的乘客。针对问题一，仅考虑公汽线路，对数据进行初步分析和处理后，考虑到数据的复杂性和数据搜索范围的广度，将不同公交汽线路抽象化，建立站点间直达线路信息存储结构元胞，基于直达线路数据库构造站点间以直达线路数目为元素的邻接矩阵，在邻接矩阵构成的数据结构之上，考虑公汽线路不同票价、线路等条件，采用改进的邻接算法分别以
2、转乘次数最少、耗时最短、费用最低为目标进行全局最佳路线的求解。并分别给出了转乘次数最少、耗时最短、费用最低三种路线来满足不同需求的乘客。针对问题二，在问题一的基础上考虑公汽与地铁混排，将地铁站点与周围的公汽站点集抽象为同一新站点，把以上公汽线路站点映射为新站点，建立新的直达数据库，结合地铁费用、地铁与公汽间的换乘时间以及两者站间行驶时间等条件，将地铁与公汽结合的问题转化为问题一，采用改进的邻接算法得到不同目标下的多种优化方案。针对问题三，根据问题一与问题二基于换乘次数最少逐步分析目标选定最佳路线的模型，在知道所有站点之间的步行时间的基础上，建立以步行代替短距离减少换乘次数和以步行邻边化减少出行
3、用时的优化数学模型，采用广度优先算法,改进公交线路的路线选择方案。关键词：多目标动态规划；MATLAB；邻接矩阵；广度优先算法一、问题重述1.1问题的背景近几年来，城市的公交系统有了很大的发展。公交运输的覆盖面越来越广，公交线路也日益增多，公共交通逐渐成为绝大多数出行人员的首选方式。发达的城市公交系统使得公众的出行更加通畅、便利，同时也给人们出行乘车线路的选择带来了一定的困扰。方便、快捷、经济的公交出行线路方案，不仅可以方便公众的出行，同时也为城市交通减少了不必要的负担，有利于提高城市交通运行的效率，展现城市的现代化风貌。1.2问题的重述 我国人民翘首企盼的第29届奥运会明年8月将在北京举行，
4、届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。1.3有待解决的问题1. 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰
5、的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762. 同时考虑公汽与地铁线路，解决以上问题。3. 假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。附：基本参数设定相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均
6、耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。二、问题分析2.1出行人员乘车需求本文参照了在宜昌市做的一个公交乘客出行心理调查统计结果，它主要对三个因素做了调查：换乘次数、出行距离、出行耗时。从图1中可以看到有41.16%的乘客在选择出行路径时首先考虑的是换乘最少，其次考虑时间最短，而将路程最短作为出行时考虑的首要条件的乘客只占18.60%，故而我们选择以转车次数最少为首要目标，时间最
7、短、路程最短为次要目标。图1：公交乘客出行心理分析图2.2公交网络的特点根据题中信息，公汽线路分三种，下面将这三种线路进行数据处理： 1. 下行线、上行线原路返回 这种线路有两个端点站，在两个端点之间双向行车，而且两个方向上的行车路线相同，经过同样的站点序列。由于线路的方向不同，因此，下行线和上行线可以抽象成两条线路处理。如下图所示：2. 线路为环行线 实际中环形路线一般是双环，但在对这两条线路进行抽象时，为保证任意两站点距离最近，把每条线路再抽象成2条。如下图所示：3. 下行线与上行线经过站点不同 由于下行线与上行线经过站点不同，显然，该种线路需要抽象成两条线路处理。如下图所示：2.3问题一
8、的分析 本问题仅考虑公汽线路，因此，只需对不包含地铁站的1018条行驶路线进行分析即可。对于公众而言，选择路线时主要考虑以下三个方面：换乘次数、路途时间和乘车费用。因此，本问题是一个多目标的规划问题。不难发现，换乘次数的增加必然会引起费用的开销，而且对费用的影响很大。费用最小时的路线，其对应的换乘次数必然很少。因此，我们把换乘次数最少作为第一目标，费用最省和时间最短分别作为第二、三目标。分别考虑对此三个目标的优化，按照第一目标最优，第二、三目标在第一目标最优前提下最优或者次优来求解。2.4问题二的分析对于问题二，对于两条地铁线路，依据问题一中的抽象化方法进行抽象化处理；对于地铁站点，由地铁与邻
9、近公汽站点可换乘的信息可知地铁站点及其周围的公汽站点距离较近，考虑将其抽象化归一为新的站点，减小站点差异性，重新构造站点间的邻接矩阵。基于问题一更新数据，寻找合适的算法组合不同路线及站点分别给出三种目标下的最优方案。2.5问题三的分析考虑公汽站点与地铁站点的实际分布情况，在某些转乘点存在步行小段距离再转车可以节省时间或减少转车次数的情况，在求解时需确定线路中该类选择多样化的站点，然后主要优化该类站点后继线路的选择方案，达到以上三个目标。三、模型假设1. 假设车站站点无重名；2. 假设相邻站点间平均行驶时间一定；3. 假设公交准点到达，不考虑红绿灯等待时间；4. 假设各公交线路公交车发车频度相同
10、；5. 假设公交系统运行顺畅，不考虑中途发生故障堵车等意外情况；6. 假设附录1所给的基本参数均为定制，且能较好的反应实际情况；7. 假设地铁线路间的换乘不需要付费，票价为3元不变；8. 假设坐环行线经过终点站后要重新收费。四、符号说明乘车时间对应的决策变量站点至站点乘车所需时间站点至站点的直达费用表示站点至站点所经过的站数步行时间对应的决策变量站点间是否有地铁换乘表示第个站点负载压力权总等待时间步行时间五、问题一的解答5.1模型一的建立5.1.1目标函数的确立目标一：换乘次数最少引入0-1决策变量表示弧是否在起点与终点的路上，则：若与之间无直接相连的弧，但可通过中间节点转跳，表明若vi与vj
11、之间无直接相连的弧，但可通过中间节点转跳，表明由站点i到j之间不可直达，但可通过转乘到达，则由到之间换乘次数为经过的总弧数减 1，即换乘次数最小可表示为：目标二：行程总时间最短：目标三：行程总费用最少：5.1.2确定约束条件1. 换乘次数约束基于对目标一的分析，以c表示换乘次数：注：为自然数其中，参数为人为设定值，根据实际情况，考虑以下三种情况：2. 行程总费用最少设表示车辆属性：设表示所经过的站数：5.1.3综上所述，得到问题一的最优化模型5.2模型一的求解运用MATLAB软件求解，得：表1：问题一结果路线第1目标换乘次数时间（分）费用（元）S3359S1828换乘次数11043时间2673
12、费用2673S1557S0481换乘次数21093时间31024费用21093S0971S0485换乘次数11313时间21063费用21063S0008S0073换乘次数1862时间4625费用1862S0148S0485换乘次数21093时间31054费用21093S0087S3676换乘次数1682时间2493费用16825.3模型一的结果分析分析结果，得：1.几乎所有换乘3次的线路都可以以较短时间、较低的费用到达目的站点，说明选择三次作为换乘次数的上限是可行的。2.考虑查询系统的时效性，给出MATLAB程序运行时间。由运行时间：查询换乘次数小于1次含1次的线路，程序运行时间远小于1秒；
13、查询换乘2次程序耗时不超过5秒；查询换乘3次程序所需时间200秒左右。在实际情况中，乘客在乘车点等车时进行路线查询，以上查询时间是可以被乘客接受的。以上所述程序运行时间说明在本文描述的数据存储结构下，改进的邻接算法的可行性与较低的时间复杂度。综述，模型I求解的线路方案集使用于不同需求下的所有用户，具有较强的实用价值，很大程度上满足了乘客乘车线路多样化的需求。六、问题二的解答6.1模型二的建立6.1.1确定目标函数目标一：换乘次数最少引入0-1决策变量表示弧是否在起点与终点的路上，则：若与之间无直接相连的弧，但可通过中间节点转跳，表明由站点i到j之间不可直达，但可通过转乘到达，则由到之间换乘次数
14、为经过的总弧数减 去1，即换乘次数最小可表示为：目标二：行程总时间最短：(1)乘车时间（为各站点最快直达时间，基于，包括地铁在内）：(2)总等待时间：设表示ij 最短直达为公汽，表示最短直达为地铁，总等待时间表示为：(3)总步行时间： 将相同车型换乘、不同车型换乘的步行时间，一同视为2 分钟 不同车型换乘多步行的4 分钟表示为：地铁转地铁是不同车型换乘的特例，且只可能在D12 与D18 转乘，出现这种情况在基础上减少步行时间4 分钟。表示为：在地铁直达时，需要另外加上4 分钟出站步行时间：若始发乘坐地铁转公交到达终点，需要增加步行时间2 分钟：若始发乘坐公交转地铁到达终点，也需要增加步行时间2
15、 分钟：总步行时间表示为：则行程总时间最短表示为（总等待时间+总步行时间+乘车时间）：目标三：行程总费用最少：6.1.2确定约束条件(1) 换乘次数约束基于对目标一的分析，以c表示换乘次数：(2) 最短路起讫点约束(3) 地铁间换乘约束站点间是否有地铁换乘，使用表示，则与走的路径需满足：有地铁线路可知，地铁转地铁只可能在D12与D18转乘，故转乘总次数不大于2：6.1.3综上所述，得到问题二的最优化模型6.2模型二的求解运用MATLAB软件求解，得：表2：问题二结果路线第1目标换乘次数时间（分）费用（元）S3359S1828换乘次数11043时间2673费用2673S1557S0481换乘次数
16、21093时间31024费用21093S0971S0485换乘次数11313时间4105.57费用21063S0008S0073换乘次数1862时间356.55费用1862S0148S0485换乘次数21093290.55时间389.56费用21093S0087S3676换乘次数0303时间0303费用16826.3问题二的结果分析分析结果，得：1.几乎所有换乘3次的线路都可以以较短时间、较低的费用到达目的站点，说明选择三次作为换乘次数的上限是可行的。2.考虑查询系统的时效性，给出MATLAB程序运行时间。由运行时间：查询换乘次数小于1次含1次的线路，程序运行时间远小于1秒；查询换乘2次程序耗
17、时不超过5秒；查询换乘3次程序所需时间200秒左右。在实际情况中，乘客在乘车点等车时进行路线查询，以上查询时间是可以被乘客接受的。以上所述程序运行时间说明在本文描述的数据存储结构下，改进的邻接算法的可行性与较低的时间复杂度。综述，模型二求解的线路方案集使用于不同需求下的所有用户，具有较强的实用价值，很大程度上满足了乘客乘车线路多样化的需求。七、问题三的解答7.1模型三的建立7.1.1确定目标函数基于前面问题的分析，本模型主要以出行总时间最省为主要目标，同时考虑转乘次数尽量少，行程费用最少，转乘点始发站最多，站点负载压力最小,所以建立以下目标函数：目标一：行程总时间最短（1）时间权值（2）引入0
18、-1决策变量表示乘车时弧是否在起点与终点的路上，则：（3）引入0-1决策变量表示步行十弧是否在起点与终点的路上，则：则目标函数为：目标二：行程总费用最少乘车费用权，则目标函数为：目标三：站点负载压力最小 以表示第个站点负载压力权，则目标函数为：7.1.2确定约束条件（1）最短路约束由于行走路线中任意两点之间只会选择一种出行方式，即：我们还知道决策变量必须满足最短路问题中的主要现在条件，如下所示：（2）换乘次数约束，以表示乘客所能承受的最大换乘次数，则（3）地铁间换乘约束 站点间是否有地铁换乘，使用表示，则与走的路径需满足：有地铁线路可知，地铁转地铁只可能在D12与D18转乘，故转乘总次数不大于
19、2：7.1.3综上所述，得到问题三的最优化模型7.2模型三程序设计流程图八、模型的评价与推广8.1模型的优点1. 通过假设舍弃了对问题影响不大的因素，只保留乘车时间，换乘次数，乘车花费这几个核心目标，使问题更加清晰，得出的线路更全面合理；2. 建立在图论基础上能够求解出转乘次数不超过三次时的所有可行方案，并可根据公众的不同需求，给出最佳路线方案，模型实用性较强；3. 模型的现实意义强，具有很好的实用性和扩展性。8.2模型的不足1. 在转乘次数超过3次的情况下，运用本模型求解计算过程复杂，计算量过大，故本模型存在一定的局限性。2. 由于在计算过程中题目给的平均行驶及转车时间是非现实的，所以使得本
20、模型的应用于现实时存在偏差。8.3模型的推广解读题目不难发现这是运筹学中的最短路问题，仔细分析建立的模型：模型不仅适用于乘公交，即最短路和最低费用的问题，通过不同的权值变化，这类问题可归结为最短路问题，而最短路问题作为图论或运筹学中的重要分支，在工商业、交通运输、工程技术、行政管理等领域有着广泛的应用，由此可知本模型实用性较强，易于推广。参考文献1 姜启源，数学建模第三版，北京：高等教育出版社，2006年2 徐多勇、李志蜀、梅林，基于GSM短信息的公交查询系统的最优化转乘方案研究与设计，计算机应用，27卷：2007年6月。3 王莉，李文权，公共交通系统最佳路径算法，东南大学学报，第34卷：第3
21、 期，2004年 3月4 Duane Hanselman、Bruce Littlefield 著，朱仁峰译，Matlab 7，北京：清华大学出版社，2006年5月第一版附录附录一：clc,clear%1第一问数据处理clc;clear allfid = fopen(1.1 公汽线路信息.txt,r); i=1; while 1 tline = fgetl(fid); if ischar(tline) break; end if strcmp(tline,) continue end if strcmp(tline(1),L) str=tline continue elseif strcmp(t
22、line,END) break end if strcmp(tline,单一票制1元。) P=1; continue elseif strcmp(tline,分段计价。) P=2; continue end if strcmp(tline(1:2),上行) Li,1=str; Li,2=P; Li,3=上行; Li,4=tline(4:end); i=i+1; continue elseif strcmp(tline(1:2),下行) Li,1=str; Li,2=P; Li,3=下行; Li,4=tline(4:end); i=i+1; continue elseif strcmp(tlin
23、e(1:2),环行) Li,1=str; Li,2=P; Li,3=环行1; Li,4=strcat(tline(4:end),tline(10:end); i=i+1; %计算来回 Li,1=str; Li,2=P; Li,3=环行2; Li,4=strcat(tline(4:end),tline(10:end); i=i+1; continue elseif strcmp(tline(1),S) Li,1=str; Li,2=P; Li,3=来回1; Li,4=tline; i=i+1; %计算来回 Li,1=str; Li,2=P; Li,3=来回2; Li,4=tline; i=i+1
24、; continue end endfclose(fid);%建立邻接矩阵for i=1:size(L,1) tline=Li,4; t=findstr(tline,S); temp=zeros(1,length(t); if strcmp(Li,3,来回2) | strcmp(Li,3,环行2) for j=length(t):-1:1 temp(length(t)-j+1)=str2double(tline(t(j)+1:t(j)+4); end else for j=1:length(t) temp(j)=str2double(tline(t(j)+1:t(j)+4); end end
25、L2i,1=temp; end for i=1:3957 if floor(i/10)=0 Citi=strcat(S000,num2str(i); elseif floor(i/100)=0 Citi=strcat(S00,num2str(i); elseif floor(i/1000)=0 Citi=strcat(S0,num2str(i); else Citi=strcat(S,num2str(i); end end Cit3958=D01：S0567，S0042，S0025; Cit3959=D02：S1487; Cit3960=D03：S0303，S0302; Cit3961=D04
26、：S0566; Cit3962=D05：S0436，S0438，S0437，S0435; Cit3963=D06：S0392，S0394，S0393，S0391; Cit3964=D07：S0386，S0388，S0387，S0385; Cit3965=D08：S3068，S0617，S0619，S0618,S0616; Cit3966=D09：S1279; Cit3967=D10：S2057，S0721，S0722，S0720; Cit3968=D11：S0070，S2361，S3721; Cit3969=D12：S0609，S0608; Cit3970=D13：S2633，S0399，S0
27、401，S0400; Cit3971=D14：S3321，S2535，S2464; Cit3972=D15：S3329，S2534; Cit3973=D16：S3506，S0167，S0168; Cit3974=D17：S0237，S0239，S0238，S0236,S0540; Cit3975=D18：S0668; Cit3976=D19：S0180，S0181; Cit3977=D20：S2079，S2933，S1919，S1921,S1920; Cit3978=D21：S0465，S0467，S0466，S0464; Cit3979=D22：S3457; Cit3980=D23：S251
28、2; Cit3981=D24：S0537，S3580; Cit3982=D25：S0526，S0528，S0527，S0525; Cit3983=D26：S3045，S0605，S0607; Cit3984=D27：S0087，S0088，S0086; Cit3985=D28：S0855，S0856，S0854，S0857; Cit3986=D29：S0631，S0632，S0630; Cit3987=D30：S3874，S1426，S1427; Cit3988=D31：S0211，S0539，S0541，S0540; Cit3989=D32：S0978，S0497，S0498; Cit399
29、0=D33：S1894，S1896，S1895; Cit3991=D34：S1104，S0576，S0578，S0577; Cit3992=D35：S3010，S0583，S0582; Cit3993=D36：S3676，S0427，S0061，S0060; Cit3994=D37：S1961，S2817，S0455，S0456; Cit3995=D38：S3262，S0622; Cit3996=D39：S1956，S0289，S0291;%2排序% T_SORT( A ,n , p ) % A 根据第n行排序 % p=1升序 ，2 降 % powered_BY_* syms pSIZE=si
30、ze(L); if p=1 xx,idx=sort(L(n,:); for i=1:SIZE(1) L(i,:)=L(i,idx); end elseif p=2 xx,idx=sort(L(n,:),descend); for i=1:SIZE(1) L(i,:)=L(i,idx); end end %3直达列表建立S(1:3957,1:3957)=zeros(1,1,uint16); for i=1:1040 t=L2i,1; for j=1:length(t)-1 for k=j+1:length(t) temp=St(j),t(k); %每条路线任意两点 str=Li,1; %L中的第
31、一列 n,m=size(temp); if n=1 & temp(1,1)=0 temp(n,1)=str2double(str(2:end); if Li,2=2 if (k-j)40 temp(n,2)=3; elseif (k-j)20 temp(n,2)=2; else temp(n,2)=1; end else temp(n,2)=1; end temp(n,3)=k-j; else temp(n+1,1)=str2double(str(2:end); if Li,2=2 if (k-j)40 temp(n+1,2)=3; elseif (k-j)20 temp(n+1,2)=2;
32、else temp(n+1,2)=1; end else temp(n+1,2)=1; end temp(n+1,3)=k-j; end St(j),t(k)=temp; end end end for i=1:3957 for j=1:3957 if length(Si,j)=1 Si,j=T_SORT(Si,j,3,1); end end end Time=zeros(3957,3957,uint8); for i=1:3957 for j=1:3957 if length(Si,j)=1 Time(i,j)=size(Si,j,1); end end end TT=zeros(3957,
33、3957,uint8); for i=1:3957 for j=1:3957 temp=Si,j; if temp(1,1)=0 TT(i,j)=temp(1,3); end end end %4邻接搜索程序段问题一求解 N=971; M=485; % 直达 if Time(N,M)=0 temp=SN,M; for i=1:size(temp,1) disp(strcat(直达车为:L,num2str(temp(i,1) end return end clear U U2 % 一次转车 t=1:3957; T2=Time(N,:).*Time(:,M); if sum(T2)=0 x=1;
34、t=t(T2=0); for i=1:length(t) t1=SN,t(i); t2=St(i),M; t1=double(t1); t2=double(t2); for j=1:size(t1,1) for k=1:size(t2,1) U(x,1)=1;%转站次数 U(x,2)=(t1(j,3)+t2(k,3)*3+5+3;%总时间 U(x,3)=t(i);%转站点 U(x,4:5)=t1(j,1) t2(k,1);%车辆 %是否始发站 temp=0; for k1=1:1040 if str2double(Lk1,1(2:end)=U(x,5) if L2k1,1(1,1)=t(i)
35、temp=1; break end end end U(x,6)=temp; U(x,7)=t1(j,2)+t2(k,2);%费用 x=x+1; end end end return end F=U(1,2); for j=2:length(U(:,2) if U(j,2)=F; F=U(j,2); index=j; endend%二次转车 t=1:3957; x=1; for i=1:3957 if Time(N,i)=0 for j=1:3957 if Time(j,M)=0 & Time(i,j)=0 t1=SN,i; t2=Si,j; t3=Sj,M; t1=double(t1); t2=double(t2); t3=double(t3); for k1=1:size(t1,1) for k2=1:size(t2,1) for k3=1:size(t3,1) U2(x,1)=2;%转站次数 %总时间 U2(x,2)=(t1(k1,3)+t2(k2,3)+t3(k3,3)*3+10+3; U2(x,3)=t(i);%转站点 U2(x,4)=t(j);%转站点 U2(x,5:6)=t1(k1,1) t2(k2,1);%车辆1,2 %是否始发 temp=0; for kk=1:1040