2007数模竞赛B题,城市公交线路选择优化模型你要的

承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：重庆大学参赛队员(打印并签名) ：1. 熊国刚2. 王杰3. 黎明指导教师或指导教师组负责人(打印并签名)：龚劬日期： 2007年 9 月 21 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：乘公交，看奥运【摘要】本文要解决的问题是以即将举行的08年北京奥运会为背景而提出的。

人们为了能现场观看奥运会，必然会面对出行方式与路线选择的问题。

因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。

鉴于公交系统网络的复杂性，我们没有采用常规的Dijkstra算法，而采用了高效的广度优先算法。

其基本思想是从经过起（始）点的路线出发，搜寻出转乘次数不超过两次的可行路线，然后对可行解进行进一步处理。

为满足不同查询者要求，我们对三个问题都分别建立了以时间、转乘次数、费用最小为目标的优化模型。

针对问题一（只考虑公汽系统），我们建立了模型一并通过VC++编程得到了任意两个站点间的多种最优路线，并得出所求站点间最优路线的最优值，如下进里又建立了图论模型。

本文的主要特点在于，所用算法的效率十分显著。

公交网络中的线路选择问题陈钢浒（计算机科学与技术）范传林（计算机科学与技术）戈卯卯（物流管理）全国二等奖摘要近年来，城市的公交系统有了很大发展，使得公众的出行更加通畅、便利。

本文分析了公交网络的特点，指出道路模型不适合公交网络模型。

通过对公交乘客出行心理分析，得到乘客的需求因素主要有三类：换乘次数、出行耗时、出行费用。

对问题一，我们建立了网络流模型，并据此模型构造一个类似邻接矩阵的0-1稀疏矩阵。

利用该矩阵的代数运算就可以方便地得到两给定站点换乘次数最小的线路。

为了综合考虑换乘次数最少与总时间最少，我们根据图论的最短路问题建立基于换乘次数最短单目标0-1整数规划模型，并提出一种以换乘次数最少为第一目标、时间最短为第二目标的最优路径算法。

该算法在求出两个站点之间最少换乘次数的所有可能路线的同时，还给出了其中总行驶时间最少的换乘路线。

对于题中所给的六对公交站点间的交通问题，得到一次换乘可达的线路为：(1)S3359→L436→S1784→L217→S1828 ；(3)S0971→L013→S0992→L417→S0485；(4)S0008→L159→S3614→L058→S0073 ；(6)S0087→L454→S3496→L209→S3676；两次换乘可达的线路为：(2)S1557→L084→S3389→L454→S1427→L447→S0481 ；(5)S0148→L308→S0036→L156→S2210→L417→S0485。

在问题二中同时考虑公汽与地铁线路。

将地铁站点与其临近得公交站点近似得看作一个整体站点可以得到一个增广的网络模型。

于是完全可以仿照问题1的算法来解决问题2。

基于换乘次数最小和时间最短为目标，选择路线如下：(1) S3359→L436→S1784→L217→S1828；(2)S1557→L084→S1919→T1→S3068→L072→S0481；(3)S0971→L119→S0567→T1→S0464→L469→S0485；(4) S0008→L159→S3614→L058→S0073；(5)S0148→L308→S0302→T1→S2512→L051→S0485；(6)S0087→T2→S3676。

2023年全国大学生数学建模竞赛题目B：题目背景在综合交通运输系统中，公共交通是一个重要的组成部分。

为了提高城市的交通效率和减少交通拥堵，许多城市采用了公共交通优先的策略。

在线调度算法是实现公共交通优先的一种重要方法。

题目描述某城市的公共交通系统包含多条公交线路和多个公交车站。

现在，你被要求设计一个在线调度算法来优化城市的公共交通系统并减少等待时间。

具体来说，给定每一条公交线路的发车时间间隔和通过每个车站所需的时间，你需要设计一个算法，使得乘坐公交车的乘客的等待时间最小。

你需要完成以下任务：1.根据给定的公交线路信息，计算每个车站的累计等待时间，即从第一趟公交车到达该车站到当前时间的总等待时间。

2.根据计算得到的累计等待时间，为每个车站分配一个优先级，并找到最高优先级的车站。

3.制定一个在线调度算法，在最高优先级车站的公交车上按照车站的优先级顺序依次上下乘客。

4.分析并讨论你设计的在线调度算法的优点和缺点，并提出改进的意见。

请使用Markdown文本描述你的算法设计，包括算法的步骤、算法的时间复杂度和空间复杂度，并给出算法的改进方向。

算法设计步骤一：计算累计等待时间1.初始化各个车站的累计等待时间为02.对每一趟公交车，从第一个车站开始，计算当前车站的累计等待时间，累计等待时间等于前一个车站的累计等待时间加上通过当前车站所需的时间。

步骤二：分配优先级1.根据计算得到的累计等待时间，为每个车站计算优先级，优先级等于累计等待时间的倒数。

步骤三：找到最高优先级车站1.遍历所有车站，找到优先级最高的车站。

步骤四：在线调度算法1.根据最高优先级车站的优先级顺序，依次上下乘客。

时间复杂度和空间复杂度•步骤一的时间复杂度为O(n)，其中n为车站的数量。

•步骤二的时间复杂度为O(n)，其中n为车站的数量。

•步骤三的时间复杂度为O(n)，其中n为车站的数量。

•步骤四的时间复杂度为O(n)，其中n为车站的数量。

•算法的空间复杂度为O(n)，其中n为车站的数量。

第38卷第14期2008年7月数学的实践与认识M A TH EM A TI CS I N PRA CT I CE AND TH EO R YV o l 138　N o 114　July,2008　公交转车的最短时间模型及求解叶　军,　杨振华(南京邮电大学数理学院,江苏南京　210003)摘要:　针对2007年全国大学生数学建模竞赛B 题——“乘公交,看奥运”中的关于公交线路的选择问题,建立了最短时间的数学模型,并给出了该数学模型的精确求解.关键词:　数学模型;公交线路选择;最短时间1　问题分析收稿日期:2008204201 2007年全国大学生数学建模竞赛的B 题是一道公交线路选择问题,它是一个多目标规划问题,要分别在换乘次数最少、费用最省、时间最短等目标下分别求解问题[1].在换乘次数和费用两个目标下较容易求出最优解.在时间最少这一目标下,较难求出最优解.在给定起点与终点的情形下,一般的方法是分别在给出转车次数为0,1,2等情形下分别给出其最短乘车时间,然后进行比较,从而求得最短时间.这种思路可以帮助我们求得最短时间,但是还有两个难点:一是由于计算复杂性,当转车次数增加时,程序运行时间较长;二是要说明最优必须遍历任意乘车次数,这显然无法实现.我们必须在理论上解决这一困难.2　仅考虑公共汽车线路时的最短时间模型及求解2.1　数学模型设N =3957表示问题中的公汽站点数,A 0=(a (i ,j ,0))N ×N 是直达最小站数矩阵,当存在公共汽车从站点S i 直达站点S j 时,a (i ,j ,0)表示从S i 直达S j 的最小站数.否则该元素取为+∞.令A m =(a (i ,j ,m ))N ×N 是m 次转乘最小站数矩阵,其元素a (i ,j ,m )表示m 次转车情形下,从S i 到S j 的最小站数.显然a (i ,j ,m )=m in{a (i ,k ,0)+a (k ,j ,m -1) 1Φk ΦN ,k ≠i ,k ≠j }(1) 转车次数为m 时,从S i 到S j 的总时间为t S (i ,j ,m )=5m +3a (i ,j ,m ),我们得到仅考虑公共汽车线路时的最短时间模型.模型1m in 0Φm Φ∞t S (i ,j ,m )=5m +3a (i ,j ,m )2.2　模型求解要对转车次数m 进行全遍历是不可能的,我们给出函数t S (i ,j ,m )的一个下界.设n S (i ,j )=m in 0Φm Φ∞a (i ,j ,m )表示公共汽车从S i 到S j 的最小乘车站数(可以转车任意次).将公汽站点设为有向图中的结点.若S i 乘公汽1站可以到达S j ,我们就设一条有向边从结点i 指向结点j .对于每一条有向边,指定其权为1,显然求n S (i ,j )就转化为有向图中结点i 到结点j 的最短路径问题.对任意给定的i ,j ,我们可以采用D ijk stra 算法求得n S (i ,j ).下面定理显然成立.定理1　t S (i ,j ,m )Ε5m +3n S (i ,j )对于给定的站点S i ,S j ,根据定理1,我们可以给出求解最短时间模型的方法:Step 1　利用D ijk stra 算法求出n S (i ,j ),令m =0;Step 2　根据(1)式求出a (i ,j ,m );令t S (i ,j ,m )=5m +3a (i ,j ,m )Step 3　若T S (i ,j ,m )=m in 0Φk Φmt S (i ,j ,k )Φ5(m +1)+3n S (i ,j ),则T S (i ,j ,m )即为最短乘车时间;否则令m ∶=m +1,转Step 2.注　1)若T S (i ,j ,m )Φ5(m +1)+3n S (i ,j ),表明转车次数大于m 时,总时间已经不小于转车次数不大于m 时的总时间,显然T S (i ,j ,m )即为最短乘车时间;2)在编程计算时,可定义一矩阵B ,它共有N 行,第i 行记录的是站点S i 能够直达的站点,即使得a (i ,j ,0)<∞的j 的集合.从而在计算a (i ,j ,m )时不必从1到N 进行循环.对于原问题中的第一对站点,我们给出求解过程.i =3359,j =1828,n S (i ,j )=13.表1　站点S 3359至站点S 1828的最小乘车时间求解过程m 01234ts (i ,j ,m )∞101646971T s (i ,j ,m )∞1016464645(m +1)+3ns (i ,j )4449545964根据表1得出,对于第一对站点,最短乘车时间为64分,需转2次车.对于原问题的6对站点,我们给出结果见表2.表2　6对站点最小乘车时间求解过程点对ts (i ,j ,m )123456m 3ns (i ,j )5(m 3+1)+3ns (i ,j )T 333592182810164369714136464155720481∞106993101103425100990971204851281033105104106427106103000820073836763593644136459014820485∞1061023104106955251051020087236766546351563105046注　1)m 3=m in{m T S (i ,j ,m )Φ5(m +1)+3n S (i ,j )},即为最小转乘次数;T3表示最短乘车时间;2)m =0时,对6个点对均有t S (i ,j ,0)=∞.72214期叶　军,等:公交转车的最短时间模型及求解3　综合考虑公共汽车和地铁线路时的最短时间模型及求解3.1　数学模型综合考虑公汽和地铁时,我们首先研究这样一个问题:在考虑时间最少时,线路中是否存在先乘地铁,再转公汽,再乘地铁这样的乘车方案?定理2　考察下面两种方案(A )从地铁站D k 乘地铁到地铁站D k 1然后由公汽站S s 1乘到公汽站S s 2,再转地铁站D l 1,乘地铁到地铁站D l ;(B )直接乘地铁由地铁站D k 到D l .则方案(B )的总时间T 2不大于方案(A )的总时间T 1.证明　我们结合计算机编程的结果给出证明.我们只要证明方案(B )的时间T 2小于方案(A )的时间T 1即可.设t DB (i ,j )表示乘地铁由地铁站D i 到地铁站D j 的最短时间,n SA (i ,j )表示可以由地铁站D i 转乘的公汽站乘公汽到可以由地铁站D j 转乘的公汽站的最小公汽站数.显然T 1Εt DB (k ,k 1)+3n SA (k 1,l 1)+t DB (l 1,l )+13,其中13表示地铁转公汽的时间与公汽转地铁的时间之和.若3n SA (k 1,l 1)+13-t DB (k 1,l 1)Ε0,则T 1-T 2Εt DB (k ,k 1)+3n SA (k 1,l 1)+t DB (l 1,l )+13-t DB (k ,l )Εt DB (k ,k 1)+t DB (k 1,l 1)+t DB (l 1,l )-t DB (k ,l )Ε0. 我们通过计算机程序(对k 1,l 1从1到39进行遍历搜索)求得只有4组(k 1,l 1)使得3n SA (k 1,l 1)+13-t DB (k 1,l 1)<0,分别为(13,30),(16,30),(30,15),(30,16).对这4组(k 1,l 1)均有n SA (k 1,l 1)=1.对这4组(k 1,l 1),分别编程求出t DB (k ,k 1)+t DB (l 1,l )+16-t DB (k ,l )的最小值(对k ,l 从1到39进行遍历搜索,且k ,k 1,l 1,l 两两不相等).可以得到这4个最小值都为2.于是T 1-T 2Εt DB (k ,k 1)+3n SA (k 1,l 1)+t DB (l 1,l )+13-t DB (k ,l )Εt DB (k ,k 1)+t DB (l 1,l )+16-t DB (k ,l )Ε2.证毕.根据定理2,对于起点和终点都不能由地铁站直接转乘的两个公汽站,只需考察下面的乘车方案:乘p 次(转p -1次)公汽,再乘地铁,最后乘q 次(转q -1次)公汽到达终点的方案,下面将这样的方案记为pD q .求任意公汽站点S i 到公汽站点S j 在pD q 方案下的最短时间,即对任意的p ,q ,以及任意的地铁站D k ,D l ,求出起点乘p 次公汽到可以直接转乘地铁站D k 的公汽站的最短时间,加上D k 到D l 的最短时间,再加上可以由地铁站D l 直接转乘的公汽站乘公汽q 次到达终点公汽站的最短时间.故S i →D k →D l →S j 在pD q 方案下所需的总时间为:t SD S (i ,j ,p ,q ,k ,l )=3N 1(i ,k ,p -1)+3N 2(l ,j ,q -1)+5(p +q -2)+13+2.5n D (k ,l )=3N 1(i ,k ,p -1)+3N 2(l ,j ,q -1)+2.5n D (k ,l )+5(p +q )+3(2)其中N 1(i ,k ,p -1)表示起点公汽站S i 乘p 次公汽到可以直接转乘地铁站D k 的公汽站的最小站数,N 2(l ,j ,q -1)表示由地铁站D l 直接转乘的公汽站乘公汽q 次到达终点公汽站S j822数　学　的　实　践　与　认　识38卷的最小站数.n D (k ,l )表示地铁站D k 到地铁D l 时所经过的最小站数,13表示公汽转地铁、地铁转公汽转乘所花费的时间之和.对于站点S i ,S j ,若已知p ,q ,那么N 1(i ,k ,p -1),N 2(l ,j ,q -1)仍然是两个公汽站点间的计算问题,可以借助于仅乘公汽方案的工作来进行计算.比如计算N 1(i ,k ,p -1)时首先找与地铁站D k 可以直接转乘的公汽站,然后利用(1)式计算公交站S i 乘p 次公汽分别到这些站点的最小站数,进一步比较得出最终的最小站数.类似可以计算N 2(l ,j ,q -1).若已知k ,l ,由于只有两条地铁线路,n D (k ,l )是容易计算的.下面是公汽转地铁再转公汽的最短时间模型.模型2m in{t SD S (i ,j ,p ,q ,k ,l ) 1Φp ,q <+∞,1Φk ,l Φ39,k ≠l } 注:要求得综合考虑公共汽车和地铁线路时的最短时间,只需比较单纯乘公汽的最短时间和上述最短时间就可以得到.3.2　模型求解在求解模型2时,对于k ,l 的遍历计算量并不是很大,主要困难在于p ,q 的遍历问题.我们也给出函数t SD S (i ,j ,p ,q ,k ,l )的一个下界.设n SD S (i ,j )表示从S i 乘车(公汽或地铁,可以转车任意次)到S j 的最小乘车站数.我们可以用D ijk stra 算法求出n SD S (i ,j ).定理3　t SD S (i ,j ,p ,q ,k ,l )ΕA (p +q ,i ,j ),其中A (x ,i ,j )=5.5x +2.5n SD S (i ,j )+3.(3) 证明　记M =N 1(i ,k ,p -1)+N 2(l ,j ,q -1)为乘车方案中乘公汽的站数,显然M Εp +q .由于总的最小站数为n SD S (i ,j ),显然有M +n D (k ,l )Εn SD S (i ,j ).于是t SD S (i ,j ,p ,q ,k ,l )=3M +2.5n D (k ,l )+5(p +q )+3Ε3M +2.5(n SD S (i ,j )-M )+5(p +q )+3=0.5M +2.5n SD S (i ,j )+5(p +q )+3Ε5.5(p +q )+2.5n SD S (i ,j )+3证毕.对于给定的站点S i ,S j ,根据定理3,我们可以给出求解综合考虑公共汽车和地铁线路时的最短时间模型的方法:Step 1　利用D ijk stra 算法求出nSD S (i ,j );令h =2;Step 2　令p 从1开始到h -1结束;q =h -p ;利用(2)、(3)式计算tSD S (i ,j ,p ,q ,k ,l )和A (p +q ,i ,j );对k ,l 遍历得:f (p ,h )=m in{tSD S (i ,j ,p ,q ,k ,l ) 1Φk ,l Φ39,k ≠l ;T SD S (i ,j ,h )=m in{f (p ,r ) 2Φr Φh }; Step 3　若T SD S (i ,j ,h )ΦA (p +q ,i ,j ),停,此时T SD S (i ,j ,h )即为最短乘车时间;否则令h =h +1,转Step 2;下面针对原题中的6对站点来求解.首先用D ijk stra 计算n SD S (i ,j ),结果见表3.92214期叶　军,等:公交转车的最短时间模型及求解表3　各对站点最短路径n SDS(i,j)点对335921828155720481097120485000820073014820485008723676 n SD S(i,j)12252411228对于第六对站点,由表3知S0087→S3676在公交转地铁再转公交情况下所需的时间根据定理3知最少需要5.5(1+1)+2.5×8+3=34m in,如果设r为乘公交的公交站数,在公交转地铁和地铁转公交两种情况下,即rΕ1,故所需的时间为3×r+2.5×(8-r)+5+4+4=33+0.5rΕ33.5m in由于站点S0087和S3676在地铁站附近,故而直接从S0087进地铁站D27做T2线经过8站到D36到S3676所需的时间是8×2.5+4+4+2=30m in,可见直接乘地铁的时间最短.但对于前5对站点,由于它们都不在地铁站附近,我们首先考虑公汽-地铁-公汽这种方案下的最短乘车时间.表4给出了在p+qΦ5时的求解.从表4中我们可以看到第1,3,4,5对站点,均有T SD S(i,j,5)<A(6,i,j).于是T SD S(i, j,5)已经是公汽转地铁再转公汽方案下的最短时间.表4　前5对站点最小乘车时间求解过程点对335921828155720481097120485000820073014820485t SD S(p+q)1+184.5116.59653.5387.5 1+27111095358.586.53 2+175.5118.51015492.5 1+376107310063.591.5 2+26231121005991.5 3+180.5117.5105.55697.5 1+47711210568.596.5 2+3671091056496.5 3+267114104.56196.5 4+185.5122.5110.559.5102.5T SD S(i,j,5)621079553.586.5A(6,i,j)6698.59663.591注　3)1+1,…,4+1表示p+q的取值情况.对于第二个点对S1557→S0481,我们可以继续扩大p+q的取值来求得最短乘车时间.这里我们采用另一简单的方法求出总的最短时间(仅考虑公汽以及综合考虑公汽和地铁).S1557到地铁线的最小站数为12(将S1557到地铁线附近的各个公汽站点作遍历搜索得到),而地铁到S0481最少站数显然不小于1.在p+q=6时,根据定理3的证明过程有t SD S(i,j,p,q,k,l)Ε0.5M+2.5n SD S(i,j)+5(p+q)+3Ε0.5×13+2.5×25+5×6=102但在表2中对于第二个点对不乘地铁时经过4次公交转乘只需要99m in,所以我们可以看出032数　学　的　实　践　与　认　识38卷第二个点对仅仅乘公汽进行转换就已经是最优的了.4　时间最优乘车方案综合以上内容,我们可以得出在公交转乘次数不超过5次的情况下,仅乘公汽及综合考虑公汽和地铁的最优方案及最优时间,见表5.仅乘公汽的时间最优解方案:S3359L324下行3站S1746L458唤行14站S1784L167下行1站S1828S1557L84下行12站S1919L189下行3站S3186L91上行10站S0902L254上行3站S0481S0971L13下行16站S2517L290环行13站S2159L469上行2站S0485S0008L198上行2站S1691L476下行5站S2085L017环行2站S0483L328上行2站S0525L103上行2站S0073S0148L308上行15站S3604L81下行2站S2361L156上行9站S2210L417下行3站S0485S0087L21下行1站S0088L231环行10站S0427L97下行1站S3676综合考虑公汽和地铁的时间最优解方案:S3359L324下行2站S2027L201上行3站S0609(D12)T26站S1961(D37)L428上行2站S1671L041下行1站S1828S1557L84下行12站S1919L189下行3站S3186L91上行10站S0902L254上行3站S0481S0971L049上行6站S0567(D01)T114站S2534(D15)L 156上行5站S2210L417下行3站S0485S0008L200上行6站S2534(D15)T13站D12T22站S0525(D25)L103上行2站S0073S0148L024上行4站S1487(D02)T113站S2534(D15)L156上行5站S2210L417下行3站S0485S0087(D27)T28站S3676(D36)表5　各对站点的最短乘车时间(注:时间不包括起始的3分钟)点对最短时间仅考虑公汽同时考虑公汽与地铁S3359→S1*******S1557→S0*******S0971→S048510395S0008→S0*******.5S0148→S048510286.5S0087→S3*******参考文献:[1]　2007年高教社杯全国大学生数学建模竞赛的B题评阅要点13214期叶　军,等:公交转车的最短时间模型及求解232数　学　的　实　践　与　认　识38卷M athematical M odel and Solution of theSystem of the Buses Cho icesYE Jun,　YAN G Zhen2hua(Co llege of M athem atics and Physics,N anjing U niversity of Po sts&T elecomm unicati ons,N anjing210003,Ch ina)Abstract:　W e establish the m athem atical model of p roblem one of p roblem B of2007Ch ineseU ndergraduate M athem atical Contest in M odeling the system of the buses cho ices.T hen w egive the exact so luti on of th is model.Keywords:　m athem atical model;the cho ice of the bus;the sho rtest ti m e期刊简介本刊主要刊登数学的最新的理论成果,及其在工业、农业、环境保护、军事、教育、科研、经济、金融、管理、决策等工程技术、自然科学和社会科学中的应用成果、方法和经验.主要任务是沟通数学工作者与其他科技工作者之间的联系,推动应用数学在我国的发展,为四化建设作贡献.主要栏目:数学建模、管理科学、工程、应用、问题研究、知识与进展、学科介绍、方法介绍、高等数学园地、数学史、研究简报、书刊评介、简讯.注:①投稿一式二份,原稿自己保存,编辑部不退还投稿的稿件.②编辑部不接收网上投稿.。

2007B题：乘公交，看奥运（数据有变化）我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。

这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。

针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。

为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。

请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。

并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。

(1)、S3769→S2857 (2)、S1557→S0481 (3)、S1879→S2322(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。

3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。

【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：6分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：5分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：8分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。

【附录2】公交线路及相关信息（见公汽线路信息，对原数据文件B2007data.rar 有少量更改）城市公交线路选择优化模型摘要本文针对城市公交线路选择问题建立了两个模型，一个是基于集合寻线算法模型，另一个是图论模型。

2007宁波第三届数学建模2007年宁波第三届数学建模比赛是一场吸引了众多参赛者的盛会。

此次比赛的主题为“城市道路交通流量规划与优化”，旨在通过数学建模的方式来解决城市交通流量问题。

以下为本次比赛的相关内容。

一、比赛要求本次比赛要求参赛者通过数学模型，对城市道路交通流量进行规划与优化。

具体要求如下：1.通过城市道路交通流量数据，建立数学模型，预测交通流量的变化趋势。

2.对城市道路交通流量进行分析，确定交通瓶颈。

3.通过交通瓶颈分析，提出交通流量优化方案，降低交通拥堵程度。

二、比赛流程本次比赛分为报名、初赛、复赛、决赛四个环节。

1.报名：参赛者需在规定时间内完成报名手续。

2.初赛：参赛者需要在规定时间内提交初赛作品。

初赛作品评选出前50名晋级复赛。

3.复赛：参赛者需要在规定时间内提交复赛作品。

复赛作品评选出前20名晋级决赛。

4.决赛：参赛者需要在规定时间内进行现场答辩。

决赛评选出前三名获得奖励。

三、比赛亮点本次比赛的亮点在于，通过数学模型，解决城市交通流量问题。

同时，本次比赛也提高了参赛者的数学建模能力和团队合作能力。

以下为本次比赛的一些亮点。

1.数学模型：参赛者需要建立数学模型，分析交通流量数据，预测交通流量的变化趋势，提出交通流量优化方案。

2.团队合作：参赛者需要组成团队，共同完成比赛任务。

在团队合作中，参赛者可以相互协作，共同解决问题。

3.实践能力：参赛者需要在实践中学习，通过实践来提高自己的数学建模能力和团队合作能力。

四、比赛成果本次比赛的成果丰硕，参赛者们通过数学模型，解决了城市交通流量问题。

以下为本次比赛的一些成果。

1.交通流量数据分析：参赛者们通过对交通流量数据的分析，确定了交通瓶颈，并提出了相应的优化方案。

2.数学模型建立：参赛者们建立了数学模型，预测了交通流量的变化趋势，并提出了相应的优化方案。

3.团队合作能力：参赛者们在团队合作中，相互协作，共同解决问题。

通过团队合作，参赛者们提高了自己的团队合作能力。

2007高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：北京化工大学参赛队员(打印并签名) ：1. 郑宇2. 姜园博3. 来斯惟指导教师或指导教师组负责人(打印并签名)：郭秋敏日期：2007 年09 月24 日赛区评阅编号（由赛区组委会评阅前进行编号）：2007高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：最优公交线路的模型研究摘要本文以乘车的路线为研究对象，根据乘客的不同需求，存在总时间、总费用、换乘次数三个目标函数。

将求解目标函数最优值的问题转化为最短路径问题。

在仅考虑公汽线路的时间最短模型中，首先由已知信息建立有向赋权图，以公交站点为顶点，所有直通公交线路为边。

对于时间，每条边的权值为公交车的运行时间加上转车时间。

然后可直接采用Dijkstra算法求出任意两公汽站点之间最优线路。

该模型方法比较简单，准确性高，可操作性强。

且对图中的权值做相应的改变，可以将其转化为总费用最少模型以及换乘次数最少模型。

同时考虑公汽和地铁线路，存在公汽与地铁的换乘问题，基于该问题本文设计了另一种有向赋权图，以所有公汽站点和地铁站点为顶点，所有直接连通线路为边。

公交线路选择的优化模型作者：张俊丽来源：《价值工程》2015年第28期摘要：本文针对城市公交线路选择问题建立了相应的数学模型。

将公共自行车看作独立于公汽、地铁的第三种交通方式。

利用网络图，主要从换乘次数、出行花费和出行总时间三个方面来确定最佳线路，分别考虑了各单目标，增加不同的上限约束，建立了任意两站点的最佳线路相应的网络流模型。

Abstract： In this paper， the corresponding mathematical model is established for the problem of urban public transportation route selection. The public bicycle as independent of the bus， the subway third modes of transport. Using the network diagram， three main factors are considered to find the best route， the number of trips， travel expenses and travel time.The network flow model of the best optimal line between any two sites， which considers the single objective and the different upper bound constraints.关键词：公交系统；最佳线路；最小费用流；优先因子Key words： bus system；best line；minimum cost flow；priority factor中图分类号：U491.1+7 文献标识码：A 文章编号：1006-4311（2015）28-0206-020 引言城市公共交通网络是城市交通网络的重要组成部分，提高城市交通系统的利用率被公认为是改善交通拥堵的有效途径之一。

B题公交车调度
公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。

下面考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。

该条公交线路上行方向共14站，下行方向共13站，第3-4页给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计。

公交公司配给该线路同一型号的大客车，每辆标准载客100 人，据统计客车在该线路上运行的平均速度为20公里/小时。

运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过 120%，一般也不要低于50%。

试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等。

如何将这个调度问题抽象成一个明确、完整的数学模型，指出求解模型的方法；根据。

承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：重庆大学参赛队员(打印并签名) ：1. 熊国刚2. 王杰3. 黎明指导教师或指导教师组负责人(打印并签名)：龚劬日期： 2007年 9 月 21 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：乘公交，看奥运【摘要】本文要解决的问题是以即将举行的08年北京奥运会为背景而提出的。

人们为了能现场观看奥运会，必然会面对出行方式与路线选择的问题。

因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。

鉴于公交系统网络的复杂性，我们没有采用常规的Dijkstra算法，而采用了高效的广度优先算法。

其基本思想是从经过起（始）点的路线出发，搜寻出转乘次数不超过两次的可行路线，然后对可行解进行进一步处理。

为满足不同查询者要求，我们对三个问题都分别建立了以时间、转乘次数、费用最小为目标的优化模型。

针对问题一（只考虑公汽系统），我们建立了模型一并通过VC++编程得到了任意两个站点间的多种最优路线，并得出所求站点间最优路线的最优值，如下进里又建立了图论模型。

本文的主要特点在于，所用算法的效率十分显著。

乘公交看奥运摘要本设计要解决的是合理给出两站点间的最佳路线选择问题，即给出一条经济且省时的路线。

在处理此问题之前，我们根据调查和分析，对影响线路选择的因素进行筛选，最终确定了以下三个影响较大的因素：第一是换乘次数；第二是乘车时间；第三是乘车费用。

依据各因素对路线选择的影响程度,我们按不同的权重对它们进行考虑。

从实际情况分析，人们通常宁愿多乘坐几站地也不愿换车，所以我们赋予换乘次数较大的权重。

为了解决换乘次数最少，乘车时间相对较短、乘车费用相对较少的问题，经过尝试与探索，我们采用了现代分析的方法，对起始站和终点站有无相交站点进行分类讨论，归纳出直达，换乘一次，换乘两次的情况（三次以上的情形可以类推），并通过Matlab 编制程序，给出了任意两站点间的最佳乘车路线以及换车的地点，最后还提出了进一步的意见和建议。

关键词：最佳路线换乘次数乘车时间乘车费用一、问题的重述第29届奥运会明年8月将在北京举行，作为城市枢纽的公共交通承担着非常重的运输任务。

近年来，北京市的公交系统有很大的发展，公交线路的条数和公交车数量在迅速增多，给人民生活带来便利的同时，也面临多条线路得选择问题，有时出行往往还需要转乘多辆公交车才能到达目的地。

如何在短时间、换乘次数最少、成本最低的情况到达目的地，是人们所关注的问题。

因此，我们通过建立线路选择的模型与算法，设计一套自主查询计算机系统，查询到出行时所需的最佳公交路线及换乘方法，给人们出行节约更多的时间和金钱。

要求：1、仅考虑公汽线路，建立任意两公汽站点之间线路选择问题的数学模型与算法。

并求出以下6对起始站→终到站之间的最佳路线。

（1）S3359→S1828（2）S1557→S0481（3）S0971→S0485 （4）S0008→S0073（5）S0148→S0485（6）S0087→S3676 2、同时考虑公汽与地铁线路，解决1中问题。

3、如果所有站点间的步行时间已知，建立任意两站点间路线选择问题的数学模型。