2007年數(shù)學建模比賽答案乘公交看奧運

一、問題重背從今年的1月1日至今，每天新增機動車1060輛，現(xiàn)在已經(jīng)達到297萬輛。為緩解交通壓力，將優(yōu)先發(fā)展公共交通，加快軌道交通系統(tǒng)的建設(shè)，114公里軌道交通的基礎(chǔ)上，還將爭取新62004002015561公里。目前，20%2015承擔公共交通的出行比例的50%以上[1]345車每天將增加108個車次；從德勝門通往小區(qū)的344路快車每天增加915120車次；300564208532255另外，將開辟10條臨時專線。其中涉及：中心區(qū)4條、五棵平十三陵鐵人三項1條、工業(yè)大學體育館1條、朝陽公園沙灘排球館1條3200881公園賽艇、奧運公園曲棍球比賽的觀眾服務(wù)。預計2008年8月8日開賽一天，35044516人次[3]問第29屆奧運會明年8月將在舉行，屆時有大量觀眾到現(xiàn)場奧運比賽其中大部分人將會乘坐公共交通工（簡稱包括公汽地鐵等出行。這些年來，城市的系統(tǒng)有了很大發(fā)展，市的線路已達800條以上，使得公眾的出行更加通暢、便利，但同時也多條線路的選擇問題。針對市場需求，需要研制開發(fā)一個解決線路選擇問題的自主查詢計算6對起始站→終到站之(1)、(2)、(4)、(5)、2二、基本參數(shù)相鄰公汽站平均行駛時間(包括停站時間)：3相鄰地鐵站平均行駛時間(包括停站時間)：2.5公汽換乘公汽平均耗時 5分鐘(其中步行時間2分鐘地鐵換乘地鐵平均耗時 4分鐘(其中步行時間2分鐘地鐵換乘公汽平均耗時 7分鐘(其中步行時間4分鐘公汽換乘地鐵平均耗時 6分鐘(其中步行時間4分鐘為：0～20站：1元；21～40站：2元；40站以上：3元地鐵票價：3元（無論地鐵線路間是否換乘三、基本假(1)忽略天氣的影響，道路不發(fā)生擁擠，人流不發(fā)生擁擠(2)相鄰公汽站、地鐵站行駛時間(包括停站時間)為常量(3)公汽、地鐵等換乘耗時為常量(4)起始點不需要步行，只需等車(5)公汽環(huán)形線路為雙向的，地鐵環(huán)形線路為單向的四、符號定L公汽系統(tǒng)的公汽路線集合；T地鐵系統(tǒng)的地鐵路線集合；S公汽系統(tǒng)站點的集合；DkSiKi{k1,kSi

第ikjS,j=1,2SibDiBi{b1,bDi

ibjD,j=1,2DiRi第iV{v1,v2,vnE{e1,e2,en

由viviSD由eieivivj)，表是vivjw(ei)

(,第iG(V,

由V，EA，BICY換乘次數(shù)+1（即上車次數(shù)四、問題分 距離，是指所乘坐的車的行駛距離、車外為了乘車而步行的距離 費用是指乘客完成從出發(fā)點到終點的乘車的所有費用 換乘次數(shù)是指完成一次出行的所換車的次數(shù)Dijkstra，F(xiàn)loyd，Bellman-Ford等算法，利用最短路徑的算法可以求出最優(yōu)解。多，我們應該采用Dijkstra做算法，這樣可以在避免空間的浪費。五、1.問題一的模型的建立和求(1)圖論模型的建化為圖中的邊權(quán)w。 算法一：經(jīng)典的Dijkstra算法對最短時間問題的求Dijkstra算法就可以解決這個問題。在構(gòu)建圖論模型時，所構(gòu)成的圖的邊集E={(i,i1)|i,i1Kj}S花費時間III乘車。，T最短路長的上界；P標號則是從起始頂點到這個頂點的最短路長，頂點vi標號記為d(vi)。Dijkstra的基本算法步驟 APd(A)=0。給頂點vi（vi

）T號d(vi=min{w（

）|

=（A，vi2.T標號中取最小值，假設(shè)viT標號且是最小的T標號。則把vi的T標號改為PT標號的其他各頂點的T標號：選頂點vj的Td(vj與d(vi+min{w（e）| e e=（i，j）}中較小者作 的新的T標號即設(shè)Pvj|vj具有P標號 具有T標號}=V-若d(vj=min{d

|vk則d(vj改記為頂點vj的P標號，于是把Tvj}vk的Tmin{dk，d(vjmin{w(ei)|ei(vj,vk)})顯然，這里只需要將與viTT3.2BP.d(B)AB的最1（考慮最短出行時間的出行路線(分L103-(3)算法二：求最少換乘次數(shù)的BFS算點之間都可以上車次數(shù)Y=1到達。所以我們可以重新構(gòu)圖，所構(gòu)圖如下：E={(ki,kj)|ki,kjKl}；w（ei）=1；BFS寬度優(yōu)先搜BFSDijkstraBFS算法中還有時間戳的標記t(vBFS A標P標號，d(A)=0,t(A)=0;給頂點vi（viA）t(vi標T標號d(vi 取所有Tvi是所有T標號中的時間戳最小的頂點。把vi頂點的T標號改為P標號. 重新計算其他具有Tvj(vivjE)d(vjd(vi

=f，f=f+1；若vjB這樣在算法結(jié)束是標號d(B)—1BFS22（考慮最少換乘次數(shù)的出行路線121121Dijkstra變種算法。 算法三：Dijkstra的變種算w(e,三元組，為最不重要因素。比如，為換乘次數(shù)，E={(ki,kj)|ki,kjKlw(ei其中I為兩站間乘坐ei路線所用時間，C為費用，在分段計費中應考慮到不構(gòu)圖是在模型二的基礎(chǔ)之上，但算法的實現(xiàn)有要在模型一的基礎(chǔ)上對Dijkstra算法進行修改。Dijkstra的就是對頂點不斷的更新標號和固定標號。Dijkstra只是對單一的因素起d(vj)=(',',')當''''時d(vid(vj有了比較三元組的規(guī)則，就可以對經(jīng)典的Dijkstra算法進行改進，只需要在不合理所以我們可以在算法中加入閥值三元組W（IF,CF,DF即d T標號頂點vi時如果新計算得到的d(vi>W放棄對vi樣的繁雜的圖系統(tǒng)來說，Dijkstra算法這樣的多項式算法顯得力不從心，有可能Dijkstra變種算法可以帶來新的希望，Dijkstra算法的優(yōu)化要利用到Dijkstra可以在近似線性時間內(nèi)完成最短路徑的計算[5]。通過實際的編Dijkstra5秒才能全部解出，Dijkstra0.4Dijkstra3表3- (分(元數(shù)32乘格32乘32間31格31間31表3- 耗車數(shù)路乘43格43乘32間32格32間32表3- 換乘次路323232313131表3- 耗車數(shù)路乘54格54乘21間21格21間21表3- 耗車數(shù)路乘43格43乘32間32格32間32表3- 換乘次路323221212121(5)算法四：求備選方案的K短路徑算KK短路徑就是在圖中找到由起始點到終點的第K短的路徑。KA**(x)。(x)FStra算法其實都可以看成是（x）0*K（x）0的估價函數(shù)顯然是不實際的，我們采用：H（vi）=dist（vi圖從BDijkstra運算得到。 問題二的模型的建立和求 由于公汽與地鐵之間的換乘時間不同，所以對換乘之間的關(guān)系要1圖1顯示了公汽換公汽，(3)根據(jù)圖1模型可點拆成多個點。比如對于中的頂點sisi，ssisisisi'sisi'' 具體換乘過程為公汽換公汽：5min=2minsisi)+3min(sisi地鐵換地鐵：4min=2min(DiDi)+3minDiDi公汽換地鐵：6min=步行2min(si2min(Di'Di

步行2min(si

等待地鐵換公汽：7min=步行2min(DiDi'步行2min(Disi'等待3min(si'si'' 通過圖的構(gòu)建之后利用問題一中的算法就可以求解各種需求的4注：線路中t表4- (分數(shù)乘74格74乘32間31格31間31表4- 耗車數(shù)路乘43格43乘32間32格32間32表4- 耗車數(shù)路乘63格63乘32間31格31間31表4- 耗車數(shù)路乘53格53乘21間21格21間21表4- 耗車數(shù)路乘63格63乘32間32格52間32表4- 換乘次路303021213030 問題三的模型的建立和求DijktraK 符號定義 S為站點集合；R為線路集合

線路r起點oK(ro)1

K(r,s2)K(r,s1)

表示rs1，s2

C0表示起始點，且Ci為轉(zhuǎn)乘的第i B(s1,s2)s1，s2s1Ss2S T(s1,s2)s1，s2s1Ss2S(2)(3)算法的介紹 假設(shè):當任意兩個轉(zhuǎn)乘點Ci與CjT(Ci,Cj)/B(Ci,Cj)

S1L(Ci,Cj)S

(S2 1.設(shè)查詢的起點為C0路徑的任意一條為

，終點站為Cn

A→C1C2路算法求解結(jié)果

B;（DijktraK2.2（A）描述轉(zhuǎn)乘點與轉(zhuǎn)乘點之間的優(yōu)化：3.2（B）描述轉(zhuǎn)乘點內(nèi)部站點與站點之間的優(yōu)化：使同一線的繞彎轉(zhuǎn)為步行，節(jié)省時間。對于每一個相鄰的轉(zhuǎn)乘點Ci與Ci1MMM,…,Mn，即K(r,Ci1)K(r,M) 則把轉(zhuǎn)乘點Ci與

2）中的起點站A把站點M

Mn2）A、B4.2（C）2（C）中起點為Cj,終點為Cj1，且線路不是一票制，此兩點之間的站點sum；40<sum<40+S2Cj1之前走（sum-40）Cj+120<sum<20+S2Cj1之前走（sum-20）Cj+1六、模型評價及改1）采用用了拆點的方法處理不同換乘時間合理的簡化了模型，減少了特2）Dijkstra的變種算法對多個因素綜合考慮，為查詢者提供3）A*K短路，為查詢者提供不同的解決4）1）Dijkstra變種算法對因素的綜合考慮仍較片面，設(shè)置閥值可能2）A*K短路算法生成的路徑會過于相似而沒有實際意義，并且K短路算法無法避免其效率較低的弱點。3）等車時間，相臨兩站的運行時間等都是隨量而現(xiàn)在只取平均值，4）此模型沒有結(jié)合城市系統(tǒng)網(wǎng)絡(luò)圖來分析，因而結(jié)論可能與實際有5）實際中每條線路的發(fā)車頻率并