公交線路轉(zhuǎn)乘選擇的優(yōu)化模型數(shù)學(xué)建模論文

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

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

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

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

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

6、問題三歸結(jié)為一個(gè)有向圖的最短路模型，文章對此模型給出了算法建議。最后文章對所提出的模型進(jìn)行了優(yōu)缺點(diǎn)分析與推廣評價(jià)。關(guān)鍵詞： 關(guān)鍵詞：城市公交線路、圖與網(wǎng)絡(luò)、最短路模型、動(dòng)態(tài)規(guī)劃3否可以換乘的信息表現(xiàn)出即可。問題三增加步行信息后，問題變得較為復(fù) 雜，因?yàn)槲覀儾⒉恢涝谀男┑胤綄叫?，因此我們采用簡單列舉的方法建立模型。三、 模型假設(shè)：1．乘客在乘坐公交線路過程中，以平均耗時(shí)為實(shí)際乘車、等車、轉(zhuǎn)乘耗時(shí)；2．乘客在選擇轉(zhuǎn)乘線路時(shí)，考慮的因素

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

8、i ? i L：存儲每條線路的收費(fèi)信息； C：?？?的所有公交線路的集合； ) ( i S SB i S：線路 ?？康乃姓军c(diǎn)； ) ( i L LB i L：乘坐 從其第 站到第 （ ）站的費(fèi)用 ) , , ( b a i Cost i L a b a b ?：表示從線路 的第 站到第 站的時(shí)間函數(shù) ) ( ) , , ( a b T b a i Tim b b ? ? i L a b：表示相鄰公汽站平均行駛時(shí)間，本題為 3 b b

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