公交线路的最优选择

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

k=1然后把520条公交线路读入到MATLAB当中，用MATLAB编程编程求解得到换乘1次和换乘2次6对起始站一终点站的最优路线。仅在此给出S3359-S1828的最佳路线：表1：换乘1次时S3359-S1828的最优线路方案起点站终点站线路1中转站线路2时间（分）费用（元）S3359S1828L436（下）S1784L167（下）1013表2：换乘2次时S3359-S1828的最优线路方案起点站终点站线路1中转站1线路2中转站2线路3时间费用S3359S1828L015（下）S2903L027（环）S1784L167（下）733其余结果见正文对于问题二：要求同时考虑公汽与地铁线路，我们同样建立了多目标模型，我们首先将增加的地铁线路信息添加到问题1建立的两个矩阵中，利用与问题1相似的编程思路，求解得到换乘1次和换乘2次时6对起始站一终到站之间的最佳路线。S3359-S1828的最佳路线与问题1的相同，其余结果见正文。对于问题三：要求同时考虑公汽、地铁和步行，我们建立了全局替换模型和局部替换模型。最后我们对模型进行了推广，给出了线路的“满载度”的定义，在考虑“满载度”之后，建立了新的模型。关键词：多目标规划 调查MATLAB满载度

关键词：多目标规划 调查MATLAB满载度1.1.问题重述问题的相关背景：我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。乘公交，看奥运的相关信息：1.2.1基本参数设定：相邻公汽站平均行驶时间（包括停站时间）：3分钟相邻地铁站平均行驶时间（包括停站时间）：2.5分钟公汽换乘公汽平均耗时地铁换乘地铁平均耗时地铁换乘公汽平均耗时公汽换乘地铁平均耗时5分钟（其中步行时间2分钟）公汽换乘公汽平均耗时地铁换乘地铁平均耗时地铁换乘公汽平均耗时公汽换乘地铁平均耗时4分钟（其中步行时间2分钟）7分钟（其中步行时间4分钟）6分钟（其中步行时间4分钟）公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0〜20站：1元；21〜40站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合1.2.2公交线路及相关信息（见数据文件B2007data.rar）需要解决的问题：问题一：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附件中的相关数据，利用所得到的模型与算法，求出以下6对起始站一终到站之间的最佳路线（要有清晰的评价说明)。(1)、S3359-S1828(4)、S0008-S0073(2)、S1557-S0481 (3)、S0971-S0485(5)、S0148-S0485 (6)、S0087—S3676问题二：同时考虑公汽与地铁线路，解决以上问题。问题三：假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。问题分析本文需要对乘公交、看奥运这一实际问题进行了深入的研究，设计出一种线路选择的算法，这种算法应该能满足不同用户的需求，能够从复杂的网络中找到

H：他按乘方便费用低用户所需要的线路。我们首先对乘客的心理进行研究的调查，H：他按乘方便费用低用户所需要的线路。我们首先对乘客的心理进行研究的调查，根据《北京公交系统（BRT）调研报告》【1】的统计结果，得到左边的饼状图：间。由此我们得到影响他们乘坐公交的主要因素：出行时间、换乘次数。对于问题一：我们只需考虑公交的情况，在文本文档公汽线路信息中一共给出了520条公汽线路，3957个公汽站点。我们分别分析出行时间、换乘次数、乘车费用，从而使建立目标函数，分别使出行时间最短、换乘次数最少、乘车费用最少。考虑到人们的心理因素，人们对换乘次数有一个最大的承受上限，不能无限制的换乘下去，所以我们限定最大换乘次数为2,即最多利用3条公交线路从起点站到达终点站。分别考虑在换乘次数为0丄2时时间最短和乘车费用最少，时间的花费主要来自公交正常行驶的时间以及换乘公交时所花费的时间。因此我们需要考虑在公交网络什么时候换乘，什么时候不需要换乘从而达到花费时间最少。乘车费用的差异主要来自选择分段计价下乘坐站数的不同以及选择不同的换乘方案等。对于问题二：我们的主要任务是在第一问的基础上修正我们构造的矩阵，以及考虑不同乘车情况下换乘时间的影响。从而建立乘车时间最短、乘车次数最少、费用最少的多目标模型，然后对模型进行求解，得出最优的乘车路线。对于问题三：此问题是在第二问的基础上，又加入了一个条件就是考虑所有站点间的步行时间，从而使从起始站到终点站所需的时间最短、换乘次数最少（步行f乘车或乘车f步行，考虑在内），从而建立一个多目标模型。模型假设1） 出行者在所经过的站点中，不允许两次经过相同的站点。2） 公交与地铁换乘距离固定，换乘、步行时间固定。3） 出行者换乘时，不受人群拥挤、交通堵塞等现象的影响且均能乘到相应线路的公汽或地铁。4） 数据文件B2007data.rar所给数据准确无误。5） 假设公交车和地铁不存在因为搭载人数满载而使市民无法搭载的情况。6） 考虑到乘车方便，假设乘客的最大换乘次数为2。7） 公交在终点处的停留时间和在站点停留的时间相同。8） 所有站点之间的步行时间均已知。9） 公交行驶速度远大于步行速度。10） 第三问中步行到车站算一次换乘。符号说明A:站点的起点B:站点的终点P:起始站A到终点B的费用ABa:从起点站到终点站经过的站点个数（i二1,分别代表公交、地铁）ib:从起点站到终点站所需的换乘次数（j=1，分别代表公交、地铁）jC：换乘点（j=1，分别代表公交、地铁）id:起点到次起点之间的站点数（包括起始点，下面三个相同）1e:次终点到终点之间的站点数jm:乘客第k次乘坐公交时所乘坐的站数（包含起点、终点站，由假设6k知k可取1，2，3）s:换乘次数h:次起点到次终点之间的站点数ijT:公交从起始站到终点站所需的时间L:包含所有起点的向量AL:包含所有终点的向量Bt:相邻公汽站平均行驶时间1t:相邻地铁站平均行驶时间2t:公汽换乘公汽平均耗时3t:地铁换乘地铁平均耗时4t:地铁换乘公汽平均耗时5t:公汽换乘地铁平均耗时6t:公汽与公汽、地铁与地铁站间的步行耗时7t:公汽与地铁站间的步行耗时8t:任意两站之间的步行时间ij问题一的求解5.1模型一的建立从起点站到终点站的所需要的总时间T由两部分构成:一是公交的行驶时间；二是乘客换乘时的耗时。公交的行驶时间等于相邻站点间的平均行驶时间乘

以公交行驶的站数，即£(m-1)*tk1k=1换乘时间题目已经给出，等车时间为换乘时间减去步行时间，即t*s+(t-1)(s+1),因此从起点站到终点站所需的总时间为：337T=£(m-1)*t+1*s+(t-1)(s+1)k 1 3 3 7k=1乘客从起点A到终点B的所需要的总费用PA为乘坐每一辆公交所需费用的加和。乘坐公汽时的收费分为两种情况：一种是单一票价的，无论乘坐多少站均收费1元；另一种是分段计价，分段计价的票价为：0〜20站：1元；21〜40站：2元；40站以上：3元。将收费方式用数学表达式表示可写成以下的形式：'1 乘客第k次乘坐的公汽为单一票价时P=<mk 2^ 乘客第k次乘坐的公汽为分段计价时其中：表示对翁上取整,即取不小于m其中：表示对翁上取整,即取不小于m的最小整数。乘客从起点A到终点B的所需要的总费用碁为乘坐每一辆公交所需费用的加和，即:AB=£npABkk=1选择最优公交线路的目标有三个：一为乘车时间最少，二为需要费用最少三为换乘次数最少，即利用的公交线路数最少，所以我们可以建立如下模型：目标函数：minT=(mk=minT=(mk=1minsminpAB=£nk=10<s<2pk一1)*t+1*s+(t一t)(s+1)k 1 3 3 7s.t.<乘客第k次乘坐的公汽为单一票价时mk20乘客第k次乘坐的公汽为分段票价时5.2模型一的求解时间的求解：a)0次换乘，即h丰0,d=0,e=0时间的求解：a)0次换乘，即h丰0,d=0,e=0时,ijijT二t*(h-1)+(t-1)1ij37b)1次换乘，即h丰0,d丰0,e二0时，即乘坐2次车ijijIt*(d+h一2)+2*(t一t)+1I1iij 3 7 3t*(e+h一2)+2*(t-1)+11iij 3 7 3c)2次换乘，即h丰0,d丰0,e丰0时，即乘坐3次车ijijT=t*(d+e+h一3)+3*(t—t)+1*21jiij 3 7 3化简得：'t*hI1ijt*(d+h)+1I1iij3t*(e+h)+11iij3t*(d+e+h)+2t1jiij3通过编程计算出结果后代入公式计算的到用时最短的路径。公交查询系统查询的步骤如下：第一步：先查找出包含起始点在内的所有路径信息M，再从里面查找出包A含终点B的路径，然后计算出各条路径的时间，选择用时最短的路径并列出汽车的路线编号和站点信息；如果没有找到符合条件的路径，则转入第二步；第二步：首先列出包括起点在内的所有线路信息组成数据库M，再列出包A括终点在内的所有路线组成数据库M，然后检索两种路线里面的交叉点即为换B乘点，若未检测到有交叉点则转入第三步；第三步：遍历包含起点的所有路径L，遍历包含终点的所有路径L，然后AB遍历所有的路径，找出能在L和L建立联系的点列（h,h），若未检测到，则A B ij停止检索，显示无结果。然后通过MATLAB编程得到起点站终点站线路1中转站线路2时间（分）费用（元）1S3359S1828L436(下)S1784L167(下)10132S1557S0481无3S0971S0485L013(下)S2184L417(下)1283

4S0008S0073L159（上）S0291L058（下）8325S0148S0485无6S0087S3676L454（上）S3496L209（下）652表1：换乘1次时6对起始站一终点站的最佳路线起点站终点站线路1中转站1线路2中转站2线路3时间费用1S3359S1828L015（下）S2903L027（环）S1784L167（下）7332S1557S0481L084（下）S1919L189（下）S3186L460（下）10633S0971S0485L013（上）S1609L140（下）S2654L469（上）10634S0008S0073L043（下）S1383L296（环）S2184L345（上）6735S0148S0485L308（上）S0036L156（上）S2210L417（下）10636S0087S3676L021（下）S0088L231（环）S0427L097（上）463表2：换乘2次时6对起始站一终点站的最佳路线5.3结果分析：以上我们分别给出了6对站点之间换乘1次和换乘2次的最佳路线，下面将综合评价这些最佳路线的优劣。首先列表比较两种情况下最佳路线的时间和费用：123456、.1?>万案时间费用时间费用时间费用时间费用时间费用时间费用换乘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分钟，换乘1次的费用3元等于换乘2次的费用3元，但就可以说换乘2次的最佳路线比换乘1次的最佳路线更优吗？但换乘1次比换乘2次的换乘次数少。经过以上的分析我们认为每对站点之间的两组最佳路线各有优劣，对于不同目标，它们都有可能是最优解。还原到题目的背景信息：某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统，我们建议在系统界面上给出一个查询条件，乘客可以自行选择是根据时间、费用和换乘其中的哪一个为首要目标进行查询，系统根据首要目标，选择输出最佳路线。问题二的求解6.1模型二的建立在问题1的基础上增加了地铁线路，乘车时间和乘车费用的表达式都将改变。在从起点A到终点B的所需要的总时间T由二部分构成：一是公交的行驶AB

时间；二是乘客换乘时的耗时，包括换乘时的步行时间和等待时间。公交的行驶时间等于相邻站点间的平均行驶时间乘以公交行驶的站数，但公交此时分为公汽和地铁，而且两者相邻站点间的平均行驶时间不同：为t和t。每一次乘坐公交12的行驶时间可表示为以下形式：m*tk1m*tk1m*tk2乘客第k次乘坐的公交为公汽时次的换乘时换乘也存在5种情况，5种换乘的时间分别为：t,t,t,t,2t。每次的换乘时34566间表示如下：乘客第k次换乘为公汽换乘公汽t4T换k t4T换k 5t62*t6乘客第k次换乘为地铁换乘公汽乘客第k次换乘为公汽换乘地铁乘客第k次换乘为公汽换乘公汽需要地铁总的耗时T可以用下面的表达式来表示:ijT二乙T+ZTAB 换kk=1 k=1乘客从起点i到终点j的所需要的总费用P为乘坐每一辆公交所需费用的加ij和。乘坐公汽时的收费分为两种情况:一种是单一票价的，无论乘坐多少站均收费1元；另一种是分段计价，分段计价的票价为：0〜20站：1元；21〜40站：2元；40站以上:3元。乘坐地铁时单一票价:3元（无论地铁线路间是否换乘）将两种收费方式用数学表达式表示可写成以下的形式：‘1 乘客第k次坐的公交为单一票价的公汽时[m]乘客第k次坐的公交为分段票价的公汽时P=120k3 乘客第k次乘坐的公交为地铁且为公汽换乘的地铁时0 乘客第k次乘坐的公交为地铁且为地铁换乘的地铁时其中：関表示对m上取整，即取不小于分的最小整数。乘客从起点A到终点B的所需要的总费用PAB为乘坐每一辆公交所需费用的加和，即:np=LpAB kk=1选择最优公交线路的目标有三个：一为乘车时间最少，二为需要费用最少三为换乘次数最少，即利用的公交线路数最少，所以我们可以建立如下模型：

S.t.<目标函数为:minTS.t.<目标函数为:minT=》T+艺TAB换kk=1%k=1minP=ZpAB kk=1mins20乘客第k次坐的公交为单一票价的公汽时乘客第k次坐的公交为分段票价的公汽时乘客第k次乘坐的公交为地铁且为公汽换乘的地铁时乘客第k次乘坐的公交为地铁且为地铁换乘的地铁时6.2模型二的求解据分析，只考虑公交时，从起点A到终点B的途径有以下4种：直达、一次换乘、两次换乘。下面分别分析这几种途径所花费的时间和所需的换乘次数：当把换乘次数最少作为首要条件考虑时，搜索过程如下：第一步：同样建立包含起始点和终点的路径信息矩阵M和M，将两矩阵A B里面所有的站点建立成二维向量；第二步：在所有的路径信息中查找包含第一步中二维向量的路径信息，包括中间站点；第三步：根据第二步中所找到的信息，计算出每一种情况所需的时间T，找出最少的时间并列出换乘点。时间的求解：1.d=0,h丰0,e=0时，时间为：i ij j直达：t*(h-1)+(t+1)TOC\o"1-5"\h\zv 2 ij 68换乘：t*(h—1)+2tJ 2 ij 6d丰0,h丰0,e=0时，时间为：i ij j起始站到次起点站之间是地铁时，即d为地铁站：j「地铁不换乘：t*(d—1)+1*(h—1)+1+12 2i 1ij 6 5］地铁换乘：t*(d—1)+1*(h—1)+1+1+12i 1ij 6 5 4次起点到次终点之间是地铁时，即h为地铁站：ij「地铁不换乘：t*(h—1)+1*(d—1)+1+1+(t—t)2 2ij 1j 58 3 7丨地铁换乘：t*(h—1)+1*(d—1)+1+1+(t—t)+12ij 1j 5 4 3 7 8d=0,h丰0,e丰0时，时间与情况2相同。ij jd丰0,h丰0,e丰0时，时间为：i ij j起始站到次起点站之间是地铁时，即d为地铁站：j〔地铁不换乘：t*(d—1)+1*(h+e—2)+1+1+12 2i 1 ijj 6 5 3丨地铁换乘：t*(d—1)+1 *(h +e—1)+1 +1 +1 +12i 1ijj 6 5 3 8次起点到次终点之间是地铁时，即h为地铁站：ij「地铁不换乘：t*(h—1)+1*(d+e—2)+1+2t2 2ij 1jj 1 6丨地铁换乘：t*(h—1)+1*(d+e—2)+1+2t+12j 1jj 1 6 8次终点到终点之间是地铁时，即e为为地铁站时：j「地铁不换乘：t*(e—1)+1*(d+h—2)+1+1+1+12j 1ij 13 6 4］地铁换乘：t*(e—1)+1*(d+h—2)+1+1+1+1+12j 1ij 1 3 6 4 8在考虑以换乘次数最少为首要条件的情况下搜索出最少的换乘次数并列出换乘点和所经过的站点的信息。第一步：搜索搜有公交信息(假设搜到地铁信息时可对应的搜到与该地铁站相连接的公交站点信息，故可将此类站点看做一个站点。)，找出所有包含起点的公交信息组合成数据库Ma，在数据库□里面搜索终点站，若能搜索到，则输出结果，若不能，则转入第二步；第二步:按照第一步的假设，搜索出包含终点在内的公交信息组合成数据库,在数据库口和Mb里面查找有无相交点，若无，则进入第三步。

第三步：列出数据库「71和MB之间的二维站点向量（h,h），搜索所有的路径信息，若包含这些而二维点，则输出，若没有，显示无结果。然后通过MATLAB求解得到：起点站终点站线路1中转站线路2时间（分）费用（元）最优目标1S3359S1828L436（下）S1784L167（下）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同时2S1557S0481L084（下）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（下）S0400L099（上）S3874T241.55时间L021（下）S0088L231（环）S0427L097（上）463费用表5：换乘2次时6对起始站一终点站的最佳路线6.3结果分析：由问题1的评价中得到的结论：当一条路线的时间、费用和换乘次数均比另一条路线少时，认为这条路线更优，可以将第6对站点间换乘2次时得到的时间和费用的最佳路线排除。7•问题三的求解7.1模型三的建立问题三中要求在同时考虑公汽与地铁线路和步行的情况下，给出任意两公汽站点之间线路选择的一般数学模型。问题三与问题二的目标相同，还是时间最少与费用最少。首先我们来分析一下步行的意义。根据假设，步行速度和公汽的速度差距还是很大的，因此如果乘客是沿着公交线路长距离行走那么步行耗时将大大多于乘

车耗时，那么在什么样的情况下步行比乘车更好呢？我们总结了两种情况：一，公汽存在绕路的情况，即实际A,B两站点距离很近，而公汽并不直接连接两站却因为其他原因绕行其他站点才到达，在这种情况下由步行从A站到B站的时间可能会比乘坐公交的时间短。二，虽然步行到其他公汽站点的时间变长了，但是经过步行我们可能找到新的行车线路，如果步行时间加上新线路的时间少于原线路的时间时，即：T+T <T步行 新路线 原路线时，步行就是有意义的。从起点A到终点B的所需要的总时间T由二部分构成：一是公交的行驶时AB间；二是乘客换乘时的耗时。。公交的行驶时间等于相邻站点间的平均行驶时间乘以公交行驶的站数，但公交此时分为公汽和地铁，而且两者相邻站点间的平均行驶时间不同：为t和t。每一次乘坐公交的行驶时间可表示为以下形式:12换乘存在m*tk换乘存在m*tk1m*tk2乘客第k次乘坐的公交为公汽时况， 9种换乘的时间分别为t,t,t,t,2t,t+(t—t),t+(t—t),t+(t—t),t+(t—t)。每一次的换乘时34566ij37ij47ij47ij37间表示如下：每一次的换乘时间表示如下：t 乘客第k次换成为公汽换成公汽3t 乘客第k次换成为地铁换成地铁4t 乘客第k次换成为地铁换成公汽5t 乘客第k次换成为公汽换成地铁6<2*t 乘客第k次换成为公汽换成公汽需要地铁6t + (t — t ) 乘客第k次换乘为公汽换成步行再换成公汽TOC\o"1-5"\h\zij 3 7t + (t — t ) 乘客第k次换乘为地铁换成步行再换成地铁ij 4 7t + (t — t ) 乘客第k次换乘为公汽换成步行再换成地铁ij 4 7t + (t — t ) 乘客第k次换乘为地铁换成步行再换成公汽ij 3 7综上总的耗时T可以由下面的表达式来表示：ijT二艺T+ETAB 行k 换kk=1 k=1乘客从起点A到终点B的所需要的总费用P为乘坐每一辆公交所需费用的AB

加和。乘坐公汽时的收费分为两种情况：一种是单一票价的，无论乘坐多少站均收费1元；另一种是分段计价，分段计价的票价为：0〜20站：1元；21〜40站:元；40站以上：3元。乘坐地铁时单一票价：3元（无论地铁线路间是否换乘）将两种收费方式用数学表达式表示可写成以下的形式：‘1 乘客第k次坐的公交为单一票价的公汽时p_[m]乘客第k次坐的公交为分段票价的公汽时k乘客第k次乘坐的公交为地铁且为公汽换乘的地铁时0 乘客第k次乘坐的公交为地铁且为地铁换乘的地铁时其中：Fz]表示对m上取整，即取不小于m的最小整数。乘客从起点A到终L20」 20 20点B的所需要的总费用鼻为乘坐每一辆公交所需费用的加和，即:np_LpAB kk_1选择最优公交线路的目标有三个：一为乘车时间最少，二为需要费用最少三为换乘次数最少，即利用的公交线路数最少，所以我们可以建立如下模型：目标函数为：minT_》T+艺TAB换kk_1%?k_1minp_乙pAB kk_1mins'0<s<2m>1kS.t.<S.t.<P_k