公交网络最佳路径研究.doc

北京公交网络最佳路径研究摘 要：本文针对北京市不同需求条件下的公交线路选择问题，考虑影响公众出行线路选择的各类因素，确定出行耗时、换乘次数、出行费用为三个主要影响因素。对问题1：仅考虑公汽线路的情况下，依据各公汽站点和公汽线路之间的连通性和方向性分别确立了关系矩阵和次序矩阵，以三个影响因素为目标，借助关系矩阵和次序矩阵，建立多目标决策优化模型。由于模型的复杂性，直接求解非常困难，于是设计了搜索树和回溯算法，并利用Matlab软件分别求得六条线路的最佳路径。例如：(5)S0148S0485：最佳路线为L308L156L154L417，耗时103分钟，车费为4元，需换乘三次。对问题2：将地铁线路纳入公交网络，使用0-1变量区别任意两个换乘站点间的路段所使用的交通工具，并根据该0-1变量在不同路段下的取值确定各种交通工具的换乘次数，在模型一的基础上重新建立优化模型，利用问题1的求解方法，用Matlab软件分别求得六条线路的最佳路径。例如：(5)S0148S0485：最佳路线为L024T1L156L417，耗时86分钟，车费为5元，需换乘三次。对问题3：针于同时考虑步行、公汽与地铁线路的最佳线路选择模型，再次引入0-1变量判断在某一路段上是否乘坐交通工具，建立多目标优化模型。本文行文清晰，算法严谨缜密，并在一定程度上减少了运算量，求出了较为满意的结果。在模型改进中又讨论了基于蚁群算法的搜索方式。模型与算法具有一般性和实用性。关键词：公交线路选择；多目标优化；关系矩阵；次序矩阵；搜索树；回溯法1、问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。须解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。2、模型假设1、铁路环线为单向环线2、相邻公汽站平均行驶时间(包括停站时间) 3分钟，相邻地铁站平均行驶时间(包括停站时间) 2.5分钟，公汽换乘公汽平均耗时5分钟(其中步行时间2分钟)； 地铁换乘地铁平均耗时4分钟(其中步行时间2分钟)；地铁换乘公汽平均耗时7分钟(其中步行时间4分钟)；公汽换乘地铁平均耗时6分钟(其中步行时间4分钟)。 3、公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元4、无论地铁线路间是否换乘，地铁票价：3元5、所给数据真实、可靠。6、公汽环行线路为单向行驶线路。7、同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)，且换乘时间以公汽换乘公汽的平均耗时5分钟计算。8、地铁换乘地铁不需要增加费用。9、如果考虑站点之间步行到达，则必须沿着公路线走。10、步行经过两站点之间的时间采用平均时间计算。3、符号说明：所查询线路的起始站（Sourse）；：所查询线路的终点站（Destination）；：所选择线路中所需的换乘次数； ： 换乘站点（）； ： 完成所选择线路的交通工具行驶总耗时（单位：分钟）； ： 完成所选择线路的换乘总耗时（单位：分钟）； ： 完成所选择线路的总耗时（单位：分钟）；：从起始站到第一个换乘站的分段计价票价（单位：元）；：两两换乘站之间搭乘的分段计价票价（；单位：元）；：从最后一个换乘站到终点站的分段计价票价（单位：元）； ： 完成所选择线路的总费用（单位：元）； ： 某一路段是否乘坐公汽或是地铁的0-1变量，有：， ： 某一路段是否乘坐交通工具或是选择步行的0-1变量，有：。：公交线路和公汽站点的关系矩阵；：为关系矩阵中第行第列元素（），如果公交线路经过某个公汽站点，则值为1，否则为0；：公交线路L和公汽站点S的次序矩阵；：为中第行第列的元素（），的值为公交线路上经过某一个公交站的次序；：相邻公汽站平均行驶时间（包括停车时间），即3分钟；：相邻地铁站平均行驶时间（包括停车时间），即2.5分钟；：公汽换乘公汽平均耗时，即5分钟（其中步行时间2分钟）；：地铁换乘地铁平均耗时，即4分钟（其中步行时间2分钟）；：地铁换乘公汽平均耗时，即7分钟（其中步行时间4分钟）；：公汽换乘公汽平均耗时，即6分钟（其中步行时间4分钟）；：记录第条线路是否为单一票制收费，有：；：表示地铁的票价3元;：任意两相邻站点间乘客的平均步行时间(单位：分钟)。4、模型的建立与求解4.1 模型准备4.1.1 对最佳路线的理解解决公交线路选择问题，应该从实际情况出发考虑，满足乘客的各种不同需求。在研究公交网络模型和最佳路径算法时，有必要先了解公交乘客出行时所考虑的因素，通过对公交乘客出行心理、行为的研究来确定模型的优化目标和约束条件。通过查阅相关调研资我们发现，通常乘客选择出行线路时受到以下几个因素的作用：“换乘次数”、“出行距离”、“出行耗时”、“出行费用”，并且在本模型中，这几个因素是相互影响的。换乘次数是指乘客在一次出行从起始站到终点站过程中所换车的次数。出行距离则包括车上距离和车外距离，车外距离指的是乘客为了乘车而步行的距离，比如说从起点到上车站台的距离、中途换车所步行的距离以及从下车站台到终点的距离。出行耗时指乘客在一次出行过程中所需的时间，它也包括车上和车外部分，车外耗时除了在车外距离部分所耗的时间外还包括在车站等车的时间。出行费用指的是乘客在完成一次出行过程中所花的车费。考虑到在乘客乘坐公交车观看奥运比赛时，我们认为乘客倾向于优先考虑花尽量少的时间赶到比赛场地观看比赛，其次考虑所花费用和换乘次数的因素。由此得到评价标准: （1）乘客以最佳路径乘车所花时间最少； （2）乘客以最佳路径乘车所花费用最少； （3）乘客换乘公共汽车次数最少。为方便讨论，我们以换乘站点将出行线路分段考虑，建立一般情况下的线路选择数学模型。计算不同换乘次数下到达终点站的最短时间及其相应费用。综合考虑这三方面因素，结合乘客的各种不同需求，选择最佳线路。4.1.2 次序矩阵由于公交线路分为上行、下行、环行等，即同一条线路上的站点之间存在方向性，而关系矩阵只能够表达站点之间的连通性，因此，按照行驶方向上所经过站点的顺序，建立的次序矩阵。元素的值为公交线路上经过某一个公交站的次序（）。例如下图：L1经过的站点：S5S1S3，L2经过的站点：S2S1S4。建立次序矩阵得：。通过找到决策变量在次序矩阵中的相对位置，能够通过和计算出行驶路线中经过的车站数。4.1.3 线路方向问题如前所述，已知共有520条公交线路和3957个公汽站点，由于公交线路分为上行、下行、环行等，即同一条线路上的站点之间存在方向性，那么我们将同一条线路的上行、下行分成两条线路，环行仍是一条线路，而上下行相同的线路将被分成两条方向相反的。这样，线路总数就不是原来的520条，而变为1017条。那么关系矩阵和次序矩阵中的行数均由原来的520增至1017。：为关系矩阵中第行第列元素（），如果公交线路经过某个公汽站点，则值为1，否则为0；：为中第行第列的元素（），的值为公交线路上经过某一个公交站的次序。需要特别说明的是：L406这条线路并没有被注明是环形线路，但它的首尾两点相同，我们将其处理为环形线路，而不是上下行路线相同的两条。4.1.4 环行车线路的讨论由于公汽不会在环形路线上一直往复不断地运行，因此需要在环形路中设立一站进行清员、加油等车辆维护方面的工作。例如，环形线路按ABCDA的方向行驶，则将A站作为进行清员、加油的站点。如果乘客希望从站点D乘公汽到达B，则可以乘坐该环形线路，但由于需经历站点A，因此该乘客还需要再次缴费并且等候。由此看来，只要乘坐环形线路在同一环线上运行，就可以将环线也视为一条单向行驶的线路，其唯一与单向行驶线路相区别的是：乘客在选择换乘的线路时，也可以再次选择该环形线路本身。4.1.5 公汽票价分类由于公汽票价分为单一票价与分段计价两种，故引入记录第条线路是否为单一票制收费，有：。为方便建立模型，将线路按计费方式重新排序，位于第1至558的线路为分段计价方式，第559至1017的线路为单一收费。当加入地铁线路时，第1018和1019的线路为地铁的计价方式，即3元。4.2 问题一模型的建立、算法与求解仅考虑公汽线路4.2.1模型建立（1）决策变量我们首先引入关系矩阵，其中，如果公交线路经过某个公汽站点，则元素的值为1，否则为0（）。用变量来表示换乘站点，这里，。这样，我们引入了（）作为决策变量。（2）目标函数 根据乘客对最佳路线的三个评价标准，考虑建立多目标决策，分别是出行耗时最少出行费用最少以及换乘次数最少为三个目标。其中，总耗时包含两个部分：为行驶总耗时，为换乘总耗时。总费用则是由各个路段的车费组成，且公汽的票价分为单一票价与分段计价两种。；（3）约束条件当换乘次数为时，路线的起始站为，终点站为，中间的换乘站点分别为，行驶的公交线路编号分别为。站点与公交线路连接形式如图：约束1：为保证每一路段上，同一条线路上的两点连通且从方向上可以到达，得到约束条件如下： 其中，表示线路上从到的站点必然相互连通，是因为相邻站点必然为1。同理，表示线路上从到的站点必然相互连通；表示线路上从到的站点必然相互连通。约束2：换乘站点同属于前一段公交线路和换乘后的公交线路上的点，那么， ；约束3：公汽行驶总耗时为各段历经的站点个数与平均行驶时间的乘积，其中因换乘次数的增加而增加相应路段的耗时，即：； 其中，表示线路上从到历经的站数，表示线路上从到历经的站数，表示线路上从到历经的站数。约束4：因为换乘次数为N，则在仅考虑公汽线路时的换乘总耗时为；约束5：以表示从起始站到第一个换乘站点的行驶站数，则它的分段计价票价为：；以表示从最后一个换乘站点到终点站的行驶站数，则它的分段计价票价为： ；以（）表示任意两个换乘站点之间的行使站数，则其分段计价票价为： 约束6：总费用是由各个路段的车费组成，首先使用来确定该线路采用单一计价还是分段计价方式。如果第段线路上的计价方式为单一计价，则该段线路上为0，而为1；如果第段线路上的计价方式为分段计价，则该段线路上=1，票价为，而为0。其中，表示每个路段的费用。 综上，建立最佳路线选择的多目标决策模型（模型一）：；4.2.2模型的逐步优化由于本问题为多目标决策模型，且各目标的单位不相同，直接通过加权转化为单目标不可行；因此在求解之前需要将问题转化为单目标问题从而实现模型的简化。（1）先不考虑出行费用和换乘次数的影响，在模型一的约束条件下，以出行总耗时最小为目标函数进行求解；模型的最优解记为，然后转到下一步对换乘次数的优化。（2）不考虑出行费用，在模型一的约束条件下，以换乘次数最少为目标函数，同时加入限制条件进行求解。同理将模型的最优解记为（过程略），转到最后一步对出行费用的优化。（3）以出行费用最少为目标函数，在模型一的约束条件下，再加入限制条件，得到（模型二）：注：依据相同的原理，可以分别求解得出仅考虑公交线路下的最终目标为出行耗时最小和换乘次数最小的最佳出行路线，从而将多目标优化问题转化为单目标。这里就不再将这两类模型的简化过程列出，具体的简化过程见附录。4.2.3模型求解(1) 算法分析搜索树及回溯法模型中有大量的0-1变量，基于问题的复杂性，用目前成熟的方法很难求出最优解，因此需要寻找其他算法。由于本问题需要考虑公汽的行驶方向，因此如果直接使用关系矩阵则无法按照站点在线路上的排列顺序来寻找最佳路线。综合考虑线路上站点之间连通与站点排列次序的问题，求解时便从次序矩阵出发，利用搜索树和回溯的方法寻找在不同换乘次数下以时间最少为目标的最优线路。算法的具体步骤描述如下：Step 1：以线路的起始点作为搜索树的根节点，即搜索起点，找出所有通过根结点的公汽线路，并记录下根节点在各条公汽线路上的次序；Step 2：在上找出所有次序比大的站点作为搜索树下一层的节点，即在上找出位于根结点下游的所有站点，并令其作为新的搜索起点开始下一层搜索，原来的搜索起点作为新搜索起点的双亲，以此类推达到要求的换乘次数结束搜索；Step 3：由于搜索树的层数=换乘次数+2，因此可以通过限定搜索树层数来控制换乘次数；Step 4：该搜索树采用双亲表示法作为存储结构。也就是在搜索过程中，每找出新的一个搜索起点，都记录下它的双亲所在搜索树的层号，并将该层号记录在一个双亲矩阵当中，该层号所对应的双亲矩阵的行与列分别是原来的搜索起点与新搜索起点；Step 5：采用回溯法寻找最优乘车线路, 从搜索树的最后一层出发，找到终止点，依据双亲矩阵逐层上推，一直回溯到线路的起始点为止，除叶子结点和根结点外所经过的结点, 即为换车的中间站点。根据站点经过的顺序组合站点对，在线路表中查找对应的换车线路；Step 6：从已找出来的从起点站到终点站的所有线路中找出最佳的那条（即耗时最少或费用最小或换乘次数最少）。(2) 算法流程图根据对公交网络的分析，画出算法流程图如下图所示： 建立次序矩阵开始输入换乘次数times，即可得搜索树的层数layer=times+2输入线路的起始点S和终止点D使起始点S为搜索树的第一层（即i=1，i表示搜索树的第i层），且为下一层（第i+1层）的双亲根据次序矩阵，求出第i+1层的所有结点，并建立双亲与孩子的关系矩阵，i=i+1即层次加1i=layer用回溯法找出起始点到终止点的所有路径求出最佳路径输出最佳路径及耗时结束(3) 搜索树的建立下图是模拟三条公交线路L1、L2、L3的分布情况，起始站为S1，终点站为S4。下面以该图为例说明搜索树的建立过程。L1经过的站点：S1S6S2，L2经过的站点：S2S3S5，L3经过的站点：S5S4S7。建立次序矩阵得：。以次序矩阵为例，起始站点为S1，终点站为S4，从S1到S4，按搜索流程建立如下图所示的搜索树时，将第四层所有结点全部列出才算结束，然后采用回溯法向上记录路径。 在搜索树图中，叶子结点中S4的个数有一个，叶子结点中终点站的个数表示乘车方案个数，即最少换车次数的方案只有一种。由起始站点S1到终点站S4至少要坐3趟车（即换2次车）才能到达。站点的组合是：乘坐线路L1由起始站点S1开始，到站点S2下车，再转乘线路L2，到站点S5下车，然后再转另一路车到终点站S4下车。如果存在若干个方案，则以时间最短为目标，选择出最佳路径。算法的最后结果是输出经过2次换车的最佳乘车方案。(4) 求解过程和结果 利用上述搜索树法和回溯法的算法原理，结合我们的模型，应用Matlab软件编程求解。模型与算法结合方面，我们将关系矩阵X自然巧妙地转换为次序矩阵Y。之前通过0-1关系矩阵控制的连通性约束条件（例如； ）在次序矩阵中通过不为零的次序就能够表达。此外，对于时间的约束本来也就是基于次序矩阵给出的。根据前面的算法，用Matlab软件编程（程序见附录）得到三种情况的结果如下：换乘次数最少：起始站终到站换乘次数总耗时费用换乘站线 路(1)S3359S182811013S1784L436下L167下或L217下(2)S1557S048121123S1919L084下或L363下L417上L254上或L312下或L447上或L460S2424(3)S0971S048511283S2184L013下L417下(4)S0008S00731832S0400L159下L474上(5)S0148S048521063S0036L308上L156上L417下S2210(6)S0087S36761652S3496L454上L209 下此时公交行驶线路经站点情况如下：（1） S3359S1828（路线：L436下L167下或L217下）S3359-S2026-S1132-S2266-S2263-S3917-S2303-S2301-S3233-S0618-S0616-S2112-S2110-S2153-S2814-S2813-S3501-S3515-S3500-S0756-S0492-S0903-S1768-S0955-S0480-S2703-S2800-S2192-S2191-S1829-S3649-S1784-S1828（2） S1557S0481（路线1：L084下L417上L254上或L312下或L447上）S1557-S3158-S2628-S3408-S2044-S1985-S2563-S2682-S0028-S0029-S0055-S0051-S1919-S2079-S0641-S2840-S1402-S2717-S3409-S3186-S3544-S2116-S2119-S1789-S1770-S2322-S0992-S2184-S2515-S2424-S1174-S0902-S0903-S2101-S0481（路线2：L363下L417上L254上或L312下或L447上）S1557-S3158-S2628-S3408-S2044-S1985-S2563-S2682-S2735-S0029-S0055-S0051-S1919-S2079-S0641-S2840-S1402-S2717-S3409-S3186-S3544-S2116-S2119-S1789-S1770-S2322-S0992-S2184-S2515-S2424-S1174-S0902-S0903-S2101-S0481（路线3：L084下L417上L460）S1557-S3158-S2628-S3408-S2044-S1985-S2563-S2682-S0028-S0029-S0055-S0051-S1919-S2079-S0641-S2840-S1402-S2717-S3409-S3186-S3544-S2116-S2119-S1789-S1770-S2322-S0992-S2184-S2515-S2424 -S1174- S0902- S0903- S2101- S0481（路线4：L363下L417上L460）S1557-S3158-S2628-S3408-S2044-S1985-S2563-S2682-S2735-S0029-S0055-S0051-S1919-S2079-S0641-S2840-S1402-S2717-S3409-S3186-S3544-S2116-S2119-S1789-S1770-S2322-S0992-S2184-S2515-S2424- S2424-S1174- S0902- S0903- S2101- S0481（3）S0971S0485（路线：L013下L417下）S0971-S3832-S3341-S2237-S3565-S3333-S1180-S3494-S1523-S1520-S1988-S1743-S1742-S1181-S1879-S3405-S2517-S3117-S2954-S0531-S2184-S2184-S0992-S2322-S1770-S1789-S2119-S2116-S3544-S3186-S3409-S2717-S1402-S2840-S0643-S2079-S1920-S2480-S2482-S2210-S3332-S3351-S0485（4）S0008S0073（路线：L159下L474上）S0008-S3412-S2743-S3586-S2544-S0913-S2953-S3874-S0630-S0854-S0400-S2633-S3053-S0410-S0411-S2846-S0605-S0604-S0527-S0525-S3470-S2619-S2340-S3162-S2181-S2705-S0073（5）S0148S0485（路线：L308上L156上L417下）S0148-S0462-S0361-S1797-S2221-S0302-S2222-S2737-S1716-S0128-S2268-S1308-S1391-S2272-S0036-S0036-S3233-S0618-S0617-S0721-S2057-S2361-S0608-S0399-S2535-S0239-S0497-S2090-S2082-S2210- S2210-S3332-S3351-S0485（6）S0087S3676（路线：L454上L209 下）S0087-S0857-S0630-S1427-S1426-S0541-S0978-S3389-S1919-S0641-S2840-S3496-S1883-S1159-S2699-S2922-S3010-S0583-S1987-S0082-S3676总耗时最小：起始站终到站换乘次数总耗时费用换乘站线路(1)S3359S18284725S2027L484上L201下L474L027L167下S2340S2705S1784(2)S1557S04813994S1919L084下L189下L460下L514S1402S0903(3)S0971S048531044S1609L263上L448上L002下L469上S2113S2017(4)S0008S00732703S1691L198上L476下L057下S2083(5)S0148S048531034S3604L308L156L154L417S2210S3351(6)S0087S36762463S0088L454L231L097上S0427此时公交行驶线路经站点情况如下：（1）S3359S1828（路线：L484上L201下L474L027L167）S3359-S2023-S2027-S2027-S1327-S1842-S0609-S0483-S0604-S2650-S3470-S2619-S2340-S3162-S2181-S2705-S2704-S1784-S1828（2）S1557S0481（路线：L084下L189下L460下L514）S1557-S3158-S2628-S3408-S2044-S1985-S2563-S2682-S0028-S0029-S0055-S0051-S1919-S2840-S1402-S2717-S3409-S3186-S3544-S2116-S2119-S1788-S1789-S1770-S2322-S0992-S2184-S2954-S3117-S2424-S1174-S0902-S0903-S0903-S2101-S0481（3）S0971S0485（路线：L263上L448上L002下L469下）S0971-S3571-S1609-S1609-S3242-S3426-S2553-S3903-S1553-S3531-S1967-S0012-2113-S2112-S2833-S0618-S1327-S2303-S3917-S3231-S2654-S1729-S3766-S1691-S1383-S1381-S1321-S2019-S2017- S2017-S2159-S0772-S0485（4）S0008S0073（路线：L198L476L057）S0008-S1383-S1691-S1691-S3766-S1726-S1008-S0940-S2085-S2083-S1538-S3547-S0609-S0483-S0604-S2650-S3470-S2619-S2340-S3162-S2181-S0073（5）S0148S0485（路线：L308L156L154L417）S0148-S0462-S0361-S1797-S2221-S0302-S2222-S2737-S1716-S0128-S2268-S1308-S1391-S2272-S0036-S3604-S0485（6）S0087S3676（路线：L454下L231L097上）S0087-S0088-S0609-S0483-S0604-S2650-S3693-S1659-S2962-S0622-S0456-S0427-S0427-S3676出行费用最小：起始站终到站换乘次数总耗时费用换乘站线路(1)S3359S18282733S2903L015下L201上L041上S1783(2)S1557S048121123S1919L084下或L363下L417上L254上或L312下或L447上或L460S2424(3)S0971S048521063S2517L013下L296上L417下S2480(4)S0008S00731832S0400L159下L474上(5)S0148S048521063S0036L308上L156上L417下S2210(6)S0087S36761652S3496L454上L209下此时公交行驶线路经站点情况如下：(1) S3359S1828（路线：L015下L201上L041上）S3359-S2903-S2027-S1327-S1842-S0609-S0483-S0604-S2650-S3470-S2619-S2340-S2182-S0992-S2322-S1770-S1790-S0458-S1792-S1783-S1671-S1828(2) S1557S0481（路线：L084下或L363下L417上L254上或L312下或L447上或L460）S1557-S3158-S2628-S3408-S2044-S1985-S2563-S2682-S0028-S0029-S0055-S0051-S1919-S2079-S0641-S2840-S1402-S2717-S3409-S3186-S3544-S2116-S2119-S1789-S1770-S2322-S0992-S2184-S2515-S2424-S1174-S0902-S0903-S2101-S0481(3) S0971S0485（路线：L013下L296上L417下）S0971-S3832-S3341-S2237-S3565-S3333-S1180-S3494-S1523-S1520-S1988-S1743-S1742-S1181-S1879-S3405-S2517-S2184-S0992-S2322-S1770-S1789-S1788-S3544-S3186-S3409-S3241-S2480-S2482-S2210-S3332-S3351-S0485(4)S0008S0073（路线：L159下L474上）S0008-S3412-S2743-S3586-S2544-S0913-S2953-S3874-S0630-S0854-S0400-S2633-S3053-S0410-S0411-S2846-S0605-S0604-S0527-S0525-S3470-S2619-S2340-S3162-S2181-S2705-S0073(5)S0148S0485（路线：L308上L156上L417下）S0148-S0462-S0361-S1797-S2221-S0302-S2222-S2737-S1716-S0128-S2268-S1308-S1391-S2272-S0036-S3233-S0618-S0617-S0721-S2057-S2361-S0608-S0399-S2535-S2534-S0239-S0497-S2090-S2082-S2210-S3332-S3351-S0485(6)S0087S3676（路线：L454上L209下）S0087-S0857-S0630-S1427-S1426-S0541-S0978-S3389-S1919-S0641-S2840-S3496-S1883-S1159-S2699-S2922-S3010-S0583-S1987-S0082-S3676(5) 算法合理性评价通过查询以往的调查资料1，发现通常乘客选择出行路线时考虑的主要因素是换乘次数。搜索树算法便是通过控制搜索树的层数来限定换乘次数，并寻找出该换乘次数下的达到终点站的最少用时或最小费用。通过这种算法可以达到将多目标决策按其重要程度的次序来逐步讨论的目的。 而在图论问题中，传统的寻找最短路径的Dijkstra算法和Floyd算法只是考虑单一目标，并不能进行对多个目标的优化。使用搜索树算法过程中，配合采用了剪枝策略，提高了运算效率。具体方法是利用判断语句，限定在搜索树上层中出现过的结点不会在下面的层中重复出现，从而大大减少重复搜索次数。文献中的搜索树算法多是基于邻接矩阵创建，即只考虑两点间是否连通而并未考虑两点间的连通顺序。由于公交网络在节点与连通性上有一定的特殊性,因此在本文中使用基于次序矩阵的搜索树算法，这样既保证了站点之间的连通性，又保证了行驶路线的方向性，是对搜索树算法的合理改进。4.3 问题二模型建立、算法与求解同时考虑公汽和地铁线路4.3.1模型建立符号补充说明：公汽换乘公汽的次数；：公汽换乘地铁的次数；：地铁换乘公汽的次数；：地铁换乘地铁的次数。同时考虑公路与铁路，我们引入新的01变量。当=1时，表示在第段线路上乘坐公汽；当=0时，表示在第段线路上乘坐地铁。换乘总次数包括公汽换乘公汽次数，公汽换乘地铁次数，地铁换乘公汽次数，地铁换乘地铁次数。路线的起始站为，终点站为，中间的换乘点分别为，经历的线路编号分别为（含铁路、公路）。由于增加了两条地铁线路，我们将这两条地铁作为新增线路，添加进原来的L-S关系矩阵X和次序矩阵Y中，但此时并不需要增加地铁站点，而是通过地铁站点对应的公交站点表示地铁线路的走向。约束条件变动如下：约束1：公汽或地铁的行驶总耗时因加入地铁而发生改变，用0-1变量判断各个路段是否乘坐地铁或公汽，并分别乘以它们相邻站点间的平均行驶时间，即得到行驶总时间，如下：约束2：公汽或地铁相互换乘时的换乘总耗时也因为地铁的加入而变得复杂。根据各种交通方式见的换乘次数可以对应求出行驶过程中总的换乘时间：约束3：表示地铁的票价3元。其中，通过0-1变量判断是否乘坐地铁，通过确定是否为单一票制收费。如果乘坐地铁则收费为，如果乘坐公汽则收费为。表示从起始出发的第段线路上的乘坐交通工具的费用。约束4：另外，由于无论地铁线路间是否换乘，地铁票价均为（3元），所以当地铁换乘地铁时，会造成重复计费。那么，当时，应当减去换乘地铁的费用。得到以下约束条件：综上所述，得到同时考虑公路与铁路且换乘次数为1次时的多目标最优线路选择模型：则一般化的模型为：（模型三）；4.3.2 模型优化与模型一的优化类似，在考虑公汽与地铁线路时建立的优化模型仍为多目标决策模型，在求解之前同样需要将问题转化为单目标问题从而实现模型的简化。（1）先不考虑出行费用和换乘次数的影响，在模型三的约束下，以出行总耗时最小为目标函数进行求解，将模型最优解记为，然后转到下一步对换乘次数的优化。（2）不考虑出行费用，在模型三的约束下，以换乘次数最少为目标函数进行求解。同时加入限制条件：将模型最优解记为，转到最后一步对出行费用的优化。（3）以出行费用最少为目标函数进行求解，再加入限制条件，。依据相同的原理，可以分别求解得出仅考虑公交线路下的最终目标为出行耗时最小和换乘次数最小的最佳出行路线，从而将多目标优化问题转化为单目标。这里就不再将这两类模型的简化过程列出，具体的简化过程见附录。4.3.3 模型求解同时考虑公汽与地铁线路时的最佳线路选择时，仍然使用搜索树算法对模型求解。当同时考虑公汽与地铁线路时，由于增加了两条地铁线路，我们将这两条地铁作为新增线路，添加进原来的L-S关系矩阵X和次序矩阵Y中，但此时并不需要增加地铁站点，而是通过地铁站点对应的公交站点表示地铁线路的走向。在关系矩阵X中，某一个地铁站用它周围相关联的公汽站来表示，那么，这些公汽站彼此之间的关系均为1；且某一地铁站周围的公汽站与这条地铁线路上其他地铁站附近公汽站的关系也为1，即它们都是相互之间可以直接到达的。 在次序矩阵Y中，地铁站点的次序也是通过它附近相关联的公汽站点表示的：在次序矩阵Y的第T1和第T2行中，同一地铁站点周围的公汽站以同一次序标号，虽然出现了同一次序号对应多个公汽站点的现象，但这正好用以达到公汽换乘地铁、地铁换乘公汽以及公汽和公汽通过地铁站进行换乘的目的。因为在算法的实施过程中，我们暂不加入费用尽可能少这一目标，而是通过耗时最小来决定最佳路线。但是，由于公汽和地铁之间可以实现连通，地铁站还可以用于公汽和公汽之间换乘的通道，这样会导致我们原来依靠次序来判断线路方向的方法出现混淆状况。因此，我们考虑增加判断条件，如下： 在搜索树上，若双亲结点与孩子结点的行号均为t1或者t2，那么运行时间为它们纵坐标之差乘以2.5。 公汽换乘地铁时，双亲结点的行号表示公汽线路，孩子结点的行号表示地铁线路，换乘时间上要多加。 地铁换乘地铁时，双亲结点的行号表示的是地铁线路，孩子结点的行号同样表示地铁线路，且换乘时间需多加。 地铁换乘公汽时，双亲结点的行号表示地铁线路，孩子结点的行号表示公汽线路，换乘时间加上。 当公汽通过地铁站换乘公汽时，相当于多加了一条树的分枝，这条多的枝的行号为地铁线路t1或者t2，且次序相同。而换乘点原有的行号和次序情况不变，即同一行内列号比其本身大。4.3.4求解结果根据前面的算法，用Matlab软件编程（程序见附录）得到三种情况的结果如下：换乘次数最少：起始站终到站换乘次数总耗时费用换乘站线路(1)S3359S182811013S1784L436下L167下或L217下(2)S1557S048121123S1919L084下或L363下L417上L254上或L312下或L447上或L460S2424(3)S0971S048511283S2184L013下L417下(4)S0008S00731832S0400L159下L474上(5)S0148S048521063S0036L308上L156上L417下S2210(6)S0087S36761652S3496L454上L209 下加入地铁线路并没有改变行驶线路，因此此时公交行驶路经站点情况与模型一中一样。总耗时最小：起始站终到站换乘次数总耗时费用换乘站线路(1)S3359S18284725S2027L484下L201下L481L027L167S2340S2705S1784(2)S1557S04813964S1919L084下L189下L460下L514S1402S0903(3)S0971S048521045S0567(D1)L094T1L395下D21(S0464)(4)S0008S00732703S0169L198L474L057S2083(5)S0148S04853865S1478(D2)L024T1L156L417D15(S2534)S2210(6)S0087S36760323T2当考虑地铁线路时，总耗时最小的路线只有第三、第五、第六条线路的选择发生了改变，此时公交行驶线路经站点情况如下：(3)S0971S0485（路线：L094T1L395下）S0971-S3571-S1609-S0345-S1419-S2389-S0567(D01)-D02-D03-D04-D05-D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21(S0464)-S0464-S0964-S3189-S2810-S2385-S0485（5）S0148S0485（路线：L024T1L156L417）S0148-S0927-S2830-S2070-S1487(D02)-D03-D04-D05-D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21(S0466)-S3189-S2810-S2385-S0071-S0485（6）S0087S3676（路线：T2）S0087(D27)-D28-D29-D30-D31-D32-D18-D33-D34-D35-D36出行费用最小：起始站终到站换乘次数总耗时费用换乘站线路(1)S3359S18282733S2903L015下L201上L041上S1784(2)S1557S048121123S1919L084下或L363下L417上L254上或L312下或L447上或L460S2424(3)S0971S048521063S1609L013下L140下L417下S2480(4)S0008S00731832S0400L159下L474上(5)S0148S048521063S0036L308上L156上L417下S2210(6)S0087S36761652S3496L231L097加入地铁线路并没有改变行驶线路，因此此时公交行驶线路经站点情况与模型一中一样。4.3 问题三模型建立考虑公汽、步行、地铁的最佳路线选择模型当考虑站点之间的步行时间时，为简化模型假设已知任意两相邻站点间的平均步行时间 ，并且只能按照公汽线路步行。引入01变量。当=0时，表示在第段线路上步行；当=1时，表示在第段线路上乘坐交通工具。当换乘总次数为（包括公汽换乘公汽次数，公汽换乘地铁次数，地铁换乘公汽次数，地铁换乘地铁次数），路线的起始站为，终点站为，中间的换乘点为，经历的线路编号为（含铁