搜索
1/24乘公交看奥运摘要本设计要解决的是合理给出两站点间的最佳路线选择问题，即给出一条经济且省时的路线。在处理此问题之前，我们根据调查和分析，对影响线路选择的因素进行筛选，最终确定了以下三个影响较大的因素：第一是换乘次数；第二是乘车时间；第三是乘车费用。依据各因素对路线选择的影响程度,我们按不同的权重对它们进行考虑。从实际情况分析，人们通常宁愿多乘坐几站地也不愿换车，所以我们赋予换乘次数较大的权重。为了解决换乘次数最少，乘车时间相对较短、乘车费用相对较少的问题，经过尝试与探索，我们采用了现代分析的方法，对起始站和终点站有无相交站点进行分类讨论，归纳出直达，换乘一次，换乘两次的情况三次以上的情形可以类推），并通过Matlab编制程序，给出了任意两站点间的最佳乘车路线以及换车的地点，最后还提出了进一步的意见和建议。b5E2RGbCAP关键词：最佳路线换乘次数乘车时间乘车费用2/24一、问题的重述第29届奥运会明年8月将在北京举行，作为城市枢纽的公共交通承担着非常重的运输任务。近年来，北京市的公交系统有很大的发展，公交线路的条数和公交车数量在迅速增多，给人民生活带来便利的同时，也面临多条线路得选择问题，有时出行往往还需要转乘多辆公交车才能到达目的地。如何在短时间、换乘次数最少、成本最低的情况到达目的地，是人们所关注的问题。p1EanqFDPw因此，我们通过建立线路选择的模型与算法，设计一套自主查询计算机系统，查询到出行时所需的最佳公交路线及换乘方法，给人们出行节约更多的时间和金钱。DXDiTa9E3d要求：1、仅考虑公汽线路，建立任意两公汽站点之间线路选择问题的数学模型与算法。并求出以下6对起始站→终到站之间的最佳路线。RTCrpUDGiT1）S3359→S18282）S1557→S04813）S0971→S04855PCzVD7HxA4）S0008→S00735）S0148→S04856）S0087→S3676jLBHrnAILg2、同时考虑公汽与地铁线路，解决1中问题。3、如果所有站点间的步行时间已知，建立任意两站点间路线选择问题的数学模型。二、模型的假设1、所有公交线路的开班、收班时间相同。2、公车不会因为堵车等因素延长行驶时间。3、各条线路不会有新的调整与变化。4、环线可以以任意站作为起点站和终点站，并且是双向的。5、除环线以外的线路，到达终点站后，所有的人都必须下车。6、人们对换乘车次数尽量少的偏好程度总是大于对花费时间相对短和花费金钱相对少的偏好程度。7、同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁费。三、符号的说明符号表示意义第条包含初始站点的线路，第条包含目标站点的线路，3/24符号表示意义第条中间线路，上的第个站点，上的第个站点，上的第个站点，乘客在第段线路上乘坐的站数乘客在一次地铁线路上乘坐的总站数公汽换乘公汽的次数地铁换乘地铁的次数地铁换乘公汽的次数公汽换乘地铁的次数四、问题的分析、模型的建立及求解4.1问题一4.1.1问题一的分析已知相邻公汽站平均行驶时间(包括停站时间：3分钟；公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟。公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段估计票价为：0～20站：1元；21～40站：2元；40站以上：3元。题目要求设计任意两公汽站点之间线路选择问题的数学模型与算法。对于附录中的1.1公汽线路信息.txt中的数据进行处理后，以文本文件形式导入Matlab中，找到了站点与站点之间的关系。进一步发现表明无论试图产生邻接矩阵或边权矩阵因数据太庞大而可行性极低，其运行时间长达50分钟，故考虑按题目给的路线来建立站点矩阵并对此矩阵进行处理后能够清晰有效地应用此矩阵。xHAQX74J0X4.1.2模型的建立及求解4/24模型一设为乘坐公交线路的费用函数：，总时间函数：1）总费用函数：2）其中表示乘客在公交线路上乘坐的站数；表示公汽换乘公汽的次数。目标：找出任意给定的两站点的乘车线路，使和相对最小。算法思路：由于人们的对换乘车次数尽量少的偏好程度总是大于对花费时间和金钱相对少的偏好程度，我们将优先考虑换乘车次数尽量少，然后再考虑花费时间相对短、花费金钱相对少，对得出的所有结果中进行筛选。换乘次数的大概思路及步骤如下：LDAYtRyKfE将所有包含初始站点的线路建成一个集合S，，，所有包含目标站点的线路建成一个集合G，，。，，，，，。1、直达的线路。当时，存在、，，，使得，即、为同一线路。此线路既包含初始站点又包含目标站点。5/24若，那么，此线路为所求直达线路。若，或者当时，考虑换乘一次的线路。2、换乘一次的线路。当有和相交时，存在、，，，有及，，。使得，即、为同一站点。若，，那么，从初始站点乘坐线路，行驶至站点，即在站点，换乘线路至目标站点。即若不满足，，或者，当无任何和相交时，考虑换乘两次的线路。3、换乘两次的线路。记，，，有，，，且满足与、都相交时，即线路既不包含初始站点又不包含目标站点，，。但是存在及，使得，存在及，使得，即、为同一站点，且、为同一站点。，，，，，，。若，，，那么，从初始站点乘坐线路，行驶至站点，即在站点，换乘线路至站点，即在站点，换乘线路至目标站点。即Zzz6ZB2Ltk6/24若不满足，，，或者，当不存在满足条件的时，说明需要换乘三次才能够到达目标站点。换乘三次的线路的模型建立原理是相同的。由于几乎没有这样的情况，故我们不作考虑。dvzfvkwMI1通过考虑花费的时间或金钱，在得出的多条结果中进行筛选。4.1.3问题一的结果由于公交线路的固定性、重叠性和可选择性,使得公交乘客出行线路选择行为具有相当的复杂性。由公交乘客的路径选择特性可知,乘客总是根据个人偏好选择出行路线(或希望出行时间最少,或希望换乘次数最少,或希望出行费用最低,可称之为最短路因素。同时,由于公交网络的复杂性,使得最短路判断出现差异,而个人选择行为带有一定的随机性,所以多路径选择较为符合乘客的行为特点。另外一个方面，当乘客要进行一次换乘时，他会考虑到时间或者费用等问题，但当乘客必须二次换乘时，时间是决定乘客选择路线的唯一因素，所以在这种情况下我们只考虑途经站点最少的二次转乘路线。基于以上考虑,我们对每道小题都给出了多种乘车路线，以供乘客根据自己的需要选择。rqyn14ZNXI程序见附录8.1、附录8.2、附录8.3）1）S3359→S1828线路条）初始站Chapter(NextSection1EquationChapter1Section1换乘站(换乘站目标站时间分）金钱元）1S3359Chapter(NextSection1EquationChapter1Section1S1784S182810132S3359Chapter(NextSection1EquationChapter1Section1S1784S182810133S3359Chapter(NextSection1EquationChapter1Section1S3515S1784S18289434S3359Chapter(NextSection1EquationChapter1Section1S0359S1784S182894353359Chapter(NextSection1EquationChapter1Section1S3515S1784S1828943评价说明：经Matlab运行程序，得出了5条优化线路。其中，1、2条换乘7/24一次，3、4、5条换乘两次，3、4、5条线路比1、2条线路多换乘一次，所花的金钱相同，但是节省了7分钟时间。EmxvxOtOco乘客根据自己的需要进行选择。2）S1557→S0481线路条）初始站Chapter(NextSection1EquationChapter1Section1换乘站(换乘站目标站时间分）金钱元）1S1EquationChapter(NextSection1557EquationChapter1Section1S1919S2424S048111232S1EquationChapter(NextSection1557EquationChapter1Section1S1919S2424S048111233S1EquationChapter(NextSection1557EquationChapter1Section1S1919S2424S048111234S1EquationChapter(NextSection1557EquationChapter1Section1S1919S2424S048111235S1EquationChapter(NextSection1557EquationChapter1Section1S1919S2424S048111236S1EquationChapter(NextSection1557EquationChapter1Section1S1919S2424S048111237S1EquationChapter(NextSection1557EquationChapter1Section1S1919S2424S048111238S1EquationChapter(NextSection1557EquationChapter1Section111238/24S1919S2424S04819S1EquationChapter(NextSection1557EquationChapter1Section1S1919S2424S04811123评价说明：经Matlab运行程序，得出了9条优化线路。乘坐这9条线路所花费的时间和金钱都相同，且均需要换乘两次。不存在换乘一次的线路。SixE2yXPq5乘客可以选择任意一条线路。3）S0971→S0485线路初始站Chapter(NextSection1EquationChapter1Section1换乘站(换乘站目标站时间分）金钱元）1S0971EquationChapter1Section1S2184S048512832S0971EquationChapter1Section1S0992S048513133S0971EquationChapter1Section1S3405S2515S04859434S0971EquationChapter1Section1S1520S2265S04859435S0971EquationChapter1Section1S1520S2654S04859436S0971EquationChapter1Section1S1520S1729S04859437S0971EquationChapter1Section1S1520S3766S04859438S0971EquationChapter1Section19439/24S1520S2265S04859S0971EquationChapter1Section1S1520S2265S0485943评价说明：经Matlab运行程序，得出了9条优化线路。其中，1条换乘一次，3~9条换乘两次，3~9条线路比1条线路多换乘一次，所花的金钱相同，但是节省了37分钟时间。6ewMyirQFL乘客根据自己的需要进行选择。4）S0008→S0073线路初始站Chapter(NextSection1EquationChapter1Section1换乘站(换乘站目标站时间分）金钱元）1S0008EquationChapter1Section1S2083S00738322S0008EquationChapter1Section1S2263S00738323S0008EquationChapter1Section1S2683S00738324S0008EquationChapter1Section1S0400S00738325S0008EquationChapter1Section1S2559S0073833