数学建模优秀论文-公交最优路线换乘模型

公交最优路线换乘模型摘要本文主要针对大量观众到 2008 年奥运会现场观看奥运比赛的出行问题进行 分析，对出行面临的多条公交线路的选择问题进行剖析，对公交的转乘情况进行 了尽可能的详尽研究。在对人们的出行行为习惯和心理因素进行统计分析的基础 上，并结合实际建立可行的模型与算法。为公司开发解决公交线路选择问题的自 主查询计算机系统提供理论依据。首先，我们对附件中的公交信息数据进行处理，把数据换成统一的形式，即 每条线路均有上行线和下行线。然后，对各个问题分别进行建立模型和算法。针对问题一，我们采用了基于最小转乘次数和最短出行时间的公交网络拓扑 模型，本模型根据实际的调查分析，考虑两种判断标准：（1）建立一个以转乘次数最小为第一目标、以出行时间最短为第二目标和 以出行费用最少作为第三目标的模型与算法。在所有可到达的线路中选择转乘次数最小值 N，再选出满足条件的各条途经总站数 M ij 。并在此情况下找到出行时 间 t 最短的目标函数:t = mint j / t j = 5* N + 3*(Mij 1)，j=1,2L k) (分钟)。（2）在第一目标条件下考虑以出行费用最少为第二目标和以出行时间最短作为第三目标的模型。模型的算法采用了结构体的存储方式，便于数据的调用。 最后，根据算法编写程序并在计算机中运行，得出相应的结果。针对问题二：我们采用与问题一同样的思想来建立模型和算法，但由于地铁 信息数据与公交的不统一，模型和算法更加复杂。我们采用把相近的各公交车站（地铁站附近）看作一点来考虑。另外我们将地铁线路图绘制出来后，利用网络 拓扑和图论的相关知识进行求解，我们设计了此种情况的算法。针对问题三：我们主要考虑相近的不同站点间的步行时间，采用时间阻抗函(1)、S3359S1828转乘次数1最短时间106费用3(2)、S1557S048121123(3)、S0971S048511283(4)、S0008S00731832(5)、S0148S048521203(6)、S0087S36761652数最小为转乘的选择标准。 问题一结果：关键字：换乘次数拓扑模型数学描述最优公交路径时间阻抗函数 Dijkstra 改进模型43一、 问题的重述随着城市建设的飞速发展及公交系统的不断完善，公交车已成为城市居民出 行的主要交通工具。但由于城市公交线路四通八达，且随着城市扩建而快速发展， 新的公交线路在不断延伸和开辟，再加上单行道、禁左等道路交通约束，即使是 当地居民也不一定能找到到达目的地的最佳线路，外地游客更是难以获取公交出 行的路径信息。因此，在2008年奥运会来临之际，北京应建立适合于公交线路查 询特点的公交数据模型，开发操作直观、便捷、快速、准确的城市公交查询系统， 为出行者提供全面、准确的公交信息，帮助出行者快速地选择出行路径、换乘路 线等,提升出行者的效率,优化公交资源的配置,提高交通运输的效率和城市的信 息服务化水平。针对这种情况要求我们设计一个系统，其核心是线路选择的模型与算法，能 够从实际情况出发，满足查询者的各种不同需求。并解决以下三个问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模 型与算法。并根据附录数据，利用所建立的模型与算法，求出以下 6 对起始站 终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359S1828(2)、S1557S0481(3)、S0971S0485 (4)、S0008S0073(5)、S0148S0485(6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，建立任意两站点之间线路选择问 题的数学模型。二、 模型的假设条件1. 所有站点和路线的数据都是准确的；2. 相邻公汽站的行驶时间相等(包括停站时间)： 3 分钟；3. 相邻地铁站的行驶时间相等(包括停站时间)： 2.5 分钟；4. 公汽换乘公汽耗时相等：5 分钟(其中步行时间 2 分钟)；5. 地铁换乘地铁耗时相等：4 分钟(其中步行时间 2 分钟)；6. 地铁换乘公汽耗时相等：7 分钟(其中步行时间 4 分钟)；7. 公汽换乘地铁耗时相等：6 分钟(其中步行时间 4 分钟)；8. 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的 票价为：020 站：1 元；2140 站：2 元；40 站以上：3 元9. 顾客在车站等候各站车的时间相等，且仅考虑从起始站出发后开始计时，直到到达终点站所需时间；10.只考虑至多二次换乘的情况。 注：上述是模型假设讨论过程中的全局性假设，在后面的分布讨论中我们可能引 入新的全局性假设。三、 符号说明1. V（G）表示所有公交站点的集合；2. TR = TRi TRi (s0 , li1 , si1 , li 2 , si 2 ,L, sd )(i = 1, 2, 3L, n) ，是包含起点 s0 和终点 sd的可行公交路径集合；3. L = l jj = 1, 2,L, 520 为公交线路集合，各线路具有唯一编号；4. vij 表示第 i 线路上的第 j 站点；5. E(G)是所有道路边的集合；6. Z 表示出行区域的集合， Z = z1 , z2 ,L, zm m为区域数 ；7. li 表示一条公交线路；8. Pxy 表示一条公交路径，可记为 Pxy = i1 , l1 , i2 , l2 , i3 , i4 ,L, lk , i2 k 1 ；9. R = lkk = 1, 2,L, K 为线路-节点关系集合，称之为线路-节点描述；10.11.N i (自然数）：第 i 条途经换乘次数；M i (正整数）：第 i 条途经总站数；12. Wi表示路段阻抗，即平均换乘所需时间。注：此处的符号变量说明为全局性变量，具体的模型中设定的变量符号只具有局 部性。1 公交网络描述四、问题分析公交网络是由公交道路网络和相应的公交车线路网络组合而成。一般的公交 道路网络包括出行区域（起始站点和目标站点）、步行边、道路边和结点。当发生换乘时，步行边是指从下车站点到另一上车站点间步行的一段。公交道路网络 中的结点一般指道路交叉口和车站，在此为研究方便，结点仅指公交站点，而道 路边指有某条公交线经过的相邻站点间道路，是一个经抽象简化的概念。公交道路网用简单图 G 表示，而结点集 V（G）是所有公交站点的集合，边集 E（G）是所有道路边的集合。V（G）的基数为 n，即 V (G) = n ，表示有 n 个不同的公交站点。出行区域的集合定义为:Z = z1 , z2 ,L, zm m为区域数ij步行边的集合用 E 0 = e i, j (Z UV (G), i j 来表示。公交车线：Ri = k , n1 , n2 ,L, nvinvi V (G), vi为Ri 上的站点数,k (0,1, 2)(1)式(1)表示公交车线可从n1点出发依次经过n2，n3,，nvi-1，到达nvi点。如果 是环线，k=2；如非环线，双向，k=1；如非环线，单向，k=0。而由所有的公交车线形成公交车线网络X：X= Rii = 1, 2,L, N R , N R为网络中车线数，而对公交网络中的一条公交路径，可记为：Pxy = i1 , l1 , i2 , l2 , i3 , i4 ,L式中：, lk , i2 k 1i1 , i2 k 1 出行区域(2)l1 , l2 ,L, lk 车线有了以上的表述,再给出两条定义：定义 1设 I V (G) ，称 I 为基结点，由 I 出发经 k 次换乘可以到达的结点为 Il的第 k 层点。I 的第 k 层点的全体记为W k ；特殊的，若 I 到 j 有直达公交线路，则称 j 为 I 的第 0 层点(或直达点)。l定义 2称结点 I 到结点 j( j W k ) 经 k 次换乘的时间最短公交路径，为 I 到 j 的第 k 阶公交最短路径，其时间称为 I 到 j 的第 k 阶公交最短行程时间，记为:2 问题背景的理解与解决思想：t k (I , j) 。公交乘务问题的实质就是给出起始点、目标点后，给用户提供乘车方案。所 谓乘车方案是一个站点、线路的交替序列，该序列说明从起点出发乘坐何线路，可以直接到达目标点，或途中如何换乘，到达终点。在大部分的城市公交网络模 型中，公交线路的选择通常受到以下几个因素的作用：(1)换乘次数：是指乘客在完成一次出行过程中所换公交车的次数；(2)出行距离：则包括车上距离和车外距离，车外距离指的是乘客为了乘车 而步行的距离；(3)出行耗时：指乘客在一次出行过程中所需的时间，它也包括车上和车外部分，车外耗时除了在车外距离部分所耗的时间外还包括在车站等车的时间；(4)出行费用：指的是乘客在完成一次出行过程中所花的车费。 不同乘客对于各项因素的要求都是不同的。经调查，表明大多数乘客在选择公交 线路出行时, 首先考虑的是乘车是否方便, 就换乘次数而言, 一般不大于两次；其次是乘车所花费的时间是否最少， 由于各相邻站点间的行驶时间是相同的， 所以存在直达线路时，时间主要是通过公交线路的站点来衡量, 站点越少越好。 同时，由于换乘耗时的存在，当不存在直达线路时，要求换乘次数越少越好。因 此, 将“换乘次数最少”和“沿途站点最少”这两点作为设计最短路径数学模型 的优化目标。3 仅考虑公汽线路时的最佳路线选择根据人们的出行习惯，首先，看 A 站是否有公交车直接到 B 站。如果有一 条或多条直达公交线路，则从中优先输出线路距离最短的公交车，如图（1（a）。如果没有，则看经过 A 站的公交车和经过 B 站的公交车有没有交叉点，若有交叉点 C，则选择在交叉点 C 转车到达 B 站，如图（1（b）。如果经过 A 站的公 交车和经过 B 站的公交车没有交叉点，则先乘经过 A 站的某一路公交车到达某一站 C，看经过 C 站的公交车与经过 B 站的公交车有没有交叉点 D，若有，则在 D 站转车到达 B 站，如图（1（c）。另外，有可能存在多种两次换乘的方案， 如图（1（d）所示。此时，需要判断哪种方案距离最短，然后优先输出距离最 短方案。如果经过 C 站的公交车与经过 B 站的公交车没有交叉点，说明经过两次换乘还不能从 A 站到达 B 站，则需要三次换乘或三次以上才可到达目的地。 考虑到方案的实用性，我们认为转乘超过两次，即为失败方案，则停止搜索。CBBA A（a）（b）CD CDABABEF（c）（d）图 1 公交线路换乘示意图4 同时考虑公汽与地铁线路的最佳路线选择 在问题一条件的基础上，加入了地铁的线路信息，虽然我们已经通过 matlab将最优结果已经计算出来了，我们原以为只要将地铁的线路信息加到问题一的模 型和程序中，就可以计算出结果，但由于地铁线路信息的数据结构与公汽线路信 息的数据结构并不兼容，因此很难利用问题一的程序将起实现。为此，我们将地铁线路图绘制出来后，发现可以利用网络拓扑和图论的相关知识进行求解，来得 出结果。5 考虑步行时间的公汽、地铁最佳路线选择第一种方案：由于 Dijkstra 算法本身虽然是计算最短路径的最优算法，但当 我们的网络比较大时，其处理的速度则大大降低，我们通过改进 Dijkstra 算法， 以换乘次数最少为主要目标，同时将路径进行优化，以实现我们的目标。另一种方案是为了我们问题计算的方便性，同时是我们建立的目标函数的可 操作性，我们引入路段阻抗的思想，将我们的最小换乘次数最优通过相应惩罚因 子的处理转换为时间最优，来构造我们的目标函数。5.1 问题一1、数据的预处理：五、模型的建立与算法的实现首先将文本附件（1.1 公汽线路信息）导入到 Excel 中，并筛去线路中上行 或下行为空的信息。其次对于只有上行或下行的，将已有行反向复制成对应的下行或上行；对于环线的，其上行与下行的数据信息相同。第三步，将 Excel 已经处理好的数据导入 matlab，并将其组织为结构体数组 的形式，其数据结构如下：businamestyleplat1plat2其中，busi表示第 i 条公汽线路； 表示第 i 条公汽线路的名称；busi.style 表示第 i 条公汽线路的计费方式；busi.plat1 表示第 i 条公汽线路的上行站台列表；busi.plat2 表示第 i 条公汽线路的下行站台列表。data1 为 Excel 的导入数据，将其化为结构体细胞数组的程序为：p=1,2080;for i=1:2080pi = cell2mat(data1(i,:);end bus=1,520; for i=1:520busi = struct(name, p4*(i-1)+1, style,p4*(i-1)+2, plat1, p4*(i-1)+3,plat2,p4*(i-1)+4);end2、基于广度优先的公交换乘搜索算法 第一步：输人乘车的起始站点 A 和目的站点 B。第二步：经过起始站点 A 的公交线路存为 X(i) (i=1,2,3m,m 为正整数)。经过目的站点 B 的公交线路 Y(j) (j=1,2,3n,n 为正整数)。第三步：判断是否有 X(i)=Y(j)，将满足条件的存入 Z。若只有一条线路满足 要求，则该路线即为最优路线，输出结果；若有几条路线满足要求，则从这几条线路里找出最优路线，并将几条路线由优等到次等排序输出。第四步：将公交线路 X(i)所包含的公交站点存为公交换乘矩阵 O(i,u)(u=1,2,3,p,p 为正整数)，公交线路 Y(j)中所包含的站点存为公交换乘矩阵 P(j,v)(v=1,2,3,h,h 为正整数)。第五步:判断是否有 O(i,u)= P(j,v)，将满足条件的存人 W，若有一个站点满 足要求，该站点即为一次换乘的转站点。从 A 站点出发，在该站点换乘即可以到达 B 点。如有几个站点满足要求，则先分别求出每一个站点的距离最短的换乘方案，然后比较各换乘方案的距离，选择所有方案中距离最短的换乘方案即为最优线路，输出结果。第六步：将经过站点 O(i,u)的公交线路存为 R(k) (k=1,2,3,p,p 为正整数)。 公交线路 R(k)所包含的站点 G(k,t) (t=1,2,3,g,g 为正整数)扩充到公交换乘矩阵 O(i,u)中。第七步：判断是否有 G(k,t) = P(j,v)，将满足条件的存人 W，若 W 非空，则 站点 G(k,t)即 P(j,v)为从站点 A 到站点 B 的二次换乘站点，公交线路 X(i)，R(k)， Y(j)为换乘二次的最优路线，输出结果并结束运算。第八步：设定换乘次数的上界 N，然后可在不大于 N 次换乘的某次循环中 找到可行路径，若可行路径有多条，考虑综合因素最高的为最优路径并输出。以上步骤如果没有找到合适的公交线路，则输出“没有找到换乘次数不超过N 次的最优换乘方案”，结束运算。3、算法的改进：上述方法的局限性是：在 a 到 b 与 b 到 a 的站点相同的时候是正确的，没有 考虑上行线与下行线不同的情况，如果在 a 到 b 与 b 到 a 的站点不完全相同时， 上述算法就不适用了，所以我们的方法时，考虑上行线和下行线可能不同的情况， 这样得到从 a 到 b 的一次换乘线路有 4 种类型（c 为中间站点）：1) a 到 c 走上行线，c 到 b 走上行线；查找函数为（见附录）：n1,m1,m,n2,m2=ff2(bus,a,b)查找 a,b 的所有一次换乘的线路，返回值中 n1 为乘坐车次(上行)，m 为换乘站点，n2 为换乘车次(上行)。2) a 到 c 走上行线，c 到 b 走下行线；查找函数为：n1,m1,m,n2,m2=ff3(bus,a,b)查找 a,b 的所有一次换乘的线路，返回值中 n1 为乘坐车次(上行)，m 为换乘站点，n2 为换乘车次(下行)。3) a 到 c 走下行线，c 到 b 走上行线；查找函数为：n1,m1,m,n2,m2=ff4(bus,a,b)查找 a,b 的所有一次换乘的线路，返回值中 n1 为乘坐车次(下行)，m 为换乘站点，n2 为换乘车次(上行)。4) a 到 c 走下行线，c 到 b 走下行线；查找函数为：n1,m1,m,n2,m2=ff5(bus,a,b)查找 a,b 的所有一次换乘的线路，返回值中 n1 为乘坐车次(下行)，m 为换乘站点，n2 为换乘车次(下行)。这样能得到所有 a 到 b 的一次换乘线路。4、6 对起始站与终点站最佳路线的结果通过以上的改进算法，利用 matlab 运行所编写的程序，主要的实现函数及 其的功能如下：m=isup(bus,s1,s2)%判断 s1，s2 站点是否在同一个上行公交线路,如果有则返回线路的序号,其中 s1为起点。m=isdown(bus,s1,s2)%判断 s1，s2 站点是否在同一个下行公交线路,如果有则返回线路的序号,其中 s1为起点。n1,m1,m,n2,m2=ff2(bus,a,b)%查看站点 a,b 是否有一次换乘的线路，返回值中 n1 为乘坐车次(上行)，m 为换乘站点，n2 为换乘车次(上行)。n1,m1,m,n2,m2=ff3(bus,a,b)%查看站点 a,b 是否有一次换乘的线路，返回值中 n1 为乘坐车次(上行)，m 为换乘站点，n2 为换乘车次(下行)。n1,m1,m,n2,m2=ff4(bus,a,b)%查看站点 a,b 是否有一次换乘的线路，返回值中 n1 为乘坐车次(下行)，m 为换乘站点，n2 为换乘车次(上行)。n1,m1,m,n2,m2=ff5(bus,a,b)%查看站点 a,b 是否有一次换乘的线路，返回值中 n1 为乘坐车次(下行)，m 为换乘站点，n2 为换乘车次(下行)。d=dis(bus,line,s1,s2)%计算同一线路中两站点的距离,其中 s1,s2 分别为起终站点，line 为线路编号。根据我们的算法得到我们的结果：6 对站点中没有直达的线路，那么我们再 考虑换乘一次能到达目的站点，如果不行再考虑换乘二次，对于二次换乘以上的，考虑乘客的满意度，我们不做考虑。除了第 2 对和第 5 对需要换乘两次之外，其 余 4 对均可通过换乘一次到达目的站点。最佳路线如下：(1)、S3359S1828转乘次数1最短时间106费用3(2)、S1557S048121123(3)、S0971S048511283(4)、S0008S00731832(5)、S0148S048521203(6)、S0087S36761652关于最佳路线更详细的信息见表 1 到表 6：表 1 起始站 S3359目标站 S1828序号路线一转站点路线二耗时费用1L436S1784L16710632L436S1784L21710633L436S1241L16711234L436S1241L21711235L436S3695L2171183表 3 起始站 S0971目标站 S0485序号路线一转站点路线二耗时费用1L13S2184L41712832L13S992L41713133L13S2322L41713434L13S1770L41713435L13S1789L4171343表 4 起始站 S0008目标站 S0073序号路线一转站点路线二耗时费用1L159S400L4748322L159S2633L4748323L159S3053L4748325L159S2683L588325L159S291L58832表 6 起始站 S0087目标站 S3676序号线路一转站点线路二耗时费用1L454S3496L2096522L454S1893L209712表 2起始站 S1557目标站 S0481（需要转乘两次）：序号线路一转站点一线路二转站点二线路三耗时费用1L84S1919L417S2424L25411232L84S1919L417S2424L31211233L84S1919L417S2424L44711234L84S1919L417S2424L51611235L363S1919L417S2424L2541123表 5 起始站 S0148目标站 S0485序号路线一转站点一路线二转站点二路线三耗时费用1L308S36L156S2210L417117172L308S36L157S2480L41712033L24S345L140S2654L46913284L24S1487L378S2023L46913565L24S345L140S2654L10414185.2 问题二5.2.1 模型的建立： 由附件中的地铁线路信息，可以画出其对应的线路示意图BCA(D01)D12D18FED（D23）模型假设：图 2 地铁线路示意图1、我们只考虑线路最短为主要目标；2、此线路图形处在整个城市的中间位置；3、图形以内的任意两站点，不考虑换乘的情况；5.2.2 模型实现算法：第一步：将每个站点看作图形中的一个点，将处在多边形 ABCDEF 中（包 括线段上）的所有站点存入集合 V 中，即：vV = vij |存在于多边形ABCDEF之中ij第二步：对于要求的任意两点 a、b 之间的线路,a) 首先判断 a、b 是否属于集合 V，如果 a、b 两点同时属于集合 V，那么 我们就无需考虑换乘的情况，只要利用问题一中的求解算法找出它们之间的线路信息；b) 如果 a 属于集合 V，而 b 不属于集合 V，那么找出从 a 到最近的地铁站 点 c 的线路信息，找出从 b 到最近的地铁站点 d 的线路信息，那么 c、d 之间的 地铁线路也就相应的得到了，综合几条线路即可得出线路信息；c) 如果 b 属于集合 V，而 a 不属于集合 V，那么找出从 a 到最近的地铁站 点 e 的线路信息，找出从 b 到最近的地铁站点 f 的线路信息，那么 e、f 之间的地 铁线路也就相应的得到了，综合几条线路即可得出线路信息；d) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形 ABCDEF 的实线没有交点，那么此问题就可以利用问题一中的算法求出最短线 路信息；e) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形 ABCDEF 的实线有 1 个交点时，同样无需考虑换乘地铁，求解算法与 d)相同； f) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形ABCDEF 的实线有 2 个交点时且连线处于 AD 之上，我们也可以得出无需考虑 换乘地铁，求解算法与 d)相同；g) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形 ABCDEF 的实线有 2 个交点时且连线处于 AD 之下，那么我们就要求解与 a、b 最 近的地铁站点和地铁站点之间的线路信息最短；h) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形 ABCDEF 的实线有 3 个交点时且没有超过 BC 边与 EF 边，可以算出同样无需换 乘地铁，计算它们之间的最短线路信息；i) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形ABCDEF 的实线有 3 个交点时且没有超过 BC 边，但超出了 EF 边，那么就要考 虑换乘地铁，算法同 g)；j) 其它情况不做考虑，算法结束。5.3问题三5.3.1、 路径优化准则与行程时间描述 方案的可行性主要体现在乘客对其满意度，主要有两种表现形式：一种是总出行时间，另一种是乘客的出行总成本。目前乘客满意度中的两种形式，可以利用乘客的时间价值研究成果进行统一处理。在此为研究的方便，将主要考虑用公 交路径行程时间（包括步行时间、等车时间及车间时间）作为乘客满意度的度量。通过对公交乘客出行心理的调查研究，说明了出行者选用换乘次数最少作为首要优化目标，以出行耗时最少为第二重要因素，而出行距离最短为第三重要因素。 以上结论是对普通市民的出行进行调查得到的结果，是一般出行者对公交网络性能信息掌握不全面情况下而做出的择路要素排序。但是如果从公交查询服务 的角度来看，以出行耗时最少（耗时中包括出行费用的转化时间）为第一优化目标，以换乘次数最少为第二重要因素为宜。 某条公交路径的行程时间，是历经该公交路径所花费的时间。典型的公交路径行程时间包括从站点的等车时间、上车时间、行车时间（一般指车辆的行驶时间）、转乘时间、最后离开公交车线网的下车时间。这其中，转乘时间可进一步 细划分为下车时间、改变乘车点的步行时间、等车时间及上车时间。公交网络初始时间矩阵Tnn 定义为：0, i = jt = mint d/ d , t ,当i j, 且i到j有m条车线经过（3）ijk ijk ij，其他式中：m 车线条数，m1；tk 车线 k 的车辆全线行驶时间；dk 线路k的全线距离；dij i到j的实际距离,i与 j V (G )当车线为环线时,上面的公式要相应作出调整。同时，定义Qnn 为对应与Tnn 选择车线矩阵为： 0, i = jq k , k 是满足 mint d/ d , t 的k 值ij , 其他针对每一个 Ri 设立一个票价函数：k ijkij1， 0 u 20或v（v为单一票价）RiC = f (R ) =i2，20 u 40（4）3， u 4（0 u 表示途经站点数）同时建立公交网络的换乘步行时间矩阵 H nn 为：0, i = jhij = tij ,当i j, 其他（5）式中：tij 从 i 到 j 的步行时间；L由于实际问题的复杂性，可以先选择一个长度 Ln 做半径，以i点为圆心作圆， 将该圆覆盖区域内的公交站点设为i点的待定转乘站点，其构成集合O 。然后求RijLd ( j OijR) ，并用式 d R 判断j是否为选定转乘站点。所有选定的转乘站点构成集合Oi 。显然Oi至少包含元素i。利用票价函数以及Qnn 即可确定一个与Tnn 对应的 n 阶方阵Cnn ，其元素 cij表示从 i 到 j 沿 qij 线乘车的票价时间值。设公交网络中有NR 条不同的车线, 各个车线的发车间隔时间可以分别用t f1,t f2 ,L, t fNR 。考虑到发车间隔的确定性和乘客出行到达某站点的随机性，本f文采用ti/2 为在某站点选乘第i条车线的等车时间。5.3.2、 公交网络最优路径求解思路和步骤 新算法的求解过程可分为两个阶段。第一阶段分别求解与起始区域 r 以及终止区域 s 以步行边相接的公交站点集合 Or 与 Os 。判断 Or IOs 是否非空。如果Or IOs 非空，即有公共点存在，说明 r 与 s 间有步行边相接，可求解 r 与 s 间的行程时间。如果Or IOs 为空集，则进入第二阶段求解。依次取Or 中的点，求其与Os 中各点的最短行程时间和最优公交路径。结合与Or 及Os 中各点所对应的已记录的步行边行程时间，即可求出 r 与 s 间的最优公交路径、最短行程时间和换 乘次数。求解的具体步骤如下：a给定 R 值，建立初始化的步行时间矩阵 H nn 。建立包含等车时间的初始时间矩阵T 0 为：t o =nn 0，i =k min (tj/ 2 + t d/ d )，当i j且i到j有m条车线经过（6）ijfl k mk ijk ，其他同时建立与T 0对应的矩阵Q。按照给定的票价函数及Q建立换乘票价时间nn 的 n 阶方阵Cnn 。nn nn b求解与起始区域 r 相接的公交站点集Or ，记 Or= n r ；求解与终止区域 s以步行边相接的公交站点集Os ，记 Osk= ns 。如果Or IOs (表示空集），记kOr I Os= nrs ，Ors (Or IOs )，k = 1, 2,L, nrs )，求 r 到 s 经Ors 的两条步行边行程t 1 , t 2 , L, t n rs rs 时间之和 R k，可得rs rs r s，取其中最小者为trs（r 与 s 间最短行程时间），并可得相应的路径 (r s)i。如果 Or I Os= ，则转下一步。c.依次取出Or 中的公交站点Or 表示Or 中的第 i 个元素。按以下步骤求该点与Os中各站点间的最短行程时间、最优公交路径以及对应的换乘次数。(a) 建立 ns 维的数组 F 与Gt（置数组 F 元素初始值为，置数组Gt 元素初始值为 0）。F 记录最短行程时间，Gt 记录路径的换乘次数。建立 V (G) 个 20 维p的数组 R j (1 j n, 置数组元素初始值为0) 。这里的 20 维表示最多可以换乘 5 次，可作相应调整。建立 n 维数组 D（置数组元素初始值为 0）。D 中元素值表示所 选公交站点到对应的各站点的最优路径行程时间的判断结果，0 表示未达到有限 值，1 表示已达到非的值，2 表示已得到最优路径。ss ss(b) 依次取O 中的元素O j 表示O 中的第 j 个元素，1 j n 。按以下步骤求解Oi 与 V(G)中各点 v的最优公交路径、换乘次数及总的行程时间。r首先在T 0ki中找出 t 0的值t 0 。如果t 0 ，则说明Oi 与 v之间有公交nn O r v kr k线直达，行程时间记为t0 。数组 D 中与 vk 对应的元素 Dk 记为 1。令i j 0RvkpOkr= (r,Oi , qoi o j , O j , s, 0, 0,L, 0)其中 qor os 为与Tnn 中 t 0 对应的 Q中的车线。同时如果 v O 。则作如下改rr ssnn ks变： F= t 0 , G= 0 ， F 与G分别表示与 v点对应的数组 F 与 Gt 中的元素。k k kkk如果t 0 = ，则说明Oi 与O j 之间无直达公交线。如果 j = V (G) ，则令 N=0，r s转步骤；否则取 j=j+1，转步骤。依次取 D 中的元素 D j 先判断，后依不同情况分别进行计算。当 D j = 0 时t N +1 (oi , j) =mint N (oi , k) + h+ t0 (m, j) + crkW Ni .morkmmj(8)Oik r当式(8)的值小于时,令 D j = 1 ；建立新的jR i 为 (r, Oi ,L, k , m, q, j, 0, 0,L, 0) ，划线处为对原 R ki 以前值的末尾添加pOr的元素。rmjN +1 ipOrN +1当 j Os 时， Fj = t(Or , j)，G j = N + 1。当 D j = 1 时，仍按式(8)计算t 。j如果tN +1 i Fj ，则令 D j = 2 。建立新的 R pO 为 (r, Or ,Lir, k , m, qmj , j, 0, 0,L, 0) 划线k处为对原 Rip O r以前值的末尾添加的元素。当 j Os 时： F= t N +1 (Oi , j)，G= N + 1。如果t N +1 F ，则令 D = 2 。jrjjj当 D j = 2 时，取下一个 D j +1 进行如上的新的判断与计算，直到 j = V (G) 。检查 D 中与Os 中的点对应的值是否均为 2。如果有 0，1 存在，则令 N=N+1，转步骤如果对应值均为 2,则转步骤。这里的判定原则是建立在公交网络 G 连 通的假设之上。OB minr求 F1 中的最小值 Fmin ，记录对应 Fmin 的站点ss。得到Oi 到 s 的最优路r径为 R pO i 最短行程时间为 F mi n 转步骤 c，直到取遍Or 中的所有元素。d利用步骤 c 中求出的Or 中各点至 s 的最优路径、最短行程时间、换乘次 数，可以最终求出 r 到 s 的最优路径、最短行程时间及换乘次数。在上述计算过程中，当出现满足式(7)或式(8)的 k 有几个不同值时，可能会出现多条最优路径。处理的办法是相应增加对应的路径记录数组 Rp 的个数，以记录多条路径。同时，上述计算步骤也可以稍加修改，求解单起点多终点的公交 网络最优路径。5.3.3 基于阻抗时间最短的最优选择模型1、公交网络换乘类型分析 两条公交线路间的换乘按照换乘站点重合程度的不同，可以分为同站换乘与步行换乘两种。结合两线路位置关系的特点，又可进一步划分为下列四种类型：a)同站换乘类型 1(见图 3（a）)： 两条公交线路相交于一点,并在该点同时存在公交站点,乘客可在此站点进行直接换乘；b)同站换乘类型 2(见图 3（b）)： 两条公交线路拥有一部分重合的路段(即公交线路“共线”的情况)，在重合路段的公交站点上，乘客可进行两线路间的直接换乘;c)步行换乘类型 1(见图 3（c）)： 两条公交线路相交于一点，但在该点不同时存在公交站点，乘客需要步行在两线路距离较近的车站间进行换乘。该换乘类型多见于城市道路大型交叉口附近的车站；d)步行换乘类型 2(见图 3（d）)： 两条公交线路不直接相交,但两线路上有相距较近的公交站点,乘客可以在这些站点间通过步行进行换乘,该类换乘多存在于相距较近的平行街道上运行的公交线路之间。a)同站换乘类型 1b)同站换乘类型 2c)步行换乘类型 1d)步行换乘类型 2站点：线路 1：线路 2：步行路段： 图 3 两条公交线路间换乘类型示意图上述四种换乘类型是两条公交线路间最基本的换乘类型,公交网络中更为复 杂的换乘关系均可归结为这四种换乘类型的组合或扩展。2、路径选择中的换乘识别方法 通过前述对公交网络中基本换乘类型的分析可以看出，当乘客在出行中经过某一站点时，如果在站点前一路段与站点后一路段上所乘坐的公交线路发生了变化，或者在公交方式与步行方式之间发生了转换，即可认 Ai 为乘客进行了换乘。为了便于在路径选择算法中有效地识别换乘，可以将换乘所带来的时间损失和不 方便程度体现在路段阻抗上。不妨采用如下函数形式表示路段阻抗：Wi = gTi + gTe其中，Wi 为路段 i 的阻抗值；Ti 为路段 i 的走行时间；Te 为平均换乘时间； 为步行惩罚因子； 为换乘惩罚因子。在下列情况下, 取相应的换乘惩罚值Ct ，表示乘客在路径选择中发生了换乘：a)路段 i 为公交路段，前一路段 i-1 为步行路段,同时路段 i-1 不是出行路径中 的第一条路段；b)路段 i 的公交线路集合 Ri 与前一路段 i-1 的公交线路集合 Ri 1 的交集为空；其他情况 取值为 0,表示没有发生换乘。路段走行时间Ti 可以根据路段长度和城市公交平均运营速度及乘客步行平均速度综合计算。步行惩罚因子 则通过判断路段i 是否为步行路段取值，如果 路段 i 为步行路段,则 取相应的步行惩罚值Cw ，如果为公交路段,则 取值为 1。步行惩罚值Cw 与换乘惩罚值Ct 应大于 1,它们反映了步行时间和换乘时间对整个公交出行时间的贡献程度。3、模型的构造 在问题一模型的基础上，我们将地铁的信息也考虑其中，进行建模。 乘客在公汽与地铁之间进行换乘，起平均的换乘等待时间设为Te ；e1 表示在这段出行路线中，公汽换乘公汽的次数；e2 表示地铁换乘地铁的次数；e3 表示地铁换乘公汽的次数；e4 表示公汽换乘地铁的次数。由此，我们可以得出Te 为：Te = 3e1 + 2e2 + 3e3 + 2e4在此路线上的走行时间设为Ti ，那么可以得出：Ti = 2e1 + 2e2 + 4e3 + 4e4Wi 表示路段阻抗，即平均换乘所需时间，由换乘识别算法Wi 可以表示为：Wi = gTi + gTe乘客在线路上的乘车消耗时间用 Si 表示；(1) (2)(3)由于地铁站点中的信息是由公汽站点所构成，所以我们可以将地铁站点转换 成相应的公汽站点来表示，这样无疑简化了我们的模型，用 n 表示该路径所经过的所有站点数，那么乘客在线路上的乘车消耗时间 Si 可以表示为：S = 3 + 2.5 n = 2.75n(4)i 2为计算的方便性，其中的 3 + 2.5 表示相邻公汽站与地铁站之间平均行驶时间。2用Ti 表示乘客在从起始站到目的站所花费的总阻抗时间，由以上（1）、（2）、（3）、（4）式可以得到目标函数：Ti = 0.8 Wi + 0.2 S i（5）六、模型的评价1 .数据的处理，采用数据处理技术对数据进行统一化（即每条线路均有上行 线和下行线）便于后面程序的实现。此方法在实际中起着至关重要的作用，因为 在大多数情况下，数据的形式可能是不符合我们的需要，只有通过对其进行处理 成我们需要的形式才有用。2.针对问题一，根据实际的调查分析，考虑两种判