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

一、問題重背從今年的1月1日至今，每天新增機(jī)動(dòng)車1060輛，現(xiàn)在已經(jīng)達(dá)到297萬輛。為緩解交通壓力，將優(yōu)先發(fā)展公共交通，加快軌道交通系統(tǒng)的建設(shè)，114公里軌道交通的基礎(chǔ)上，還將爭取新62004002015561公里。目前，20%2015承擔(dān)公共交通的出行比例的50%以上[1]345車每天將增加108個(gè)車次；從德勝門通往小區(qū)的344路快車每天增加915120車次；300564208532255另外，將開辟10條臨時(shí)專線。其中涉及：中心區(qū)4條、五棵平十三陵鐵人三項(xiàng)1條、工業(yè)大學(xué)體育館1條、朝陽公園沙灘排球館1條3200881公園賽艇、奧運(yùn)公園曲棍球比賽的觀眾服務(wù)。預(yù)計(jì)2008年8月8日開賽一天，35044516人次[3]問第29屆奧運(yùn)會(huì)明年8月將在舉行，屆時(shí)有大量觀眾到現(xiàn)場奧運(yùn)比賽其中大部分人將會(huì)乘坐公共交通工（簡稱包括公汽地鐵等出行。這些年來，城市的系統(tǒng)有了很大發(fā)展，市的線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也多條線路的選擇問題。針對(duì)市場需求，需要研制開發(fā)一個(gè)解決線路選擇問題的自主查詢計(jì)算6對(duì)起始站→終到站之(1)、(2)、(4)、(5)、2二、基本參數(shù)相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)：3相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)：2.5公汽換乘公汽平均耗時(shí) 5分鐘(其中步行時(shí)間2分鐘地鐵換乘地鐵平均耗時(shí) 4分鐘(其中步行時(shí)間2分鐘地鐵換乘公汽平均耗時(shí) 7分鐘(其中步行時(shí)間4分鐘公汽換乘地鐵平均耗時(shí) 6分鐘(其中步行時(shí)間4分鐘為：0～20站：1元；21～40站：2元；40站以上：3元地鐵票價(jià)：3元（無論地鐵線路間是否換乘三、基本假(1)忽略天氣的影響，道路不發(fā)生擁擠，人流不發(fā)生擁擠(2)相鄰公汽站、地鐵站行駛時(shí)間(包括停站時(shí)間)為常量(3)公汽、地鐵等換乘耗時(shí)為常量(4)起始點(diǎn)不需要步行，只需等車(5)公汽環(huán)形線路為雙向的，地鐵環(huán)形線路為單向的四、符號(hào)定L公汽系統(tǒng)的公汽路線集合；T地鐵系統(tǒng)的地鐵路線集合；S公汽系統(tǒng)站點(diǎn)的集合；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èi)用是指乘客完成從出發(fā)點(diǎn)到終點(diǎn)的乘車的所有費(fèi)用 換乘次數(shù)是指完成一次出行的所換車的次數(shù)Dijkstra，F(xiàn)loyd，Bellman-Ford等算法，利用最短路徑的算法可以求出最優(yōu)解。多，我們應(yīng)該采用Dijkstra做算法，這樣可以在避免空間的浪費(fèi)。五、1.問題一的模型的建立和求(1)圖論模型的建化為圖中的邊權(quán)w。 算法一：經(jīng)典的Dijkstra算法對(duì)最短時(shí)間問題的求Dijkstra算法就可以解決這個(gè)問題。在構(gòu)建圖論模型時(shí)，所構(gòu)成的圖的邊集E={(i,i1)|i,i1Kj}S花費(fèi)時(shí)間III乘車。，T最短路長的上界；P標(biāo)號(hào)則是從起始頂點(diǎn)到這個(gè)頂點(diǎn)的最短路長，頂點(diǎn)vi標(biāo)號(hào)記為d(vi)。Dijkstra的基本算法步驟 APd(A)=0。給頂點(diǎn)vi（vi

）T號(hào)d(vi=min{w（

）|

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

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

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

線路r起點(diǎn)oK(ro)1

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

表示rs1，s2

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

S1L(Ci,Cj)S

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

，終點(diǎn)站為Cn

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

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

2）中的起點(diǎn)站A把站點(diǎn)M

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