數(shù)學(xué)建模論文-公交系統(tǒng)最佳路線的查詢模型.doc

1公交系統(tǒng)最佳路線的查詢模型摘要本文針對“乘公交，看奧運(yùn)”的問題，建立了多目標(biāo)優(yōu)化模型，解決了僅坐公車，可坐公車和地鐵，可坐公車、地鐵或步行等三種情況下最佳出行路線的確定問題。對于問題一，我們用多目標(biāo)決策中的分層序列法對該多目標(biāo)問題優(yōu)化，建立了分別以“換乘次數(shù)最少為第一目標(biāo)，出行時(shí)間最短和車費(fèi)最少為第二、第三目標(biāo)”和以“出行時(shí)間最短為第一目標(biāo)，換乘次數(shù)最少和車費(fèi)最少為第二、第三目標(biāo)”的優(yōu)化模型和模型。同時(shí)，給出了乘客滿意度函數(shù)，根據(jù)不同乘客的需求，對這兩種模型進(jìn)行了比較，滿足了不同乘客的需求。在模型情況下，6對起始站終點(diǎn)站的最佳線路有：18283559SS：最佳路線有2條，轉(zhuǎn)車1次，耗時(shí)104分，車費(fèi)共3元；04811557SS：最佳路線有2條，轉(zhuǎn)車2次，耗時(shí)109分，車費(fèi)共3元；04850971SS：最佳路線有1條，轉(zhuǎn)車1次，耗時(shí)131分，車費(fèi)共2元；00730008SS：最佳路線有5條，轉(zhuǎn)車1次，耗時(shí)86分，車費(fèi)共2元；04850148SS：最佳路線有1條，轉(zhuǎn)車2次，耗時(shí)109分，車費(fèi)共3元；36760087SS：最佳路線有1條，轉(zhuǎn)車1次，耗時(shí)68分，車費(fèi)共2元。對于問題二，我們通過改進(jìn)后的Floyd算法，將地鐵交通系統(tǒng)嵌入原有的公交系統(tǒng)中，并分層序列法建立的優(yōu)化模型，得出了較第一問時(shí)間上更優(yōu)化的路線。6對起始站終點(diǎn)站的最佳線路有：18283559SS：最佳路線有1條，共轉(zhuǎn)車3次，其中公交與地鐵間轉(zhuǎn)乘2次，地鐵與地鐵間轉(zhuǎn)乘1次，耗時(shí)87.5分鐘，車費(fèi)共計(jì)5元。04850971SS：最佳路線有10條，轉(zhuǎn)車2次，都為公交與地鐵間轉(zhuǎn)車，耗時(shí)99分鐘，車費(fèi)共計(jì)5元。00730008SS：最佳路線有1條，轉(zhuǎn)車2次，其中公交與地鐵間轉(zhuǎn)乘2次，地鐵與地鐵間轉(zhuǎn)乘1次，耗時(shí)56.5分鐘，車費(fèi)共計(jì)5元。36760087SS：最佳路線有1條，轉(zhuǎn)車0次，通過地鐵到達(dá)，耗時(shí)30分鐘，車費(fèi)共計(jì)3元。對于問題三，我們提出了交通阻抗的概念，得到了乘客在公交線上出行的換乘次數(shù)、出行時(shí)間、乘車費(fèi)用、乘車距離等綜合費(fèi)用指標(biāo)，將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為了單目標(biāo)優(yōu)化問題。并以18283559SS為例，進(jìn)行了計(jì)算，得出對于最佳路線為3359S乘坐（下行）436L在S1784下車，步行一站至1828S。關(guān)鍵詞：多目標(biāo)優(yōu)化模型；分層序列法；乘客滿意度；交通阻抗；綜合費(fèi)用指標(biāo)2一、問題重述我國人民翹首企盼的第29屆奧運(yùn)會明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場觀看奧運(yùn)比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問題。針對市場需求，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)。為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。請你們解決如下問題：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站終到站之間的最佳路線（要有清晰的評價(jià)說明）。(1)、S3359S1828(2)、S1557S0481(3)、S0971S0485(4)、S0008S0073(5)、S0148S0485(6)、S0087S36762、同時(shí)考慮公汽與地鐵線路，解決以上問題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。二、問題分析該問題是一個(gè)解決城市公交系統(tǒng)最佳路線的優(yōu)化問題。首先，由于原題中給的數(shù)據(jù)不規(guī)范，為了實(shí)現(xiàn)Matlab的編程，須對數(shù)據(jù)進(jìn)行預(yù)處理。對數(shù)據(jù)初步分析，可以發(fā)現(xiàn)，一般來說，每條線路都有上行和下行之分，但如果下行線是上行線原路返回或是環(huán)線，即缺失了下行線數(shù)據(jù)。為了簡化編程，我們將缺失的下行數(shù)據(jù)進(jìn)行如下處理：若下行線是上行線的原路返回，則將上行線的站點(diǎn)逆置后加到對應(yīng)的下行線中；而對于環(huán)行線，則直接照搬到對應(yīng)的下行線中。其次，解決城市公交系統(tǒng)的最優(yōu)路線選擇問題，需要結(jié)合乘客的多方需要，從市場調(diào)查分析中，我們可以把乘客的基本需求歸納為：換乘次數(shù)應(yīng)盡量減少；乘車時(shí)間應(yīng)盡量節(jié)省；乘車費(fèi)用應(yīng)盡量降低；乘車經(jīng)過的站數(shù)盡量少。因此，我們應(yīng)該建立一個(gè)多目標(biāo)的優(yōu)化模型來對最優(yōu)線路進(jìn)行選擇。再次，對城市公交路線進(jìn)行最優(yōu)分析，需要把公交系統(tǒng)的實(shí)體抽象成圖論中的網(wǎng)絡(luò)拓?fù)鋱D，Dijkstra算法是當(dāng)今在最短路問題中比較常用的方法，但是在此處，該算法不完全適用，因?yàn)椋?該算法要求要求給出兩點(diǎn)間的直接距離，而在此處，上千個(gè)公交站點(diǎn)之間的距離并未直接給出，我們需要在考慮時(shí)間、票價(jià)的同時(shí)給出相應(yīng)的權(quán)值，工作量較大。2該算法算出的是一點(diǎn)到其余各點(diǎn)的權(quán)值最少路徑，城市的公交站點(diǎn)有上千個(gè)，用該算法計(jì)量很大，使公交系統(tǒng)的查詢時(shí)間過長。33該算法給出的是最短路徑圖，在選擇路線的時(shí)候可能適用，但在選擇公交路線時(shí)可能未考慮乘客不愿意轉(zhuǎn)乘的心理，其計(jì)算結(jié)果可能造成乘客需要換乘好幾次或十幾次才能夠到達(dá)目的地,這顯然是沒有任何意義的。因此我們采用了改進(jìn)的Dijkstra算法對問題進(jìn)行求解。最后，在第二問同時(shí)考慮公交和地鐵線路時(shí)，出現(xiàn)了一個(gè)地鐵站對應(yīng)一個(gè)或多個(gè)公車站的情況，由于一個(gè)地鐵站對應(yīng)的多個(gè)公車站之間可以通過地鐵站換乘，必須對題中給出的換乘時(shí)間及步行時(shí)間做進(jìn)一步細(xì)化，如表1表1細(xì)化后換乘時(shí)間表公汽車站間步行平均耗時(shí)21t分鐘地鐵車站間步行平均耗時(shí)22t分鐘公汽車站與地鐵站間步行平均耗時(shí)43t分鐘等待公車的平均耗時(shí)34t分鐘等待地鐵的平均耗時(shí)25t分鐘公汽換乘公汽平均耗時(shí)56t分鐘地鐵換乘地鐵平均耗時(shí)47t分鐘地鐵換乘公汽平均耗時(shí)78t分鐘公汽換乘地鐵平均耗時(shí)69t分鐘第三問增加步行的方式，加大了路線選擇的靈活性，但由于各站點(diǎn)之間的明確距離或步行時(shí)間未給出，我們只能給出初步的模型。三、模型假設(shè)1.假設(shè)題目所給的數(shù)據(jù)真實(shí)可靠；2各種公交方式都正常運(yùn)行，如：公交車道不堵車，每列地鐵正點(diǎn)按班到站等。3各種公交方式的平均鄰站行駛時(shí)間及換乘時(shí)間基本符合實(shí)際情況。4.乘客所能接受的最大換乘次數(shù)為2次，若包括地鐵與地鐵之間的換乘，乘客的最大換乘次數(shù)不超過3次。4四、定義與符號說明N表示換乘總次數(shù)M表示乘車總費(fèi)用T表示乘車總耗時(shí)表示通過車站jS的公車數(shù)表示兩站iS、jS之間可直達(dá)的公車數(shù)表示iS和jS之間的一次中轉(zhuǎn)站個(gè)數(shù)表示與iS可通過一次公車直達(dá)的車站個(gè)數(shù)表示能在地鐵站lD換乘的公車數(shù)表示從地鐵站iD到地鐵站jD所有路徑數(shù)jS表示公車站)3,2,1(),(aaSBj表示通過車站jS的公車)3,2,1(),(ddSSPji表示兩站iS、jS之間可直達(dá)的公車)3,2,1(),(1ddSSTji表示乘),(dSSPji車從iS到j(luò)S的時(shí)間)3,2,1(),(1ddSSMji表示乘),(dSSPji車從iS到j(luò)S的車費(fèi))3,2,1(),(eeSSiz表示與iS可通過一次公車直達(dá)的車站)3,2,1(),(hhSSCji表示iS和jS之間的一次中轉(zhuǎn)站)3,2,1(),(rrDSld表示能在地鐵站lD換乘的公車),2,1(),(2wwDDTji表示從地鐵站iD到地鐵站jD的時(shí)間2M表示從地鐵站iD到地鐵站jD的車費(fèi)5五、問題一的模型建立與求解（一）模型的分析首先，選擇公交方式出行時(shí),可行的乘車方案一般有多個(gè),出行者必須做出選擇。而出行者考慮的因素很多,不能簡單的抽象為最短路問題。因此需要對公交乘客的出行心理、行為進(jìn)行調(diào)查研究，確定模型的優(yōu)化目標(biāo)和約束條件。公交乘客選擇出行路徑的決策過程主要受到以下4個(gè)因素的影響:“換乘次數(shù)”、“出行距離”、“出行耗時(shí)”和“車費(fèi)”。所以，這個(gè)問題是一個(gè)多目標(biāo)優(yōu)化問題。其目標(biāo)是，MinMinMinMinFNMT由于同時(shí)處理多個(gè)目標(biāo)問題的最優(yōu)化較困難，經(jīng)常是有所失才能有所得，故我們采用分層序列法分析。分層法的思想是把目標(biāo)按其重要性給出一個(gè)序列，分為最重要目標(biāo)，次要目標(biāo)等等。為了得出各項(xiàng)指標(biāo)的重要性，我們查找了相關(guān)資料。圖1是1999年在南京市的8個(gè)主要公交站點(diǎn)進(jìn)行了一次公交乘客出行心理問詢調(diào)查結(jié)果。由圖1可見,41.16%的乘客在選擇出行路徑時(shí)首選考慮的是換乘最少,其次是時(shí)間最短。并考慮到題目數(shù)據(jù)中只給出的耗時(shí)數(shù)據(jù)及乘車費(fèi)用,而且一般來說，當(dāng)相鄰公汽站平均行駛時(shí)間和換乘車時(shí)間基本確定時(shí)，路程的長短與出行時(shí)間的長短成正比。故除了換乘次數(shù)，我們還選擇了易于量化的“公交出行時(shí)間最少”和“車費(fèi)最少”。在上述分析的基礎(chǔ)上，我們分別選用“換乘次數(shù)最少”和“時(shí)間最少”作為第一優(yōu)化目標(biāo),建立了分層優(yōu)化的多目標(biāo)模型和模型。6（二）模型的建立1按上所述，模型以換乘次數(shù)最少為第一目標(biāo)，出行時(shí)間最短和車費(fèi)最少分別為第二和第三目標(biāo)。設(shè)其序列分別為)(0xN，)(0xT，)(0xM，然后逐個(gè)將其最優(yōu)化：對第一目標(biāo)即換乘次數(shù)最少求最優(yōu)并找出所有最優(yōu)解的集合記為0R。然后在0R內(nèi)求第二個(gè)目標(biāo)即出行時(shí)間最短的最優(yōu)解，記這時(shí)的集合為1R。最后在1R內(nèi)求第三目標(biāo)即乘車費(fèi)用最少的最優(yōu)解，記這時(shí)的集合為2R,其模型如下：)()(0010xNxNMinRRxMinRRxxT01)(01)(0xTMinRRxxM12)(01)(0xM若2R，則集合2R為模型的最佳線路。2算法的描述（1）算法的流程圖描述流程圖如圖2。圖2模型算法流程圖7（2）算法的數(shù)學(xué)描述1)符號定義1.起始站為mS，則通過起始站的公車為),(bSBm；2.終點(diǎn)站為nS，則通過終點(diǎn)站的公車為),(cSBn。2）若存在cb,使得),(),(cSBbSBnm，則mS與nS可直達(dá)做該次公車從iS到j(luò)S的時(shí)間為),(1dSSTji；車費(fèi)為),(1dSSMji。這種情況下優(yōu)化第二目標(biāo)的算法為Min41),(tdSSTnm；優(yōu)化第三目標(biāo)的算法為Min),(1dSSMnm。3)若通過換乘車一次可到達(dá)考慮起始站和終點(diǎn)站，那么有),(fSSmz、),(gSSnz。若存在gf,，使得),(),(gSSfSSnzmz，說明mS和nS可以通過),(fSSmz即),(gSSnz站中轉(zhuǎn)。那么乘客所乘的公車車次為分別為),(,(,uhSSCSPnmm、),),(vShSSCPnnm。這種情況下優(yōu)化第二目標(biāo)的算法為Min64