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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上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ì)所作的模型

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

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

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

5、： 相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)： 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ù)；分別

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

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

8、始點(diǎn)站和終點(diǎn)站的各線路集合，再比較兩集合是否有交點(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ò)一次換乘的線路集合，再判斷

9、兩集合的是否存在交集：令 （其中表示ri可直達(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ù)相同的多種路線選擇的問(wèn)題，為了選擇最佳線路，現(xiàn)建立該模型。 在換乘次數(shù)相同的情況下確定此模型，所要考慮的問(wèn)題是，所花時(shí)間與費(fèi)用最小，現(xiàn)設(shè)為由導(dǎo)的最小換乘次數(shù)，則第種選擇所花時(shí)間為：所需費(fèi)用為（這里考慮到票價(jià)形式的不同）： （其中：a表示公共汽車(chē)換乘時(shí)間， 表示取

10、整） 再通過(guò)最小花費(fèi)函數(shù)F（時(shí)間，票價(jià)），考慮到雙目標(biāo)函數(shù)，進(jìn)行對(duì)時(shí)間和費(fèi)用進(jìn)行權(quán)重，其中表示在第種選擇下，第次乘車(chē)行駛的站點(diǎn)數(shù)，進(jìn)行量綱歸一化（這里設(shè)最大時(shí)間為180分鐘，最大費(fèi)用為8元），從而最佳路線為使最小的而優(yōu)化問(wèn)題的解。 （二）模型的算法（基于廣度優(yōu)先遍歷的公交換乘的搜索算法）由于模型二的有關(guān)數(shù)據(jù)來(lái)源于模型一，因此合并模型一與模型二的算法為：步驟1：輸入乘車(chē)的起始站點(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)入下一步

11、。步驟4：搜索公交數(shù)據(jù)庫(kù)，將公交線路，所包含的公交站點(diǎn)存為可能的公交換站點(diǎn)集A2,比較A2與B2是否相交,若相交,則確定交點(diǎn)(可供選擇的中轉(zhuǎn)站)并記錄該點(diǎn)所在的公交線路及該站點(diǎn)在線上的第幾站.進(jìn)一步計(jì)算乘車(chē)站數(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種

12、選擇)(6)、S0087S3676； (共2種選擇)把程序中所有結(jié)果進(jìn)行處理，對(duì)總站數(shù)，時(shí)間，費(fèi)用進(jìn)行升序排序，得出如(圖表1)表格，包括了開(kāi)始點(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é)果見(jiàn)附錄4通過(guò)程序的調(diào)用，運(yùn)行 (2)、S15

13、57S0481 ，(5)、S0148S0485，可知兩對(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èn)題二在日常生活中，人們乘坐的公共交通工具往往包括公汽，地鐵等，特別是在大城市，交通路網(wǎng)相對(duì)

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

15、上述分析，運(yùn)用換乘次數(shù)及線路選擇模型、廣度優(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í)，比較地鐵與公汽在相同

16、站點(diǎn)數(shù)與不同站點(diǎn)數(shù)所需要的時(shí)間，票價(jià)，從而選擇最佳線路；從上述分析，確定時(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，選擇

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

18、緊鄰站點(diǎn)的存在使得人們?cè)谶x擇換乘路線時(shí)多了一個(gè)考慮，就是如果在某一點(diǎn)下車(chē)后沒(méi)有直接換乘的車(chē)次，還可以考慮附近的站點(diǎn)是否有換乘車(chē)次。根據(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)算

19、法的基本思想為分別從起點(diǎn)A、終點(diǎn)B出發(fā),通過(guò)比較公交網(wǎng)絡(luò)上各車(chē)站的可換乘車(chē)站,追索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ù))

20、為線路R(K)上的站點(diǎn)。L(O,X)(X= 1,2,j)(j為正整數(shù))為線路Y(O)上的站點(diǎn)。d(m,n)表示站點(diǎn)m與站點(diǎn)n之間沿道路的距離。w表示乘客在換車(chē)時(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次車(chē)即乘坐5條線路的公交車(chē),方可到達(dá)目的地的情況都是很少發(fā)生的6。所以根據(jù)杭州市公交線路的實(shí)際情況,本文認(rèn)為三次以?xún)?nèi)的轉(zhuǎn)車(chē)是比較合理的,超過(guò)三次的轉(zhuǎn)車(chē)的情況在這里不予考慮。算法的步驟如下:(1)輸入乘車(chē)的起始站點(diǎn)A及目的站

21、點(diǎn)B;(2)求經(jīng)過(guò)站點(diǎn)A的所有線路集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)算,如果沒(méi)有則進(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),即滿(mǎn)足d(E,F) =w;如果滿(mǎn)足E(I,U) =F(J,V) ,則線路S(I),T(J)即為一次轉(zhuǎn)車(chē)的線路,E(I,U)即為轉(zhuǎn)車(chē)站點(diǎn)且換車(chē)時(shí)不用更換站點(diǎn);如果滿(mǎn)足E(I,U)F(J,V)但滿(mǎn)足d(E,F) =w,則線

22、路S(I),T(J)即為一次轉(zhuǎn)車(chē)的線路,E(I,U)即為轉(zhuǎn)車(chē)站點(diǎn)但換車(chē)時(shí)要步行到緊鄰站點(diǎn)F(J,V)。如果沒(méi)有,再執(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)為兩次換車(chē)的線路,換車(chē)站點(diǎn)為E(I,U)和F(J,V) ,輸出結(jié)果,結(jié)束運(yùn)算;如果沒(méi)有,則執(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),即滿(mǎn)足d(G,L) =w;如果滿(mǎn)足G(K,W) =L(O,X)

23、 ,則線路S(I),R(K),Y(O),T(J)即為三次轉(zhuǎn)車(chē)的線路,E(I,U),G(K,W),F(J,V)即為轉(zhuǎn)車(chē)站點(diǎn),且換車(chē)時(shí)不用更換站點(diǎn);如果滿(mǎn)足G(K,W)L(O,X)但滿(mǎn)足d(G,L) =w,則在站點(diǎn)G(K,W)轉(zhuǎn)車(chē)時(shí)要步行到緊鄰站點(diǎn)L(O,X)。在上述情況中,滿(mǎn)足條件的線路可能不止一種,這時(shí)再計(jì)算每種方案的乘車(chē)距離,取距離最短的乘車(chē)方案,輸出結(jié)果。五、模型的檢驗(yàn)我們的模型主要功能就是查找兩個(gè)任意站點(diǎn)之間的最優(yōu)線路，通過(guò)求解問(wèn)題一和問(wèn)題二后，把模型找到的所有路線，通過(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)先遍