公交查询系统最佳路线设计

公交查询系统最佳路线设计摘要本文研究的是在三种不同情况下，确定任意两站点最优路线问题。结合生活实际，我们定义最优路线标准是换乘次数最少，所用时间最短，乘车费用最低，并将其分别位作为第一、第二、第三目标建立多目标规划模型。利用广度优先遍历原理编程得到满意的乘车路线。针对问题一，只考虑公交的情况下，对公交路线进行抽象化处理。根据网上调查结果，确定多目标规划模型，利用matlab编程求解得到依次满足三个目标的任意两点的乘车路线。以下为6对起始站一终到站之间的部分可行路线：起始f终到站路线转乘时间/分费用S3359-S1828S3359切36（下）＞S1784l167（下）＞S182811013S1557fS0481S1557l08（下）＞S3389l08。（下）＞S2361—L312（下）＞S048121303S0971fS0485S0971L013（下）＞S2184L417（下）＞S048511283S0008fS0073S0008L15（下）＞S2683l058下）＞S00731832S0148fS0485S0148l02（环）＞S0345lvkk下）＞S3037—L104（下）＞S048521303S0087fS3676S0087L216（下）＞S0145 L506＞S367611253针对问题二，将地铁站点与其周围的公汽站抽象为同一站点。同样建立以转乘次数最少的为第一目标，所用时间短和费用低分别为第二、三目标的多目标规划模型。利用matlab编程求解，得到满意的乘车路线。针对问题三，以乘客所在站点为中心，步行时间上线为半径的区域内站点均考虑步行。将此区域内站点抽象为同一站点，建立多目标规划模型，进行编程求解，并与问题二结果进行比较。关键字多目标规划模型广度优先遍历抽象化关键字多目标规划模型广度优先遍历抽象化1、 问题重述1.1背景信息：我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具(简称公交，包括公汽、地铁等)出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。1.2需要解决的问题：1、 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站一终到站之间的最佳路线(要有清晰的评价说明)。(1)、S3359-S1828 (2)、S1557-S0481 (3)、S0971-S0485(4)、S0008-S0073 (5)、S0148-S0485 (6)、S0087-S36762、 同时考虑公汽与地铁线路，解决以上问题。3、 假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2、 模型假设与符号说明2.1模型假设假设1：相邻站点平均时间一定；假设2：公交运行不出现交通堵塞，公交准时到达每个站点;假设3：交通工具票价稳定，不考虑其他因素对票价的影响;假设4：所有人的步行速度相等；假设5：不会出现车辆拥挤或超载而使乘客误车的情况。2.2符号说明t相邻公汽站平均行驶时间t二3分钟t'相邻地铁站平均行驶时间t'=2.5分钟t1公汽换乘公汽平均耗时t=5分钟1t2公汽换乘地铁平均耗时t=6分钟2t3地铁换乘地铁平均耗时t=4分钟3t4地铁换乘公汽平均耗时t=7分钟4

T从始发站到终点站所用总时间W从始发站到终点站所花总费用y1公汽与公汽的转乘次数y2公汽转乘地铁的次数y3地铁转乘地铁的次数y4地铁转乘公汽的次数Y从始发站到终点站总共转乘次数x从始发站到终点站乘坐公交所经过的总站点数（不考虑出发占）x'从始发站到终点站乘坐地铁所经过的总站点数（不考虑出发占）tpq从站点p到站点q的步行时间t〃乘客选择步行的时间上限3、 问题分析本文主要研究的交通网络中的寻优问题，要求在三种不同情况下，找出任意两站点之间最佳路线。联系生活实际，考虑公众乘坐公交的出行，确定目标函数，找出乘客满意的乘车路线。对于问题一，在仅考虑公汽线路的情况下，根据公众乘坐公交出行的考虑因素，建立以换车次数最少为第一目标，所花时间和费用最少分别为第二、第三目标下的多目标规划模型。通过题中给出数据运用matlab编程得到任意两点之间的乘车路线，再结合目标函数对所得路线进行筛选，找出换车次数最少，所花时间和费用较小的路线作为最佳路线。对于问题二，在同时考虑地铁和公交的情况下。根据问题一中的抽象化方法，将地铁线路T1抽象为一条单向的公交线路，T2抽象为一条环形的公交线路；对于地铁站点，由于地铁与邻近公汽站点可换乘，我们认为地铁站点与周围的公汽站点距离较近，将其抽象化为同一站点，重新构造站点间的关系矩阵。结合问题一，建立优化模型进行编程求解。对于问题三，将步行考虑在出行方式中。一般来说，出行者选择步行的目的是为了减少换乘次数或花费时间。当两个站点相邻近时，乘客才愿意选择步行换乘，因此我们需确定一个邻近站点的范围界限。但考虑到本文的目标之一是所用时间最短，为此将邻近站点的范围界限转化为时间界限，即所用步行时间在某一范围之内时，乘客才考虑步行。基于这种思想，再结合问题一，确定多目标优化模型进行编程求解。

4、 数据处理4.1对站点数据处理利用matlab编程从文本中按行读取数据，将每一行数据作为一个元胞，按行存放在元胞矩阵中，如下图1示：元胞1□---L001元胞2分段计价元胞3|--------S0619-S1914..元胞...［一一…4.2地铁线路的抽象处理地铁与邻近公汽站点可换乘说明地铁站点及其周围的公汽站点距离较近，所以考虑将其抽象为新的站点，如下图2：加靠为一个站点4.3公交乘客出行心理调查分析：在研究乘公交出行最优算法时，首先要了解乘客出行时所要考虑的因素。通过对公交乘客的出行心理、行为的调查研究来确定模型的优化目标及约束条件是必要的。根据网上搜索得到合肥市关于公交乘客出行需求的调查结果，如图3所示：从图中可以看出公交乘客在出行时，考虑最多的是换乘次数，其次时间最短（在此将时间最短和路程最短统一作为时间最短来考虑）和费用最少。所以在换乘次数已经确定的情况下，选择时间较短和费用较少的路线作为最佳路线。4.4所能接受的最长步行时间调查表:

结合实际情况，乘客对距离较近的站点会考虑步行换乘，省钱的同时也可能节省时间。当步行时间较短时，才会选择步行。以下是通过网上搜索得到的换乘口一S口一S分钟」S.86%-20^钟以上」S.S6%^16-20^,7.59%通过观察发现，大多数人所能接受的最长步行时间是6-10分钟。所以对于问题三，我们考虑以步行8分钟为乘客的步行时间上限。数据来源：问卷星unip.Bin 5、 问题一的解答5.1模型建立根据问题一的分析，建立以换车次数最少为第一目标，所花时间和费用最少分别为第二、第三目标下的多目标规划模型。5.1.1确立目标函数：目标一：转乘次数最少设从始发站到终点站总共转乘次数为r，则转乘次数最少的目标函数：minY目标二：所用总时间最短总时间包括转乘时间和经过站点所用时间，得所用时间最少的目标函数：minT=tx+1y目标三：所花费用最少判断线路/是否为分段计价：勺单一票价七一w分段计价在路线i(i<y1+1)(分段计价)经过站数为X.，则：[1(0<x<20)w.=<2(21<X<40).得出所花费用最少的目标函数：minW=罢+'ui=i=15.1.2确定约束条件在分段计价路线上经过的站不超过A-B经过的共站点，即:土<xii=1只考虑换乘次数不超过两次的情况下的乘车路线，得：约<2综上得问题一的多目标优化模型为：1minY<minTminW罢*1x,<x5.2模型求解：5.2.1求出换乘次数最少的可行路径设S(A)、S(B)分别为经过起点A、终点B的所有公汽线路的集合，即S(A)={Ali=1,2,3…a}，S(B)={BIj=1,2,3…b}设第i条线路A=；A,A，,A…A'其中A,A分别表示第i条线路的起点和终TOC\o"1-5"\h\zI i11213 im i1im点；第j条线路B=〈B「B2,B B)，其中B,B分别表示第j条线路的起点和终点。算法品下："°"" 刀"1、 若S(A)cS(B)^0，即存在i,j使A=B，表示站点A,B间可以通过一次乘车直接到达，线路如： ijA—a=Bj>B找出经过站点最少的路线作为最优路线。2、 若S(A)cS(B)=0，则A,B两站点间没有直达路线，需要换乘。模型只考虑换成两次的情况：一次换乘：经过起点站A的某条公汽线路与经过终点B的某条公汽线有公共站点A(B)，得出线路如：ipjA-A->A(B)-a->B若可以一次转乘，则计算出起始站与终点站间经过站点最少的路线为最优路线。二次换乘：设S(C)为S(A)中所有能转乘车次的集合S(C)={CIr=1,2,3…c}如果S(C)cS(B)^0，即存在C=B，则找出此交集，并按顺序找出这个交集中的车由哪些车次转来，可知经两次转车可达到目的站点。路线如下：A—r>a(C)-r>C(B)—>B计算出A,B之间所经站点最少的路线作为最优路线。5.2.2算法步骤：首先我们将文本数据按行存在一个元胞矩阵的每一行中，然后从外部输入要查询线路的起点与终点。查找线路时，我们先考虑能否直达，步骤如下：建立一个记录经过某一点的所用线路的函数；然后将输入的点分别代到上述函数中，分别得到经过起点A和终点B的所有线路S（A），S（B）；判断两者是否在S（A）=S（B）。如果存在，将A,B两之间经过的站点数n记录下来，与初始A,B间站点数n0（初始值设为无穷大）比较。如果n<n0，则记录次线路，同时将n0赋值为n；否则舍去此线路；以此循环，直到找出所有S（A）=S（B）且n最小的情况。考虑转乘一次，步骤如下：先输入始发站A，搜索经过A的所有线路S（A）；然后在上述线路上分别用A之后的每个站点搜索经过它的所有线路；重复直达的情况下的算法步骤。考虑转乘两次和上面一样，不同的是在转乘一次的基础上增加一个搜索线路。5.2.3模型结果依照以上的算法步骤，运用matlab编程进行求解。在路线的选择时，首先考虑换乘次数最少的，其次是经过站点最少（所用时间最少），最后考虑的是费用。问题一的具体结果如下：①从S3359-S1828转乘次数最少的，经过站点较少的选择路径，如下表1.1：转乘次数路线经过站点数所花时间（分钟）所用费用（元）1S3359切36（下）＞S1784li们（下）＞3359l436（下）＞S1784乙2顷下）＞S1828321013②从S1557-S0481转乘次数最少的，经过站点较少的选择路径，如下表1.2：转乘次数路线经过站点数所花时间（分钟）所用费用（元）2S1557lo8（下）＞S3389l。8（下）＞S2361—L312（下）＞S04814013032S1557 L084（下）＞S3389l157（上）＞S2361—L312（下）＞S04814013032S1557L084（下）＞S3389l河.下）＞S2361—L312（下）＞S04814013032S1557L084（下）＞S3389%3倒下）＞S2361—L312（下）＞S0481401303③从S0971-S0485转乘次数最少的，经过站点较少的选择路径，如下表1.3：转乘次数路线经过站点数所花时间（分钟）所用费用（元）

1S0971顷3（下）＞S2184切17（下）＞S0485411283④从S0008-S0073转乘次数最少的，经过站点较少的选择路径，如下表1.4：转乘次数路线经过站点数所花时间（分钟）所用费用（元）1S0008心（下）＞S2683l058下）＞S0073268321S0008L159（下）＞S0291l058（下）＞S007326832⑤从S0148-S0485转乘次数最少的，经过站点较少的选择路径，如下表1.5：转乘次数路线经过站点数所花时间（分钟）所用费用（元）2S0148L02（环）＞S0345lmo（下）＞S3037—L104（下）＞S04854013032S0148L02（环）＞S1609lm0（下）＞S3037—L104（下）＞S04854013032S0148L308（下）＞S0345%1你下）＞S3037—L104（下）＞S0485401303⑥从S0087-S3676转乘次数最少的，经过站点较少的选择路径，如下表1.6：转乘次数路线经过站点数所花时间（分钟）所用费用（元）1S0087L21（下）＞S0145L506＞S36764012535.3结果分析从以上六个表中的数据可以看出，根据模型求出的任意两点之间所用时间和费用均相等，乘车路线也无太大差异，所以以上所有路线均可供乘客选择。6、 问题二的解答6.1模型建立将地铁与相邻公交站点抽象为同一站点，结合问题一，建立以转乘次数最少为第一目标，所用时间和费用最少分别第二、三目标的多目标优化模型。6.1.1确定目标函数目标一：换乘次数最少总换乘次数为两种交通工具互转乘次数的和，得转乘次数最少的目标函数：miny=miny=£（y+y+y+y）目标二：所花时间最少12 3 4总时间包括转乘时间和经过站点所用时间，其中乘公交所用时间T1=xt乘地铁所用时间T2=xft，则所用总时间最少的目标函数：minT=T+T+(yt+yt+yt+yt)1 2 11 22 33 44目标三：所花费用最少总费用等于各条路线上所花费用之和。判断线路i是公交线还是地铁线；若i为公交线，判断线路i是单一票价还是分段计价'1 公交(单一票价)u=\w公交(分段计价)'[3i地铁得总费用最少的目标函数：minW=引uii=16.1.2确定约束条件总转乘次数少于两次：0<Y<2(YeN)综上得问题二多目标模型为：minY<minT

minWS.t0<Y<2(YeN)6.2模型求解依照问题一的算法步骤，运用matlab编程进行求解得出题中6对起始站一终到站之间的最佳路线。7、 问题三的解答7.1模型建立：根据分析，当步行时间在某一范围之内乘客时才会选择步行。以乘客所在的站点为中心，以步行时间上限为半径，找出在范围内的所有站点(邻近点)。同问题二，将这些点抽象为同一点，如下图：O\'邻近站点—-—-——这些站点之间均通过步行到达。7.1.1确定目标函数

目标一：换乘次数最少minY=£(y+y+y+y)12 3 4目标二：所花时间最短乘公交所用时间：乘地铁所用时间:步行所花时间：乘地铁所用时间:步行所花时间：T=xt1T=xftfT=zxfft苴中*_{1站点p,q间步行pq其中X=0站点p,q间不步行得出从始发站到终点站所用时间最少的目标函数为：pqminT=T+T+T+(yt+yt+yt+yt)1 2 3 11 22 33 44目标三：所花费用最少同问题二，总花费最少的目标函数：minW=Y+1uii=17.1.2确定约束条件：从站点p到站点q所花时间不超过乘客步行时间上限:t<t〃总转乘次数不超过两次：0<Y<2(YeN)综上得问题三的多目标优化模型：minY<minT

minW{0<Y<2s.tt<t〃pq8、 模型的评价、改进及推广8.1.1优点：1、 模型舍弃了对问题影响不大的因素，只保留换乘次数，乘车时间，所花费用这几个核心目标建立模型，使问题简化清晰。2、 根据网上搜索的公交乘客出行调查表的结果确立目标函数，使模型更贴近实际情况。3、 模型将距离较近的站点抽象为同一站点，使问题得到简化。8.1.2缺点1、 在模型中我们只考虑了最多两次转乘就能够到达目的地的情况。如果2次转乘还不能到达目的地本模型将不能给出答案。2、 本模型没有考虑到乘客在乘公交时的其他需求，如沿途观光旅游等。8.2模型改进1、 像观看奥运会这样的大型赛事，对游客而言，更希望在乘车途中可观赏到北京的特色景观及建筑，如奥运场馆、名胜古迹等。基于这些因素，我们所设计的查询系统在给出常规最佳路线的同时，也应提示一条观光路线供乘客自由选择。2、 题中给出的是一个静态的交通系统，只要给出始发站和终点站，我们就可以通过算法求得可行路线。但是在现实生活中，交通系统随时都可能在发生变化，常见的如：上下班时候的高峰期，由于交通事故某两个站点之间的线路暂时中断等，这些在本题中都没有能够反应出来。所以应考虑从实际出发，建立动态系统模型，可以根据最新的数据信息得出最优方案。8.3模型推广本文解决的是最佳路线的设计问题，结合实际情况建立优化目标模型。本模型不仅适用于乘车路线的选择，还可用于观光旅游及公交站点位置的选择等。9、 参考文献【1】邓化宇李康弟黄建雄，改进的Dijkstra矩阵算法在城市公交线路选择中的应用［J］，上海电力学院学报，第25卷第1期；【2】王林曹帅王欢李扬，基于广度优先的城市公交出行线路选择［J］，沈阳化工学院数理系，辽宁沈阳，110142；【3】扈震张发勇刘书良，城市公交换乘数据模型研究及算法实现［J］,中国地质大学信息工程学院，湖北武汉，430074【4】百度，出行者所期望的地铁与公交换乘步行时间和换乘候车时间问卷调查表，(/report/222042.aspx)附录基本参数设定相邻公汽站平均行驶时间（包括停站时间）：3分钟相邻地铁站平均行驶时间（包括停站时间）：2.5分钟公汽换乘公汽平均耗时： 5分钟（其中步行时间2分钟）地铁换乘地铁平均耗时： 4分钟（其中步行时间2分钟）地铁换乘公汽平均耗时： 7分钟（其中步行时间4分钟）公汽换乘地铁平均耗时： 6分钟（其中步行时间4分钟）公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0〜20站：1元；21〜40站：2元；40站以上：3元地铁票价：3元问题一的matlab程序%%%functionmainclear;clc;s0=input(,请输入起点站\n');s1=input(,请输入终点站\n');%s0='S3359';s1='S1828';n=0;a={};b1={'线路/过站数’};a1=fopen('d:/我的文档/桌面/1.1公汽线路信息.txt');whilen<520*4+1t=fgetl(a1);n=n+1;ifischar(t)a=[a;t];endendk1=f(a,s0);k2=f(a,s1);p0=inf;%直达fori=1:size(k1,1)forj=1:size(k2,1)ifk1(i}(1)==k2(j}(1)||k1(i}(1)+1==k2(j}(1)||k1(i}(1)-1==k2(j}(1)b=[s0];p=g(a,s0,s1);m=k1(i}(1);fori1=1:4m=m-1;ifstrncmp(a{m},'L',1)b=[b,'-',a{m},'-',s1,'',p];ifall(strcmp(b,b1(size(b1,1),:)))||p>p0

b=[];elseb1=[b1;b];p0=p;endendendendendendifsize(b1,1)~=1disp(bl);break;end%转乘一次fori=1:size(k1,1)fori1=k1{i}(2):6:size(a{k1{i}(1)},2)-4k3=f(a,a{k1{i}(1)}(i1:(i1+4)));p1=g(a,s0,a{k1{i}(1)}(i1:(i1+4)));p2=g(a,a{k1{i}(1)}(i1:(i1+4)),s1);fori2=1:size(k3,1)forj=1:size(k2,1)ifk3(i2}(1)==k2(j}(1)||k3(i2}(1)+1==k2(j}(1)||k3(i2}(1)-1==k2(j}(1)b=[s0];p=p1+p2;m1=k1(i}(1);fori3=1:4m1=m1-1;ifstrncmp(a{m1},'L',1)b=[b,'-',a{m1},'-',a{k1{i}(1)}(i1:i1+4)];endendm=k3(i2}(1);fori4=1:4m=m-1;ifstrncmp(a{m},'L',1)b=[b,'-',a{m},'-',s1,'',num2str(p)];ifall(strcmp(b,b1(size(b1,1),:)))||p>p0b=[];elseb1=[b1;b];p0=p;endendendendend

endendendendendifsize(b1,1)~=1disp(bl);break;end%转乘两次fori=1:size(k1,1)%确定线路fori1=k1{i}(2):6:size(a{k1{i}(1)},2)-4%确定站点k3=f(a,a{k1{i}(1)}(i1:(i1+4)));p1=g(a,s0,a{k1{i}(1)}(i1:(i1+4)));fori2=1:size(k3,1)%再次确定线路fori3=k3{i2}(2):6:size(a{k3{i2}(1)},2)-4%确定站点k4=f(a,a{k3{i2}(1)}(i3:(i3+4)));p2=g(a,a{k1{i}(1)}(i1:(i1+4)),a{k3{i2}(1)}(i3:(i3+4)));p3=g(a,a{k3{i2}(1)}(i3:(i3+4)),s1);fori4=1:size(k4,1)%确定线路forj=1:size(k2,1)%经过终点站的线路ifk4(i4}⑴==k2{j}(1)||k4{i4}⑴+1==k2(j}(1)||k4(i4}(1)-1==k2(j}⑴b=[s0];p=p1+p2+p3;m1=k1(i}(1);fori5=1:4m1=m1-1;ifstrncmp(a{m1},'L',1)b=[b,'-',a{m1},'-',a{k1{i}(1)}(i1:i1+4)];endendm2=k3(i2}(1);fori6=1:4m2=m2-1;ifstrncmp(a{m2},'L',1)b=[b,'-',a{m2},'-',a{k3{i2}(1)}(i3:(i3+4))];endendm3=k4(i4}(1);fori7=1:4m3=m3-1;ifstrncmp(a{m3},'L',1)b=[b,，-，,a{m3},，-，,s1,',num2str(p)];ifall(strcmp(b,b1(size(b1,1),:)))||p>p0b=[];elseb1=[b1;b];p0=p;endendendendendendendendendenddisp(b1);%子函数，搜索经过该点的线路%functionk1=f(a,n)%k1={};%fori=1:size(a,1)% k=0;% k=findstr(a{i},n);% ifk~=0% k1=[k1;[i,k]];% end%end%