优秀7基于多种评价方案的公交线路选择优化模型

图的优化模型。模型1从人们乘坐出行主要考虑的换乘次数、出行时间、出行费用出三个因素的综合评价标准。文中建立了基于搜索算法的模型1，但效率较低，因此又建立了基于Dijstra2，大大提高了运算效率，并求出了不同评价点）在图中拆分成2～3个子节点，用构造“站”的方式将等车的时间等效为原始站点与站点之间的行驶时间，将不同的评价标准等价为图中各有向边上的不同权分布这一现象，提出了对期和交通顺畅期路径选择进行对比的模型。同时，我方便的求解我们的问题，但缺点是开发周期长电路板的焊制成本高。层次分析法评价标准Dijkstra算法带权有向图结点电路模拟车流量比较模问题重 (4)、 (5)、 (6)、2、同时考虑公汽与地铁线 解决以上问题模型假符号说M N ——所给数据中一 线路所包含的最大站点数，此题 iiS——编号为i的车站L——编号为i的线路Di——编号为iii

i1,2,，MiT——编号为i的地铁线路i1iA(aij)MM——aij1表示从Si到Sj有线路直达；aij0表示从Si到Sj没有B(bij)N——bijSk表示第i 线路经过SkF(fij)N1——fij1表示的线路执行单一票制，fij0表示Lki 线路Pp pkL

jj

ijM 到达车站St

模型建立与我们根据题目中所给的线路存在上行和下行以及环行的情况，将每条车路线分解为两条线路，即用有向线来对应网络中的线路，同一条线路的上行线和对于这个有向G，我们建立了不同站点之间的邻接0-1A(aij)MM当从i地当站点数不够的时候，其余的矩阵项补0。记换乘次数为r； v1,v2·vraS,vav av,T1(1ir ii rN,r心理上限，因此我们选择Q3，如果换乘的次数才能到达目的地，我们建议X(ii1,2,3,·nn为正整数,nN)Step4：搜索数据矩阵B，将线路X(i)所包含的站点存为换乘矩阵O(i,u)(u1,2,3,·g,g为正整数,gM)，线路Y(j)所包含的站点存为换乘矩阵Pjv)(v123,·hh为正整数,hM)即P(j,v)为从站点S到站点T的一次换乘站点，线路X(i)和Y(j)为换乘一次的最Step6：搜索数据矩阵B，将经过站点O(i,u)的全部线路存为R(k)，其中(t1,2,3,·g,g为正整数,gN)扩充到换乘矩阵O(i,u)中Step8：在不大于上界Q（为简便起见，未标明线路名称S相连，于是我们便找到了换乘两次就可以到达终点T的路径SA1 1、在所有能从起点到终点的换乘次数小于Q的方案路线中，无论时间，费用或其它因(1)S33591 (2)S15572S1557下S1919 (3)S0971140 (4)S00081 (5)S01482 (6)S00871 就是最好的，不管换乘几次。因此，在这个模型中，我们的评价标准是在换乘次数不大Lk为 (i,j)，每一条方案路线的换车地点分别为v1,v2,…vr(rN,rQ),分别Lk 坐线路L,L rt总3

(S,v1)fLi11

(v,T))5(rL 于是我们的目标就是求出t总在算法方面，同上1.1类似，只是在搜索到n次换乘（0nQ）的可行和花费的最小值。仍以图1为例，取Q3，这时我们的可行解就有两条：SA1A6T和SA1A5A7T，再对结果进行比较。解（（钟）（元（元下下 下33S1557下S1919 340 4S2159上3S0008 3S2184上3上 31 1023（元（元(1)S3359下3 43下4 1(2)S1557S1557下S1919 34 (3)S0971 34 (4)S0008 34 (5)S0148 34 (6)S0087S0087 34 (1)S3359S3359下S1746下 14S1784下123(2)S1557S1557下S1919 34(3)S0971S0971251716 13S2159上S223(4)S0008 34(5)S0148 34(6)S0087S0087上1 23层中，我们考虑面的因素：总时间，费用和换乘次数。A， 1A

5 1 7 1 用“和法A的特征根据特征值可算出一致性指标CIn0.033，从而算出一致性比率nCRCI0.05690.1一致性检验通过，于是w 0-15-30-45-60-80-等级标28183Hwi一次换乘的最优解：Hmax0.708725，并且有两个方案，路线分别为S0087S1893S3676和S0087S3496S367622112例3123假设A为一个有三条线路通过的可换乘站点，考虑到乘客可以在A站换乘，将A点按照拆分原则（见下）A1、A2、A3时间x为权值的边，其中：x

YY（Y）来拆分。每个站点在图中建立两个节点SB和B，其中S为原始站点，B为站点<1>对于节点S，建立由S出发的有向边，指向从S出发能直接到达的所有站点<2>对于节点S的站B，建立从这些节点出发到达其对应节点S的有向边 站B所用时t=每两站间行驶时间（3分钟）× 从S出发到达的所有站点 站B，T车费Y

10k(1)S335921 1S1784下13(2)S15573 4(3)S097121 113(4)S00084 1 S0525上15(5)S01483S0148 4(6)S00872S0087上S0088 3基于实际情况，从出行时间的角度出发，考虑到不 。。。。 （地铁ST 站点S 地铁车站 图例 （ST 站点S 地铁车站 <1>对于节点S，建立由S出发的有向边，指向从S出发能直接到达的所有站点的站B，T。其中，若以出行时间最短为目标，则地铁站点T1和T2间各站,除D12D18外不能直接到若以出行费用最少为目标，则地铁站点T1和T2间各站,都能直<2>对于节点S的站B、T，建立从这些节点出发到达其对应节点S的有向边<3>考虑到公共汽车站和地铁站之间存在互相的情况，则在连通的SB，B，STTBST,STB,TSB,SBT,TB,BT,SBST,STSB 站点的站B，T的边权为从S出发到达的所有站点 站B，T所用时汽5分钟，地铁4分钟）BSTTSBTBSBST64744467 站点的站B，T的边权为从S出发到达的所有站点 站B，T车费 YY k 10kk0<1>由于将换乘时间与乘车时间等效，从某站i出发在j站到k站在模型中的步骤为：从i站的原始节点S出发，到j站的节点，到j站的原始节点，到k站的<2>考虑到一些汽车站与地铁站相连，在其原始节点和节点间都加入了有向边，在以最短出行时间为目标进行求解时，可能出现下列情况与实际不符，但由于采用Dijkstra从某车站步行到相通的或地铁站，然后在此站换乘。此时，在图中有两种走法：一种为直接到其原始节点换乘；另一种为先到其站点再从站点到原始站点换乘。显然，第二种情况重复计算了一部分步行时间，而且与实际不符。但由于前案所(1)S3359S3359S29031 1S609行D153D37行S19611S0167S182817(2)S1557 4(3)S09711D1D15行S2533S22104116(4)S0008S00085(5)S01481D2D1534(6)S00871D12D3634费用(1)S3359S3359077214 20S0096S1828113(2)S155714D32行S086站203(3)S0971 3(4)S0008下 2(5)S0148 3(6)S0087101在模型三的基础上增加一组对应于原始节点的步行节点W0

行没有意义其中的B,W对应不同的Si,Sj是相邻的两个站。(1)S3359S3359行S29031S609行D123D37行S196115(2)S1557 S3186 4(3)S0971D11元D15415(4)S0008D255(5)S0148D15S25345(6)S0087 3全改为步行。进一步对汽车行驶速度以及步行速度分析可以发现，当汽车行驶速度大于题目中假设汽车的行驶速度为3分钟/站，若在上下班期道路拥堵，假设6：S3359行D11元21S1671行S3359D123元1S1671模型拓 端电压达到阈值0.7V时导通。当Uab逐渐增大时，从A到B的通的二极管数2。这样，我们就构造出一个由二极管断增长的电压UabT，因为所有的二极管均不象的时候，让S点的电压停止增长，这样就得到了一条花费时间最短的路径。显然，在这心。我们可以很容易的数出此时任一条通的二极管数目，除以2就是最短的花费时间。在具体实现中，我们需要利用电路模拟软件Pspice 2>汽车站的等车时间t的正态分布的方差与此到达公共汽车站的线路数的 min min表示最小的值，max表示最大的maxmin maxmin 期等车时间

,i1, maxmin maxmin4>交通通畅时段等车时间 i