1、2007高教社杯全國大學生數(shù)學建模競賽B題【摘要】本文根據(jù)人們出行習慣、情緒等特點,確定任意兩站點之間的最佳線路的模型和算法。在只考慮公汽的情況下，在以換乘次數(shù)最小為主要因素,通過建立換乘次數(shù)及線路選擇模型,在要求時間，費用最小的條件下，通過進行權重分析，建立最小花費函數(shù)，從而得到最佳路線。通過運用廣度優(yōu)先遍歷算法和MATLAB編程，由已知的數(shù)據(jù)運算得到任意給定兩站點之間的所有線路選擇及其最優(yōu)線路。 在同時考慮地鐵、公汽線路時，沿用此模型思想、算法確定最佳路線。 假設又考慮步行時間，可通過建立最小路徑成本模型，運用最優(yōu)路徑改進算法，確定最優(yōu)路線。 最后針對對所作的模型、算法進行評價與推廣，提出

2、可行有效的改進如Dijkstra算法。【關鍵詞】：公交 最小換乘次數(shù) 廣度優(yōu)先遍歷 最佳路線14一、 問題重述這些年來，城市的公交系統(tǒng)有了很大發(fā)展，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。如何從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。現(xiàn)需要解決的問題如下：分別在只考慮公交線路，同時考慮公交與地鐵，或同時考慮已知站點之間的步行時間的情況下確定其最佳路線。（1）、僅考慮公汽線路，任意兩公汽站點之間線路選擇問題的一般數(shù)學模型與算法。并根據(jù)附錄數(shù)據(jù)，在只考慮公交線路的情況下，求出以下6對已知站點之間的最佳路線（要有清晰的評價說明）。 (1)、 (2)、 (3)、(4)、 (5

3、)、 (6)、二、 問題分析實現(xiàn)公交網(wǎng)絡查詢系統(tǒng)的最優(yōu)路徑查詢的重點在于如何實現(xiàn)查詢者的個人滿意度最高的問題。在公交換乘的過程中，有多種優(yōu)先策略考慮。比如換乘次數(shù)最少、費用最少、時間最短等。每個人考慮的重要因素不同，但大多數(shù)人對換乘次數(shù)的多少比較在意，因此我們考慮用基于換乘次數(shù)最少的公交換乘優(yōu)先策略，其次考慮時間最短，最后考慮費用最少，這比較符合大眾出行時的心理情況。對于只考慮公交換乘方案的問題一，則可依次尋找兩站點間是否存在直達線路、一次換乘線路、二次換乘線路等直達線路一致，有結果則輸出。若二次換乘仍沒有結果則輸出“沒有找到換乘次數(shù)少于2次的最優(yōu)換乘方案”，結束運算。對于問題二，需同時考慮公

4、交與地鐵線路，考慮到目前大眾心理對地鐵的便利性、快捷性的認同感，在考慮了換乘次數(shù)最少的情況下可優(yōu)先考慮地鐵換乘，其次再考慮公交換乘，其目的在于將行程的最大時間消耗不妨利用地鐵的快捷減少時間上的損耗。對于問題三，在已知站點間的步行時間的條件下，對環(huán)行路線的影響較大，我們可只考慮環(huán)行路線。三、模型的假設和符號說明（一）模型的假設：1 假設每路況和車況相同，不影響公交的正常運行，并且不考慮公交線路的運輸能力的限制及擁擠影響；2 假設任意相鄰兩站點的距離相等，運行時間相同，等車時間相同；3 出行者總是按直達，1次換乘，2次換乘等的優(yōu)先順序選擇線路；4 基本參數(shù)設定： 相鄰公汽站平均行駛時間(包括停站時

5、間)： 3分鐘相鄰地鐵站平均行駛時間(包括停站時間)： 2.5分鐘公汽換乘公汽平均耗時： 5分鐘(其中步行時間2分鐘)地鐵換乘地鐵平均耗時： 4分鐘(其中步行時間2分鐘)地鐵換乘公汽平均耗時： 7分鐘(其中步行時間4分鐘)公汽換乘地鐵平均耗時： 6分鐘(其中步行時間4分鐘)公汽票價：分為單一票價與分段計價兩種，標記于線路后；其中分段計價的票價為：站：1元；站：2元；站以上：3元地鐵票價：3元（無論地鐵線路間是否換乘）（二）符號說明：表示第條路線，第個站點的站名；表示為始點站；表示為終點站；表示第條線路k站點的站數(shù)；表示第條線路的總站數(shù)；表示換乘的次數(shù)；分別表示第條路線為單一票價與分段計價；表示

6、在條線路上由站點到站點所需要的時間；表示在條線路上由站點到站點所需要的票價；四、模型的建立，算法及求解（一）換乘次數(shù)及線路選擇模型根據(jù)人們的出行習慣，在選擇從A站到B站的乘車路線時，首先會先看經(jīng)過A站的車是否有直接到B站的，若有，馬上會選擇直達車（圖1（a）；如果存在不止一條的直達線路，再考慮距離、時間、票價等綜合因素的乘車方案；如果沒有直達車，就會考慮一次換乘的乘車方案：即經(jīng)過A站的車與經(jīng)過B站的車有公共站點C嗎？如果有，則可以在公共站點C處轉車(圖1（b）)；如果沒有則又要考慮二次換乘的乘車方案，即乘坐經(jīng)過A點的車到某一站C下車，經(jīng)過C站點的車與經(jīng)過B站點的車是否有公共站點D，如果有就再到

7、D轉車，兩次轉車可到達B站(圖1（c）)；如果沒有，則需要三次換乘或三次以上才可到目的地。考慮到人們的心理、情緒等特點，可設 (人們換乘次數(shù)的最大容忍程度)，大連市89條線路，376個不同的車站，結果顯示直達的占7.17%，換乘一次的占53.38%，換乘兩次的占38.07%，換乘兩次找不到目標站的占1.37%。（可見四次之內(nèi)的換乘是比較合理的，超過四次的換乘是沒有意義的，不予以考慮）圖1 公交線路選擇圖問題一建模時，將同一線路的上行、下行看作兩條線路，通過對線路重新命名可以區(qū)分。按照人們出行乘車的心理特點，本文提出換乘次數(shù)及線路選擇模型，通過此模型尋找經(jīng)過始點站和終點站的各線路集合，再比較兩集

8、合是否有交點，從而選擇是否通過直達還是換乘的線路到達終點站。即：（1）設始點站、終點站的線路，分別建立經(jīng)過這兩站點的所有線路的集合： （2）判斷兩集合和是否有公共交點：1若，則從始點站r1到終點站r2可直達且A中元素為可選路線。2。若，則表明從始點站r1到終點站r2不可直達，必須通過換乘方法才能達到終點站。令 (其中表示可與直達的所有站點所在集合) （1）、若，則通過換乘一次可到達終點站，B中的點為換乘站點，并可確定線路，該過程可以建模下去（2）、若，則表明要到終點站，必須換乘2次以上才能到達，運用上述原理，找出從ri可直達或經(jīng)過一次換乘的線路集合，再判斷兩集合的是否存在交集：令 （其中表示r

9、i可直達或經(jīng)過一次換乘的線路集合）然后再考慮與的交集情況，若不為空集，則換乘2次可到達終點站；若為空集，則必須換乘3次或3次以上通過分別考慮上、下行與環(huán)行的不同，可得到由站點經(jīng)線路到達站點所需時間及費用分別為 （其中、分別表示取整）（二）最佳線路模型通過確定換乘次數(shù)及線路選擇模型后，可能存在換乘次數(shù)相同的多種路線選擇的問題，為了選擇最佳線路，現(xiàn)建立該模型。 在換乘次數(shù)相同的情況下確定此模型，所要考慮的問題是，所花時間與費用最小，現(xiàn)設為由導的最小換乘次數(shù)，則第種選擇所花時間為：所需費用為（這里考慮到票價形式的不同）： （其中：a表示公共汽車換乘時間， 表示取整） 再通過最小花費函數(shù)F（時間，票價

10、），考慮到雙目標函數(shù)，進行對時間和費用進行權重，其中表示在第種選擇下，第次乘車行駛的站點數(shù)，進行量綱歸一化（這里設最大時間為180分鐘，最大費用為8元），從而最佳路線為使最小的而優(yōu)化問題的解。 （二）模型的算法（基于廣度優(yōu)先遍歷的公交換乘的搜索算法）由于模型二的有關數(shù)據(jù)來源于模型一，因此合并模型一與模型二的算法為：步驟1：輸入乘車的起始站點和目的站點，確定公交數(shù)據(jù)庫。步驟2：搜索公交數(shù)據(jù)庫，經(jīng)過起始站點和目的站點的公交線路保留為、 。步驟3：判斷與是否相交，若相交則確定交點（可供選擇的直達路線）并記錄起始點和目的站點在該線路上是第幾站；若不交，則轉入下一步。步驟4：搜索公交數(shù)據(jù)庫，將公交線路，

11、所包含的公交站點存為可能的公交換站點集A2,比較A2與B2是否相交,若相交,則確定交點(可供選擇的中轉站)并記錄該點所在的公交線路及該站點在線上的第幾站.進一步計算乘車站數(shù),時間與費用,并記錄.（三）模型的求解根據(jù)上述模型與求解，用Matlab編制程序輸入給定的6對起始站點，先直接調(diào)用程序1(附錄1)判斷是否為直達，由程序的結果可以知道6對站點均不能直達，因此就調(diào)用程序2(附錄2)，程序結果顯示一次轉乘可以到達終點的有:(1)、S3359S1828；(共11種選擇)(3)、S0971S0485: (共13種選擇)(4)、S0008S0073； (共101種選擇)(6)、S0087S3676；

12、(共2種選擇)把程序中所有結果進行處理，對總站數(shù)，時間，費用進行升序排序，得出如(圖表1)表格，包括了開始點S3359轉乘一次到達終點S1828的所有線路，并包括每條線路的各種因素，全部結果可以查看(附錄3)，運用最佳線路選擇模型原理，首先考慮總站數(shù)最少，如果總站數(shù)相同，接著就考慮時間的長短，選擇時間最短，接著考慮費用最小。(圖2)由上圖可以看到總站數(shù)最少為32，時間最短為101分鐘，費用最少為3元， 用最佳線路模型中最小花費可以選擇出最優(yōu)路線有兩條分別如下:其余路線的最優(yōu)線路同理可得，所有一次轉乘的最優(yōu)線路結果見附錄4通過程序的調(diào)用，運行 (2)、S1557S0481 ，(5)、S0148S

13、0485，可知兩對站點不能轉乘一次到到達，故要二次轉乘，調(diào)用程序3(附錄5)，整理結果得到如(圖3)和(圖4)的線路表示圖: (2)、S1557S0481所有路線:(圖3)(5)、S0148S0485所有路線:(圖4)同理利用最佳路線的選擇方法，可得:(2)、S1557S0481最優(yōu)路線:(2)、S0148S0485最優(yōu)路線:由于這時已經(jīng)把送給6對起始站終到站之間的最佳路線找出了，不用繼續(xù)轉乘。如果還要轉乘，就要繼續(xù)利用程序求解，但是現(xiàn)實生活中一般不會轉乘超過兩次。問題二在日常生活中，人們乘坐的公共交通工具往往包括公汽，地鐵等，特別是在大城市，交通路網(wǎng)相對發(fā)達，交通工具類型相對較多，各種交通工

14、具又各自有其特點如：地鐵可以有效控制時間，快速便捷，但一般不在家門口，必須通過步行或乘坐其他交通工具才能到達；而公汽站點多，線路線網(wǎng)發(fā)達，但速度忙，容易受路況影響，究竟選擇何種交通工具乘坐，逐漸成為人們必須考慮的問題。現(xiàn)同時考慮公汽與地鐵兩種交通工具，要研究任意兩站點通過何種交通工具選擇最佳線路的問題。在此問題上也是通過從始點站能否找到直達線路或者換乘來到達終點站，如下圖5：地鐵站地鐵站公汽站公汽站終點站 圖5現(xiàn)考慮只可直達或者換乘一次，有以下幾種情形：（一）若始點站為地鐵站，則有：（二）若始點站為公汽站，則有（三）若出現(xiàn)換乘兩次或兩次以上，同理可得。根據(jù)上述分析，運用換乘次數(shù)及線路選擇模型、

15、廣度優(yōu)先遍歷的公交換乘的搜索算法來求出任意兩站點之間是否存在交集，通過判斷A是否存在集合，可得到是否有直達或換乘的次數(shù)，從而選擇最佳路線。若換乘次數(shù)相同時，可能存在多種線路可供選擇條件下，乘客根據(jù)個人的需要選擇時間最小或者票價最少或者時間和票價的最優(yōu)組合,通過對影響路線選擇的主要因素如時間、票價等因素進行權重。有以下幾種情形：1.當存在直達時，比較地鐵與公汽在相同站點數(shù)與不同站點數(shù)所需要的時間，票價，從而選擇最佳線路；2.當要換乘時，比較地鐵與公汽在相同站點數(shù)與不同站點數(shù)所需要的時間，票價，從而選擇最佳線路；3.當既存在直達又有換乘時，比較地鐵與公汽在相同站點數(shù)與不同站點數(shù)所需要的時間，票價，

16、從而選擇最佳線路；從上述分析，確定時間，票價模型如下：（其中g,q分別表示是乘公汽，地鐵，）（其中d=0表示只乘地鐵直達，否則為1，表示取整）再定義最小花費函數(shù)F（時間，票價），對時間和票價進行權重,并進行量綱歸一化（這時設最大時間為180分鐘，最大費用為8元）：利用上述模型和算法，可得到對站點的線路選擇情況，如下圖： 由上述圖表，可知(3)、S0971S0485，(4)、S0008S0073 ， (5)、S0148S0485通過換乘地鐵比較節(jié)省時間，如果(1)、S3359S1828 ， (2)、S1557S0481 ， (6)、S0087S3676，選擇換乘地鐵的話所要花費的時間比坐公交車更

17、慢，問題三從上述問題可以發(fā)現(xiàn)只有當不同線路之間具有公共站點時才能夠進行轉車，這樣計算出來的結果有時并不符合實際情況，比如在實際出行時只需換乘二次便可到達目的地，但計算出來的結果卻需要換乘三次或四次。出現(xiàn)這種情況的原因是忽視了現(xiàn)實生活中人們步行小段距離再轉車的現(xiàn)象。具體地說，人們在轉車時，并不是下車后直接在下車的站點處轉車，往往需步行一小段距離到附近的站點去轉車。人們選擇這種方式通常可以減少換乘次數(shù)，而且這種換車方式也是由站點的分布情況所決定的。緊鄰是一個半定量的距離概念，用以描述公交站點空間位置上的距離關系，通常是根據(jù)人們?yōu)榱晳T和平均公交路段長度來決定的。緊鄰站點的存在使得人們在選擇換乘路線時

18、多了一個考慮，就是如果在某一點下車后沒有直接換乘的車次，還可以考慮附近的站點是否有換乘車次。根據(jù)這種思想， 本文對上面的算法進行了改進，即在換乘時，加入對緊鄰站點的判斷和分析。這種算法更加符合站點的分布情況以及人們出行時的實際選擇情況。從前面的公交乘客出行心理調(diào)查統(tǒng)計表可以看出,換乘次數(shù)最少是公交乘客出行時考慮的第一重要因素,所以就以換乘次數(shù)最少作為最優(yōu)路徑算法的第一約束目標,而出行耗時最少雖是公交乘客考慮的第二重要因素,但因為其難以準確測算,所以選擇易于量化的出行距離最短作為第二約束目標。可以通過建立最小成本路徑模型,得到最佳線路.然后運用最優(yōu)路徑改進算法的基本思想為分別從起點A、終點B出發(fā)

19、,通過比較公交網(wǎng)絡上各車站的可換乘車站,追索A到B的可能路徑,然后比較各可能路徑的距離,來確定最小成本路徑。設S(I)(I=1,2,m)(m為正整數(shù))為經(jīng)過A或其附近的線路集。T(J)(J= 1,2,n)(n為正整數(shù))為經(jīng)過B或其附近的線路集。E(I,U)(U= 1,2,p,p為正整數(shù))為線路S(I)上的站點。F(J,V)(V= 1,2,q,q為正整數(shù))為線路T(J)上的站點。R(K)(K= 1,2,g)(g為正整數(shù))為經(jīng)過E(I,U)的線路。Y(O)(O= 1,2,z)(z為正整數(shù))為經(jīng)過F(J,V)的線路。G(K,W)(W= 1,2,i)(i為正整數(shù))為線路R(K)上的站點。L(O,X)(

20、X= 1,2,j)(j為正整數(shù))為線路Y(O)上的站點。d(m,n)表示站點m與站點n之間沿道路的距離。w表示乘客在換車時步行距離的最大心理承受值,它是一個人為干預的經(jīng)驗值,與公交站點間的平均長度呈線性相關。對于站點m與站點n之間的緊鄰關系,可以用一個不等式來表示:d(m,n) <=w。根據(jù)經(jīng)驗表明,即使在上海這樣的大都市的公交網(wǎng)絡上,換4次車即乘坐5條線路的公交車,方可到達目的地的情況都是很少發(fā)生的6。所以根據(jù)杭州市公交線路的實際情況,本文認為三次以內(nèi)的轉車是比較合理的,超過三次的轉車的情況在這里不予考慮。算法的步驟如下:(1)輸入乘車的起始站點A及目的站點B;(2)求經(jīng)過站點A的所有

21、線路集S(I)和經(jīng)過站點B的所有線路集T(J) ;(3)判斷S(I) =T(J)嗎?如果有,則找到了從站點A到站點B的直達線路S(I)即T(J) ,輸出結果,結束運算,如果沒有則進行下一步。(4)求線路S(I)上的站點E(I,U)以及線路T(J)上的站點F(J,V) ; (5)判斷是否存在相同站點,即E(I,U) =F(J,V) ,或者存在緊鄰站點,即滿足d(E,F) <=w;如果滿足E(I,U) =F(J,V) ,則線路S(I),T(J)即為一次轉車的線路,E(I,U)即為轉車站點且換車時不用更換站點;如果滿足E(I,U)F(J,V)但滿足d(E,F) <=w,則線路S(I),T

22、(J)即為一次轉車的線路,E(I,U)即為轉車站點但換車時要步行到緊鄰站點F(J,V)。如果沒有,再執(zhí)行下面。(6)求經(jīng)過E(I,U)的線路集R(K) ,經(jīng)過F(J,V)的線路集Y(O) ;(7)判斷R(K) =Y(O)嗎?如果有,則線路S(I),R(K),T(J)為兩次換車的線路,換車站點為E(I,U)和F(J,V) ,輸出結果,結束運算;如果沒有,則執(zhí)行下面。(8)求線路R(K)上的站點G(K,W)和線路Y(O)上的站點L(O,X) ;(9)判斷是否存在相同站點,即G(K,W) =L(O,X) ,或者存在緊鄰站點,即滿足d(G,L) <=w;如果滿足G(K,W) =L(O,X) ,則

23、線路S(I),R(K),Y(O),T(J)即為三次轉車的線路,E(I,U),G(K,W),F(J,V)即為轉車站點,且換車時不用更換站點;如果滿足G(K,W)L(O,X)但滿足d(G,L) <=w,則在站點G(K,W)轉車時要步行到緊鄰站點L(O,X)。在上述情況中,滿足條件的線路可能不止一種,這時再計算每種方案的乘車距離,取距離最短的乘車方案,輸出結果。五、模型的檢驗我們的模型主要功能就是查找兩個任意站點之間的最優(yōu)線路，通過求解問題一和問題二后，把模型找到的所有路線，通過在原數(shù)據(jù)中選擇性對照，檢驗可得找到的線路是可令兩站點通過線路可達，接著比較各條路線的最優(yōu)性，得到的最優(yōu)路線就是模型找到的最優(yōu)路線。通過檢驗，模型的結果和現(xiàn)實是吻合的，表明模型準確率高穩(wěn)定性好。六、模型的評價和改進優(yōu)點：1僅考慮公汽線路的情況下，為了得出任意兩站點之間的最佳線路，運用換乘次數(shù)及線路選擇模型，通過對各線路各站點分析，比較經(jīng)過任意兩站點的線路集合，從而得到可直達線路或換乘的次數(shù)以及公共站點。該模型從數(shù)集角度分析，容易判斷任意兩集合是否存在交點，易于計算，效果理想。2.根據(jù)換乘次數(shù)及線路選擇模型，利用廣度優(yōu)先遍