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

2、2所屬學校（請填寫完整的全名）：廣西師范學院參賽隊員（打印并簽名）：1. 鐘興智2. 尹海軍3. 斯婷指導教師或指導教師組負責人（打印并簽名）：韋程東日期：2007 年9月24 日賽區評閱編號（由賽區組委會評閱前進行編號）：編號專用頁賽區評閱編號（由賽區組委會評閱前進行編號）：賽區評閱記錄（可供賽區評閱時使用）：評閱人評分備注全國統一編號（由賽區組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：乘公交，看奧運摘要我們基于最小換乘次數算法，設計了公交查詢系統，能夠分別從時間和花費 出發考慮，選擇最優路徑，以滿足查詢者的各種不同需求。問題一：采用最小換乘次數算法，求出任意兩站的最

3、小換乘次數，在次數一 定的情況下，分別選取花費最少和時間最少作為優化目標，建立兩種模型：最少 .33一 .時間模型：min f（A,B） 3 （1 xR）5x ；取少化費模型：i 1i 13,.min g（A,B）（xi' （1 xijyij ；利用兩種模型求出6組數局的最彳土路線如下（兩i種模型求出的最優結果是一樣的）；起始站一終點站乘車路線時間費用S335A S1828L436 下行(S1784) 一 L167 下行1013S1557 S0481L084 下行（S1919） -L189 下行（S3186）一L460下行（有2條最優路線）1063S048A S0971L013 下行(

4、S0992) 一 L417 下行1283S0008 S0073L159 下行（S0491） 一 L058 下行（有5條最優路線）832S0148f S0485L308 上行(S0036) 一 L156 上行(S3351)一 L417下行1013S0087 S3676L454 上行(S3496) 一 L209 下行652問題二：把兩條地鐵的任意站點的附近公交站點以相同的序號表示，因此將地鐵的線路轉化成公交的問題，改進問題一中的模型求出此問題的最少時間模型3min f(A, B)(3i 13(Xi ni (1i 13Xi)qi)5xJ)i 133(1 yi)(2.5 ( (Xii 1i 1'

5、;n i(1 Xi)qi)3334Xi )7(1 z i) yi + 6Ziyi 1i 1i 1得到6組數據的最優路線如下：起始站一終點站乘車路線所需費用S3359- S1828L436 下行(S1784) 一 L167 下行101分3元S1557 S0481L363 下行（S1919） -L189 下行（S3186）一 L460下仃（后兩條）106分3元S048A S0971L013 下行(S0992) 一 L417 下行128分3元S0008 S0073L159 下行（S0491） 一 L058 下行（有5條）83分2元S0148f S0485L308 上行(S0036) 一 L156 上

6、行(S3351)一 L417下行101分3元S0087 S3676T2 (D27-D36)33分3元問題三：考慮到會存在緊鄰站點與終點站的直達線路， 所以我們對問題一的 最小換乘算法進行了改進。關鍵詞：最小換乘次數， 算法，緊鄰點，數據庫，路線集問題重述第 29 屆奧運會明年8 月將在北京舉行，屆時有大量觀眾到現場觀看奧運比賽， 其中大部分人將會乘坐公共交通工具 (簡稱公交， 包括公汽、 地鐵等) 出行。這些年來，城市的公交系統有了很大發展，北京市的公交線路已達800 條以上，使得公眾的出行更加通暢、 便利， 但同時也面臨多條線路的選擇問題。 針對市場需求，某公司準備研制開發一個解決公交線路選

7、擇問題的自主查詢計算機系統。其核心是線路選擇的模型與算法， 應該從實際情況出發考慮， 滿足查詢者的各種不同需求。現需解決以下問題：1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數學模型與算法。并根據附錄數據，利用你們的模型與算法，求出以下6對起始站-終到站 之間的最佳路線。(1)、S335gS1828(2)、S1557f S0481(3)、S0971-S0485(4)、S000A S0073(5)、S0148-S0485(6)、S0087f S 36762、同時考慮公汽與地鐵線路，解決以上問題。3、假設又知道所有站點之間的步行時間，給出任意兩站點之間線路選擇問題的數學模型。模型假

8、設1. 相鄰兩站公汽站距離和所需行駛時間相同。2. 公汽與地鐵線路都暢通無阻，即沒有堵車。3. 人們考慮換乘次數不超過兩次。4. 在有直達車的情況下，人們首選直達車。5. 同一地鐵站對應的任意兩個公汽站之間可以通過地鐵站換乘(無需支付地鐵費 )。6. 人們選擇坐地鐵都是出于省時考慮，暫不考慮花費。模型建立與求解問題一1. 問題分析人們在選擇公交出行路線時考慮的因素很多，如出行耗時是否最少，線路是否最短，換乘次數是否最少，花費是否最少。資料調查顯示，大多數乘客在選擇公汽線路時， 首先考慮的是乘車是否方便， 就換乘次數而言， 一般不大于兩次3 。所以我們采用最小換乘次數算法1 ，求出最少換乘次數。

9、然后在最少換乘次數一定的情況下， 我們再針對個人偏好， 分別選取花費最少和時間最少作為優化目標。最小換乘次數最少算法的基本思想是從起始站點 A (任意的) ，終止站點 B(任意的) 出發， 通過比較公交網絡上各車站的可換乘車站， 追索 A 到 B 的可能 路徑，然后比較各可能路徑的時間或花費，來確定最優路線。2 .模型算法與求解2.1 符號說明：S(K)| K 1,2, ,m為經過A的線路集T(L) L 1,2, ,n為經過B的線路集。E(K,U)(U 1,2, r)為線路S(K)上的站點。其中U可表示為線路S(K)上各站點 的序號。F(L,V)(V 1,2, Pj)為線路T(L)上的站點。其

10、中V可表示為線路T(L)上各站點的)丁萬。R(M)(M 1,2, ,g)為經過E(K,U)的線路集。Y(N)(N 1,2, ,z)為經過F(L,V)的線路集。2.2 算法步驟及流程圖：(1)輸入乘車的起始站點A及終止站點B;(2)求出經過站點A的所有線路集S(K)和經過站點B的所有線路集T(L);(3)判斷S(K)是否等于T(L),如果相等再判斷S(K)是否為環行線路，如果是則S(K) 為站點A到站點B的直達線路，如果不是環行線路但線路上結束的序號大于開始的序號 則仍是直達線路；輸出結果，結束運算；如果沒有則進行下一步。(4)求線路S(K)上的站點E(K,U )以及線路T(L)上的站點F(L,

11、V);(5)判斷是否存在相同站點，即是否有存在 E(K,U ) = F(L,V)的情況，如果有再判斷 相交路線是否為環行，如果是且經過終點的路線也為環行，則可一次轉車；如果相交路 線不是環行，但線路上結束的序號小于結束站序號，仍可一次轉車，線路S(K),T(L)即為一次轉車的線路，E(K,U)即為轉車站點。如果沒有相同站點再執行下面。(6)求出經過E(K,U)的線路集R(M),經過F(L,V)的線路集Y(N);(7)判斷R(M )是否等于Y(N)。如果相等再判斷R(M)是否為環行線路，如果是則線路S(K), R(M), T(L)為兩次換車的線路，換車站點為 E(K,U)和F(L,V);如果不

12、是環行線路但線路上結束的序號大于開始的序號則仍可實現二次轉車。輸出結果，結束 運算。15最少換乘次數算法流程圖:是直達進入下組數據（圖一）一次轉乘算法流程圖:(圖二)2.3 模型建立：對于所求轉車線路可能不止一條，我們根據最少時間或最少花費為目標函數求出個 人所需最優線路。記E(K,Ua)為線路S(K)上的A站點，其序號為Ua ； F(L,Vb)線路T(L)上的B站點,其序號為Vb o記 ni U U a , n2 V U ,我 Vb V ,自A起三條路線的總站數分別為Pi, P2, P31 U,UaPi； 1 u,v P2I V,VbP3若線路為上下行或單行，則從 A站點E(K,Ua)到轉車

13、站點E(K,U)的站點數為 ni| U Ua ,從E(K,U)到F(L,V)的站點數為也 V U ,從轉車站點F(L,V)到B站 點的站點數為n3 VB V。若線路為環行，當 Ua<U , U V , V<Vb時，A站點到E(K,U), E(K,U)到F(L,V) , F(L,V)到B站點的站點數為】U U a ,門2 V U , % Vb V。當Ua>U,V>Vb 時，A 站點到 E(K,U), E(K,U)到 F(L,V),為 Pini, P2n2, P303(1)最少時間模型:33min f (A, B) 3 ( 由 q (1 Xi)q。)5xiF(L,V)到B站

14、點的站點數(1.1)s.t. Xi1，0,線路為上下行或單行 線路為環行1,2,3)(1)31Xi3i 1(2)qi (n R)mod(Pi), 0 qi Pi ( i(2)最少花費模型:3ming(A, B)(為(1 xjyi)11,2,3)(3)(1.2)s.t.x'1,0,線路為單一票制線路為分段計價1,2,3)(Di 1i 1(2)(3)1,1ni20,yj 2,21 Q 40, (j 1,2,3)3,41 1nj31 Xi 3i 12.4 模型求解我們將所給文本1.1公路線路信息.txt中的數據作處理，用替換的方法使得文本利 于導入數據庫，利用C#將文本文件的內容一次導入SQ

15、L數據庫，接著利用C#8寫程序 (見附件1),數據庫代碼見附件2。利用算法實現的代碼與數據庫連接求得最優解。2.5 模型結果及分析:最少時間和最少花費的線路結果表:起始站一終點站乘車路線時間費用S335g S1828L436 下行(S1784) 一 L167 下行101分3元S155片 S0481L363 下行(S1919) 一 L189 下行(S3186) 一 L460下行106分3元L084 下行(S1919) 一 L189 下行(S3186) 一 L460下行106分3元S048A S0971L013 下行(S0992) 一 L417 下行128分3元S000A S0073L159 下行

16、(S0491) 一 L058 下行83分2元L159 下行(S3053) 一 L474 上行83分2元L355 下行(S2303) 一 L345 上行83分2元L463 下行(S2083) 一 L057 上行83分2元L159 下行(S0491) 一 L058 下行83分2元S014A S0485L308 上行(S0036) 一 L156 上行(S3351) 一 L417下行101分3元S008片 S3676L454 上行(S3496) 一 L209 下行65分3元我們發現在這6組數據里面，時間最少和花費最少的最佳路線是一樣的。這也是符 合常情的。但也存在站數和時間少但花費多的情況。這時人們就

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

18、i 1,2,39）為開始站點A對應地鐵站點的車次，Dj（j 1,2,39）為終止站點B 對應站點的車次Mi為地鐵站點Di對應的公汽站點的集合，M j為地鐵站點Dj對應的公汽站點的集 合2.2 算法步驟 1） 1）輸入乘車的起始站點A 及終止站點B 2） 分別判斷A, B是否屬于MMj,若都不屬于則回到問題一的算法；若A Mi,B Mj則進行第（3）, （4）步；若A MB M j則進行第（5）步；若A MB M j 則進行第（6）步。 3） 判斷i是否等于j ,若i j則A可以通過Di轉到B。若i j ,則進行下一步。 4） 若 1 i 23,1 j 23,則可從 Di乘 T1 直達 Dj ；

19、若1 i 23,27j32,則先從Di乘T1在D12下車，然后坐T2到達Dj ；若1 i 23,33j 39或24j26,則先從Di乘T1在D18下車，然后坐T2到達Dj ；若27 i 32,1 j 23 ,則先從Di 乘 T2 在 D18 下車，然后坐T1 到達判斷相交路線是否為環行，如果是且經過終點的路線也為環行，則可一次轉車；如果相交路線不是環行，但線路上結束的序號小于結束站序號，仍可一次轉車， Dj；若33 i 39或24 i 32, 1j23,則先從Dj乘T2在D12下車，然后坐T1到達Dj；若24 i 39或i 12,18, 24 j39或者j 12.18,則從 D i 可乘 T2

20、 直達 D j 。 5） A MB Mj,判斷能否找到A和Mi中某公汽站點A'的直達線路。若沒 有則退出運算；若有則根據第（ 3） ， （ 4）步求出A' 和 B 的地鐵轉乘路線。這樣就可求出A 到 B 的公汽地鐵的轉乘路線。 6） 6） A M i ， B M j ，類似第（5）步求出A 到 B 的地鐵公汽的轉乘路線。2.3 模型建立當A到B的路線為通過地鐵站點Di直接轉到時，所需時間為公汽與地鐵站點的步行時間，即t4 4 =8當從Di乘T1直達Dj時，所需時間為t28 (j i)2.5Di乘T1D12下車，然后乘T2Dj所需t3(18 i2.5Di乘T1D18下車，然后乘T

21、2Dj所需t4(18 i(j1733)mod(17)Di乘T2D18下車，然后坐T1Dj所需t5(33 i) 18 j) 2.5Di乘T2在D12下車，然后坐T1Dj所需t6(i 17 33)mod(17)12 j)2.5當從Di可乘T2直達Dj時，所需時間為t7當為公汽一一地鐵或地鐵一一公汽路線時，所需時間為t8當不能通過地鐵轉乘時，所需時間為問題一的最短時間t9綜上所述，模型一可歸納如下:minf(A,B)min(t1,t2，t9)(1.3)s.t.t1 =8，t2(j i)2.51 i 2323t4t5t6t34 (1832) 2.523, 2732(18 i (j1733)mod(17

22、)3339 或 24j 26(33 i) 18 j) 2.5, 27 i(i 17 33)mod(17) 12 j)t7為環形直達所需時間,322.524 i 39 或 i33 i12,18 ,2339或 24 i 3224 j 39或者j12.1823t8,為公汽與地鐵換乘所需時間A Mi, B Mj 或 A Mi, B Mjt9為問題一中情況所需時間A Mi, B Mj2.4 模型評價此模型算法復雜，且求解各段時間較為困難，很難編程解出結果。所以我們考慮了 第二種模型3 .模型二的建立與求解3.1 模型建立把兩條地鐵的任意站點的附近公交站點以相同的序號表示，因此將地鐵的線路轉化成公交的問題

23、，然后利用求出的公交站點求出地鐵的站臺號。這樣可以回歸到問題的模 型求解。記：E(K,U)(U 1,2, pj為原公汽線路S(K)上的站點；E(K,U)(U 1,2, pj為由地鐵改編成的公汽線路S(K)的站點；F(L,V)(V 1,2, Pj)為原公汽線路T(L)上的站點；F(L,V)(V 1,2, p j)為由地鐵改編成的公汽線路T(L)上的站點；n1 U Ua, % V U , % Vb Vn U U a, n2 V U , % Vb V1,乘坐原公汽線路yi 0 乘坐改編成的公汽線路33乘坐改編成的公汽線路時的時間為2.5 (xi ni (1 xi)qi)4xii 1i 13地鐵與公汽

24、換乘時間為7yii 13公汽與地鐵換乘時間為6yii 11,公汽地鐵換乘z；0地鐵-公汽換乘綜上所述最少時間模型:min f(A,B)(yi(3i 1(Xi nii 1(1Xi )qi)5Xi)13(1i 13yj(2.5 (Xi(1Xi)qi)34為)i 137(1i 13Zi)yi+ 6ZiYi(1.4)s.t. xi1,0,線路為上下行或單行 線路為環行1,2,3)(DqiVZi3Xi1(2)(ni1,01,0Pi)mod(Pi), 0 qiPi ( i1,2,3)(3)乘坐原公汽線路乘坐改編成的公汽線路公汽地鐵換乘地鐵-公汽換乘(4)(5)3.2模型求解把地鐵線路轉換成公交線路，進行問

25、題中的運算。運算結果如下表:起始站一終點站乘車路線時間費用S335g S1828L436 下行(S1784) 一 L167 下行101分3元S155片 S0481L363 下行(S1919) - L189 下行(S3186)一 L460下行106分3元S155片 S0481L084 下行(S1919) - L189 下行(S3186)一 L460下行106分3元S048A S0971L013 下行(S0992) 一 L417 下行128分3元S000A S0073L159 下行(S0491) 一 L058 下行83分2元L159 下行(S3053) 一 L474 上行83分2元L355 下行(

26、S2303) 一 L345 上行83分2元L463 下行(S2083) 一 L057 上行83分2元L159 下行(S0491) 一 L058 下行83分2元S014A S0485L308 上行(S0036) 一 L156 上行(S3351)一 L417下行101分3元S008片 S3676T2 (D27-D36)33分3元3.3模型評價：此模型引用的是問題一中的模型，對時間最短模型進行改進。只是增加了條件，程 序運行復雜度更高。問題三1 .問題分析考慮站點之間步行時間后，就有可能存在與終止站點直達線路的緊鄰站點，只要先 步行到緊鄰站點，再由緊鄰站點乘直達車到終止站點，就有可能減少時間。所以要

27、對問 題一的算法進行改進202 .改進的算法2.1 符號說明：S(K) K 1,2, ,m為經過A的線路集。T(L)| L 1,2, ,n為經過B的線路集。E(K,U)(U 1,2, r)為線路S(K)上的站點。其中U可表示為線路S(K)上各站點 的序號。F(L,V)(V 1,2, Pj)為線路T(L)上的站點。其中V可表示為線路T(L)上各站點的)丁萬。R(M)(M 1,2, ,g)為經過E(K,U)或其附近的線路集。Y(N)(N 1,2, ,z)為經過F(L,V)或其附近的線路集。t(m,n)表示站點m與站點n之間步行的時間，T表示乘客在換車時步行時間的最大心理承受值。對于站點m與站點n之間的緊鄰關系，可以用一個不等式表示：t(m,n) T2.2 算法步驟：(1)輸入乘車的起始站點A及