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

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

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

3、小换乘次数，在次数一 定的情况下，分别选取花费最少和时间最少作为优化目标，建立两种模型：最少 .33一 .时间模型：min f（A,B） 3 （1 xR）5x ；取少化费模型：i 1i 13,.min g（A,B）（xi' （1 xijyij ；利用两种模型求出6组数局的最彳土路线如下（两i种模型求出的最优结果是一样的）；起始站一终点站乘车路线时间费用S335A S1828L436 下行(S1784) 一 L167 下行1013S1557 S0481L084 下行（S1919） -L189 下行（S3186）一L460下行（有2条最优路线）1063S048A S0971L013 下行(

4、S0992) 一 L417 下行1283S0008 S0073L159 下行（S0491） 一 L058 下行（有5条最优路线）832S0148f S0485L308 上行(S0036) 一 L156 上行(S3351)一 L417下行1013S0087 S3676L454 上行(S3496) 一 L209 下行652问题二：把两条地铁的任意站点的附近公交站点以相同的序号表示，因此将地铁的线路转化成公交的问题，改进问题一中的模型求出此问题的最少时间模型3min f(A, B)(3i 13(Xi ni (1i 13Xi)qi)5xJ)i 133(1 yi)(2.5 ( (Xii 1i 1'

5、;n i(1 Xi)qi)3334Xi )7(1 z i) yi + 6Ziyi 1i 1i 1得到6组数据的最优路线如下：起始站一终点站乘车路线所需费用S3359- S1828L436 下行(S1784) 一 L167 下行101分3元S1557 S0481L363 下行（S1919） -L189 下行（S3186）一 L460下仃（后两条）106分3元S048A S0971L013 下行(S0992) 一 L417 下行128分3元S0008 S0073L159 下行（S0491） 一 L058 下行（有5条）83分2元S0148f S0485L308 上行(S0036) 一 L156 上

6、行(S3351)一 L417下行101分3元S0087 S3676T2 (D27-D36)33分3元问题三：考虑到会存在紧邻站点与终点站的直达线路， 所以我们对问题一的 最小换乘算法进行了改进。关键词：最小换乘次数， 算法，紧邻点，数据库，路线集问题重述第 29 届奥运会明年8 月将在北京举行，届时有大量观众到现场观看奥运比赛， 其中大部分人将会乘坐公共交通工具 (简称公交， 包括公汽、 地铁等) 出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800 条以上，使得公众的出行更加通畅、 便利， 但同时也面临多条线路的选择问题。 针对市场需求，某公司准备研制开发一个解决公交线路选

7、择问题的自主查询计算机系统。其核心是线路选择的模型与算法， 应该从实际情况出发考虑， 满足查询者的各种不同需求。现需解决以下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站-终到站 之间的最佳路线。(1)、S335gS1828(2)、S1557f S0481(3)、S0971-S0485(4)、S000A S0073(5)、S0148-S0485(6)、S0087f S 36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。模型假

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

9、然后在最少换乘次数一定的情况下， 我们再针对个人偏好， 分别选取花费最少和时间最少作为优化目标。最小换乘次数最少算法的基本思想是从起始站点 A (任意的) ，终止站点 B(任意的) 出发， 通过比较公交网络上各车站的可换乘车站， 追索 A 到 B 的可能 路径，然后比较各可能路径的时间或花费，来确定最优路线。2 .模型算法与求解2.1 符号说明：S(K)| K 1,2, ,m为经过A的线路集T(L) L 1,2, ,n为经过B的线路集。E(K,U)(U 1,2, r)为线路S(K)上的站点。其中U可表示为线路S(K)上各站点 的序号。F(L,V)(V 1,2, Pj)为线路T(L)上的站点。其

10、中V可表示为线路T(L)上各站点的)丁万。R(M)(M 1,2, ,g)为经过E(K,U)的线路集。Y(N)(N 1,2, ,z)为经过F(L,V)的线路集。2.2 算法步骤及流程图：(1)输入乘车的起始站点A及终止站点B;(2)求出经过站点A的所有线路集S(K)和经过站点B的所有线路集T(L);(3)判断S(K)是否等于T(L),如果相等再判断S(K)是否为环行线路，如果是则S(K) 为站点A到站点B的直达线路，如果不是环行线路但线路上结束的序号大于开始的序号 则仍是直达线路；输出结果，结束运算；如果没有则进行下一步。(4)求线路S(K)上的站点E(K,U )以及线路T(L)上的站点F(L,

11、V);(5)判断是否存在相同站点，即是否有存在 E(K,U ) = F(L,V)的情况，如果有再判断 相交路线是否为环行，如果是且经过终点的路线也为环行，则可一次转车；如果相交路 线不是环行，但线路上结束的序号小于结束站序号，仍可一次转车，线路S(K),T(L)即为一次转车的线路，E(K,U)即为转车站点。如果没有相同站点再执行下面。(6)求出经过E(K,U)的线路集R(M),经过F(L,V)的线路集Y(N);(7)判断R(M )是否等于Y(N)。如果相等再判断R(M)是否为环行线路，如果是则线路S(K), R(M), T(L)为两次换车的线路，换车站点为 E(K,U)和F(L,V);如果不

12、是环行线路但线路上结束的序号大于开始的序号则仍可实现二次转车。输出结果，结束 运算。15最少换乘次数算法流程图:是直达进入下组数据（图一）一次转乘算法流程图:(图二)2.3 模型建立：对于所求转车线路可能不止一条，我们根据最少时间或最少花费为目标函数求出个 人所需最优线路。记E(K,Ua)为线路S(K)上的A站点，其序号为Ua ； F(L,Vb)线路T(L)上的B站点,其序号为Vb o记 ni U U a , n2 V U ,我 Vb V ,自A起三条路线的总站数分别为Pi, P2, P31 U,UaPi； 1 u,v P2I V,VbP3若线路为上下行或单行，则从 A站点E(K,Ua)到转车

13、站点E(K,U)的站点数为 ni| U Ua ,从E(K,U)到F(L,V)的站点数为也 V U ,从转车站点F(L,V)到B站 点的站点数为n3 VB V。若线路为环行，当 Ua<U , U V , V<Vb时，A站点到E(K,U), E(K,U)到F(L,V) , F(L,V)到B站点的站点数为】U U a ,门2 V U , % Vb V。当Ua>U,V>Vb 时，A 站点到 E(K,U), E(K,U)到 F(L,V),为 Pini, P2n2, P303(1)最少时间模型:33min f (A, B) 3 ( 由 q (1 Xi)q。)5xiF(L,V)到B站

14、点的站点数(1.1)s.t. Xi1，0,线路为上下行或单行 线路为环行1,2,3)(1)31Xi3i 1(2)qi (n R)mod(Pi), 0 qi Pi ( i(2)最少花费模型:3ming(A, B)(为(1 xjyi)11,2,3)(3)(1.2)s.t.x'1,0,线路为单一票制线路为分段计价1,2,3)(Di 1i 1(2)(3)1,1ni20,yj 2,21 Q 40, (j 1,2,3)3,41 1nj31 Xi 3i 12.4 模型求解我们将所给文本1.1公路线路信息.txt中的数据作处理，用替换的方法使得文本利 于导入数据库，利用C#将文本文件的内容一次导入SQ

15、L数据库，接着利用C#8写程序 (见附件1),数据库代码见附件2。利用算法实现的代码与数据库连接求得最优解。2.5 模型结果及分析:最少时间和最少花费的线路结果表:起始站一终点站乘车路线时间费用S335g S1828L436 下行(S1784) 一 L167 下行101分3元S155片 S0481L363 下行(S1919) 一 L189 下行(S3186) 一 L460下行106分3元L084 下行(S1919) 一 L189 下行(S3186) 一 L460下行106分3元S048A S0971L013 下行(S0992) 一 L417 下行128分3元S000A S0073L159 下行

16、(S0491) 一 L058 下行83分2元L159 下行(S3053) 一 L474 上行83分2元L355 下行(S2303) 一 L345 上行83分2元L463 下行(S2083) 一 L057 上行83分2元L159 下行(S0491) 一 L058 下行83分2元S014A S0485L308 上行(S0036) 一 L156 上行(S3351) 一 L417下行101分3元S008片 S3676L454 上行(S3496) 一 L209 下行65分3元我们发现在这6组数据里面，时间最少和花费最少的最佳路线是一样的。这也是符 合常情的。但也存在站数和时间少但花费多的情况。这时人们就

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

18、i 1,2,39）为开始站点A对应地铁站点的车次，Dj（j 1,2,39）为终止站点B 对应站点的车次Mi为地铁站点Di对应的公汽站点的集合，M j为地铁站点Dj对应的公汽站点的集 合2.2 算法步骤 1） 1）输入乘车的起始站点A 及终止站点B 2） 分别判断A, B是否属于MMj,若都不属于则回到问题一的算法；若A Mi,B Mj则进行第（3）, （4）步；若A MB M j则进行第（5）步；若A MB M j 则进行第（6）步。 3） 判断i是否等于j ,若i j则A可以通过Di转到B。若i j ,则进行下一步。 4） 若 1 i 23,1 j 23,则可从 Di乘 T1 直达 Dj ；

19、若1 i 23,27j32,则先从Di乘T1在D12下车，然后坐T2到达Dj ；若1 i 23,33j 39或24j26,则先从Di乘T1在D18下车，然后坐T2到达Dj ；若27 i 32,1 j 23 ,则先从Di 乘 T2 在 D18 下车，然后坐T1 到达判断相交路线是否为环行，如果是且经过终点的路线也为环行，则可一次转车；如果相交路线不是环行，但线路上结束的序号小于结束站序号，仍可一次转车， Dj；若33 i 39或24 i 32, 1j23,则先从Dj乘T2在D12下车，然后坐T1到达Dj；若24 i 39或i 12,18, 24 j39或者j 12.18,则从 D i 可乘 T2

20、 直达 D j 。 5） A MB Mj,判断能否找到A和Mi中某公汽站点A'的直达线路。若没 有则退出运算；若有则根据第（ 3） ， （ 4）步求出A' 和 B 的地铁转乘路线。这样就可求出A 到 B 的公汽地铁的转乘路线。 6） 6） A M i ， B M j ，类似第（5）步求出A 到 B 的地铁公汽的转乘路线。2.3 模型建立当A到B的路线为通过地铁站点Di直接转到时，所需时间为公汽与地铁站点的步行时间，即t4 4 =8当从Di乘T1直达Dj时，所需时间为t28 (j i)2.5Di乘T1D12下车，然后乘T2Dj所需t3(18 i2.5Di乘T1D18下车，然后乘T

21、2Dj所需t4(18 i(j1733)mod(17)Di乘T2D18下车，然后坐T1Dj所需t5(33 i) 18 j) 2.5Di乘T2在D12下车，然后坐T1Dj所需t6(i 17 33)mod(17)12 j)2.5当从Di可乘T2直达Dj时，所需时间为t7当为公汽一一地铁或地铁一一公汽路线时，所需时间为t8当不能通过地铁转乘时，所需时间为问题一的最短时间t9综上所述，模型一可归纳如下:minf(A,B)min(t1,t2，t9)(1.3)s.t.t1 =8，t2(j i)2.51 i 2323t4t5t6t34 (1832) 2.523, 2732(18 i (j1733)mod(17

22、)3339 或 24j 26(33 i) 18 j) 2.5, 27 i(i 17 33)mod(17) 12 j)t7为环形直达所需时间,322.524 i 39 或 i33 i12,18 ,2339或 24 i 3224 j 39或者j12.1823t8,为公汽与地铁换乘所需时间A Mi, B Mj 或 A Mi, B Mjt9为问题一中情况所需时间A Mi, B Mj2.4 模型评价此模型算法复杂，且求解各段时间较为困难，很难编程解出结果。所以我们考虑了 第二种模型3 .模型二的建立与求解3.1 模型建立把两条地铁的任意站点的附近公交站点以相同的序号表示，因此将地铁的线路转化成公交的问题

23、，然后利用求出的公交站点求出地铁的站台号。这样可以回归到问题的模 型求解。记：E(K,U)(U 1,2, pj为原公汽线路S(K)上的站点；E(K,U)(U 1,2, pj为由地铁改编成的公汽线路S(K)的站点；F(L,V)(V 1,2, Pj)为原公汽线路T(L)上的站点；F(L,V)(V 1,2, p j)为由地铁改编成的公汽线路T(L)上的站点；n1 U Ua, % V U , % Vb Vn U U a, n2 V U , % Vb V1,乘坐原公汽线路yi 0 乘坐改编成的公汽线路33乘坐改编成的公汽线路时的时间为2.5 (xi ni (1 xi)qi)4xii 1i 13地铁与公汽

24、换乘时间为7yii 13公汽与地铁换乘时间为6yii 11,公汽地铁换乘z；0地铁-公汽换乘综上所述最少时间模型:min f(A,B)(yi(3i 1(Xi nii 1(1Xi )qi)5Xi)13(1i 13yj(2.5 (Xi(1Xi)qi)34为)i 137(1i 13Zi)yi+ 6ZiYi(1.4)s.t. xi1,0,线路为上下行或单行 线路为环行1,2,3)(DqiVZi3Xi1(2)(ni1,01,0Pi)mod(Pi), 0 qiPi ( i1,2,3)(3)乘坐原公汽线路乘坐改编成的公汽线路公汽地铁换乘地铁-公汽换乘(4)(5)3.2模型求解把地铁线路转换成公交线路，进行问

25、题中的运算。运算结果如下表:起始站一终点站乘车路线时间费用S335g S1828L436 下行(S1784) 一 L167 下行101分3元S155片 S0481L363 下行(S1919) - L189 下行(S3186)一 L460下行106分3元S155片 S0481L084 下行(S1919) - L189 下行(S3186)一 L460下行106分3元S048A S0971L013 下行(S0992) 一 L417 下行128分3元S000A S0073L159 下行(S0491) 一 L058 下行83分2元L159 下行(S3053) 一 L474 上行83分2元L355 下行(

26、S2303) 一 L345 上行83分2元L463 下行(S2083) 一 L057 上行83分2元L159 下行(S0491) 一 L058 下行83分2元S014A S0485L308 上行(S0036) 一 L156 上行(S3351)一 L417下行101分3元S008片 S3676T2 (D27-D36)33分3元3.3模型评价：此模型引用的是问题一中的模型，对时间最短模型进行改进。只是增加了条件，程 序运行复杂度更高。问题三1 .问题分析考虑站点之间步行时间后，就有可能存在与终止站点直达线路的紧邻站点，只要先 步行到紧邻站点，再由紧邻站点乘直达车到终止站点，就有可能减少时间。所以要

27、对问 题一的算法进行改进202 .改进的算法2.1 符号说明：S(K) K 1,2, ,m为经过A的线路集。T(L)| L 1,2, ,n为经过B的线路集。E(K,U)(U 1,2, r)为线路S(K)上的站点。其中U可表示为线路S(K)上各站点 的序号。F(L,V)(V 1,2, Pj)为线路T(L)上的站点。其中V可表示为线路T(L)上各站点的)丁万。R(M)(M 1,2, ,g)为经过E(K,U)或其附近的线路集。Y(N)(N 1,2, ,z)为经过F(L,V)或其附近的线路集。t(m,n)表示站点m与站点n之间步行的时间，T表示乘客在换车时步行时间的最大心理承受值。对于站点m与站点n之间的紧邻关系，可以用一个不等式表示：t(m,n) T2.2 算法步骤：(1)输入乘车的起始站点A及