【正文】 45 46 2）2007年全國大學(xué)生數(shù)學(xué)建模競賽優(yōu)秀論文及承諾書“乘公交，看奧運(yùn)”公交最優(yōu)路線選擇摘要建立了北京公交線路選擇問題的優(yōu)化模型，該方案使人們在北京奧運(yùn)會期間，可以更方便快捷的觀看體育賽事。在滿足人們的各種不同需求的基礎(chǔ)上，依據(jù)時(shí)間短、費(fèi)用少和轉(zhuǎn)車少的原則,我們建立了線路選擇的查詢系統(tǒng)。首先按問題分為三種不同清況 ,然后在討論的基礎(chǔ)上，對模型作出了評價(jià)和改進(jìn),從而提供了一定數(shù)量的合理備選路徑供出行者根據(jù)自己的實(shí)際情況進(jìn)行選擇.關(guān)鍵詞：動態(tài)規(guī)劃 01規(guī)劃 有向圖 結(jié)點(diǎn) 篩選 最優(yōu)路線 問題提出：基本情況我國人民翹首企盼的第29屆奧運(yùn)會明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場觀看奧運(yùn)比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問題。針對市場需求，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)。 需要解決的問題為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。請你們解決如下問題：僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站→終到站之間的最佳路線（要有清晰的評價(jià)說明）。 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676同時(shí)考慮公汽與地鐵線路，解決以上問題。假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。相關(guān)信息（見附件）【附錄1】基本參數(shù)設(shè)定相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)： 3分鐘相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)： 公汽換乘公汽平均耗時(shí)： 5分鐘(其中步行時(shí)間2分鐘)地鐵換乘地鐵平均耗時(shí)： 4分鐘(其中步行時(shí)間2分鐘)地鐵換乘公汽平均耗時(shí)： 7分鐘(其中步行時(shí)間4分鐘)公汽換乘地鐵平均耗時(shí)： 6分鐘(其中步行時(shí)間4分鐘)公汽票價(jià)：分為單一票價(jià)與分段計(jì)價(jià)兩種，標(biāo)記于線路后；其中分段計(jì)價(jià)的票價(jià)為：0～20站：1元；21～40站：2元；40站以上：3元地鐵票價(jià)：3元（無論地鐵線路間是否換乘）注：以上參數(shù)均為簡化問題而作的假設(shè)，未必與實(shí)際數(shù)據(jù)完全吻合。【附錄2】公交線路及相關(guān)信息 （）問題分析。由于公交乘客出行路徑選擇心理的復(fù)雜性，往往單一的乘車路徑并不能滿足所有乘客的需要。例如，一些乘客希望選擇換乘次數(shù)最少的乘車路徑，而另外一些乘客則傾向于選擇出行距離更短的乘車路徑。即使是被出行者選中的路徑方案，在實(shí)際中也可能由于公交車輛滿載或道路交通擁擠而被放棄。因此，一個(gè)先進(jìn)、有效的公交乘客信息系統(tǒng)不能只為用戶提供單一的路線優(yōu)化方案，還應(yīng)提供一定數(shù)量的合理備選路徑供出行者根據(jù)自己的實(shí)際情況進(jìn)行選擇。乘客不一定要找最短，里面還涉及到換乘次數(shù)最少，費(fèi)用最少等問題,我們將距離附近的一切公交車站點(diǎn)抽象集合在一起，看成一個(gè)統(tǒng)一的地點(diǎn),并將這些獨(dú)立的包含各種公交車站點(diǎn)的地點(diǎn)，看成有向圖中間獨(dú)立的各個(gè)結(jié)點(diǎn)。于是，問題就變成，在一個(gè)擁有大量結(jié)點(diǎn)的有向圖中，如何求任意兩個(gè)點(diǎn)之間的最短距離的離散數(shù)學(xué)問題。由于本問題中，我們所要求得路徑應(yīng)該是精確的值，也就是說，我們希望得到是對所有可能窮盡后的最合適花費(fèi)最小的解,既優(yōu)化的解，所以我們提出一些對本問題的看法和算法方面的一些設(shè)計(jì)。 模型假設(shè)(1)為了方便我們假設(shè)在一個(gè)地點(diǎn)只有一個(gè)相同的站點(diǎn)，我們不考慮一個(gè)相同的地點(diǎn)前后幾米的位置有兩三個(gè)不同的站點(diǎn)的現(xiàn)象(2) 行駛同一條路線時(shí),人們換乘的那輛公交比人們步行所花時(shí)間要非常省事方便.(3) 所有交通工具均按平均速度行駛(題目中給出的平均速度),而且準(zhǔn)時(shí)到站(4) 假定乘客上車時(shí)不滿載(5)在公交線路上所有車輛總能正常通行，不考慮諸如堵車、交通事故等意外情況；(6)多個(gè)乘車方案時(shí)，有直達(dá)方案時(shí)優(yōu)先考慮，其次才考慮換乘方案。定義與符號說明S0 汽車的起始站點(diǎn)Sj 汽車第j個(gè)站點(diǎn),其中j=(1,2,…)K 乘客到達(dá)目的地要K次轉(zhuǎn)車K1 乘客坐單一票價(jià)列車的次數(shù)K2 乘客坐站數(shù)小于等于20站的列車次數(shù)K3 乘客坐站數(shù)大于20小于等于40站的列車的次數(shù)K4 乘客坐站數(shù)超過40的列車的次數(shù)L1 單一票價(jià)的價(jià)格L2 站數(shù)小于等于20站的列車的價(jià)格L3 站數(shù)大于20小于等于40站的列車的價(jià)格L4 站數(shù)超過40的列車的價(jià)格V1公交換地鐵的次數(shù)V2地鐵換公交的次數(shù)V3地鐵換地鐵的次數(shù)ti 站點(diǎn)Si1到Si步行的時(shí)間 人們對時(shí)間的偏好程度 ,人們對費(fèi)用的偏好程度,同時(shí)+=1.模型的建立從所要解決的問題和對問題所做的假設(shè)出發(fā),我們對公交線路的最優(yōu)選擇模型建立了如下三個(gè)模型 : 模型一:不考慮交通方式間的轉(zhuǎn)換, 僅考慮公汽線路在建立模型時(shí)我們將乘客起程站點(diǎn)設(shè)為S0,(假使乘客從出發(fā)點(diǎn)到目的地的最優(yōu)選擇路線需要轉(zhuǎn)K次車),我們將乘客每次轉(zhuǎn)車的站點(diǎn)都記下標(biāo)號,按轉(zhuǎn)車時(shí)間先后依次設(shè)為S1 S2,…..Sk 那么到達(dá)目的地為 SK+1:設(shè)Aj表示乘客從站點(diǎn)Sj1到Sj經(jīng)過的站數(shù)(j=k+1),則得到總站數(shù)S=所花時(shí)間T1= 3*S+ 5*K:乘客坐各種公交車等于轉(zhuǎn)車的次數(shù)加一即: =K+1那么乘客到達(dá)目的地需要的費(fèi)用(M)為： M1=則乘客所選擇的最優(yōu)路線應(yīng)滿足下面的模型: Min1=*T1+*M1.模型二: 同時(shí)考慮公汽與地鐵線路,不考慮其他交通方式 應(yīng)用01規(guī)劃：我們設(shè) : 設(shè)Bj表示乘客從地鐵Tj1到Tj經(jīng)過的站數(shù)(j=V3),時(shí)間T2= 2當(dāng)查詢者從節(jié)約費(fèi)用上考慮時(shí):乘客坐各種公交車等于轉(zhuǎn)車的次數(shù)加上地鐵轉(zhuǎn)公交車的次數(shù)即： =K+1+V2 乘客到達(dá)目的地需要的費(fèi)用(M) M2=+3*i則乘客所選擇的最優(yōu)路線應(yīng)滿足下面的模型: Min2=*T2+*M2前提三: 已知所有站點(diǎn)之間的步行時(shí)間,將公汽、地鐵和步行同時(shí)考慮,其他忽略.:T3=+2當(dāng)查詢者從節(jié)約費(fèi)用上考慮時(shí): M3=+3*i則乘客所選擇的最優(yōu)路線應(yīng)滿足下面的模型:Min3=*T3+*M3模型的求解在模型中我們將經(jīng)過S0和Sk+1站點(diǎn)所經(jīng)過的公交車篩選出來記:Li(S0)和Lj(Sk+1)(i=1,2…….)(j=1,2…….)分別表示經(jīng)過S0站和SK+1的所有公交車，在滿足模型約束條件下，尋找Li(S0)=Lj(Sk+1)是否存在？如果不存在，將Li(S0)經(jīng)過的第二個(gè)站點(diǎn)，記為S1，尋找Li(S1)=Lj(Sk+1)是否存在，依據(jù)類推我們可以得到多種路線選擇，利用窮舉算法，找到最優(yōu)路線，具體算法如下：// 乘車方案 include include /* 成坐公共汽車時(shí)的換車問題。例如從站A到Z要坐幾路車，換幾次，在哪里換車，這些問題如何解決。 define L // 車次數(shù) L=520 // 車次?？空玖斜? char *Station[L] = { abc…k, // 第i次車 I小于等于m // 已經(jīng)乘著過的車次列表，對應(yīng)t [i]=0表示還未乘著，＝1表示已經(jīng)乘著過 int t [L]={0,0…0}。 // 換車的下車點(diǎn) struct Exchange { static int h。 // 長度length int r。 // 車次route char poi。 // 換車站點(diǎn)point } Path[L]。 // 換車路徑path int Exchange::h = 0。 // 初始化路徑長度 bool PassBy(char P, char* path) // 看路徑path的車是否經(jīng)過點(diǎn)P { while(*path!=39。\039。) if( P==*(path++) ) return true。 return false。 } void print_path() { static int t = 0。 printf(%04d,++t)。 for(int i=0。iPath[0].h1。i++) printf( (%2d: %c) ,Path[i].r+1,Path[i].poi)。 printf( (%2d: %c) ,Path[i].r+1,Path[i].poi)。 printf(\n)。 } void NextSearchPath(char end,int r) // 遞歸尋找路徑 { if( taked[r]!=0 ) return。 // have been taked。 if( PassBy(end,Station[r]) ) { Path[Path[0].L].poi = end。 Path[Path[0].L].r = route。 Path[0].h++。 print_path()。 Path[0].h。 return。 } taked[r] = 1。 //have been taked。 Path[Path[0].L].r = route。 for(int i=0。istrlen(Station[r])。i++) { char nowPoi = Station[r][i]。 if( nowPoi==Path[Path[0].h1].poi ) continue。 for( int j=0。 jl。 j++) if( PassBy(nowPoi,Station[j]) ) { Path[Path[0].L].poi = nowPoi。 Path[0]h++。 NextSearchPath(end,j)。 Path[0].h。 } } taked[r] = 0。 //have been taked。 } void SearchPath(char sta