公交线路选择优化模型

1公交线路选择优化模型李昆程鹏曹梦涛摘要本题是一个公交线路查询的优化问题。根据查询者对换乘次数少、出行时间短以及出行费用低的不同需求，找出适合查询者的最优公交出行线路。首先，本文提出了单次出行最大换乘次数为2的模型假设，并分析了Dijkstra算法在公交路径查询中的不适用性，试图提出有效的查询算法。在问题一中，本文从公交系统线路图出发，在模型一中提出了基于“点”单源广度优先搜索模型。为了克服这种单向搜索效率低下的缺点，在模型二中，我们建立了基于“线”的双向广度优先搜索模型，极大的提高了搜索效率，分别得到了题目中六对起讫站点之间直达、一次换乘和二次换乘的所有可行线路。为了找到符合需求的最优线路，我们抓住换乘次数、出行时间和出行费用这三个影响线路选择的主要因素，针对三个影响因素重要程度相差较大的情况，建立了基于影响因素优先级的线路选择模型，即模型三。相反地，针对三个影响因素的重要程度相差不大的情况，我们在模型四中制定了因素的重要性尺度和综合评价指标，通过量化的方法建立了基于综合评价的线路选择模iW型。通过C++程序求解，分别得到了模型三与模型四的最优线路。问题二仅仅在问题一的基础上加入了针对地铁的考虑。因此，两个问题在模型和算法上具有很大的相似性。我们首先找出了地铁线与公汽线之间的站点联系，针对搜索效率极高的模型二进行相应的改进，找到了换乘次数不超过两次的所有可行线路。和处理问题一中最优线路的确定方法类似，依据模型三和模型四，分别找出了基于优先级的最优线路和基于综合评价的最优线路。针对问题三，本文定义了乘客的“步行容忍时间”，从而确定了某站点的“步行邻点集”。在“步行容忍时间”的约束下，试图找出换乘次数更少，出行时间更短、出行费用更低的出行方案。在论文的最后，我们首先对“最大换乘次数为两次”的模型假设进行讨论，通过分析肯定了假设的合理性。其次，通过对模型三与模型四这两种最优线路选择方案进行比较，分析了各自的优劣。最后，我们通过查找文献，并联系客观实际，提出了“换乘次数是乘客的主要考虑因素”，并在此基础上结合模型三与模型四的优点，进一步提出了基于换乘次数最少的综合评价模型。关键词公交线路选择单源广度优先搜索双向广度优先搜索需求优先级综合评价21111问题重述问题重述问题重述问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。【附录1】基本参数设定相邻公汽站平均行驶时间（包括停站时间）：3分钟相邻地铁站平均行驶时间（包括停站时间）：2.5分钟公汽换乘公汽平均耗时：5分钟（其中步行时间2分钟）地铁换乘地铁平均耗时：4分钟（其中步行时间2分钟）地铁换乘公汽平均耗时：7分钟（其中步行时间4分钟）公汽换乘地铁平均耗时：6分钟（其中步行时间4分钟）公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。【附录2】公交线路及相关信息（见数据文件B2007data.rar）2222问题分析问题分析问题分析问题分析近几年来，城市的公交系统有了很大的发展。公交运输的覆盖面越来越广，公交线路也日益增多，公共交通逐渐成为绝大多数出行者的首选方式。发达的城市公交系统使得公众的出行更加通畅、便利，同时也给人们出行乘车线路的选择带来了一定的困扰。方便、快捷、经济的公交出行线路方案，不仅可以方便公众的出行，同时也为城市交通减少了不必要的交通流量，有利于提高城市交通的运行效率，展现城市的现代化风貌。2.1影响公交出行线路选择的因素在研究公交最优路线选择的算法时，应该从实际情况出发考虑。因此，我们有必要先了解乘客出行时所考虑的因素，通过对乘客出行心理、行为的研究来确定模型的优化目标和约束条件。3按照传统的想法，乘客总是选择从起始点到终讫点的最短路径。研究表明[1]，最短路径并不是决定公交线路选择的主要因素。其它因素却是十分重要的影响因素。通常受到以下几个因素的作用。（1）换乘次数：指乘客在完成一次出行过程中所换公交车的次数。（2）出行距离：包括车上距离和车外距离。车上距离指乘客完成一次出行的过程中，乘坐的所有公交车辆（包括地铁）行驶的总距离（在问题一与问题二的模型中进行讨论）；车外距离指乘客为了乘车而步行的距离（在问题三的模型中进行讨论）。在本模型中，由于相邻车站的平均行驶时间已知，因此车上距离体现在车上耗时上。（3）出行耗时：指乘客在一次出行过程中所需的时间，它也包括车上和车外部分。车上耗时即指乘客在公交车辆（包括地铁）上花费的总时间。车外耗时除了在车外距离部分所耗的时间外，还包括在车站等车的时间。（4）出行费用，指的是乘客在完成一次出行过程中所花的车费。针对如此多的因素，有时很难做出有关出行方案的准确判断。因此，我们根据人们出行的实际需要，分别针对出行方便（换乘次数最少）、快捷（出行耗时最少）、经济（出行成本最低）提出两站之间多种的乘车方案，以便乘客根据自己的不同需要进行选择选择。2.2公交线路的形式公交线路的形式是公交线路信息组织与处理的关键。针对本题而言，北京市公交线路的形式主要有三种，如图2.2—1所示：IIIIII2.2—1（1）往返一致型：下行时车辆严格依照上行线路往返；（2）圆环型：线路的起点和终点相接，运行路径为圆环；（3）往返不一致型：车辆上下行线路基本一致，但是局部站点不同。2.3Dijkstra算法不适合公交最优路径查询[2]公交路径查询要求的是从起点到终点的最优路径，而Dijkstra算法求出的是从某点到其余各点的最短路径。在一个类似北京这样的大型城市里，站点少则几百，多则上千，这无疑会增加运算时间和程序的复杂度。在大量数据的情况下，计算速度会慢的让人难以忍受。其次，用Dijkstra算法求出的最短路径在多数情况下不适合公交线路，因为Dijkstra算法求出的结果可能是：从A站到B站需要转几次甚至十几次车，此结果只对私车出行有益，对公交线路没有意义。3333模型假设模型假设模型假设模型假设�相邻公汽站平均行驶时间(包括停站时间)：3分钟。�相邻地铁站平均行驶时间(包括停站时间)：2.5分钟。4�公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟，候车时间3分钟)。�地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟，候车时间2分钟)。�地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟，候车时间3分钟)。�公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟，候车时间2分钟)。�公汽票价分为单一票价与分段计价两种。其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元。�无论地铁线路间是否换乘，地铁票价均为3元。�同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)。�假设乘客每次出行公汽与公汽的换乘次数不超过两次。�出行耗时从起始站点的上车时刻算起，不考虑有关起始站点的步行时间和候车时间。4444符号说明符号说明符号说明符号说明——经过站点的所有公交线路的集合iSi——第条出行线路公汽换乘公汽的次数（不通过地铁站）1iNi——第条出行线路的地铁换乘地铁的次数2iNi——第条出行线路的地铁换乘公汽的次数3iNi——第条出行线路的公汽换乘地铁的次数4iNi——第条出行线路的公汽通过地铁站换乘公汽的次数5iNi——第条出行线路乘坐公汽的总站数1ini——第条出行线路乘坐地铁的总站数2ini——第条出行线路的出行耗时iTi——第条出行线路在公交车辆上（包括地铁）消耗时间的总和1iti——第条出行线路换乘消耗时间的总和2iti——第条出行线路出行费用的总和iCi——某条出行线路中两相邻站点（指起点、终点或换乘站点）之间的行车区段l——第条出行线路上第区段的票价函数。(,,)ticketlABil——第个影响因素的权系数(1,2,3)kwk=k——第个影响因素的量化指标(1,2,3)knumk=k5——第条出行线路上所选择出行方案的综合评价指标iWi5555模型的建立与求解模型的建立与求解模型的建立与求解模型的建立与求解根据2.1所述，在本模型中，由于相邻车站的平均行驶时间已知，因此车上距离在车上耗时中体现出来。在充分考虑影响公交出行线路选择的各个因素的前提下，我们本着出行方便、快捷、经济的原则，分别选取换乘次数、出行耗时和出行费用最小为目标建立优化模型。5.1仅考虑公汽线路时，任意两个公汽站点之间的可行线路统计为了找到任意两个公汽站点之间的最优线路，首先我们需要确定任意两个公汽站点之间的可行线路。这里的可行线路是指通过不大于两次的换乘能够连通指定两公汽站点的线路。考虑到两个站点之间可能出现没有直达车而出现换乘的情况，因此，在上文假设中换乘次数不超过两次的前提下，我们试图通过设计一定的算法，分别求出任意两公交站点之间不需换乘的线路、需要换乘一次的线路以及需要换乘两次的线路，以及相应的时间消耗、费用等参数。我们将公交站点抽象成公交系统交通图中的“点”，将公交线路抽象成公交系统交通图中的“线”，“点”与“线”相互联系，共同构成了复杂的公共交通系统。5.1.1模型一：基于“点”的单源广度优先搜索模型引用文献[3]中提出了一种“两点乘车算法”，其核心思想是以起点为“根”，通过公交线路间的可换乘表（Route-Route）长“枝”，通过公交线路的长枝表（Route-Con）确定下一层“枝”生长的“节点”，最终长成以出行起点为顶的有向树。本模型在其算法思想基础上进行拓展，提出以“点”为中心，基于“点”的单源广度优先搜索模型，找出两确定站点之间换乘次数不大于两次的公交出行线路。算法步骤如下：Step1：以起点临近站点为“根”，令其为；把的下游相邻站点作为第一层“枝”SS的节点，设其为，，……,如图5.1.1—1所示：（图中只列出了第一层和第二1,1S1,2S1,3S层）SSSS1111,,,,1111SSSS1111,,,,2222SSSSSSSS2222,,,,1111SSSS2222,,,,2222SSSS2222....3333SSSS2222,,,,4444••••••••••••••••••5.1.1-1Step2：长“枝”时，记录换车次数。当换车次数时终止长“枝”。num2num6Step3：根据实际生成的“长枝表”，找出首次出现终点的“枝”的节点，经由D各层“枝”连接与的连线，就是一条符合要求的公交线路。再根据记录其换乘次数SD的变量即可完整的确定该条公交线路的方案。num该模型紧紧围绕公交系统网络图中“点”这一中心，通过节点树确定出可行的公交线路方案，思想简明易懂。但是，这种算法“单源”的特性决定了其搜索效率的低下。附件所给数据中包含了3957个公汽站点，数据量庞大，通过多层生“枝”，搜索速度慢，效率低。若运用于公交查询系统，很难在较短的时间内查询出可行的公交线路。因此，我们并没用使用该模型进行求解。为了克服模型一搜索效