2007數(shù)模競(jìng)賽B題,城市公交線路選擇優(yōu)化模型論文

PAGEPAGE2城市公交線路優(yōu)化模型摘要本文針對(duì)城市公交線路選擇問(wèn)題建立了兩個(gè)模型，一個(gè)是基于集合尋線算法模型，另一個(gè)是圖論模型。基于集合尋線算法模型中，首先固定換乘次數(shù)，通過(guò)集合論的相關(guān)知識(shí)把確定換乘點(diǎn)的具體位置,轉(zhuǎn)化成確定一些集合間的交集，從而建立集合尋線算法，再根據(jù)集合相關(guān)公式，得到所有可行線路；進(jìn)一步考慮時(shí)間和費(fèi)用等因素，對(duì)可行線路進(jìn)行處理比較，得出最佳線路。圖論模型中，通過(guò)圖論的知識(shí)將整個(gè)北京市交通線路構(gòu)建出一個(gè)有向圖，每個(gè)站點(diǎn)與有向圖的頂點(diǎn)一一對(duì)應(yīng)，同一線路上的相鄰站點(diǎn)對(duì)應(yīng)為有向邊，通過(guò)不同目標(biāo)（時(shí)間、費(fèi)用）給有向圖進(jìn)行不同的賦權(quán)，分別將不同目標(biāo)轉(zhuǎn)化為賦權(quán)有向圖尋找最短有向路，根據(jù)最短路徑算法，得到最佳線路。最后綜合評(píng)價(jià)了兩個(gè)模型的優(yōu)缺點(diǎn)。關(guān)鍵詞：集合尋線算法；最短路算法；換乘點(diǎn)；賦權(quán)有向圖

1問(wèn)題提出 北京將于2008年舉行奧運(yùn)會(huì)，屆時(shí)會(huì)有從四面八方而來(lái)觀看奧運(yùn)比賽觀眾，其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱(chēng)公交，包括公汽、地鐵等）出行。隨著現(xiàn)代化的步伐加快，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問(wèn)題。在現(xiàn)實(shí)生活中，公交線路以及其相應(yīng)經(jīng)過(guò)的站點(diǎn)非常多且密，乘客往往難以知道如何選擇公交線路，所以針對(duì)市場(chǎng)需求以及公交線路選擇上的問(wèn)題，某公司準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)。該系統(tǒng)的核心在于線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)，滿足查詢者的各種不同需求。根據(jù)附錄1、附錄2，解決如下問(wèn)題：1.僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用建立的模型與算法，求出以下6對(duì)起始站→終到站之間的最佳線路。(1)S3359→S1828(2)S1557→S0481(3)S0971→S0485(4)S0008→S0073(5)S0148→S0485(6)S0087→S36762.同時(shí)考慮公汽與地鐵線路，解決以上問(wèn)題。3.假設(shè)知道所有站點(diǎn)之間步行時(shí)間，給出任意兩站點(diǎn)之間線路選擇的數(shù)學(xué)模型。2問(wèn)題分析為了研制開(kāi)發(fā)一個(gè)解決公交線路最佳選擇（即乘客在多條公交線路中根據(jù)自己的需求獲得最適合自己的線路）問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)，只要乘客給出起點(diǎn)站和終點(diǎn)站兩個(gè)站點(diǎn)，系統(tǒng)就給出最佳交通線路，使得公眾出行更加通暢、便利。而問(wèn)題核心是如何在多條線路選擇中獲得最佳線路。乘客往往不能只乘一輛公交便直達(dá)終點(diǎn)，而是要通過(guò)換乘一輛或多輛公交才能到達(dá)終點(diǎn)站，但若多次換乘公交，可能導(dǎo)致乘客所花時(shí)間及其費(fèi)用的增加，更會(huì)給乘客造成不便。在奧運(yùn)將在北京舉行的背景下，我們知道乘客前往觀看奧運(yùn)比賽時(shí)，主要注重的是能否及時(shí)到達(dá)，所以在為乘客選擇線路時(shí)，力求乘坐花費(fèi)的時(shí)間盡可能少以及路程盡可能短的線路，同時(shí)考慮換乘車(chē)輛以及乘車(chē)費(fèi)用盡量少的最佳線路，而現(xiàn)實(shí)是很難同時(shí)滿足上面三個(gè)目標(biāo)的。為了使問(wèn)題簡(jiǎn)單化，我們分別以乘車(chē)時(shí)間、乘車(chē)費(fèi)用以及換乘次數(shù)為目標(biāo)函數(shù)，得到各自的較優(yōu)線路，再通過(guò)對(duì)比，有效地處理這些線路，最終得出查詢系統(tǒng)給出的結(jié)果。3模型準(zhǔn)備3.1模型假設(shè)1.假設(shè)同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過(guò)地鐵站換乘（無(wú)需支付地鐵費(fèi)）；2.假設(shè)所有交通線路都不出現(xiàn)停運(yùn)或者線路變動(dòng)；3.假設(shè)公汽的環(huán)行行駛線路是單向的。3.2符號(hào)約定：相鄰公汽站平均行駛時(shí)間（包括停站時(shí)間），；：相鄰地鐵站平均行駛時(shí)間（包括停站時(shí)間），；：公汽換乘公汽平均耗時(shí)，（其中步行時(shí)間2）；：地鐵換乘地鐵平均耗時(shí)，（其中步行時(shí)間2）；：地鐵換乘公汽平均耗時(shí)，（其中步行時(shí)間4）；：公汽換乘地鐵平均耗時(shí)，（其中步行時(shí)間4）；：交通工具與交通工具換乘所需時(shí)間；：地鐵票價(jià)，元；：換乘次數(shù)；：乘客在可選擇的從起始站到終點(diǎn)站線路中第條線路的換乘點(diǎn)（包括始點(diǎn)和終點(diǎn)），，為起點(diǎn)，為終點(diǎn)；：乘客從第換乘點(diǎn)上車(chē)到第換乘點(diǎn)的下車(chē)所付的票價(jià)，；：公交車(chē)從第換乘點(diǎn)到第換乘點(diǎn)經(jīng)過(guò)的站點(diǎn)數(shù)（含第換乘點(diǎn)）；：公交車(chē)在第線路上從第換乘點(diǎn)到第換乘點(diǎn)線路；：公交車(chē)在第線路上從第換乘點(diǎn)到第換乘點(diǎn)經(jīng)過(guò)每站所需時(shí)間；：只換乘次乘客從起始站到終點(diǎn)站選擇第條線路所需要的總時(shí)間；：只換乘次乘客從起始站到終點(diǎn)站選擇第條線路所需要的總費(fèi)用。4基于集合尋線算法的模型4.1集合尋線算法的建立現(xiàn)實(shí)乘客換乘的次數(shù)很小，公司在設(shè)計(jì)一個(gè)城市公交線路時(shí)，為了使線路更合理，一般不會(huì)使乘客要通過(guò)多次換乘（超過(guò)3次）才到達(dá)終點(diǎn)站。則不妨假設(shè)換乘次數(shù)，。我們可以看到問(wèn)題中關(guān)鍵要解決的是找出換乘點(diǎn)的具體位置，顯然換乘點(diǎn)是公交線路的交叉點(diǎn)，或者說(shuō)站點(diǎn)至少要有兩條公交線路經(jīng)過(guò)。由于公交線路不是一條直線段或者有一定幾何規(guī)律的曲線，所以我們通過(guò)代數(shù)的相關(guān)知識(shí)，把具有同一屬性的站點(diǎn)放入同一集合中，這樣就把問(wèn)題轉(zhuǎn)化成代數(shù)問(wèn)題?；诖怂枷?，我們建立以下集合尋線算法：步驟1：找出經(jīng)過(guò)終點(diǎn)站的所有公交線路存放到集合，以及這些線路經(jīng)過(guò)的所有站點(diǎn)存放到集合。步驟2：找出經(jīng)過(guò)起始站的所有公交線路，存放到集合，以及這些公交線路經(jīng)過(guò)的站點(diǎn)存放到集合。步驟3：判斷和的關(guān)系：1．若，即存在，使得，表示起始站A到終點(diǎn)站B之間有一條或幾條直達(dá)線路，乘客不必?fù)Q乘公交車(chē)，算出這些直達(dá)線路各自所需要的時(shí)間和票價(jià)；通過(guò)比較大小，得到該情況下的乘車(chē)最少時(shí)間和最少費(fèi)用，以及其相應(yīng)的線路。2．若，則說(shuō)明起始站與終點(diǎn)站之間不存在公交車(chē)直達(dá)的情況，只能通過(guò)換乘才能到達(dá)終點(diǎn)站，則要尋找換乘點(diǎn)。步驟4：查找公交線路與公交線路的所有共同站點(diǎn)，存放到集合。集合中的元素是換乘點(diǎn)。步驟5：判斷集合：1．如果集合，即乘客可以通過(guò)一次換乘就能到達(dá)終點(diǎn)站。記錄換乘點(diǎn)及其相應(yīng)線路。2．如果集合，即乘客不能通過(guò)一次換乘到達(dá)終點(diǎn)站，則要選取新的起始點(diǎn)。步驟6：選取新的起始點(diǎn)：從集合中任取一站點(diǎn)（），即遍歷集合中所有的元素，以站點(diǎn)代替原來(lái)的起始站。轉(zhuǎn)到步驟2，這樣就能找出所有經(jīng)過(guò)兩次換乘的線路。步驟7：通過(guò)重復(fù)上面的6個(gè)步驟可得經(jīng)過(guò)次換乘的所有可能線路。4.2模型的建立4.2.1時(shí)間及我們固定換乘次數(shù)，通過(guò)集合尋線算法，得到通過(guò)次換乘的所有可達(dá)線路，再對(duì)這些線路進(jìn)行下面的運(yùn)算：從起點(diǎn)站到終點(diǎn)站，：經(jīng)過(guò)起點(diǎn)站的第條公交線路；：經(jīng)過(guò)終點(diǎn)站的第條公交線路；只通過(guò)次換乘到達(dá)可選擇的線路共有條，設(shè)第條乘坐線路的換乘點(diǎn)為,，為起點(diǎn)，為終點(diǎn),第條線路上從第換乘點(diǎn)到第換乘點(diǎn)線路為，其途徑的站點(diǎn)數(shù)，，所付的票價(jià),相鄰站點(diǎn)平均行駛時(shí)間，第個(gè)換乘點(diǎn)需要的換乘時(shí)間為。1）只考慮公汽線路：a.第線路所需要的總時(shí)間：（1）其中，表示公汽相鄰兩站的平均行使時(shí)間，汽車(chē)換乘需要的平均耗時(shí)。b.第線路所需要的總費(fèi)用：（2）其中,2）同時(shí)考慮公汽與地鐵線路：a.第線路所需要的總時(shí)間：（3）其中，b.第線路所需要的總費(fèi)用：（4）3）同時(shí)考慮公汽、地鐵和步行時(shí)間：a.第線路所需要的總時(shí)間：（5）其中，b.第線路所需要的總費(fèi)用：（6）注意：由于步行不需費(fèi)用，所以要給個(gè)步行線路約束：步行時(shí)間不超過(guò)。4.2.2固定了換乘次數(shù)，確立以下目標(biāo)：1）時(shí)間目標(biāo)：，即找出只通過(guò)次換乘乘車(chē)時(shí)間最少的最佳線路及其時(shí)間；2）費(fèi)用目標(biāo)：，即找出只通過(guò)次換乘乘車(chē)費(fèi)用最少的最佳線路及其費(fèi)用。4.由于公交線路很多，在同一目標(biāo)下，乘客可能還有較多條最佳線路的選擇，那么我們不可能把所有最佳線路給乘客選擇，乘客也不能接受，所以我們可根據(jù)下面幾點(diǎn)進(jìn)行處理：1）盡量滿足時(shí)間最短的情況下，選擇費(fèi)用最少的線路；2）盡量不要把換乘站點(diǎn)安排在熱門(mén)站點(diǎn)（即較多線路交叉點(diǎn)，不妨設(shè)最佳線路大于5條時(shí)，通過(guò)查找經(jīng)過(guò)換乘站點(diǎn)的所有交通線路，遍歷所有換乘站點(diǎn)，記錄每一個(gè)站點(diǎn)對(duì)應(yīng)的，較大就是熱門(mén)站點(diǎn)）；3）可以隨機(jī)抽取幾條給乘客，避免某條線路上過(guò)于繁忙；4）盡量不要把繁忙線路（累加每一條線路上所有站點(diǎn)對(duì)應(yīng)的得到較大的的線路為繁忙線路）安排為最佳線路，避免交通阻塞；4.2.4算法的由于所選的換乘次數(shù)最多兩次，所以此算法的時(shí)間復(fù)雜度為。5基于圖論的模型及其算法實(shí)現(xiàn)5.1圖論模型的建立以每個(gè)站點(diǎn)為頂點(diǎn)，若站點(diǎn)A到站點(diǎn)有公交線路并且A與為相鄰站點(diǎn)，則連一條到有向邊，根據(jù)所給的站點(diǎn)與線路我們建立一個(gè)得到一個(gè)有重邊的有向圖。一條公交線路就是的一條有向路。5.1.1以時(shí)間為目標(biāo)的線路模型1）僅考慮公汽線路對(duì)于有向圖，給每條有向邊都賦權(quán)c（相鄰公汽站點(diǎn)行駛時(shí)間），若站點(diǎn)有條公汽線路,則把A變成個(gè)點(diǎn)（相當(dāng)于增加了假想點(diǎn)，換乘公汽線路需要從變?yōu)椋?，的每?jī)身旤c(diǎn)都連對(duì)稱(chēng)有向邊，即這是一個(gè)階雙向完全有向圖（見(jiàn)圖1），每條邊都賦權(quán)e（公汽換乘公汽耗時(shí)），于是得到一個(gè)賦權(quán)有向圖。則任意兩公汽站點(diǎn)之間線路最少時(shí)間選擇問(wèn)題就轉(zhuǎn)化為求的對(duì)應(yīng)兩頂點(diǎn)的最短有向路問(wèn)題。圖1圖22）同時(shí)考慮公汽和地鐵對(duì)于有向圖，給每條公汽線路的有向邊都賦權(quán)c，每條地鐵線路的有向邊都賦權(quán)d，若站點(diǎn)B有條公交線路（其中條公汽線，條地鐵線）,則把B變成個(gè)頂點(diǎn)（相當(dāng)于增加了個(gè)假想點(diǎn)），邊為個(gè)頂點(diǎn)都連對(duì)稱(chēng)有向邊，它一個(gè)階完全雙向有向圖(見(jiàn)圖2)。間的邊賦權(quán)e（公汽換乘公汽耗時(shí)），間的邊賦權(quán)f（地鐵換乘地鐵耗時(shí)），的每點(diǎn)到的每點(diǎn)的邊賦權(quán)h（公汽換乘地鐵耗時(shí)），的每點(diǎn)到的每點(diǎn)的邊賦權(quán)g（地鐵換乘公汽耗時(shí)）。得到一個(gè)賦權(quán)有向圖。則任意兩公汽站點(diǎn)之間線路最少時(shí)間選擇問(wèn)題就轉(zhuǎn)化為求的對(duì)應(yīng)兩頂點(diǎn)的最短有向路問(wèn)題。3）同時(shí)考慮公交與步行時(shí)間在賦權(quán)有向圖中任兩點(diǎn)之間（除去假想點(diǎn)）連接對(duì)稱(chēng)有向邊，其邊賦權(quán)為，從而得到一個(gè)新的賦權(quán)有向圖。則任意兩公汽站點(diǎn)之間線路最少時(shí)間選擇問(wèn)題就轉(zhuǎn)化為求的對(duì)應(yīng)兩頂點(diǎn)的最短有向路問(wèn)題。5.1.2以費(fèi)用為目標(biāo)的線路模型1）僅考慮公汽的線路對(duì)于公交線路有向圖，給所經(jīng)過(guò)的同一公汽線路上的最大站點(diǎn)數(shù)的有向路進(jìn)行賦權(quán)：若單一票價(jià)，則賦權(quán)；若分段計(jì)價(jià)，則賦權(quán)，于是得到一個(gè)動(dòng)態(tài)賦權(quán)有向圖。則任意兩公汽站點(diǎn)之間線路最少費(fèi)用選擇問(wèn)題就轉(zhuǎn)化為求動(dòng)態(tài)賦權(quán)有向圖的對(duì)應(yīng)兩頂點(diǎn)的最短有向路問(wèn)題。2）同時(shí)考慮公汽和地鐵對(duì)于城市公交線路自然圖，給所經(jīng)過(guò)的同一公汽線路上的最大站點(diǎn)有向路進(jìn)行賦權(quán)：若單一票價(jià)，則賦權(quán)；若分段計(jì)價(jià)，則賦權(quán)，給所經(jīng)過(guò)的同一地鐵線路賦權(quán)，于是得到一個(gè)動(dòng)態(tài)賦權(quán)有向圖。于是任意兩公交站點(diǎn)之間線路最少費(fèi)用選擇問(wèn)題就轉(zhuǎn)化為求的對(duì)應(yīng)兩頂點(diǎn)的最短有向路問(wèn)題。3）同時(shí)考慮公交和步行由于步行是不需要費(fèi)用的，則在賦權(quán)圖是上任意兩點(diǎn)間連上對(duì)稱(chēng)的有向邊，但其權(quán)為0，顯然費(fèi)用最少為0，即步行到終點(diǎn)站。顯然是不合理的。故這里不能用賦權(quán)圖對(duì)應(yīng)線路。5.2最短路徑算法上面模型可以通過(guò)如算法實(shí)現(xiàn)：步驟1：通過(guò)計(jì)算式子（其中是終點(diǎn)，1是起點(diǎn)，終點(diǎn)的，從終點(diǎn)出發(fā)逐步向起點(diǎn)推算，是與相鄰，為已知點(diǎn)到終點(diǎn)的最小線路），得到最短路。此算法時(shí)間復(fù)雜度為：步驟2：通過(guò)對(duì)上面最短路經(jīng)過(guò)的站點(diǎn)的搜索和判斷，找出換乘點(diǎn)和換乘次數(shù)。步驟3：把步驟1最短路的權(quán)值與步驟2換乘目標(biāo)值相加，得到最終的最短路。6模型的求解 因?yàn)槌俗馁M(fèi)用比較少，乘客還是偏重與對(duì)時(shí)間的選擇，本文下面的求解都是以時(shí)間為目標(biāo)得到的最佳線路。6.1基于集合尋線算法模型的求解6.1.1僅考慮公汽 根據(jù)模型求解出問(wèn)題中通過(guò)模型得到了6對(duì)查詢點(diǎn)都不能通過(guò)一條線路直接到達(dá)，也得到1，2次換乘的最佳線路。見(jiàn)下表:S3359→S1828的不同線路乘車(chē)方案線路一換乘點(diǎn)1線路二換乘點(diǎn)2線路三總站數(shù)總時(shí)間總費(fèi)用換乘次數(shù)1L436下行S1784L16732101312L436下行S1784L21732101313L015下行S2903L027上行S1784L167下行2173324L015下行S2903L027上行S1784L217下行2173325L015下行S2903L201上行S1790L041上行2173326L015下行S2903L201上行S0458L041上行2173327L015下行S2903L201上行S1792L041上行2173328L015下行S2903L201上行S1783L041上行2173329L015下行S2903L201上行S1671L041上行21733210L123上行S2903L027上行S1784L167下行21733211L123上行S2903L027上行S1784L217下行21733212L123上行S2903L201上行S1790L041上行217332S1557→S0481的不同最優(yōu)解路線乘車(chē)方案線路一換乘點(diǎn)1線路二換乘點(diǎn)2線路三總站數(shù)總時(shí)間總費(fèi)用換乘次數(shù)1L084下行S1919L189下行S3186L46032106222L363下行S1919L189下行S3186L4603210622S0971→S0485的最佳路線乘車(chē)方案線路一換乘點(diǎn)1線路二換乘點(diǎn)2線路三總站數(shù)總時(shí)間總費(fèi)用換乘次數(shù)1L013下行S2184L417下行41128312L013上行S1690L140下行S2654L46932106323L013下行S2517L296上行S2480L41732106324L024下行S1690L140下行S2654L46932106325L094上行S1690L140下行S2654L46932106326L119下行S1690L140下行S2654L46932106327L263下行S1690L140下行S2654L4693210632S0008→S0073最佳路線乘車(chē)方案線路一換乘點(diǎn)1線路二換乘點(diǎn)2線路三總站數(shù)總時(shí)間總費(fèi)用換乘次數(shù)1L159下行S2683L058下行2683212L159下行S0291L058下行2683213L159下行S3614L058下行2683214L159下行S0491L058下行2683215L159下行S2559L058下行2683316L159下行S3315L058下行2683317L159下行S2559L464上行2683318L159下行S0400L474上行2683219L159下行S2633L474上行26832110L159下行S3053L474上行26832111L355下行S2263L345上行26832112L355下行S3917L345上行26832113L355下行S2303L345上行26832114L463下行S2083L057上行26832115L198上行S3766L296上行S2184L345196732S0148→S0485的不同最優(yōu)解路線乘車(chē)方案線路一換乘點(diǎn)1線路二換乘點(diǎn)2線路三總站數(shù)總時(shí)間總費(fèi)用換乘次數(shù)1L308上行S36L156上行S2210L417下行32106222L308上行S36L156上行S3332L417下行32106223L308上行S36L156上行S3351L417下行3210622S0087→S3676的最佳路線乘車(chē)方案線路一換乘點(diǎn)1線路二換乘點(diǎn)2線路三總站數(shù)總時(shí)間總費(fèi)用換乘次數(shù)1L454上行S3496L209下行2065212L021下行S0088L231環(huán)行S0427L462下行124632通過(guò)模型得到了6對(duì)查詢點(diǎn)都不能通過(guò)一條線路直接到達(dá)，換乘一次，兩次的較優(yōu)線路，根據(jù)乘客的不同的需求，確定目標(biāo)，選擇適合自己的最佳線路。例如上面從站點(diǎn)到站點(diǎn)，如果乘客不想多次換乘，那么他就可以選擇換乘一次的兩條線路的一條，如果乘客想盡快到達(dá)終點(diǎn)站，那么他可以選擇換乘兩次的10條線路中的一條。6.1.2同時(shí)考慮公汽和地鐵我們先算出問(wèn)題中6對(duì)查詢點(diǎn)一定上要一次地鐵的最佳線路見(jiàn)表3：表3乘坐一次地鐵的最佳線路始點(diǎn)→終點(diǎn)公汽線路一換乘點(diǎn)地鐵線路地鐵起點(diǎn)地鐵終點(diǎn)公汽線路二換乘點(diǎn)時(shí)間費(fèi)用S3359→S1828線路超過(guò)二次換乘，無(wú)法提供具體線路S1557→S0481L084下行S0978T2D32D24L516上行S0537116.55S0971→S0485L094上行S0567T1D1D20L417下行S207999.55S0008→S0073L159下行S2633T1D13S12L057上行S060975.55S0148→S0485L024下行S1487T1D2D20L417下行S2079915S0087→S3676——T2D27D36——363 再與只考慮公汽的最佳線路進(jìn)行比較，選擇時(shí)間最短的，得到S3359→S1828，S1557→S0481，S0008→S0073只乘坐公汽，S0971→S0485，S0148→S0485，S0087→S3676要乘坐地鐵才能獲得最短時(shí)間。6.2圖論模型的求解 因?yàn)楦鶕?jù)此模型得到的結(jié)果，根上面模型基本一致，在此本文就不再贅述，有興趣的讀者可以通過(guò)算法得到。7模型評(píng)價(jià)7.1基于集合尋點(diǎn)算法的模型的評(píng)價(jià)基于集合尋點(diǎn)算法的模型所給的查詢系統(tǒng)是固定換乘次數(shù)基礎(chǔ)上，算出能通過(guò)次換乘的所有線路。再通過(guò)對(duì)不同換乘數(shù)所得到的這些最佳線路，對(duì)這些線路的時(shí)間，費(fèi)用的分別比較，通過(guò)層層的對(duì)比篩選排除，通過(guò)一些條件對(duì)最佳線路的進(jìn)行處理，最后乘客可以根據(jù)自己的不同需求進(jìn)行選擇。其優(yōu)點(diǎn)：模型中緊緊抓住選擇最佳線路問(wèn)題的突破點(diǎn)――換乘次數(shù)，通過(guò)集合的相關(guān)知識(shí)把難點(diǎn)――換乘點(diǎn)的具體位置的確定,轉(zhuǎn)化成確定一些集合間的交集，從而把站點(diǎn)，線路與集合中的元素一一對(duì)應(yīng)起來(lái)，建立起集合尋線算法，再根據(jù)集合相關(guān)公式，通過(guò)線路計(jì)算式子，有效地計(jì)算出最佳線路，并且考慮一些因素，如時(shí)間等對(duì)最佳線路進(jìn)行處理。算法中有效的摒棄一些無(wú)效站點(diǎn)，從而大大減少了計(jì)算量和時(shí)間，明顯比運(yùn)用圖論求得最短路要有效的多。能為查詢者提供不同換乘次數(shù)下時(shí)間與路程最少的最佳線路，以及對(duì)于多條最佳線路，查詢系統(tǒng)盡量采用不太熱門(mén)的公交線路，隨機(jī)地為查詢者提供指定數(shù)目的線路，避免同一最佳線路過(guò)熱的情況發(fā)生。其缺點(diǎn)：就是此模型只能為查詢者提供換乘次數(shù)較少下的最佳線路，當(dāng)換乘次數(shù)大于三時(shí)，模型實(shí)現(xiàn)的時(shí)間較長(zhǎng)。7.2圖論模型的評(píng)價(jià)由圖論模型所得的查詢系統(tǒng)，是以圖論知識(shí)中的最短路有向圖為基礎(chǔ)，對(duì)不同線路經(jīng)過(guò)同一站點(diǎn)時(shí)，假設(shè)多個(gè)假想點(diǎn)，并將各不同站點(diǎn)之間所需時(shí)間作為權(quán)，對(duì)各線路站點(diǎn)賦權(quán)，分別確定以時(shí)間、費(fèi)用、換乘為目標(biāo)轉(zhuǎn)化為尋找有向的完全圖，并根據(jù)實(shí)際情況，建立出動(dòng)態(tài)賦權(quán)有向圖，得出最佳線路。其優(yōu)點(diǎn)：模型充分利用公交線路其實(shí)就是一個(gè)有向圖，而且在比較成熟的最短路算法基礎(chǔ)上，通過(guò)插入換乘時(shí)間，得到最佳線路。算法還是比較容易實(shí)現(xiàn)。其缺點(diǎn)：模型在引入步行，求費(fèi)用最少，卻不能實(shí)現(xiàn)。而且運(yùn)用最短路算法，得到不一定是真正意義上的最佳線路，只能是近似最佳線路。8模型的推廣建立此模型的思想，不但能應(yīng)用到現(xiàn)在這種公交線路中，并能推廣到海、陸、空多種交通線路之間尋找最優(yōu)線路。通過(guò)實(shí)際情況對(duì)模型的進(jìn)行調(diào)整，模型就能適應(yīng)更多情況。例如圖論模型中對(duì)有向圖的權(quán)進(jìn)行調(diào)整就能實(shí)現(xiàn)不同時(shí)間差站點(diǎn)的最佳線路的選擇。參考文獻(xiàn)[1]姜啟源，謝金星.數(shù)學(xué)模型[M](第三版).北京:高等教育出版社,2003.[2]孫惠泉.圖論及其應(yīng)用[M].北京:,2004.[3]邊肇祺,張學(xué)工等.模式識(shí)別[M](第二版).北京:清華大學(xué)出版社,1999.[4]蔡自興,徐光祐.人工智能及其應(yīng)用[M](第二版).北京:清華大學(xué)出版社,1996.[5]袁新生,邵大宏,郁時(shí)煉.LINGO和EXCEL在數(shù)學(xué)建模中的應(yīng)用[M].北京:科學(xué)出版社,2007.

程序附錄部分程序%數(shù)據(jù)的初始處理clcfid=fopen('QCLS.txt','r');Data=fread(fid);len=length(Data);gcl=0;qq=0;fori=1:len-1ifchar(Data(i))=='L'&qq==0gcl=gcl+1;GCLS{gcl}{1}=strcat([Data(i),Data(i+1),Data(i+2),Data(i+3)]);i=i+4;elseifchar(Data(i))=='L'&qq==1forj1=1:length(GCLS{gcl}{3})GCLS{gcl}{4}{j1}=GCLS{gcl}{3}{length(GCLS{gcl}{3})+1-j1};endgcl=gcl+1;qq=0;GCLS{gcl}{1}=strcat([Data(i),Data(i+1),Data(i+2),Data(i+3)]);i=i+4;elseifchar(Data(i)*256+Data(i+1))=='。'&char(Data(i+4))=='S'x=3;i=i+3;qq=1;s=0;elseifchar(Data(i)*256+Data(i+1))=='分'GCLS{gcl}{2}=1;i=i+8;elseifchar(Data(i)*256+Data(i+1))=='單'GCLS{gcl}{2}=2;i=i+11;elseifchar(Data(i)*256+Data(i+1))=='上'x=3;i=i+4;qq=0;s=0;elseifchar(Data(i)*256+Data(i+1))=='下'x=4;i=i+4;qq=0;s=0;elseifchar(Data(i)*256+Data(i+1))=='環(huán)'x=5;i=i+4;qq=0;s=0;elseifchar(Data(i))=='S's=s+1;GCLS{gcl}{x}{s}=strcat([Data(i),Data(i+1),Data(i+2),Data(i+3),Data(i+4)]);clci=i+4;endendfori1=1:520iflength(GCLS{i1})~=5n=length(GCLS{i1}{3});GCLSF{i1}{1}=GCLS{i1}{1};GCLSF{i1}{2}=GCLS{i1}{2};fori2=1:nGCLSF{i1}{3}{i2}=GCLS{i1}{3}{n-i2+1};endn=length(GCLS{i1}{4});GCLSF{i1}{1}=GCLS{i1}{1};GCLSF{i1}{2}=GCLS{i1}{2};fori2=1:nGCLSF{i1}{4}{i2}=GCLS{i1}{4}{n-i2+1};endelseiflength(GCLS{i1})==5n=length(GCLS{i1}{5});GCLSF{i1}{1}=GCLS{i1}{1};GCLSF{i1}{2}=GCLS{i1}{2};fori2=1:nGCLSF{i1}{5}{i2}=GCLS{i1}{5}{n-i2+1};endendendclc%地鐵情況的運(yùn)算Untitled%讀取文件DCLS%地鐵文件處理ZHANDIAN2%各公交車(chē)站點(diǎn)處理k=input('輸入初始站點(diǎn)');t=input('輸入終點(diǎn)站');n=[];ZCSL1{1}=[];ZCSL1{2}=[];ZCSL2{1}=[];ZCSL2{2}=[];DDT1=[];DDT2=[];ZCSL1{3}=[];ZCSL2{3}=[];ZCSL1{4}=[];ZCSL2{4}=[];ll=size(ZD{k});DIST0=9999;fori=1:ll(1)n=str2num(ZD{k}(i,2:4));l=length(GCLS{n}{SL{k}(i)});forj=1:lifstr2num(GCLS{n}{SL{k}(i)}{j}(2:5))==kforjj=j+1:lif(jj-j)*3+10<DIST0ZCSL1{1}=[ZCSL1{1},str2num(GCLS{n}{1}(2:4))];ZCSL1{2}=[ZCSL1{2},GCLS{n}{2}];ZCSL1{3}=[ZCSL1{3},SL{k}(i)];ZCSL1{4}=[ZCSL1{4},jj-j];DDT1=[DDT1,str2num(GCLS{n}{SL{k}(i)}{jj}(2:5))];endendifSL{k}(i)==5forjj=2:j-1if(l-j+jj)*3+10<DIST0ZCSL1{1}=[ZCSL1{1},str2num(GCLSF{n}{1}(2:4))];ZCSL1{2}=[ZCSL1{2},GCLSF{n}{2}];ZCSL1{3}=[ZCSL1{3},SL{k}(i)];ZCSL1{4}=[ZCS