数学建模07全国二等其一.doc

论文点评：本文建立模型及算法描述详细清楚、结果正确。本文的特点是采用了一些技巧来处理数据存储问题，使存储量大大减少，而且数据结构对算法设计有很大好处。本文对算法结果的分析也很全面。本文缺点是算法不容易推广到多次换乘方案的求解，因为这会导致计算量出现过快增长。全国数学建模竞赛二等奖论文公交线路查询的计算机算法吕旸 刘俊江 齐弘宇 指导教师： 熊春光 摘要：本文建立模型的目标是最少的存储空间和最快的运行速度，以及兼顾其他因素。讨论并解决了包括换乘在内公交线路查询问题，并改进模型让模型能更加广泛地通过计算机编程来实现。为了减少模型的存储空间，我们构建了动态分配的数据结构，通过利用每一块存储单元，来减少存储空间，使得本模型可以应用于小型的系统上。此外，小巧的存储结构能减少搜索的次数，提高了算法的执行效率。在提高模型运行的效率的方面，设计了搜索算法和择优算法，分别对每个算法进行了优化，并利用先前的搜索结果。最后将两套算法融合成一个整体。根据题目的实际情况以及数据的特点，减少搜索过程，降低了搜索的次数，使模型可以采取更为方便快捷的搜索方法，提高了查询效率。选择最佳乘车路线时，在研究乘客选择线路心理的基础上，充分考虑到了换乘次数、行程的时间、行程的价格，并引入了站点环境因素的概念，即根据站点停靠线路的数目确定站点的繁华程度，设定了一套评定站点繁华程度的体系以及评定方法，为这些因素设定了判定等级，分别输出直达、换乘一次、换乘两次的最优路线，方便乘客根据自身的需要选择乘车路线。整个模型的设计采用了层层递进的方式，在构建模型方面先考虑只有公交车的情形，建立出一套公交路线查询模型，并进行了优化。然后在此模型的基础上，把地铁看作特殊的公交车加入到此模型中，且作了适当的修改。最后将此模型扩展到包含了步行等因素的更为一般化的情形中。在模型建完后，利用自己设计的算法编出了一个公交路线查询的软件，该软件能够实现前两种模型的功能，并利用该软件分别对题中所给的数据进行了处理，得到了合理的结果，在文章的结尾对这些结果进行了详细的分析，讨论了加入实际因素的情形。最后利用该模型所得到的结果对公交状况进行了分析。关键字：公交查询 软件设计 运行效率 存储空间 最优路径站点环境 1问题的重述公交网络作为城市最重要的交通运输工具，对一个城市的繁荣发展和城市的运行效率起着至关重要的作用。北京市作为中国政治、经济、文化中心，同时又是2008年奥运会的主办城市，公交运输无疑将成为北京市市民、游客最主要的出行方式，然而像北京这样的大型城市，公交系统通常都错综复杂，且还包括地铁等多种交通工具，设计一套公交出行的查询系统成了一项很有意义并且相当必要的任务。根据城市交通查询的需要，必须考虑到换乘次数，出行时间以及费用等多方面的因素。为了使问题更好地被解决，可以通过以下三个层次考虑设计交通查询系统：1.1 公交车模型在公交系统中，先不考虑地铁的作用。首先建立简单的模型，对于一套简单的公交系统，我们可以仅考虑公交线路，得到任意两个站点间的出行路线，再将这样的模型扩展到更为一般的情况。显然，这样的路线必须首先考虑到乘客的方便程度，即行车的换乘次数，出行所需要的时间，然后是出行花费等因素。任意两个站点间的行车方式众多，因此查询系统必须给出考虑到多方面因素的优化路线。1.2 包含地铁的模型在1.1中，我们得出了仅考虑公交车的模型。现在可以将地铁也包含在这个模型中了。加入地铁将使得这个问题更为复杂，因为这将不得不考虑到换乘地铁与换乘公交车间的取舍，怎样在保证尽可能短时间的前提下，降低出行的费用以及选择停靠线路较多的换乘车站。这个问题的解决将有助于提高这个模型应用的广泛性。1.3 更加一般化的模型以上两个模型显然忽略掉了很多实际的情况，比如说有这样的一条路线：图 1.1-考虑行走情况的示意图ADBECFHG如上图所示，假设有一路公交车走的是如图所示的路线，它的路线是逆时针方向运行的。从B到G需要经过5个车站，这样就需要15分钟。而实际上B，G之间的步行距离可能很短，这样就根本用不着公交车经过这样一个复杂的线路。因此，在选择乘车路线的时候必须把步行的因素考虑在内，得到一个更加符合实际情况的模型。2模型的假设和参数的说明2.1假设的情况为了使问题便于研究，做一些假设是必要的。这些假设将忽略一些次要的因素，使得问题更加清晰明了：假设1：任意两个相邻公交车站点间的距离为定值，并且每辆公交车的运行速度相同，也就是说每两个站点间行走的路程与花费的时间都是相同的。假设2：任意两个相邻地铁站点间的距离为定值，并且每列地铁的运行速度相同，也就是说每两个地铁站点间的路程与花费的时间都是相同的。假设3：若终点站有多条路线的公交车可到达，则可以认定这些公交车到达的是同一个公交车站，也就是说下了公交车就是目的地，而不需要步行。如果是中转站，则要考虑不同站点间步行所花费的时间，并且设定这一个时间是定值。假设4：同一地铁站对应的任意两个公交站间可以通过地铁站换乘(无需支付地铁费)。假设5：环形线路分为顺时针环形和逆时针环形，并且这两条路线分别属于不同的公交车，如果从顺时针线路换为逆时针线路则作为一次换乘。假设6：除了环形线路以外的公交车如果到达终点再次开出则算为一次换乘。2.2参数的说明l 任意相邻两个公交车站点间的平均行驶时间（包括停站时间）为3分钟l 任意相邻两个地铁站间的平均行驶时间（包括停站的时间）为2.5分钟l 公交车与公交车间的换乘时间为5分钟（其中步行时间2分钟）l 地铁与地铁间的换乘时间为4分钟（其中步行时间2分钟）l 地铁换公交车时间为7分钟（其中步行时间4分钟）l 公交车换地铁的时间为6分钟（其中步行时间4分钟）l 公交车的票价分为单一票价与分段计价两种：分段计价的票价：0-20站： 1元21-40站：2元40站以上 3元单一票价： 1元l 地铁的票价为3元（地铁换乘地铁不另外收费）2.3数据中的约定在题目中，给出了数据的附表，然而数据的格式不利于处理，因此必须对数据的格式以及符号做相应的变化，为了便于存储，把数据中的中文字体全部变成数字的格式，在此我们约定：l 分段计价用0表示l 单一计价用1表示l 去掉“上下行”l 环线则在路线的前面加一个0。例如：删除图 2.1数据约定示意图2.4 符号的约定l 在一条线路中，S1代表的出发车站在该线路中的站点编号（即在该线路中的第几个车站），S2则代表目的地车站的编号。l P代表站点的繁荣度。3模型的建立3.1乘客的需求分析由于此模型是为了方便乘客查询公交路线的而设计的，因此模型必须建立在乘客需求的基础上。本模型在建立前首先考虑了决定乘客选择线路的因素，通过查找资料1获得如下表所示的调查：表3.1-乘客出行心理统计表根据表中信息所示，本模型将主要考虑以下因素作为影响乘客选择出行路线的依据：换乘次数、乘车时间、乘车路程、乘车费用。此外，考虑到2008年奥运会，将有大量的外地游客和国际友人来到北京市观看比赛，我们特别加入了站点环境因素。例如，当一个外地游客（尤其是不知道城市交通网络信息的乘客），希望换乘车站是一个大站（大站一般都有很多的公交线路通过，且一般都处于城市中较为繁华的地带），模型将会考虑到这种情形。考虑到乘客的不同需求，模型将给出所有换乘路线的最优路线：l 直达路线：由于大部分的乘客都不愿意换乘公交车（换乘通常情况下较为麻烦），因此首先给出无需换乘的方案：综合考虑乘车时间、乘车路程、乘车费用、换乘车站的环境等因素给出最优的三条路线。l 换乘一次的路线：虽然直达车很方便，但是有时候直达车可能意味着花费更多的时间、金钱和行走更长的路程或者根本就无法直达，因此模型将在换乘一次的基础上综合考虑乘车时间、乘车路程、乘车费用、换乘车站的环境等因素给出最优的三条路线。l 换乘两次的路线：同换乘一次的原因相同，换乘两次的路线可能比前两者的选择更具有效率，因此我们将综合考虑乘车时间、乘车路程、乘车费用、换乘车站的环境等因素给出最优的三条路线。l 推荐最优路线：由于三次及三次以上的换乘在现实生活中很少发生，因此本模型不予以考虑。当给出上述三个标准的换乘方案后，模型将会综合考虑换乘次数、换乘时间、换乘路程、换乘费用、换乘车站的环境等因素给出一个最优的换乘线路。当然模型将会给出所有路线所需要的时间，路程以及费用等信息，乘客可以根据上述的信息从中选择符合自己需要的路线。比如有的乘客（例如游客）想欣赏沿途的风景而放弃选择乘坐地铁，虽然地铁有可能更省时间。3.2公交路线的分析分析题目中的信息，所有的公交路线可以分为以下三种类型2：l 上下行路线相同（即完全的双向路线）ABCDGFE图 3.1-公交路线上下行相同的示意图这种路线是公交车的上下行路线完全相同的情况，公交车能够往返于图中标注的任意两个站点。如图所示，上行路线是A-B-C-D-E-F-G，下行路线是G-F-E-D-C-B-A。 l 上下行路线不相同的情况FFGHIABCED图 3.2-公交路线上下行不同的示意图A这种情况通常会形成一个回路，假设上行线以A位起点，F为终点站，则公交车先从A站出发沿途经过B-C-D-E四个站点，最后到达F站点。此时公交车再以F站为起点，此时算作一次换乘，然后再经过G-H-F-I回到A点。然而在这种路线中，公交车只能按照固定的方向行驶，如图，乘客能从B站直接到达C站，然而无法从C站直接到B站。FEAB另外，也有这样情况的路线：IHGDC图 3.3-公交路线上下行不同的示意图B在这种线路中，假设上行线路是A-B-C-D-E-F，下行路线是F-E-G-H-I-B-A，其中在B-E中间的路线上下行出现了不同，而起始点和终点的一段路程相同。同样，公交不能逆向行驶，这样乘客不能从D站直接返回C站。l 环形线路图 3.4-公交路线环形示意图HFGACBDEIF环形路线的样式似乎与上下行不同的路线A相似，然而实际上环形路线包括了顺时针环形和逆时针环形两部分，比如，乘客能从A站到B站，也可以直接从B站返回A站。当然如果乘客从A站到达B站，再乘坐公交车从B站返回A站，则需要一次换乘。3.3建立存储的数据结构为了处理庞大的数据，模型需要创建合理的数据结构来接受所给出的数据，问题的关键在于建立什么样的数据结构34，使得接下来的搜索算法更为简单快捷，并且最大限度的减少存储空间。这样可以扩大本模型的适用范围，把这种算法应用于存储空间有限的小型设备中。具体的数据结构如下图所示：表 3.2存储结构表编号123站点表头路线表头经过该站点的线路数记录下一节点的位置1计价方式记录下一节点的位置线路信息站点信息记录下一节点的位置节点信息A节点信息B该线路经过站点的序号记录下一节点的位置2节点信息C节点信息D节点信息E3节点信息F节点信息G节点信息H整个存储结构由一个行和一个列作为表头指引节点信息，其中路线表头指引着路线信息，例如整个编号为1的行就是线路L001的信息，表头的每个元素有两个信息组成，第一个信息记录着该路线公交的计价方式，第二个信息指向该公交路线的首发站；站点表头的每个元素也有两个信息组成：一个用来记录经过该公交车站的线路数目，另一个信息指向停靠在该站编号最小的线路。节点信息如图所示：图 3.5-节点储存示意图 每个节点元素将记录五条信息，线路信息记录着该节点所属的线路编号，站点信息记录着该节点所属的站点编号，站点的序号记录着该节点的站点在所属线路中的序号（即它是第几个停靠的公交车站），但我们约定环形路线的序号全部为0。图 3.6节点连接示意图从每一行来看，路线表头连着一连串的节点信息，它们的顺序就是该线路所经过公交站的顺序，第一个节点是该线路的起点站，最后一个节点是该线路的终点站。节点信息的长度由该线路所经过的公交车站的数目决定。节点信息A路线表头节点信息B节点信息C图 3.6-节点连接示意图如上图所示假设该公交路线只有两个站点A和B，则节点A就存储A站点的信息，节点B就存储B站点的信息，而节点C因为没有站台了，所以就不分配存储空间了，这样就节省了大量的存储空间（毕竟没有必要为每个线路分配接近4000个站台的存储空间）。并且该站台的信息存储是按照该线路停靠的顺序存储的，仍然以图3.6为例，假设一条线路经过的车站为S0003,S0002,S0001。则节点A存储S0003,节点B存储S0002,节点C存储S0001。但是，按这样的方式存储存在一个问题，就是站点表头如何对应。因为节点信息存储的顺序是按照公交路线停靠的顺序来存储的，而不是按照公交车站编号的顺序存储并且一条路线不会经过所有的将近4000个站台，只是经过其中的一部分，所以不能直接按照节点信息的编号来对应站点表头，模型采取如下的对应方式：路线1存储站点3存储站点2存储站点1存储站点2存储站点1没有分配存储空间站点1站点2站点3路线2图 3.7-纵向连接示意图如图所示，假设路线1停靠3个站点，且停靠的顺序是3-1-2，路线2停靠两个站点，停靠顺序是2-1。则纵向采取如图的连接方式：节点存储顺序不依据站点的顺序，则站点1应该连接在路线1的第二个节点上，而站点2则连接在路线1的第三个节点上，同时路线1的第二个节点还应该指向路线2的第二个节点，因为它们存的都是站点1，路线1的第三个节点则应指向路线2的第一个节点，因为它们都存储的是站点2。同时因为路线2只有两个站点，所以路线2的第三个节点并没有分配存储空间。简单的说，这种存储结构就像一个存储矩阵一样，只是它的存储顺序不是按照矩阵的行列坐标，而是按照公交停靠站点的先后顺序，此外对于没有任何信息的节点不分配存储空间，这样就极大的降低了存储空间的消耗。3.4公交路线的换乘有了以上的存储结构，现在就可以讨论关于换乘的问题了5。我们可以把每一行的线路停靠的站点抽象为一条横线，将停靠在一个站的所有线路抽象为一条纵线，这样，整个公交网络就形成了一个表格状的图形：图中甲为起点站，乙为终点站图 3.8-换乘示意图lnABmCDEF丙KLIJGHopq乙丁戊甲l 直接到达的情况：如果甲站所在列（即所有到达甲站的路线）中的某个节点与乙站所在列（即所有到达乙站的路线）中的某个节点在同一行上，即在同一条路线上则可以直接到达，例如在甲的站点列表中有A点，乙的站点列表中有B点，它们都在l行上，则甲、乙之间可以直接到达。l 换乘一次的情况：如果甲站的所在的列的路线与乙站所在的列的路线不在同一行上（C点在m行，D点在n行），然而它们（C点和D点）所在的路线上的站点在同一列上（E,F在丙列上），则甲乙之间可以换乘一次到达，从甲站通过路线m到达E点的丙站，再从丙站上车走路线n从G点到达D点(终点站乙站)。l 换乘两次的情况：如果甲站所在的列的路线与乙站所在的列的路线不在同一行上（G点在o行，H点在p行），并且它们（G点和H点）所在的路线上的站点不在同一列上（I在丁列上,J在戊列上），但是这两个站点（I点和J点）所对应的列中有在同一行上的两点（即K，L在同一条公交线路q上），则可以从G点出发通过路线o，到达I点（第一个换乘车站丁），然后从丁站的K点上车通过线路q到达L点（第二个换乘车站戊），再从戊站的J点上车通过线路p到达H点（终点站乙站）。l 换乘三次及三次以上的情形可以以此类推，但考虑到实际很少出现换乘三次或三次以上的情况，故不再此赘述。3.5搜索算法在3.4中已经给出了寻找直达，换乘一次，换乘两次线路的方法。然而，不同运作方式的公交线路使得模型不能简单的搜索两个站点是否在同一公交路线上。这里得考虑到公交车的运行方向问题。例如一个公交路线的上行路线可以从A地到达B地，但是下行路线却不一定能从B地直接到达A地。此外，环线的两条路线都能往返于线路上的任意两个站点，只是它们运行的方向不同。同时为了在优化算法中方便的计算以及选择，在搜索中还得获取每条线路的换乘次数、花费的时间、费用以及换乘站的情况（当然这些数据最后不用都存储，这点在优化算法中将会详细介绍）。显然我们可以单独的进行直达，换乘一次，换乘两次线路的搜索，但是这就增加了整个算法的运行时间。通过分析不同换乘次数的方法，我们发现换乘一次的搜索实际上是在直达搜索的基础上进行的。直达的条件是两个站点间线路相同，而换乘一次的条件是两站点间的路线不相同，因此只需要在不相同的路线上查找换乘一次的路线即可。这样就将换乘一次和直达的情况合并在一起了。同理，换乘两次的搜索是建立在换乘一次搜索的基础上，如果两条线路上站点不重合则执行两次换乘的搜索。同时由于在建立数据结构时没有存储多余的节点，搜索过程会变得更为简单和快捷。3.6择优算法由3.5给出的算法可以实现直达、换乘一次，换乘两次的查询。然而，如果把一组查询数据输入，得到的结果将是灾难性的。对于某些站点，程序会列出上千个出行方案，这些方案中大部分都是耗时的，或者价格较高的，有的甚至有会出现在日程生活中很不合理的路线。因此需要对查询算法给出的数据进行优化处理，选择其中最为合理的方案。根据3.1中对于乘客心理的分析，我们将从换成次数、乘车时间、出行路程、换乘车站的环境多方面的因素综合考虑对数据进行优化，并给出直达，换乘一次，换乘两次的三条最优方案，使得结果尽可能的满足现实中人们对于公交路线选取的要求。同时，模型的优化算法还重点考虑了本模型构建的初衷，如摘要中所述，本算法将尽可能的减少存储空间，以及提高优化的速度。运行效率以及存储效率成为我们算法设计的基础。通过搜索算法可以得到直达、换乘一次，换乘两次查询的所有路线以及换乘站点的信息，一种方法是将这些信息全部存起来，然后在这个存储结构上进行优化处理。这样将会不得不牺牲相当可观的存储空间。同时在此数据结构上查询时，会花费时间用于数据的查找以及排序。实际上正如在3.5中所说的，这些数据信息实际上不用存储，并且可以利用搜索算法中遍历过程完成查找替换过程。由于模型要输出三条最优化的路线，所以只需要给每种换乘方案分配记录三条最优路线的存储空间就可以了。在设计算法之前有必要对影响优化的因素进行分析和界定。由于本模型将分别给出直达、换乘一次、换乘两次的最优路线，故算法先不用区分换乘次数的优劣。因此我们考虑的因素按权重的大小排列依次是：行程花费的时间、路程的长度、换乘车站的环境、路线近似问题共四大因素：l 行程时间：如果是直达的情况，则根据假设，路程的长短就等价于行程花费的时间，设交通工具经过相邻两站的平均时间为t，线路通过的站数为n，则总时间T=t*n；如果加入换乘的因素则只需要再加上每次换乘所需要的时间即可。l 出行路程：路程不需要考虑换乘所经过的路程，只需要将每次行车路线的长度加起来即可。l 换乘车站的环境：依据日常生活经验，停靠线路较多的站点通常都是较为繁华的地段，因此在保证时间、路程最优的基础上我们将优先考虑提供大站的换乘路线。但在此之前，首先要制定一个标准来评判换乘车站的环境。在此约定：停靠在一个站点的路线越多，该站就越繁华。为了更精确的描述一个站的繁华程度，可以区分公交车站与地铁站并为它们设定一个权值：公交站的权值为1，地铁站的权值为3。这样的约定是合理的，因为在一般情况下地铁都在城市的繁华地带，而且地铁的票价也是普通公交车的三倍。对于换乘两次的情况，我们先判定两个换乘车站繁华度的和，如果站点A的繁华度P1与B的繁华度P2相比：P2-P1，则选取繁华度的和较大的线路A，否则比较两个站点繁华度的差的绝对值P3和P4，选择其中较小的。l 路线近似：因为不同的线路中可能会有某一段线路重合，所以搜索出来的三条最优线路中，可能出现重复的情况，它们只是中间的换乘车站不相同，但乘坐的所有车次都是相同的，我们这里去除重复的线路的方法比较简单，就是对于那种乘车时间相同、乘车费用相同且所有的车次都相同的线路出现时，不予存储。根据上述分析，我们可以在搜索算法的基础上得到搜索优化一体化的算法：1) 读入数据，依次遍历两个车站上（设起始站点为A，目的地车站为B）的线路。2) 判断两个车站上的线路是否相同，如果路线相同则转入步骤3），如果路线不相同则转入步骤4)。3) 判断两个站点之间的线路运行方式：（1）如果是上下行不同的路线，判断上下行路线中是否能从A到达B，若能到达由S2-S1算得两站间的车站数目，判断线路的计价方式，计算出车票价格，并获取能够到达的路线以及路线经历的站数，花费的时间和费用的信息，先按时间比较预先设置的存储空间中的三条路线，以倒序的顺序（即从最后一个到第一个数据）比较（若表中无数据则从第一个开始覆盖），如果当前的线路时间短则用当前的线路覆盖原有的线路，若路程相等则以路程为参照标准进行调整，若时间路程都相等，再以费用为标准调整线路。在前三遍的优化中，如果遇见近似路线情况则不覆盖原有路线。完成后返回步骤1）继续遍历；若上下行都不能到达则直接返回步骤1）继续遍历。（2）如果是上下行相同的路线，判断是上行路线能够到达还是下行路线能够到达，按照（1）的方法进行优化，然后返回步骤1）继续遍历。（3）如果是环形路线则记录顺时针绕行和逆时针绕行两条路线，并分别遍历两条线路计算两站间的车站数，按照（1）的方法进行优化，然后返回步骤1）继续遍历。4) 如果线路不相同，则依次遍历两条线路，如果两条线路经过的车站相同则进入步骤5），如果两条线路经过的车站不同则进入步骤6），遍历结束返回步骤1）继续遍历。5) 按照步骤3）的方法分别判断从起点到达相同车站（设为C）以及从C到终点的线路运行方式：（1）如果两段路线都能运行，则按照步骤3）的方法判定线路，如果时间、路程、费用都相同，选择繁华度最高的站点作为评判标准调整线路。然后返回步骤4）继续遍历。（2）若两条线路中有一条不能运行，则直接返回步骤4）继续遍历。6) 如果两条线路经过的车站不同，则依次遍历经过这两个不同车站的线路，若路线相同则转入步骤7），若路线不同则转入步骤6）继续遍历，遍历结束返回步骤4）继续遍历。7) 如果经过两个车站的路线相同，则按照步骤3）的方法判断经过两个车站（设靠近A点的车站为D，靠近B点的车站为E）的线路的运行方式：（1）如果经过该线路可以从D点到E点，则按照步骤3）的方法判定线路，如果时间、路程、费用都相同，按照两个站点的繁华度评定标准来调整线路，然后返回步骤6）继续遍历。（2）如果经过该线路无法到达E点，则直接返回步骤6）继续遍历。8) 如果步骤1）的遍历结束，则算法终止。4添加地铁后的模型的建立在上述建立的公交车查询模型的基础上，我们可以做适当的修改和扩展，把地铁也考虑在内。在此之前，我们需要对地铁的相关情况进行分析。4.1地铁路线的分析根据题目中所给的信息，共有两条地铁线路。其中一条是环线，一条是直线。这两条路线可以分别对应公交车中的环形路线和上下行相同的路线。故线路的相关情况可以完全参照公交车线路的标准，而不需要另加考虑路线的模型。地铁站点与公交站点的区别在于有的地铁站对应了多个公交车站。这就意味着多个公交车站间可以相互通行且不算作换乘，并且在搜索中，也得考虑到这种一对多的对应方式。例如地铁站D01连接了公交车站S0567，S0042，S0025。那么这三站中任意两站间的通行都不用考虑换乘的问题。当乘客到达S0567站后，可以通过地铁站D01到达公交车站S0042乘坐通过该站点的公交车，这个过程只换乘了一次。4.2公交车模型的扩展的线路问题通过以上的分析我们可以看出，地铁的情形与公交车相似，只是在站点方面稍有不同，因此我们可以把地铁看作一种特殊的公交车，这种公交车只有环形线路和上下行线路相同的情况，并且这种公交车的计费为同一的三元计价。唯一需要处理的是站点连接的问题。我们可以用这样的一种方式来处理站点的问题：如果一个地铁站点连接了一个以上的站点，我们可以把该地铁站存成所有的公交车站点。例如地铁站D01连接了公交车站S0567，S0042，S0025，在存储的时将D01存储成S0567，S0042，S0025。在这种情况下，我们就需要对通过这些站点的方式分情况讨论（以D01为例）：l 当乘坐地铁通过：地铁站被存成了多个车站，然而实际上它们只是同一个站点，因此当乘坐地铁通过这三个车站时，实际上并没有花费时间，路程也没有增加。我们的模型将这三个站点的站台编号存成同一个数字，这样在计算通过的站点的数目时实际上就没有计算通过这三个点的站点数目。而时间是根据线路通过的站点数目计算的，所以时间也没考虑在内。l 当换乘时通过：在换乘时虽然不用考虑路程问题，但是要算上换乘时间，因此凡是通过地铁站换乘公交车时都要把换乘时间加上。4.3公交车模型扩展的站点计算问题在4.2中讨论过了直线地铁的站点计算问题，在这节中将进一步分析环形地铁的问题。由于环形地铁各站点的编号都记为0，因此需要通过遍历的方式来计算通过的站点数目。但是由于存在一个地铁站被存成多个公交站的情况，所以不能按照公交车环线的搜索方式。在遍历线路的时候，需要判断该点是否与前一个站点相同，这就需要记录每个公交站点所对应的地铁站名，如果遇上一个站点相同，则不增加经过车站的数目。4.4加入地铁后的公交模型的算法分析整个算法仍然沿用3.6中得到的搜索优化一体化算法，只是在计算线路的站点以及费用信息时按照4.2和4.3中讨论的方法计算。这里就不再重述描绘算法了。5增加步行后的改进算法5.1更为一般化的模型分析上面的算法可以发现只有当不同线路之间具有公共站点时才能够进行转车,这样计算出来的结果有时并不符合实际情况,比如用上面的算法求出两地没有直达车，但现实生活中人们可以步行小段距离（一、两站）再乘车，就有可能坐到直达车。选择这种方式可以减少换乘次数,而且这种换车方式也是由站点的分布情况所决定的。5.2关于临近站点的讨论为了便于与讨论，两站距离之内为紧邻站，紧邻站点的存在使得人们在选择换乘路线时多了一个考虑,就是如果在某一站点下车后没有直接换乘的车次,还可以考虑附近的站点是否有换乘车次。根据这种思想,可以对上面的算法进行改进,即在换乘时,加入对紧邻站点的判断和分析。这种算法更加符合站点的分布情况以及人们出行时的实际选择情况。仍沿用前面的建立的数据结构与优化准则。该算法的基本思想6为分别从起点A 、终点B 出发,通过比较公交网络上各车站的可换乘车站,追索A 到B 的可能路径,然后比较各可能路径,来确定最优路径。设S(I)(I=1,2,m,m为正整数)为经过A或其附近的线路集。T(J)(J=1,2,n,n为正整数)为经过B或其附近的线路集。E(I,U)(U=1,2,p,p为正整数)为线路S(I)上的站点集。F(J,V)(V=1,2,q,q为正整数)为线路T(J)上的站点集。R(K)(K=1,2,g,g为正整数)为经过E(I,U)的线路集。Y(O)(O=1,2,z,z为正整数)为经过F(J,V)的线路集。G(K,W)(W=1,2,i,i为正整数)为线路R(K)上的站点集。L(O,X)(X=1,2,j,j为正整数)为线路Y(O)上的站点集。d(m,n)表示站点m与站点n之间的距离。w表示乘客在换车时步行距离的最大心理承受值,它是一个人为干预的经验值。对于站点m 与站点n 之间的紧邻关系,可以用一个不等式来表示:d(m,n)=w。因此搜索的时候可以包括临近点的车站。算法的步骤如下:(1)输入乘车的起始站点A及目的站点B;(2)求经过站点A 的所有线路集S(I)和经过站点B的所有线路集T(J);(3)判断S(I)=T(J)吗?如果有,则找到了从站点A到站点B的直达线路S(I) 即T(J) ,输出结果。如果没有,再执行下面。(4)求线路S(I)上的站点E(I,U)以及线路T(J)上的站点F(J,V);(5)判断是否存在相同站点,即E(I,U)= F(J,V),或者存在紧邻站点,即满足d(E,F)=w;如果满足E(I,U)=F(J,V),则线路S(I),T(J)即为一次转车的线路, E(I,U)即为转车站点且换车时不用更换站点;如果满足E(I,U)F(J,V)但满足d(E,F)S0245，显示如下：地铁线路及上下地铁站无该类型线路图 6.2-软件示意图2这个小软件使用比较方便，而且输出的信息也比较全面，但对于最优线路的选择上还可以进行进一步的优化。6.2公交模型的结果分析6.2.1线路S3359-S1828表 6.1-最优路线信息表1起始站线路1中转站1线路2中转站2线路3终点站费用（元）总时间（分钟）直达S3359无S1828换乘一次L436(下行)S1784L167(下行)3101L436(下行)S1784L217(下行)3101L436(下行)S1241L167(下行)3107换乘两次L015(下行)S2903L485(环线)S1784L167(下行)364L015(下行)S2903L485(环线)S1784L217(下行)364L123(上行)S2903L485(环线)S1784L167(下行)364如果完全按照假设条件和我们以时间优先的原则选最优线路的话，模型会推荐选择换乘两次的线路，即使大多数乘客不愿意增加换乘的次数，但以多花将近40分钟的时间为代价，还是很不划算的， 查询换乘一次中的三条线路可以发现，S3359站位于L436的中部位置，而S1784站和S1241站在线路中的较后位置且两站距离相距较近，所以第一次所乘的车时间较长且车上可能会比较拥挤；通过我们的计算看出，S1784站和S1241站均为比较大的站（通过S1784站的线路有43条，通过S1241站的线路有34条），所以这一段路线可能会比较拥堵，实际花费的时间可能会比计算的时间要长；三种方案中的第二次换乘的车只运行了一站或两站地，且这段路位于线路中的最后部分，所以这段路线不会花费太多的时间且车上不会很拥挤；再考虑换乘时的等车时间，由于换乘站均是大站，所以公交车会比较多，等车时间不会很长。查询换乘两次的三条路线可以发现，第一次和第三次乘车均只坐了一站，且这一站都在线路的尾部，所以不会花费很多时间且车上不会太拥挤；而在中间的乘车过程中，因为这一段路位于线路的中间位置，且前后两个车站都是大站（通过S2903站的线路有49条，通过S1241站的线路有43条），所以花费在这一段线路的时间可能比我们模型算出的时间多，同时车上会比较的拥挤，但第二条线路相比换乘一次方案中的第一条用时少很多。同上面的道理一样，这两次换乘时的等车时间均不会很长。综合上述各种因素考虑，我们还是应该选择换乘两次的方案，因为在这两类方法中，除了时间和换乘次数上有所不同外，其它状况基本上是相同的，但如果乘客时间充裕而且希望沿途观光城市风景的话，可能会选择换乘一次的方法，但在乘车过程中的拥挤状况还是会使乘客放弃这种选择。下面再把步行的因素考虑在内，因为在这两类方法中，都有只坐一站或两站的情况，所以如果乘客时间充裕而且考虑经济因素，可以选择步行，而且这样可以观光一下城市风景。6.2.2线路S1557-S0481表 6.2-最优路线信息表2起始站线路1中转站1线路2中转站2线路3终点站费用（元）总时间（分钟）直达S1557无S0481换乘一次无换乘两次L084(下行)S1919L189(下行)S3186L460(下行)3106L363(下行)S1919L189(下行)S3186L460(下行)3106L084(下行)S1919L417(上行)S2424L254(上行)3112没有直达和换乘一次的公交汽车线路，那我们只能从换乘两次的方法中选择最优解，所以我们可以选择换乘两次方法中的前两个之一。然而考虑到实际情况，可能就会有一些变化首先三种方案的换乘站都是大站，因此前两种方法没什么区别，只是第一种方案的第二条路线只经过了三个站点，考虑到乘客的心理第二种方案要更合适点，三条路线经过的站点都较为平均。而对于第三种方案，虽然时间多了6分钟，但是最后一条线路L254很特别，它是一个短程路线（总共17站），因此这辆车在实际状况中往返的频率会很高，这就意味着等车的时间会比较长的路线要少很多，同时车多也就意味着每辆车的人会相对少点，因此有可能方案3会更适合。6.2.3线路S0971-S0485表 6.3-最优路线信息表3起始站线路1中转站1线路2中转站2线路3终点站费用（元）总时间（分钟）直达S0971无S0485换乘一次L013(下行)S2184L417(下行)4128L013(下行)S0992L417(下行)4131L013(下行)S1789L417(下行)3134换乘两次L013(下行)S2517L290(环线)S2159L469(上行)3103L013(上行)S1609L140(下行)S2654L469(上行)3106L024(下行)S1609L140(下行)S2654L469(上行)3106换乘两次的方法时间短，而且花费只有3元，则应该选择，但还是考虑换乘次数问题，和第二个一样，换乘一次和换乘两次时间上差别不是很大，一些乘客还是会选择换乘一次的方法，但比较换乘一次的三个方法中，前两种方法比第三种方法并没有快很多，但多花了一元钱，所以应该选择第三种方法。6.2.4线路S0008-S0073表 6.4-最优路线信息表4起始站线路1中转站1线路2中转站2线路3终点站费用（元）总时间（分钟）直达S0008无S0073换乘一次L355(下行)S2303L345(上行)283L463(下行)S2083L057(上行)283L159(下行)S2633L474(上行)283换乘两次L043(下行)S1383L290(环行)S2184L345(上行)367L043(下行)S1383L296(环行)S2184L345(上行)367L198(上行)S1383L290(环行)S2184L345(上行)367这里存在一个选择的问题，本来应该用层次分析法来解决这个问题，然而由于时间的限制，我们没能够建立这个模型。因此这里分析下，通过对时间换乘次数以及站点因素，费用等因素的考虑，得出一个合理的路线。考虑到换乘次数在乘客选择中占据很大比重，故应该考虑换乘一次的方案。然而可能有些乘客更加看中时间的因素，因此将把所有的换乘一、两次都列出来还是比只列出一条层次分析得出的最优路线要有价值的。6.2.5线路S0148-S0485表 6.5-最优路线信息表5起始站线路1中转站1线路2中转站2线路3终点站费用（元）总时间（分钟）直达S0148无S0485换乘一次无换乘两次L308(上行)S0036L156(上行)S2210L417(下行)3106L308(上行)S0036L157(下行)S2480L417(下行)3109L308(上行)S3604L129(上行)S1383L469(上行)3115根据模型的评判标准应该选择第一条路线，因为在相同的费用下，第一条路线花费的时间最少。在没有直达路线的情况下这的确是最好的选择。考虑到实际情况，我们可以发现方案一除了上述的优点外，L156的起点站恰好是S0036站。这样，乘客在S0036站会很容易的乘坐L156路公交车，并且通常起始站的乘客都较少，公交车不会太拥挤。6.2.6线路S0087-S3676表 6.6-最优路线信息表6起始站线路1中转站1线路2中转站2线路3终点站费用（元）总时间（分钟）直达S0087无S3676换乘一次L454(上行)S3496L209(下行)265L454(上行)S1893L209(下行)271换乘两次L021(下行)S0088L231(环线)S0427L097(上行)346L021(下行)S0088L281(环线)S0427L097(上行)346L021(下行)S0088L231(环线)S0427L462(下行)346这里的情形同第四个站点的问题一样，存在一个用层次分析法来解决选择的问题。虽然换乘次数在乘客选择中占据很大比重，但换乘方案极大的减少了在路途当中所消耗的时间。大部分乘客在获取了换乘时间的资料后可能会倾向于换乘两次的方案。且换乘车站都是大站，不用担心等车会花费很长的