乘公交看奥运模型

北京市公交最优乘车路径选择的数学模型摘要2008年8月，奥运圣火将在北京点燃。

盛大的奥运赛事聚焦了全世界人民的目光，明年的北京将绽放最绚丽的光彩。

届时，客流量将会大幅上升，环境、交通、城市建设都将面临很大考验。

怎样才能更好的解决奥运期间市民和游客的出行问题呢？针对这样的实际问题，我们设计了一个城市公交线路的自主查询系统，建立了关于城市公交最优乘车路径选择的数学模型和算法，巧妙的运用Java语言编写程序，解决了现实生活中乘车路径选择的问题。

针对问题 1，在只考虑公汽线路时，首先求出起始站和终到站所有公交线路集合的交集，若此交集为非空交集，则选择所有直达线路中途经站点数最少，即花费最少的线路出行；若交集为空，选择起始站附近的站点，求出此站和终到站所有公交线路集合的交集，若为非空交集，则可选择换乘一次的方法出行；否则，换乘两次，换乘三次……直到找到换乘N次的乘车方案为止。

存在多条乘车线路时，考虑途经站点最少的乘车方式。

在此基础上，通过运用Java语言编程，确定了所需的最优乘车路径：（1）乘坐L436路公交车从S3359到S1784站，在S1784站换乘L167或L217路到S1828站，全程换乘一次，耗时101分钟，乘车费用为3元；（2）乘坐L84路公交车从S1557到S1919站，在S1919站换乘L189到S1402站,在S1402换乘L460到S0481站，全程换乘两次，耗时112分钟，乘车费用为3元；（3）乘坐L13路公交车从S0971到S2184，在S2184站换乘L417路到S0485站，全程换乘一次，耗时128分钟，乘车费用为3元；（4）乘坐L43路公交车从S0008到S1383，在S1383站换乘L282路到S0073站，全程换乘一次，耗时113分钟，乘车费用为3元；（5）乘坐L308路公交车从S0148到S0302，在S0302站换乘L427到S2027站，在S2027站换乘L469到S0485,全程换乘两次，耗时118分钟，乘车费用为3元；（6）乘坐L454路公交车从S0087到S3469，在S3469站换乘L209路到S3676站，全程换乘一次，耗时65分钟，乘车费用为2元；针对问题 2，要求同时考虑公汽线路和地铁线路，在同一地铁站对应的任意公汽站间可免费换乘，利用问题1的思想建立数学模型，运用Java语言编程，得到同时考虑公汽和地铁时的最优乘车路径：前五对起始站→终到站的最优乘车路径的选择与问题1一致。

数学建模全国⼀等奖论⽂系列（27）乘公交，看奥运摘要由于可供选择的车次很多，各种车辆的换乘⽅式也很多，为了避免上下⾏站点不⼀样的车次等对路线产⽣的影响，我们以由易到难的思路来完成模型。

⾸先分析⼀辆车可以直接到达的情况，在这其中⼜考虑到环线的特殊性对其单独进⾏判断讨论；由于⼀辆车可使乘客到达⽬的地的可能性太⼩，我们接下来讨论要进⾏⼀次换乘的情况，在这⾥巧妙地利⽤矩阵来判断两辆车是否含有共同站这个思想，避免了⾄少两重循环，使运算速度⼤⼤提⾼；虽然这样就已经能够解决不少的问题，但并不完全，因此我们继续计算换乘两次的乘车路线，经过⼤量的运算，我们发现基本所有的站点间都可以通过换乘两次到达，⾄此对公交线路的讨论基本完成。

对加⼊地铁的讨论与只有公交车时类似，从最简单的两辆地铁换乘的情况开始考虑，由浅⼊深。

论⽂中并没有运⽤⼤量的符号，⽽是⽤⽂字来说明程序的主要步骤，这样可以让不了解程序的读者也清楚地知道模型的思路，⽽且，只要知道起始与终点，利⽤程序就可以计算所有可能路线，并可以在结果中为读者提供路线的相关信息，⽐如路费及所需时间，以供选择。

对于最优的解释，我们除了以时间最少、车费最省为原则，还对时间与车费进⾏了加权平均，⽽权数便是乘客对时间与⾦钱的偏好程度，当输⼊⾃⼰愿⽤1元钱去换多少分钟乘车时间时，程序会根据个⼈的不同喜好，来选择出适合每个⼈的最优路线。

这样将程序⼈性化，可以更符合实际中⼈们的需要。

关键词：公交线路选择最优化矩阵加权平均数组分类讨论⾃主查询问题重述北京是中国的⾸都，是政治、⽂化中⼼，同时也是国际交往的中⼼。

在成功取得2008年第29届夏季奥运会的举办权后，北京市城市建设的步伐将进⼀步加快。

众所周知，可靠的交通保障是成功举办奥运会的关键之⼀，公共客运交通服务系统尤为重要。

在保持公车票价⼀直相对较低的情况下，北京市⼜已经实⾏机动车单双号出⾏，⽬的就是为了⿎励⼈们乘公共汽车出⾏，缓解交通阻塞状况。

第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期刊简介本刊主要刊登数学的最新的理论成果,及其在工业、农业、环境保护、军事、教育、科研、经济、金融、管理、决策等工程技术、自然科学和社会科学中的应用成果、方法和经验.主要任务是沟通数学工作者与其他科技工作者之间的联系,推动应用数学在我国的发展,为四化建设作贡献.主要栏目:数学建模、管理科学、工程、应用、问题研究、知识与进展、学科介绍、方法介绍、高等数学园地、数学史、研究简报、书刊评介、简讯.注:①投稿一式二份,原稿自己保存,编辑部不退还投稿的稿件.②编辑部不接收网上投稿.。

建模更是一种精神】数学建模全国大赛历年题目分析以及参赛成功方法数学建模竞赛的赛题分析1. CUMCM历年赛题简析2. “彩票中的数学”问题3. 长江水质的评估、预测与控制问题4. 煤矿瓦斯和煤尘的监测与控制问题5. 其他几个数学建模的问题数学建模竞赛的规模越来越大,水平越来越高；竞赛的水平主要体现在赛题水平；赛题的水平主要体现：（１）综合性、实用性、创新性、即时性等；（２）多种解题方法的创造性、灵活性、开放性等；（３）海量数据的复杂性、数学模型的多样性、求解结果的不唯一性等。

纵览16年的本科组32个题目(专科组13个)，从问题的实际意义、解决问题的方法和题型三个方面作一些简单的分析。

一、CUMCM历年赛题的简析1. CUMCM 的历年赛题浏览：1992年:(Ａ)作物生长的施肥效果问题(北理工：叶其孝）(B)化学试验室的实验数据分解问题（复旦：谭永基）1993年:(Ａ)通讯中非线性交调的频率设计问题（北大:谢衷洁）(Ｂ)足球甲级联赛排名问题（清华：蔡大用）1994年:(Ａ)山区修建公路的设计造价问题（西电大：何大可）(Ｂ)锁具的制造、销售和装箱问题（复旦:谭永基等）1995年:(Ａ)飞机的安全飞行管理调度问题（复旦:谭永基等）(Ｂ)天车与冶炼炉的作业调度问题（浙大:刘祥官等）一、CUMCM历年赛题的简析1. CUMCM 的历年赛题浏览：1996年:(A)最优捕鱼策略问题（北师大：刘来福）(B)节水洗衣机的程序设计问题（重大：付鹂）1997年:(A)零件参数优化设计问题（清华：姜启源）(B)金刚石截断切割问题（复旦：谭永基等）1998年:(A)投资的收益和风险问题（浙大：陈淑平）(B)灾情的巡视路线问题（上海海运学院:丁颂康）1999年:(A)自动化机床控制管理问题（北大：孙山泽）(B)地质堪探钻井布局问题（郑州大学：林诒勋）(C)煤矸石堆积问题（太原理工大学：贾晓峰）一、CUMCM历年赛题的简析1. CUMCM 的历年赛题浏览：2000年:(A)DNA序列的分类问题（北工大：孟大志）(B)钢管的订购和运输问题（武大：费甫生）(C)飞越北极问题（复旦：谭永基）(D)空洞探测问题（东北电力学院：关信）2001年:(A)三维血管的重建问题（浙大：汪国昭）(B)公交车的优化调度问题（清华：谭泽光）(C)基金使用计划问题（东南大学：陈恩水）2002年:(A)汽车车灯的优化设计问题（复旦:谭永基等）(B)彩票中的数学问题（信息工程大学：韩中庚）(D) 球队的赛程安排问题（清华大学：姜启源）一、CUMCM历年赛题的简析1. CUMCM 的历年赛题浏览2003年:(A)SARS的传播问题（集体）(B)露天矿生产的车辆安排问题（吉林大：方沛辰）(D)抢渡长江问题（华中农大：殷建肃）2004年:(A)奥运会临时超市网点设计问题(北工大：孟大志)(B)电力市场的输电阻塞管理问题(浙大:刘康生）(C)酒后开车问题（清华大学：姜启源）(D)公务员的招聘问题（信息工程大学：韩中庚）2005年:(A)长江水质的评价与预测问题（信息工大:韩中庚）(B)DVD在线租赁问题（清华大学：谢金星等）(C) 雨量预报方法的评价问题（复旦：谭永基）一、CUMCM历年赛题的简析1. CUMCM 的历年赛题浏览2006年:(A)出版社的资源管理问题（北工大:孟大志）(B)艾滋病疗法的评价及预测问题（天大：边馥萍）(C)易拉罐形状和尺寸的设计问题（北理工：叶其孝）(D)煤矿瓦斯和煤尘的监测与控制问题（信息工程大学：韩中庚）2007年:(A)中国人口增长预测问题（清华大学:唐云）(B)“乘公交，看奥运”问题（吉大：方沛辰，国防科大：吴孟达）(C)“手机套餐”优惠几何问题(信息工程大学:韩中庚)(D)体能测试时间的安排问题(首都师大:刘雨林)一、CUMCM历年赛题的简析一、CUMCM历年赛题的简析1. CUMCM 的历年赛题浏览2001年夏令营三个题:(A)三峡工程高坡开挖优化设计(三峡大学:李建林等）(B)城市交通拥阻的分析与治理(北京理工大学:叶其孝）(C)乳房癌的诊断问题（复旦大学:谭永基）2006年夏令营三个题:(A)教材出版业的市场调查、评估和预测方法问题（北工大:孟大志）(B)铁路大提速下的京沪线列车调度问题（信息工程大学:韩中庚）(C)旅游需求的预测预报问题（北京理工：叶其孝）2、从问题的实际意义分析32个问题从实际意义分析大体上可分为：工业、农业、工程设计、交通运输、经济管理、生物医学和社会事业等七个大类。

奥运会场馆⼈员疏散的数学模型奥运会场馆⼈员疏散的数学模型⼯⾼班姜伟3011141076吴志军3011211085摘要本⽂参阅⼤量具有实际背景的统计数据, 对体育场⼈员组成、交通⼯具使⽤情况做出合理评估. 针对体育场⼈员疏散各环节, 提出了“拥挤状态下的⼈流模型”、“运动场通道设计的最⼤流量原则”、“车辆停放优化模型” 和“地铁-公交车疏散模型”四个⼦模型.对模型进⾏了适⽤范围、边界条件、实测数据拟合等特性的分析, 得到了: “密度-⼈流通量”曲线、体育场疏散时间和通道设计计算公式、最优停车⽅式设计、地铁-公交车疏散时间公式等⼀系列具有实⽤价值的结果. 上述结果与各种参考⽂献中提供的实测数据⾮常吻合.借助所获得的模型和结论, 给出了对运动场疏散全过程的时间、进程模拟, 并利⽤虚拟现实建模技术给出部分疏散场景的实况.根据模拟的结果, 认为100 000⼈规模的体育场可以在45min左右的时间内完成⼈员疏散. 并在此基础上提出体育场及其周边设施建设的若⼲优化⽅案.关键字体育场馆疏散调度⼈流模型问题重述2008年奥运会将在北京举⾏，奥运会期间的交通问题是⾮常重要的问题。

特别是开幕式、闭幕式这样的场合，参与⼈员多，离开时间集中，对交通设施的建设和车辆的安排调度都是⼀个值得探讨的问题。

根据你所了解的往届奥运会举办城市的有关交通⽅⾯的解决⽅案的信息，考虑到北京市的场馆设施和交通状况，请你分析和设计⼀套可以保证在奥运会期间的任何仪式或⽐赛结束后能够在合理的时间内将⼈员疏散的⽅案，⽅案的设计要尽可能的节省投资。

假设场馆坐落在市郊，可容纳10万⼈，附近有⾜够通⾏能⼒的⾼速公路。

要求就场馆的出⼝、通道、停车场的设置、合理的车型、各类参加⼈员的构成估计、车辆的调度、可以接受的等待时间等问题进⾏分析和设计，建⽴适当的数学模型来解决。

给出⼀个模拟疏散实况，计算全部撤离所需的时间。

1．1．相关假设1.1 体育场选址和规模根据北京市对奥运会场馆建设的规划[1] 承担奥运会开、闭幕式的国家体育场(The National Stadium)将位于北京市北部奥林匹克公园的中⼼区域. 这⼀区域周边公路通⾏能⼒较强且处于市郊, 可认为疏散过程不会受到外部交通的影响.题⽬给出的体育场设计规模为10万⼈, 依照参照[2]所给出的建筑标准以及往届奥运会场馆的建设先例, 估算体育场的占地⾯积(不包括停车场等周边设施)约为12万m2.图1-1. 北京2008奥运会⽐赛地点图1-2. 奥林匹克公园平⾯图1.2 出席⼈员组成体育场的⼈员由表演⼈员、观众、贵宾、⼯作⼈员组成, 奥运会在主体育场举⾏的各种仪式或⽐赛, 观众都将占⼈员总数的95%以上. 可以认为体育场疏散的主体为观众, 因此⽂中建⽴的模型除特殊提及外, 均针对普通观众.1.3 交通⼯具选择分配体育场的选址位于市郊, 绝⼤部分观众都将乘坐代步⼯具往返. 届时可以选择的交通⼯具包括: ①通往体育场的地铁和公交车②⼩型私⼈车辆③出租汽车④私⼈团体使⽤的客运车辆.这⾥认为④所占⽐例不⼤, 可以忽略. 下⽂将着重讨论①和②的调度⽅案和疏散能⼒.2． 2．拥挤状态的⼈流模型2.1 个体⽣理尺⼨个体的占地⾯积由其各⽅向上的最⼤⽣理尺⼨决定, 通常使⽤肩宽b p 和⾝体厚度d p 决定. 为了简便计算, 通常将个体抽象成椭圆形, 或矩形区域[3].图2-1. ⼈体的椭圆形模型图2-2. ⼈体的矩形模型此时的个体占地⾯积S p (m 2)可分别表⽰为:p p pE 41d b S π=12- 和p p pS d b S =22- 下⾯给出不同地区⼈群⽣理尺⼨的数据考虑到我国⼈⼝素质未来6年的发展情况, 兼顾计算的简便, 在本⽂中取 b p =0.5m, d p =0.25m, S p =S pS =0.125m 2.2.2 ⼈群密度⼈群中个体的⽣理尺⼨和个体之间的间距共同决定⼈群的密度, 参考资料[4]给出了⼀些典型情况下的空间占⽤(最⼩包络圆的直径).鉴于体育场疏散时观众⼈群密度偏⼤, 可以假设相邻个体的横向间距恒为100mm, 纵向间距随⼈群密度变化.资料[5]进⼀步指出: 出于对安全因素的考虑, 拥挤区域站⽴⼈群的最⼤密度不应超过40⼈/10m 2. 结合上⾯对个体占地⾯积的计算, 可以得到体育场各通道内的⼈群密度的允许区间为(0, 4) ⼈/m 2. (此处尚未考虑速度因素, 下⽂将给出理想值).2.3 拥挤状态下的⼈流模型⼏点假设:1 1 ⼈流限制在单向定宽度⽆限长通道内前进, 且相对饱满, 即速度不⼤于某极限速度V max =3m/sec.2 2 任何个体均遵循普遍原则前进: 不试图超越前⽅个体, 亦不会留出过⼤间距.3 3 ⼈群密度ρ(⼈/m 2)在通道各处相等, 且随速度v (m/sec)的递增⽽递减, 取值范围为(ρmin , ρmax )4 4 定义⼈流通量q (⼈/m ·sec)为单位时间、单位通道截⾯积通过的⼈数, 则有q =ρv模型建⽴:拥挤状态下步幅l (m)等于相邻个体的间距. 参照图2-3, 结合上⽂对个体⽣理尺⼨参数的计算, 可以得到:p p )1.0(1d b l -+=ρ32-图 2-3. ⼈流模型⽰意图利⽤[6]和[7]给出的速度、步幅等数据, 能够确定⼈群密度ρ与⾏⾛频率f 之间存在关系:n K ρ=f 42- 并可以进⼀步验证上式中K=1.36, n ≈0.5.将⼈群速度表⽰为密度的函数:np p K ))1.0(1(ρρ?-+=?=d b f l v 52- 确定⼈流通量:nK d b v q ρρ?-+=?=)1.01(p p 62- 利⽤前述数学模型和相关参数, 并考虑边界条件, 绘制v -ρ曲线和 q -ρ曲线如下:图 2-4. 密度-速度曲线图 2-5. 密度-⼈流通量曲线可以确定当⼈流密度值ρ0=2.22⼈/m 2, 相应的速度为v 0=1.01m/sec.时, 通量q 取得极值q *= 2.25⼈/m ·sec.结论和分析:理论预测所得曲线⾛势与⽇常经验相符, 并且量值上与现有数据相当吻合. 通过对⼈流通量变化趋势的计算, 可以获得满⾜通量最⼤的速度和密度条件.体育场内的各通道均为狭窄路段, 且疏散过程中⼈流密度⾜够⼤, 可以应⽤此模型进⾏疏散分析. 为了获得最⼩的疏散时间, 运动场内各处通道的设计均应满⾜⼈流通量在q *附近. 下⽂中将应⽤此结论探讨实施细节, 并给出预期的疏散时间.3． 3．运动场设计优化和疏散时间计算3.1 通道设计的最⼤流量原则前⾯分析得到: 为使疏散时间最⼩, 需要在设计体育场内通道时保证⼈流通量q 在其极值q *附近, 并且尽量宽阔. 为此参考[2]总结下列设计原则:1. 1. 根据中国⼈的⾝材特点, 座宽设计为0.6m. 每圈平均有50组座椅坐供1 600⼈就座. 相邻两组间距离为 1.0m. 为使流量最⼤,由于座位密度近似为⼈流密度的初始值, 应把座位密度设为2⼈/m 2, 即每⼈占据0.5m 2的空间, 则每前后相邻两排间距设计为0.5/0.6=0.83m. ⼀圈平均周长为50×(30×0.6+1)=950m. 上下层各有31~32排. 总计约有100 000个座位.图 3-1. 座椅排布和通道设置2. 2. 相邻两排座椅之间的通道(称为0级通道)仅需承载单股⼈流, 其设计宽度满⾜⼀⼈通过即可. ⼈流在0级通道⽆法达到理想的通量q *, 因此每段的长度应尽可能短(建议为15倍座位长度). 0级通道的总长度仅与场内座位数⽬有关.3. 3. 其它依次各级内部通道的设计, 应合理控制宽度, 保证前⼀级的⼈流均匀汇⼊, 使稳定状态下整个通道内的平均⼈流通量尽可能⾼.图 3-2. 通道连接部分由此原则可以得到 1n n 2-=D k D 13-k —— n 级通道与n -1级通道的汇合点总数 D i —— i 级通道的宽度4. 4. 外通道(出⼝)的设计, 存在关系式:BC D =23-B —— 疏通⼝(道)设计可通过⼈流股数C —— 单股⼈流宽度. ⼀般地, C =b p +0.1=0.6m.其他设计细节还包括:1 1 采⽤下⾏、⽔平、坡道疏散⽅式以提⾼⼈群移动速度.2 2 楼梯和坡道宽度较⼤(>3m)时, 加设中间分隔栏杆扶⼿, 辅助疏导⼈流. 3.2体育场疏散时间的计算体育场观众数量多, 疏散时间集中, 因此设计应有畅通的交通道和均匀分布的出⼊⼝, 以便在⼀定时间内使全部观众疏散完毕. 给出⼤型体育场疏散时间计算公式[2]:BA N V S T +=s 33- T s —— 疏散时间V —— ⼈流疏散速度(m/min)A —— 单股⼈流通⾏量(⼈/min)B —— 疏散⼝(道)可通过⼈流股数N —— 疏散⼈数S —— 疏散距离(m)就影响体育场疏散时间的⼏个因素分别加以分析:1 1 单股⼈流通⾏量A(⼈/min)ρρVC C V A ==143- C —— 单股⼈流宽度. ⼀般取C =b p +0.1=0.6m.ρ —— ⼈群密度2 2 疏散⼝(道)数量n b疏散⼝(道)数量越多, 则从看台出⼝到外出的加权总距离越⼩, 越有利于缩短疏散时间T s .但外出⼝的数量不应过多, 否则从体育场涌出⼈流过多且过于分散, 不利于控制, 同时加重场外通路的负担, 容易在较狭窄路段形成瓶颈, 不利于安全.考察国外⼤型体育场设计, 把主要外出⼝数n b 定为4. 对称分布. 并可增加备⽤出⼝使总出⼝数达到8个甚⾄更多, 为意外事故发⽣时恐慌⼈流的疏散.3 3 疏散⼝(道)可通过⼈流股数B这是影响疏散时间的最主要因素, 是可以控制的. 参考体育场观众疏散设计标准及其设计规模, 预计外出⼝疏散时间T o 为15min.观众应占总⼈数的95%以上, 认为N =100 000.b o An T N B =53- 4 4 ⼈流疏散速度V (m/min)“拥挤状态下的⼈流模型”定量地给出了⼈群密度和速度之间的关系. 为了获得最⼩的疏散时间, 运动场内各处通道的设计均应满⾜⼈流通量在q *附近. 从⽽速度亦应在v 0附近.⼈流疏散速度V = v 0=60m/min5 5 .疏散距离S (m)由看台上的出⼊⼝⾄外门⼝,经过道、楼梯的实际距离, 计算体育场总距离时则为加权距离, 其计算公式如下:∑∑==?=ni i n i i i bb S S 1163- b 1, b 2, ... 为第⼀、第⼆疏散道⼈流股数S 1, S 2, ... 为第⼀、第⼆疏散道疏散距离疏散距离S 应尽量⼩. 参考现有体育场设计, 观众席分为上下2层. 疏散形式如图3-3[2]:图3-3. 双层的疏散通道体育场设计为对称结构, 为⽅便计算, 只考察取出的扇形部分.图 3-4. 看台的扇形模型由公式3-6, 此处:212211)(s s s S s S S ++?=73- S 1 —— 上层观众平均疏散距离S 2 —— 下层观众平均疏散距离s 1 —— 上层看台扇形⾯积s 2 —— 下层看台扇形⾯积此扇形模型中⽤扇形⾯积代替了⼈流股数. 在这个扇形中, 中间⼀排有1600/8=200个座位. 假设相邻长排相差2个座位, 上下层均有30排左右. 因⽽, 离赛场最近⼀排座位有140个座位, 最远⼀排有260个座位. 计算扇形看台⾯积:排数最远⼀排座位数最近⼀排座位数?+=)(s 83- 则有:172321=s s 83- 每圈距离l c ≈120m. 楼梯及缓台的坡度α=30o. 上下层观众席⾼h =排数×每排⾼(约0.47m)=14.1m. 则上下楼的平均距离为14.1/sin30o=28.2m. 则:m 7421c 1=+=h l S 93-m 88sin 212=+=αh S S 103- 带⼊公式3-7得到:m 05.82=S 113- 计算体育场疏散时间 min 4.16o s =+=T V S T 123-4． 4．停车场规划和疏散时间4.1 停车场规模前⾯1.3中提到疏散车辆以地铁-交车和私⼈车辆为主, 运动场附设的停场为私⼈车辆专有. 下⾯计算乘坐私⼈车辆观众的⽐例.北京市2001年私有车总计为50万辆, 并保持每年15%的增长率[8]. 同期⼈⼝总数为1 380万, 预计年增长率2.4%[9]. 可以推知: 2008年北京市及周边地区车辆占有率约为每百⼈8.16辆. 加之对未来车辆增长的考虑, 停车场设计规模为10 000辆, 按平均每辆车承载3⼈计算, 将可疏散27 000⼈.为减少疏散⼈群的步⾏时间, 建造两个地上停车场, 单个停车场容量约为5 000辆.为了节约成本, 将考虑尽量减⼩停车场尺⼨和提⾼空间利⽤率.4.2 车辆尺⼨数据利⽤从[10]获得的常见车型尺⼨数据, 可以估算出私⼈车辆的平均尺⼨.本⽂中使⽤下述模型及数据计算停车场的相关设计参数.图 4-1. 平均车型尺⼨4.3 车辆停放⽅式优化单车占地⾯积与停车⾓度θ的关系如图4-2所⽰:图4-2 单车占地⾯积设l c 和w c 分别为⼀个停车位的长和宽:θθcos 5.2sin 5c +=l 14- θsin /5.2c =w 24- 则⼀个车位的占地⾯积θθθsin )cos 5.2sin 5(5.2c +=S 34-变化规律如图4-3所⽰图 4-3 Sc-θ的关系曲线 S c 随θ减⼩⽽增⼤, 但θ的减⼩有利于车的开出. 当θ为45o时, 单车占地⾯积变化不⼤, ⽽出车较易. 并且可以选择使车辆交错停放, ⼤⼤节省了空间.图 4-4(a) 45度斜式泊车⽰意图图 4-4 (b) 泊车⾓度⾮45度时存在空间浪费θ=45o时, 单车平均占地为:m 4.4c =l 44- m 5.3c =w 54-4.4 停车场设计和车辆调度优化为进⼀步优化停车场结构, 减少或避免阻塞, 提出下列停车场设计和车辆调度原则:1. 1. 尽量缩短停车场长宽⽐, 以保证观众⾏⾛路线尽可能短, 即尽量缩短⾏⾛的时间.2. 2. ⼈⾏道与出车道交叉处, 设置斑马线, 同时提前设置限速障碍物. 限速障碍物可以保障⾏⼈安全, 并使车辆通过减速带后的车距拉⼤, 便于其它车辆插⼊车流.图4-5 限速障碍物对⾏⼈的保护作⽤图4-6 限速障碍物利于车辆插⼊车流图4-7 设置限速障碍物对相邻车距的影响3. 3.⼊车道为4车道, 其中中间两车道只允许停车位在7⾄12组的车⾏驶, 以避免车⾏⽅向交叉或相互阻碍图4-8. 停车位分组⽰意4. 4.停车场形状设计成狭长有利于出车道与公路的连接.5. 5.疏散⼈流进⼊停车场时, 可利⽤⼊车道将⼈流导⼊停车场, 这时不允许车辆驶⼊.4.5 停车场疏散时间的计算⼏点假设:1. 1.停车场采⽤单⼊多出式, 中部驶⼊车道, 设计为4车道, 宽10m. 共⽤驶出车道的两排车为⼀组, 出车道道宽4m. 每隔固定间隔设置⼈⾏道, 道宽2.5m.2. 2.⼈⾏道数⽬变化较⼩, 为⽅便计算⼜不失⼀般性, 设⼈⾏道共有六条.3. 3.在疏散时, ⼈流可由⼊车道引进, 极⼤避免了⼈流与车流的交叉. 且有限速障碍物限速, 使车在通过⼈⾏道之前速度很慢, 因此先忽略⼈流对车流的影响.4. 4.出车时的平均车速为5m/sec, ⼈⾏⾛的速度为1.3m/sec.变量说明:n——组数w p——⼈⾏道总宽w i——⼊车道宽t1——疏散过程中离出⼝最远车辆的驶出时间t 2 —— 从停车场⼊⼝到某辆车步⾏的最⼤时间计算公式:n w t 25000c 1=64-)225000)42((3.11i p c c 2w w n w n l t ++++=74- 经计算, t 1<< t 2, 因此疏散时间主要取决于t 2. 当n 取19时, t 2的值最⼩. 停车场疏散时间:min 7)min(21p =+=t t T 84- 同时可以进⼀步给出停车场的优化设计参数: 单排车总数132辆, 停车总数为5 016辆. 每隔22辆车设⼀⼈⾏道. 共设四条⼈⾏道. 车场总长为500(487)m, 总宽为250(244)⽶. 占地⾯积为12.5(11.9)万m 2.5． 5．地铁和公交车疏散时间前⾯4.1中计算得出观众中将有27%即27 000⼈使⽤私⼈车辆, 这⾥假设余下观众均按照承载⼈数⽐例选择轨道交通⼯具和公交车. 鉴于这两种交通⼯具的时间规律, 承载能⼒固定, 模型相对简单, 下⾯直接给出假设和结论:地铁和公交车疏散时间:g c t N N N T b ?=15- t g —— 相邻车次的等待间隔时间(min).N —— 选择交通⼯具的⼈数 73 000⼈N l —— 可⽤的线路数⽬.N c —— 每车次的疏散能⼒(⼈/车次)参考[11]给出的量值, 可以测算N c 数量级为103, 这⾥设为2 000⼈/车次. 并设理想等待时间t g =2.5min. 根据[1]的有关新闻, 北京市将为2008年奥运会新建7条地铁线路, 假设其中N l=3条位于主体育场附近. 则带⼊公式 5-1 得到:min 30b =T 25-6． 6．结论和分析根据2.3节拥挤状态下的⼈流模型: 体育场各通道和出⼝的设计均尽量保⾜够⼤的⼈流密度ρ和必要的流动速度v , 从⽽使⼈流通量q 尽可能接近极值q *. 在此前提下, 3.2, 4.5和5节分别针对⼈员疏散的各个阶段, 给出体育场通道、外出⼝、停车场布局等定量结论和车辆调度原则等设施建设的细节. 进⼀步得到各阶段疏散时间的估计. 给出体育场⼈员总体疏散时间T 的表达式:),max (b p i T T T T +=16- T i —— 体育场内疏散时间(公式3-12)T p —— 停车场疏散时间(公式4-8)T b —— 地铁和公交车辆的疏散时间(公式5-2)总结前⽂分析和计算结果, 100 000⼈规模的体育场的全部疏散时间约为46分钟.分析T的各分量不难发现: 地铁和公交车疏散时间T b为影响疏散时间的主要因素, 为尽量减⼩T b, 可以考虑增加可⽤线路数⽬和车次密度. 另⼀⽅⾯, 由于我国私⼈车辆基数处在相当低的⽔平, 停车场规模较⼩使得T p被T b所掩盖. 但是可以预见, 2010年之后的体育场馆疏散将更多⾯对如何协调各种交通⼯具的搭配问题.7．7．参考⽂献[1]. 北京2008奥运会官⽅⽹站, /doc/c0112cbf9a6648d7c1c708a1284ac850ac0204cd.html /[2]. 蔡镇钰主编, 《建筑设计资料集第7册》. 北京: 中国建筑⼯业出版社. 1997[3] J. J. Fruin, Pedestrian Planning and Design. Metropolitan Association of Urban Designers and Environmental Planners, Inc. 1971.[4] Stephen Pheasant, Bodyspace: Anthropometry, Ergonomics and the Design of the Work2nd Ed. USA Taylor & Francis Inc. 2001[5] Department of National Heritage, Guide to Safety at Sports Grounds 4th Ed.H.M.S.O. Publications. 1997[6] 姜启源编, 《数学模型》第2版. 北京: ⾼等教育出版社. 1993[7] G.. Keith Still, Crowd Dynamics. /doc/c0112cbf9a6648d7c1c708a1284ac850ac0204cd.html /[8] 竞车⽹, /doc/c0112cbf9a6648d7c1c708a1284ac850ac0204cd.html /news_3/rushiyiwei.htm[9] 中国⼈⼝信息⽹, /doc/c0112cbf9a6648d7c1c708a1284ac850ac0204cd.html /new0406-6.htm[10] 中国汽车⽹, /doc/c0112cbf9a6648d7c1c708a1284ac850ac0204cd.html /[11] 许燕莉, 《北京轻轨铁路梦圆在即》. 《光明⽇报》1995年11⽉15⽇[12] 刘禹，林威，李德志, 2002年哈尔滨⼯业⼤学数学建模竞赛试题答卷。