奧運(yùn)路徑——數(shù)學(xué)建模

1、2010高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽承 諾 書(shū)我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。 我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫(xiě)）： B 我們的參賽報(bào)名號(hào)為（

2、如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚?xiě)完整的全名）： 參賽隊(duì)員 (打印并簽名) ：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期： 2010 年 9 月 6 日11 / 13文檔可自由編輯打印賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：論文題目摘要隨著城市交通系統(tǒng)的日益發(fā)達(dá)，線路的選擇問(wèn)題也日益嚴(yán)重。本文通過(guò)對(duì)北京交通路線的分析，并從實(shí)際情況出發(fā)考慮，建立了滿足查詢者各種不同需求的最佳路線的查詢模型，并用程序加以實(shí)現(xiàn)。問(wèn)題一是在只考慮公汽路線時(shí)，考慮到查詢者的各種不同需求建立了五個(gè)模型，分別為最短路徑模型、最短時(shí)間路徑模型、最少換乘路徑模型、最省錢(qián)路徑模型以及滿意度

3、最高路徑選擇模型。其中，滿意度最高的路徑模型是通過(guò)層次分析法，給出路徑長(zhǎng)度，時(shí)間，錢(qián)數(shù)，換乘數(shù)這四個(gè)因素對(duì)應(yīng)的權(quán)重，通過(guò)加權(quán)法計(jì)算各個(gè)可行路徑的評(píng)價(jià)值，已給出最佳路徑。問(wèn)題二是在問(wèn)題一的基礎(chǔ)上，增加了地鐵路線。修改了問(wèn)題一的五個(gè)模型，實(shí)現(xiàn)更方便、準(zhǔn)確的搜索。問(wèn)題三在前兩問(wèn)的基礎(chǔ)上考慮站點(diǎn)間的步行，修改問(wèn)題二中的模型。使模型更符合現(xiàn)實(shí)。摘要中應(yīng)特別注意的是：應(yīng)以第三人稱寫(xiě)作.摘要是完整的短文,具有獨(dú)立性,可以單獨(dú)使用.即使不看論文全文的內(nèi)容,仍然可以理解論文的主要內(nèi)容,作者的新觀點(diǎn)和想法以及論文所要實(shí)現(xiàn)的目的,采取的方法,研究的結(jié)果與結(jié)論.(摘要中不能出現(xiàn)“我”、“我們”等表示第一人稱的詞語(yǔ))關(guān)

4、鍵詞：Dijkstra算法；層次分析法；加權(quán)法1 問(wèn)題重述隨著交通系統(tǒng)的快速發(fā)展，交通路線的選擇問(wèn)題已成為人們關(guān)注的焦點(diǎn)。例如第29屆奧運(yùn)會(huì)在北京舉行期間，有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人都選擇乘坐公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）出行。這些年來(lái)，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問(wèn)題。要求針對(duì)市場(chǎng)需求，從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求，開(kāi)發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)。根據(jù)已給數(shù)據(jù)解決一下三個(gè)問(wèn)題。1.1 問(wèn)題一僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的

5、一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對(duì)起始站終到站之間的最佳路線（要有清晰的評(píng)價(jià)說(shuō)明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4) 、S0008S0073 (5)、S0148S0485 (6)、S0087S36761.2 問(wèn)題二要求同時(shí)考慮公汽與地鐵線路，解決問(wèn)題一所述的問(wèn)題。1.3 問(wèn)題三假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問(wèn)題的數(shù)學(xué)模型。2 問(wèn)題分析2.1 查詢需求分析分析查詢者的需求可將問(wèn)題分為以下五種情況建立模型，分別為最短路徑模型、最短時(shí)間路徑模型、最少換乘路徑模型、最省

6、錢(qián)路徑模型以及滿意度最高路徑選擇模型，即用戶可能要查詢路徑最短的，時(shí)間最短的，換乘最少的，最省錢(qián)的，以及綜合四個(gè)因素而成的最滿意的路徑。因此三個(gè)問(wèn)題都分為以上五種建立模型。3 模型假設(shè)(1) 假設(shè)站點(diǎn)之間的距離相等。(2) 假設(shè)不考慮交通堵塞和其他延誤車輛速度的問(wèn)題。(3) 假設(shè)相鄰公汽站平均行駛時(shí)間為3分鐘(包括停車時(shí)間)。(4) 假設(shè)相鄰地鐵站平均行駛時(shí)間為2.5分鐘(包括停站時(shí)間)。(5) 假設(shè)公汽換乘公汽平均耗時(shí)為5分鐘(其中步行時(shí)間2分鐘)。(6) 假設(shè)地鐵換乘地鐵平均耗時(shí)為4分鐘(其中步行時(shí)間2分鐘)。(7) 假設(shè)地鐵換乘公汽平均耗時(shí)為7分鐘(其中步行時(shí)間4分鐘)。(8) 假設(shè)公汽

7、換乘地鐵平均耗時(shí)為6分鐘(其中步行時(shí)間4分鐘)。(9) 假設(shè)同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過(guò)地鐵站換乘(無(wú)需支付地鐵費(fèi))。(10) 公汽票價(jià)分為兩種，單一票價(jià)和分段計(jì)價(jià)兩種，單一票價(jià)為1元，分段計(jì)價(jià)為020站：1元；2140站：2元；40站以上：3元。(11) 地鐵票價(jià)為3元(無(wú)論地鐵線路之間是否換乘)。4 符號(hào)說(shuō)明：查詢者要查詢的起點(diǎn)。： 查詢者要查詢的終點(diǎn)。：路線所經(jīng)過(guò)點(diǎn)的集合。： 第種交通路線乘坐公汽需要經(jīng)過(guò)的所有站點(diǎn)個(gè)數(shù)。： 第種交通路線中乘坐線路的公汽需要經(jīng)過(guò)的站數(shù)。： 第種路線需要乘坐地鐵所要經(jīng)過(guò)的站數(shù)。： 第種路線所需時(shí)間。：第種路線所需花費(fèi)的錢(qián)數(shù)。： 第種路線中乘坐公

8、交中為單一票制1元的個(gè)數(shù)。：第種路線中乘坐地鐵的次數(shù)。：第種路線需要公汽換乘公汽的次數(shù)。：第種路線需要地鐵換乘地鐵的次數(shù)。：第種路線需要地鐵換乘公汽的次數(shù)。：第種路線需要公汽換乘地鐵的次數(shù)。： 相鄰公汽站平均行駛時(shí)間。： 相鄰地鐵站平均行駛時(shí)間。： 公汽換乘公汽平均耗時(shí)。： 地鐵換乘地鐵平均耗時(shí)。： 地鐵換乘公汽平均耗時(shí)。： 公汽換乘地鐵平均耗時(shí)。：站點(diǎn)到站點(diǎn)需要的步行時(shí)間。模型建立與求解4.1 問(wèn)題一在只考慮公汽的情況下，根據(jù)用戶的不同需求建立以下五種路徑選擇模型。由于換乘次數(shù)太多是很不合理的，最大的忍耐程度是有限的，假設(shè)最大的忍耐度為2，即最多換乘兩次。可畫(huà)出如下的示意圖，其中=0，1，2

9、。圖1. 換乘圖如圖1所示的換乘方式，為直達(dá)路徑；，公交路線為有一條交點(diǎn)的路徑，即需換乘一次的路徑；、公交路線為有兩個(gè)交點(diǎn)的路徑，即需要換乘兩次到達(dá)目的地的路徑。直達(dá)路徑的求法：對(duì)于線路，滿足，(1)則為站點(diǎn)到站點(diǎn)的直達(dá)路徑。換乘一次的路徑求法：線路，滿足，(2)則、為站點(diǎn)到站點(diǎn)的換乘一次的需要乘坐的路線。換乘兩次的路徑求法：線路，滿足，(3)則、為站點(diǎn)到站點(diǎn)的換乘兩次需要乘坐的路線。查找到以上三種可行路徑，再用以下的方法查找出滿足查詢者的各種不同需求的最佳路線。4.1.1 最短路徑模型由于假設(shè)各站之間的距離相等，因此最短路徑也就是經(jīng)站點(diǎn)最少的路徑。首利用程序查出所有由起點(diǎn)到終點(diǎn)可行路線，并通

10、過(guò)記錄每條路徑所經(jīng)過(guò)的站點(diǎn)數(shù)。因此只需求滿足的路線。4.1.2 最短時(shí)間路徑模型最短時(shí)間路徑，即查找由起點(diǎn)到終點(diǎn)的耗時(shí)最少的路徑。首利用程序查出所有由起點(diǎn)到終點(diǎn)可行路線，由于路徑所耗時(shí)間包括乘車時(shí)間以及換乘所用時(shí)間，因此需記錄每條路徑所經(jīng)過(guò)的站點(diǎn)數(shù)以及該路徑所需換乘次數(shù)。因此只需求滿足的路線，其中。 (4)4.1.3 最少換乘路徑模型查找最少換乘路徑，首先利用程序查出所有由起點(diǎn)到終點(diǎn)可行路線，并記錄每條路徑所需換乘次數(shù)，因此只需求滿足的路線。4.1.4 最省錢(qián)路徑模型由于公汽的收費(fèi)分為兩種，一種是通價(jià)票1元，另一種是分段計(jì)價(jià)的票價(jià)為：020站：1元；2140站：2元；40站以上：3元，所以要分

11、別記錄該路徑上乘坐這兩種車的次數(shù)。查找最省錢(qián)路徑，首先利用程序查出所有由起點(diǎn)到終點(diǎn)換乘在2次以下的可行路線，每條路徑所需換乘次數(shù)，以及其中是通價(jià)1元的車輛次數(shù)和非通價(jià)1元的路線需要經(jīng)過(guò)的站數(shù)。 (5)因此，查找最省錢(qián)路徑只需找滿足式(5)的路徑。4.1.5 滿意度最高路徑選擇模型綜合以上四個(gè)因素，利用層次分析法可建立滿意度最高路徑。圖2. 層次模型圖建立路徑滿意程度的判斷矩陣。 (6)矩陣通過(guò)歸一化處理, (7)對(duì)式(4)中各行元素取平均可得到。 (8)矩陣的特征向量式(5)的規(guī)一化處理后得到 ， (9)。 (10)帶入式(10)對(duì)矩陣的一致性檢驗(yàn)，通過(guò)一致性檢驗(yàn)，認(rèn)為判斷矩陣的一致性是可以接

12、受的，因此得出表1權(quán)重表。準(zhǔn)則層權(quán)重0.2710.3420.284 0.103 表1. 最終的權(quán)重表因此根據(jù)表1權(quán)重的大小，可以列出下式。 (11)首先對(duì)數(shù)據(jù)無(wú)量綱化處理，再根據(jù)式(11)求出各個(gè)路線的評(píng)價(jià)值，值最小的即為滿意度最高的路徑。4.2 問(wèn)題二將地鐵線路考慮到模型中，根據(jù)假設(shè)(9)可以將地鐵路線轉(zhuǎn)化為公汽路線。4.2.1 最短路徑模型由于假設(shè)各站之間的距離相等，因此最短路徑也就是經(jīng)站點(diǎn)最少的路徑。首利用程序查出所有由起點(diǎn)到終點(diǎn)可行路線，并通過(guò)記錄每條路徑所經(jīng)過(guò)的站點(diǎn)數(shù)。因此只需求滿足的路線。4.2.2 最短時(shí)間路徑模型添加地鐵路線后，由于地鐵的站點(diǎn)間的乘車時(shí)間、換乘時(shí)間與公汽不同，因

13、此要單獨(dú)計(jì)算。最短時(shí)間路徑，即查找由起點(diǎn)到終點(diǎn)的耗時(shí)最少的路徑。首利用程序查出所有由起點(diǎn)到終點(diǎn)可行路線，并記錄每條路徑所經(jīng)過(guò)的站點(diǎn)數(shù)以及該路徑所需換乘次數(shù)、。因此只需求滿足的路線，其中。 (12)4.2.3 最少換乘路徑模型查找最少換乘路徑，首先利用程序查出所有由起點(diǎn)到終點(diǎn)可行路線，并記錄每條路徑上四種換乘方式對(duì)應(yīng)的次數(shù)、 ，有。(13)滿足式(13)的路徑即為換乘最少即可到到目的地的路徑。4.2.4 最省錢(qián)路徑模型查找最省錢(qián)路徑，首先利用程序查出所有由起點(diǎn)到終點(diǎn)可行路線，每條路徑所需換乘次數(shù)，以及其中是通價(jià)1元的車輛次數(shù)，第種交通路線中乘坐線路的公汽需要經(jīng)過(guò)的站數(shù)，第種交通路線中乘坐地鐵的次

14、數(shù)。 (14)因此，查找最省錢(qián)路徑只需找滿足式(14)的路徑。4.2.5 滿意度最高路徑選擇模型根據(jù)表1權(quán)重的大小，可以列出下式。 (15)首先對(duì)數(shù)據(jù)無(wú)量綱化處理，再根據(jù)式(15)求出各個(gè)路線的評(píng)價(jià)值，值最小的即為滿意度最高的路徑。4.3 問(wèn)題三由于考慮到站點(diǎn)之間都可用步行的方式到達(dá)，而步行是要消耗時(shí)間而不需要費(fèi)用的，因此最省錢(qián)的模型沒(méi)有意義，改成只剩下四個(gè)模型?；ㄙM(fèi)的費(fèi)用依然是。 (16)4.3.1 最短路徑模型由于假設(shè)各站之間的距離相等，因此最短路徑也就是經(jīng)站點(diǎn)最少的路徑。首利用程序查出所有由起點(diǎn)到終點(diǎn)可行路線，并通過(guò)記錄每條路徑所經(jīng)過(guò)的站點(diǎn)數(shù)。因此只需求滿足的路線。4.3.2 最短時(shí)間路

15、徑模型最短時(shí)間路徑，即查找由起點(diǎn)到終點(diǎn)的耗時(shí)最少的路徑。首利用程序查出所有由起點(diǎn)到終點(diǎn)可行路線，并通過(guò)記錄每條路徑所經(jīng)過(guò)的站點(diǎn)數(shù)以及該路徑所需換乘次數(shù)。因此只需求滿足的路線，其中。 (17)4.3.3 最少換乘路徑模型查找最少換乘路徑，首先利用程序查出所有由起點(diǎn)到終點(diǎn)可行路線，并記錄每條路徑上四種換乘方式對(duì)應(yīng)的次數(shù)、 ，有。(18)滿足式(18)的路徑即為換乘最少即可到到目的地的路徑。4.3.4 最省錢(qián)路徑模型由于考慮到站點(diǎn)之間都可用步行的方式到達(dá)，而步行是要消耗時(shí)間而不需要費(fèi)用?？紤]到走的站數(shù)越多費(fèi)用越少，但步行的站點(diǎn)過(guò)多是不合理的，因此限制步行的站數(shù)不能多于4站。查找最省錢(qián)路徑，首先利用程序查出所有由起點(diǎn)到終點(diǎn)可行路線，每條路徑所需換乘次數(shù)，以及其中是通價(jià)1元的車輛次數(shù)，第種交通路線中乘坐線路的公汽需要經(jīng)過(guò)的站數(shù)，第種交通路線中乘坐地鐵的次數(shù)。 (19)因此，查找最省錢(qián)路徑只需找滿足式(14)的路徑。4.3.5 滿意度最高路徑選擇模型根據(jù)表1權(quán)重的大小，可以列出下式。 (20)首先對(duì)數(shù)據(jù)無(wú)量綱化處理，再根據(jù)式(20)求出各個(gè)路線的評(píng)價(jià)值，值最小的即為滿意度最高的路徑。5 模型實(shí)現(xiàn)6 模型評(píng)價(jià)與分析6.1鼠標(biāo)左鍵單擊該段落，輸入替換之。內(nèi)容為小