公交线路选择优化问题

#公交线路选择优化问题摘要本文针对公交线路选择问题进行了讨论。最佳路线的选择受时间和票价两个因素的影响，将题目已知的公交线路信息转化成线路矩阵处理。首先，从时间角度分析，所要寻找的路线经过的站点数和转车次数应该尽可能的少，考虑到所选择线路到达终点站所用的时间包括公交经过线路上各站点的时间、转车时间和步行时间，建立以所需时间最少为目标函数的线性优化模型一，从实际出发限制转车次数最多为2次，根据搜索算法利用MATLAB编程，求得问题一中S3359-S1828（其余见正文）之间的最佳路线为：436下行-S1784-L167下行和L436下行-S1784-L217下行，所用时间为101分钟，总车费为3元；问题二中S3359-S1828之间的最佳路线为：L015上行-S3068-D08-T1上行-D18-T2-D38-S3262-L041上行，所用时间为73分钟，总车费为5元。其次，从票价角度分析，寻找的路线应尽可能是单一票价车路线或经过站点数尽可能少的分段计价车路线，考虑到所选择线路需要的总车费包括公汽费用和地铁费用，建立以所需车费最少为目标函数的线性优化模型二，根据搜索算法利用MATLAB编程，求得问题一中S3359-S1828之间存在L436下行-S1784-L167下行等10条最佳路线（其余见正文），所用时间为101分钟，总车费为3元；问题二中S3359-S1828之间的最佳路线为：L015上行-S3068-D08-T1上行-D18-T2-D38-S3262-L041上行，所用时间为73分钟，总车费为5元。再次，根据乘客的不同需求可以赋予时间和票价两个因素不同的权值，建立以所需时间与所用票价在各自权值下的和最小为目标函数的线性优化模型三，当取权值皆为0.5时得问题一中S3359-S1828之间的最佳路线为：436下行-S1784-L167下行和L436下行-S1784-L217下行，所用时间为101分钟，总车费为3元；问题二中S3359-S1828之间的最佳路线为：L015上行-S3068-D08-T1上行-D18-T2-D38-S3262-L041上行，所用时间为73分钟，总车费为5元。最后，对模型进行了评价，并将该模型推广到路径选择问题中。关键词公交线路选择；线性优化模型；搜索算法一、问题重述第29届奥运会将于明年8月在北京举行,届时有大量观众到现场观看，大部分人都会乘公共交通工具，北京市的交通逐步发达，开通的线路也逐渐增多，某公司针对市场需求准备开发一个解决公交线路选择问题的系统，需解决如下问题：1、仅考虑公汽线路，针对任意两公汽站点之间的线路建立一般数学模型，利用建立的模型求出以下6对起始站一终到站之间的最佳路线。(1)、S3359-S1828(2)、S1557-S0481(3)、S0971-S0485(4)、S0008-S0073(5)、S0148-S0485(6)、S0087-S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。二、问题分析随着交通事业的发展，公交公司所开通的线路也逐渐增多，针对市场需求需要建立一个合适的模型，解决上述公交线路选择问题。对于最佳路线可以从时间和票价两个角度分析，走完选定路线所用的时间包含经过所有站点的时间和转车所用的时间，全程所需的总车费包括单程票价车和分段计价车两部分，二者的权重可由乘客任意确定，对于乘客的不同要求给出不同的选择路线。针对问题一，将已知的公汽线路信息转化为相应的线路矩阵处理，在矩阵中搜索出所有从所需起始站到达终点站的可行路线，算出各条路线所需的时间和费用，再根据乘客的不同要求寻找出一条最优路径。针对问题二，在问题一的基础上加入地铁考虑路线选择问题，同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘无需支付地铁费，在问题一处理的线路矩阵中将对应地铁站的公汽站改为地铁站进行处理，利用问题一的算法寻找出最优路径，并和问题一的结果进行比较。针对问题三，加入步行的考虑，可理解为增设了一种新的交通工具，步行的自由选择限制程度低，可根据乘客意愿选择不同线路或不同换乘站点。从票价角度考虑，如果某条线路涉及到的分段计价车所经过的站点数略大于20或40，从实际利益出发，可以考虑步行若干站来很好的节约车费。三、模型假设1．交通保持顺畅；2．任意两站点之间的距离相等；3．在可行路线中，如果转车和不转车行完全程所用时间相等，尽可能选择转车次数少的路线；4．从人的一般习惯考虑，所选路线最多转车两次；5．从实际情况出发考虑，公汽转乘地铁至多一次，地铁转乘公汽也是至多一次；6．人可以在任意两公交站点之间行走；7．步行经过相邻两站所用的时间相等；8．步行转到公汽不考虑等车时间；9．步行走过的公汽站点数至多为3；10．如果乘坐单一票价的车可以满足需求，则不考虑步行。四、符号约定a起始站；b终点站；m所有和a相隔1站的公汽站点数；n所有和b相隔1站的公汽站点数；a所有和a相隔1站的公汽站点，i=1,2,…,m；b所有和b相隔1站的公汽站点，j=1,2,…,n；n1公汽线路数目；n2每一条线路上的公汽站点数；n3地铁线路数目；n4每一条线路上的地铁站点数；4k公汽在第i条公汽线路上的行驶次数；il地铁在第i条地铁线路上的行驶次数；iN公汽在第i条公汽线路上经过的站数；ir步行的次数；s步行走过的公汽站点数；t经过相邻两站步行所用时间；q在第i条公汽线路上的转车站点；a只考虑公汽时赋予时间的权值；a'考虑公汽和地铁时赋予时间的权值；0只考虑公汽时赋予票价的权值；0'考虑公汽和地铁时赋予票价的权值；t(a,b)公汽从a到b花费的时间；ijijC(a,b)从a到b花费的票价；ijij[1,公汽在第i条公汽线路上经过第j站；x=<ij0,公汽在第i条公汽线路上不经过第j站;x[1,公汽在第i条公汽线路上行驶；i0,公汽不在第i条公汽线路上行驶；[1，地铁在第i条地铁线路上经过第j站；y=<ij0,地铁在第i条地铁线路上不经过第j站;、，[1,地铁在第i条地铁线路上行驶；y=<i0,地铁不在第i条地铁线路上行驶；和[1,第i条公汽线路是单一票价；p=<i0,第i条公汽线路是分段票价；[1，地铁换乘公汽；U=50,地铁不换乘公汽；

1公汽换乘地铁；w=<0,公汽不换乘地铁；mi相邻公汽站平均行驶时间（包括停站时间），且m】=3（单位：分钟）；m2公汽换乘公汽平均耗时（其中步行时间2分钟），且m2=5（单位：分钟）；m3相邻地铁站平均行驶时间（包括停站时间），且m3=2.5（单位：分钟）；m地铁换乘地铁平均耗时（其中步行时间2分钟），且m=4（单位：分钟）；44m5地铁换乘公汽平均耗时（其中步行时间4分钟），且m5=7（单位：分钟）；m公汽换乘地铁平均耗时（其中步行时间4分钟）且m=6（单位：分钟）。66五、模型的建立与求解在实际生活中，乘客一般选择转车次数尽可能少的路线，为了符合实际满足乘客需要，本文将筛选出最多只转两次车的路线，当乘客在系统中输入所需要的起始站和终点站时，系统调出可行的全部路线，且限于至多转两次车。在所调出的全部路线中从所用时间和所需票价两个角度根据乘客需要选择最佳路线，对二者分别赋予不同的权重，将问题转化为最优路径问题。问题一的求解仅考虑公汽线路，从时间和票价两个方面进行分析，建立任意两公汽站点之间线路选择问题的数学模型与算法。模型一的建立（仅考虑公汽线路中以所用时间最少为目标函数）从时间角度分析，走完选定路线所用的时间包括公汽经过所有站点的时间和转车所用的时间，则所要寻找的最优路线经过的站点数和转车次数应该尽可能的少。建立模型如下：MinZ=mMinZ=m11x-k+miji2丿5kx—1iiIi=1丿5x.=1;iai=15xib=1;5bx;5bx;ijj=q5x>ijj=ak<2；ike乙ii=1,2,,n1;目标函数为经过所有公汽站点所用时间与转车所用时间之和。约束条件一和二限制了所选路线只经过起始站和终点站各一次，约束条件三限制了站点不能重复经过，约束条件四限制最多转车两次。

模型二的建立（仅考虑公汽线路中以所需车费最少为目标函数）从票价角度分析，走完选定路线所用车费包括乘坐单一票价和分段计价的车费，则所要寻找的最优路线尽可能的选择单一票价车路线且选择的分段计价车路线经过的站点数最少。建立模型如下：MinZ=pKkx+MKkx2iiiMiii=1i=1M=1-p,0<N<20;iior:M=2(1-p),21<N<40；s.s.t.<or:M=3(1-P),N>41；iiNeZ;ii=1,2,...,n.1目标函数为所选路线中所需单一票价的车费与分段计价所需车费之和。约束条件一、二和三分别表示分段计价车费与经过站点数的关系。模型三的建立在模型一和模型二的基础上，根据乘客的不同需求，分别赋予时间权值ex和票价权值0不同的值，其大小可由乘客自己选择，且x+卩=1。建立模型如下：MinZ=xZ+0Z12d+0=1；x，0>0；K1xia=1;i=1K1xib=1;s.t.s.t.<Kx.>Kx..,i=1,2,...,n;jj1j=aj=qM=1-P,0<N<20;iior:M=2(1-p),21<N<40;ior:M=3(1-p),N>41;iik<2iN,ke乙ii当x=1，0=0时，即为模型一；x=0，0=1时，即为模型二。模型的算法要从所有的路线中搜索出所有从所需起始站到达终点站的可行路线，然后寻找出一条花费时间和费用最低的路线，将其转化为矩阵中求最小路径问题，从而得到以下搜索算法：Stepl根据已知的公汽线路信息，将其转化为线路矩阵A二(a),a表示第i条公ijij汽线路的第j站；Step2将a和b进行初始化；Step3搜索出矩阵A中出现a和b的所有点，分别记在矩阵E和F中，并记E的行数为ii；Step4搜索出矩阵E和f中第1列相同的所有元素，即找出a和b同时出现的所有路线，并取g°二1；Step5对A中出现的a的第g0行，在A中除过该行的所有元素，搜索出与该行中a后的各个元素相同的所有元素的位置；SteP6取g0二g0+1；Step7重复Step5和Step6，直至g二ii，再取g二1；Step8从A中出现a的第g]行中的站点a开始在A的所有行中搜索通向b的所有线路，其中当第g]行中的a后的元素与A中其它行中的元素相同时，则通过该元素换到其所对应的行中；Step9取g]=g]+1；Step10重复Step8和Step9，直至g1二ii，从而得到A中从a通向b的所有线路；Step11分别计算出由Step10得到的a至b的所有线路所用的时间和所需的车票费用；Step12分别比较各个线路的所用时间和所需车票费用，分别得到花费时间最短和车票费用最少的线路；Step13在以上基础上，分别给时间和车票费用赋予一定的权重，根据需要可得不同的最优线路。模型的求解根据模型求解得S1、S2、S3、S4、S5和S6的最优路线如下：(模型三中给时间和票价皆赋予权值0.5，L为需乘的公汽线路，S为转站点)从实际考虑出发，转车次数越少越好，在只需转车一次就可以到达终点站时，限制转车次数最多为1次。求解S1、S3、S4、S6最优线路时，只转车一次就可以到达终点站，得其最优路线为：S1(S3359-S1828)：模型一的求解路线为：L436下行-S1784-L167下行；L436下行-S1784-L217下行。共2条。模型二的求解路线为：L436下行-S-L167下行，其中S可为S1784,S1241;L436下行-S-L217下行，其中S可为S1784,S1241,S3695,S2606；L469上行-S-L217上行，其中S可为S2364,S0727,S0304,S3192。共10条。模型三的求解路线为：L436下行-S1784-L167下行丄436下行-S1784-L217下行。共2条。S3(S0971-S0485)：模型一的求解路线为：L013下行-S2184-L417下行。共1条。模型二的求解路线为：L013下行-S2119-L395下行；L013下行-S-L417下行，其中S可为S2184,S0992,S2322,S1770,S1789,S2119;L119上行-S-L417上行,其中S可为S0872,S1703。共9条。模型三的求解路线为：L013下行-S2184-L417下行。共1条。(S0008-S0073)：模型一的求解路线为：L159下行-S2559-L464下行；L463下行-S2083-L057下行；L159下行-S-L474下行，其中S可为S0400,S2633,S3053;L159下行-S-L058下行，其中S可为S2683,S0291,S3614,S0491,S2559,S3315；L355下行-S-L345下行，其中S可为S2263,S3917,S2303。共14条。模型二的求解路线为：L159下行-S-L474下行，其中S可为S0400,S2633,S3053;L159下行-S-L058下行，其中S可为S2683,S0291,S3614；L335下行-S2263-L057下行；L335下行-S2263-L345下行；L335下行-S3917-L057下行；L335下行-S3917-L345下行等共29条。模型三的求解路线为：L463下行-S2083-L057下行丄159下行-S-L474下行，其中S可为S0400,S2633,3053;L159下行-S-L058下行，其中S可为S2683,S0291,S3614,S0491;L355下行-S-L345下行，其中S可为S2263,S3917,S2303。共11条。S6(S0087-S3676)：模型一的求解路线为：L454上行-S3496-L209上行。共1条。模型二的求解路线为：L454上行-S3496-L209上行；L454上行-S1893-L209上行。共2条。模型三的求解路线为：L454上行-S3496-L209上行。共1条。而在求解S2和S5的最优线路时，必须转两次车才能到达终点站，则限制其转车次数为2次，得其最优路线为：S2(S1557-S0481),三种模型的求解结果均为：LO84下行-S1919-L189下行-S3186-L460下行;L363下行-S1919-L189下行-S3186-L460下行。共2条。(S0148-S0485),三种模型的求解结果均为：L308上行-S0036-L156上行-S2210-L147下行；L308上行-S0036-L156上行-S3332-L417下行；L308上行-S0036-L156上行-S3351-L417下行。共3条。表1问题一中所求各线路最优路线所用时间和车费模型■辿目标函数S1S2S3S4S5S6模型一时间(min)1011061288310665车费(元)333232模型二时间(min)1011061288310665车费(元)333232模型三(权重各占50%)时间(min)1011061288310665车费(元)3332325.2问题二的求解同时考虑公汽与地铁线路，如果公汽到达某一地铁站对应的任意一个公汽站，就可

以在该公汽站转乘地铁，在问题一的基础上从所用时间和所需票价两个方面进行分析，建立任意公汽站点与地铁站点之间线路选择问题的数学模型。模型四的建立（考虑公汽和地铁线路中以所用时间最少为目标函数）从时间角度分析，走完选定路线所用的时间包括公汽和地铁经过所有站点的时间公汽转地铁所用的时间和地铁转公汽所用的时间。建立模型如下：MinZ=m31ii=15MinZ=m31ii=15x〔5x—k+m[5kijij=1丿2Ii=15y任y.-11+m+m3ii=1ijij=i丿5x.=1;iai=1iix—1—w+wmii丿y—i—u+um丿'i=151xib=1;i=1st]5x.>5x..,i=1,2,...,n;ijij1j=aj=q5y..=1,j=1,2,...,n;j4i=1k<2;ike乙i模型五的建立（考虑公汽和地铁线路中以所需车费最少为目标函数）从票价角度分析，走完选定路线所用车费包括乘坐单一票价、分段计价的公汽车费和地铁的费用，而地铁的费用是一定的。建立模型如下：MinZ45kxiiMinZ45kxiiIi=1[5ki—w+3w

丿M=1-p,0<N<20;iior:M=2(1-p),21<N<40；ior:M=3(1-p),NA41;iiNeZ,i=1,2,...,n.i1模型六的建立赋予影响选择路线的时间和票价两个因素不同的权值，其大小由乘客自己选择，得出最优路线。建立模型如下：MinZ'=a'Z+P'Z34区x=1;iai=1区xib=1;i=1迓x.>迓x..,i=1,2,...,n;ijij1j=aj=qS1空yj=人j=1,2,…,佇i=1M=1-p,0<N<20;iior:M=2(1-p),21<N<40;iior:M=3(1-P),NA41;iik<2;iN,keZ,i=1,2,...,n;ii1模型的求解从时间角度考虑公汽与地铁的换乘时，只考虑使公汽到达转乘地铁站点的时间最短，以简化模型的求解。根据模型求解得S1、S2、S3、S4、S5和S6的最优路线如下：(模型三中给时间和票价皆赋予权值0.5,L为需乘的公汽线路，S为转站点)(S3359-S1828)：模型四求解路线为：L015上行-S3068-D08-T1上行-D18-T2-D38-S3262-L041上行模型五求解路线为：L015上行-S3068-D08-T1上行-D18-T2-D38-S3262-L041上行模型六求解路线为：L015上行-S3068-D08-T1上行-D18-T2-D38-S3262-L041上行(S1557-S0481)：模型四求解路线为：L084下行-S1919-D20-T1下行-D18-T2-D24-S0537-L516上行模型五求解路线为：L084下行-S1919-D20-T1下行-D8-S0616-L072下行模型六求解路线为：L084下行-S1919-D20-T1下行-D18-T2-D24-S0537-L516上行(S0971-S0485)：模型四求解路线为：L094上行-S0567-D01-T1上行-D21-S0466-L051上行模型五求解路线为：L013上行-S0567-D01-T1上行-D21-S0466-L050上行模型六求解路线为：L094上行-S0567-D01-T1上行-D21-S0466-L051上行S4（S0008-S0073）：模型四求解路线为：L200上行-S2534-D15-T1上行-D18-T2-D25-S0525-L103上行模型五求解路线为：L043上行-S1919-D20-T1下行-D8-S0616-L011下行模型六求解路线为：L200上行-S2534-D15-T1上行-D18-T2-D25-S0525-L103上行S5(S0148-S0485)：模型四求解路线为：L024下行-S1487-D2-T1上行-D21-S0466-L051上行模型五求解路线为：L024下行-S1487-D2-T1上行-D21-S0466-L050上行模型六求解路线为：L024下行-S1487-D2-T1上行-D21-S0466-L051上行S6（S0087-S3676）：模型四求解路线为：L454上行-S3496-L209上行模型五求解路线为：L454上行-S3496-L209上行；L454上行-S1893-L209上行模型六求解路线为：L454上行-S3496-L209上行表2问题二中所求各线路最优路线所用时间和车费模'型怨、目标函数s1s2s3s4s5s6模型一时间（min）7379826673.565车费（元）555552模型二时间（min）7380859573.565车费（元）555552模型三（权重各占50%）时间(min)7379826673.565车费（元）555552由表1和表2观察可得，乘坐地铁大大节约了时间，但票价较贵，公汽的乘车时间较长，但票价相对较便宜。根据此规则，乘客可根据自己的需求选择不同的线路。5.3问题三的求解在问题二的基础上，加入了步行的考虑，相当于增加了一种自由选择度很高的交通工具。5.3.1模型七的建立根据乘客的意愿可以选择任意上车站点、转车站点和经过站点数。从时间角度分析，建立模型如下：

MinZ=m5n1x31ii=1+m3i=1MinZ=m5n1x31ii=1+m3i=1迓y•任y.._/|+m运x-k|+mijj=1任kx-1-w|+wmii丿从票价角度分析，MinZ4ijij=1丿i丿、i=1①ly-1-u|+um+rt(s-1)丿iii=15x.=1;ias.tJi=15n1x=1;ibi=1工x..>工X..,i=1,2,...,n;ijij1j=aj=q53yij=1,j=1,2,.,n;ij4i=10<s<3;k<2；ik,se乙i可以认为步行这种交通方式的票价为0，建立模型如下：=pi5n1ki=1A-w|丿+M5n1kx-w|+3w+(s-1)x0iiM=1-p,0<N<23;iior:M=2(1-p),24<N<43;iior:M=3(1-P)，N>44；ii0<s<3;N,seZ;i=1,2,.,n.1从实际考虑出发，如果两站之间没有设公交线路，则步行是必须应用的交通方式，当公交在两站点之间绕路行驶时，不及步行两点之间线段最短来的快，实际生活中堵车是在所难免的，此时步行在时间角度上才最好的发挥其自由选择度高的优点。从票价角度考虑，如果某条线路涉及的分段计价车所经过的站点数大于20小于等于23或大于40小于等于43（假设步行走过的公汽站点数至多为3），从实际出发，可以考虑步行三站以内完成需要多付费的站点，很好的节约了车费。

5.3.2模型八的建立由于模型七没有明显的突出步行的优点，因为可能会出现某公汽转乘到另一公汽后只行驶了一站路就到了终点站，此时人们往往会选择步行完