上傳人：s***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：沃**（實(shí)名認(rèn)證）

IP屬地：上海

IP屬地：上海 上傳時(shí)間：2022-03-04 格式：DOCX 頁(yè)數(shù)：17 大?。?70.66KB 積分：20 舉報(bào) 版權(quán)申訴

1、2007高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽承 諾 書我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wè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)填寫）： B 我們的電子文件名： B0302

2、所屬學(xué)校（請(qǐng)?zhí)顚懲暾娜?廣西師范學(xué)院 參賽隊(duì)員 (打印并簽名) ：1. 鐘興智 2. 尹海軍 3. 斯 婷 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 韋程?hào)| 日期： 2007 年 9 月 24 日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2007高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編 號(hào) 專 用 頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：乘公交，看奧運(yùn)摘要 我們基于最小換乘次數(shù)算法，設(shè)計(jì)了公交查詢系統(tǒng)，能夠分別從時(shí)間和花費(fèi)出發(fā)考慮，選擇最優(yōu)路徑，

3、以滿足查詢者的各種不同需求。 問(wèn)題一：采用最小換乘次數(shù)算法，求出任意兩站的最小換乘次數(shù)，在次數(shù)一定的情況下，分別選取花費(fèi)最少和時(shí)間最少作為優(yōu)化目標(biāo)，建立兩種模型：最少時(shí)間模型：；最少花費(fèi)模型：；利用兩種模型求出6組數(shù)局的最佳路線如下（兩種模型求出的最優(yōu)結(jié)果是一樣的）；起始站終點(diǎn)站乘車路線時(shí)間費(fèi)用S3359S1828L436下行（S1784）L167下行1013S1557S0481L084下行（S1919）L189下行（S3186）L460下行（有2條最優(yōu)路線）1063S0485S0971L013下行（S0992）L417下行1283S0008S0073L159下行（S0491）L058下行(有

4、5條最優(yōu)路線)832S0148S0485L308上行（S0036）L156上行（S3351）L417下行1013S0087S3676L454上行（S3496） L209下行 652問(wèn)題二：把兩條地鐵的任意站點(diǎn)的附近公交站點(diǎn)以相同的序號(hào)表示，因此將地鐵的線路轉(zhuǎn)化成公交的問(wèn)題，改進(jìn)問(wèn)題一中的模型求出此問(wèn)題的最少時(shí)間模型 + 得到6組數(shù)據(jù)的最優(yōu)路線如下：起始站終點(diǎn)站乘車路線所需費(fèi)用S3359S1828L436下行（S1784）L167下行101分3元S1557S0481L363下行（S1919）L189下行（S3186）L460下行（有兩條）106分3元S0485S0971L013下行（S0992）

5、L417下行128分3元S0008S0073L159下行（S0491）L058下行（有5條）83分2元S0148S0485L308上行（S0036）L156上行（S3351）L417下行101分3元S0087S3676T2（D27D36）33分3元 問(wèn)題三：考慮到會(huì)存在緊鄰站點(diǎn)與終點(diǎn)站的直達(dá)線路，所以我們對(duì)問(wèn)題一的最小換乘算法進(jìn)行了改進(jìn)。 關(guān)鍵詞：最小換乘次數(shù)， 算法，緊鄰點(diǎn)，數(shù)據(jù)庫(kù)，路線集問(wèn)題重述第29屆奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）出行。這些年來(lái)，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)8

6、00條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問(wèn)題。針對(duì)市場(chǎng)需求，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)。其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求?，F(xiàn)需解決以下問(wèn)題：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對(duì)起始站終到站之間的最佳路線。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同時(shí)考慮公汽與

7、地鐵線路，解決以上問(wèn)題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，給出任意兩站點(diǎn)之間線路選擇問(wèn)題的數(shù)學(xué)模型。模型假設(shè)1. 相鄰兩站公汽站距離和所需行駛時(shí)間相同。2. 公汽與地鐵線路都暢通無(wú)阻，即沒有堵車。3. 人們考慮換乘次數(shù)不超過(guò)兩次。4. 在有直達(dá)車的情況下，人們首選直達(dá)車。5. 同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過(guò)地鐵站換乘(無(wú)需支付地鐵費(fèi))。6. 人們選擇坐地鐵都是出于省時(shí)考慮，暫不考慮花費(fèi)。模型建立與求解問(wèn)題一1. 問(wèn)題分析 人們?cè)谶x擇公交出行路線時(shí)考慮的因素很多，如出行耗時(shí)是否最少，線路是否最短，換乘次數(shù)是否最少，花費(fèi)是否最少。資料調(diào)查顯示，大多數(shù)乘客在選擇公汽線路時(shí)，首先考慮的

8、是乘車是否方便，就換乘次數(shù)而言，一般不大于兩次3。所以我們采用最小換乘次數(shù)算法1，求出最少換乘次數(shù)。然后在最少換乘次數(shù)一定的情況下，我們?cè)籴槍?duì)個(gè)人偏好，分別選取花費(fèi)最少和時(shí)間最少作為優(yōu)化目標(biāo)。最小換乘次數(shù)最少算法的基本思想是從起始站點(diǎn)（任意的），終止站點(diǎn)（任意的）出發(fā)，通過(guò)比較公交網(wǎng)絡(luò)上各車站的可換乘車站，追索到的可能路徑，然后比較各可能路徑的時(shí)間或花費(fèi)，來(lái)確定最優(yōu)路線。2模型算法與求解2.1 符號(hào)說(shuō)明：為經(jīng)過(guò)的線路集。為經(jīng)過(guò)B的線路集。為線路上的站點(diǎn)。其中可表示為線路上各站點(diǎn)的序號(hào)。為線路上的站點(diǎn)。其中可表示為線路上各站點(diǎn)的序號(hào)。為經(jīng)過(guò)的線路集。為經(jīng)過(guò)的線路集。2.2 算法步驟及流程圖：(1

9、)輸入乘車的起始站點(diǎn)及終止站點(diǎn)； (2)求出經(jīng)過(guò)站點(diǎn)的所有線路集和經(jīng)過(guò)站點(diǎn)的所有線路集； (3)判斷是否等于，如果相等再判斷是否為環(huán)行線路，如果是則為站點(diǎn)到站點(diǎn)的直達(dá)線路，如果不是環(huán)行線路但線路上結(jié)束的序號(hào)大于開始的序號(hào)則仍是直達(dá)線路；輸出結(jié)果，結(jié)束運(yùn)算；如果沒有則進(jìn)行下一步。(4)求線路上的站點(diǎn)以及線路上的站點(diǎn)； (5)判斷是否存在相同站點(diǎn)，即是否有存在=的情況，如果有再判斷相交路線是否為環(huán)行，如果是且經(jīng)過(guò)終點(diǎn)的路線也為環(huán)行，則可一次轉(zhuǎn)車；如果相交路線不是環(huán)行，但線路上結(jié)束的序號(hào)小于結(jié)束站序號(hào)，仍可一次轉(zhuǎn)車，線路，即為一次轉(zhuǎn)車的線路，即為轉(zhuǎn)車站點(diǎn)。如果沒有相同站點(diǎn)再執(zhí)行下面。(6)求出經(jīng)過(guò)的

10、線路集，經(jīng)過(guò)的線路集； (7)判斷是否等于 。如果相等再判斷是否為環(huán)行線路，如果是則線路，為兩次換車的線路，換車站點(diǎn)為和；如果不是環(huán)行線路但線路上結(jié)束的序號(hào)大于開始的序號(hào)則仍可實(shí)現(xiàn)二次轉(zhuǎn)車。輸出結(jié)果，結(jié)束運(yùn)算。開始直達(dá)進(jìn)入下組數(shù)據(jù) 是獲得起點(diǎn)A和終點(diǎn)B獲得經(jīng)過(guò)A的線路集合S（K）和B的線路集合T（L）S(K)與T(L)是否有交集交集中的線路類型是否為環(huán)形用一轉(zhuǎn)的方法解決線路上結(jié)束的序號(hào)是否大于開始的序號(hào)是否否得經(jīng)過(guò)A的線路集合S（K）和B的線路集合T（L）是否最少換乘次數(shù)算法流程圖： （圖一）一次轉(zhuǎn)乘算法流程圖：S（K）與T（L）路線是否存在交點(diǎn)相交路線類型是否為環(huán)行用二轉(zhuǎn)算法解決線路上結(jié)束的

11、序號(hào)是否小于結(jié)束站序號(hào)經(jīng)過(guò)終點(diǎn)的路線是否為環(huán)行線路上結(jié)束的序號(hào)是否小于結(jié)束 站序號(hào)一轉(zhuǎn)可到達(dá)進(jìn)入下一組數(shù)據(jù)是否否是否否否是是 （圖二）2.3模型建立：對(duì)于所求轉(zhuǎn)車線路可能不止一條，我們根據(jù)最少時(shí)間或最少花費(fèi)為目標(biāo)函數(shù)求出個(gè)人所需最優(yōu)線路。記為線路上的站點(diǎn)，其序號(hào)為；線路上的站點(diǎn)，其序號(hào)為。記, ,自起三條路線的總站數(shù)分別為；若線路為上下行或單行，則從站點(diǎn)到轉(zhuǎn)車站點(diǎn)的站點(diǎn)數(shù)為，從到的站點(diǎn)數(shù)為，從轉(zhuǎn)車站點(diǎn)到站點(diǎn)的站點(diǎn)數(shù)為。若線路為環(huán)行，當(dāng)<， ，<時(shí)，站點(diǎn)到，到，到站點(diǎn)的站點(diǎn)數(shù)為，。當(dāng)>,>時(shí)，站點(diǎn)到，到，到站點(diǎn)的站點(diǎn)數(shù)為，（1）最少時(shí)間模型： （1.1）s.t. , （1

12、） （2） ， （3）（2）最少花費(fèi)模型： （1.2）s.t.， （1） ， （2） （3）2.4模型求解 我們將所給文本1.1公路線路信息.txt中的數(shù)據(jù)作處理，用替換的方法使得文本利于導(dǎo)入數(shù)據(jù)庫(kù)，利用C#將文本文件的內(nèi)容一次導(dǎo)入SQL數(shù)據(jù)庫(kù)，接著利用C#編寫程序（見附件1），數(shù)據(jù)庫(kù)代碼見附件2。利用算法實(shí)現(xiàn)的代碼與數(shù)據(jù)庫(kù)連接求得最優(yōu)解。2.5模型結(jié)果及分析：最少時(shí)間和最少花費(fèi)的線路結(jié)果表：起始站終點(diǎn)站乘車路線時(shí)間費(fèi)用S3359S1828L436下行（S1784）L167下行101分3元 S1557S0481L363下行（S1919）L189下行（S3186）L460下行106分3元L084

13、下行（S1919）L189下行（S3186）L460下行106分3元S0485S0971L013下行（S0992）L417下行128分3元S0008S0073L159下行（S0491）L058下行83分2元L159下行(S3053) L474上行83分2元L355下行(S2303) L345上行83分2元L463下行（S2083）L057上行83分2元L159下行（S0491）L058下行83分2元S0148S0485L308上行（S0036）L156上行（S3351）L417下行101分3元S0087S3676L454上行（S3496） L209下行65分3元我們發(fā)現(xiàn)在這6組數(shù)據(jù)里面，時(shí)間最

14、少和花費(fèi)最少的最佳路線是一樣的。這也是符合常情的。但也存在站數(shù)和時(shí)間少但花費(fèi)多的情況。這時(shí)人們就可以根據(jù)自己實(shí)際情況選擇路線。2.6模型評(píng)價(jià)優(yōu)點(diǎn)：采用最小換乘次數(shù)算法，既符合人們一般想法，又把問(wèn)題及模型簡(jiǎn)單化。能夠分別從時(shí)間和花費(fèi)考慮建立兩種模型，滿足查詢者的不同需求。模型結(jié)構(gòu)簡(jiǎn)單，條理清晰，易于實(shí)施，對(duì)于編程來(lái)說(shuō)是比較容易的缺點(diǎn)：采用地毯式的遍歷搜索，使得程序運(yùn)行的復(fù)雜度過(guò)高，運(yùn)行時(shí)間長(zhǎng)，不適合于大量數(shù)據(jù)的應(yīng)用。問(wèn)題二1.問(wèn)題分析如果同時(shí)考慮汽車和地鐵換乘，雖然花費(fèi)可能會(huì)增加，但很有可能減少路徑時(shí)間，這對(duì)趕時(shí)間的人來(lái)說(shuō)是十分必要的。所以此問(wèn)只考慮最小換乘次數(shù)的最少時(shí)間模型。我們依然規(guī)定最小換

15、乘次數(shù)為2次。我們建立了兩個(gè)模型。2.模型一的算法與求解2.1符號(hào)說(shuō)明為開始站點(diǎn)對(duì)應(yīng)地鐵站點(diǎn)的車次，為終止站點(diǎn)對(duì)應(yīng)站點(diǎn)的車次為地鐵站點(diǎn)對(duì)應(yīng)的公汽站點(diǎn)的集合，為地鐵站點(diǎn)對(duì)應(yīng)的公汽站點(diǎn)的集合2.2 算法步驟（1）輸入乘車的起始站點(diǎn)及終止站點(diǎn)（2）分別判斷，是否屬于，若都不屬于則回到問(wèn)題一的算法；若,則進(jìn)行第（3），（4）步；若，則進(jìn)行第（5）步；若，則進(jìn)行第（6）步。（3）判斷是否等于，若則可以通過(guò)轉(zhuǎn)到。若，則進(jìn)行下一步。（4）若，則可從乘T1直達(dá)；若，則先從乘T1在D12下車，然后坐T2到達(dá)；若，則先從乘T1在D18下車，然后坐T2到達(dá)；若，則先從乘T2在D18下車，然后坐T1到達(dá)判斷相交路線是

16、否為環(huán)行，如果是且經(jīng)過(guò)終點(diǎn)的路線也為環(huán)行，則可一次轉(zhuǎn)車；如果相交路線不是環(huán)行，但線路上結(jié)束的序號(hào)小于結(jié)束站序號(hào)，仍可一次轉(zhuǎn)車，；若，則先從乘T2在D12下車，然后坐T1到達(dá)；若，則從可乘T2直達(dá)。（5），判斷能否找到和中某公汽站點(diǎn)的直達(dá)線路。若沒有則退出運(yùn)算；若有則根據(jù)第（3），（4）步求出和的地鐵轉(zhuǎn)乘路線。這樣就可求出到的公汽地鐵的轉(zhuǎn)乘路線。（6），類似第（5）步求出到的地鐵公汽的轉(zhuǎn)乘路線。2.3 模型建立當(dāng)?shù)降穆肪€為通過(guò)地鐵站點(diǎn)直接轉(zhuǎn)到時(shí)，所需時(shí)間為公汽與地鐵站點(diǎn)的步行時(shí)間，即=8當(dāng)從乘T1直達(dá)時(shí)，所需時(shí)間為當(dāng)從乘T1在D12下車，然后乘T2到達(dá)時(shí)，所需時(shí)間為當(dāng)從乘T1在D18下車，然后乘

17、T2到達(dá)時(shí)，所需時(shí)間為當(dāng)從乘T2在D18下車，然后坐T1到達(dá)時(shí)，所需時(shí)間為當(dāng)從乘T2在D12下車，然后坐T1到達(dá)時(shí)，所需時(shí)間為當(dāng)從可乘T2直達(dá)時(shí)，所需時(shí)間為當(dāng)為公汽地鐵或地鐵公汽路線時(shí)，所需時(shí)間為當(dāng)不能通過(guò)地鐵轉(zhuǎn)乘時(shí)，所需時(shí)間為問(wèn)題一的最短時(shí)間綜上所述，模型一可歸納如下： （1.3）s.t. =8， ， ， ，為環(huán)形直達(dá)所需時(shí)間， ，為公汽與地鐵換乘所需時(shí)間 ，或，為問(wèn)題一中情況所需時(shí)間 ， 2.4 模型評(píng)價(jià)此模型算法復(fù)雜，且求解各段時(shí)間較為困難，很難編程解出結(jié)果。所以我們考慮了第二種模型3.模型二的建立與求解3.1模型建立把兩條地鐵的任意站點(diǎn)的附近公交站點(diǎn)以相同的序號(hào)表示，因此將地鐵的線路轉(zhuǎn)

18、化成公交的問(wèn)題，然后利用求出的公交站點(diǎn)求出地鐵的站臺(tái)號(hào)。這樣可以回歸到問(wèn)題的模型求解。記： 為原公汽線路上的站點(diǎn)；為由地鐵改編成的公汽線路的站點(diǎn)；為原公汽線路上的站點(diǎn)；為由地鐵改編成的公汽線路 上的站點(diǎn)；，乘坐改編成的公汽線路時(shí)的時(shí)間為地鐵與公汽換乘時(shí)間為公汽與地鐵換乘時(shí)間為綜上所述最少時(shí)間模型： + （1.4）s.t. , （1） （2） ， （3） （4） （5）3.2模型求解把地鐵線路轉(zhuǎn)換成公交線路，進(jìn)行問(wèn)題中的運(yùn)算。運(yùn)算結(jié)果如下表：起始站終點(diǎn)站乘車路線時(shí)間費(fèi)用S3359S1828L436下行（S1784）L167下行101分3元S1557S0481L363下行（S1919）L189下行

19、（S3186）L460下行106分3元S1557S0481L084下行（S1919）L189下行（S3186）L460下行106分3元S0485S0971L013下行（S0992）L417下行128分3元S0008S0073L159下行（S0491）L058下行83分2元L159下行(S3053) L474上行83分2元L355下行(S2303) L345上行83分2元L463下行（S2083）L057上行83分2元L159下行（S0491）L058下行83分2元S0148S0485L308上行（S0036）L156上行（S3351）L417下行101分3元S0087S3676T2（D27D3

20、6）33分3元3.3模型評(píng)價(jià)：此模型引用的是問(wèn)題一中的模型，對(duì)時(shí)間最短模型進(jìn)行改進(jìn)。只是增加了條件，程序運(yùn)行復(fù)雜度更高。問(wèn)題三1.問(wèn)題分析考慮站點(diǎn)之間步行時(shí)間后，就有可能存在與終止站點(diǎn)直達(dá)線路的緊鄰站點(diǎn)，只要先步行到緊鄰站點(diǎn)，再由緊鄰站點(diǎn)乘直達(dá)車到終止站點(diǎn)，就有可能減少時(shí)間。所以要對(duì)問(wèn)題一的算法進(jìn)行改進(jìn)2。2.改進(jìn)的算法2.1符號(hào)說(shuō)明：為經(jīng)過(guò)的線路集。為經(jīng)過(guò)B的線路集。為線路上的站點(diǎn)。其中可表示為線路上各站點(diǎn)的序號(hào)。為線路上的站點(diǎn)。其中可表示為線路上各站點(diǎn)的序號(hào)。為經(jīng)過(guò)或其附近的線路集。為經(jīng)過(guò)或其附近的線路集。表示站點(diǎn)與站點(diǎn)之間步行的時(shí)間，T表示乘客在換車時(shí)步行時(shí)間的最大心理承受值。對(duì)于站點(diǎn)與站點(diǎn)之間的緊鄰關(guān)系，可以用一個(gè)不等式表示：2.2算法步驟：(1)輸入乘車的起始站點(diǎn)及終止站點(diǎn)； (2)求