2007年乘公交,看奥运优秀论文.doc

2012高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 2007B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：乘公交，看奥运摘要这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。本文针对公交线路的的选择问题，采用多目标规划求解，根据题意，我们用三个目标进行规划，这三个目标分别是路径、花费和换乘次数。用Dijkstra、邻接矩阵等多种算法和理论建立模型，并提出了满足题中6对公交站点的最佳路径算法，针对实际问题给出了合理的选择方案。对于问题一，我们从附录数据中，建立邻接矩阵，通过matlab搜索经过任意一对起点到终点的线路,再从三个目标入手分别来优化求解：目标一：最小路径将附录2中的数据载入matlab，并用自定义的算法确立站点间的邻接矩阵，再用Dijkstra算法求解，最终得到6对站点的最小路径。目标二：最小花费分析附录2中的数据，将所有路线信息、收费信息导入matlab，建立矩阵，搜索任意两站点的路线。为缩小数据的维数，我们从6对站点，建立可达矩阵，再对应收费信息，算出每个线路花费的钱数，最后搜索这些可行解的最小花费输出，作为最终最小花费方案。目标三：最小换乘次数全面分析附录数据，将公交线路的完全信息导入matlab，建立所有路线与站点关系的（0，1）矩阵，根据换乘算法的原理和方法建立模型，确立条件约束，针对题中所给的6对公交站点，我们采取深度广度优先搜索，确立通过这些点的线路和信息，再由线路间的关系用换乘算法的方法来求解。对于问题二，我们现将地铁和公汽的换乘信息打包放入公汽路线，将每个地铁站点带入到与其邻近的公汽站点，统一作为新的公交路线来对待，将新问题转化为旧问题来考虑，并最终用换乘算法来求解，分别求出这三个目标的最优解，并对其进行分析。对于问题三，在已知所有站点之间的步行时间时，即可知对步行来说所有站点之间都是邻接的，则设定步行最多站点数n ,于是问题转化成为使用公交和步行两者综合最优的问题，进而固定步行行驶范围，求解范围内所有点与终点通过公交到达的模型，降介法求解多目标规划。关键词：多目标规划、Dijkstra算法、邻接矩阵、最优化求解、MATLAB一、问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)： 3分钟；相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟；公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)；地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)；地换乘公汽平均耗时：7分钟(其中步行时间4分钟)；公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)；公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元；地铁票价：3元（无论地铁线路间是否换乘）；注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。二、问题分析2.1 问题一已知相邻公汽站平均行驶时间(包括停站时间)：3分钟；公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)；公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段估计票价为：020站：1元；2140站：2元；40站以上：3元；题目要求设计任意两公汽站点之间线路选择问题的数学模型与算法。对于附录中的1.1 公汽线路信息.txt中的数据进行处理后，以文本文件形式导入Matlab中，找到了站点与站点之间的关系。进一步发现表明无论试图产生邻接矩阵或边权矩阵因数据太庞大而可行性极低，其运行时间长达50分钟，故考虑按题目给的路线来建立站点矩阵并对此矩阵进行处理后能够清晰有效地应用此矩阵。2.2 问题二已知相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟；地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)；地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)；公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)；地铁票价：3元（无论地铁线路间是否换乘）；其它的公汽时间信息与问题一相同。题目要求同时考虑公汽与地铁线路，设计任意两公汽站点之间线路选择问题的数学模型与算法。在此，我们考虑了总时间和总费用两个函数，讨论方法与一题类似，只是加入了地铁，分为乘坐地铁和完全不坐地铁两种。2.3 问题三已知所有站点间的步行时间，其余信息与问题二相同，题目要求建立任意两站点间路线选择问题的数学模型。问题三在问题二的基础上又增加了步行这种情况，在适当站点步行，可以节省交通费用而且不会消耗过多时间，比如某些乘客在一段分段计价线路上欲乘坐21或41个站点，则可以选择在第20站或第40站下车，步行一站即到达目的地，这样做可以节省1元。三、基本假设1、假设所有公交线路的开班、收班时间相同；2、假设公车不会因为堵车等因素延长行驶时间；3、假设各条线路不会有新的调整与变化；4、假设环线可以以任意站作为起点站和终点站，并且是双向的；5、假设除环线以外的线路，到达终点站后，所有的人都必须下车；6、假设人们对换乘车次数尽量少的偏好程度总是大于对花费时间相对短和花费金钱相对少的偏好程度；7、假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁费；8、假设文中所利用到得资料和数据都真实可靠。四、符号说明：第条包含初始站点的线路，；：第条包含目标站点的线路，；：第条中间线路，；：上的第个车站，；：上的第个站点，；：上的第个站点，；：乘客在第段线路上乘坐的站数；：乘客在一次地铁线路上乘坐的总站数；：公汽换乘公汽的次数；：地铁换乘地铁的次数；：地铁换乘公汽的次数；：公汽换乘地铁的次数。五、模型的建立与求解5.1 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。5.1.1模型的建立设为乘坐公交线路的费用函数：总时间函数： （1）总费用函数： （2）其中表示乘客在公交线路上乘坐的站数；表示公汽换乘公汽的次数。目标：找出任意给定的两站点的乘车线路，使和相对最小。5.1.2模型的求解由于人们的对换乘车次数尽量少的偏好程度总是大于对花费时间和金钱相对少的偏好程度，我们将优先考虑换乘车次数尽量少，然后再考虑花费时间相对短、花费金钱相对少，对得出的所有结果中进行筛选。换乘次数的大概思路及步骤如下：将所有包含初始站点的线路建成一个集合S，所有包含目标站点的线路建成一个集合G，。 ， ，。1、直达的线路。当时，存在、，使得，即、为同一线路。此线路既包含初始站点又包含目标站点。若，那么，此线路为所求直达线路。若，或者当时，考虑换乘一次的线路。2、换乘一次的线路。当有和相交时，存在、，有及，。使得，即、为同一站点。若，那么，从初始站点乘坐线路，行驶至站点，即在站点，换乘线路至目标站点。即若不满足，或者，当无任何和相交时，考虑换乘两次的线路。3、换乘两次的线路。记，有，且满足与、都相交时，即线路既不包含初始站点又不包含目标站点，。但是存在及，使得，存在及，使得，即、为同一站点，且、为同一站点。，。若，那么，从初始站点乘坐线路，行驶至站点，即在站点，换乘线路至站点，即在站点，换乘线路至目标站点。即若不满足，或者，当不存在满足条件的时，说明需要换乘三次才能够到达目标站点。换乘三次的线路的模型建立原理是相同的。由于几乎没有这样的情况，故我们不作考虑。通过考虑花费的时间或金钱，在得出的多条结果中进行筛选。5.1.3结果分析由于公交线路的固定性、重叠性和可选择性,使得公交乘客出行线路选择行为具有相当的复杂性。由公交乘客的路径选择特性可知,乘客总是根据个人偏好选择出行路线(或希望出行时间最少,或希望换乘次数最少,或希望出行费用最低),可称之为最短路因素。同时,由于公交网络的复杂性,使得最短路判断出现差异,而个人选择行为带有一定的随机性,所以多路径选择较为符合乘客的行为特点。另外一个方面，当乘客要进行一次换乘时，他会考虑到时间或者费用等问题，但当乘客必须二次换乘时，时间是决定乘客选择路线的唯一因素，所以在这种情况下我们只考虑途经站点最少的二次转乘路线。基于以上考虑,我们对每道小题都给出了多种乘车路线，以供乘客根据自己的需要选择。（1） S3359S1828表5-1 S3359S1828的乘车路线线路（条）初始站换乘站 (换乘站)目标站时间（分）金钱（元）1S3359S1784 S182810132S3359S1784 S182810133S3359S3515S1784S18289434S3359S0359S1784S182894353359S3515S1784S1828943评价说明：经Matlab运行程序，得出了5条优化线路。其中，1、2条换乘一次，3、4、5条换乘两次， 3、4、5条线路比1、2条线路多换乘一次，所花的金钱相同，但是节省了7分钟时间。乘客根据自己的需要进行选择。（2） S1557S0481表5-2 S1557S0481的乘车路线线路（条）初始站换乘站 (换乘站)目标站时间（分）金钱（元）1S1557S1919S2424S048111232S1557S1919S2424S048111233S1557S1919S2424S048111234S1557S1919S2424S048111235S1557S1919S2424S048111236S1557S1919S2424S048111237S1557S1919S2424S048111238S1557S1919S2424S048111239S1557S1919S2424S04811123评价说明：经Matlab运行程序，得出了9条优化线路。乘坐这9条线路所花费的时间和金钱都相同，且均需要换乘两次。不存在换乘一次的线路。乘客可以选择任意一条线路。（3） S0971S0485表5-3 S0971S0485的乘车路线线路初始站换乘站 (换乘站)目标站时间（分）金钱（元）1S0971S2184 S048512832S0971S0992 S048513133S0971S3405S2515S04859434S0971S1520S2265S04859435S0971S1520S2654S04859436S0971S1520S1729S04859437S0971S1520S3766S04859438S0971S1520S2265S04859439S0971S1520S2265S0485943评价说明：经Matlab运行程序，得出了9条优化线路。其中，1条换乘一次，39条换乘两次， 39条线路比1条线路多换乘一次，所花的金钱相同，但是节省了37分钟时间。乘客根据自己的需要进行选择。（4） S0008S0073表5-4 S0008S0073 的乘车路线线路初始站换乘站 (换乘站)目标站时间（分）金钱（元）1S0008S2083 S00738322S0008S2263 S00738323S0008S2683 S00738324S0008S0400 S00738325S0008S2559 S00738336S0008S1383S2833S00738237S0008S1691S2833S00738238S0008S3766S2833S00738239S0008S1383S2833S007382310S0008S1383S2833S0073823评价说明：经Matlab运行程序，得出了10条优化线路。其中，15条换乘一次，所花费的时间相同，但是14条比5条节省了1元钱。610条换乘两次，所花的金钱比14条多1元，只节省了1分钟时间。所以建议乘客选择14条。（5） S0148S0485表5-5 S0148S0485 的乘车路线线路初始站换乘站 (换乘站)目标站时间（分）金钱（元）1S0148S0036S2210S048510632S0148S0036S3332S048510633S0148S0036S3351S04851063评价说明：经Matlab运行程序，得出了3条优化线路。乘坐这3条线路所花费的时间和金钱都相同，且均需要换乘两次。不存在换乘一次的线路。乘客可以选择任意一条线路。（6） S0087S3676表5-6 S0087S3676的乘车路线线路（条）初始站换乘站 (换乘站)目标站时间（分）金钱（元）1S0087S3496 S36766522S0087S1893 S36767123S0087S0541S0236S36765234S0087S0541S2336S3676523评价说明：经Matlab运行程序，得出了4条优化线路。其中，1、2条换乘一次，所花费的金钱相同，但是1条比2条节省了6分钟。3、4条换乘两次，所花的金钱相同，且比1、2条多1元，但节省了时间。所以建议乘客选择1、3、4条。5.2 同时考虑公汽与地铁线路，解决问题一。5.2.1模型的建立设，分别为乘坐公交和地铁线路的费用函数： 总时间函数： （，） （3）总费用函数： （4）其中表示乘客在公交线路上乘坐的站数；表示乘客在一次地铁线路上乘坐的总站数；分别表示公汽换乘公汽，地铁换乘地铁，地铁换乘公汽，公汽换乘地铁的次数。目标：找出任意给定的两站点的乘车线路，使和相对最小。5.2.2模型的求解由于假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费，那么不妨把同一地铁站所对应的几个公汽站合并成一个站。地铁线路，。1、可以乘坐地铁的线路。（1）若初始站点和目标站点都在地铁线路或者上，那么，只乘坐地铁或者便可以直达。其中，若都在线路上，就选择经过站数最少的方向。若初始站点和目标站点分别在地铁线路和上，那么，需要进行一次地铁换乘地铁才能到达。（2）若只有初始站点或只有目标站点在地铁线路上，则需要换乘公汽才能到达目标站点。初始站点，目标站点且，。当有和地铁相交时，即存在，有，使得，。，。若，那么，从初始站点（记为） 乘坐地铁线路，行驶至站点（记为），换乘公汽线路至目标站点。，。即 （） （）其中， 时需要地铁换乘地铁。若不满足，或者当没有这样的时，说明在地铁换乘公汽后，还需要进行公汽换乘公汽。由于这样的情况几乎不存在，故不作考虑。目标站点，初始站点且，同理可得结论。（3）若初始站点和目标站点都不在地铁线路上，则先乘坐公汽，换乘地铁，再由地铁换乘公汽。地铁线路既和相交又和相交时，即地铁线路既不包含初始站点又不包含目标站点。但是存在、，有，使得，记为，使得，记为，。若，那么，从初始站点乘坐线路，行驶至站点（记为），换乘地铁线路至站点（记为），换乘线路至目标站点。即 （） （）其中， 时需要地铁换乘地铁。若不满足，或者不存在、都与地铁线路相交，说明需要在地铁线路前或后进行公汽与公汽的换乘。由于这样的情况几乎不存在，故不作考虑。2、只乘坐公汽的线路。完全排除地铁线路，与解决问题一的方法相同。5.2.3结果分析（1）S3359S1828应用Matlab编出的程序显示出没有在地铁站附近车站转站的的转站台，所以此时不坐地铁的结果完全和“问题一”中的第一小题的结果相同。因此在这种情况下，建议在这些站点乘客应当首先考虑坐公汽。具体情况请参照“问题一”的的结果。（2）S1557S0481同（1）的结论。图1 北京地铁图（3）S0971S0485通过S0971的路线同时又能够到达地铁站的线路分别为：L160上行，L263下行，L119上行，L024下行，L119下行，L013上行，分别到达地铁的D01，D02，D26；另外一方面，与终点站S0485相连并能够到达地铁站的公交线路分别是L375上，L469下行，L051上行，L417下行，L395下行，分别到达地铁站的D21，D22和D20。可以乘坐地铁：线路（条）初始站换乘站 (换乘站)目标站时间（分）金钱（元）1S0971（D26）（D21）S0485138.562S0971（D26）（D21）S0485138.563S0971（D26）（D21）S0485138.56只乘坐公汽：线路初始站换乘站 (换乘站)目标站时间（分）金钱（元）1S0971S2184 S048512832S0971S0992 S048513133S0971S3405S2515S04859434S0971S1520S2265S04859435S0971S1520S2654S04859436S0971S1520S1729S04859437S0971S1520S3766S04859438S0971S1520S2265S04859439S0971S1520S2265S0485943评价说明：经Matlab运行程序，得出了3 条乘坐地铁的优化线路。但与乘坐公汽对比，如果要坐地铁，不仅需要换乘多次，还会花费大量时间。建议乘客乘坐公汽。（4）S0008S0073同（1）的结论。（5）S0148S0485可以乘坐地铁：线路（条）初始站换乘站 (换乘站)目标站时间（分）金钱（元）1S0148S3045（D02）（D21）S048587.552S0148S3045（D02）（D21）S048587.553S0148S3045（D02）（D21）S048587.554S0148S3045（D02）（D21）S048587.55只乘坐公汽：线路初始站换乘站 (换乘站)目标站时间（分）金钱（元）1S0148S0036S2210S048510632S0148S0036S3332S048510633S0148S0036S3351S04851063评价说明：经Matlab运行程序，得出了4条乘坐地铁的优化线路。与乘坐公汽对比，节省的时间较多。乘客根据自己的需要进行选择。（6）S0087S3676抽象出T1和T2的模型，如图1所示。由于S0087和S3676这两个站点都对应地铁站，又由2.2 地铁T2线换乘公汽信息.txt，故把S0087合并到地铁站点D27，把S3676合并到地铁站点D36。又由图1所知，当乘客在S0087时，他有两种很快捷，方便的乘车路线到达S3676，即，。两条路线都只花3元钱，而第一条线路耗时25分钟，第二条只耗时20分钟。相比于“问题一”中的第六个小题，在花费均相等的前提下，建议乘客选乘地铁，因为这在很大程度上节约了时间，同时也免去了转车带来的麻烦。5.3 假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。5.3.1模型的建立设分别为乘坐公交和地铁线路的费用函数： 根据实际情况，在地铁线路上不考虑步行。我们可以在初始站点、目标站点或换乘站点的附近考虑步行，即在任意公交线路,上最多下车一次。否则，若在某个,上下车步行两次，则在上需要多购买车票一次，同时消耗的时间更多，此做法既违反常理，又不经济实惠。设在线路，上步行的站数为，相邻公汽站步行时间为，那么总时间函数：， （5）总费用函数：， （6）目标：找出任意给定的两站点的乘车线路，使和相对最小。六、模型的评价和改进6.1 模型的优点此模型简单易懂，操作简单，涵盖了所有路线的选择情况。而且，此模型的设计完全符合“乘公交，看奥运”的主题，解决了公交线路的选择问题，使公众的出行更加通畅便利。6.2 模型的缺点该模型在问题考虑上忽略了人流和车流拥挤的状况。6.3 模型的改进对于若干条从某一初始站点到目标站点的线路，我们可以设计一种带记忆功能的系统，即乘客选择某路径的次数越多，说明此路径是比较优的路径，为以后选择路径提供必要的信息。系统使用的时间越长，为乘客提供的信息越全面，越准确，系统也越智能化。这样就可以为乘客需求量最大的一条增加班次，以满足更多人的需要。在假设中提到，所有线路的开班、收班时间相同，但事实并非如此。那么可以在模型的设计中加入线路运行的时间元素，使乘客查询时只显示正在运行的线路。七、参考文献1慧光，独立光伏系统最佳倾角计算研究J,节能技术与市场。2姜启源，谢金星，叶俊，数学模型(第三版)M，北京:高等教育出版社，2003。3薛毅，数学建模基础M，北京：北京工业大学出版社，2005。4马莉，MATLAB数学实验与建模M，北京：清华大学出版社，2010。5任升录，关于线性回归模型的显著性检验，数学数学，2012年第三期，7-8,2012。附录：问题一的程序代码（直达的线路）x1=input(please input starting station:);y1=input(please input the terminal :);i1,j1=find(a=x1);i2,j2=find(a=y1);m,n=size(i1);p,q=size(i2);r=0;for i=1:m for j=1:p if i1(i,n)=i2(j,q) %找出出发站和终点站在一条线路上的 nv=find(x1=a(i1(i,n),:); nu=find(y1=a(i2(j,q),:); if nvnu r=r+1; t(r)=i1(i,n); end end endend if r=0 disp(t) else t=0 endj1j2%直达的输出说明 t是线路 j1是起点站在该线路的第几个站 j2是终点站在该线路的第几个站问题一的程序代码（换乘一次的线路）x1=input(请输入起点站:);y1=input(请输入终点站:);W=input(输入最多经过站点的个数:); i1,j1=find(a=x1); %记录行和列 i2,j2=find(a=y1); m,n=size(i1); p,q=size(i2); for i=1:m for j=1:p ro=0; if i1(i,n)=i2(j,q) mv=a(i1(i,n),:); mu=a(i2(j,q),:); mo,no=size(mv); po,qo=size(mu); for io=1:no for jo=1:qo if mv(mo,io)=mu(po,jo) ad=find(a(i1(i,n),:)=x1); %x1所在的位置 bd=find(a(i2(j,q),:)=y1); %y1所在的位置 ao=find(mv(mo,io)=a(i1(i,n),:); %转站点在x1所在列的位置 bo=find(mv(mo,io)=a(i2(j,q),:); %转站点在y1所在列的位置 if adao&bobd&(ao-ad+bd-bo)W ro=ro+1; to(ro)=mv(mo,io); tka(ro)=ao-1; tji(ro)=bo-1; end end end end if ro=0 disp(中转站点) disp(to) disp(中转站点在始发线上的位置) disp(tka) disp(中转站点在抵达线上的位置) disp(tji) vo(1)=i1(i,n);vo(2)=i2(j,q); disp(始发线和抵达线) a(vo,1) disp(起点站位置) ad-1 disp(终点站位置) bd-1 end end end end问题一的程序代码（换乘两次的