公交线路转乘选择的优化模型本科毕业论文.doc

公交线路转乘选择的优化模型摘 要本文以奥运会的公交线路换乘为大背景，建立了在公汽线路、地铁以及步行三种方式中综合进行路线转乘的模型。此问题可以归结为两个站点之间的最短路问题，由于直接以站点构建最短路问题计算量较大，本文在处理三个问题时分别提出了相应的模型与求解算法，以乘坐时间最短为标准回答了问题一与问题二，对问题三提出了最短路模型。在问题一建模过程中，我们以任意两条线路是否可以直接换乘为突破口，建立了以每条线路为顶点，两条线路之间的换乘信息为弧的图，将问题一归结为弧长可变的最短路问题，提出了结合动态规划方法与分枝定界思想的算法。首先将题目所给出的路线与站点信息翻译为两条线路是否可以直接相交以及在何处相交的信息矩阵；其次以换乘时间最短或者费用最小为决策函数，建立动态规划问题；再次设计相应的算法进行求解。通过求解，以最短时间为目标，问题一的结果如下所示（以(1),(2)组为例，其它见正文表1）：组（1）：S3359S1828，最短时间73分钟，费用3元；组（2）：S1557S0481，最短时间106分钟，费用3元。同时文章对运算结果进行了相关分析。在问题二建模过程中，沿用问题一的求解思想，将新增加的地铁视为新的线路，将所有线路信息转化为新的转乘矩阵，同时按照新的背景得到新的乘车时间与费用计算方法，同样以最短时间为目标，相同的算法可以得到问题二的结果（以(5),(6)组为例，具体见正文表2）：组（5）：S0148S0485，最短时间87.5分钟，费用5元；组（6）：S0087S3676，最短时间28分钟（已经加上地铁站到地面站点的步行时间，其中地铁运行时间20分钟），费用3元。在问题三建模过程中，由于增加了步行的信息，问题一、二的方法无法直接使用，文章建立了一个新的最短路问题。以每个站点为顶点，以两个顶点之间的最短路径（最短达到时间或者最小到达费用）为弧构造有向图，其中最短达到时间由问题二得到的两个站点之间使用公交网络的换乘时间与步行时间的最小值决定。从而将问题三归结为一个有向图的最短路模型，文章对此模型给出了算法建议。最后文章对所提出的模型进行了优缺点分析与推广评价。关键词：城市公交线路、图与网络、最短路模型、动态规划一、 问题重述：近些年来，城市公共交通系统有了很大发展，使得公众的出行更加通畅、便利。绝大多数市民出行时首先会考虑选择公交设施，同时也面临如何在众多条线路中如何选择合适线路的问题。针对市场需求，要求开发一个解决公交线路选择问题的自主查询计算机系统，可以满足查询者的各种不同需求，对不同的起点和终点给出最佳的公交转乘路线。竞赛要求设计线路选择的模型与算法，解决以下三个问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。二、 问题分析：（1） 从影响出行选择的因素看，每个人主要会从两个标准对线路进行选择与优劣衡量：从起点到终点所需要的总时间最短；从起点到终点需要花费的费用。（2） 从本质上讲，选择线路的问题可以归结为最短路问题，但是考虑到转乘线路需要时间，并且一条公交线路不能按照站点进行拆分，因此以每个站点构造路线图不利于解决问题。注意到从起点站到目标站关键是选择乘坐哪些公交线路，需要在公交线路中如何选择转乘线路，因此可以以公交线路为顶点，以两个站点之间是否可以转乘为弧构造图，而点到点之间最佳路线的选择可以转化为经过分别两个端点的公交线路集合之间的最短路问题。同时我们需要任意两个线路之间是否可以转乘的信息。（3） 在给出的线路信息中，我们发现主要有三类线路：下行线路与上行线路不同，下行线路是上行线路的原路返回，环形线路。为了区分同一条线路不同的运行方向，我们人为地将每一条线路变为两条线路，这样做既可以分清楚所换乘的是那条线路的哪个方向，同时也可以将两条线路换乘点的信息与每个站点在本条线路上的位置相联系，这样可以用来判断乘坐某条线路公交车从某个站点出发时，可以换乘哪些公交线路（换乘站点必须在乘车点沿着公交车运行方向的后方）。（4） 在公交线路信息中，与决策目标有关的元素还有每条线路的计费方式及每条线路乘坐时花费的时间。对于计费方式，我们按照单一票价与分段计价进行识别，分段计价与乘坐的站点数有关，这也是我们需要每个站点在每条线路上具体位置的原因；同样运行时间也与站点的具体位置有关。（5） 问题一仅对公共汽车进行分析，可以转化为一个图论问题，使用动态规划方法进行算法设计与计算。问题二增加两条地铁信息后，对问题一模型的影响仅在于需要考虑线路数的增加，也只需要将地铁线路与公车线路是否可以换乘的信息表现出即可。问题三增加步行信息后，问题变得较为复杂，因为我们并不知道在哪些地方将会步行，因此我们采用简单列举的方法建立模型。三、 模型假设：1 乘客在乘坐公交线路过程中，以平均耗时为实际乘车、等车、转乘耗时；2 乘客在选择转乘线路时，考虑的因素有两个：花费的时间最少与费用最小；3 在计算换乘时间时，由公交车换公交车、地铁换地铁、公交车换地铁以及地铁换公交车时不单独计算步行时间；4 由起点所在站点直接乘坐地铁及从地铁直接到终点时，需单独计算步行时间。四、 符号说明及定义：衡量每条线路在每个站点是否停靠的01矩阵；：衡量每条线路经过的每个站点是从起点起算的第几站的矩阵；：线路的停靠站点向量：存储每条线路的收费信息；：停靠的所有公交线路的集合；：线路停靠的所有站点；：乘坐从其第站到第（）站的费用：表示从线路的第站到第站的时间函数：表示相邻公汽站平均行驶时间，本题为3：从站点经过一系列线路到达的总时间：从站点经过一系列线路到达的总费用：所有线路的转乘矩阵：公交线路，两两转乘集合；：为所有站点集合；：有向图中表示两个站点之间最短距离（最少时间或者最少费用）信息五、 问题一建模与求解一个城市所有的公交线路和停车点构成了一个复杂的网络图, 这些停车点可以看作该网络图的结点, 这些结点由相应的公交路线相连。 结点之间的边就是公交路线。 有的结点之间有边相连(即在某一条公交线上) , 有的结点之间无边相连(即这两个结点不在任何一条公交线上)。 因此, 城市的公交路线网络图非常复杂, 结点很多, 公交线路纵横交错。描述公交线路网络的一个简单方法是以每个站点为顶点，以两个顶点之间的公交线路信息（需要花费的时间、花费的费用等）为弧建立赋权图，本题中站点个数共有3957个，这样得到的矩阵将是3957阶方阵，如此庞大的矩阵在使用计算机处理时，将会遇到很大的困难，我们所拥有的计算机硬件达不到要求。因此我们需要从另外一个角度重新描述公交线路网络。进而我们可以使用通过动态规划方法、最短路方法等建模思想构造算法、编写程序，使问题得到圆满地解决。5.1 原始数据处理（1）公交线路处理我们将题中给出的520条公交线路进行处理，将每条线路人为地变成两条，每一条代表一个具体的行驶方向，得到1040条起点终点固定的单方向行驶的公交线路。具体的处理方法如下：a) 对于上行与下行站点相同的线路，如图1中(a)，将上行与下行视为不同的两条线路，每一条作为一条新的单方向行驶的公交线路，即及；由于两个走向站点相同，因此这两条线路经过的站点集合相同，但是每个站点在两条线路中的位置不同，这对衡量从某个站点出发乘坐该线路是否可以换乘其他线路，以及换乘哪条线路非常重要（详细说明见后续命题）；b) 对于上行与下行站点不同的线路，如图1中(b)，将上行方向与下行方向视为两个不同的线路及，这两条线路经过的站点集合不同，从而每个站点在两条线路中的站点位置也不同；c) 对于环形线路，如图1中(c)，起点与终点为的环形道路，从中间某个站点断开，作为前一路线的终点以及后一路线的起点，这样就形成两条新的线路。由于环线中间某些站可能重合，因此分割线路时要保证同一线路中没有公共站点（编程设计的需要）并且兼顾两条新线路长度均等。AB（a）AB（b）（c）A图1通过以上处理，我们将所有情况统一转化为以起点和终点确定的1040条具有单一方向的有向线段。（2）建立站点与线路关系矩阵利用（1）得到的1040条线路及其上每个站点的信息，构造下列两个反映1040条线路与3957个站点相关信息的矩阵，称为停靠信息矩阵：与。为1040行3957列的矩阵，元素为0或者1，反映每条线路是否经过每个站点，元素取值为：。也为1040行3957列的矩阵，元素为0或者某个自然数，反映每条线路经过每个站点时，从该线路的起始点算起，该站为第站，元素取值为：。定义向量为线路的停靠向量，为线路停靠的站点集合：。为停靠站点的公汽线路集合：。（3）每条线路的计费信息定义向量为每条线路的计费信息，按照题中所给出的计费信息，元素取值为。若，则线路为单一收费，票价均为1元；若，则线路为分段收费，按照题中所给定的公汽票价方案，可以得到乘坐从其第站到第（）站的费用为，其中。可以发现单一收费情形可以并入上述公式，因此所有公汽线路（包括单一收费与分段收费）的费用计算可以合并为一个函数，其中。称函数为沿着公交线路从其第站到第站的费用函数。相应于费用函数，用函数表示从该线路的第站到第站的时间函数，其中表示相邻公汽站平均行驶时间，在本题中取值为。5.2 判别两条线路之间是否可以换乘，得到任意两条线路之间的换乘矩阵命题1：乘客从出发，乘坐线路可以直接到站点的充要条件为，并且。同时可以得到花费的时间为花费的车费为。命题2：设线路的停靠向量为, 的停靠向,那么，线路可以转乘线路的充要条件为中有元素2，并且2所对应的站点为到的中转站。证明：按照停靠向量的定义，均为元素为0或者1的向量。因此若的第个分量为2，则，说明两条线路在站点相交，从而可以在站点处换乘。定义：设与在处相交，,在上为第站，在上为第站，则称二元数对为线路到的换乘数对，记。若与不可换乘，则记；同时。注意到换乘数对与换乘线路之间的关系，若为线路到的换乘数对，则为线路到的换乘数对。将所有线路之间的换乘信息构成矩阵，称此矩阵为换乘矩阵，记为，。同时集合表示能够与实现直接换乘的线路集合。命题3：设线路到线路的换乘数对为乘客从站点出发，乘坐线路，通过换乘线路，到达站点的充要条件为在中存在一个换乘数对，使得且。同时,花费时间为：，其中表示公汽换乘公汽的时间，在本题取值为。花费费用为。命题4：若经由转乘再转乘到，而，分别为到，到的换乘数对集合，则必存在，使得，同时，花费时间为花费费用为。按照上面所述的四个命题的规律，可以得到具有任意条中转线路的公汽路线的条件以及所花费的时间与费用。命题5：若乘客从出发，通过换乘线路，到达，则 必存在个换乘数对使得：（a），；（b）（c）同时花费的时间为花费的费用为。5.3 任意两点之间寻找换乘方式的动态规划模型利用5.1中所得到的元素，构造反映任意两条线路之间的换乘图，如图2所示，其中图的顶点表示每一条线路（一共有1040个顶点），而两个顶点之间的弧表示两个顶点的换乘信息。L1L2L3LjL1040Ljtr(i,j)图2 所有公汽线路的换乘图需要说明的是，由于与与的顺序有关，因此在后续提出的动态规划模型中，将按照计算的次序与换乘线路的先后次序将换乘图配上不同的方向，这些方向与计算以及花费的时间与费用有关。假设某个乘客需要从站点通过公汽网络到达站点，则我们需要寻找从公汽集合到达集合在上述换乘图中的最短路径，这样问题一可以归结为下面寻求最短路问题：寻找换乘线路，使得，乘客从出发，可以通过此线路到达（满足5.2节中命题5），并且在所有可能的转乘线路中在下列两个目标下最优：（a）所花费的总时间最短；（b）所花费的总费用最小；这两个目标函数由5.2节命题5给出。5.4 求解问题一的算法由于上述最短路问题中所涉及的数据量较大，并且不同于传统最短路问题之处在于在图中我们得到的并不是相邻两点的路径，而是可以换乘的两条线路换乘的信息，因此不能直接用求解传统最短路问题的算法，如Dijstra算法进行计算。为了解决上述问题，我们给出下列算法，算法的主要思想如下：i. 使用动态规划的顺序或者逆序算法，将求解此问题的三个主要方面：a) 判断是否能在所给出的两点实现换乘；b) 计算每次换乘所需要的时间与费用；c) 判别是否达到时间最短或者费用最小结合在一起。ii. 在算法设计过程中，采用整数线性规划的分枝定界思想，以换乘的次数为分枝变量，以已经实现换乘情形下的时间或者费用为定界变量，实现在增加换乘次数的同时判别没有到达终点的换乘序列是否可能达到最优，即若当前存储实现成功换乘的最短时间或者最小费用为，则以为剪枝标准，在没有达到终点的线路中，如果所花费的时间或者费用已经超过，则不需要进一步换乘寻找。算法I（给定起点与终点，判别两个站点是否在同一条线路上）1） 分别求出停靠与的所有线路集合，；2） 若，则退出；3） 若，则对任意的线路，计算所需时间与费用；4） 返回最小的时间或者费用，以及对应的线路。算法II（给定公汽线路停靠信息矩阵、换乘矩阵，计算任意起点到终点的最优路径）：1) 输入起点，终点，对最短时间后者最小费用变量赋初值，；2) 按照算法1，判断，是否在一条公汽线路上，若在一条线路上， ，存储乘坐信息，否则转下一步；3) 写出，；4) 对任意的，按照换乘矩阵写出能够与进行换乘的所有线路，按照5.2节命题3判断中的线路能否实现一次换乘到；5) 若存在能够一次换乘到的线路，计算需要的最短时间或者最小费用，转6），否则转7）；6) 若，则或者若，则，存储换乘信息，否则转7）；7) 对于不能实现换乘一次到达的线路中，计算通过能够换乘到的线路得换乘点需要的时间或者费用，或者，以或者为标准判断，若或者，则从下一步搜索路线集合中删去此换乘方式；8) 令为7）剩下的路线集合，返回4）；9) 输出或者，以及换乘信息集合。5.5 问题一的求解结果利用MATLAB实现上述算法，并将此算法用来求解题目中所给出的六组换乘站点，求解结果如下表（由于结果较多，在表中仅列举出一种，在表后将进行适当的评价）：表1. 问题一求解结果序号换乘站点对以时间最短为目标结果及对应时间与费用（1）S3359S1828最短时间73分钟，费用3元（2）S1557S0481最短时间106分钟，费用3元（3）S0971S0485最短时间106分钟，费用3元（4）S0008S0073最短时间67分钟，费用3元（5）S0148S0485最短时间106分钟，费用3元（6）S0087S3676最短时间46分钟，费用3元对问题一结果的评价：a) 在所有得到的以时间最短的最优解中，费用均为3元。通过检验，6组站点对都不能实现直接达到，因此即使存在换乘一次的线路，所需要的费用至少为2元，这与最终每个时间最短的最优解花费3元相比，相差不大，因此我们在求解过程中主要以时间最短为优化目标。b) 在对每个站点对进行最优求解时，都存在出现多个最优解的情况，如第1组S3359S1828，出现了换乘线路不完全相同的50个最优解，下面列举出其中的4个：，时间为73分钟，花费3元；，时间为73分钟，花费3元；，时间为73分钟，花费3元；，时间为73分钟，花费3元；通过比较上述四条线路与表格中所选择的最优线路，可以发现所用时间与费用完全相同，比较换乘的公交线路，有很多相同的地方，这说明这些线路之间存在多个换乘点，换乘站点数的增加可以方便乘客出行，但是也暴露出公交线路站点重复的问题，因此从长远看，通过问题一可以给公交部门一个改进公交线路设计的参考方案。c) 从人的心理出发，一些乘客在乘车时有时会以换乘次数少为选择路线的标准，问题一的结果表明换乘次数少并不能够得到最经济或者最节约时间的换乘方式，如第三组站点对S0971S0485可以实现换乘一次S0971S2184S0485，但是需要128分钟，费用也为3元，此换乘方式与我们最终采用的二次换乘方式相比多用了22分钟，而费用完全相同；同样第4组也可以实现换乘一次S0008S0291S0073，花费时间83分钟，费用2元，与换乘两次的最优结果相比较，虽然少花1元，但是时间多用了16分钟。六、 问题二建模与求解6.1 问题二分析与问题一相比较，问题二种涉及的乘车方式多了两条地铁线路，因此我们采用的建模思想与算法与问题一的类似，只是对计算换乘时间与费用的公式有所修改。观察所给的数据，地铁线路的信息与公汽信息有所不同，公汽给出的是行走路线，而地铁线路给出了每个地铁站点可以换乘的公交线路。但是仔细考察问题一中算法实现的过程，我们也只需要能够把地铁信息翻译为地铁与地铁、地铁与公交线路是否可以换乘的数据。同时按照题中所给出的假设“同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)”，在给出地铁信息后，公汽线路的换乘矩阵需要进行相应的修改。而得到所有地铁与公汽线路的换乘矩阵后，可以直接调用问题一的算法进行求解。6.2 问题二原始数据处理增加地铁信息后，我们按照题目要求对原有的信息进行了适当的处理，具体描述如下：（1） 按照行驶方向不同，将地铁T1人为处理为两条线路：T11：D01-D23；T12：D23-D01。这样做的目标也是能够将T1地铁的两个行驶方向按照站点的顺序考察与每个公汽线路换乘信息。（2） 地铁T2为环形线，我们人为处理为四条线路：T11(D24D25-D39); T22(D24D39-D25);T23(D32D18-D39D24-D31)T24(D32D31-D24D39-D18)。这样分割保证每条线路有18个站，同时每条线路没有相同的站点。（3） 由于地铁给出的信息是每个地铁站点可以换乘到哪些公交车站，因此我们在考察每条地铁可以与哪些公交车换乘时，调用问题一中经过可以换乘公汽车站的线路，如地铁T1在D01车站可以换到三个公汽站点S0567，S0042，S0025，这说明T11可以在第1站与经过S0567，S0042，S0025的所有公汽线路，即集合中的公汽线路实现换乘；而T12可以在其第23站与相同集合中的公汽线路进行换乘。同样的方式可以得到每条地铁与每个公交线路的换乘方式。（4） 按照假设“同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)”，原有公汽线路之间的换乘矩阵需要进行适当的修改，比如T1线路在D01站点可以换到S0567，S0042，这样所有经过S0567的线路集合中的所有线路都可以与经过S0042的线路集合中的所有线路在该站点实现换乘。（5） 收费方式的处理，由于地铁票价为单一计费方式，并且地铁线路之间进行换乘也仅需要支付3元，因此在计算线路费用时，只要有地铁线路存在，仅计单一费用3元。（6） 花费时间的处理，与问题一相比，仅需要在考虑换乘时注意是否有地铁存在。以分别表示公汽换地铁、地铁换公汽、地铁换地铁所需要的时间，在本题中取值为。在进行具体乘车线路需要时间计算时可以按照不同的换乘方式进行适当填加。如换乘路线为SmSkS1487D02D06S0394Sl，则总的时间为（7） 使用与问题一同样的分析方法，我们可以建立类似的换乘图，在图中，顶点表示所有的公交线路与地铁线路，任意两点之间如果可以实现换乘，则给出换乘集合，不能换乘记为，这样可以形成类似的换乘矩阵，对此换乘矩阵应用问题一给出的算法I，II进行求解，所不同的是计算花费时间或者费用时需要按照有地铁情形下进行修正。6.3 问题二求解结果使用问题一中的算法I，II对修改后的换乘矩阵进行求解，得到下列换乘方案，如下表2。表二 问题二求解结果序号换乘站点对以时间最短为目标结果及对应时间与费用（1）S3359S1828最短时间73分钟，费用3元（2）S1557S0481最短时间106分钟，费用3元（3）S0971S0485最短时间96分钟，费用5元（4）S0008S0073最短时间55分钟，费用5元（5）S0148S0485最短时间87.5分钟，费用5元（6）S0087S3676最短时间28分钟（已经加上从地铁站达到地面站点的步行时间，其中地铁运行时间20分钟），费用3元6.4 问题二求解分析分析问题一与问题二的结果，我们可以得到下面几个结论：（1） 地铁线路的存在使得乘客出行有了更多的选择，同时地铁的快捷也使得换乘的时间减少，从问题二的结果可以发现(3)-(6)四组换乘线路中均涉及到地铁线路。因此大力发展地铁等快捷公共交通系统将为市民的出行带来极大的便利。（2） 在问题求解中我们也发现(1)(2)两组站点最终选择的最优路线与问题一的结果相同，仔细分析两组站点所经过的公汽线路很难与地铁线路换乘，这也说明了地铁网络的欠发达。（3） 地铁线路成为市民选择出行路线时主要考察的换乘通道，换乘地铁可以减少大量的交通时间，但是也提高了费用，虽然说仅提高了2元，但是对于每天出行的市民，费用也将成为他们考虑的一个因素。因此对于每个城市的交通部门来说，对地铁进行合理的定价，在保证健康运行的前提下，减少市民出行的费用支出，将是更为重要的问题。七、 问题三模型建立7.1 问题三分析问题三假设知道所有站点之间的步行时间，要求给出任意两个站点之间的线路选择问题。给出步行信息后，任意两个站点之间的换乘将会多一种选择，如果与问题一、问题二一样将步行作为一条线路，将会给模型建立带来一定的难度，由于我们不知道在哪些站点到哪些站点之间需要步行，并且“步行”这条线路将与每条公交线路在任意该线路上任意站点相交，前面两个问题所用的算法将无法实施。因此问题三的解决需要采用不同的模型。考虑到步行涉及到所有两个站点，因此我们从站点之间的最短路出发进行建模。7.2 问题三模型建立以每个站点为顶点，任意两个顶点之间的最短时间或者最小费用为边建立有向图如下图3。S1SjS3957S2Sieijeji图3 任意两个站点之间的最短网路图以表示该图，其中顶点集合，弧矩阵，其中元素表示由站点到站点的最少换乘时间或者最少费用，以及取此值的换乘方式。在中包含两个信息：从到的最少时间以及表明得到此最少时间对应的换乘或者行走方式。这样我们将问题三转化为求任意两个站点的最短路问题，可以使用最短路的一些算法进行求解，由于模型涉及数据比较庞大，无法求解。在构造最短路模型时，最重要的是决定任意两点之间的最短时间或者最少费用，即的取值，详细说明如下。（1） 以最少时间为目标情形下的弧长计算假设到的步行时间为，显然。设表示利用公交系统线路换乘时从到的最短时间，该数据可以利用问题二的计算方法得到，同时我们也可以得到此最短时间对应的换乘方式。由于每条线路上下行影响，有可能，的情形，因此将会出现。按照下列方式确定：若，则；若，则。以的第一个时间分量进行最短路求解，得到到的最短时间（可能会涉及到“乘车步行乘车”方式，从题意理解，这是允许的），进而按照最短时间对应的最短路，确定最终的换乘方案。（2） 以最少费用为目标情形下的弧长计算若以最小费用为标准，则最佳的换乘方式就是步行，因此以最少费用为单一目标没有必要进行最短路计算。（3） 以最短时间与最少费用为两目标进行换乘决策分析在现实中，可能会存在最短时间与最少费用的两目标决策，此时可以根据市民对两个目标的不同倾向建立综合两个目标的单目标规划模型，如以最少费用不高于某个给定数值为条件进行决策等。八、 模型的评价及优缺点分析8.1 模型的评价与推广论文对三个问题分别提出了各自的模型及求解方法，问题一、二相似程度较高，因此完全采用同样的方法解决，所不同的是问题二将地铁信息转换为线路换乘信息时与问题一有所不同。问题一给出的算法可以用来求解任意一个公交系统的路线换乘问题，可以相对精确地给出任意两个站点之间的转乘路线，但是随着公交网络的不断扩大，计算量也在不断加大，这对计算机的硬件配置提出了更高的要求。再问题一与问题二的求解过程中，我们将每条线路都人为处理为两条，这对衡量线路与线路之间在何处换乘，以及起点及终点在线路中的位置非常重要，这样做保证了任意两条线路换乘信息的正确性。本文提出的算法是基于最短路图论问题的动态规划方法，同时也结合了不断判断剪枝的思想。由于问题所涉及到的信息较大，此算法在进行计算机实现时对编程能力要求较高。本文给出的结果主要是依据换乘时间最少为目标进行算法设计与模型求解，此算法有下面几个方面的推广：（1）综合换乘次数、时间最短与费用最小三个方面进行建模分析。应当说这三个因素对应于不同的需求群体，一个好的模型应当能够在三个不同情况下给出各自的选择结果。（2）此模型仅给出了任意两个站点的最佳换乘方式，对此模型加以推广，是否可以使用此模型对某个城市的公交体系进行衡量，从公交线路的设置、票价的设置等方面对现有公交线路进行适当的改善。8.2 模型的优缺点分析本模型的优点如下：1、此模型及算法不但可以为乘客提供公交线路的优化选择,而且可以作为检验城市交通线路布局是否合理的检验标准，提供对公交线路的结构进一步改进的方案。如果进一步发展改进，应该具有很好的市场应用前景。2、模型使用的算法结合了动态规划方法与分枝定界的基本思想，两种方法的综合使用降低了搜索判断的时间。3、通过得到换乘矩阵使得在进行算法求解时，可以将最少时间与最少时间路线一起求出，同时也为判断起点与终点是否可以通过某些路线换乘提供了非常有价值的信息。本模型的缺点：1、由于数据量大，因此在处理时可能产生些错误，这可能给结果造成误差。2、模型主要以最少时间为目标进行求解与算法设计，没有考虑其他因素，模型在实用性方面需要进一步的改进。3、在处理原始数据时，由于数据量较大，而MATLAB处理数据的能力有限，只能将原始数据拆成几个部分分别处理，缺乏系统性。九、 参考文献1 肖位枢，图论及其算法M . 航空工业出版社, 199212 胡良剑，孙晓君等，MATLAB数学实验，高等教育出版社，20063 姜启源等，数学模型，高等教育出版社，20034 朱德通，最优化模型与实验，同济大学出版社，20035 韩中庚，数学建模方法与应用，高等教育出版社，20056 韩中庚，数学建模竞赛获奖论文奖精选与点评，科学出版社，2007附件一：问题一计算结果表表1. 问题一求解结果序号换乘站点对以时间最短为目标结果及对应时间与费用（1）S3359S1828最短时间73分钟，费用3元（2）S1557S0481最短时间106分钟，费用3元（3）S0971S0485最短时间106分钟，费用3元（4）S0008S0073最短时间67分钟，费用3元（5）S0148S0485最短时间106分钟，费用3元（6）S0087S3676最短时间46分钟，费用3元 附件二：问题二求解结果：表2.问题二求解结果序号换乘站点对以时间最短为目标结果及对应时间与费用（1）S3359S1828最短时间73分钟，费用3元（2）S1557S0481最短时间106分钟，费用3元（3）S0971S0485最短时间96分钟，费用5元（4）S0008S0073最短时间55分钟，费用5元（5）S0148S0485最短时间87.5分钟，费用5元（6）S0087S3676最短时间28分钟（已经加上从地铁站达到地面站点的步行时间，其中地铁运行时间20分钟），费用3元附件三：算法源程序代码（MATLAB语言）i. 有地铁转乘程序function f=f2(a,b,aa,bb,cc)tmin=5000;A=aa;B=bb;C=cc;m,n=size(A);n=1;d=150,224,225,226,273,381,393,3,4,9,20,23,24,30,31,32,34,35,36,41,45,48,49,52,55,60,61,67,69,70,73,74,76,78,80,83,86,87,89,92,93,95,96,101,102,106,107,108,110,111,113,114,117,120,126,136,138,143,144,146,147,149,151,153,156,158,161,162,165,168,169,172,173,174,176,178,179,181,182,183,185,188,193,195,197,200,202,203,206,207,208,209,212,213,214,215,216,217,219,220,228,231,234,235,237,238,239,241,243,245,246,247,250,251,252,253,254,258,265,268,269,270,272,274,278,279,281,284,288,291,292,293,294,298,303,306,307,310,313,316,319,322,326,327,328,333,334,335,336,341,342,343,344,346,349,350,352,356,357,362,364,367,369,370,371,376,379,380,383,385,388,389,390,394,396,397,398,399,400,402,403,404,407,408,410,412,414,416,420,421,426,425,431,432,433,434,438,444,445,451,452,453,455,458,459,462,463,466,467,471,472,479,480,483,487,488,489,490,491,492,493,494,495,499,500,501,504,505,506,507,508,509,512,514,515,517,520;d1=2.*d;d=d1-1,d1;%单一票价的线路e=1041,1042,1043,1044,1045,1046;for i2=1:m if A(i2,a)=1 & A(i2,b)=1 t2=B(i2,b)-B(i2,a); if t20 ans(3,n)=i2;%线路 ans(1,n)=t2*3;%时间 if any(d=i2) ans(2,n)=1;%价钱 elseif t220.1 ans(2,n)=1; elseif t21 tmin=min(ans(1,:);endbus1=find(A(:,a)=1);bus2=find(A(:,b)=1);for i3=1:length(bus1) for j3=1:length(bus2) if C(bus1(i3),bus2(j3)=1 sum0=A(bus1(i3),:)+A(bus2(j3),:); lap=find(sum0=2); for k3=1:length(lap) c=lap(k3); t31=(B(bus1(i3),c)-B(bus1(i3),a)*3; t32=(B(bus2(j3),b)-B(bus2(j3),c)*3; if t310 & t320 & t31+t32tmin ans(3,n)=bus1(i3);%线路 ans(4,n)=bus2(j3); ans(6,n)=c; if any(d=bus1(i3)%价钱 mon31=1; elseif t3120.1 mon31=1; elseif t3120.9 mon31=2; else mon31=3; end if any(d=bus2(j3) mon32=1; elseif t3220.1