数学建模论文-公交系统最佳路线的查询模型.doc

1公交系统最佳路线的查询模型摘要本文针对“乘公交，看奥运”的问题，建立了多目标优化模型，解决了仅坐公车，可坐公车和地铁，可坐公车、地铁或步行等三种情况下最佳出行路线的确定问题。对于问题一，我们用多目标决策中的分层序列法对该多目标问题优化，建立了分别以“换乘次数最少为第一目标，出行时间最短和车费最少为第二、第三目标”和以“出行时间最短为第一目标，换乘次数最少和车费最少为第二、第三目标”的优化模型和模型。同时，给出了乘客满意度函数，根据不同乘客的需求，对这两种模型进行了比较，满足了不同乘客的需求。在模型情况下，6对起始站终点站的最佳线路有：18283559SS：最佳路线有2条，转车1次，耗时104分，车费共3元；04811557SS：最佳路线有2条，转车2次，耗时109分，车费共3元；04850971SS：最佳路线有1条，转车1次，耗时131分，车费共2元；00730008SS：最佳路线有5条，转车1次，耗时86分，车费共2元；04850148SS：最佳路线有1条，转车2次，耗时109分，车费共3元；36760087SS：最佳路线有1条，转车1次，耗时68分，车费共2元。对于问题二，我们通过改进后的Floyd算法，将地铁交通系统嵌入原有的公交系统中，并分层序列法建立的优化模型，得出了较第一问时间上更优化的路线。6对起始站终点站的最佳线路有：18283559SS：最佳路线有1条，共转车3次，其中公交与地铁间转乘2次，地铁与地铁间转乘1次，耗时87.5分钟，车费共计5元。04850971SS：最佳路线有10条，转车2次，都为公交与地铁间转车，耗时99分钟，车费共计5元。00730008SS：最佳路线有1条，转车2次，其中公交与地铁间转乘2次，地铁与地铁间转乘1次，耗时56.5分钟，车费共计5元。36760087SS：最佳路线有1条，转车0次，通过地铁到达，耗时30分钟，车费共计3元。对于问题三，我们提出了交通阻抗的概念，得到了乘客在公交线上出行的换乘次数、出行时间、乘车费用、乘车距离等综合费用指标，将多目标优化问题转化为了单目标优化问题。并以18283559SS为例，进行了计算，得出对于最佳路线为3359S乘坐（下行）436L在S1784下车，步行一站至1828S。关键词：多目标优化模型；分层序列法；乘客满意度；交通阻抗；综合费用指标2一、问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359S1828(2)、S1557S0481(3)、S0971S0485(4)、S0008S0073(5)、S0148S0485(6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。二、问题分析该问题是一个解决城市公交系统最佳路线的优化问题。首先，由于原题中给的数据不规范，为了实现Matlab的编程，须对数据进行预处理。对数据初步分析，可以发现，一般来说，每条线路都有上行和下行之分，但如果下行线是上行线原路返回或是环线，即缺失了下行线数据。为了简化编程，我们将缺失的下行数据进行如下处理：若下行线是上行线的原路返回，则将上行线的站点逆置后加到对应的下行线中；而对于环行线，则直接照搬到对应的下行线中。其次，解决城市公交系统的最优路线选择问题，需要结合乘客的多方需要，从市场调查分析中，我们可以把乘客的基本需求归纳为：换乘次数应尽量减少；乘车时间应尽量节省；乘车费用应尽量降低；乘车经过的站数尽量少。因此，我们应该建立一个多目标的优化模型来对最优线路进行选择。再次，对城市公交路线进行最优分析，需要把公交系统的实体抽象成图论中的网络拓扑图，Dijkstra算法是当今在最短路问题中比较常用的方法，但是在此处，该算法不完全适用，因为，1该算法要求要求给出两点间的直接距离，而在此处，上千个公交站点之间的距离并未直接给出，我们需要在考虑时间、票价的同时给出相应的权值，工作量较大。2该算法算出的是一点到其余各点的权值最少路径，城市的公交站点有上千个，用该算法计量很大，使公交系统的查询时间过长。33该算法给出的是最短路径图，在选择路线的时候可能适用，但在选择公交路线时可能未考虑乘客不愿意转乘的心理，其计算结果可能造成乘客需要换乘好几次或十几次才能够到达目的地,这显然是没有任何意义的。因此我们采用了改进的Dijkstra算法对问题进行求解。最后，在第二问同时考虑公交和地铁线路时，出现了一个地铁站对应一个或多个公车站的情况，由于一个地铁站对应的多个公车站之间可以通过地铁站换乘，必须对题中给出的换乘时间及步行时间做进一步细化，如表1表1细化后换乘时间表公汽车站间步行平均耗时21t分钟地铁车站间步行平均耗时22t分钟公汽车站与地铁站间步行平均耗时43t分钟等待公车的平均耗时34t分钟等待地铁的平均耗时25t分钟公汽换乘公汽平均耗时56t分钟地铁换乘地铁平均耗时47t分钟地铁换乘公汽平均耗时78t分钟公汽换乘地铁平均耗时69t分钟第三问增加步行的方式，加大了路线选择的灵活性，但由于各站点之间的明确距离或步行时间未给出，我们只能给出初步的模型。三、模型假设1.假设题目所给的数据真实可靠；2各种公交方式都正常运行，如：公交车道不堵车，每列地铁正点按班到站等。3各种公交方式的平均邻站行驶时间及换乘时间基本符合实际情况。4.乘客所能接受的最大换乘次数为2次，若包括地铁与地铁之间的换乘，乘客的最大换乘次数不超过3次。4四、定义与符号说明N表示换乘总次数M表示乘车总费用T表示乘车总耗时表示通过车站jS的公车数表示两站iS、jS之间可直达的公车数表示iS和jS之间的一次中转站个数表示与iS可通过一次公车直达的车站个数表示能在地铁站lD换乘的公车数表示从地铁站iD到地铁站jD所有路径数jS表示公车站)3,2,1(),(aaSBj表示通过车站jS的公车)3,2,1(),(ddSSPji表示两站iS、jS之间可直达的公车)3,2,1(),(1ddSSTji表示乘),(dSSPji车从iS到jS的时间)3,2,1(),(1ddSSMji表示乘),(dSSPji车从iS到jS的车费)3,2,1(),(eeSSiz表示与iS可通过一次公车直达的车站)3,2,1(),(hhSSCji表示iS和jS之间的一次中转站)3,2,1(),(rrDSld表示能在地铁站lD换乘的公车),2,1(),(2wwDDTji表示从地铁站iD到地铁站jD的时间2M表示从地铁站iD到地铁站jD的车费5五、问题一的模型建立与求解（一）模型的分析首先，选择公交方式出行时,可行的乘车方案一般有多个,出行者必须做出选择。而出行者考虑的因素很多,不能简单的抽象为最短路问题。因此需要对公交乘客的出行心理、行为进行调查研究，确定模型的优化目标和约束条件。公交乘客选择出行路径的决策过程主要受到以下4个因素的影响:“换乘次数”、“出行距离”、“出行耗时”和“车费”。所以，这个问题是一个多目标优化问题。其目标是，MinMinMinMinFNMT由于同时处理多个目标问题的最优化较困难，经常是有所失才能有所得，故我们采用分层序列法分析。分层法的思想是把目标按其重要性给出一个序列，分为最重要目标，次要目标等等。为了得出各项指标的重要性，我们查找了相关资料。图1是1999年在南京市的8个主要公交站点进行了一次公交乘客出行心理问询调查结果。由图1可见,41.16%的乘客在选择出行路径时首选考虑的是换乘最少,其次是时间最短。并考虑到题目数据中只给出的耗时数据及乘车费用,而且一般来说，当相邻公汽站平均行驶时间和换乘车时间基本确定时，路程的长短与出行时间的长短成正比。故除了换乘次数，我们还选择了易于量化的“公交出行时间最少”和“车费最少”。在上述分析的基础上，我们分别选用“换乘次数最少”和“时间最少”作为第一优化目标,建立了分层优化的多目标模型和模型。6（二）模型的建立1按上所述，模型以换乘次数最少为第一目标，出行时间最短和车费最少分别为第二和第三目标。设其序列分别为)(0xN，)(0xT，)(0xM，然后逐个将其最优化：对第一目标即换乘次数最少求最优并找出所有最优解的集合记为0R。然后在0R内求第二个目标即出行时间最短的最优解，记这时的集合为1R。最后在1R内求第三目标即乘车费用最少的最优解，记这时的集合为2R,其模型如下：)()(0010xNxNMinRRxMinRRxxT01)(01)(0xTMinRRxxM12)(01)(0xM若2R，则集合2R为模型的最佳线路。2算法的描述（1）算法的流程图描述流程图如图2。图2模型算法流程图7（2）算法的数学描述1)符号定义1.起始站为mS，则通过起始站的公车为),(bSBm；2.终点站为nS，则通过终点站的公车为),(cSBn。2）若存在cb,使得),(),(cSBbSBnm，则mS与nS可直达做该次公车从iS到jS的时间为),(1dSSTji；车费为),(1dSSMji。这种情况下优化第二目标的算法为Min41),(tdSSTnm；优化第三目标的算法为Min),(1dSSMnm。3)若通过换乘车一次可到达考虑起始站和终点站，那么有),(fSSmz、),(gSSnz。若存在gf,，使得),(),(gSSfSSnzmz，说明mS和nS可以通过),(fSSmz即),(gSSnz站中转。那么乘客所乘的公车车次为分别为),(,(,uhSSCSPnmm、),),(vShSSCPnnm。这种情况下优化第二目标的算法为Min64