最佳路徑選擇方案的優(yōu)化模型數(shù)學(xué)建模論文

最佳路徑選擇方案的優(yōu)化模型摘要本文對乘公交、看奧運這一實際問題進行了深入的研究，首先對公交乘客進行了心理分析，得出影響乘客出行的三個主要因素分別為：換乘次數(shù)、出行時間、出行費用，通過調(diào)查研究，得出換乘次數(shù)最少是乘客出行考慮的最主要因素，其次是出行時間和出行費用。然后利用公交乘客的出行過程抽象為站點一線路的交替轉(zhuǎn)換的思想，建立了站點一線路序列模型，從而確定了出行者對路線的所有選擇方案。針對問題一：僅考慮公汽的情況下，以換乘次數(shù)最少為第一目標(biāo)、出行時間為第二目標(biāo)建立了優(yōu)化模型一，再以換乘次數(shù)最少為第一目標(biāo)、出行費用為第二目標(biāo)建立了優(yōu)化模型二，從而滿足了兩類不同乘客的需求。并依靠站點一線路序列模型采用圖論中計算方法，分別得到了公交乘客的最少換乘次數(shù)，所經(jīng)過的站點，出行時間、出行費用以及相應(yīng)的算法。針對問題二：在問題一的基礎(chǔ)上再考慮地鐵線路，建立了對應(yīng)的兩組優(yōu)化模型，并推導(dǎo)出相應(yīng)的改進算法。針對問題三：在問題一、二的基礎(chǔ)上，考慮出行者可以通過步行到達相鄰的公交站點的情況，同樣建立了兩組相應(yīng)的優(yōu)化模型，并給出了相應(yīng)的計算方法。然后利用基于換乘次數(shù)最少的最優(yōu)路徑改進算法思想，借助MATLAB軟件編程分別對問題一和二進行了求解，得到的結(jié)果見模型的求解（正文第21、22頁）。最后對所求得的結(jié)果進行了對比分析和檢驗，根據(jù)各參數(shù)的變化關(guān)系，進行了靈敏性分析，本模型主要抓住了乘客的心理需求，實用性強，具有較強的現(xiàn)實意義。關(guān)鍵詞：站點一線路序列最優(yōu)路徑改進算法公交一、問題的提出1.1基本情況我國人民翹首企盼的第29屆奧運會明年8月將在北京舉行，屆時有大量觀眾到現(xiàn)場觀看奧運比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇（包括不同線路上的換乘交通工具的路徑選擇等）問題。針對市場需求，某公司準(zhǔn)備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)。L2基本參數(shù)設(shè)定：1）相鄰公汽站平均行駛時間（包括停站時間）：3分鐘；2）相鄰地鐵站平均行駛時間（包括停站時間）：2.5分鐘；3）公汽換乘公汽平均耗時：5分鐘（其中步行時間2分鐘）；4）地鐵換乘地鐵平均耗時：4分鐘（其中步行時間2分鐘）；5）地鐵換乘公汽平均耗時：7分鐘（其中步行時間4分鐘）；6）公汽換乘地鐵平均耗時：6分鐘（其中步行時間4分鐘）；7）公汽票價：分為單一票價與分段計價兩種，標(biāo)記于線路后；其中分段計價的票價為：0?20站：1元； 21~4。站：2元；40站以上：3元。地鐵票價：3元（無論地鐵線路間是否換乘）。注：以上參數(shù)均為簡化問題而作的假設(shè)，未必與實際數(shù)據(jù)完全吻合。1.3相關(guān)信息（詳見附件）【附件1】公汽和地鐵線路信息數(shù)據(jù)文件格式說明；【附件1.1】公汽線路及相關(guān)信息；【附件1.2］地鐵線路及相關(guān)信息；【附件2】地鐵換乘公汽信息數(shù)據(jù)文件格式說明；【附件2.1】地鐵T1線換乘公汽信息；【附件2.2】地鐵T2線換乘公汽信息。1.4需解決的問題為了設(shè)計這樣一個公交線路選擇的自助查詢計算機系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實際情況出發(fā)考慮，以滿足查詢者的各種不同需求。進而需要解決如下問題：問題一、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附件中的相關(guān)數(shù)據(jù)，利用所得到的模型與算法，求出以下6對起始站f終到站之間的最佳路線(要有清晰的評價說明)。(1)、S3359fsi828 (2)、SI557fs0481 (3)、SO971fs0485(4)、S0008-S0073 (5)、SOI48fse)485(6)、S0087—S3676問題二、同時考慮公汽與地鐵線路，解決以上問題。問題三、假設(shè)乂知道所有站點之間的步行時間，請你給出任意兩站點之間線路選擇問題的數(shù)學(xué)模型。二、基本假設(shè)2.1出行者對公交線路的選擇是理性的且能夠順利正常的到達目的地。2.2出行者在所經(jīng)過的站點中，不允許兩次經(jīng)過相同的站點。2.3公交與地鐵換乘距離固定，換乘步行時間為常數(shù)。2.4同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站換乘且無需支付地鐵費。2.5出行者換乘時，不受人群擁擠、交通堵塞等現(xiàn)象的影響且均能乘到相應(yīng)線路的公汽或地鐵。2.6出行者換乘交通工具時的平均耗時包括出行者到站的等待時間和換乘的步行時間；公汽線路上的單一制票價為1元，分段計價的票價為：0~20個站：1元；21?40站:2元；40站以上：3元；地鐵票價：3元(無論地鐵線路間是否換乘)。附件所給數(shù)據(jù)準(zhǔn)確無誤。(注：本文中針對相應(yīng)問題的假設(shè)將在后文中陸續(xù)給出)三、問題分析與模型建立觀看2008年8月在北京舉行的奧運會是我國人民翹首企盼的盛事，屆時將會有大量的觀眾需要到現(xiàn)場觀看奧運比賽，公交也將成為主要的交通工具，因此觀看比賽的首要問題應(yīng)當(dāng)是解決每位觀眾如何去的路線問題。本文需要設(shè)計乘客對路線的選擇方案，在探討選擇公交線路的數(shù)學(xué)模型和最優(yōu)路徑算法時，有必要先了解公交乘客出行時所考慮的因素，通過對公交乘客出行心理、行為的研究來確定模型的優(yōu)化目標(biāo)和約束條件。對公交乘客的心理研究通常乘客出行時，主要考慮以下兒個主要因素臼:“換乘次數(shù)”、“出行經(jīng)歷的總站數(shù)”、“出行耗時”、“出行費用”、“存在的步行時間”等。就乘客本身而言，公交乘客出行更多考慮的是出行的方便性和舒適性，下面就影響公交乘客出行的各因素進行具體分析，不妨將以上影響因素作如下歸納解釋：(1)換乘次數(shù)：出行者完成一次從出發(fā)點到終點出行過程中所換車的次數(shù)。(2)出行經(jīng)歷的總站數(shù)：由起點到終點所經(jīng)歷的站點總數(shù)。(3)出行耗時：出行者在一次乘公交出行過程中所用的總時間。(4)出行費用：出行者在完成一次由起點到達目的地過程中所花的車費。(5)存在的步行時間：出行者由起點到終點所有步行時間的總和。從實際生活可知，上述幾個因素是相互關(guān)聯(lián)，相互影響的，因此影響乘客出行的因素可以通過對比后進行簡化。比如“換乘次數(shù)”與“出行費用”和“存在的步行時間”都具有一定的正相關(guān)性，一般說來，當(dāng)乘客的換乘次數(shù)越多，出行費用將更高，通過換乘而步行的時間也就越多，這在單一的公汽票價上最容易體現(xiàn)與費用的相關(guān)性；”出行經(jīng)歷的總站數(shù)”與“出行耗時”也具有一定的正相關(guān)性，尤其是不需要經(jīng)過換乘就能到達的目的地。而“換乘次數(shù)”與“出行經(jīng)歷的總站數(shù)”在一般情況下，將不會存在絕對的相關(guān)性。因此，可認(rèn)為“換乘次數(shù)”和“出行耗時”是影響出行者的兩個獨立的因素,經(jīng)研究表明多數(shù)的公交乘客希望換乘次數(shù)最少，況且公交公司對公交線路的設(shè)計也是盡量減少乘客的平均換乘次數(shù)121；而且公交乘客出行時還受到行李、地理位置等客觀因素的影響，這樣更不希望有較多的換乘。其次對于看奧運非常心切的出行者來講，出行耗時對他們也許是比較關(guān)鍵的。在此當(dāng)給出供乘客選擇的公交路線也應(yīng)當(dāng)盡可能的滿足公交乘客的需求，那么什么樣的出行路線乂是出行者最需要的呢？這除了對個別的公交乘客進行心理分析得到不同的需求結(jié)果之外，還應(yīng)當(dāng)使得眾多的公交乘客在選擇上得到滿意，為權(quán)衡這兩方面的獨立因素，有必要對看奧運的公交乘客進行心理調(diào)查，介于競賽期間的時間關(guān)系本文對出行看奧運的出行者的心理調(diào)查就不作單獨的深入研究，現(xiàn)參考在南京市做的一個公交乘客出行心里調(diào)查統(tǒng)計結(jié)果臼,該調(diào)查主要對3個因素做了統(tǒng)計:換成次數(shù)，出行距離，出行耗時。其記錄結(jié)果如下圖(圖3-2)所示：45.00%40.00%35.00%30.00%25.00%45.00%40.00%35.00%30.00%25.00%20.00%15.00%10.00%5.00%0,°勰路程最短時間最短換乘最少其他圖3-2公交乘客出行心理分析圖從圖中統(tǒng)計的心理分析結(jié)果可以看出，有41.16%的出行者在選擇出行路徑時，首先考慮的是換乘次數(shù)最少，其次考慮的是時間最短。在實際生活中，出行者往往受到行李、地理位置、天氣等諸多因素的影響，選擇最少換乘次數(shù)的公交路線往往能最大限度地解決某些因出行帶來的麻煩，并且從一條線路換乘到另一條線路是費時乂費力的，這也是大多數(shù)公交乘客希望換乘最少而與實際生活調(diào)查相吻合的主要原因。因此公交乘客在選擇最優(yōu)路線時應(yīng)當(dāng)是以換乘次數(shù)最少為第一目標(biāo)。另外，對于一個以出行看奧運為目的的出行者來說，達到目的地的出行總費用遠(yuǎn)不足以作為主要因素。并且出行費用受換乘次數(shù)的影響較顯著，當(dāng)不考慮地鐵、較多站數(shù)的分段計價線路的公汽是不會有多大影響的，因此這不比作為主要目標(biāo)加以考慮。綜上所述，可以以換乘次數(shù)最少為第一目標(biāo)，以選擇乘車所用時間最少為第二目標(biāo)建立相應(yīng)的線路選擇的優(yōu)化模型。但對這些目標(biāo)函數(shù)和約束條件的具體考證和檢驗還需要進一步挖掘附件中的相關(guān)信息。分析附件中的主要相關(guān)信息直觀統(tǒng)計結(jié)果作為需要乘坐公交工具去看奧運的行者來說，了解乘車路線的相關(guān)信息同樣是最重要的；由EXCEL軟件統(tǒng)計【附件1.11和【附件1.2］中的公交線路系統(tǒng)數(shù)據(jù)，得到如下信息：（1）該公交系統(tǒng)共有公汽線路520條。其中票價信息為分段計價的線路283條，單一票制1元的線路237條；上下行路徑不同的線路409條，上下行路徑相同的線路89條，環(huán)行線路22條。（2）該公交系統(tǒng)共有公汽站點3957個。（3）該公交系統(tǒng)共有地鐵線路2條。其中直行線路1條，環(huán)行線路1條；（4）該公交系統(tǒng)共有地鐵站點39個。信息處理對于上述統(tǒng)計的直觀信息，結(jié)合本文L2節(jié)基本參數(shù)設(shè)定中的票價信息，結(jié)合上述第（1）條統(tǒng)計結(jié)果中的分段計價線路進行綜合考慮，可得：在分段計價路線中，共有27條的公汽站點數(shù)不超過20,有148條的公汽站點數(shù)在21?40之間，公汽站點數(shù)超過40的線路有108條。因此，從單獨的計算角度來考慮，可以將分段計價中站數(shù)不超過20的線路歸為單一票制1元的線路，因此上述信息（1）可修正為：票價信息為單一票制1元的線路264條；在分段計價的路線中，共有256條，其中有148條的公汽站點數(shù)在21?40之間，公汽站點數(shù)超過40的線路有108條。從上述處理結(jié)果可以看到，在公汽的運行系統(tǒng)中“出行費用”的增長將勝過換乘次數(shù)的增長，其原因是出行者在乘坐分段計價的公汽線路時，將可能被多耗費用，所以將費用計算出來共乘客參考也是有必要的。為給出行者提供乘車路程，考慮到22條環(huán)行路線中，存在一定數(shù)量的單一票價制線路，因此還需要計算出所經(jīng)歷的相應(yīng)站點總數(shù)。同樣，當(dāng)條件對步行時間給予強調(diào)時，步行時間應(yīng)是為不便于步行的公交乘客所參考的。為進一步簡化問題，同時也便于統(tǒng)一變量所表示的含義。不妨對附件中的相關(guān)信息進行如下符號約定：公汽站點 小： 上表示出行者選擇第，條公交線路所經(jīng)過的第攵個站點。公汽站點集S S={s0c01,§0002,S3957}公汽線路 kL；以表示出行者選擇第，條公交線路所乘坐的第〃輛公交工具。公汽線路集L: L={LOQl,LOQ2,---,L52O}地鐵站點 小：也匕%表示出行者選擇第i條公交線路所經(jīng)過的第攵個站點。地鐵站點集D：。={。01，。0門…,。39}地鐵線路 kT；也表示出行者選擇第，條公交線路所乘坐的第〃輛公交工具。地鐵線路集T:7=您,八}從上述信息可知，分析公交乘客的心理而得到出行者對路線選擇目標(biāo)的重要性是至關(guān)重要的，但還不能完全解決此類問題?？梢娨苯咏⒁粋€全面的，能快速選擇任意兩站點之間最優(yōu)乘車路線的模型是比較困難的。同時就是能得到具體的出行線路，也還必須依賴于具體的公交行車路線和大范圍的公交站點。根據(jù)解決問題的時應(yīng)當(dāng)采取化繁為簡，先易后難的原則，本文在此不妨對所研究的問題進行重難點分析以得到相應(yīng)的建模思路。重點、難點分析與建模思路首先，對公交系統(tǒng)中乘客給出的任意一對起始站一終到站，如何確定其最優(yōu)乘車方案是本文討論的中心。所謂乘車方案即可看著是一個站點、線路的交替序列口】，該序列說明從起點出發(fā)乘坐何種路線，途中如何換乘，直至到達終到站。因此，從前文的分析可以看出，建立站點、線路的交替序列臼模型是分析公交線路選擇問題的關(guān)鍵和出發(fā)點,也是本文所有問題討論的基礎(chǔ)。其次，在站點上放置一個便于乘客查詢到達目的地的理想乘車方案的計算機系統(tǒng)，必須讓計算機收集到本站到其他任意一站的路徑與換乘信息，因此單獨設(shè)計這樣的算法是相當(dāng)困難的，而且算法的精度要求也比較高。對本文附件中的公交系統(tǒng)中所列的3957個公汽站點和39個地鐵站點來說，直接要得到所有任意兩站點之間的最優(yōu)公交路徑的計算量是相當(dāng)大的。當(dāng)面對這樣一個密集的交通網(wǎng)絡(luò)來說，對路線的選擇主要是將面臨一個P類問題［4】，根據(jù)尸類問題的處理特點，可以用某種主次改進的方法來求解。由于每次改進中的計算量都是多項式界的，改進的次數(shù)也是多項式界的。目前已找到具有這種特性的算法，如橢球算法，卡馬卡算法，但都相當(dāng)復(fù)雜。因此要滿足出行者的路線需求，則有必要對目標(biāo)進行歸類篩選，以降低不必要的選擇、計算與搜索。不妨采用改進的廣度優(yōu)先搜索算法，基于改進次數(shù)為多項式界的算法理論，本文選擇從某次乘公交的起點和終點的兩端進行同時搜索，在滿足換乘次數(shù)最少的條件下尋找不同線路中的共同站點或不同站點之間的相同線路，并計算其總路線的中的乘車時間和站點數(shù)。預(yù)備知識據(jù)問題提出的相關(guān)信息可知，本文所要解決的根本問題是設(shè)計一個公交線路選擇的自助查詢的計算機系統(tǒng)，并從實際情況出發(fā)考慮，以滿足查詢者的各種不同需求。設(shè)計該系統(tǒng)的核心是線路選擇的模型與算法。由附件中的統(tǒng)計信息可以知道，任意一個公交站點都不是孤立的，即連接任意兩公交站點之間的公交路徑都是存在的。當(dāng)然這樣的路徑可能只有一條，也可能有多條，不妨記出行者所選擇出行的起始站為匕，終到站為匕，從％到匕的所有路徑的集合也不妨記為依，其中第/.條路徑為花,。進一步分析和考慮出行者乘公交的具體情況，一個出行者的出行可簡單描述為如下路徑（圖3-1）：乘第3乘第3節(jié)公交圖3-1出行者選乘公交路徑規(guī)律分析示意圖注：圖中M表示某出行者的換乘次數(shù)從圖中內(nèi)容也可以反應(yīng)，出行者出行乘公交的路徑可看著是站點、車次、站點、車次的交替進行，直至到達終到站。為區(qū)別前后的車次或站點，使得前后排列的站點與車次都有一定的順序，不妨設(shè)出行者選擇第i條路徑次，時，所乘坐的第攵節(jié)公交工具為Pik，第攵個換乘站點（中轉(zhuǎn)站）記為％，由于出行者不能在同一站點上出現(xiàn)兩次，即%各不相同，特別地令%=%,匕凹+1=也；于是可以得到從匕到功的所有路徑集序中的第i條路徑為我/次,=<%，〃“，匕，〃,2,…，匕>因此將所有路徑次，?集在一起，可得：TR={TRi\TRi=<%,/乙”匕卬,2，匕2廣，匕>}由此而來，對任何一個出行者來說，只要知道他的出行起始站九和終到站匕之后,便可以在路徑集77?中找到他最需要的出行路線，據(jù)此可以得到站點一線路交替序列的一般模型。站點一線路交替序列模型通過前文的逐步分析，設(shè)出行者僅通過公汽及換乘從起始點匕到達終到點匕，出行者選擇第i條線路上的第4次乘車的公交線為P…經(jīng)過的第％個站點為小，則該條選擇線路上的站點一線路交替序列丁凡為：其中站點一線路交替序列次,.表示從起始點Vo選擇線路P“到達%,換乘Pl2到達匕2,……，最終到達匕的第i種路徑。不妨將所有的站點一線路交替序列次，集在一起，可得到相應(yīng)的從起始站丫。到達終到站匕的公交線路選擇集丁R，即：TR={殂ITR[=<v0,p〃,%,pi2，匕2，…，匕>}可見本模型對路線的選擇范圍確定了界限，這樣也明確了尋求最優(yōu)線路的討論范圍，即搜索的路徑（公交線路化％）和節(jié)點（公交站點?）都是相互關(guān)聯(lián)的。342多目標(biāo)優(yōu)化函數(shù)的提出通過前文對公交乘客的心理分析，已經(jīng)得到設(shè)計出以換乘次數(shù)最少為第一目標(biāo)，以出行時間最短為第二目標(biāo)所建立的數(shù)學(xué)模型是比較合理的，因此這需要提出一個針對該種情況下的多目標(biāo)函數(shù)。設(shè)出行者選擇第，條路線時的換乘次數(shù)為Nj；出行者選擇第i條路線時所消耗的總時間為小則在有序約束集77?中，選擇在滿足換乘次數(shù)最少的情況下的出行時間最短的目標(biāo)函數(shù)為：“在這里，是指一個目標(biāo)優(yōu)先的二元目標(biāo)函數(shù)集，即首先滿足Nj達到目標(biāo)后,再使得f,達到目標(biāo)的最優(yōu)方案集。相應(yīng)地，次i表示出行者選擇第，?條路線時的有序路徑集當(dāng)然對所得的目標(biāo)函數(shù)還必須賦予一定的函數(shù)性質(zhì)，否則該目標(biāo)函數(shù)將不會有任何實際意義。根據(jù)以上分析，可知應(yīng)當(dāng)滿足：6U門 6U八 dUdU——>0, ——>0, ——?——6M 的 犯的同理，可將上述原理作一般性推廣，如當(dāng)需要建立以換乘次數(shù)最少為第一目標(biāo)，出行所消耗的時間為第二目標(biāo)，所支付的公交費用為第三目標(biāo)時的目標(biāo)函數(shù)，可表示為：dUn GU門 dU門 dUdUdU——〉0, ——〉0, ——〉0, ——?——?——其中，刎 M oQ, 6MMdQ,0表示出行者選擇第/?條公交線路從起始站到達終到站所應(yīng)當(dāng)支付的所有費用。注：在本文中，后面所用到的上述目標(biāo)優(yōu)化函數(shù)，不作特別說明，都默認(rèn)為分別具有相應(yīng)的函數(shù)性質(zhì)。3.5針對問題一的分析與建模在問題一中，要求僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型。根據(jù)前文對公交乘客的出行心理分析，以選擇換乘次數(shù)最少為第一目標(biāo)，以選擇乘車所用時間最少為第二目標(biāo)可得到相應(yīng)的目標(biāo)函數(shù)，而具體的約束條件則需要另外求得。對于換乘次數(shù)，聯(lián)系被選擇線路上的站點一線路交替序列次,的元素個數(shù)可以表示出來；站點總數(shù)則采用給同一線路上的站點排序的方法也可以求到，由于只考慮了公汽之間的換乘，則出行時間只與換乘次數(shù)和所歷站數(shù)有關(guān)；對于出行費用則在換乘次數(shù)的基礎(chǔ)上，引入分段計價的加價函數(shù)也可求得。351模型1：公汽路線選擇的通用模型在問題的分析中，我們已經(jīng)初步地得到了尋求線路最優(yōu)的雙目標(biāo)函數(shù)選擇的優(yōu)化模型，現(xiàn)歸納如下：目標(biāo)函數(shù)：若以換乘次數(shù)最少為第一目標(biāo)，以選擇乘車所用時間最少為第二目標(biāo)可得總體的目標(biāo)函數(shù)，嘔nU(N")約束條件：(1)當(dāng)選擇總目標(biāo)取最小時，而換乘次數(shù)和乘車所用時間也都同樣在要求最少，因此u與M是正相關(guān)的；即，—>0.dNi(2)同樣U與4也是正相關(guān)的，即：去>0,(3)由于在優(yōu)先選擇權(quán)上，按相應(yīng)條件，在目標(biāo)函數(shù)中，N,應(yīng)優(yōu)于小很明顯，上述優(yōu)化函數(shù)滿足多目標(biāo)優(yōu)化的條件，因此可轉(zhuǎn)化為多目標(biāo)求解。單由上述模型提供的總目標(biāo)選擇，還不能全面地選擇出相應(yīng)的全程公交線路；因此，需要進一步對目標(biāo)函數(shù)中的相關(guān)子目標(biāo)進行細(xì)化和計算。同時考慮該最優(yōu)目標(biāo)下的約束條件應(yīng)是強約束的，而出行者所乘坐公交時的換乘次數(shù)與出行者乘公交所用時間不存在明顯的相關(guān)性，因此這需要將兩方面進行獨立考慮，根據(jù)前文的分析與敘述已經(jīng)知道，需要在滿足Nj取最小值時，再進行其它變量的確定與計算，才能選擇到相應(yīng)的目標(biāo)。即需要在可行域77?={%|見=<GP”,%,/%,%,???,%>}中進行優(yōu)先性的條件搜索。(1)換乘次數(shù)不妨設(shè)R,表示有序集株>中的元素的個數(shù)，為便于區(qū)別，現(xiàn)標(biāo)記R=CardTR,于是換乘次數(shù)的計算公式可簡單歸納為:國一11

-1(2)所通過的總站數(shù)設(shè)非環(huán)行線路上的兩個站點匕j和％在沿著公交工具行進方向上的站數(shù)按照正整數(shù)從小到大的排序分別為女(PDl)和奴Pnk),其中仍然記匕0=%；匕M+1=也，于是由附件中的相關(guān)統(tǒng)計結(jié)果可知：當(dāng)線路外為環(huán)行線路時，設(shè)該環(huán)行路線上的總站數(shù)為K…%為以上的任意一站,匕。，也分別為公交工具在沿著p/亍進方向上的最后一站和前一站，于是可標(biāo)記k(Pik,%o)=Kik.奴/%,%)=1.k(Pik，%J=2 k(Pik，%) =j.…9 ， ， 9 9所以出行者乘坐p,k線路的公交所經(jīng)過的站點數(shù)目為：Jk(PhW(Ph%t) p認(rèn)為非環(huán)行線路：P?I'“)”(P『九)-&(PEiH*P次為環(huán)行線路.所以，出行者途經(jīng)的總站數(shù)為共條行車路線上車站數(shù)的總和，即M+1jt=i（3）出行者所用時間由于在只有公汽交通的線路中，僅存在公汽線路之間的換乘消耗時間和在公汽上的運行時間，于是由問題中的參數(shù)設(shè)定可以得到：相鄰公汽站平均行駛時間（包括停站時間）：3分鐘；公汽換乘公汽平均耗時：5分鐘（其中步行時間2分鐘）；不妨設(shè)出行者選擇第i條線路從起始站之到達終到站、所耗的平均總時間為4,換乘一次所耗的平均時間為%=5分鐘，相鄰兩站點之間乘車的平均時間為1=3分鐘。則有<=，0乂+%（S.-1）（4）乘車總費用由問題中的參數(shù)設(shè)定容易知道，乘車的總體花費會受到出行者換乘次數(shù)，乘坐分段計價車時通過的站數(shù)的影響，在附件統(tǒng)計信息已經(jīng)得到，公汽線路上的單一制票價為1元，分段計價的票價標(biāo)準(zhǔn)為出行者通過本線路0-20個站：1元；21?40站：2元；40站以上：3元。不妨令公汽的單一票價為2。，出行者在所選擇的出行線路中所應(yīng)支付的車旅費為0,所乘同一公交線路上的最高收費為?！ǎ侄斡媰r時加價的最少站數(shù)為L。，于是有:2=2o<M+l）+WL（P,Jminj ，其中［A」表示取不超過A的最大整數(shù)，參數(shù)：0。=1（元），G=3（元），4=20.、［0線路p業(yè)為單一票制線路；11線路〃法為分段記價線路綜上所述，根據(jù)不同目標(biāo)因素的優(yōu)先性可建立不同的線路選擇方案模型；當(dāng)然針對不同的出行者的選擇要求，將會有更多的選擇方案的模型，但是無論優(yōu)選目標(biāo)順序如何變化，它們的基本約束條件都是相同的，不妨記問題一中的約束條件集為《，則有：（1）以換乘次數(shù)最少為第一目標(biāo)，乘車所用時間最少為第二目標(biāo)所建立的模型為:mill

7Rr（2）以換乘次數(shù)最少為第一目標(biāo)，乘車總費用最少為第二目標(biāo)所建立的模型為:哂u（M，2）IK，其中，基本約束條件集凡為:a=s.t.TR={T/?,|TRt=<v0, ,vfl,pi2,v/2,?■■,>}a=s.t.&=CardTRt;P次（匕i,%）=k(PQik)-k(PikMk-J為非環(huán)行線路；k(PQik)-k(PEkT)P次（匕i,%）=M+ls’=￡/%?(%-3)?jt=i4=，oNi+i。?(Sj—1)0=0。,M+?（pjminj ，2,i-1[0線路p次為單一票制線路；小[i線路p認(rèn)為分段計價線路；為了使出行者在乘坐公交的過程中，達到最少換乘次數(shù)min乂，而N,只與出行者TRi在某一公交體系中的初始站、終到站、公交線路、公交站點有關(guān)。因此可以考慮以換乘次數(shù)從小到大的排除選優(yōu)搜索法進行求解計算。3.5針對問題二的分析與建?？紤]地鐵與公汽并行時的公交系統(tǒng)時，出行者的選擇將變得更加靈活，其主要變化的因素有：（1）地鐵票價稍高但是固定且在地鐵航線之間換乘而不需另外支付交通費用，相鄰站點之間的距離較公汽站點大，而運行時間卻相對減少。（2）地鐵與公汽之間進行換乘時，由于地鐵站點不可能與公汽站點都建在同一個地方，因此從地鐵站到公汽站的步行時間相對較多，而且位于與地鐵換乘的公汽站點還可以通過本地鐵站進行免費耗時換乘到下一個公汽站。綜上所述，不妨將跨公交站的步行也同樣看著是一條步行公交線路，不過該條公交線路具有免費耗時的特點。同問題一中的解決方案可建立相應(yīng)的數(shù)學(xué)模型。地鐵一公汽型公交線路選擇模型當(dāng)并入地鐵公汽的交通網(wǎng)絡(luò)時，增加地鐵站與其周圍的公汽站之間的步行線連接轉(zhuǎn)換后，本問題可轉(zhuǎn)化為問題一中的模型求解，同樣有出行者通過公汽換乘、地鐵換乘、公汽與地鐵之間的換乘后從起始站」到達終到站口的可行路徑集為：TR=^TRi\TRt=<%,P“，匕1，pr2,匕2,…,匕>}其中外的屬性將被擴大，它將表示公汽、地鐵、步行這三類交通路線中的某一類交通路線；而％的含義與問題一中小的含義相同，仍表示公交站點或地鐵站點。（1）換乘次數(shù)與途經(jīng)總站數(shù)同樣設(shè)路徑刀?’的換乘次數(shù)為途經(jīng)總站數(shù)為，，同問題一對S,仍然有：&=CardTR「1*Sj=￡/%（%.一”口）/t=l（2）出行者乘公交所用時間在地鐵一一公汽的公交系統(tǒng)中，出行者將會表現(xiàn)在公汽運行耗時，地鐵運行耗時，地鐵換乘公汽耗時，公汽換乘地鐵耗時，公汽換乘公汽耗時，地鐵換乘地鐵耗時，公汽通過指定地地鐵換乘公汽耗時。為簡化變量，考慮出行者的異站步行也納入到公交線的行列中，則所消耗的時間可歸結(jié)為：交通工具運行耗時，交通線路換乘耗時兩類。根據(jù)基本參數(shù)設(shè)定的類型，不妨設(shè)出行者從起始站」到達終到站匕所用的總時間為4,從公交站點吃J乘/“線路公交工具到達公交站點k所消耗的時間（包括相鄰兩站點間的停站時間）為：《匕I，%），由P“.線路的公交工具換乘到Re線路的公交工具

所消耗的時間為：晨P*,P*M）,由基本參數(shù)設(shè)定的信息可得:M+1 傳c=￡/%（%-1，％）,/（匕*=1 1=1其中32.532.5?匕I，%）==7601MTwS;heS；匕i ￡0；“iGD;hkeS；匕gD：其它.'4，'4，（Pg，PQ=《50PiiWT；1％eT；Pik-i^L；]%wL；其它.（3）乘車總費用在問題二的討論中，乘車的總體花費會受到出行者換乘次數(shù)，乘坐分段計價車時通過的站數(shù)的影響，而在本問題中，有假設(shè)知道同一地鐵站對應(yīng)的任意兩個公汽站可以通過地鐵站換乘而不需要支付地鐵費，同樣根據(jù)問題一中，對乘公交所支付費用的討論思想，仍然令乘坐公汽的單一票價為2。，出行者在所選擇的出行線路中所應(yīng)支付的車旅費為0,所乘同一公交線路上的最高收費（含地鐵收費）為。…分段計價時加價的最少站數(shù)為于是有:0=2o./N（pnPwP+ftsJmin]P""；t-1K=1 k=l II4其中IA」表示取不超過A的最大整數(shù)；參數(shù)：0。=1（元），牖=3（元），4=20.0線路p認(rèn)為單一票制線路或地繳路;1線路p,%為分段記價的公交線路1P小￡LPi+i￡LN"k，P"J={3Pik訂,P.i￡T0其它

綜上所述，同樣采用問題一中對目標(biāo)函數(shù)和約束條件的處理，仍然根據(jù)不同目標(biāo)因素的優(yōu)先性可建立不同的線路選擇方案模型；它們?nèi)跃哂邢嗤募s束條件集，不妨記問題二中的約束條件集為此，則(1)以換乘次數(shù)最少為第一目標(biāo)，乘車所用時間最少為第二目標(biāo)所建立的模型為:min

7Rs.t.(2)以換乘次數(shù)最少為第一目標(biāo)，乘車總費用最少為第二目標(biāo)所建立的模型為:mmTRts.t.Ns.t.N苫R,;Qi￡R[?其中，上述模型中的基本約束條件&為:R=s.t.TR={TRt|TR,=<v0,pfl,v.1,p.2,v1.2,---,vJR=s.t.Rt=Card77?,;iRT2RT2-1；k（Pik，、k）-MPkHi） P4為非環(huán)行線路;我（PiA，h）-&（P2g）+%P決為環(huán)行線路M+iSi=￡/%(%-1,％)?A=1M+1 跖Jt=lA=13匕iCS;%g52.5匕1gD?k￡D，(匕hi，vik)=<7匕”O(jiān)；”S6 GS;vikeD0其它4PiiST"%"t(pil,pik)=-PgET;PikeT;0其它.Qi"00-xN(Pik, )+'L(/%)?mu"，0TA=1a=i [Ly>J4=2。； ?！?3;0o=L0線路p,淡為單一票制線路或地鐵戔路;1線路p4為分段計價的公交線路P,kwL,Pik+\WL、Pik生T,PlgT.其它.3.6針對問題三的分析與建模考慮到出行者在步行時，所經(jīng)過的任意兩站點之間的路徑都應(yīng)該是至少有一條公汽線路上的公交工具通過，由問題三的條件可知，步行時所經(jīng)過的兩站點之間的步行時間是一個已知值。據(jù)實際情況，假設(shè)步行者步行在相鄰兩公汽站所用時間平均是公汽經(jīng)過這兩站（包括停站時間）所用時間的〃倍，則由基本參數(shù)設(shè)定可知，步行者通過這樣兩站點所用的平均時間為弘分鐘，于是將行人步行所經(jīng)過的線路也納入到公交線路中，其特點是費時費力但選擇靈活，路途捷近。步行一地鐵一公汽型公交線路選擇模型設(shè)出行者以步行、乘公交、換乘等任意的出行方式從初始站％到達終到站匕的可行路徑集為：TR={4<|TRt=<v0,，匕，Pn,%,…,匕>},其中，上式中的p,%、也都與問題二中p,%、總的含義分別相同，（1）換乘次數(shù)、途經(jīng)總站數(shù)設(shè)該路徑TR,的換乘次數(shù)為N,,途經(jīng)總站數(shù)為S1,仍然有jV,+1s,=￡/%（%-1，％）（2）出行者乘公交所用時間在步行一地鐵一公汽的公交系統(tǒng)中，出行者將會出現(xiàn)公汽運行耗時，地鐵運行耗時,地鐵換乘公汽耗時，公汽換乘地鐵耗時，公汽換乘公汽耗時，地鐵換乘地鐵耗時，公汽通過指定地地鐵換乘公汽耗時，公交站點之間的步行耗時。同樣考慮出行者的異站步行納入到公交線的行列中來簡化變量，則所耗時間仍然可分為：交通工具運行耗時（包括步行耗時），交通線路換乘耗時兩類。同樣設(shè)出行者從起始站％到達終到站口所用的總時間為右，從公交站點匕1乘線路公交工具到達公交站點”所消耗的時間（包括相鄰兩站點間的停站時間）為：，（匕I，0），由/“線路的公交工具換乘到線路的公交工具所消耗的時間為：f（P*,P*+J，則由基本參數(shù)設(shè)定的信息可得:M+l MA=1 k=l其中’3匕"S,%gS；2.5k”。，小wD；，（匕5%）=<7k-i，%es：6gD：3kVikTES,、kES，PikT生L,Pik生T;0?其它.k為公汽行進時是出行者步行時的平均倍率。IMS%"pik_^UpikwL；其它.（3）乘車總費用在問題三的討論中，乘車的總體花費會受到出行者換乘次數(shù)，乘坐分段計價車時通過的站數(shù)的影響，而在本問題中，有假設(shè)知道同一地鐵站對應(yīng)的任意兩個公汽站可以通過地鐵站換乘而不需要支付地鐵費，步行的出行者在步行的公交站點線路上也不需要支付公交費用，同樣由問題一中對乘公交所支付的費用的討論思想，同樣令乘坐公汽的單一票價為0。，出行者在所選擇的出行線路中所應(yīng)支付的車旅費為0，所乘同一公交線路上的最高收費（含地鐵收費）為分段計價時加價的最少站數(shù)為"，于是有:Q,=00./N(/?,.,,Pik+P++L*(/A,)-niuJ -1A=1 I%其中[A」表示取不超過A的最大整數(shù)，在本題中4=20；。〃=3；00=1. [0線路p法為單一票制線路或地物線路；L（）=<* [1線路P認(rèn)為分段記價的公交線路11%￡Lpi+igLN"k，&+J=?3Pi」T, eT0其它綜上所述，同樣采用問題一中對目標(biāo)函數(shù)和約束條件的處理，仍然根據(jù)不同目標(biāo)因素的優(yōu)先性可建立不同的線路選擇方案模型；但是無論優(yōu)選目標(biāo)順序如何變化，它們的基本約束條件仍然是相同的，因此設(shè)問題三中的約束條件集為此，則（1）以換乘次數(shù)最少為第一目標(biāo)，乘車所用時間最少為第二目標(biāo)所建立的模型為:millU(N")TRjs.t.(2)以換乘次數(shù)最少為第一目標(biāo)，乘車總費用最少為第二目標(biāo)所建立的模型為:nunU(Nj,Qj)f/V,e/?3;s.t.I。e凡.其中，基本約束條件集凡為：Rm=s.t.TR=^'Ri\TRi=<v0,pf.1,vf.1,p.2,vf2,--,vJ>｝；Rm=s.t.=CardTR「,ikg，匕）-kg,憶-Jp法為非環(huán)行線路;kg，h）-kM，匕i）+K汝p旗為環(huán)行線路M+1s,=￡/%（%一1,％）.*=1Nj+1 以。=￡〃旗（憶-1,山）,/（匕1。）+￡/（〃“丹+1）；k=L k=l3匕iwS;%e57/（%，%）=<（o3k02?5匕-e7/（%，%）=<（o3k0匕￡T￡Q；%wSkeS;%gD匕人￡S,Pik_3L,[%任丁其它.z/z/（P,i，P,x）=?50PikS%eT；eT;其它Qi=2.0-XN（P次，P,e）+1〃（PJmm]；"""尸、），2〃Tk=l ￡=1 IL0L。=20;0]=3;2,o=L* 0L（P欣）=<]線路p* 0L（P欣）=<]11%sL,pxL：

n（p5p,“+J=<3Pikgr-r.0其它.從上面的模型可以看出，要得到公交乘客的具體乘車路線，還必須對上述三個問題的模型進行求解，其中在可行域TR中可根據(jù)目標(biāo)函數(shù)的優(yōu)先性，對M進行有目的的搜索和篩選，方可得到解答，計算詳細(xì)步驟及算法思想見模型求解。四、模型求解4.L基于換乘次數(shù)最少的最優(yōu)路徑搜索改進算法⑸4.1.1換乘方案的選擇：根據(jù)人們的出行習(xí)慣⑹，在選擇從A站到B站的行車路線時，首先考慮是否有經(jīng)過A站直接到達B站的車，如果有，馬上會選擇直達車(如圖4-1(a)),如果存在不只一條的直達線路，在考慮所走路線的遠(yuǎn)近，選擇距離最近的乘車方案；如果沒有直達車，就會考慮換一次車的方案：即經(jīng)過A站的車與經(jīng)過B站的車是否有公共站點C。如果有,則可在公共站點C處轉(zhuǎn)車到達站點B(如圖4-1(b));如果沒有換一次車的方案，則乂要考慮乘坐經(jīng)過A點的車到某一站C下車，經(jīng)過C站點的車與經(jīng)過B站點的車是否有公共站點D,如果有，就到公共站點D轉(zhuǎn)車，兩次轉(zhuǎn)車可到達站點B(如圖4T(c))；如果沒有，則需要轉(zhuǎn)乘三次或三次以上才可到達目的地(如圖4T(d))o在上述情況中如果存在不止一種的選擇方案，則在考慮乘車距離，選擇路程最短的乘車方案。⑶直達的情況(b)換乘一次車的情況(c)換乘兩次車的的情況(d)換乘多次車的情況圖4-1公交線路換乘方案示意圖4.L2.算法設(shè)計分析對上面換乘方案選擇的分析，我們可以發(fā)現(xiàn)只有當(dāng)不同線路之間具有公共站點時才能夠進行轉(zhuǎn)車，這樣計算出來的結(jié)果有時并不符合實際情況，比如在實際出行時只需換乘兩次便可到達目的地，但計算出來的結(jié)果缺需要換乘三次或四次。出現(xiàn)這種情況的愿意是忽視了現(xiàn)實生活中人們步行小段距離在轉(zhuǎn)車的現(xiàn)象。具體地說，人們在轉(zhuǎn)車時，并不是下車后直接在下車的站點處轉(zhuǎn)車，往往需要步行一小段距離到附近的站點去轉(zhuǎn)車。人們選擇這種方式通常可以減少換乘次數(shù)，而且這種換車方式也是由站點的分布情況所決定的。參考文獻⑴已詳細(xì)分析了緊鄰站點的分布情況。緊鄰是一個半定量的距離概念,用以描述公交站點空間位置上的距離關(guān)系，通常是根據(jù)人們的行為習(xí)慣和平均公交路段長度來決定的。緊鄰站點的存在使得人們在選擇換乘路線時多了一個考慮方案，就是如果在某一站點下車后沒有直接換乘的車次，還可以考慮附近的站點是否有換乘車次。根據(jù)這種思想，本文對上面的算法進行了改進，即在換乘時，加入對緊鄰站點的判斷和分析。這種算法更加符合站點的分布情況以及人們出行時的實際選擇情況。從前面的公交乘客出行心里調(diào)查統(tǒng)計表可以看出，換乘次數(shù)最少是公交乘客出行時考慮的第一重要因素，所以就以換乘次數(shù)最少作為最優(yōu)路徑算法的第一約束目標(biāo)，而出行耗時則是公交乘客考慮的第二重要因素，所以將其作為最優(yōu)路徑算法的第二約束目標(biāo)。4.L3.算法的設(shè)計思想及步驟（I）算法的設(shè)計思想該算法的基本思想為⑸，分別從起點A、終點B出發(fā)，通過比較公交網(wǎng)絡(luò)上各車站的可換乘車站，追索A到B的可能路徑，然后比較各可能路徑的換乘次數(shù)、所用的時間來確定最佳選擇的路徑。設(shè)5（/X/=12…即）（〃?為正整數(shù)）為經(jīng)過A或其附近的線路集。丁。"=1,2,…/X〃為正整數(shù)）為經(jīng)過5或其附近的線路集。EU,UXU=1,2,…,p,p為正整數(shù)）為經(jīng)過線路S（/）上的站點。產(chǎn)（JWXV=12…國應(yīng)為正整數(shù)）為經(jīng)過線路T（J）上的站點。/?（/0小=1,2,--七）（且為正整數(shù)）為經(jīng)過石（/々）的線路。丫（。乂。=1,2,…,zXz為正整數(shù)）為經(jīng)過尸"W）的線路。G（K,卬乂卬=1,2,…,火，為正整數(shù)）線路”（K）上的站點。L（O,X）（X=1,2,--,力。為正整數(shù)）為線路丫（。）上的站點。表示站點團到達站點〃所用的時間。卬表示乘客在換車時步行距離的最大心里承受值，它時一個人為干預(yù)的經(jīng)驗值，與公交站點間的平均時間成線性相關(guān)。對于站點陽與站點〃之間的緊鄰關(guān)系，可以用一個不等式來表示:t（m,n）＜wo根據(jù)參考文獻⑼所提供的資料表明，在上海都市的公交網(wǎng)絡(luò)上，換3次車即乘坐4條線路的公交車，，方可到達目的地的情況都是很少發(fā)生的。所以根據(jù)北京市公交線路的實際情況，本文認(rèn)為三次以內(nèi)的轉(zhuǎn)車是比較合理的，超過三次的轉(zhuǎn)車情況在這里不予考慮。（n）算法的設(shè)計步驟（1）輸入乘車的起始站點4及目的站點6;;（2）求經(jīng)過站點A的所有線路集義/）和經(jīng)過站點B的所有線路集TQ）；（3）判斷S（/）=T（J）嗎?如果有，則找到了從站點A到站點6的直達線路S（/）即TQ）,輸出結(jié)果，結(jié)束運算，如果沒有則進行下一步。(4)求線路S(I)上的站點E(I,U)以及線路T(J)上的站點；(5)判斷是否存在相同站點，即七(/,U)二/QW),或者存在緊鄰站點，即滿足t(E,F)<w；如果滿足E(I,U)=F(J,V),則線路5(Z),T(J)即為一次轉(zhuǎn)車的線路，E(I,U)即為轉(zhuǎn)車站點且換車時不用更換站點；如果滿足鳳/,u)w尸a,u)但滿足，(瓦/)<卬，則線路S(/),T(J)即為一次專車線路，E(/,U)即為轉(zhuǎn)車站點但換車時要步行到緊鄰站點F(J,V)O如果沒有，再執(zhí)行下面步驟。(6)求經(jīng)過上(/，⑺的線路集H(K),經(jīng)過尸UW)的線路集y(。)；(7)判斷取K)=y(。)嗎?如果有,則線路S(/),Rg,T(J)為兩次換車的線路,換車站點為石(/，⑺和尸QW),輸出結(jié)果，結(jié)束運算；如果沒有則執(zhí)行下面步驟。(8)求線路R(K)上的站點G(K,W)和線路丫(0)上的站點L(QyX);(9)判斷是否存在相同站點，即G(K,W)="O,X),或者存在相鄰站點，即滿足t(G,L)<w；如果滿足G(K,W尸L(QX),則線路S(/),R(K),Y(O),TQ)即為三次轉(zhuǎn)車的線路，EQ,U),G(K,W),尸(J,V)即為轉(zhuǎn)車站點，且換車時不用更換站點；如果滿足G(K,W)w〃O,X)但滿足f(G,L)<卬，則在站點G(K,W)專車時要步行到緊鄰站點〃QX)。在上述情況中，滿足條件的線路可能不止一種，這時在計算每種方案的換乘次數(shù)和所用時間，取在換乘系數(shù)最少的前提下，所用的時間最短的乘車方案為最終結(jié)果輸出。其算法流程圖⑸見附錄圖(附-1)4.2求解結(jié)果根據(jù)算法思想及所提供的算法步驟，運用Matlbe軟件編程計算，所得求解結(jié)果為:針對問題一中所給六對站點的最佳路徑的計算結(jié)果如下：(1)第一條路線：S3359fsi828出行的最佳路徑為：由出發(fā)點S3359乘坐L0436路公交車，到達S3500站點，換乘L0167路公交車，到達目的地S1828站點。整個過程，換乘次數(shù)：1(次)；出行耗時：101(分鐘)；途經(jīng)總站數(shù)：32(個)；花費金額：3(元)。(2)第二條路線：SI557fs0481出行的最佳路徑為:由出發(fā)點S1557乘坐L0363路公交車，到達S1919站點，換乘L0417路公交車，到達站點S2424,然后換乘L0516路公交車到達目的地S0481站點。整個過程，換乘次數(shù)：2(次)；出行耗時：109(分鐘)；途經(jīng)總站數(shù)：33(個)；花費金額：3（元）。（3）第三條路線：SO971fs0485出行的最佳路徑為：由出發(fā)點S0971乘坐L0013路公交車，到達S2184站點，然后換乘L0417路公交車到達目的地S0485o整個過程，換乘次數(shù)：1（次），出行耗時：128（分鐘）；途經(jīng)總站數(shù)：41（個）；花費金額：3（元）。（4）第四條路線：S0008-S0073出行的最佳路徑為：由出發(fā)點S0008乘坐L0463路公交車，到達S2083站點，然后換乘L0057路公交車到達目的地S0073。整個過程，換乘次數(shù)：1（次）；出行耗時：80（分鐘）；途經(jīng)總站數(shù)：25（個）；花費金額：2（元）。（5）第五條路線：SO148fs0485出行的最佳路徑為：由出發(fā)點S0148乘坐L0308路公交車，到達S0036站點,換乘L0156路公交車到達S2210站點，然后換乘L0417路公交車到達目的地S0485。整個過程，換乘次數(shù)：2（次）；出行耗時：103（分鐘）；途經(jīng)總站數(shù)：31（個）；花費金額：3（元）。（6）第六條路線：SOO87fs3676出行的最佳路徑為：由出發(fā)點S0087乘坐L0454路公交車，到達S3496站點，然后換成L0209路公交車到達目的地S3676c整個過程，換乘次數(shù)：1（次）；出行耗時：65（分鐘）；途經(jīng)總站數(shù)：65（個）；花費金額：2（元）。2.2針對問題二最佳路徑的選擇計算結(jié)果如下：當(dāng)同時考慮公交與地鐵的情況下，相對問題一，除了第六條路線S0087-S3676有更優(yōu)的路徑選擇外，其余五條路徑均無明顯變化。第六條線路：SOO87fs3676出行的最佳路徑為：由出發(fā)點S0087進入地鐵站D27,乘坐T02路地鐵到達D36站點出站，然后到達目的地S3676公交站點。整個過程中，換乘次數(shù)：0（次）；出行耗時：40.5（分鐘）；途經(jīng)總站數(shù)：H（個）；花費金額：3（元）。2針對問題三尋求最佳路徑的方案.針對本問我們給出了出行者選擇最佳乘車路線的多目標(biāo)優(yōu)化模型及與起相匹配的算法。由于問題中所有站點之間的步行時間作為符號常量給出，所以在本文中我們不能對其進行求解，但實際生活中該符號常量可通過重復(fù)試驗測出其平均值，即可將其當(dāng)作已知常數(shù)。所以，當(dāng)考慮公汽、地鐵及在站點之間采取必要的步行措施時，我們同樣可以通過本問中所提供的多目標(biāo)優(yōu)化模型及算法求出出行者欲從起始站到達終點站所需要選擇的最佳（換乘次數(shù)最少且耗時最短）路徑及相應(yīng)花費的票價總金額。五、結(jié)果分析與檢驗在上述所求解的結(jié)果中，可以發(fā)現(xiàn)，所得到的六組路徑，都是沒有直接通達的車次,即至少需要換乘一次，其結(jié)果統(tǒng)計歸納如下：路徑中轉(zhuǎn)站換乘次數(shù)歷經(jīng)站數(shù)出行時間出行費用(1)、S3359fsi828S3500132101分鐘3元(2)、S1557fs0481S1919,S2424233109分鐘3元(3)、S0971fs0485S2184141128分鐘3元(4)、S0008fS0073S208312580分鐘2元(5)、SO148fs0485S0036,S2210231103分鐘3元(6)S0087—S3676D27,D3601140.5分鐘3元S3496,16565分鐘2元可見在這組交通路線中，增加交通工具的公交線路，不一定能改變出行者的交通路線，當(dāng)然，離在新交通工具站點附近的站點出行的乘客受到的影響則比較大如第（6）對站點。根據(jù)上表中各參數(shù)的變化關(guān)系，可見增加換乘次數(shù)，可以明顯地減少站點總數(shù),而對時間和費用的影響不大。因此本模型在考慮換乘次數(shù)上比較穩(wěn)定。六、模型評價及推廣模型的評價本文分析了公交與地鐵交通網(wǎng)絡(luò)相互配合的交通特點，建立了以換乘次數(shù)最少為第一目標(biāo)，以選擇最少乘車所用時間（或途經(jīng)站數(shù)）為第二目標(biāo)的最佳乘車路徑選擇模型,并在此模型的基礎(chǔ)上設(shè)計了廣度優(yōu)先搜索算法。在模型的建立過程中，考慮到影響乘車者選擇乘車方案的因素很多，如換乘次數(shù)，乘車時間，乘車費用等因素，所以不能簡單的將本文中的最佳路徑選擇問題抽象為最短路問題⑻。在算法的設(shè)計過程中，由于傳統(tǒng)的交通網(wǎng)絡(luò)最短路徑查詢算法⑻通常需要先求出發(fā)地和目的地之間的最短路徑，然后在考慮這個路徑上的換乘方案。這可能導(dǎo)致?lián)Q乘的次數(shù)過多而使乘車的時間和費用增加，這不符合人們的乘車習(xí)慣。而基于乘車換乘次數(shù)最少的查詢算法是一種較為符合實際的算法，符合人們的心里要求⑶；另外，傳統(tǒng)的交通網(wǎng)絡(luò)最短路徑查詢算法在計算轉(zhuǎn)乘方案時往往忽視了人們在換車時可能步行一段距離到轉(zhuǎn)乘點，而以緊鄰站點來表示這種轉(zhuǎn)乘的情況既能符合實際乂能較為有效地解決中途換乘的問題。模型的具體優(yōu)、缺點分析：優(yōu)點：.分析具有邏輯性。首先，在模型的建立過程中采取了逐層推進的方法，使其有較強的邏輯性；同時，對必要的結(jié)論加以證明，使模型的建立更有根據(jù)性。其次對模型的求解結(jié)果進行了靈敏度分析，這對出行者在最佳路徑的選擇方面具有一定的實際參考價值。.實用性強。因本文所提出的算法是通過計算機程序來實現(xiàn)求解的，所以本文中的模型和算法均可通過計算機編譯，將其轉(zhuǎn)化為計算機應(yīng)用系統(tǒng)。只要出行者從計算機輸入起點站與終點站即可得知應(yīng)選擇的最佳乘車路徑及相應(yīng)的票價總金額。這將使模型及算法具有很強的實用性。.容易推廣。本文的1,2,3問題中所建立模型的最大優(yōu)點是設(shè)計了與模型相匹配的求解算法(廣度優(yōu)先搜索算法)，這使問題的解決可通過計算機搜索的方法找出所有可共選擇路徑中的最佳路徑。本模型的建立過程及算法的設(shè)計思想同樣可以應(yīng)用到解決其它方面的類似問題，有較強的推廣價值。缺點：.本模型在建立過程中的影響因素較多，為使問題簡單化，僅研究了影響出行者選擇乘車路線的主要因素，忽略了次要因素，所以使模型在實際的應(yīng)用過程中會產(chǎn)生一定的誤差。.由于題中所給參數(shù)均為簡化問題而做的假設(shè)，而未必與實際數(shù)據(jù)完全吻合，這將給模型在推廣方面帶來一定的局限性。.1.2模型及算法的改進(1)模型功能的完善。本模型僅實現(xiàn)了城市公交，地鐵網(wǎng)絡(luò)最佳路徑的查詢目的，對于人們想了解的城市公交，地鐵其它方面的信息未能提供。所以將本模型的功能進一步擴充，完善成一個城市公交，地鐵網(wǎng)路的綜合查詢模型將是下一步改進的方向。(2)最優(yōu)路徑算法的改進。本文提出的算法僅討論了基于換乘數(shù)最少的前提下，使乘車時間最短的最佳乘車路徑選擇問題。這種算法雖然符合實際但仍存在不足之處：首先，算法的效率隨換乘次數(shù)的增加而急劇下降，特別是需要搜索緊鄰站點時。其次，算法中只考慮了換乘次數(shù)，乘車時間，途徑的站點數(shù)等幾個因素，但對于現(xiàn)實生活中影響乘車方案的其它因素，如道路阻塞程度、公共汽車發(fā)車間隔、公共汽車舒適程度等因素都未加以考慮?；谝陨嫌绊懸蛩?，增強本算法的功能性將是下一步所需要改進完善的。.L3.數(shù)據(jù)動態(tài)更新和實時查詢的實現(xiàn)。本文所研究和實現(xiàn)的的查詢系統(tǒng)是一個靜態(tài)的系統(tǒng)，數(shù)據(jù)如果發(fā)生了變更，就可能需要對其重新進行預(yù)處理，如城市公交線路的新增、改線及原來定義的屬性信息擴展等。因此本查詢系統(tǒng)還需要在系統(tǒng)功能上進一步改進完善以適應(yīng)數(shù)據(jù)的動態(tài)更新及在動態(tài)更新的基礎(chǔ)上實現(xiàn)實時查詢。6.2模型的推廣本文通過對出行者的心里調(diào)查，參考文獻⑴，得出了出行者乘交通工具時首先考慮的時途中換乘的次數(shù)最少，在此基礎(chǔ)上使所花費的時間最短。針對此條件，我們列出了以換乘次數(shù)最少為前提，滿足從出發(fā)點到達終點所花費時間最短的交通網(wǎng)絡(luò)模型，并根據(jù)建立模型的思想，設(shè)計了相應(yīng)的算法。另外，本模型填補了傳統(tǒng)的最短路法的局限性,相應(yīng)算法在應(yīng)用的過程中也具有一定的廣泛性和靈活性。尤其在情況較為復(fù)雜的一些道路交通網(wǎng)絡(luò)模型中具有較好的推廣性。如在客運路徑的選擇，最短路徑選擇方面都具有良好的推廣性。七、參考文獻[1]楊新苗、王煒、馬文騰，基于GIS的公交乘客出行路徑選擇模型[J],東南大學(xué)學(xué)報(自然科學(xué)版)，30(6)：87-88,2000年。[2]韓傳峰、胡志偉，城市公交路網(wǎng)性能評估的網(wǎng)絡(luò)圖方法[J],系統(tǒng)工程，21(3)：58-61,2003.[3]趙巧霞、馬志強、張發(fā)，以最小換乘次數(shù)和站數(shù)為目標(biāo)的公交出行算法[J],計算機應(yīng)用，24(12)：136-137,2004年。[4]楊啟帆、方道元，數(shù)學(xué)建模[M],杭州：浙江大學(xué)出版社，188-189,1999年[5]王建林，基于換乘次數(shù)最少的城市公交網(wǎng)絡(luò)最優(yōu)路徑算法[J],浙江交通職業(yè)技術(shù)學(xué)院院報，25(5)：673-676,2000.[6]陳蕭楓、蔡秀云、唐德強，最短路徑算法分析及其在公交查詢的應(yīng)用[J],工程圖學(xué)學(xué)報，(3)：20-24,2001.[7]趙玲，基于MAPINFO的城市公交信息查詢系統(tǒng)的設(shè)計與實現(xiàn)[D],中南大學(xué)碩士論文,2003.[8]嚴(yán)寒冰、劉迎春，基于GIS的城市道路網(wǎng)最短路徑算法探討[J],計算機學(xué)報，23(2)：211-215,2000.[9]陳家治，ARC/INFO路徑尋找功能的擴展：雙向比較追索法[J],上海師范大學(xué)學(xué)報(自然科學(xué)版)，(3)：78-83,2003.29附錄一：算法程序圖圖（附T）改進算法流程圖附錄二：試驗結(jié)果FROM3359TO1828:turntobusNO.436fenduanjijia(0)->S3359(1)->S2O26(2)->SU32(3)->S2266(4)->S2263(5)->S3917(6)->S2303(7)->S2301(8)->S3233(9)->S618 (10)->S616 (11)->S2U2(12)->S2110(13)->S2153(14)->S2814(15)->S2813(22)->S1768(29)->S1829(30)->S3649(31)->S1784turntobusNO.167fenduanjijia(0)->S1784(1)->S1828Fromabloveweknowthat：FromS3359ToS1828needtochangebus1times：AtbusstopS3359TakebusNO.S436AtbusstopSI784TakebusNO.S167totlecost3yuanf^cost101minitsFROM1557TO481:turntobusNO.363fenduanjijia(0)->S1557(1)->S3158(2)->S2628(3)->S3408(4)->S2044(5)->S1985(6)->S2563(7)->S2682(8)->S2735(9)->S29 (10)->S55 (11)->S1919turntobusNO.417fenduanjijia(0)->S1919(1)->S2O79(2)->S641(3)->S2840(4)->S1402(5)->S2717(6)->S3409(7)->S3186(8)->S3544(9)->S2116(10)->S2U9(11)->S1789(12)->S1770(13)->S2322(14)->S992(15)->S2184(16)->S2515(17)->S2424turntobusNO.516fenduanjijia(0)->S2424(1)->S1174(2)->S902(3)->S903(4)->S2101(5)->S481Fromabloveweknowthat：ToS481needtochangebus2times：AtbusstopS1557TakebusNO.S363AtbusstopS1919TakebusNO.S417AtbusstopS2424TakebusNO.S516FromS1557(15)->S2813(22)->S1768(29)->S1829(30)->S3649(31)->S1784turntobusNO.167fenduanjijia(0)->S1784(1)->S1828Fromabloveweknowthat：FromS3359ToS1828needtochangebus1times：AtbusstopS3359TakebusNO.S436AtbusstopSI784TakebusNO.S167totlecost3yuanf^cost101minitsFROM1557TO481:turntobusNO.363fenduanjijia(0)->S1557(1)->S3158(2)->S2628(3)->S3408(4)->S2044(5)->S1985(6)->S2563(7)->S2682(8)->S2735(9)->S29 (10)->S55 (11)->S1919turntobusNO.417fenduanjijia(0)->S1919(1)->S2O79(2)->S641(3)->S2840(4)->S1402(5)->S2717(6)->S3409(7)->S3186(8)->S3544(9)->S2116(10)->S2U9(11)->S1789(12)->S1770(13)->S2322(14)->S992(15)->S2184(16)->S2515(17)->S2424turntobusNO.516fenduanjijia(0)->S2424(1)->S1174(2)->S902(3)->S903(4)->S2101(5)->S481Fromabloveweknowthat：ToS481needtochangebus2times：AtbusstopS1557TakebusNO.S363AtbusstopS1919TakebusNO.S417AtbusstopS2424TakebusNO.S516FromS1557FROMtotlecost3yuanf^cost109minits971TO485:turntobusNO.13fenduanjijia(0)->S971(1)->S3832(2)->S3341(3)->S2237(4)->S3565(5)->S3333(6)->S1180(7)->S3491(8)->S1523(9)->S1520(10)->S1988(11)->S1743(12)->S1742(13)->S1181(14)->S1879(15)->S3405(16)->S2517(17)->S3U7(18)->S2954(19)->S531(20)->S2184turntobusNO.417fenduanjijia(0)->S2184(1)->S992(2)->S2322(3)->S1770(4)->S1789(5)->S2119(6)->S2116(7)->S3544(16)->S3501(17)->S3515(18)->S3500(19)->S756 (20)->S492 (21)->S903(23)->S955 (24)->S480 (25)->S2703(26)->S2800(27)->S2192(28)->S2191(8)->S3186(9)->S3409(10)->S2717(11)->S14O2(12)->S2840(13)->S643 (14)->S2079(15)->S1920(16)->S2480(17)->S2482(18)->S2210(19)->S3332(20)->S3351(21)->S485Fromabloveweknowthat：FromS971ToS485needtochangebus1times：AtbusstopS971TakebusNO.S13AtbusstopS2181TakebusNO.S417totlecost2yuanf^cost128minitsFROM8TO73:turntobusNO.463yiyuantong(0)->S8(1)->S1688(2)->S3459(3)->S2532(4)->S3474(5)->S369(6)->S1776(7)->S2855(8)->S338(9)->S2849(10)->S2782(11)->S935(12)->S2084(13)->S2083turntobusNO.57fenduanjijia(0)->S2083(1)->S1538(2)->S3547(3)->S609(4)->S483(5)->S604(6)->S2650(7)->S3470(8)->S2619(9)->S2340(10)->S3162(11)->S2181(12)->S73Fromabloveweknowthat：FromS8ToS73needtochangebus1times：AtbusstopS8TakebusNO.S463AtbusstopS2083TakebusNO.S57totlecost2yuanf^cost80minitsFROM148TO485:turntobusNO.308fenduanjijia(0)->S148⑴->S462 (2)->S361 (3)->S1797(4)->S2221(5)->S302(6)->S2222(7)->S2737(8)->S1716(9)->S128(8)->S3186(9)->S3409(10)->S2717(11)->S14O2(12)->S2840(13)->S643 (14)->S2079(15)->S1920(16)->S2480(17)->S2482(18)->S2210(19)->S3332(20)->S3351(21)->S485Fromabloveweknowthat：FromS971ToS485needtochangebus1times：AtbusstopS971TakebusNO.S13AtbusstopS2181TakebusNO.S417totlecost2yuanf^cost128minitsFROM8TO73:turntobusNO.463yiyuantong(0)->S8(1)->S1688(2)->S3459(3)->S2532(4)->S3474(5)->S369(6)->S1776(7)->S2855(8)->S338(9)->S2849(10)->S2782(11)->S935(12)->S2084(13)->S2083turntobusNO.57fenduanjijia(0)->S2083(1)->S1538(2)->S3547(3)->S609(4)->S483(5)->S604(6)->S2650(7)->S3470(8)->S2619(9)->S2340(10)->S3162(11)->S2181(12)->S73Fromabloveweknowthat：FromS8ToS73needtochangebus1times：AtbusstopS8TakebusNO.S463AtbusstopS2083TakebusNO.S57totlecost2yuanf^cost80minitsFROM148TO485:turntobusNO.308fenduanjijia(0)->S148⑴->S462 (2)->S361 (3)->S1797(4)->S2221(5)->S302(6)->S2222(7)->S2737(8)->S1716(9)->S128(10)->S2268(11)->S13O8(12)->S1391(13)->S2272(14)->S36turntobusNO.156yiyuantong(0)->S36(1)->S618(2)->S617(3)->S721(4)->S2057(5)->S2361(6)->S608(7)->S399turntobusNO.156yiyuantong(0)->S36(1)->S618(2)->S617(3)->S721(4)->S2057(5)->S2361(6)->S608(7)->S399(8)->S2535(9)->S2534(10)->S239(11)->S497(12)->S2090(13)->S2082(14)->S2210(8)->S2535(9)->S2534(10)->S239(11)->S497(12)->S2090(13)->S2082(14)->S2210turntobusNO.417fenduanji??turntobusNO.417fenduanji??Jia(0)->S2210(1)->S3332(2)->S3351(3)->S485(0)->S2210(1)->S3332(2)->S3351(3)->S485Fromabloveweknowthat：Fromabloveweknowthat：FromS148ToS485needtochangebus2times：FromS148ToS485needtochangebus2times：AtbusstopS148TakebusNO.S308AtbusstopS148TakebusNO.S308AtbusstopS36TakebusNO.S156AtbusstopS2210TakebusNO.S417totlecost3yuanf^cost103minitsFROM 87TO3676:turntobusNO.454fenduanjijiaturntobusNO.454fenduanjijia(0)->S87(1)->S857 (2)->S630 (3)->S1427(4)->S1426(5)->S541 (6)->S978(7)->S3389(8)->S1919(9)->S641(10)->S2840(11)->S3196(0)->S87turntobusNO.209 yiyuantong(0)->S3496(1)->S1883(2)->S1159(3)->S2699(4)->S2922(5)->S3010(6)->S583(7)->S1987(8)->S82 (9)->S3676Fromabloveweknowthat：ToS3676needtochangebus1times：AtbusstopS87ToS3676needtochangebus1times：AtbusstopS87TakebusNO.S454AtbusstopS3496TakebusNO.S209FromS87totlecost2yuan￡icost65minits附錄三、源程序%C0PYRIGHRWANGBO2007SUSE%C0PYRIGHRWANGBO2007SUSE%functionmcm2007testclear;clc;Stopp=[3359,1828,1557,481,971,485,8,73,148,485,87,3676];%實驗待求解數(shù)據(jù)loadbase_dat.txt為調(diào)用基本數(shù)據(jù)庫loadrailway,txt%調(diào)用fp二fopenCmcm2007.doc','w');rail=railway;data=base_dat;為公交車線路總數(shù)%theminnumberofbusstop為公交車線路總數(shù)%theminnumberofbusstop%themaxnumberofbusstopmin_nobs=l;max_nobs=3957;max_stop=l;maxbins=l;num_s_by_b=zeros(2,max_stopT,numbejbus)每輛公交車痛毆過各個站點的順序(分上行和下行)num_b_in_s(max_nobs,max_b_in_s)=O;羯通過每個站點的公交車編號stop=ones(1,max_nobs);先求出通過每個站點的公交車路數(shù)與每輛公交車通過的站點的順序fori=l:number_bus先求出通過每個站點的公交車路數(shù)forj=2:untIzero(data(4*(i-l)+3,:))ifnotin(data(4*(i-l