全国大学生数学建模一等奖获奖论文

1、2007高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的电子文件名： B0302

2、所属学校（请填写完整的全名）： 广西师范学院 参赛队员 (打印并签名) ：1. 钟兴智 2. 尹海军 3. 斯 婷 指导教师或指导教师组负责人 (打印并签名)： 韦程东 日期： 2007 年 9 月 24 日赛区评阅编号（由赛区组委会评阅前进行编号）：2007高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：乘公交，看奥运摘要 我们基于最小换乘次数算法，设计了公交查询系统，能够分别从时间和花费出发考虑，选择最优路径，

3、以满足查询者的各种不同需求。 问题一：采用最小换乘次数算法，求出任意两站的最小换乘次数，在次数一定的情况下，分别选取花费最少和时间最少作为优化目标，建立两种模型：最少时间模型：；最少花费模型：；利用两种模型求出6组数局的最佳路线如下（两种模型求出的最优结果是一样的）；起始站终点站乘车路线时间费用S3359S1828L436下行（S1784）L167下行1013S1557S0481L084下行（S1919）L189下行（S3186）L460下行（有2条最优路线）1063S0485S0971L013下行（S0992）L417下行1283S0008S0073L159下行（S0491）L058下行(有

4、5条最优路线)832S0148S0485L308上行（S0036）L156上行（S3351）L417下行1013S0087S3676L454上行（S3496） L209下行 652问题二：把两条地铁的任意站点的附近公交站点以相同的序号表示，因此将地铁的线路转化成公交的问题，改进问题一中的模型求出此问题的最少时间模型 + 得到6组数据的最优路线如下：起始站终点站乘车路线所需费用S3359S1828L436下行（S1784）L167下行101分3元S1557S0481L363下行（S1919）L189下行（S3186）L460下行（有两条）106分3元S0485S0971L013下行（S0992）

5、L417下行128分3元S0008S0073L159下行（S0491）L058下行（有5条）83分2元S0148S0485L308上行（S0036）L156上行（S3351）L417下行101分3元S0087S3676T2（D27D36）33分3元 问题三：考虑到会存在紧邻站点与终点站的直达线路，所以我们对问题一的最小换乘算法进行了改进。 关键词：最小换乘次数， 算法，紧邻点，数据库，路线集问题重述第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达8

6、00条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。现需解决以下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与

7、地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。模型假设1. 相邻两站公汽站距离和所需行驶时间相同。2. 公汽与地铁线路都畅通无阻，即没有堵车。3. 人们考虑换乘次数不超过两次。4. 在有直达车的情况下，人们首选直达车。5. 同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)。6. 人们选择坐地铁都是出于省时考虑，暂不考虑花费。模型建立与求解问题一1. 问题分析 人们在选择公交出行路线时考虑的因素很多，如出行耗时是否最少，线路是否最短，换乘次数是否最少，花费是否最少。资料调查显示，大多数乘客在选择公汽线路时，首先考虑的

8、是乘车是否方便，就换乘次数而言，一般不大于两次3。所以我们采用最小换乘次数算法1，求出最少换乘次数。然后在最少换乘次数一定的情况下，我们再针对个人偏好，分别选取花费最少和时间最少作为优化目标。最小换乘次数最少算法的基本思想是从起始站点（任意的），终止站点（任意的）出发，通过比较公交网络上各车站的可换乘车站，追索到的可能路径，然后比较各可能路径的时间或花费，来确定最优路线。2模型算法与求解2.1 符号说明：为经过的线路集。为经过B的线路集。为线路上的站点。其中可表示为线路上各站点的序号。为线路上的站点。其中可表示为线路上各站点的序号。为经过的线路集。为经过的线路集。2.2 算法步骤及流程图：(1

9、)输入乘车的起始站点及终止站点； (2)求出经过站点的所有线路集和经过站点的所有线路集； (3)判断是否等于，如果相等再判断是否为环行线路，如果是则为站点到站点的直达线路，如果不是环行线路但线路上结束的序号大于开始的序号则仍是直达线路；输出结果，结束运算；如果没有则进行下一步。(4)求线路上的站点以及线路上的站点； (5)判断是否存在相同站点，即是否有存在=的情况，如果有再判断相交路线是否为环行，如果是且经过终点的路线也为环行，则可一次转车；如果相交路线不是环行，但线路上结束的序号小于结束站序号，仍可一次转车，线路，即为一次转车的线路，即为转车站点。如果没有相同站点再执行下面。(6)求出经过的

10、线路集，经过的线路集； (7)判断是否等于 。如果相等再判断是否为环行线路，如果是则线路，为两次换车的线路，换车站点为和；如果不是环行线路但线路上结束的序号大于开始的序号则仍可实现二次转车。输出结果，结束运算。开始直达进入下组数据 是获得起点A和终点B获得经过A的线路集合S（K）和B的线路集合T（L）S(K)与T(L)是否有交集交集中的线路类型是否为环形用一转的方法解决线路上结束的序号是否大于开始的序号是否否得经过A的线路集合S（K）和B的线路集合T（L）是否最少换乘次数算法流程图： （图一）一次转乘算法流程图：S（K）与T（L）路线是否存在交点相交路线类型是否为环行用二转算法解决线路上结束的

11、序号是否小于结束站序号经过终点的路线是否为环行线路上结束的序号是否小于结束 站序号一转可到达进入下一组数据是否否是否否否是是 （图二）2.3模型建立：对于所求转车线路可能不止一条，我们根据最少时间或最少花费为目标函数求出个人所需最优线路。记为线路上的站点，其序号为；线路上的站点，其序号为。记, ,自起三条路线的总站数分别为；若线路为上下行或单行，则从站点到转车站点的站点数为，从到的站点数为，从转车站点到站点的站点数为。若线路为环行，当<， ，<时，站点到，到，到站点的站点数为，。当>,>时，站点到，到，到站点的站点数为，（1）最少时间模型： （1.1）s.t. , （1

12、） （2） ， （3）（2）最少花费模型： （1.2）s.t.， （1） ， （2） （3）2.4模型求解 我们将所给文本1.1公路线路信息.txt中的数据作处理，用替换的方法使得文本利于导入数据库，利用C#将文本文件的内容一次导入SQL数据库，接着利用C#编写程序（见附件1），数据库代码见附件2。利用算法实现的代码与数据库连接求得最优解。2.5模型结果及分析：最少时间和最少花费的线路结果表：起始站终点站乘车路线时间费用S3359S1828L436下行（S1784）L167下行101分3元 S1557S0481L363下行（S1919）L189下行（S3186）L460下行106分3元L084

13、下行（S1919）L189下行（S3186）L460下行106分3元S0485S0971L013下行（S0992）L417下行128分3元S0008S0073L159下行（S0491）L058下行83分2元L159下行(S3053) L474上行83分2元L355下行(S2303) L345上行83分2元L463下行（S2083）L057上行83分2元L159下行（S0491）L058下行83分2元S0148S0485L308上行（S0036）L156上行（S3351）L417下行101分3元S0087S3676L454上行（S3496） L209下行65分3元我们发现在这6组数据里面，时间最

14、少和花费最少的最佳路线是一样的。这也是符合常情的。但也存在站数和时间少但花费多的情况。这时人们就可以根据自己实际情况选择路线。2.6模型评价优点：采用最小换乘次数算法，既符合人们一般想法，又把问题及模型简单化。能够分别从时间和花费考虑建立两种模型，满足查询者的不同需求。模型结构简单，条理清晰，易于实施，对于编程来说是比较容易的缺点：采用地毯式的遍历搜索，使得程序运行的复杂度过高，运行时间长，不适合于大量数据的应用。问题二1.问题分析如果同时考虑汽车和地铁换乘，虽然花费可能会增加，但很有可能减少路径时间，这对赶时间的人来说是十分必要的。所以此问只考虑最小换乘次数的最少时间模型。我们依然规定最小换

15、乘次数为2次。我们建立了两个模型。2.模型一的算法与求解2.1符号说明为开始站点对应地铁站点的车次，为终止站点对应站点的车次为地铁站点对应的公汽站点的集合，为地铁站点对应的公汽站点的集合2.2 算法步骤（1）输入乘车的起始站点及终止站点（2）分别判断，是否属于，若都不属于则回到问题一的算法；若,则进行第（3），（4）步；若，则进行第（5）步；若，则进行第（6）步。（3）判断是否等于，若则可以通过转到。若，则进行下一步。（4）若，则可从乘T1直达；若，则先从乘T1在D12下车，然后坐T2到达；若，则先从乘T1在D18下车，然后坐T2到达；若，则先从乘T2在D18下车，然后坐T1到达判断相交路线是

16、否为环行，如果是且经过终点的路线也为环行，则可一次转车；如果相交路线不是环行，但线路上结束的序号小于结束站序号，仍可一次转车，；若，则先从乘T2在D12下车，然后坐T1到达；若，则从可乘T2直达。（5），判断能否找到和中某公汽站点的直达线路。若没有则退出运算；若有则根据第（3），（4）步求出和的地铁转乘路线。这样就可求出到的公汽地铁的转乘路线。（6），类似第（5）步求出到的地铁公汽的转乘路线。2.3 模型建立当到的路线为通过地铁站点直接转到时，所需时间为公汽与地铁站点的步行时间，即=8当从乘T1直达时，所需时间为当从乘T1在D12下车，然后乘T2到达时，所需时间为当从乘T1在D18下车，然后乘

17、T2到达时，所需时间为当从乘T2在D18下车，然后坐T1到达时，所需时间为当从乘T2在D12下车，然后坐T1到达时，所需时间为当从可乘T2直达时，所需时间为当为公汽地铁或地铁公汽路线时，所需时间为当不能通过地铁转乘时，所需时间为问题一的最短时间综上所述，模型一可归纳如下： （1.3）s.t. =8， ， ， ，为环形直达所需时间， ，为公汽与地铁换乘所需时间 ，或，为问题一中情况所需时间 ， 2.4 模型评价此模型算法复杂，且求解各段时间较为困难，很难编程解出结果。所以我们考虑了第二种模型3.模型二的建立与求解3.1模型建立把两条地铁的任意站点的附近公交站点以相同的序号表示，因此将地铁的线路转

18、化成公交的问题，然后利用求出的公交站点求出地铁的站台号。这样可以回归到问题的模型求解。记： 为原公汽线路上的站点；为由地铁改编成的公汽线路的站点；为原公汽线路上的站点；为由地铁改编成的公汽线路 上的站点；，乘坐改编成的公汽线路时的时间为地铁与公汽换乘时间为公汽与地铁换乘时间为综上所述最少时间模型： + （1.4）s.t. , （1） （2） ， （3） （4） （5）3.2模型求解把地铁线路转换成公交线路，进行问题中的运算。运算结果如下表：起始站终点站乘车路线时间费用S3359S1828L436下行（S1784）L167下行101分3元S1557S0481L363下行（S1919）L189下行

19、（S3186）L460下行106分3元S1557S0481L084下行（S1919）L189下行（S3186）L460下行106分3元S0485S0971L013下行（S0992）L417下行128分3元S0008S0073L159下行（S0491）L058下行83分2元L159下行(S3053) L474上行83分2元L355下行(S2303) L345上行83分2元L463下行（S2083）L057上行83分2元L159下行（S0491）L058下行83分2元S0148S0485L308上行（S0036）L156上行（S3351）L417下行101分3元S0087S3676T2（D27D3

20、6）33分3元3.3模型评价：此模型引用的是问题一中的模型，对时间最短模型进行改进。只是增加了条件，程序运行复杂度更高。问题三1.问题分析考虑站点之间步行时间后，就有可能存在与终止站点直达线路的紧邻站点，只要先步行到紧邻站点，再由紧邻站点乘直达车到终止站点，就有可能减少时间。所以要对问题一的算法进行改进2。2.改进的算法2.1符号说明：为经过的线路集。为经过B的线路集。为线路上的站点。其中可表示为线路上各站点的序号。为线路上的站点。其中可表示为线路上各站点的序号。为经过或其附近的线路集。为经过或其附近的线路集。表示站点与站点之间步行的时间，T表示乘客在换车时步行时间的最大心理承受值。对于站点与站点之间的紧邻关系，可以用一个不等式表示：2.2算法步骤：(1)输入乘车的起始站点及终止站点； (2)求