公交線路轉乘選擇的優(yōu)化模型數學建模論文

1、1公交線路轉乘選擇的優(yōu)化模型摘要： 摘要：本文以奧運會的公交線路換乘為大背景，建立了在公汽線路、地鐵以及步行三種方式中綜合進行路線轉乘的模型。此問題可以歸結為兩個站點之間的最短路問題，由于直接以站點構建最短路問題計算量較大，本文在處理三個問題 時分別提出了相應的模型與求解算法，以乘坐時間最短為標準回答了問題一與問題二，對問題三提出了最短路模型。在問題一建模過程中，我們以任意兩條線路是否可以直接換乘為突破口，建立了以每條線路為頂點，兩條線

2、路之間的換乘信息為弧的圖，將問題一歸結為弧長可變的最短路問題，提出了結合動態(tài)規(guī)劃方法與分枝定界思想的算法。首先將題目所給出的路線與站點信息翻譯為兩條線路是否可以直接相交以及在 何處相交的信息矩陣；其次以換乘時間最短或者費用最小為決策函數，建立動態(tài)規(guī)劃問題；再次設計相應的算法進行求解。通過求解，以最短時間為目標，問題一的結果如下所示（以(1),(2)組為例，其它見正文表1）：組（1）：S3359→S1828， 1828 458 2903

3、3359 41 201 15 S S S S L L L ? ?? ? ? ? ? ? ?? ?，最短時間73分鐘，費用3元；組（2）：S1557→S0481， 481 3186 1919 1557 460 189 84 S S S S L L L ? ? ? ? ? ? ? ? ? ?? ?，最短時間106分鐘，費用3元。同時文章對運算結果進行了相關分析。在問題二建模過程中，沿用問題一的求解思想，將新增加的地鐵視為新的線路，將所有線路

4、信息轉化為新的轉乘矩陣，同時按照新的背景得到新的乘車時間與費用計算方法，同樣以最短時間為目標，相同的算法可以得到問題二的結果（以(5),(6)組為例，具體見正文表2）：組（5）：S0148→S0485，最短時間 87.5 分鐘， 485 466 21 02 1487 0148 51 1 24 S S D D S S L T L ? ?? ? ? ?? ? ? ? ?? ?費用 5 元；組（6）：S0087→S3676， ，最短時間28分

5、鐘 3676 36 27 0087 2 S D D S T ? ?? ? ?（已經加上地鐵站到地面站點的步行時間，其中地鐵運行時間20分鐘） ，費用3元。在問題三建模過程中，由于增加了步行的信息，問題一、二的方法無法直接使用，文章建立了一個新的最短路問題。以每個站點為頂點，以兩個頂點之間的最短路徑（最短達到時間或者最小到達費用）為弧構造有向圖，其中最短達到時間由問題二得到的兩個站點之間使用公交網絡的換乘時間與步行時間的最小值決定。從而將

6、問題三歸結為一個有向圖的最短路模型，文章對此模型給出了算法建議。最后文章對所提出的模型進行了優(yōu)缺點分析與推廣評價。關鍵詞： 關鍵詞：城市公交線路、圖與網絡、最短路模型、動態(tài)規(guī)劃3否可以換乘的信息表現出即可。問題三增加步行信息后，問題變得較為復 雜，因為我們并不知道在哪些地方將會步行，因此我們采用簡單列舉的方法建立模型。三、 模型假設：1．乘客在乘坐公交線路過程中，以平均耗時為實際乘車、等車、轉乘耗時；2．乘客在選擇轉乘線路時，考慮的因素

7、有兩個：花費的時間最少與費用最??； 3．在計算換乘時間時，由公交車換公交車、地鐵換地鐵、公交車換地鐵以及地鐵換公交車時不單獨計算步行時間；4．由起點所在站點直接乘坐地鐵及從地鐵直接到終點時，需單獨計算步行時間。四、 符號說明及定義：：衡量每條線路在每個站點是否?？康?0—1 矩陣； ) , ( j i LS：衡量每條線路經過的每個站點是從起點起算的第幾站的矩陣； ) , ( j i LSN：線路 的?？空军c向量 :) , (i LS L

8、i ? i L：存儲每條線路的收費信息； C：?？?的所有公交線路的集合； ) ( i S SB i S：線路 停靠的所有站點； ) ( i L LB i L：乘坐 從其第 站到第 （ ）站的費用 ) , , ( b a i Cost i L a b a b ?：表示從線路 的第 站到第 站的時間函數 ) ( ) , , ( a b T b a i Tim b b ? ? i L a b：表示相鄰公汽站平均行駛時間，本題為 3 b b

9、T：從站點 經過一系列線路到達 的總時間 ) , , ( n m S S Time ? m S n S：從站點 經過一系列線路到達 的總費用 ) , , ( n m S S TCost ? m S n S：所有線路的轉乘矩陣 TR：公交線路 ， 兩兩轉乘集合； ) , ( j i tr i L j L：為所有站點集合； V：有向圖中表示兩個站點之間最短距離（最少時間或者最少費用）信息 E五、 問題一建模與求解一個城市所有的公交線路和停車