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