奥运会公交工具路线选择的设计与优化

1、奥运会公交工具路线选择的设计与优化【摘要】本论文通过对公交路线选择问题的抽象简化，建立了一个明确、完整的数学模型。我们借鉴“集合”的概念，并采用了分层序列法，设计出了一个便于任意两个站点之间路线选择并找到最佳路线的方案。路线选择系统分为可行路线查询和最佳路线确定两个部分，从而将实际乘车问题可以抽象为统计分析和目标优化的问题。可行路线查询具体算法：遍历经过起始站的所有车次线存入集合，与经过终点站的所有车次集合进行比较。两个集合的交集即为直达车次。若无相同车次则继续遍历经过集合各线路中起始站之后的所有站点（记为集合），与经过集合各线路中终点站之前的站点（记为集合）进行比较，其交集即为中转站点。如此

2、“线点线”循环迭代，较快的找到所有的可行线路。最佳路线的选择问题我们建立了一个多目标规划模型，并且采用分层序列法求解，圆满的解决了在换乘次数、耗费时间、车票费用三目标约束下最佳路线的选择问题。根据建立的多目标优化模型，可以求出问题(一)6组起始站终点站的最佳路线，如第1组S3359S1828的最佳路线有两条：始乘车次中转站转乘车次最短时间最优票价L436S1784L167101min3元L436S1784L217101min3元问题（二）添加了两条地铁线，数据库增大后同样可求出6组起始站终点站的最佳路线。其中第6组S0087S3676由于地铁站与公交车站联通，可以乘地铁直达：地铁线路名出发地铁

3、站到达地铁站最短时间最优票价T2D27D3625min3元问题（三）增加了步行选择，等价于增加了通路。我们通过合理假设，认为从出发站点向四周辐射，步行时间在10分钟以内的各站点都视为连通。把问题转化为与前两问相类似的问题。此时比较的点集更大，但仍可以用相同的方法建立和求解模型。关键词： 最佳路线 可行路线 分层序列法一 问题的重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。建立解决公交线路选择问题的自主查询计算机系统就很有必要，这里有几方面的因素需要考虑：“换乘次数”是大部分公交乘客

4、在选择出行方案时首先考虑的因素，“出行距离最短”也是乘客考虑的重要目标。需要解决的问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型与算法，求出以下6对起始站终到站之间的最佳路线。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。二 模型的基本假设1假设公交工具的票价在很长一段时间内不发生变动

5、；2假设每站之间的时间相同，都等于题目给出的平均时间，忽略路程的微小差异。3假设公共汽车公司有足够多的公交车参加营运，不会发生车站乘客过多导致无法上车的情况；4假设气候正常，路况良好，不会影响公共汽车的正常行驶。5假设交通秩序良好，公交工具路上不会出现意外的交通事故、零件损坏或者公交不会受交通阻塞等；6假设乘客坐公共汽车到达终点站之后必须下车，如果要继续乘坐必须增加车费。三 符号说明符号 表示意义备注车次集遍历查询起始站车次集遍历查询终点站站点集合SA任意站点起始站后内站点站点集合SB任意站点终点站前内站点车次集遍历查询的所有车次车次集遍历查询的所有车次最短总时间最少总费用换乘次数时间变量坐车

6、时间、换乘时间、步行时间票价变量分段票价、单一票价换乘次数最优解集时间最短解集换乘次数解集约束下费用最少解集时间最短解集约束下四 问题的分析及模型的建立4.1 乘客心理分析公交线路信息的数据给出了北京所有的公共汽车和地铁的线路标号、经过站点名和公交之间换乘方式的情况，这实际就是比较真实反映了2008年北京奥运会的交通实况，我们设计的模型就是要能满足不同乘客在查询路线选择时的相应要求。乘客在从任意起始站出发到终点站之间的路径选择不是惟一的，而且乘坐工具也是多样的。基于相关文献对乘客的出行心理进行的调查分析，其结果可以表明：“换乘次数”是公交乘客出行方案选择时优先考虑的因素，“公交行使时间最短”是

7、公交乘客考虑第二重要的因素，“乘车总费用最少”是公交乘客次之考虑的因素。4.2 北京公交网络分析连通性 在公交网络中，多条公交线路虽然可以相交于空间的同一个点，但是该点不一定是公交停靠站点，或者不是同时有站点，因而不同公交线路在此是不连通的。公交网络中接点的连通状态有三种： 同路公交路段的连通； 不同公交线路路段在同一点通过换乘实现连通； 不同公交线路路段在不同点的连通，此种情况需要换乘多次车，增加了时间的消耗；结点性质 在公交网络中，站点可以按到一定原则抽象成网络图上的相关结点，从而可以有效模拟出公交线路之间的情况。在同一道路上行使的不同公交线路在行程上是有部分重叠的，但各自的站点不可能完全

8、重叠；在公交网络中，结点与属性之间为一对多的关系。道路网中空间位置和属性相同的同名站点，在公交网络中因位于不同的公交线路而性质和权值可能不一样。有向线性质 实际的公交线路是有方向的，起点和终点决定了公交线路的行驶路径和方向，不同的公交线路有不同的行驶路线和方向，即使同一路公交车，其上行车和下行车行使的路径和停靠站点也可能不完全重叠，所以公交网络图应是有方向的，应引入有向线路集，而空间位置相同的结点和权值在不同线路上是不同的。换车代价模拟 在公交网络上的实际通勤中，人们选择路径最优，实际上是考虑时间最优，即在尽量短的时间到达目的地。同时根据人们的行为习惯，在时间较优的情况下，还要考虑到达目的地的

9、方便程度，比如中途是否要换车，换车时是否步行等，称之为便捷性最优。复杂性 北京作为我国的首都，又是一个历史悠久的老城市，具有站点繁多，道路体系复杂的特点。从题目给出的数据来看，总共有520条公交线路，约4000个公交站点，构成一个极其庞大且复杂的公交网络。4.3 可行路线选择算法 一般查找公交线路的方法我们先来观察一种普通的公交线路的查找方法。一般来说，从A站乘公交车到B站，会先看经过A站的车有直接到B站的吗？若有，马上得到直达车路线。若无，则再看A站有什么车经过，经过A站的车会到达哪些站?这些站有到B站的车吗？若经过A站的车会到达C站,而C站恰好有直接到B站的车,则可考虑在C站转车。若无，则

10、乘坐经过A站的车到另一站如C站下车，经过C站的车可以到达一个有直达B站的车的站点D吗？若有再在D站转车，两次转车可到达B。若无，两次转车不成功。如此推论下去，得出计算结果可能是：从A站到B站需要转好几次甚至十几次车才能到达。这样的结果对于北京公交查询来说显然是没有什么意义的。必须找出一种新的高效可行的算法。上下行线路处理根据我们对公交网络分析知道，结合北京公交网络数据信息。乘客出行路径的选择就是用户从起点出发到目的地，究竟选择乘坐哪路公交车，如何换乘才能最方便。因此算法要解决的问题是在已经建立好的公交网络上寻找一条换乘次数最少、距离字短的路径。一般来说，路径选择算法有两种模式：以换乘次数为代价

11、换取空间上的距离最短；以算法搜索时间为代价换取换乘次数最少。根据上述我们对乘客心理分析知道，大部分乘客还是愿意少换乘车或者不换乘。显然第一种算法方向是应该提倡的。根据我们对公交网络分析知道，同一车次其上行车和下行车行使的路径和停靠站点也可能不完全重叠。所以我们将公交车有上行和下行方向有分的车次分别作为两个独立的车次，上下行彼此毫不相干。如题目中给出的车次L002，就可以分成L002A与L002B两个车次。L002A表示L002的上行线，L002B为下行线。如此来原本520条路线在计算机表示中就变成了1040条，虽然数据库的容量增加了一倍，但与公交线路查询的准确性相比，这点牺牲是值得的。另外这种

12、处理方法令人可喜的是数据库访问时间并没有太明显的增加。 查询算法的基本思想以下便是我们求解问题和编制程序的具体算法，下述该算法比上叙一般路径选择算法复杂度小很多，且满足中转次数不超过2次情况下到达目的地。也可以添加中转次数限制条件使得在某一次比较之后能直接结束程序，以获得有限次中转的合理方案。算法的基本思想框图如下： SXXX1(出发站)SXXX2(目的站)库LS1：LAi（所有经过SXXX1的车次）库SE1：SBj（所有经过SXXX2的车次）库SS1：SAi(库LS1中SXXX1后面各车次中各站名)库SE1：SBj (库LE1中SXXX2后面各车次中各站名)库LS2：LAm(经过SAi的所有

13、车次)库LE2：LBn (经过SBj的所有车次)比较比较比较直达车中转站中间车次图1 可行方案查询基本思想示意图我们的算法主要借鉴了“集合”的概念，先分别求出与出发站点和目的站点相关的车次的集合，再求交集，交集里的元素即为可行解。如果交集为空，再衍生出与上述车次相关的站点集合，并求交集。如此可以迭代下去，找到所有可行方案。在查询从站点SXXX1到站点SXXX2 的可行方案的过程中，算法的基本思想如图1 所示，首先查询能直达站点SXXX1 的所有路线和能直达站点SXXX2 的所有车次，对这两个集合求取交集，如果存在交集，则结束迭代，交集里的所有车次即为所有可直达的车次；如果没有交集，则查询站点S

14、XXX1 所能直达的所有站点和能直达站点SXXX2 的所有站点，对这两个集合求取交集，如果存在交集，则结束迭代，交集里的所有站点即为一次换乘的中转站点，从出发站到该站点的车即为换乘前坐的车，从该站点到SXXX2坐的车即为应换乘的车次；如果没有交集，则查询经过站点SXXX1所能直达的所有站点的所有车次，和经过站点SXXX2所能直达的站点的所有车次，对这两个集合求交集，如果存在交集，则得到必须换乘两次才能到达的乘车方案，交集里的所有车次为第一次中转后应换乘的车次。如果仍然没有交集，就说明经过两次中转仍然无法到达，可以依照此法继续迭代，直到找到乘车方案为止。但是由于随着中转次数的增加，需要遍历的数据

15、量会大幅增加，为了提高系统查询效率，对允许的换乘次数加以限制，认为换乘两次以上无法找到。434可行路线查询算法的具体实现步骤：算法开始：Step1：输入出发站名SXXX1和目的站名SXXX2 查询所有经过的车次（最多 1040*86*2次）得到结果： 库LS1：LAi（肯定不会超过100个数据，根本不会有一个50辆车到同一个站点停靠）库LE1：LBi（同上不会超过100个数据）Step2：比较库LS1与库LE1中是否有相同车次？（LA与LB比较 100*100次） 有记入库（直达） 无无法直达Step3： 查询（1）：库LS1中后面各车次中各站名SAi 查询（2）：库LE1中前面各车次中各站名

16、SBj得到结果：库LS1中后面各车次中各站名SAi，库SS1：SAi（最多50*86个）库LE1中前面各车次中各站名SBj，库SE1：SBj（最多50*86个）Step4： 比较SS1 和SE1中的元素（为中转站）。 库SS1和库SE1中是否有相同站名？有记入库（一次中转）：SAi=SBj，及相应的始乘车次和转乘车次无无法一次中转完成Step5：查询（3）： 经过SAi的所有车次查询（4）： 经过SBj的所有车次得到结果： 库LS2：LAm经过SAi的所有车次 库LE2：LBn经过SBj的所有车次Step6： 比较库LS2 和库LE2中相同的元素（为中间车次）。有记入库（二次中转）：LAm=L

17、Bn，及相应的两个中转站名和从出发站点、目的站点到中转站的车次 无无法两次中转完成至此，完成了对所有可行路线的搜索，并保证不去计算超过两次中转以上的方案。算法结束4.4 最佳路线模型的建立 问题分析和求解策略选择根据乘客出行选择的统计分析知道，乘客确定最优路线主要考虑的因素有换乘次数、时间、费用。要求找到一条最佳路线，使这三个目标都达到最优。由此可见，最佳路线模型的建立实际上是一个多目标规划问题。解决多目标规划问题一般的做法是将多目标规划问题化成单目标规划问题来处理。而通常的转化方法有主目标法、分层序列法、线形加权求和法等多种求解策略。根据乘客出行选择统计分析知道，优化路线主要有换乘次数、时间

18、、费用三个目标。换乘次数是乘客路线选择时考虑的最重要的，实际在可行路线算法已经很好的体现换乘次数少作为我们的第一有效解。因为时间和费用这两个目标孰轻孰重缺乏具体数字说明，即很难赋予这两个目标的权重系数和界限值。因此主目标法、线形加权求和法等方法是不太适合模型的求解。考虑到看奥运会这个大背景下，能否按时进入比赛场地是较多人们关心的问题。相对与费用来说，时间应该是次之重要的目标。在解决规划问题上，分层序列法是我们使用的最好求解策略。所谓分层序列法是指：把其中的p个目标，按其重要程度安排一个次序。p个目标的次序已排好：最重要，次之，再次之，最后一个目标为。解出第一目标的最优解，再将这些解集作为下一目

19、标的可行域，直至完成全部目标。即先求出可行解集，再在范围内满足的可行解集，如此继续下去，范围内的解集。以下就是利用分层序列法建立的最佳路线数学模型：第一个目标“换乘次数”的目标函数.表示可行方案集，n表示换乘次数最优解，为最优路径可行解集。第二个目标“行驶时间”的目标函数.T表示最短时间解，为最优路径解集，T为第二目标的可行域。第三个目标“车票费用”的目标函数.P表示最少费用解，为最优路径解集，P为最佳路线解集。五 模型求解5.1问题一问题分析：在公交工具局限为公共汽车的条件下，要对6组起始站-终点站做出最佳路线的求解。通过查询告诉乘客最优乘车方案。附表数据里面给出了北京公汽线路路线编号、票价

20、、往返方式等情况。因为公交工具只有公共汽车，换乘公交时只需要考虑公汽换乘公汽平均耗时。依据我们建立的可行路线算法的描述，将上行方向和下行方向独立开来。这样要求乘客在坐一辆车时到终点必须下车，也就是不允许乘客不下车等这辆公汽下行行使时还在车上。因此在乘客对起始站在S3359到终点站S1828路线选择时，用我们的算法和模型可以很好的满足乘客的需求。问题的解答问题一中6组起始终点站对数据分别为S3359S1828 、S1557S0481 、S0971S0485、S0008S0073、S0148S0485、S0087S3676。上述我们给出了求解任意两个公汽站点之间路线选择问题的一般数学模型与算法。下

21、面以第一组S3359S1828为例给出具体解答过程：（1）已知起始站点名为 S3359，终点站名为S1828。图2是可行路线算法程序编制的模拟流程图。程序导出结果原则是换乘次数不向下兼容。即在查询是否有相同车次或者站名时，若是则退出程序，输出满足条件的路线名和站点名。程序代码见附录源程序1.1终点站起始站 车次库LS1车次库LE1 比较查询 否 是否有相同车次吗？ 是 否直达 记录库2终点站前面各车次中各站SBj记录库1起始站后面各车次中各站SAi所有车次考察完毕？ 是 可行路线 比较查询 经过SAi的所有车次记录为LS2经过Sbj的所有车次记录为LE2有相同站吗？ 是 中转次数 增1 否有相

22、同车次吗？中转次数 增1 是 否 退出 否可行路线所有车次考察完毕？ 图2程序运行结果知道无直达车次且中转次数为1，其中转情况填入表1如下所示：表1(S3359S1828车次表)起始站S3359终点站S1828始乘车次中转站名换乘车次实际开始车次实际换乘车次8721784334L436L1678721784434L436L2178721241334L436L1678721241434L436L2178723695434L436L2178722606434L436L217937519334L469L1679372364434L469L217937727434L469L217937304434L4

23、69L2179373192434L469L217注释：编程采用了将车次上下行拆分为两条新车次路线，故与实际的车次编号有所不同，换算方式是：实际车次编号=程序车次编号/2，余数是四舍五入原则。（2）找出表1所有可行路线时间最少的路线。显然上述的路线的总时间计算表达式可为：总时间=（起始站中转站终点站）的总站数*公汽站平均行使时间+公汽换乘平均耗时*中转次数.具体如表2所示，表2(S3359S1828时间表)起始站经过站数中转站经过站数终点站中转次数总时间/分S335931S17841S18281101S335931S17841S18281101S335931S12412S18281104S335

24、931S12412S18281104S335932S36953S18281110S335933S26066S18281122S335924S051921S18281140S335927S236416S18281134S335928S072715S18281134S335929S030414S18281134S335930S319213 S18281134从表2总时间的统计结果可以看出，行使时间最短是101分钟，中转站名是S1784。（3）这样，根据车票总费用作为第三目标，当然也是最后一个优化指标。表2已经表明只有坐L436次公车并且在S1784站点换乘才是时间最少可行集域的解。根据附录给出的信

25、息知道换乘车次L167的车票是分段计价的，车次L217是单一票价一元制的。而分段计价的票价标准为：020站 1元；2140站 2元；40站以上 3元。而中转站到终点站只有一站，所以L436L217和L436L167这两条路线的费用是一样的，都是最佳路线。手动计算结果与程序运行结果完全一致。下表3就是matlab得到的结果：表3起始站乘坐车次中转站名换乘坐车次87217843348721784434（4）类似利用我们建立的模型来求解第一对S3359S1828的最佳路线步骤，可以求出6组起始站终到站之间的最佳路线，如表4所示。表4（仅公汽下最优方案表）起始站终点站最佳路线最短时间(分)最少费用（元

26、）S3359S18281013S1557S04811063S0971 S04851283S0008S0073832S0148S04851063S0087S36766525.2问题二问题分析同时考虑公汽与地铁线路，对6对起始站终到站之间的最佳路线重新确定。根据附录给出的地铁线换乘公汽信息知道，地铁的每一个地铁站点都有一个或者多个公汽站点与之对应。这样就可以将新增加的两条地铁线等同为新增加了两条公共汽车线。即在原有1040的基础上增加了4条，定义为10411044次，这里将地铁的正反向运行区分开来了。进一步通过附录地铁换乘公汽信息数据文件格式说明文本知道假设同一地铁站对应的任意两个公汽站之间可以通

27、过地铁站换乘，无需支付地铁费。这样就可以将对应多个公汽站点的地铁站点简化，在程序实现时将多个公汽站点视为一个站点，剩余站点与之等效。新增加的地铁线以公汽的形式就可以如下所示：T1A：S0567（S0042，S0025）S1487S0303（S0302） S0566 S0436（S0438，S0437S0435） S0392（S0394，S0393，S0391） S0386（S0388，S0387，S0385） S3068（S0617，S0619，S0618，S0616） S1279 S2057（S0721，S0722，S0720） S0070（S2361，S3721） S0609（S0608）

28、 S2633（S0399，S0401，S0400） S3321（S2535，S2464） S3329（S2534） S3506（S0167，S0168） S0237（S0239，S0238，S0236，S0540） S0668 S0180（S0181） S2079（S2933，S1919，S1921，S1920） S0465（S0467，S0466，S0464） S3457 S2512T1B： S0567（S0042，S0025）S1487S0303（S0302） S0566 S0436（S0438，S0437S0435） S0392（S0394，S0393，S0391） S0386（S038

29、8，S0387，S0385） S3068（S0617，S0619，S0618，S0616） S1279 S2057（S0721，S0722，S0720） S0070（S2361，S3721） S0609（S0608） S2633（S0399，S0401，S0400） S3321（S2535，S2464） S3329（S2534） S3506（S0167，S0168） S0237（S0239，S0238，S0236，S0540） S0668 S0180（S0181） S2079（S2933，S1919，S1921，S1920） S0465（S0467，S0466，S0464） S3457 S25

30、12T2A：S0537（S3580） S0526（S0528，S0527，S0525） S3045（S0605，S0607） S0609（S0608） S0087（S0088，S0086） S0855（S0856，S0854，S0857） S0631（S0632，S0630） S3874（S1426，S1427） S0211（S0539，S0541，S0540） S0978（S0497，S0498） S0668 S1894（S1896，S1895） S1104（S0576，S0578，S0577） S3010（S0583，S0582） S3676（S0427，S0061，S0060） S196

31、1（S2817，S0455，S0456） S3262（S0622） S1956（S0289，S0291）T2B：S0537（S3580） S0526（S0528，S0527，S0525） S3045（S0605，S0607） S0609（S0608） S0087（S0088，S0086） S0855（S0856，S0854，S0857） S0631（S0632，S0630） S3874（S1426，S1427） S0211（S0539，S0541，S0540） S0978（S0497，S0498） S0668 S1894（S1896，S1895） S1104（S0576，S0578，S0577

32、） S3010（S0583，S0582） S3676（S0427，S0061，S0060） S1961（S2817，S0455，S0456） S3262（S0622） S1956（S0289，S0291）由于无论地铁线路间是否换乘，地铁票价始终为3元，所以在计算线路价格时，应特别注意，单独计算。无论从哪儿进从哪儿出，从进地铁站到出地铁站只需付一次费。问题解答问题2就是在问题1的基础上多了几路车次而已，因而完全可以按照问题1求两个公汽站点的最佳路线步骤，只是在计算时间时，由于要把各站的公交站点直线铺开了，所以不能计算经过了多少公交站的时间，而应该返回到地铁站计算，看共经过了多少地铁站。以下就是我

33、们求解这6组起始站终到站之间的最佳路线。结果如下表5所示：表5（增加地铁后最优路线表）起始站终点站最佳路线最短时间(分)最少费用（元）S3359S18281013S1557S04811063S0971 S04851283S0008S0073832S0148S04851063S0087S36762535.3问题三 问题分析和模型假设当我们知道所有站点之间的步行时间时，我们就不得不考虑到，除了乘坐公共汽车和地铁外，人们出门看奥运还有一种选择步行。如果出发站点和目的站点足够近，人们一般都会直接步行前往；如果需要乘车，人们可以走过几个站再搭乘直达车，或者乘车到某站下车后再走到目的站，也可以先乘车到某站

34、，再走到另一站去转乘直达目的站点的车。但是，人们徒步行走得时间不可能太长，尤其是在北京得烈日下。据有关医学调查，人在烈日下平均连续步行10分钟就已经大量出汗，感到不适；若步行时间达到30分钟以上，将有可能出现脱水等症状。所以外出步行连续步行时间应在10分钟以内为宜。从健康实际和舒适出发，我们作出假设：出行看奥运的人们不会连续步行10分钟以上，即如果两个站点之间的步行时间大于10分钟，人们将会放弃步行而选择乘车到达。5.3.2 建模思想和模型建立增加了步行选择，实际上只是另外增加了一些通路而已。从出发站点向四周辐射，步行时间在10分钟以内的各站点都可视为连通，即增加了从SXXX1到SSAi（行程

35、在10分钟以内的站点）的公交路线。这样就可以把问题转化为与第二问相类似的问题。新增通路太多的话，给各新增路线全都编号就会使查询工作变得非常复杂。所以我们只找到距离出发站点在10分钟以内的站点的名称，而并没有给各新增路线加以编号。针对这种情况，我们只需对模型的建立过程进行一些改动，也能得到合理的解决。模型建立的基本原理可以用下图表示：比较步行比较直达车中转站中间车次库LSX1：LSAi库SSX1：SSBi库SSX0：SSAiSXXX1库LSX2：LSBi库SSX2：SSCi库LEX1：LEAj库SEX1：SEBj库SEX0：SEAjSXXX2库LEX2：LEBj库SEX2：SECj图3 有步行情

36、况可行方案查询原理图步行中转图中，SXXX1、SXXX2分别表示出发站点和目的站点，椭圆形库内存放的是站点名，方形库内存放的是车次名，双向箭头表示对两库中的数据进行比较，如果有相同的则执行燕尾肩头所指向的方案。由于具体建模时采用了双向查找的方法，在对出发站点进行一系列操作时，同时也对目的站点进行这些操作。故这里只给出出发站点一侧的处理步骤：第一步：通过已知的各站点之间的步行时间找到距离SXXX1的步行时间为10min以内的站点SSAi（i1，2，3，N），并将这些点（包含SXXX1）存入库SSX0。第二步：将SSAi与SXXX2相比较，若存在SSAk=SXXX2，说明可以直接步行到达，并将结果

37、记入可行方案。第三步：查询经过SSAi的所有车次LSAi，记入库LSXi。第四步：将LSAi与LEAj相比较，若存在LSAkLEAl，说明可以乘车直达，或者走一段路后乘车直达。将可乘车次和乘车站点记入可行方案。第五步：如果没有找到直达车次，则考虑转车。查询LSAi经过SSAi以后的所有车站SSBi，记入库SSX2。第六步：比较SSBi和SEBj，若存在SSBk=SEBl，则该站即为中转站，并将结果记入可行方案。第七步：查询距离SSBi步行时间为10min以内的所有站点SSCi（包含SSBi），记入库SSX3。第八步：比较SSCi和SEBj，若存在SSCkSEBl，则可以乘车到SSBi下车，再走

38、到SSCi站转乘LEAj去SEAj，就可以走到SXXX2。将结果记入可行方案。第九步：查询所有经过SSCi的车次LSBi，记入库LSX2。第十步：比较LSBi和LEBj，若存在LSBk=LEBl，则该车次为两次中转方案的中间车次。将结果记入可行方案。第十一步：该模型可以无限迭代下去，直到找出所有的可行解为止。但是实际上，中转次数越多，查到的可行方案将以几何级数增长；而这些多次中转的方案由于其费时又费力，一般不会被人们采用。所以为了节省计算机资源，提高查询效率。可以再每偶数步时添加一个判断条件：如果没有找到可行方案才进入下一步，否则执行完本步骤就退出程序。5.3.3 模型求解 当我们找到一系列可

39、行方案时，由于一样可以计算出各方案的转乘次数、耗费时间和花费价格，所以可以采用与前两问相同的“分层排序法”求得最佳路线。详细解法见第一问，在此就不赘述了。六 模型的评价61 优点1.通过对问题的充分分析，创造性地把同一车次上下行方向独立成两个车次，有效的解决了公交车的往返路线不同的问题，并且极大地提高了整体查询的准确性。2.分析公交线路信息建立可行路线算法的时候，巧妙的借鉴了“求交集”的思想，创造出一种高效快速的可行路线查询方法。3. 采用了起始站和终点站分别向后和向前的双向搜索方法，大大简化了问题的复杂程度，增加了搜索效率。4.对多目标规划问题，采用分层排序法，避开了时间和价格的权数比不明确

40、的问题。得出的结果更具有合理性。5.模型具有很强的实用性，在多个目标的重要性排序上，处理得比较人性化，考虑到了看奥运这个大环境，很贴近现实。6.整个路线选择系统的查询效率非常高，当输入两个站名后，瞬间就可以得出一次中转之内得所有方案和最佳路线；需要转乘两次的方案也可以在几分钟之内求出，并且不会出错。62 缺点1.用“分层序列法”求解最短路线时，缺乏确切的乘客查询路线时的选择数据，不能具体给出三目标之间的权重系数。故模型的结果只是定性分析的结果，但是考虑到一般乘客心理因素和看奥运会这个大环境下，我们以换乘次数最重要、时间次之、费用再次之的原则也是完全合乎情理的。2.在整个建模过程中，我们都是在假

41、设没有任何交通变化得情况下进行的。而在实际乘客出行时，常常会碰上大雾、塞车等情况，所以我们得出的最佳路线也只是在理想状况下的最佳路线。而在实际生活中可能并不是最佳的。七 模型的改进与推广71改进针对上文提到的一些缺点，我们可以对模型做出以下改进，使其更具备实用性：1.通过大量搜集数据，进行分析处理，确定各个决策目标之间的权数关系。或者邀请一批专家、有经验的工人和干部等，请他们对各目标权系数或界限值发表意见，以获得比较可靠的权系数。这样就能够对每一条可行路线的优劣程度进行定性的分析，以得出更加合乎的实际的最优解。2.到交通部门了解塞车多发路段的信息，并以此也作为另一个决策目标，对最佳路线进行重新选择。这样可以在一定程度上避免遇上塞车情况。3.将我们的线路查询系统与网络相连接，随时更新当前路况，添加到决策中，这样能够根据乘客需求成功避开所有不良路段，节约到达时间。72 推广我们所建立的线路选择系统可以应用于各种线路查询选择情况，包括火车、汽车，甚至国际航班的选择都可以通过我们的查询方案得出所有可行路线和最佳路线。只需为我们的程序设立一个简单的人机交互界面，就能够将它放置到大街小巷，供人们查询。如果能够设置成中英文选择界面，那么外国游客也能非常方便的查询到北京的公交、地铁线路了。相信采用我们的路线选择系统，一定能让中外游客都满意，为我们的北京奥运更添一份喝彩