公交最优乘车路径模型

1、北京市公交最优乘车路径选择的数学模型摘要2008年8月，奥运圣火将在北京点燃。盛大的奥运赛事聚焦了全世界人民的目光， 明年的北京将绽放最绚丽的光彩。届时，客流量将会大幅上升，环境、交通、城市建设 都将面临很大考验。怎样才能更好的解决奥运期间市民和游客的出行问题呢？针对这样 的实际问题，我们设计了一个城市公交线路的自主查询系统，建立了关于城市公交最优 乘车路径选择的数学模型和算法，巧妙的运用Java语言编写程序，解决了现实生活中 乘车路径选择的问题。针对问题1，在只考虑公汽线路时，首先求出起始站和终到站所有公交线路集合的 交集，若此交集为非空交集，则选择所有直达线路中途经站点数最少，即花费最少的

2、线 路出行；若交集为空，选择起始站附近的站点，求出此站和终到站所有公交线路集合的 交集，若为非空交集，则可选择换乘一次的方法出行；否则，换乘两次，换乘三次 直到找到换乘N次的乘车方案为止。存在多条乘车线路时，考虑途经站点最少的乘车方 式。在此基础上，通过运用Java语言编程，确定了所需的最优乘车路径：（1）乘坐L436路公交车从S3359到S1784站，在S1784站换乘L167或L217路到 S1828站，全程换乘一次，耗时101分钟，乘车费用为3元；（2）乘坐L84路公交车从S1557到S1919站，在S1919站换乘L189到S1402站，在 S1402换乘L460到S0481站，全程换

3、乘两次，耗时112分钟，乘车费用为3元；（3）乘坐L13路公交车从S0971到S2184,在S2184站换乘L417路到S0485站，全 程换乘一次，耗时128分钟，乘车费用为3元；（4）乘坐L43路公交车从S0008到S1383,在S1383站换乘L282路到S0073站，全 程换乘一次，耗时113分钟，乘车费用为3元；（5）乘坐L308路公交车从S0148到S0302，在S0302站换乘L427到S2027站，在 S2027站换乘L469到S0485，全程换乘两次，耗时118分钟，乘车费用为3元；（6）乘坐L454路公交车从S0087到S3469，在S3469站换乘L209路到S3676站

4、， 全程换乘一次，耗时65分钟，乘车费用为2元；针对问题2,要求同时考虑公汽线路和地铁线路，在同一地铁站对应的任意公汽站 间可免费换乘，利用问题1的思想建立数学模型，运用Java语言编程，得到同时考虑 公汽和地铁时的最优乘车路径：前五对起始站一终到站的最优乘车路径的选择与问题1 一致。而起始站S0087到终到站S3676可通过选乘T2地铁线路直达，耗时25分钟，费 用为3元。针对问题3,鉴于问题1和问题2都是基于能乘车就不选择步行的出行方式建立的 模型，故没有在真正意义上满足乘客出行的各种不同需求。如起始站到终到站需经过21 个站点，且按分段计费的方式计价，那么对以费用为主要考虑因素的顾客而言

5、，他将会 选择在第20站的位置下车步行抵达目的地，这样即可节省一元钱的费用。关键词最优乘车路径换乘次数Java编程一、问题重述明年，第29届奥运会将在我国首都举行，明年的北京将成为全世界的焦点。为了 能身临其镜的享受奥运的精彩赛事，来自各个国家的观众都将于明年相聚北京，相约奥 运。与此同时，北京市的客流量将大幅提高，交通成为了众人关心的首要问题。如今， 虽然城市的公交系统有了很大发展，仅北京市的公交线路就已超过800条，但要很好的 解决奥运期间市民和游客的出行问题，仅仅靠增加公交车的线路是远远不够的，最重要 的是要帮助民众选择一条既省时又省钱的最优乘车路径，使得大家在奥运期间的出行畅 通无阻。

6、从城市的实际情况出发，为了满足大家的各种不同需求，设计一个城市公交线路的 自主查询系统，帮助出行者快速地选择出行路径、换乘路线等，解决以下几个问题：1、仅考虑公汽线路，当给出任意两个公交站点时，怎样才能很快找到连接两个公交站 点之间的最优乘车路径呢？如果已经给出以下6对起始站一终到站，通过清晰的分析说 明，并建立数学模型和算法，帮助出行者选择出最佳的出行方式。(1) S3359-S1828(2) S1557-S0481(3) S0971-S0485(4) S0008-S0073(5) S0148-S0485(6) S0087-S36762、同时考虑公汽线路和地铁线路，解决上面的问题。3、假设知

7、道所有站点之间的步行时间，给出任意两个站点之间线路选择问题的数学模 型。二、问题分析如果已经获取起始站A和终到站8的相关信息，需要确定从A到B的最优乘车路 径，我们可以这样分析讨论：首先，求出经过起始站A和终到站B的所有公交线路的集合，求这两个集合的交集， 如果为非空交集，则存在直达线路，可优先选择直达线路乘车。若存在多条直达线路， 应考虑途经站点最少或花费乘车费用最少的乘车方式出行。如果交集为空集，则可选择与A邻近的某一线路上的站点C，求出经过C站的所有 公交线路的集合与经过B站的所有公交线路集合求交集。若为非空交集，则可选择换乘 一次的方法出行。否则，可依次类推，换乘两次，换乘三次直到找到

8、换萩次的乘 车方案为止。如果每种乘车方式都存在多条乘车线路时，同样我们应考虑使途经最少站 点或花费最少乘车费用的方法出行。针对问题1，在仅考虑公汽线路时，只要使换乘次数最少、途经的公交站点数最少， 乘车费用即可降到最低，所选择的路径便可达到省时或省钱的目的。针对问题2,在问题1的基础上综合考虑公汽线路和地铁线路。因在同一地铁站对 应的任意公汽之间通过地铁站进行公汽的换乘而无需支付额外的地铁费用，可将经过地 铁站换乘的所有公汽站点的公交线路都考虑在集合之内，忽略通过地铁站转乘公汽在路 上所耗费的时间，进行模型的建立和求解。针对问题3,鉴于问题1和问题2都是基于能乘车就不选择步行的出行方式建立的

9、模型，故没有在真正意义上满足乘客出行的各种不同需求。例如起始站到终到站需经过 21个站点，且按分段计费的方式计价，为了节省乘车费用，一些乘客会选择在第20站 的位置下车步行抵达目的地，这样即可节省一元钱。按照这样的思维模式，如需在第22 站下车，选择在20站下车步行至目的地的方法乘客同样可以接受。依次类推，随着步 行站点的增多，选择此方法的乘客将会越来越少。因此，对分段计价的公交线路，站点 数目在20-40之间或在40个以上的站点进行加权。三、模型的建立和求解模型I模型假设1、当任意两站之间存在多条公交线路时，我们一般考虑选择换乘次数最少的公交线路出行，当存在多条这样的路线时，我们则选择途经站

10、点数最少的路线；2、假设城市交通运行正常，不考虑交通拥堵的情况；3、假设在能乘车的情况下就不选择步行的出行方式。符号说明S(A):经过起始站A的所有公交线路的集合；S(B):经过终到站B的所有公交线路的集合；A.:经过起始站A的第i条公交线路；气：经过起始站A的第i条公交线路的第j个站点；5(A):经过起始站A的第i条公交线路的第j个站点的所有公交线路的集合；A(i, j)：经过起始站A的第i条公交线路的第j个站点的所有公交线路的集合的第u条 公交线路；A(i, j)v :经过起始站A的第i条公交线路的第j个站点的所有公交线路的集合的第u条 公交线路的第v个站点；5(A(i, j)uv):经过

11、起始站A的第i条公交线路的第j个站点的所有公交线路的集合的第u条公交线路的第v个站点所有公交线路的集合；x :从起始站A到终到站B的公交线路上，途经的所有公交站点的数量(包括起始站和 终到站)；J当k = 0时,七表示从起始站直达终到站时，途经的所有公交站数；，K: i当k 0时,表示从第(k -1)次换乘到第k次换乘途经的所有公交站数。(包括起始站和终到站)；Mk :实现换乘N次的第k次到第(k + D次换乘所花费的乘车费用；单位：元(其中第N +1站表示终到站)注：其中N 0，k g 0,N，i, j,u, v均为正整数。模型的建立1、根据题目所提供的信息，实现N次换乘的算法如下:获取起始

12、站A和终到站B；求出经过起始站A的所有公交线路的线路集S(A)和经过终到站B的所有公交线路的线 路集S (B);求S(A) c S(B),如果S(A) c S(B)秘，则结束运算，输出结果；如果S(A) c S(B) = ，则继续下一步运算；顺序取出集合S (A)中线路A.,分别取出A,中的第j个站点气，求出经过第j个站点 的所有公交线路的线路集S(A )；ij求算S(*) c S(B)的结果，如果S(A ) c S(B)更，则结束运算，输出结果；ij如果S(A ) c S(B) = ，则继续下一步运算；ij顺序取出集合S (*)中线路A(i, j)，分别取出A(i, j)中的第v个站点A(i

13、, j)，求出 经过第v个站点的所有公交线路的线路集S(A(i, j)；求 S(A(i, j) ) c S(B)，如果S(A(i, j)v) c S(B)耕，则结束运算，输出结果。如果S(A(i, j) c S(B) = ，则继续下一步运算。依次类推，直到找到经N次换乘后从起始站到达终到站的公交线路为止。2、实现N次换乘的公交线路所耗费时间就等于公汽在各个站点之间行驶的总时间与换 乘公汽所耗费的总时间的和，即T = 3 x(x -1)+ 5 x N3、实现N次换乘的公交线路所花费的乘车费用的函数可表示为：M =歹 M ( k 0 )k=0当公汽采用单一票价方式收费时，Mk即为乘车的实际票价；当

14、公汽采用分段计价方式收费时，Mk为一个分段函数；当（七1） 20 时,Mk= 1；当20 （y -1） 40时,M = 3;1 kk（四）模型的求解在已经建立的数学模型和算法的基础上，运用Java进行编程（程序见附表），输出 结果后经过简单筛选处理，得到部分可行路线如下表所示，表中的黑体部分为最优乘车 路径：起始站f终到站换乘次数（次）耗费时间（分钟）途经公 交站点数换乘站点名称乘坐线路费用（元）乘车 时间换乘 时间S33591241L4363196532S1784L436L167 或L21731132544S0304L46931135545S0519L4694S15

15、57S048121471049S0028L84421561052S0029L84421651055S0029L84421321044S0978L84421131138S0978L84621081036S1919L84321021034S1919S1402L84L189L4603S0971S04851126542S992L1331123541S2184L13 L41731144548S0872L1193S0008S00731132544S1064L2941108536S1383L43 L2823S0148S048521531051S0345S0993L240325S21

16、84L240345S0872L24L119421201040S0345S3037L24 L140321141038S1487S2023L24L378321111037S1487S2027L24L378321081036S0302S2027L308L427L4693S0087S3676160520S3496L454L2092166522S1893L454L2092注：换乘站点和乘坐线路依次向下。模型II（一）模型假设1、当任意两站之间存在多条公交线路时，我们一般考虑选择换乘次数最少的公交线路 出行，当存在多条这样的路线时，我们则选择途经站点数最少的路线；2、假设城市交通

17、运行正常，不考虑交通拥堵的情况；3、假设在同一地铁站对应的任意两个公汽站之间进行换乘时，可将地铁站作为两公汽 站的连接通道，无需再支付额外的地铁费用；4、在同一地铁站对应的任意两个公汽站之间进行换乘时，不考虑在换乘过程中步行所 耗费的时间；5、假设在能乘车的情况下就不选择步行的出行方式。（二）符号说明E（A）：可通过地铁免费到达起始站A的所有公交站点的集合；E（B）：可通过地铁免费到达终到站B的所有公交站点的集合；S（A）：经过E（A）中站点的所有公交线路的集合；S（B）：经过E（B）中站点的所有公交线路的集合；A.:经过S（A）中的第，条公交线路；A,:经过S（A）中的第，条公交线路的第j个

18、站点；E（A）:可通过地铁免费到达气的所有公交站点的集合；S（4）：经过E（A）中站点的所有公交线路的集合；x :在所确定的乘车线路中，经过的公汽站点的数量；1x :在所确定的乘车方式中，经过的地铁站点的数量；2X :在所确定的乘车方式中，公汽换乘公汽的次数； 3X :在所确定的乘车方式中，地铁换乘地铁的次数； 4X :在所确定的乘车方式中，地铁换乘公汽的次数； 5X :在所确定的乘车线路中，公汽换乘地铁的次数； 6J当k = 0时,七表示从起始站到终到站途经的所有公交站数yk: i当k。时，表示从第a次换乘到第k次换乘途经的所有公交站数vk（包括起始站和终到站）；Mk :针对公汽换乘而言，从

19、第k次换乘到第（k + D次换乘所花费的乘车费用；单位： 元注：其中N 0，k g 0,N，i, j均为正整数。（三）模型的建立1、根据题目所提供的信息，实现N次换乘的算法如下：1）获取起始站A和终到站B ；2）求可通过地铁免费到达起始站A的所有公交站点的集合E（A）和可通过地铁免费到达终到站B的所有公交站点的集合E（B）；3）求出经过E（A）中站点的所有公交线路的集合S（A）和经过E（B）中站点的所有公交线路的集合S（B ）；4）求S（A）c S（B），如果S （a） S（B）8，则结束运算，输出结果；如果S（A） S（B）= 8，则继续下一步运算；5）顺序取出集合S（A）中线路A，分别取出

20、A中的第j个站点A，求可通过地铁免费iiij到达A的所有公交站点的集合E（A）；6）求出经过Eq）中站点的所有公交线路的集合S（A）；7）求S （a.）n S（B），如果S （a.）n S（b） 更8，则结束运算，输出结果；如果S a）n S（B）= e，则继续下一步运算；8）依次类推，直到找到经N次换乘后从起始站到达终到站的公交线路为止；2、实现N次换乘的公交线路所耗费时间就等于公汽在各个站点之间行驶的总时间、公 汽换乘公汽所耗费的总时间、地铁换乘地铁所耗费的总时间、公汽换乘地铁所耗费的总 时间、地铁换乘公汽所耗费的总时间和地铁在各个站点之间行驶的总时间的和，即T 3（x - x ） + 2

21、.5（x -1） + 5x + 4x + 7x + 6x ；3、实现N次换乘的公交线路所花费的乘车费用为乘坐公汽的费用与乘坐地铁的费用， 则费用的函数可表示为：M =少 M + 3 （ k 0）k=0当公汽采用单一票价方式收费时，Mk即为乘车的实际票价；当公汽采用分段计价方式收费时，Mk为一个分段函数；当（七一1） 20 时,Mk= 1；当20 （y -1） 40时,M = 3;v kk（四）模型的求解在已经建立的数学模型和算法的基础上，运用Java进行编程（程序见附表），输出 后的结果经简单筛选处理，得到部分可行路线如下表所示，表中的黑体部分为最优乘车 路径：起始站f终到站换乘次数（次）耗费

22、时间（分钟）途经公 交站点数换乘站点名称乘坐线路费用（元）乘车 时间换乘 时间S33591241L4363196532S1784L436L167/ L21731132544S0304L46931135545S0519L4694S1557S048121471049S0028L84421561052S0029L84421651055S0029L84421321044S0978L84421131138S0978L84621081036S1919L84321021034S1919S1402L84L189L46031126542S992L133S0971S04851123541

23、S2184L13 L41731144548S0872L11931132544S1064L294S0008S00731108536S1383L43 L282321531051S0345S0993L240325S2184L240345S0872L24L1194S0148S048521201040S0345S3037L24L140321141038S1487S2023L24L378321111037S1487S2027L24L378321081036S0302S2027L308L427L4693S0087S3676025010/T23注：换乘站点和

24、乘坐线路依次向下。模型III鉴于问题1和问题2都是基于能乘车就不选择步行的出行方式建立的模型，故没有 在真正意义上满足乘客出行的各种不同需求。例如起始站到终到站需经过21个站点， 且按分段计费的方式计价，为了节省乘车费用，一些乘客会选择在第20站的位置下车 步行抵达目的地，这样即可节省一元钱。按照这样的思维模式，如需在第22站下车， 选择在20站下车步行至目的地的方法乘客同样可以接受。依次类推，随着步行站点的 增多，选择此方法的乘客将会越来越少。因此，对分段计价的公交线路，站点数目在20-40 之间或在40个以上的站点进行加权。四、模型的优缺点根据题目所给信息进行了合理假设，问题的分析由简到难

25、；从仅考虑公汽线路的乘 车方式入手，进一步综合考虑公汽线路和地铁线路，最后再加入步行时间，模型层次结 构清晰；巧妙的运用了 Java语言编程，从而得到了最优乘车路径的选择方案；鉴于问 题1和问题2都是基于能乘车就不选择步行的出行方式建立的模型，在模型III中考虑了 此因素，在真正意义上了满足乘客出行的各种不同需求。但是，由于没有考虑到现实生 活中可能出现交通拥堵等类似的客观原因，从而使得乘车时间有所延长。参考文献1印旻，Java与面向对象程序设计教程，北京：高等教育出版社M, 1999年。2Bruce Eckel，Java编程思想，北京：机械工业出版社M,2007年6月。3王朝晖、杨洁，公交线

26、路中最优路线的查询算法设计，电子政务与地理信息技术论 文专辑J，149-152，2005 年。4吴永军、蔡永香、郭庆胜，城市公交查询系统的设计与实现，测绘信息与工程J， 40-42，2006年。5廖楚江、蔡忠亮、杜清运、王长耀，基于最少换乘的公交最优路径算法的设计与实 现，武汉大学学报J，第31卷第10期，904-907，2006年。package公交查询；import java.io.DataInputStream;import java.io.File;import java.io.FileInputStream;import java.io.FileNotFoundException;i

27、mport java.io.IOException;public class 公交查询系统static node cline二new node500;static boolean fflag二new boolean3957;static int then=0;static String luxin;static String huan=new String500;public static void main(String args) for(int i=0;i3957;i+) String s;fflagi=new Boolean(false);if(i10)s=new String(S00

28、0+(i+1);else if(i100)s=new String(S00+(i+1);else if(i1000)s=new String(s0+(i+1);else s=new String(s+(i+1);luxin=new chaxun1().getS();cline0=new node();String s1二new String(S0870”),s2=new String(S3120”);cline0.pre=-1;cline0.s=new String(sl);cline0.then=0;int i=1;boolean ff;dof仁findline(s1,s2,cline,0,

29、0,huan,luxin,i+,fflag);System.out. println(i);while(ff=false);static boolean findline(String s1,String s2,node cline,int then,int th,String huan,String luxin,int chishu,boolean fflag) String sname;boolean flag二false;if(chishu1)return false;int i;for(i=0;i3957;i+) if(i10)sname二new String(S000+(i+1);e

30、lse if(i100)sname二new String(S00+(i+1);else if(i1000)sname二new String(s0+(i+1);else sname=new String(s+(i+1);if(fflagi)return false;if(sname.equalsIgnoreCase(s1)=true)fflagi=true;break;String口 xianji = luxini;for(int j=0;j1)for(int j=0;jxianji.length;j+)/s1站点一；s2；站点二；cline;数组；then；数组中位置；th；深度；huan；环

31、行数组；luxin；路线详细；chishu xianlu x=new xianlu(xianjij); boolean flag1 = false,flag2 = false; for(int k=0;kx.xian1.length;k+)flag1二findline(x.xian1k,s2,cline,then,th+1,huan,luxin,chish u-1,fflag);for(int k=0;kx.xian2.length;k+)flag2二findline(x.xian2k,s2,cline,then,th+1,huan,luxin,chish u-1,fflag);flag二fl

32、ag1|flag2;return flag;static void putout(node lin,node cline,String huan) node l=lin;node line = new nodelin.then+1;int i;for(i=0;i0)l=clinel.pre;i-;System.out.println(line:);for(i=0;i=lin.then;i+) System.out.println(huani+ +linei.s);class node public int pre;public String s;public int shijian;publi

33、c int jiage;public int then;class chezhan String name;public xianlu line;public chezhan(String name) int i=0; = name;xianlu jline;xianlu line = new xianlu50;for(int j=1; j=520; j+) String s;if(j10)s = new String(L00”+j); else if(j100)s = new String(L0+j); else s = new String(L+j); xianlu xi

34、an = new xianlu(s); if(xian.exit() linei=new xianlu(s); i=i+1;jline = new xianlui;for(int j=0; ji; j+) jlinej = linej;class tongxing int xflag=12;xianlu line;String s1,s2;int jiage;int shijian;public boolean flag二false;public tongxing(xianlu line,String s1,String s2) int len=1;if(line.flag=

35、1) /根据上下行车方式计算时间和价格 int i,j;for(i=0; iline.xian1.length; i+)if(s1.equalsIgnoreCase(line.xian1i) break;for(j=0;jline.xian1.length;j+)if(s2.equalsIgnoreCase(line.xian1j) break;if(ij) xflag=11;/上行if(j=i) for(i=0; iline.xian1.length; i+)if(s1.equalsIgnoreCase(line.xian2i) break;for(j=0;j=line.xian1.leng

36、th)len=0;if(xflag=12)if(j=line.xian2.length)len=0;if(ij&len=1) flag二true;shijian=(j-i)*3;if(line.jiflag=1) jiage=1;/统一记价else /分段记价if(j-i=20)jiage=1;else if(j-i=40)jiage=2;else jiage=3;else if(line.flag=2) /根据环行行车方式计算时间和价格 int i,j,l;for(i=0; iline.xian1.length; i+)if(s1.equalsIgnoreCase(line.xian1i)

37、break;for(j=0;jline.xian1.length;j+)if(s2.equalsIgnoreCase(line.xian1j) break;/System.out.println(+i+j);if(ji)j=j-2;if(ji|ij)&iline.xian1.length&jline.xian1.length)l = (j-i + line.xian1.length)%line.xian1.length;flag二true;shijian=l*3;if(line.jiflag=1) jiage=1;else if(l=20)jiage=1;else if(l=40)jiage=

38、2;else jiage=3;else /根据可逆行车方式计算时间和价格 int i,j,l;for(i=0; iline.xian1.length; i+)if(s1.equalsIgnoreCase(line.xian1i) break;for(j=0;jline.xian1.length;j+)if(s2.equalsIgnoreCase(line.xian1j) break;if(i!=j&iline.xian1.length&jline.xian1.length) l=i-j;flag二true;if(l0)l=j-i;shijian=l*3;if(line.jiflag=1) ji

39、age=1;else if(l=20)jiage=1;else if(l=40)jiage=2;else jiage=3;class xianlu int jiflag;/记价方式int flag;/行车方式String name;public String口 xian1,xian2,xian0;xianlu(String name) = name; String口 str; chaxun s = new chaxun(); str = s.getS(); String regex = new String(); xian0 = str0.split(regex); xianl = str1.split(regex); xian2 = str2.split(regex); if(xian00.equalsIgnoreCase(danyipiaozhi) jiflag = 1; /单一票价 else jiflag =