07年高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、過(guò)比較公交網(wǎng)絡(luò)上各車站的可換乘車站,追索a到b的可能路徑,然后比較各可能路徑的距離,來(lái)確定最小成本路徑。設(shè)s(i)(i=1,2,m)(m為正整數(shù))為經(jīng)過(guò)a或其附近的線路集。t(j)(j= 1,2,n)(n為正整數(shù))為經(jīng)過(guò)b或其附近的線路集。e(i,u)(u= 1,2,p,p為正整數(shù))為線路s(i)上的站點(diǎn)。f(j,v)(v= 1,2,q,q為正整數(shù))為線路t(j)上的站點(diǎn)。r(k)(k= 1,2,g)(g為正整數(shù))為經(jīng)過(guò)e(i,u)的線路。y(o)(o= 1,2,z)(z為正整數(shù))為經(jīng)過(guò)f(j,v)的線路。g(k,w)(w= 1,2,i)(i為正整數(shù))為線路r(k)上的站點(diǎn)。l(o,x)(x=

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

21、集s(i)和經(jīng)過(guò)站點(diǎn)b的所有線路集t(j) ;(3)判斷s(i) =t(j)嗎?如果有,則找到了從站點(diǎn)a到站點(diǎn)b的直達(dá)線路s(i)即t(j) ,輸出結(jié)果,結(jié)束運(yùn)算,如果沒有則進(jìn)行下一步。(4)求線路s(i)上的站點(diǎn)e(i,u)以及線路t(j)上的站點(diǎn)f(j,v) ; (5)判斷是否存在相同站點(diǎn),即e(i,u) =f(j,v) ,或者存在緊鄰站點(diǎn),即滿足d(e,f) <=w;如果滿足e(i,u) =f(j,v) ,則線路s(i),t(j)即為一次轉(zhuǎn)車的線路,e(i,u)即為轉(zhuǎn)車站點(diǎn)且換車時(shí)不用更換站點(diǎn);如果滿足e(i,u)f(j,v)但滿足d(e,f) <=w,則線路s(i),t(j

22、)即為一次轉(zhuǎn)車的線路,e(i,u)即為轉(zhuǎn)車站點(diǎn)但換車時(shí)要步行到緊鄰站點(diǎn)f(j,v)。如果沒有,再執(zhí)行下面。(6)求經(jīng)過(guò)e(i,u)的線路集r(k) ,經(jīng)過(guò)f(j,v)的線路集y(o) ;(7)判斷r(k) =y(o)嗎?如果有,則線路s(i),r(k),t(j)為兩次換車的線路,換車站點(diǎn)為e(i,u)和f(j,v) ,輸出結(jié)果,結(jié)束運(yùn)算;如果沒有,則執(zhí)行下面。(8)求線路r(k)上的站點(diǎn)g(k,w)和線路y(o)上的站點(diǎn)l(o,x) ;(9)判斷是否存在相同站點(diǎn),即g(k,w) =l(o,x) ,或者存在緊鄰站點(diǎn),即滿足d(g,l) <=w;如果滿足g(k,w) =l(o,x) ,則線路

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