公交线路的最优选择

1、公交线路的最优选择摘要本文对乘公交、看奥运这一实际问题进行了深入的研究，首先对公交乘客进行了调查，得出影响乘客出行的三个主要因素分别为：换乘次数、出行时间、出行费用，通过北京公交系统（BRT）调研报告【1】的统计结果，得出出行时间最短是乘客出行考虑的最主要因素，其次是换乘次数和出行费用(由于费用比较少，以出行时间和换乘次数为主)，然后建立的多目标规划模型，从而确定了出行者对路线的所有选择方案。对于问题一：我们仅考虑公交线路，考虑到人们的心理因素，人们对换乘次数有一个最大的承受上限，不能无限制的换乘下去，所以我们限定最大换乘次数为2，即最多利用3条公交线路从起点站到达终点站，分别建立出行时间和乘

2、车费用多目标模型为：然后把520条公交线路读入到MATLAB当中，用MATLAB编程编程求解得到换乘1次和换乘2次6对起始站终点站的最优路线。仅在此给出S3359S1828的最佳路线：表1：换乘1次时S3359S1828的最优线路方案起点站终点站线路1中转站线路2时间（分）费用（元）S3359S1828L436(下)S1784L167(下)1013表2：换乘2次时S3359S1828的最优线路方案起点站终点站线路1中转站1线路2中转站2线路3时间费用S3359S1828L015(下)S2903L027(环)S1784L167(下)733其余结果见正文对于问题二：要求同时考虑公汽与地铁线路，我们

3、同样建立了多目标模型，我们首先将增加的地铁线路信息添加到问题1建立的两个矩阵中，利用与问题1相似的编程思路，求解得到换乘1次和换乘2次时6对起始站终到站之间的最佳路线。S3359S1828的最佳路线与问题1的相同，其余结果见正文。对于问题三：要求同时考虑公汽、地铁和步行，我们建立了全局替换模型和局部替换模型。最后我们对模型进行了推广，给出了线路的“满载度”的定义，在考虑“满载度”之后，建立了新的模型。关键词：多目标规划 调查 MATLAB 满载度1. 问题重述1.1问题的相关背景：我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交

4、通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。1.2乘公交，看奥运的相关信息：1.2.1基本参数设定：相邻公汽站平均行驶时间(包括停站时间)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其

5、中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。1.2.2公交线路及相关信息（见数据文件B2007data.rar）1.3需要解决的问题：问题一：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附件中的相关数据，利用所得到的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359S1828 (2)、S1557S0481 (3)、S0971

6、S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676问题二：同时考虑公汽与地铁线路，解决以上问题。问题三：假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2. 问题分析本文需要对乘公交、看奥运这一实际问题进行了深入的研究，设计出一种线路选择的算法，这种算法应该能满足不同用户的需求，能够从复杂的网络中找到用户所需要的线路。我们首先对乘客的心理进行研究的调查，根据北京公交系统（BRT）调研报告【1】的统计结果，得到左边的饼状图：从图中可以看出快速准时是广大市民的首选，其次是换乘方便和费用低(由于费用比较少，以出行时间和换

7、乘次数为主)因此我们在设计查询系统时首先考虑时间。由此我们得到影响他们乘坐公交的主要因素：出行时间、换乘次数。对于问题一：我们只需考虑公交的情况，在文本文档公汽线路信息中一共给出了520条公汽线路，3957个公汽站点。我们分别分析出行时间、换乘次数、乘车费用，从而使建立目标函数，分别使出行时间最短、换乘次数最少、乘车费用最少。考虑到人们的心理因素，人们对换乘次数有一个最大的承受上限，不能无限制的换乘下去，所以我们限定最大换乘次数为2，即最多利用3条公交线路从起点站到达终点站。分别考虑在换乘次数为0,1,2时时间最短和乘车费用最少，时间的花费主要来自公交正常行驶的时间以及换乘公交时所花费的时间。

8、因此我们需要考虑在公交网络什么时候换乘，什么时候不需要换乘从而达到花费时间最少。乘车费用的差异主要来自选择分段计价下乘坐站数的不同以及选择不同的换乘方案等。对于问题二：我们的主要任务是在第一问的基础上修正我们构造的矩阵，以及考虑不同乘车情况下换乘时间的影响。从而建立乘车时间最短、乘车次数最少、费用最少的多目标模型，然后对模型进行求解，得出最优的乘车路线。对于问题三：此问题是在第二问的基础上，又加入了一个条件就是考虑所有站点间的步行时间，从而使从起始站到终点站所需的时间最短、换乘次数最少（步行乘车或乘车步行，考虑在内），从而建立一个多目标模型。3. 模型假设1) 出行者在所经过的站点中，不允许两

9、次经过相同的站点。2) 公交与地铁换乘距离固定，换乘、步行时间固定。3) 出行者换乘时，不受人群拥挤、交通堵塞等现象的影响且均能乘到相应线路的公汽或地铁。4) 数据文件B2007data.rar所给数据准确无误。5) 假设公交车和地铁不存在因为搭载人数满载而使市民无法搭载的情况。6) 考虑到乘车方便，假设乘客的最大换乘次数为2。7) 公交在终点处的停留时间和在站点停留的时间相同。8) 所有站点之间的步行时间均已知。9) 公交行驶速度远大于步行速度。10) 第三问中步行到车站算一次换乘。4. 符号说明：从起点站到终点站经过的站点个数（分别代表公交、地铁）：从起点站到终点站所需的换乘次数（分别代表

10、公交、地铁）：换乘点（分别代表公交、地铁）：起点到次起点之间的站点数（包括起始点，下面三个相同）：次终点到终点之间的站点数：乘客第k次乘坐公交时所乘坐的站数（包含起点、终点站，由假设6知k可取1，2，3） ：次起点到次终点之间的站点数：公交从起始站到终点站所需的时间：包含所有起点的向量：包含所有终点的向量5. 问题一的求解5.1模型一的建立从起点站到终点站的所需要的总时间由两部分构成：一是公交的行驶时间；二是乘客换乘时的耗时。公交的行驶时间等于相邻站点间的平均行驶时间乘以公交行驶的站数，即换乘时间题目已经给出，等车时间为换乘时间减去步行时间，即，因此从起点站到终点站所需的总时间为：乘客从起点到

11、终点的所需要的总费用为乘坐每一辆公交所需费用的加和。乘坐公汽时的收费分为两种情况：一种是单一票价的，无论乘坐多少站均收费1元；另一种是分段计价，分段计价的票价为：020站：1元；2140站：2元；40站以上：3元。将收费方式用数学表达式表示可写成以下的形式：其中：表示对上取整，即取不小于的最小整数。乘客从起点到终点的所需要的总费用为乘坐每一辆公交所需费用的加和，即：选择最优公交线路的目标有三个：一为乘车时间最少，二为需要费用最少，三为换乘次数最少，即利用的公交线路数最少，所以我们可以建立如下模型：目标函数：5.2模型一的求解时间的求解：a) 0次换乘，即时，b) 1次换乘，即时，即乘坐2次车c

12、) 2次换乘，即时 ，即乘坐3次车化简得：通过编程计算出结果后代入公式计算的到用时最短的路径。公交查询系统查询的步骤如下：第一步：先查找出包含起始点在内的所有路径信息，再从里面查找出包含终点B的路径，然后计算出各条路径的时间，选择用时最短的路径并列出汽车的路线编号和站点信息；如果没有找到符合条件的路径，则转入第二步；第二步：首先列出包括起点在内的所有线路信息组成数据库，再列出包括终点在内的所有路线组成数据库，然后检索两种路线里面的交叉点即为换乘点，若未检测到有交叉点则转入第三步；第三步：遍历包含起点的所有路径，遍历包含终点的所有路径，然后遍历所有的路径，找出能在和建立联系的点列（），若未检测到

13、，则停止检索，显示无结果。然后通过MATLAB编程得到：起点站终点站线路1中转站线路2时间（分）费用（元）1S3359S1828L436(下)S1784L167(下)10132S1557S0481无3S0971S0485L013(下)S2184L417(下)12834S0008S0073L159(上)S0291L058(下)8325S0148S0485无6S0087S3676L454(上)S3496L209(下)652表1：换乘1次时6对起始站终点站的最佳路线起点站终点站线路1中转站1线路2中转站2线路3时间费用1S3359S1828L015(下)S2903L027(环)S1784L167(下

14、)7332S1557S0481L084(下)S1919L189(下)S3186L460(下)10633S0971S0485L013(上)S1609L140(下)S2654L469(上)10634S0008S0073L043(下)S1383L296(环)S2184L345(上)6735S0148S0485L308(上)S0036L156(上)S2210L417(下)10636S0087S3676L021(下)S0088L231(环)S0427L097(上)463表2：换乘2次时6对起始站终点站的最佳路线5.3结果分析：以上我们分别给出了6对站点之间换乘1次和换乘2次的最佳路线，下面将综合评价这些

15、最佳路线的优劣。首先列表比较两种情况下最佳路线的时间和费用：123456方案时间费用时间费用时间费用时间费用时间费用时间费用换乘1次1013无1283832无652换乘2次733106310636731063463表3：两种方案最佳路线的时间、费用对比表我们发现除第2与第4对站点之间只有换乘两次的路线之外，其余的4对站点的时间最优解均在换乘2次时出现，而费用的最优解一般在换乘1次时出现。以第4对站点的最佳路线为例：换乘1次的时间83分钟大于换乘2次的时间67分钟，但换乘1次的费用2元小于换乘2次的费用3元，两者之间谁更优呢？而第1对站点，换乘1次的时间101分钟大于换乘2次的时间73分钟，换乘

16、1次的费用3元等于换乘2次的费用3元，但就可以说换乘2次的最佳路线比换乘1次的最佳路线更优吗？但换乘1次比换乘2次的换乘次数少。经过以上的分析我们认为每对站点之间的两组最佳路线各有优劣，对于不同目标，它们都有可能是最优解。还原到题目的背景信息：某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统，我们建议在系统界面上给出一个查询条件，乘客可以自行选择是根据时间、费用和换乘其中的哪一个为首要目标进行查询，系统根据首要目标，选择输出最佳路线。6. 问题二的求解6.1模型二的建立在问题1的基础上增加了地铁线路，乘车时间和乘车费用的表达式都将改变。在从起点A到终点B的所需要的总时间由二部分构

17、成：一是公交的行驶时间；二是乘客换乘时的耗时，包括换乘时的步行时间和等待时间。公交的行驶时间等于相邻站点间的平均行驶时间乘以公交行驶的站数，但公交此时分为公汽和地铁，而且两者相邻站点间的平均行驶时间不同：为和。每一次乘坐公交的行驶时间可表示为以下形式：换乘也存在5种情况，5种换乘的时间分别为：。每一次的换乘时间表示如下：总的耗时可以用下面的表达式来表示：乘客从起点i到终点j的所需要的总费用为乘坐每一辆公交所需费用的加和。乘坐公汽时的收费分为两种情况：一种是单一票价的，无论乘坐多少站均收费1元；另一种是分段计价，分段计价的票价为：020站：1元；2140站：2元；40站以上：3元。乘坐地铁时单一

18、票价：3元（无论地铁线路间是否换乘）将两种收费方式用数学表达式表示可写成以下的形式：其中：表示对上取整，即取不小于的最小整数。乘客从起点A到终点B的所需要的总费用为乘坐每一辆公交所需费用的加和，即：选择最优公交线路的目标有三个：一为乘车时间最少，二为需要费用最少，三为换乘次数最少，即利用的公交线路数最少，所以我们可以建立如下模型：目标函数为：6.2模型二的求解据分析，只考虑公交时，从起点到终点的途径有以下4种：直达、一次换乘、两次换乘。下面分别分析这几种途径所花费的时间和所需的换乘次数:当把换乘次数最少作为首要条件考虑时，搜索过程如下：第一步：同样建立包含起始点和终点的路径信息矩阵和，将两矩阵

19、里面所有的站点建立成二维向量；第二步：在所有的路径信息中查找包含第一步中二维向量的路径信息，包括中间站点；第三步：根据第二步中所找到的信息，计算出每一种情况所需的时间，找出最少的时间并列出换乘点。时间的求解：1. 时，时间为：2. 时，时间为：1) 起始站到次起点站之间是地铁时，即为地铁站：2) 次起点到次终点之间是地铁时，即为地铁站：3. 时，时间与情况2相同。4. 时，时间为：1) 起始站到次起点站之间是地铁时，即为地铁站：2) 次起点到次终点之间是地铁时，即为地铁站：3) 次终点到终点之间是地铁时，即为为地铁站时：在考虑以换乘次数最少为首要条件的情况下搜索出最少的换乘次数并列出换乘点和所

20、经过的站点的信息。第一步：搜索搜有公交信息（假设搜到地铁信息时可对应的搜到与该地铁站相连接的公交站点信息，故可将此类站点看做一个站点。），找出所有包含起点的公交信息组合成数据库，在数据库里面搜索终点站，若能搜索到，则输出结果，若不能，则转入第二步；第二步：按照第一步的假设，搜索出包含终点在内的公交信息组合成数据库，在数据库和里面查找有无相交点，若无，则进入第三步。第三步：列出数据库和之间的二维站点向量，搜索所有的路径信息，若包含这些而二维点，则输出，若没有，显示无结果。然后通过MATLAB求解得到：起点站终点站线路1中转站线路2时间（分）费用（元）最优目标1S3359S1828L436(下)S

21、1784L167(下)1013同时2S1557S0481无3S0971S0485L013(下)S2184L417(下)1283同时4S0008S0073L159(上)S0291L058(下)832同时5S0148S0485无6S0087S3676(D36)L021(上)S0630(D29)T2334时间6S0087S3676L454(上)S3496L209(下)652费用表4：换乘1次时6对起始站终点站的最佳路线起点站终点站线路1中转站1线路2中转站2线路3时间费用最优目标1S3359S1828L015(下)S2903L027(环)S1784L167(下)733同时2S1557S0481L08

22、4(下)S1919L189(下)S3186L460(下)1063同时3S0971S0485L094(上)S0567T1S0466L051(上)965时间L013(下)S2517L296(环)S2480L417(下)1063费用4S0008S0073L200(上)S2534T1S0609L057(上)65.55时间L198(上)S1691L296(环)S2184L345(上)673费用5S0148S0485L024(下)S1487T1S0466L051(上)87.55时间L308(上)S0036L156(上)S3332L417(下)1063费用6S0087S3676L216(下)S0400L09

23、9(上)S3874T241.55时间L021(下)S0088L231(环)S0427L097(上)463费用表5：换乘2次时6对起始站终点站的最佳路线6.3结果分析：由问题1的评价中得到的结论：当一条路线的时间、费用和换乘次数均比另一条路线少时，认为这条路线更优，可以将第6对站点间换乘2次时得到的时间和费用的最佳路线排除。7. 问题三的求解7.1模型三的建立问题三中要求在同时考虑公汽与地铁线路和步行的情况下，给出任意两公汽站点之间线路选择的一般数学模型。问题三与问题二的目标相同，还是时间最少与费用最少。首先我们来分析一下步行的意义。根据假设，步行速度和公汽的速度差距还是很大的，因此如果乘客是沿

24、着公交线路长距离行走那么步行耗时将大大多于乘车耗时，那么在什么样的情况下步行比乘车更好呢？我们总结了两种情况：一，公汽存在绕路的情况，即实际两站点距离很近，而公汽并不直接连接两站却因为其他原因绕行其他站点才到达，在这种情况下由步行从站到站的时间可能会比乘坐公交的时间短。二，虽然步行到其他公汽站点的时间变长了，但是经过步行我们可能找到新的行车线路，如果步行时间加上新线路的时间少于原线路的时间时，即：时，步行就是有意义的。从起点A到终点B的所需要的总时间由二部分构成：一是公交的行驶时间；二是乘客换乘时的耗时。公交的行驶时间等于相邻站点间的平均行驶时间乘以公交行驶的站数，但公交此时分为公汽和地铁，而

25、且两者相邻站点间的平均行驶时间不同：为和。每一次乘坐公交的行驶时间可表示为以下形式：换乘存在9种情况，9种换乘的时间分别为：。每一次的换乘时间表示如下：每一次的换乘时间表示如下：综上总的耗时可以由下面的表达式来表示：乘客从起点A到终点B的所需要的总费用为乘坐每一辆公交所需费用的加和。乘坐公汽时的收费分为两种情况：一种是单一票价的，无论乘坐多少站均收费1元；另一种是分段计价，分段计价的票价为：020站：1元；2140站：2元；40站以上：3元。乘坐地铁时单一票价：3元（无论地铁线路间是否换乘）将两种收费方式用数学表达式表示可写成以下的形式：其中：表示对上取整，即取不小于的最小整数。乘客从起点A到终点B的所需要的总费用为乘坐每一辆公交所需费用的加和，即：选择最优公交线路的目标有三个：一为乘车时间最少，二为需要费用最少，三为换乘次数最少，即利用的公交线路数最少，所以我们可以建立如下模型：目标函数为：8. 模型的评价、改进和推