公交最优路线问题.doc

公交最优路线问题摘要针对公交系统的特点，该文把环形路线和往返路线做成上下行路线，由此构造了1040行、100列的矩阵（矩阵的每个非零元素为对应路线的站点）。矩阵的行下标对应公交系统中的线路号（行数为偶数：线路号=行数/2；行数为奇数：线路号=（行数+1）/2），矩阵的列下标对应每条路线上公汽经过站点的次序，当路线中的站点不足100个时，矩阵中对应的位置以0代替。鉴于公交系统网格的复杂性，没有采用常规的迪克斯特拉（Dijkstra）算法，而是提出了一个能高效搜索任意两站点之间的路线选择的算法。基本思想时从经过起始站的路线出发，搜寻出任意两站点间转乘次数不超过两次的可行路线，然后对可行解进一步处理，建立了以时间最少为目标的优化模型。从实际情况出发，经过尝试与探索，为了满足查询者的不同需求，归纳出直达，换乘一次，换乘两次的情况，并通过Matlab编制程序，给出了任意两站点间的最佳乘车路线以及换车的站点，最后提出了进一步的意见和建议。利用此模型和算法求解所给的6对起始站终到站之间的最佳（最省时）路线。这6对路线的具体情况如表1出发站 终点站S3359S1828S1557S0481S0971S0485S0008S0073S0148S0485S0087S3676最短耗时（min）731061067010646最少转乘次数（次）222222最佳路线（种）1062530314表1 6对起始站终到站之间的最佳（最省时）路线关键字： 优化模型，最优路线，搜索筛选，换乘次数，乘车时间。一 问题重述城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。如果能够提供一种服务，为市民特别是外来旅游、出差、就医等急需了解本地道路情况的人提供方便、快捷、经济、高效的乘车方案，将方便他们的出行和生活，同时减少不必要的交通流量，提高交通运输效率。这已是一个越来越迫切急于解决的现实问题。针对市场需求，本文研制开发了一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。需解决如下问题：给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用所求的模型与算法，求出以下6对起始站终到站之间的最佳（最省时）路线。(1)S3359S1828 (2)S1557S0481 (3)S0971S0485(4)S0008S0073 (5)S0148S0485 (6)S0087S3676基本参数设定：相邻公汽站平均行驶时间(包括停站时间)：3分钟；公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)。二 模型假设（1）各条线路不会有新的调整与变化；（2）查询者转乘公交的次数不超过两次；（3）所有公交线路的开班、收班时间相同；（4）环线可以以任意站作为起点站或终点站；（5）假设各车次在往或返的终点站是不休息，继续行使；（6）除环线以外的线路，到达终点站后，所有的人都必须下车；（7）假设不考虑每车次每日的总班次，各车次工作时间都较为均衡；（8）行车过程中不考虑车辆出现意外（抛锚，交通事故等）以及堵车的情况；（9）假设公交行驶过程中不受地形、天气、路况和上车人数的影响，相邻公交站的平均行驶时间固定不变。三 符号说明：选择第种路线的总时间；:选择第种乘车路线的转乘次数；：选择第种乘车路线，所乘公汽经过的站点的总个数。四 模型的建立与求解4.1 模型的分析为了研制开发一个解决公交线路最佳选择问题的自主查询计算机系统，只要乘客给出起点站和终点站，就能找到所有可行的路线，进而可以找到最省时的路线和换乘次数最少的路线以满足乘客的需求。但从实际情况出发，本文设计一个城市公交路线自主查询系统。为了使线路更合理，并且满足乘客乘车心理（乘客通常也不会因节省几分钟换乘多次），该系统不会使乘客多次转乘到终点站，所以转乘次数小于三次比较合理。为了便于建立模型及求解，对数据进行如下处理：首先构造公交系统的矩阵，先将环形路线和往返路线做成上下行路线，即把原环形路线的最后一站点去掉后作为此路线的上行路线，再把此原环行路线的第一个站点去掉后作为此路线的下行路线；在往返路线中，把数据中所给的原路线作为上行路线，将此上行路线首尾翻转作为下行路线。按照此原则处理后，可构造一个1040行、100列的矩阵。矩阵的行下标对应公交系统中的线路号（行数为偶数：线路号=行数/2；行数为奇数：线路号=（行数+1）/2），矩阵的列下标对应每条路线上公汽经过站点的次序，当路线中的站点不足100个时，矩阵中对应的位置以0代替。4.2 模型的建立4.2.1公汽路线的建立任意两个站点间的路线有多种情况，如果最多允许转乘两次，则路线分别对应图1的三种情况。例如，图1中的、为出发站和终点站,所在路线为，记，所在路线为，记，、为转乘站， 即为与的交点，为与的交点，为与的交点。ABACBABED（a）（b）（c）图1 公汽直达、转乘图L1码1L1码1L1码1L2码1L2码1L3码1（1）直达路线（如图1（a）所示）任意两个公汽站点与，利用MATLAB查找这两站点在矩阵中所在的行与列，由于同一站点的行与列不只一个，如果存在与行数相等，且的在该行的列数小于在该行的列数，则认为可直达。 （2）转乘一次路线（如图1（b）所示）任意两个公汽站点与，利用MATLAB查找这两站点在矩阵中所在的行与列，如果存在与行数不相等，和中含有相同的站点。且在所在路线的前方，在所在路线的后方，则可作为到的一个转乘站，即可经一次转乘到达。（3）转乘二次路线（如图1（c）所示）任意两个公汽站点与，利用MATLAB查找这两站点在矩阵中所在的行与列，如果存在与行数不相等的，则看是否存在路线，与和中含有相同的站点和，且在所在路线的前方，在所在路线的前方，在所在路线的后方，则可作为到的第一次转乘站，可作为到的第二次转乘站，即可经两次转乘到达。4.2.2 最优路线模型的建立找到任意两个公汽站点之间的可行路线，就可以从中找出最优路线。以乘车用时最短作为目标函数，建立最优路线的模型。行驶时间等于乘车时间与转车时间之和，即 。4.3 模型的求解对所给的6对起始站终到站，利用上面的模型和算法求解出每对起始站终到站直达所用的时间，转乘一次所用的时间，转乘两次所用的时间并进行比较得出所有可行路线中用时最少的路线。6对起始站终到站的最佳（最省时）路线情况如下所述：(1)S3359-S1828的最佳（最省时）路线共有106条，均需换乘2次，出行耗时73分钟，在此只列出其中5条，此5条线路具体情况参看表1。表1 S3359-S1828最佳（最省时）路线最优路线起点公汽线转乘站公汽线转乘站公汽线终点1S3359L015S2903L201S0458L041S18282S3359L324S1746L027S1784L217S18283S3359L132S2903L027S1784L217S18284S3359L484S3727L027S1784L167S18285S3359L474S2903L027S1784L167S1828(2)S1557-S0481的最佳（最省时）路线共有2条，均需换乘2次，出行耗时106分钟，此4条线路具体情况参看表2。表2 S1557-S0481最佳（最省时）路线最优路线起点公汽线转乘站公汽线转乘站公汽线终点1S1557L084S1919L189S3186L460S04812S1557L363S1919L189S3186L460S0481(3)S0971-S0485的最佳（最省时）路线共有5条，均需换乘2次，出行耗时106分钟，此5条线路具体情况参看表3。表3 S0971-S0485最佳（最省时）路线最优路线起点公汽线转乘站公汽线转乘站公汽线终点1S0971L263S1609L140S2654L469S04852S0971L024S1609L140S2654L469S04853S0971L94S1609L140S2654L469S04854S0971L119S1609L140S2654L469S04855S0971L012S1609L140S2654L469S0485(4)S0008-S0073的最佳（最省时）路线共有30条，均需换乘2次，出行耗时70分钟，在此只列出其中5条，此5条线路具体情况参看表4。表4 S0008-S0073最佳（最省时）路线最优路线起点公汽线转乘站公汽线转乘站公汽线终点1S0008L355S2755L017S0609L057S00732S0008L355S2755L017S0483L057S00733S0008L159S0630L231S2650L432S00734S0008L159S0854L231S0609L057S00735S0008L159S0854L242S0483L057S0073(5)S0148-S0485的最佳（最省时）路线共有3条，均需换乘2次，出行耗时106分钟，此2条线路具体情况参看表5。表5 S0148-S0485最佳（最省时）路线最优路线起点公汽线转乘站公汽线转乘站公汽线终点1S0148L308S0036L156S2210L417S04852S0148L308S0036L156S3351L417S04853S0148L308S0036L156S3332L417S0485(6)S0087-S3676的最佳（最省时）路线共有14条，均需换乘2次，出行耗时46分钟，此6条线路具体情况参看表6。表6 S0087-S3676最佳（最省时）路线最优路线起点公汽线转乘站公汽线转乘站公汽线终点1S0087L021S0088L231S0427L462S36762S0087L206S0088L231S0427L462S36763S0087L206S0088L231S0427L097S36764S0087L021S0088L231S0427L462S36765S0087L454S0088L231S0427L097S36766S0087L454S0088L231S0427L462S3676五 模型的评价与推广5.1 模型的评价模型讨论了在只考虑公交线路情况下的用时最短线路，鉴于公交系统网络的复杂性，没有采用常规的迪克斯特拉（Dijkstra）算法，而采用搜索所用可行路线，从中筛选最优路线的方法。该模型简单易懂，操作简单，涵盖了所有路线的选择情况，模型中最重要的一个功能是在乘客给出起点和终点后, 自动计算出最优的乘车路线，满足查询者的需求。设计出合理而有效的算法,在一定程度上,可使公交客流分配更加合理，路线利用率最大。5.2 模型的改进和推广在假设中提到，忽略了人流、车流拥挤的状况，但事实并非如此。可以在模型的设计中加入线路运行的时间元素，使乘客查询时只显示正在运行的线路。还可以对若干条从某一初始站点到目标站点的线路，设计一种带记忆功能的系统，即乘客选择某路径的次数越多，说明此路径是比较优的路径，为以后选择路径提供必要的信息。系统使用的时间越长，为乘客提供的信息越全面，越准确，系统也越智能化。这样就可以为乘客需求量最大的一条增加班次，以满足更多人的需要。参考文献1杨新苗 ,王 炜 ,马文腾 . 基于GIS的公交乘客出行路径选择模型. 东南大学学报 (自然科学版) ,第30 卷第6 期: 87-91,2000 年11 月2谢金星,邢文训，网络优化，北京： 清华大学出版社， 2000 3陈萧枫，蔡秀云，唐德强，最短路径算法分析及其在公交查询的应用，工程图学学报，第3期：20-24，2001年4杨群，关伟，张国伍，基于合理多路径的路径选择方法的研究，管理工程学报，Vol.16 , No.4：42-44，2002年附录（1）%数据处理n1=length(a1);for i=1:6:n1 b=a1(i:i+5); if b(2)=L b1=str2num(b(3:6); c(b1,:)=0; else b=b(3:6); b2=str2num(b) c(b1,(i-1)/6+1)=b2; endendn2=length(a2);for i=1:6:n2 b=a2(i:i+5); if b(2)=L b1=str2num(b(3:6); c(b1,:)=0; else b=b(3:6); b2=str2num(b) c(b1,(i-1)/6+1)=b2; endendn3=length(a3);for i=1:6:n3 b=a3(i:i+5); if b(2)=L b1=str2num(b(3:6); c(b1,:)=0; else b=b(3:6); b2=str2num(b) c(b1,(i-1)/6+1)=b2; endendn4=length(a4);for i=1:6:n4 b=a4(i:i+5); if b(2)=L b1=str2num(b(3:6); c(b1,:)=0; else b=b(3:6); b2=str2num(b) c(b1,(i-1)/6+1)=b2; endendn5=length(a5);for i=1:6:n5 b=a5(i:i+5); if b(2)=L b1=str2num(b(3:6); c(b1,:)=0; else b=b(3:6); b2=str2num(b) c(b1,(i-1)/6+1)=b2; endendfor k=1:520 u=find(c(k,:)=0); n=length(u); c(k,1:n)=c(k,u); c(k,n+1:end)=0;end c(:,300:end)=;t=zeros(1,520);for k=1:520 n=length(c(k,:); for i=1:n-1 if c(k,i)=c(k,i+1) & c(k,i)=0 t(1,k)=1; end endendn1=find(t=1);n2=17,27,89,152,158,213,231,239,273,290,296,365,381,407,408,412,425,433,485,505,509,514;for i=1:111 for j=1:22 if n1(i)=n2(j) n1(i)=0; end endendq=find(n1=0);n1=n1(1,q);d=zeros(1040,300);for k=1:520 a1=find(n1=k); a2=find(n2=k); r1=isempty(a1); r2=isempty(a2); if r1=1 n=find(c(k,:)=0); u=c(k,n); d(2*k-1,1:length(u)=u; d(2*k,1:length(u)=fliplr(u); elseif r2=1 n11=find(c(k,:)=0); u1=c(k,n11); u2=u1(1:end-1); u3=u1(2:end); d(2*k-1,1:length(u2)=u2; d(2*k,1:length(u3)=u3; else q=find