《公交线路选择系统优化模型》由会员分享，可在线阅读，更多相关《公交线路选择系统优化模型（6页珍藏版）》请在金锄头文库上搜索。
1、1公交线路选择系统优化模型摘要本文解决的是一个公交线路选择问题，在分析城市公交网络的基础上，提出公 交体系中最优公交乘车算法 ，目的是系统通过选择最少换乘数的情况下，以站数尽可能少来确定最佳路径， 使得乘车的时间和费用最小。 对于问题一，在如下的最小换乘数算法中解决换乘最少的方案。 对于问题二，是在上问的基础上再增加路线节点约束条件来实现最优路线选择。对于问题三，在问题一的模型基础上，综合考虑步行时间和票价的情况下引入 了票价的时间价值概念，选出最优路径。 关键词：路线选择，换乘，最佳路径，公交网络，时间价值2一、问题提出背景：2008 年奥运会将在北京举行，届时将有大量观众乘做公交车去看比赛
2、。 可行的乘公交车方案一般有多，出行者必须做出选择，而出行者考虑的因素很多， 如换乘次数、旅行时间，等公交时间的不确定性和费用等，不能简单的抽象为最短 问题，研究表明，乘客对途中换车比较敏感，一般出行者以换乘次数为优先考虑的 目标，因此本文以最小换乘次数为第一目标，另外，旅行时间也是乘客很关心的问 题，而旅行费用的计算方式较多，但一般而言所需时间、费用都与途径的站数正相 关，为避免过于复杂，本文选择最小途经的站数第二目标。即：在所有可行路径中 选择换乘数最小，且在满足此目标条件下使途经站数最少的路径为最优路径二、符号约定G(V,P,R,L)来表示公交网络V=vi | i=1,2,-,n为节点集
3、合，包括交通网络中所有的公交站点或可能的出行起讫点，对各节点给定唯一编号。P=pi | i=1,2,-,k为公交线路集合，各线路具有唯一编号。R=rk | r=1,2,-,k为线路-节点关系集合，称之为线路-节点描述。由所包含的站点按通过顺序构成的节点有序序列表示。如第 k 条线路：rk=,其中 vk1,vkmk是该线路的始发、终点站L=lj | j=1,2,-,n为节点-线路关系集合。L 是由节点角度建立的节点-线路描述。如lj = pj1,pj2,-,pjtj为所有经过节点 vj的线路编号集合。若 Ij =,表示无线路经过该节点。Cij=cijk*kp 为线路相交矩，其中cij=1 (若
4、ri,rj 有公共节点),否则为 0Tp 公交票价的时间价值，M 票价 n 经过的站点数。Ei,j 为 ij 直达线路数 n,即 Ei,j=n(ij,)，Ei,j=0(i=j) 三、模型假设 3由于该问题涉及公交及地铁网，我们需要对公交及地铁网作必要的假设： (1) 相临公交站点之间的距离相等； (2) 相临地铁站点之间的距离也相等; (3) 假设在公交站点以及地铁站点不发生堵车，乘客均可以上车 (4) 居民人均收入为 8000 元 (5) 法定工作天数为 260 天 模型分析与模型建立： 公交乘车问题的一般模型为，设给定起点 vo 和讫点 vd，可 行的公交路径集合为 TR=TRi | TR
5、i=,Tri 表示在起点 vo 选 择线路 pi1 到达 vi1,换乘 pi2 到达 vi2，-，最终到达 vd,该路径换乘次数 Ni，途经 总站数 Si。 出行者的目标函数为： maxU Ni, Si TRi目标函数性质: U Ni 0, U Si 0, U Ni U Si 最优公交乘车算法最优乘车路径的搜索算法设在公交网络上任给起讫点vo,vd 可达，需要确定最优乘车方案。首先需要确定换乘次数上界 TN,然后根据 G(V,P,R,L)按换乘次数递增进行搜索，算法必在不大 于 TN 次换乘的某次循环中找到可行路径，若可行路径有多条，寻找总站数最小的 为最优路径并输出。 算法步骤：step1:
6、输入起讫点vo,vd,确定换乘次数上界 TNstep2:判断直达线路是否存在如果lold，则有直达路线，计算各路线站数，最小者即最优路径，转 step4.否则，继续 step3：令 A0=lo,i=0; step4:若不存在 i 次换乘的可行路径，搜索 i+1 次换乘可行路径根据线路相交矩阵，寻找U A A j j= =与 Aj 中任一线路相交的线路集合 Ai+14if Ai+!ld，则有可行路径，对每一可行路径，回溯确定线路序列，计算每一可行路径的总站数。 确定总站数最小的为最优路径。 转 step5 否则，i:=i+1，重复执行 4 step5:根据最优路径上的线路序列确定换乘方案，结束。
7、 在该算法中确定换乘次数上界，及根据线路序确定换乘方案两个问题在下面讨 论。 换乘次数上界的动态规划解法 对一对起讫点必须首先确定其换乘数上界，设某对起讫点有某可行路径 TRk,其 途经站点数最少即 Sk=min(Si)，其换乘次数为 Nk，因此可以用途经站数最小的路径 的最小换乘次数的上界。求两节点之间最小途经站数路径的问题可以转为求最短问 题，有成熟的算法。假设已求得，则需求该路径的最小换乘次数。 对某路径可能有多种换乘方式，导致换乘次数不同，而最小换乘问题满足动态 规划最优化原理，因此设计了动态规划的逆序算法。算法的基本思想是：首先寻找 能经过该路径直达讫点的节点区间（0 次换乘节点区间
8、） ；对该区间中的任一节点寻 找能够经过该可行路径直达迄点的节点区间（0 次乘换节点区间） ；对该区间的任一 节点寻找能够经过该可行路径直达该节点的最接近起点的出发节点，比较所有出发 节点得到一个最左侧的出发节点，则位于该出发点和 o 次换乘节点区间左边界（不 含）的所有节点到讫点的最小换乘数为 1（一次换乘节点区间） ；对一次换科节点区 间过行类行类似操作，得到二次乘节点区间，依次进行，直到出现以起点为出发节 点，算法结束。设某可行路径的节点序列为：,vk1=vo,vkn=vd,不失一般性设序列中的节点脚标按 k1,k2,-,kn 自然顺序排列。其中某节点的最长公共线路节点 是指在该可行路径
9、上至少存在一条公交线路可以直达该节点的最接近起点的节点。 最小换乘次数算法步骤: Step1:初始化，换乘次数 TN：= 0确定vkn 的最长公共线路节点vklnif ln = 1 then 结束else 节点区间边界 ML :=ln, MR :=n;Step2:临时变量 ml:=ln-1for iML,MR do5if lkilk,l-1 = 确定公共线路节点vkliif li = 1 then 结束ml :+min(ml,li)end for TN := TN +1; Step 3: MR: = ML, ML :=ml 转 Step2 算法结束。 子例程：确定 vki 最长公共线路节点 v
10、ki step1:初始化，公共线路集合 C:=Lki, Lki 根据四元组 G(V,P,R,L)得到。 Step2: for j = i -1 to step -1 doC :=CLkjif C= 转 Step3 end for Li :=1 结束 Step3:li := j+1算法结束。 确定上界，还可以有第二种方法，即引入直达矩阵。可以证明可以表示为通过(n-1)换乘从节点 ij 的路径数。四、模型的解决 问题一：根据建立的模型，将 S3359S1828 输进去可以得到几条线路，如下： 1在 L469(上行)上车直到 S0519 站下，换乘 L167（下行）至 S1828 2在 L469(
11、上行)上车直到 S2364 站下，换乘 L217(下行)至 S1828 3在 L436(下行)上车直到 S1241 站下，换乘 L167(下行)至 S1828 4在 L436(下行)上车直到 S1784)站下，换乘 L167（下行）至 S1828 利用动态规划算法得出最佳路径为第 4 条。同理将 S1557S0481 输入得最后的路线为：在 L457(下行)上车在 S1920 换 乘 L009(下行)在 S2211 下车换乘 L157(上行)在 S2361 下车换乘 L312(下行)S0481 下将 S0971S0485 输入得最后的路线为：在 L013 上车在 S0485 换乘 L4176至
12、终点站 S0485将 S0008S0073 输入得最后的路线为：在 L043 上车在 S3180 换乘 L170 至终点站 S0073将 S0148S0485 输入得最后的路线为：在 L024 上车在 S3923 换乘 L008 在 S2265 换乘 L104 至终点站将 S0087S3676 输入得最后的路线为：在 L454 上车在 S3496 换乘 L209 至终点站问题二:将公汽与地铁综合起来考虑，乘客可以成公汽到地铁站换乘地铁或在地 铁站换乘公汽到达目的地。 将 S3359S1828 输入得最后的路线为:在 L015(上行)上车在 S0464 下车换 乘 D21 至 D29 处换乘 L
13、97 S0630 至终点 将 S1557S0481 输入得最后的路线为：在 L363(下行)上车在 S0385 下换 乘 D7 至 L28 处换乘 S1776 至终点 将 S0971S0485 输入得最后的路线为：在 L013 上车在 S0485 换乘 L417 至终点站 S0485 将 S0008S0073 输入得最后的路线为：在 L043 上车在 S3180 换乘 L170 至终点站 S0073 将 S0148S0485 输入得最后的路线为：在 L436（下行）上车在 S4752 处下换乘 D19 至 D27 处换乘 S2681 至终点 将 S0087S3676 输入得最后的路线为：在 L
14、454 上车在 S3496 换乘 L209 至终点站问题三：知道了所有站点间步行所需时间，根据假设得 Tp=n*M*480*260/8000 ，在利用算法选择路径时将 Tp 考虑进去 即的最佳路径。五、模型评价 本文分析了一般公共交通的特点，建立了以换乘次数最小为第一目标，途经站 数最小为第二目标的最优公交出行路径模型，第三个问题的模型没考虑当乘客可以 走小路的情况。该模型设计过于理想化，想要软件实现还有待于进一步改进。六、参考文献 李国勇 最优控制理论及参数优化 国防工业出版社 page118-121 东南大学学报 第 34 卷第 2 期 2004 年 3 月杨启帆 何勇 谈之奕 数学建模竞赛 浙江大学出版社 page79-80
