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

《公交線路轉(zhuǎn)乘選擇的優(yōu)化模型數(shù)學(xué)建模論文》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

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

2、為兩條線路是否可以直接相交以及在何處相交的信息矩陣；其次以換乘時(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，，最短時(shí)間73分鐘，費(fèi)用3元；組（2）：S1557→S0481，，最短時(shí)間106分鐘，費(fèi)用3元。同時(shí)文章對運(yùn)算結(jié)果進(jìn)行了相關(guān)分析。在問題二建模過程中，沿用問題一的求解思想，將新增加的地鐵視為新的線路，將所有線路信息轉(zhuǎn)化為新的轉(zhuǎn)乘矩陣，同時(shí)按照新的背景得到新的乘車時(shí)間與費(fèi)用計(jì)算方法，同樣以最短時(shí)間為目標(biāo)，

3、相同的算法可以得到問題二的結(jié)果（以(5),(6)組為例，具體見正文表2）：組（5）：S0148→S0485，最短時(shí)間87.5分鐘，費(fèi)用5元；組（6）：S0087→S3676，，最短時(shí)間28分鐘（已經(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í)間的最小值決定。從而將問題三歸結(jié)為一個(gè)

4、有向圖的最短路模型，文章對此模型給出了算法建議。最后文章對所提出的模型進(jìn)行了優(yōu)缺點(diǎn)分析與推廣評價(jià)。關(guān)鍵詞：城市公交線路、圖與網(wǎng)絡(luò)、最短路模型、動(dòng)態(tài)規(guī)劃29一、問題重述：近些年來，城市公共交通系統(tǒng)有了很大發(fā)展，使得公眾的出行更加通暢、便利。絕大多數(shù)市民出行時(shí)首先會(huì)考慮選擇公交設(shè)施，同時(shí)也面臨如何在眾多條線路中如何選擇合適線路的問題。針對市場需求，要求開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)，可以滿足查詢者的各種不同需求，對不同的起點(diǎn)和終點(diǎn)給出最佳的公交轉(zhuǎn)乘路線。競賽要求設(shè)計(jì)線路選擇的模型與算法，解決以下三個(gè)問題：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路

5、選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用模型與算法，求出以下6對起始站→終到站之間的最佳路線（要有清晰的評價(jià)說明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同時(shí)考慮公汽與地鐵線路，解決以上問題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。二、問題分析：（1）從影響出行選擇的因素看，每個(gè)人主要會(huì)從兩個(gè)標(biāo)準(zhǔn)對線路進(jìn)行選擇與優(yōu)劣衡量：從起點(diǎn)到終點(diǎn)所需要的總時(shí)間最短；從起點(diǎn)到終點(diǎn)需

6、要花費(fèi)的費(fèi)用。（2）從本質(zhì)上講，選擇線路的問題可以歸結(jié)為最短路問題，但是考慮到轉(zhuǎn)乘線路需要時(shí)間，并且一條公交線路不能按照站點(diǎn)進(jìn)行拆分，因此以每個(gè)站點(diǎn)構(gòu)造路線圖不利于解決問題。注意到從起點(diǎn)站到目標(biāo)站關(guān)鍵是選擇乘坐哪些公交線路，需要在公交線路中如何選擇轉(zhuǎn)乘線路，因此可以以公交線路為頂點(diǎn)，以兩個(gè)站點(diǎn)之間是否可以轉(zhuǎn)乘為弧構(gòu)造圖，而點(diǎn)到點(diǎn)之間最佳路線的選擇可以轉(zhuǎn)化為經(jīng)過分別兩個(gè)端點(diǎn)的公交線路集合之間的最短路問題。同時(shí)我們需要任意兩個(gè)線路之間是否可以轉(zhuǎn)乘的信息。（3）在給出的線路信息中，我們發(fā)現(xiàn)主要有三類線路：下行線路與上行線路不同，下行線路是上行線路的原路返回，環(huán)形線路。為

7、了區(qū)分同一條線路不同的運(yùn)行方向，我們?nèi)藶榈貙⒚恳粭l線路變?yōu)閮蓷l線路，這樣做既可以分清楚所換乘的是那條線路的哪個(gè)方向，同時(shí)也可以將兩條線路換乘點(diǎn)的信息與每個(gè)站點(diǎn)在本條線路上的位置相聯(lián)系，這樣可以用來判斷乘坐某條線路公交車從某個(gè)站點(diǎn)出發(fā)時(shí)，可以換乘哪些公交線路（換乘站點(diǎn)必須在乘車點(diǎn)沿著公交車運(yùn)行方向的后方）。（4）在公交線路信息中，與決策目標(biāo)有關(guān)的元素還有每條線路的計(jì)費(fèi)方式及每條線路乘坐時(shí)花費(fèi)的時(shí)間。對于計(jì)費(fèi)方式，我們按照單一票價(jià)與分段計(jì)價(jià)進(jìn)行識別，分段計(jì)價(jià)與乘坐的站點(diǎn)數(shù)有關(guān)，這也是我們需要每個(gè)站點(diǎn)在每條線路上具體位置的原因；同樣運(yùn)行時(shí)間也與站點(diǎn)的具體位置有關(guān)。（5）

8、問題一僅對