上傳人：3***

認證信息

認證類型：個人認證

認證主體：雷**（實名認證）

IP屬地：湖北

IP屬地：湖北 上傳時間：2021-11-20 格式：DOC 頁數(shù)：17 大?。?39KB 積分：28 舉報 版權(quán)申訴

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

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

3、以滿足查詢者的各種不同需求。 問題一：采用最小換乘次數(shù)算法，求出任意兩站的最小換乘次數(shù)，在次數(shù)一定的情況下，分別選取花費最少和時間最少作為優(yōu)化目標，建立兩種模型：最少時間模型：；最少花費模型：；利用兩種模型求出6組數(shù)局的最佳路線如下（兩種模型求出的最優(yōu)結(jié)果是一樣的）；起始站終點站乘車路線時間費用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問題二：把兩條地鐵的任意站點的附近公交站點以相同的序號表示，因此將地鐵的線路轉(zhuǎn)化成公交的問題，改進問題一中的模型求出此問題的最少時間模型 + 得到6組數(shù)據(jù)的最優(yōu)路線如下：起始站終點站乘車路線所需費用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元 問題三：考慮到會存在緊鄰站點與終點站的直達線路，所以我們對問題一的最小換乘算法進行了改進。 關(guān)鍵詞：最小換乘次數(shù)， 算法，緊鄰點，數(shù)據(jù)庫，路線集問題重述第29屆奧運會明年8月將在北京舉行，屆時有大量觀眾到現(xiàn)場觀看奧運比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達8

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

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

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

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

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

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

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

13、84下行（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ù)里面，時

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

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

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

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

18、路轉(zhuǎn)化成公交的問題，然后利用求出的公交站點求出地鐵的站臺號。這樣可以回歸到問題的模型求解。記： 為原公汽線路上的站點；為由地鐵改編成的公汽線路的站點；為原公汽線路上的站點；為由地鐵改編成的公汽線路 上的站點；，乘坐改編成的公汽線路時的時間為地鐵與公汽換乘時間為公汽與地鐵換乘時間為綜上所述最少時間模型： + （1.4）s.t. , （1） （2） ， （3） （4） （5）3.2模型求解把地鐵線路轉(zhuǎn)換成公交線路，進行問題中的運算。運算結(jié)果如下表：起始站終點站乘車路線時間費用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（D27

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