2007高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽

PAGE2007高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽承諾書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則．我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題．我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的,如果引用別人的成果或其他公開的資料（包括網(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)填寫）：A 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）：200711605所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜┗幢泵禾繋煼秾W(xué)院參賽隊(duì)員(打印并簽名)：1．丁敏敏2．王麗3．趙亞剛指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人(打印并簽名)：日期：2007年09賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2007高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽編號(hào)專用頁賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國前編號(hào)）：全國評(píng)閱編號(hào)（由全國組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：PAGE2公交車乘車線路選擇的模型摘要本文針對(duì)最優(yōu)公交車乘車線路選擇的實(shí)際問題,在合理假設(shè)的條件下通過分析,對(duì)三種不同條件下的問題提出不同方案,運(yùn)用站點(diǎn)元素標(biāo)記法和MATLAB編程建立模型,選出最優(yōu)路徑.問題一中只需要考慮公汽之間的換乘,我們采用站點(diǎn)元素標(biāo)記法給分別含有起點(diǎn)站和終點(diǎn)站的線路上所有站點(diǎn)進(jìn)行紅綠色標(biāo)記,再根據(jù)時(shí)間和費(fèi)用的權(quán)重選擇最優(yōu)路徑.問題二中,由于加入了地鐵與公汽換乘情況,我們利用問題一求出的最優(yōu)路徑,在此路徑上的公汽站點(diǎn)構(gòu)成的集合與地鐵站點(diǎn)構(gòu)成的集合求交集,則交集為可能實(shí)現(xiàn)換乘的站點(diǎn),然后考慮換乘后的結(jié)果,進(jìn)行比較得出更優(yōu)路徑.問題三中,對(duì)問題二中的模型條件進(jìn)行了更為具體的要求（增加步行時(shí)間）,步行這個(gè)條件把地鐵和公汽連接了起來,產(chǎn)生了相關(guān)站點(diǎn),這樣使得滿足條件的路徑增加了,有利于更優(yōu)路徑的產(chǎn)生.文章最后對(duì)本文建立的模型進(jìn)行了評(píng)價(jià).該模型能在一定程度上解決公交線路選取的最優(yōu)問題.關(guān)鍵詞:最優(yōu)路徑元素標(biāo)記法Matlab加權(quán)

一問題重述我國人民翹首企盼的第29屆奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，由于考慮到實(shí)際情況的影響(私家車和出租車可能引起交通過度擁擠)其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）出行．這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問題．針對(duì)市場(chǎng)需求，我們準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)．為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是設(shè)計(jì)線路選擇的模型與算法，我們從實(shí)際情況考慮，滿足查詢者的各種不同需求．通過建立模型解決如下問題：針對(duì)問題1我們僅考慮公汽線路，解決給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法．并根據(jù)附錄數(shù)據(jù)，利用所建立的模型與算法，求出(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36766對(duì)起始站→終到站之間的最佳路線．針對(duì)問題2同時(shí)考慮公汽與地鐵線路，通過建立模型解決以上問題．針對(duì)問題3假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，建立任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型．二問題分析期待已久的奧運(yùn)會(huì)將于2008年在首都北京舉行，屆時(shí)北京的交通系統(tǒng)將會(huì)進(jìn)入非常繁忙的階段，本題就是以北京城市的公汽交通為背景，針對(duì)不同的乘車條件選擇最優(yōu)的乘車路線．在問題1中任意給出的一對(duì)公汽起點(diǎn)站和終點(diǎn)站中，我們分別在含有起點(diǎn)站和終點(diǎn)站的公交線路中所有的站點(diǎn)進(jìn)行標(biāo)記，利用站點(diǎn)元素標(biāo)記法，找出符合條件的線路，再根據(jù)時(shí)間和乘車費(fèi)用的權(quán)重選擇最優(yōu)路徑．在問題2中針對(duì)題目要求公汽和地鐵同時(shí)考慮的情況，我們利用了第一個(gè)問題中的最佳路線，通過公汽與地鐵的換乘，使到達(dá)目的站路線更優(yōu)，我們采用換乘次數(shù)或乘車時(shí)間最少原則，找出符合條件的換乘站點(diǎn)，然后根據(jù)各方面具體情況比較即可得到更優(yōu)化路線．在問題三中我們?cè)诰C合考慮其它條件的同時(shí)，再加上各站點(diǎn)間步行時(shí)間的因素解決地鐵與公汽的線路選擇問題，通過模型的分析與比較，我們從中可以得出更佳的線路．三模型的符號(hào)說明與假設(shè)(一)符號(hào)說明(1)L+三位數(shù)字表示公汽線路編號(hào)(2)S+四位數(shù)字表示公汽站點(diǎn)編號(hào)(3)T1，T2表示地鐵線路編號(hào)(4)D+兩位數(shù)字表示地鐵站點(diǎn)編號(hào)(5)分別表示乘客所選線路的起點(diǎn)站和終點(diǎn)站，=1,2,…(6)表示經(jīng)過的任意一條線路,=1,2,…(7)表示經(jīng)過任意一條線路，=1,2,…(8)表示含有起點(diǎn)站的第條線路上的第個(gè)站點(diǎn)(9)表示含有終點(diǎn)站的第條線路上的第個(gè)站點(diǎn)(二)模型假設(shè)(1)假設(shè)相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)：3分鐘相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)：2.5分鐘公汽換乘公汽平均耗時(shí)：5分鐘(其中步行時(shí)間2分鐘)地鐵換乘地鐵平均耗時(shí)：4分鐘(其中步行時(shí)間2分鐘)地鐵換乘公汽平均耗時(shí)：7分鐘(其中步行時(shí)間4分鐘)公汽換乘地鐵平均耗時(shí)：6分鐘(其中步行時(shí)間4分鐘)(2)假設(shè)同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過地鐵換乘并且無需支付地鐵費(fèi)．(3)假設(shè)公交車行駛不存在通行不暢問題，如紅綠燈，交通堵塞等，并且公交車是勻速行駛，在任意一個(gè)車站的停靠時(shí)間相同．(4)假設(shè)任意相鄰兩站點(diǎn)之間的距離為常數(shù)．(5)不考慮乘客個(gè)人的喜愛偏好．(6)權(quán)重的數(shù)學(xué)公式為：0.3*(沒有換乘的)站數(shù)+0.5*(換乘的)次數(shù)+0.7*乘車次數(shù)四模型準(zhǔn)備(1)最優(yōu)乘車線路的存在性每個(gè)城市的公交線路都構(gòu)成一個(gè)連通網(wǎng)，網(wǎng)中任意兩個(gè)結(jié)點(diǎn)（即兩個(gè)車站）經(jīng)過有限次換乘后，一定能從一個(gè)站點(diǎn)到達(dá)另一個(gè)站點(diǎn)，所以任意兩站點(diǎn)之間至少有一條線路，但求最優(yōu)線路我們首先給出最優(yōu)線路的定義：1)時(shí)間盡可能短；2)所需費(fèi)用盡可能少．由定義我們可以看出，乘客換乘次數(shù)越少，花費(fèi)的時(shí)間會(huì)越少，所需交通費(fèi)也越少．并且，該問題的最優(yōu)解可能不止一個(gè)，比如有很多條線路都經(jīng)過交通要道，我們只選取其中的一條路徑．(2)站點(diǎn)元素標(biāo)記法化學(xué)中我們?cè)褂猛凰貥?biāo)記法來觀測(cè)不同元素在生物生長過程中的留存情況，它的優(yōu)點(diǎn)是標(biāo)記后，這一種元素在生物體內(nèi)的不同位置都可以很快的找出來，受到同位素的啟發(fā)，我們建立了一種求解方案——站點(diǎn)元素標(biāo)記法，把包含起點(diǎn)站的某一條線路上的站點(diǎn)在所有公交線路上用一種顏色標(biāo)記出來，把包含終點(diǎn)站的某一條線路上的站點(diǎn)用另一種顏色表示出來，如果兩種顏色相關(guān)，則出現(xiàn)一條線路，這樣能找出很多線路，在這些線路中擇優(yōu)．(3)站點(diǎn)相關(guān)性如果用表示相關(guān)性，兩個(gè)不同的站點(diǎn)出現(xiàn)在同一條線路上，則=1，如果不在同一線路上，則=0．五模型的建立與求解問題一：假設(shè)起始站點(diǎn)為，終點(diǎn)站是，那么求乘車的最短路徑，我們可以從出發(fā)，以公交線路為基礎(chǔ)進(jìn)行廣度搜索，直到找到站點(diǎn)，建立模型如下：假設(shè)乘車路線為，i,j=1,2,…,(1)看是否存在的某一站，使得=，則表明只要乘線路上的公交車即可直接到達(dá)終點(diǎn)，此時(shí)乘車路線為，此即無需換乘情形；如果這種情形不存在，則繼續(xù)下面的步驟；(2)既然沒有直達(dá)的公交車，那么我們首先考慮一次換乘，搜索集合和,如果有，則至少有存在，則說明乘客只需乘兩次車，即換乘一次即可達(dá)到目的地，此時(shí)乘車路線為；(3)如果(2)也不能解決問題，則說明乘客至少需乘車3次，即換乘2次，此時(shí)我們需要找到含有和的線路，乘車路線為；(4)如果前面的這些操作仍然找不到符合條件的乘車線路，那我們就按照前面的思路逐層向下推理，直到找到符合條件的為止．具體求解步驟如下：如果不能直接從線路中看出符合條件的乘車路線，則應(yīng)用如下的站點(diǎn)元素標(biāo)記法：(1)選擇一條，將它上面所有的站點(diǎn)標(biāo)記成綠色，則所有公交線路中出現(xiàn)的站點(diǎn)均為綠色，現(xiàn)在將終點(diǎn)標(biāo)志成紅色，若出現(xiàn)紅色和綠色相關(guān)，則該線路為行車路線，此時(shí)乘客需要乘2次車，即為換乘1次，如下圖1：圖1(2)如果(1)不可行，則繼續(xù)把任選的線路上面的所有的站點(diǎn)標(biāo)記成紅色，則所有同時(shí)出現(xiàn)紅色和綠色的線路即為行車路線．這說明乘客需要乘車3次，即換乘2次，如下圖2：圖2這個(gè)方法非常獨(dú)特，最優(yōu)解的直觀視覺效果也好，但是這種窮舉法效率非常低，而且遺漏的可能性很大，我們可以通過MATLAB程序?qū)崿F(xiàn)，見附錄．在實(shí)際生活中，一般認(rèn)為，乘車三次即可達(dá)到目的地，也就是說，第四步基本上不用搜索，如果三次還不能到達(dá)目的地，說明這個(gè)城市的公交系統(tǒng)很可能存在問題，國家公交管理部門應(yīng)該考慮調(diào)整或增加公交車線路．(a)通過對(duì)圖3的路徑和權(quán)重比較得到最佳路線為：圖3L436下行S3359-S2026-S1132-S2266-S2263-S3917-S2303-S2301-S3233-S0618-S0616-S2112-S2110-S2153-S2814-S2813-S3501-S3515-S3500-S0756-S0492-S0903-S1768-S0955-S0480-S2703-S2800-S2192-S2191-S1829-S3649-S1784（換乘L167或L217）-1828(b)通過對(duì)圖4的路徑和權(quán)重比較得出最佳路線為：圖4L084下行S1557-S3158-S2628-S3408-S2044-S1985-S2563-S2682-S0028-S0029-S0055-S0051-S1919-S3389（換乘L206）-S3389-S0497-S0541-S0153-S3726-S1426-S1427-(換L447)-S0630-S0854-S0400-S2633-S0410-S0143-S2684-S2686-S2649-S2651-S3013-S1808-S1173-S0910-S3517-S0453-S2424-S1174-S0902-S0903-S2101-S0481(c)通過對(duì)圖5的路徑和權(quán)重比較得出最佳路線為：圖5L013下行S0971-S3832-S3341-S2237-S3565-S3333-S1180-S3494-S1523-S1520-S1988-S1743-S1742-S1181-S1879-S3405-S2517-S3117-S2954-S0531-S2184-S2182-S0992-S2324-S2322-S1770-S1789-S2119（轉(zhuǎn)乘L395）-S2116-S3544-S3186-S3409-S2716-S2820-S2783-S0520-S3829-S1893-S1555-S0297-S0271-S0464-S0964-S3189-S2810-S2385-S0485(d)通過對(duì)圖6的路徑和權(quán)重比較得出最佳路線為：圖6L159下行S0008-S3412-S2743-S3586-S2544-S0913-S2953-S3874-S0630-S0854-S0400-S2633-S3053-S0408-S0145-S3138-S2684-S2683-S0291-S3614-S0491-S2559-S0991-S3315(換乘L058)-S3898-S1855-S0073(e)通過對(duì)圖7的路徑和權(quán)重比較得出最佳路線為：圖7L308下行S0148-S0462-S0361-S1797-S2221-S0302-S2222-（換乘L348）-S3836-S0566-S2826-S0438-S0431-S0394-S0350-S1978-S0386(f)通過對(duì)圖8的路徑和權(quán)重比較得出最佳路線為：圖8L231下行S0087-S0857-S0965-S1427(換乘L381)-S1426-S0153-S0539-S2978-S0668-S3648-S1895-S0577-S0582-S0427（換乘L097）-3676問題二：同時(shí)考慮公汽與地鐵線路，我們的解答過程如下：在問題一中求解出的最佳路線模型的基礎(chǔ)上，我們把其中任意一條最佳路線上的所有站點(diǎn)作為一個(gè)集合，這里我們把這類集合記為．然后把所有與地鐵、相連的公汽站點(diǎn)記為集合，通過找與的交集，交集即為地鐵和公汽的公共站點(diǎn)（即乘客在此處有可能實(shí)現(xiàn)公汽和地鐵的換乘），從而達(dá)到路線的再次優(yōu)化．針對(duì)以上思考方案我們對(duì)問題一中的六種情況進(jìn)行了分析與求解，發(fā)現(xiàn)只有第2、6兩種情況實(shí)現(xiàn)了模型的再次優(yōu)化而其它四種情況下模型均不能達(dá)到再次優(yōu)化．(1)因?yàn)?，通過與問題一中的最佳路線比較：由于地鐵的費(fèi)用是只要上車就需要3元，而在乘公汽時(shí)S0618和S0616之間只有一站轉(zhuǎn)乘不僅帶來了麻煩而且乘車總費(fèi)用增加，所以不能實(shí)現(xiàn)線路的再次優(yōu)化．(2)由于通過求交集，地鐵與公汽交點(diǎn)站上我們認(rèn)為：只要滿足兩種交通工具換乘過程時(shí)間和交通費(fèi)用減少就能達(dá)到目標(biāo)，但在問題一中我們所找出的最佳路線為：S1557-S3158-S2628-S3408-S2044-S1985-S2563-S2682-S0028-S0029-S0055-S0051-S1919-S3389（換乘L206）-S3389-S0497-S0541-S0153-S3726-S1426-S1427(換乘L447)-S0630-S0854-S0400-S2633-S0410-S0143-S2684-S2686-S2649-S2651-S3013-S1808-S1173-S0910-S3517-S0453-S2424-S1174-S0902-S0903-S2101-S0481在上面路線中到達(dá)目的需要換乘兩次并且線路較長，通過計(jì)算我們知道所需時(shí)間為130分鐘，綜合以上條件并分析知：我們可以在公汽1919站換乘地鐵通過從站點(diǎn)到站點(diǎn)，從而到達(dá)站點(diǎn)S2633，實(shí)現(xiàn)與公汽的換乘，通過綜合考慮此路徑優(yōu)化后到達(dá)目標(biāo)所需要的時(shí)間為113分鐘，所以此方案達(dá)到了模型更優(yōu)化的目的．(3)由于=，通過交集的結(jié)果我們知道，在此路線基礎(chǔ)上不能實(shí)現(xiàn)再優(yōu)化過程，因?yàn)槿绻ㄟ^此交集換乘，而在題目中我們不知道地鐵的實(shí)際路線，因此只通過一次換乘不一定能到達(dá)目的地．通過分析問題一中的4、5我們知道，換乘地鐵不僅僅不能實(shí)現(xiàn)線路更優(yōu)化，并且還要花費(fèi)更多時(shí)間和乘車費(fèi)用，所以此時(shí)不能達(dá)到線路更優(yōu)化．(4)對(duì)于第6問，由于=而問題一中的起點(diǎn)為S0087，到終點(diǎn)S3676的最優(yōu)路徑為：S0087-S0857-S0965-S1427(換乘L381)-S1426-S0153-S0539-S2978-S0668-S3648-S1895-S0577-S0582-S0427（換乘L097）-S3676需要兩次換乘，所需時(shí)間為46分鐘，費(fèi)用為3元．通過上面的交集結(jié)果知道通過地鐵的站點(diǎn)到站點(diǎn)，正好能到達(dá)我們所要到達(dá)的終點(diǎn)站，所以用地鐵換乘公汽，我們不僅僅不需要兩次換乘公汽而且也只需要22．5分鐘，大大宿短了乘車時(shí)間并且交通費(fèi)也沒有增加，所以通過這種方法能實(shí)現(xiàn)模型的更好優(yōu)化．問題三：由于此時(shí)我們考慮到了站點(diǎn)之間的步行時(shí)間，而站點(diǎn)之間的步行時(shí)間指的是兩個(gè)相鄰站點(diǎn)的步行時(shí)間，否則我們認(rèn)為坐公交車可以解決問題．根據(jù)已知條件:在每一個(gè)地鐵站點(diǎn)附近都有一個(gè)甚至多個(gè)相鄰站點(diǎn)，我們稱為該站點(diǎn)的度，記為=．我們把從起始站（終點(diǎn)站）到終點(diǎn)站（起始站）的所有路線都可以看作是樹的樹枝，那么樹枝的繁茂程度決定了它們相交的程度．此時(shí)我們由相關(guān)性定義：（1）其中，分別表示公汽站點(diǎn),的度，是(,)公共的度與的和，，分別是小于1常數(shù)。因此當(dāng)把地鐵站點(diǎn)的度考慮進(jìn)來，明顯遞增，所以也隨之遞增．在解答問題一時(shí),我們找到含有起始站點(diǎn)和終點(diǎn)站點(diǎn)的所有路線并對(duì)它們是否相交進(jìn)行判斷,如果沒有交點(diǎn)我們就需要重復(fù)進(jìn)行操作,但此時(shí)我們的目標(biāo)不是找交點(diǎn),而是找相關(guān)站點(diǎn)(即表示在同一地鐵站點(diǎn)相鄰的公汽站點(diǎn)),如果找到相關(guān)點(diǎn),我們就能在相關(guān)點(diǎn)處實(shí)現(xiàn)公交與地鐵的相互換乘．相比較第一種換乘法,這種方法將大大節(jié)省時(shí)間和提高交通運(yùn)輸效率．六模型的評(píng)價(jià)與設(shè)想本文研究了以北京這個(gè)城市為背景的公共交通線路的最優(yōu)求解問題，根據(jù)給出的不同條件建立相應(yīng)的模型，運(yùn)用不同的方法得出最優(yōu)行車路線，并根據(jù)實(shí)際情況進(jìn)行篩選，模型得出的結(jié)果具有可實(shí)現(xiàn)性，在小范圍內(nèi)準(zhǔn)確性較高，對(duì)于大范圍的行程，可以計(jì)算機(jī)程序化，同樣可以實(shí)現(xiàn)，應(yīng)用此方法，可以方便乘客尋找最佳的乘車路線，也可以綜合應(yīng)用此法對(duì)城市的公交線路網(wǎng)絡(luò)圖的性能狀況進(jìn)行評(píng)估分析，提供對(duì)公交線路的結(jié)構(gòu)進(jìn)行進(jìn)一步改進(jìn)的方案．隨著公交系統(tǒng)的智能化進(jìn)一步發(fā)展，早期的只能提供車站名稱列表和行進(jìn)路線的查詢系統(tǒng)將會(huì)慢慢淡出人們的視野，未來的智能化的公交查詢系統(tǒng)將會(huì)實(shí)現(xiàn)以下功能：對(duì)輸入的起點(diǎn)、終點(diǎn)類型不要有太多的限制，只要是“用戶想知道什么，就輸入什么”，可以是車站名，地名，或小單位圖上任意一點(diǎn)，并且能放寬起點(diǎn)、終點(diǎn)類型的要求限制．七模型的優(yōu)化容易發(fā)現(xiàn)我們?cè)诮⒁陨夏Ｐ瓦^程中為了簡(jiǎn)化模型忽略了很多自然因素及人為因素，而在現(xiàn)實(shí)中這些問題都真實(shí)地存在，因此我們要優(yōu)化模型，則要把更多的因素包括進(jìn)去，這樣我們首先要建立一個(gè)數(shù)據(jù)庫,使其包含每一班次公交車的詳細(xì)信息．公交的信息分為兩大類:一類信息對(duì)于每一次公交車基本是固定的,如:車次、車類型、總里程、途徑車站總數(shù)、首末車時(shí)間、車票計(jì)價(jià)規(guī)則、平均擁擠度等;另一類信息則是車站、時(shí)間的函數(shù),如:車站地理坐標(biāo)、發(fā)車頻率、擁擠度、交通費(fèi)用計(jì)算等．我們可以用如下公式來表示乘車方案:P=f(b,t)+g(a)+h(c)+i(m)其中,b表示路面交通狀況(包括發(fā)車頻率、擁擠度)等；t表示方案發(fā)生的時(shí)間；a表示行車線路長度；c表示轉(zhuǎn)乘車行走的距離；m表示交通費(fèi)用