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