公交线路的选择问题

公交线路的选择问题摘要这是一个在不同的目标下，求解最优路径的问题。在模型预处理部分，我们较详细地进行公交网络特性分析、换乘情况分析、公交路线分析和影响因子分析。通过分析，我们提取出影响乘客抉择的主要3个因子：换乘次数、耗时和费用。其中换乘次数影响最大，很大程度上影响乘客的心理和抱怨度，作为一级指标；耗时和费用，在换乘次数确定的条件下，对乘客的抉择起到一定作用，并列地作为二级指标。对问题1：本文采用直达矩阵这一数据存储结构来有机的构建复杂的公交网络。接着我们引入最小换乘矩阵，讨论公交网络结点间的换乘问题，得出最小换乘算法。用最小换乘算法算得最小换乘次数，并确定了相应的路径，得出公交网络的方便可达性的结论。再在这些路径中分别选取耗时最少和费用最少的路径。通过仔细分析数据，我们得出耗时最少的同时费用最少。不论乘客对耗时和费用的偏好程度怎样，线路的选择总是不变。对问题2：当考虑地铁线路时，我们认为有地铁尽量选择地铁，使得耗时尽量小。通过与换乘次数最小的结果进行比较，取耗时相对较少的解。对问题3：当考虑步行线路时，根据步行长度的长短，将所有站点之间的距离分成三类，每类耗时和费用取不同的权值，来进行决策。第一问的结果：（我们只列出了前三组的结果，详见正文）（1） S3359—331站TS1784（中转站）一姿过站—S1828，耗时101分钟，费用3元。乘坐L436 乘坐L167（2）S1557一经一过一12站tS1919（中转站） 一经过一3站tS3186（中转站）—经一过一17站一tS0481，耗乘坐L184 乘坐L189 乘坐L460时106分钟，费用3元。（3） s0971一一过一tS2184（中转站）一一一tS0485，耗时128分钟，费用3元。乘坐L013 乘坐L417第二问的结果（我们只列出前三组的结果,详见正文）:1)S3359—过—站TS1784（中转站）经过1站TS1828乘坐L436乘坐L1672)S1557经过2站tS1919（中转站）经过3站S3186(中转站)经过17站TS0481乘坐L184乘坐L189乘坐L4603)S0971经过6站——TS0567(D01)-经过19站TS1920(D20)经过6站TS0485乘坐L094或L119乘坐T1乘坐L417关键字：换乘次数、耗时、费用、最小换乘算法、标号法、交集法一、问题重述第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具(简称公交，包括公汽、地铁等)出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。要解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型与算法，求出以下6对起始站一终到站之间的最佳路线(要有清晰的评价说明)。(1)、S3359-S1828 (2)、S1557-S0481 (3)、S0971-S0485(4)、S0008-S0073 (5)、S0148-S0485 (6)、S0087-S36762、 同时考虑公汽与地铁线路，解决以上问题。3、 假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。二、模型假设公汽线路中相邻公汽站的距离都一样，这对于同条公交线路和不同的公交线路都成立。地铁线路中相邻地铁站的距离也一样，不过比公汽线路的要长得多。马路两对面的车站为同一个车站，即多条公交线路经过同一地点时用的是同一个站点。而且对于同一条公交线路的上、下行线经过同一地点时，虽然分别停在马路的两边，但我们还是将其记为同一个公交站点。公汽换乘公汽是指在同一车站内的换乘，不会在一个站下车后走到另一个车站再上车。地铁换乘地铁只在地铁线交叉的地方发生，即只在D12和D18这两个站完成T1、T2之间的转换。同一地铁站对应的两公汽站(如S0567和S0042)之间的换乘一定要通过地铁来完成，即要从公汽站S0567-＞地铁站D01-＞公汽站S0042，而不能直接从公汽站S0567-＞公汽站S0042。目的地只是公交车站(包括公汽站和地铁站)，我们只考虑站到站的路线问题，不考虑到达目的车站后，再走多少米到达目的地的问题。只有公汽可搭乘，即不考虑地铁线路和步行线路,这时认为同一个地铁站的公汽站点不互通，如D01的S0567、S0042、S0025之间不可通过地铁站走通。选择方案时只以转乘次数最少为目的，先不考虑耗时和路费对路线选择的影响。三、符号说明N 转乘次数T 公汽行驶时间tT 等待时间wTn 通过(n-1)次换乘从顶点i-j的路径数Q 使得Tn工0的n的最少换乘次数i,j i,jT矩阵 直达矩阵Q矩阵 最少换乘矩阵T(a=1,2…n) 每种路经的耗时aC(a=1,2,…n) 每种路经的费用aC 单一票价dC 分段计价fS 出发地到目的地的路程a 耗时的权值Ta 费用的权值c四、问题一模型的分析、建立与求解模型的预处理：公交网络分析公交车站是前后两个站点是紧邻的，同一线路上是可直接到达的。前面一个结点必须经过本结点才能和后一结点取得联系，即它是有先后顺序的有向网络。一个确定的公交站点，和它有直达车的站数，相比于总的站点数来说，是很小的一部分，也就是说如果建立一个公交网络图矩阵，这个矩阵将是一个稀疏矩阵。在一个公交网络中，有多条线路经过同一站点的情况，还会出现一个站点多次连到另一站点的情况。如下图：

图1：A与B之间有多条线路可通这样如果建立邻接矩阵将是三维的。而且相邻站点还会出现各种不同的情况。如下图：图2：相邻公汽站的各种相对位置这些情况都要考虑在内。由于题目中给出相邻公汽站平均行驶时间（包括停站时间）：3分钟，因此公交网络是等权的网络。公交路线换乘情况分析公汽站点数为3957个，线路520条。对于在同一站换车，即公汽换乘公汽，有两种情况：在同一站的马路同一边换，即不过马路直接上另一辆公汽。在同一站的马路对面换，即下车后要过到马路的另一边再搭乘另一辆公车。这种情况是有可能发生的，如图：如图乘线路1到左公汽站，再走到右公汽站乘线路2。左公汽站和右公汽站都标同一个号，这也是在同一站换车的情况之一。公交路线分析公交路线可以分为三类：（I）上下行线的公交站一样；（II）上下行线的公交站不完全一样；（III）上下行线的公交站完全不一样，即环形线。第I类同一条线路的上下行线要用不同的边来表示，如L002的S3748和S2160的路线，对于上行线来说，要建立的有向图的边为S3748->S2160，对于下行线，有向边为S2160->S3748。也就是说，对于相同的一段路，走的方向不一样，相应建立的有向边也不一样。第II类虽然可以用无向的边来表示，但为了和第I类统一，我们还是用有向边来表示，即还是将一条线路分成上行线和下行线来计算，下行线即是上行线的原路返回。如公汽线L001,将其扩展成上行线：S0619->S1914->S0388->„->S3914->S0128->S0710和下行线：S0710->S0128->S3914->„->S0388->S1914->S0619。上下行线的表示方法任用第I类的表示方法，这样第II类路线的表示方法就和第I类统一了。第III类是一条单行线，即相当于第I、II类的上、下行线的某一条。我们可以将其归为一类，用有向图的边来表示。通过以上的处理我们将三类公交线路用统一的有向边来表示，这样就不需将三类公交线路分开考虑，只需将整个公交网用一个有向图来表示。对于题中数据的质疑。公汽线路L290:附录中认为此线为环形线，但我们观察可知该线的起始站为S1477而终点站为S1479，即起始站和终点站不一样，这和环形线的定义不一致，我们又通过搜索该线的最后几站S2017-S1479,在L066中找到了S2017-S1479-S1477这条线，我们认为是L290的最后漏掉了S1479-S1477这一个站。这样L290的线路为：S1477-S2159-S1404-S2480-S3241-S3409-S3186-S3544-S1788-S1789-S1770-S2322-S0992-S2184-S2517-S3501-S3746-S2151-S3100-S0618-S1327-S2303-S3917-S3231-S2654-S1729-S3766-S1691-S1383-S2347-S1381-S1321-S2019-S2017-S1479-S1477本文按L290为环线且终点站为S1477来做。公汽线路L406:附录中认为此线不是环形线，但该线的起始站S1871和终点站S1871编号一样，而且途中的站没有重复出现的，故我们认为L406这条线是环形线且双向行驶的，也就是说，这条双向行驶的线是环形的。公交线路的选择的影响因子分析该问题建立在只考虑公汽线路不考虑地铁和步行的条件下。公交线路的选择由三个因素决定：转乘次数N、耗时T和路费C。其中，转乘次数指的是从出发地A到目的地B要转乘的公汽线路的次数；耗时指的是由出发地A到目的地B的所有行驶时间T、等待时间T之和，即T=T+T；路费指的是途中搭乘公汽或twtw地铁产生的费用。其中转乘次数起到相当重要的影响，由于选择路线是人们总是希望路线便于记忆，如果转乘次数太多就不便于记忆。同时，有材料显示如果转乘次数太多，则乘客的抱怨度就会明显增高。我们还考虑到行驶路线的长短这个因素对线路选择的影响。行驶路线的长短可以由耗时来反映，一般来说路程越长，耗时越多，费用越高。而且，实际生活中，要从A地到B地，我们只会关心要用多少时间和如何走，对于走的路程有多长我们并不关心。比如说，由A->B有两条线路可选，一条路程长耗时少，一条路程短耗时多，我们一定选择的是耗时少的那条路。所以本文认为行驶路线的长短对路线的选择无影响，即公交线路的选择只由三个因素决定：转乘次数N、耗时T和路费C。下面我们分别以只考虑转乘次数、只考虑耗时和只考虑路费为目标，建立问题一条件下的转乘次数模型、耗时模型和路费模型。模型一：转乘次数模型假设8：选择方案时只以转乘次数最少为目的，不考虑耗时和路费对路线选择的影响。模型的分析与建立实际生活中，转乘公交车会带来很大的麻烦，很大一部分人不希望转车的次数太多，故我们考虑最少转乘次数是合理的。由于转乘次数为N,则该模型可直接表述为：N0,1,2,3,4(1)模型的求解至于如何求得最少转乘次数，我们采用交集法。即先找到起始点、终点所在路线是否可以直达，如不能直达，就要找它们所在路线的交集结点，如他们所在路线没有交集结点。就要从起始点、终点相向双向搜索，直到找到二次转乘的交集结点。依此类推，找到更多次转乘的结点。如果单纯的进行深度或广度遍历，则算法的复杂度将会很高，计

引入两个矩阵[1]：直达矩阵和最少换乘矩阵T矩阵（直达矩阵）其中T为顶点iTj直达线路数n。i,j例如：L002的上行路线：…->S1223->S1404->S2377->S1477->…下行路线：•••->S2017->S1477->S1404->S1223->…如果其他没有线路再经过 S1404和S2377，则t=1。但下行路线没有1404,2377S2377->S1404这段路，而且如果其他线路都没有S2377->S1404这段路，则t=02377,1404抽象成数学表达式，即(2)i=j我们通过举一个例子来说明T矩阵的含义。下图为一公交网络，其中1〜15为顶点,R1〜R5为线路（用实线段表示）。11图5：以15个站点为例的公汽网络示意图由定义得顶点1〜9的T矩阵为0111001000J01001100000000000000010000000011]000010100000000000000000001-000000000-图6：由图5所示公汽网络得到的直达矩阵可以证明Tn表示通过（n-1）次换乘从顶点iTj的路径数。如T2=1表示从顶点11,5到5有一条一次换乘路线，换乘点为顶点2。T为顶点kTj的直达路线数，则有k,jTn=ETn-1T （3）i,j i,kk,jkQ矩阵（最少换乘矩阵）Q为使得Tn丰0的n的最少换乘次数。i,j i,j例如，我们想算S3359到S1828的最少换乘次数，只要算得t、t2、t3…直到t”的n 这一项不为0,此时得到的Tn矩阵就是矩阵Q。这样，图5公交网络的Q矩阵为:3359,1828■*X3D::i2J::i\2\0sc1I22J230XE1]12312J]3D■201■JXt1222?2132■3EKGGK□G3Ge122!230=8HX0DHgg1S£11ga18GOgGODO3G-000諒1DODG]saN至竺££ag22J238E3CWEg0DEw1Eg2ag宴SGE•DOgDC-gg00]g8H笄*工GG>110]2000持B00|1E虫2-aoaa2CcaH□e-gH0图7：图5所示的公汽网络的最小换乘矩阵利用Q矩阵可以确定最少换乘次数，还可用于评价公交网络。若计算所得Q很大,i,j说明从顶点iTj需多次换乘，方便性较差，可通过增加或改善i，j间公交线路来减少Q。i,j对于一条公交线路上的顶点，应用T矩阵所得结果可能偏大，但这并不影响Q矩阵的有效性。当Tk为偏大值时，必存在p<k,使得TP丰0。如T2=1表示从顶点1到顶i,j i,j 1,3点3有一条一次换乘路径，换乘点为2，此值偏大（1T3可直达）。而t2=1，故Q=1。1,3 31,最小换乘算法的算法思路：设s,d表示出发地和目的地。①若s=d，则为无效路径；若Q=1，选取D（s,d）中一条路线，得直达路径；s,d若Q =2,则必存在一个站点m,使得q=1,q=1。分别选取s,d s,m m,dD（s,m）和D（m,d）中一条路线相连，得一次换乘路径，换乘点为m；若q=3，必存在2个不同站点m,m，使得Q=1,q=I,q=1。分别选s,d 1 2 sm1 m1m2 m2d取D（s,m）,D（m,m）和D（m,d）中一条路线相连，得二次换乘路径，换乘点为1122m,m。12算法的复杂度分析前面引入直达矩阵T、最小转乘矩阵的思想来解决此问题，必须要讨论一下此算法的可行性，也就是它的时间复杂度。对于一般的矩阵连乘问题，矩阵（a）连乘n次，ijmxm它的时间复杂度为O（n加3）。对于本题我们要得到某一个结点的连乘问题，首先要先得到它所在行的所有m个元素，然后进行乘法运算，这样它的时间复杂度就为O（m2），连乘n次以后复杂度变为o（nDm2）。在本问题中m=3957，而n所代表的转乘次数一般不超过4次，即4x39572=62,631,396次，这对现在计算机来说每秒都可运行几千万次，因此它是高效的。模型的结果说明：转乘次数最小时，仍有若干解能达到这个最小的转乘次数，这里只给出每组的1个解，详细的解见附录。（1） 有11组并列的解S3359 经U过29站-fS0304（中转站）—M过15站-fS1828乘坐L469 乘坐L217（2） 只有1组解S1557—经—过—12站fS1919（中转站）——经过—3站—fS3186（中转站）—经—过—17站fS0481乘坐L184 乘坐L189 乘坐L460（3） 有12组并列的解S0971—经—过—17站fS0872（中转站）—经—过—31站—fS0485乘坐L119 乘坐L417（4） 有46组并列的解S0008—经—过—12站fS3053（中转站）—经—过—14站fS0073乘坐L159 乘坐L4745）只有1组解S0148-经过44站-fS0036（中转站）—经-过-15站-fS2210（中转站）——经过—3站—fS0458乘坐L308 乘坐L156 乘坐L417（6）有2组并列的解S0087—经—过—11站fS3496（中转站）——经过—9站—fS3676乘坐L454 乘坐L209实际生活中，转乘次数的变化比耗时和费用的变化对顾客情绪的影响更大，也就是说转乘次数是公交线路选择的关键。所以下面的耗时模型和费用模型都是建立在转乘次数最少的情况下，即在转乘次数模型算出了最少的转乘次数时（比如说最少转乘1次），满足这种条件的方案有多种，我们通过计算这每种方案的耗时，取其中耗时最少的。同样，计算每种方案的费用，取费用最少的。模型二：基于最小转乘次数的耗时模型假设8'：在转乘次数一定时，选择方案只以时间最短为目的，路费对路线选择无影响。模型的分析与建立由于转乘次数一定，根据转乘模型的结果，设有n种路径可以实现这样的转乘次数，由于路径已知，则每种路径的耗时T（a=1,2…n）可以算出。该问题的目标就是取出耗时a最少的那个路径，即：min{T,T,…T} （4）1 2n对于仅考虑公汽线路的情况来讲，总路程的耗时T（单位：分）只由坐车的站数M和转车的次数N决定。这样，T由两部分构成:坐在车上的行驶的时间T和转车时在公at汽站点耗费的时间T，即T=TT。由题意，相邻公汽站平均行驶时间（包括停站时间）c atc为3分钟，则T=3M；公汽换乘公汽平均耗时为5分钟，则T=5N。所以有：tcT=3M+5N ⑸a这样该模型可以表述成：min{T,T,…T}1 2n7=3M+5Naa=1,2,—ns.t.]1<M<1000<N<4M、N为整数模型的求解由于此模型是建立在转乘次数上的，所以此时的路线已经确定，我们只需将每条路径的耗时（T,T,…T）算出，再取这些费用的最小值min{T,T,…T}，这样这个最小费12n12n用对应的路径即是在转乘次数最少的情况下，耗时最少的路程。模型的结果说明：该结果包括了最小的耗时、经过的站点数和中转站。在满足最小耗时的情况下，仍有多组并列的解，这些解的换乘次数、耗时都一样。我们仅列出每组的1个解，详解见附录。（1） 耗时101分钟,经过32个站。有2组并列的解S3359 经过31站fS1784（中转站）一经过1站fS1828乘坐L436 乘坐L167（2） 耗时106分钟，经过32个站。只有1组解S1557 经过42站fS1919（中转站） 经过3站fS3186（中转站）经过17站fS0481乘坐L184 乘坐L189 乘坐L460（3） 耗时128分钟，经过41个站。有1组并列的解S0971 经过20站fS2184（中转站）经过21站fS0485乘坐L013 乘坐L417（4） 耗时83分钟，经过26个站。只有9组解S0008 经过12站fS3053（中转站）经过14站fS0073乘坐L159 乘坐L474（5） 耗时106分钟，经过32个站。只有1组解S0148 经过14站fS0036（中转站）经过15站fS2210（中转站） 经过3站fS0458乘坐L308 乘坐L156 乘坐L417（6） 耗时65分钟，经过20个站。只有1组解S0087 经过11站fS3496（中转站） 经过9站fS3676乘坐L454 乘坐L209模型三：基于最小转乘次数的路费模型假设8''：在转乘次数一定时，选择方案时只以路费最少为目的，不考虑耗时对路线选择的影响。模型的分析与建立由于转乘次数一定，根据转乘模型的结果，设有n种路径可以实现这样的转乘次数，由于路径已知，则每种路径的费用c（a=1,2,…n）可以算出。该问题的目标就是取出费a

用最少的那个路径，即：min{C,C,…C} ⑹12n由于我们只考虑乘车费用，也就是说，定行驶路线时不论行驶的时间有多长，只要费用最少即可。这样题目中的各种时间我们都不予考虑，只考虑公汽票价，我们对公汽票价可分析如下：公汽的票价有两种：单一票价C和分段计价C。df其中：单一票价为1元，即：(7)分段计价的票价可表示为如下的分段函数：（其中M表示坐车的站数）1<M<401<M<40(8)C（M）=J 20f3 M>40为了简化编程，我们将单一票价归结到分段计价来表示，原因是：单一票价的运费相当于行一站路的运费1元，对于单一票价的路线来说不管路程有多长，都只相当于一站路（M=l）。这样（7）式和（8）式就可合并成：1<M<40（1<M<40（包括单一票价路线）M>40(9)C(M)=」 20a3由（6）式和（9）式，我们将该模型表述如下：min{C,C,…C}12n[「M+19— 1<M<40C(M)“ 20s.t. <a[3 M>40a=1,2…n模型的求解由于此模型是建立在转乘次数上的，所以此时的路线已经确定，我们只需将每条路径的费用（C,C,…C）算出，再取这些费用的最小值min{C,C,…C}，这样这个最1 2 n 1 2 n小费用对应的路径即是在转乘次数最少的情况下，费用最省的路程。模型的结果说明：该结果包括了最少的费用、经过的站点数和中转站。在满足最小费用的情况下，仍有多组并列的解，这些解的换乘次数、费用都一样。我们仅列出每组的1个解，详解见附录。（1）消费3元。有2组并列的解S3359 经过31站fS1784（中转站）一经过1站fS1828乘坐L436 乘坐L167（2） 消费3元。只有1组解S1557 经过42站fS1919（中转站）经过3站fS3186（中转站）经过17站fS0481乘坐L184 乘坐L189 乘坐L460（3） 消费3元。有1组并列的解S0971经过20站fS2184（中转站）经过21站fS0485乘坐L013 乘坐L417（4） 消费2元。只有10组解S0008 经过12站fS3053（中转站）经过14站fS0073乘坐L159 乘坐L474（5） 消费3元。只有1组解S0148 经过14站fS0036（中转站）经过15站fS2210（中转站）经过3站fS0458乘坐L308 乘坐L156 乘坐L417（6） 消费2元。只有1组解S0087 经过11站fS3496（中转站）经过9站fS3676乘坐L454 乘坐L209对模型一、二、三结果的评价与说明耗时与费用的加权组合我们分析耗时模型和费用模型的结果可知，当耗时最少时，费用也最少。也就是说耗时最少与费用最少同时达到。这样不论耗时的权重大还是费用的权重大，得到的方案还是一样的。故没有将耗时与费用结合在一起的必要。以最小转乘为唯一目标得到最优解后，进行数据分析：第（1）、（3）、（4）、（6）组起始站T终点站只需要转乘1次，因而公交网络是方便可达的。其中：第（1）组最优解为最少经过32个站，消费3元；第（3）组最优解为最少经过41个站，消费3元；第（4）组最优解为最少经过26个站，消费2元；第（6）组最优解为最少经过20个站，消费2元。如果我们单纯以费用C最少为目标，不考虑转乘次数N由于对于每组来说，各起始站T终点站之间没有直达路线，故而消费1元的情况是绝对不会出现的，最少也要消费2元。这样，费用的最小值c>2元，也就是说，只以费用C最少为目标算出的最min小费用，再小也不会小于2元。这样，对于第（4）、（6）组，我们用最小换乘模型算出的最优解，一定和单纯以费用最少为目标，算出的最优解同时取得。而消费3元的第（1）、（3）组是转乘次数最少的情况下得出的，在现有站数最少情况下它们又满足费用最少，也就是转乘次数最小的情况下它们耗费的费用是最低的。如果想进一步减少经过的站数，就必须要增加转乘次数。这样一来，经过两次以上转乘的话，则最少要3元。因此，第（1）、（3）组以最小转乘为唯一目标我们得到最优解也是以最少费用为目标的最优解。分析到此，我们可以得出以最小转乘为目标的最优解也是以最小费用为目标的最优解。即在保证转乘次数最少时取得的费用最小解，与只考虑费用最少时取得的解一样。这样我们就不必再讨论单纯以费用最少为目标的情况了。因此，路费模型就应该是，以最小转乘为第一目标，以路费最省为第二目标的组合优化模型。在耗时模型中，是在最小转乘为第一目标的基础上得到的，要耗时最少就要尽可能的减少就要经过尽可能少的站点，而耗费与路径长短有必然的联系，故而耗时模型是以最小转乘为第一目标，以耗时最少为第二目标的组合优化模型。综合以上分析，以最小转乘为第一目标，以路费最省为第二目标或耗时最少为第二目标的模型是等价的，我们把它们统称组合优化模型。同时，我们比较两组结果，发现它们是相同的。这就证明了我们上述的推断。模型四：最短路径模型(不考虑转乘次数)我们还考虑了这种情况：现实生活中，旅客晕车的情况是很常见的，则这样的旅客不管转乘次数和费用是多少，只要能在最短程内到达目的地即可。为了满足这部分旅客的要求，我们建立了最短路径模型。也就是说，此模型不是在转乘次数模型的条件下得到的。假设8'''：选择方案时只以路程最短为目的，不考虑转乘次数、耗时和路费对路线选择的影响。1.模型的建立这是一个有向图的最短路径问题，目标显然是使从出发地到目的地的路程最短，即minS (10)2.模型的求解传统最短路径搜索算法---Floyd算法和Dijkstra算法的不可行性：这是一个求有向图的最短路径的问题。最短路径的问题有很多经典的算法解决，如Floyd算法和Dijkstra算法。Floyd算法的时间复杂度为o(n3),对于有4000个公汽车站的有向图来说，这样长的计算时间是无法容忍的，所以我们不采用此算法。而Dijkstra算法的时间复杂度为o(n2)，这样的复杂度是可行的。但是，该算法的各有向边权值不同，而根据假设1,公汽网的每边权值都是一样的，所以Dijkstra算法不适用于公交线路的选择问题。下面我们分别用Dijkstra算法的改进算法-—标号法，和利用矩阵相乘原理的算法---修改的最小换乘法，来解决此问题。算法一：改进的Dijkstra算法 标号法⑵由于Dijkstra算法的o(n2)这个时间复杂度较小，我们考虑用Dijkstra算法相类似的标号法［1］进行求解。标号法，是指与图的每一个顶点对应的数字。这里每个公汽站即是图中的顶点，公汽站构成的公汽网络即是一个有向图。设：b(j)表示公汽站V的标号，代表的是V到V的最短长度。V已标号则意味着V到VTOC\o"1-5"\h\zj s j j s j的最短路以及这条路径的长度已经求出。显然初始时b(s)0。l(i,j)表示从公汽站V到V的路程，我们认为是一段弧(V,V)。i j ijK(i,j)表示当前有向路加入弧(V,V)后，V到V的有向路长度。ij sj要从S到D,初始时图中每个点V的标号都为0。从S出发，则S标1,有两条路可走，而且走这两条路的概率都一样，这样走到k、i,且k、i都被标1。如果k走到j,则j是从S经过2步到达的，这样j标记2。如果从i到l再到j,则i是从S经过3步到达j的，这样j标记3。取2和3中最小的，这样就把j标记2。再按这种原则走到D即可。该算法的流程图如下：b（s）eo还有未标号的弧图9：标号法的算法流程图由标号法的算法流程可以看出，标号法采用顺推的方法，每边检测一次，也就是说，按顺序把所有能走的通路都走一遍，取路程最短的，这样就没有重复的回溯搜索，因此是一种很好的算法。复杂度为O(n2)。算法二：修改的最小换乘法在转乘次数模型中，我们已经利用原始的最小换乘法，解决了以换乘次数最少为目标的问题，我们仅仅通过修改此算法的T矩阵，就能解决路径最短的问题。原始的最小换乘法的T矩阵由以下的方法得到的：两站点之间只要有公汽线通，相应位就记1。例如：有L002的上行线：…S2160->S1223->S1404->…。此时t =1，2160,1404也就是说，两公汽站之间只要相通，不管它们之间隔了几站(如此例的S1223)我们都记为1。由此来算最小换乘的次数。修改的最小换乘法的T矩阵是由如下方法得到的:两站之间要有公汽线相通且相邻，相应位才置1。我们还是以公汽线路L002的上行线为例。此时不论对于原始的算法还是对于修改的算法，都有T =1,T=1。但是对于原始的算法T =1，而修改2160,1223 1223,1404 2160,1404后，t=0，这是因为S2160与S1404有公汽线相通但不是相邻的两站。相当于修2160,1404改后的算法认为这两站不相通，我们做这样的修改是为了算出最短路径，即坐的站数最少。做这样修改能算出最短路径的原理如下：原始的最小换乘法求的是换乘的次数最少，也就是说在不同的公汽线路之间转换的次数最少。此时的公汽线路是由若干个公汽站点连接而成，而修改后的公汽路线相当于只由两个公汽站连接起来的一小段一小段的线路。还是以L002的上行线为例，原始的是…S2160->S1223->S1404->…这样一条连续的线，修改后相当于一条公汽线断成如…、S2160->S1223、S1223->S1404、…这样的若干小段公汽线。这样原先在长的公汽线间的转乘就变成了，在只有两个站点的公汽线的转乘。所有公汽线都断成了长度为一站的小公汽线，在小段公汽线间转乘1次，就相当于行驶一站路。这样换乘了多少次就相当于行驶了多少站路。修改后，求换乘次数最少即是求经过的站数最少，也就是最短路径。这样经过修改T矩阵，我们很容易就将最小换乘算法的应用拓展到了求最短路径。根据最小换乘模型中对最小换乘算法复杂度的分析，可知此算法复杂度为O(nxm2)，其中n=1,2,3,4。以上两种算法用Pascal语言进行编程得到的结果一样，即要使路程最短，应按如下路线乘车：S3359-S1828S3359TS2023TS2027TS0248TS0060TS2867TS0582TS0427TS1961TS1187TS1671TS1828S1557-S0481S1557TS3158TS2628TS3408TS1985TS2563TS2682TS0028TS0055TS0051TS1919TS2840TS1402TS3186TS3544TS1788TS1787TS1783TS1784TS2703TS0480TS0955TS1786TS0903TS2101TS0487S0971-S0485S0971TS3341TS2237TS3565TS3333TS1180TS3494TS1523TS1522TS3674TS0391TS0393TS3727TS3697TS1746TS0248TS0060TS2867TS0582TS0584TS3409TS3241TS2480TS1404TS1495TS0771TS0485S0008-S0073S0008TS27439S2544TS0913TS3874TS0630TS0087TS0088TS0609TS0483TS0604TS0525TS3162TS0073S0148-S0485S0148TS0462TS0361TS1797TS2221TS0302TS0710TS0128TS2268TS1308TS1391TS2272TS2270TS1842TS0048TS0630TS3874TS2534TS0239TS0497TS1921TS2480TS1404TS1495TS0771TS0485S0087-S3676S00879S1842TS1327TS2302TS0248TS0060TS2867TS0582TS0427TS3676五、问题二模型的分析、建立与求解该问题考虑公汽与地铁线路,但不考虑步行，这样假设7改为：假设7''：有公汽路线和地铁路线可乘，不考虑步行路线。我们先采用同问题一的最小转乘模型用Pascal语言编程求解，观察数据结果可得与问题一的解相同。我们简单分析其原因：由于除了第6组起始、终止站外，其余5组起始、终止站均不在地铁口，要想在求得的解中加入地铁的成份，就要至少经过一个公交换乘地铁、地铁换乘公交的过程，至少要经历两次换乘。而我们第一问求得的最优解中，最多需要换乘两次，而且费用还比加入地铁的节省，故而无需改变模型的解。模型的分析与建立对于长距离行驶，地铁能大大缩短耗时，我们这里将地铁作为第一考虑的交通工具，能坐地铁尽量坐地铁。我们先观察第一问的数据，最小转乘模型的最优解所经过的站数。第（1）~（6）组的站数分别为：32、32、41、26、32和20站。站数较多，如转乘地铁有可能降低时耗。地铁的基本示意图如下：•地铁站 oO地铁站出口 Q: Q'O图10：地铁站口的示意图由于除了第6组起始、终止站外，其余5组起始、终止站均不在地铁口，故而乘坐地铁就要增加转乘次数，因此，我们尽量利用地铁的方法其目标是减少时耗。我们需要用一个以减少时耗为目标的耗时模型。通过以上分析，我们定制两个准则：① 乘坐公汽的站点尽可能的少。② 公交线路上尽量不要出现转乘现象。按照上述两个准则，我们用耗时模型（同问题一模型）。模型的求解由于要考虑地铁线路，而且地铁的运行速度比公汽的要快，能坐地铁的尽量坐地铁。第（6）组的起始站和终到站都位于T2的地铁口，这样直接坐地铁线T2即可到达。其它5组的起始站和终到站都不在地铁口，这样必须通过公汽线路来转乘。由于搭地铁快，我们尽量找到离起始公汽站最近的地铁站，搭乘地铁，在离终到公汽站最近的地铁站，下地铁。这样就充分利用了地铁资源，节省了时间。算法流程如下：

同为T1或者T2Y输出路线图11：双向搜索的算法流程图模型的结果(1)经过公汽共29站，地铁共7站，转2次，耗时117.5分钟。S3359- tS0856(D28) S0326(D38)-经-过1-0-tS1828乘坐L474 乘坐T2 乘坐L41经过公汽共27站，地铁共8站，转2次，耗时114分钟。S1557 经-过-14站tS0978(D32)—经-过-8tS0537(D24)经-过-13站tS0481乘坐L084 乘坐T2 乘坐L516经过公汽共12站，地铁共19站，转2次，耗时96.5分钟。S0971--经-过6---tS0567(D01)—经-过-19-tS1920(D20)——经过—6站—tS0485

乘坐L094或L119 乘坐T1 乘坐L417经过公汽共9站，地铁共5站，转2次，耗时52.5分钟。S0008——经—过7——―tS3874(D30)—经—过—5tS0525(D25)——经过—2—tS0073乘坐L150或L159 乘坐T2 乘坐L103经过公汽共10站，地铁共18站，转2次，耗时88分钟。有2组并列的解S0148———^—S0302(D03)——过—站—S0464(D21) 经过— tS0481乘坐L308 乘坐T1 乘坐L104或L395或L469S0148——经过—5站—S0302(D03)—经—过1—8站—S0466(D21)——经—过—5站——S0481乘坐L308 乘坐T1 乘坐L051或L450不经过公汽站，经过地铁共8站，不转车，耗时30分钟。S0087(D27)—经—过—8站tS3676(D36)乘坐T2我们将该模型的结果与转乘次数模型的结果比较，看哪个结果的耗时少，就选择相应的方案。两个结果的耗时对照表如下：表格1：转乘次数最少和尽量用地铁的耗时对照表第(1)组第(2)组第(3)组第(4)组第(5)组第(6)组转乘次数模型101分钟106分钟128分钟83分钟106分钟65分钟耗时模型117.5分钟114分钟96.5分钟52.5分钟88分钟30分钟于是可得第(1)、(2)组采用转乘模型的方案，其余组采用耗时模型的方案。问题二的最终结果为：S3359 经过31站fS1784(中转站)一经过1站fS1828乘坐L436 乘坐L167S1557 经过42站fS1919(中转站) 经过3站fS3186(中转站)经过17站fS0481乘坐L184 乘坐L189 乘坐L460(3) S0971 经过6站 fS0567(D01) 经过19站fS1920(D20) 经过6站fS0485乘坐L094或L119 乘坐T1 乘坐L417(4) S0008 经过7站 fS3874(D30) 经过5站fS0525(D25) 经过2站fS0073乘坐L150或L159 乘坐T2 乘坐L103S0148 经过5站fS0302(D03) 经过18站fS0464(D21) 经过5站 fS0481(5) 乘坐L308 乘坐T1 乘坐L104或L395或L469S0148经过5站fS0302(D03)经过18站fS0466(D21)经过5站fS0481乘坐L308 乘坐T1 乘坐L051或L450(6)S0087(D27) 经过8站fS3676(D36)乘坐T2结果分析对于最小转乘模型，我们将T矩阵连乘，乘n次，一直乘到Tn的所有元素不为0,也就是说，经过n次转乘，任意两站点间都能互通。我们将每乘一次后Tn含有的0元素的百分比(即还没有相通的站点百分比)统计如下：表格2:转乘n次时还没有相通的站点数转乘次数N只有公汽线时未通的站点数有公汽线和地铁线时未通的站点数0100%100%160.07%57.04%27.08%4.90%30.125%6.68e-446.45e-64.82e-6500根据表2可以看出：①转乘达4次时,基本上所有的站点都可互通，所以在转乘次数模型中我们限制转乘

次数最多不超过4次。②我们还算出了转乘次数的加权平均值。只有公汽线时为：0X1+1X0.6007+2X0.0708+3x0.00125+4x6.45e-6〜0.746，就是说任意两站点间平均转乘0.746次就可互通；有公汽线和地铁线时：0x1+1x0.5704+2x0.049+3x6.68e-4+4.82e-6〜0.670，此时平均转乘次数降低，这是因为加了地铁线后通路变多的缘故。六、问题三的模型行人的速度大约是公汽车的1/5，公汽车行驶一站要3分钟，则我们假设行人走1站路要15分钟。假设7'''：已知所有站点之间的步行时间。我们对假设7'''作如下解释：考虑步行时间相当于整个北京多了一张步行网，这张网的所有顶点即是公交站点，但各顶点之间的通路不受公交网的限制，也就是说步行网的所有顶点之间都有路相连，而且已知各顶点之间的步行时间已知，设为w-—站点i到站点j的步行时间。ij此模型我们将耗时和费用综合起来考虑。路线选择的决策S由耗时T、费用C加权而成：(11)S=aT+aC(11)tc其中：a+a=1，a、a>0tctc下面分别分析3种出行方式的耗时与费用:步行：耗时最多，费用为零；公汽：耗时中等，费用中等；地铁：耗时最少，费用最多。由于公汽站点多，且相邻公汽站的距离一样，现实生活中人们也经常用公汽车站的个数来衡量两地之间的距离，所以这里通过将w与3分钟一-公汽行驶一站路的时间进ij行比较，来衡量两地路程的长短。当0<w<2（站）x15（分钟/站）时，即i和j之间的距离在2站路之内。此时认为i、ijj间的距离很短，可以步行。距离小于两站路时，费用是关键，此时a=0,a=1。tc当2（站）x15（分钟/站）<w<5（站）x15（分钟/站）时，即i和j之间的距离在2站ij路和5站路之内。此时认为行人无法容忍i、j之间的距离，认为很长而不愿意走；但搭地铁又觉得费用太高，所以只搭公汽。此时，耗时和费用并重，a=0.5,a=0.5。采tc用问题一的模型。当w>5（站）x15（分钟/站）时，i和j之间的距离比5站路还要长。此时要行驶的ij

距离太长了，行人不管要花多少费用都不愿意走，或者搭公车(搭公车的耗时太多)。此时耗时比费用要关键，能用地铁的尽量用地铁。我们取a=0.7,«=0.3。采用问题二tcminami