公交線(xiàn)路優(yōu)化模型

《公交線(xiàn)路優(yōu)化模型》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、公交線(xiàn)路選擇的網(wǎng)絡(luò)優(yōu)化模型摘要本文針對(duì)城市公交線(xiàn)路選擇問(wèn)題建立了相應(yīng)的數(shù)學(xué)模型。將查詢(xún)者尋找連接兩點(diǎn)的最佳線(xiàn)路的過(guò)程看作車(chē)輛將查詢(xún)者從起始站點(diǎn)運(yùn)輸?shù)侥康恼军c(diǎn)的過(guò)程，對(duì)于此類(lèi)運(yùn)輸問(wèn)題，可以建立網(wǎng)絡(luò)流模型來(lái)求解。對(duì)于問(wèn)題一，將公汽站點(diǎn)看作頂點(diǎn)，3957個(gè)公汽站點(diǎn)再加上源點(diǎn)S和收點(diǎn)T就構(gòu)成了頂點(diǎn)集V。至于有向邊vivj，并不是公汽站點(diǎn)間的實(shí)際線(xiàn)路，而是表明任意兩站點(diǎn)i與j之間能否直達(dá)的有向弧，各邊的容量為1、費(fèi)用率為bij,就構(gòu)造了容量費(fèi)用網(wǎng)絡(luò)。再定義0-1變量fij作為流量，當(dāng)fij=1時(shí)表明該有向邊vivj中有流量通過(guò)，即最佳路線(xiàn)包括邊vivj，就可以建立最小費(fèi)用流模型來(lái)求解。由于源

2、點(diǎn)S的出度和匯點(diǎn)T的入度均為1，且所有有向邊的容量cij=1，此最小費(fèi)用流問(wèn)題便轉(zhuǎn)化為從vs到vt的最短路徑問(wèn)題，本文采用改進(jìn)的Dijkstra算法求解此最短路問(wèn)題。結(jié)合實(shí)際情況，本文從出行花費(fèi)、換乘次數(shù)、出行時(shí)間三方面來(lái)理解所謂的“最佳線(xiàn)路”，用mij、kij和qij分別表征這三個(gè)目標(biāo)的費(fèi)用率，再引入優(yōu)先因子來(lái)區(qū)分各目標(biāo)的優(yōu)先級(jí)，并結(jié)合實(shí)際增加換乘次數(shù)、費(fèi)用、時(shí)間的上限約束，建立了類(lèi)似目標(biāo)規(guī)劃的網(wǎng)絡(luò)流模型，編程可求出任意兩點(diǎn)在六種情況下的最佳線(xiàn)路。對(duì)于問(wèn)題二，其實(shí)就是在問(wèn)題一的容量費(fèi)用網(wǎng)絡(luò)中增加了39個(gè)頂點(diǎn)及部分有向邊，仍舊是一個(gè)最小費(fèi)用流問(wèn)題，還可以用問(wèn)題一中的方法求解，只是費(fèi)

3、用、換乘時(shí)間的計(jì)算比問(wèn)題一復(fù)雜。對(duì)于問(wèn)題三，將步行看作獨(dú)立于公汽、地鐵的第三種交通方式，仍利用問(wèn)題二中的網(wǎng)絡(luò)圖，不再增加有向邊，并假設(shè)步行只能沿已有的有向邊行進(jìn)。主要從步行時(shí)間、換乘次數(shù)、出行花費(fèi)和出行總時(shí)間四個(gè)方面來(lái)理解最佳線(xiàn)路，分別考慮各單目標(biāo)，增加不同的上限約束，建立了相應(yīng)的網(wǎng)絡(luò)流模型。模型評(píng)價(jià)中對(duì)本文中的網(wǎng)絡(luò)流模型進(jìn)行了詳細(xì)的評(píng)價(jià)說(shuō)明，最后著眼于開(kāi)發(fā)一個(gè)解決公交線(xiàn)路選擇問(wèn)題的自主查詢(xún)計(jì)算機(jī)系統(tǒng)，提出了一點(diǎn)建議。關(guān)鍵詞：最佳線(xiàn)路；最小費(fèi)用流；Dijkstra算法；優(yōu)先因子；上限約束31一、問(wèn)題重述近年來(lái)，城市的公交系統(tǒng)有了很大發(fā)展，使得公眾的出行更加通暢、便利，但公眾也同時(shí)面

4、臨著多條線(xiàn)路的選擇問(wèn)題。針對(duì)此市場(chǎng)需求，某公司準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決公交線(xiàn)路選擇問(wèn)題的自主查詢(xún)計(jì)算機(jī)系統(tǒng)。設(shè)計(jì)這樣一個(gè)系統(tǒng)的核心是線(xiàn)路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿(mǎn)足查詢(xún)者的各種不同需求。現(xiàn)已給出某市公交線(xiàn)路及相關(guān)信息，請(qǐng)解決如下問(wèn)題：1、僅考慮公汽線(xiàn)路，給出任意兩公汽站點(diǎn)之間線(xiàn)路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對(duì)起始站→終到站之間的最佳路線(xiàn)（要有清晰的評(píng)價(jià)說(shuō)明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0

5、087→S36762、同時(shí)考慮公汽與地鐵線(xiàn)路，解決以上問(wèn)題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)給出任意兩站點(diǎn)之間線(xiàn)路選擇問(wèn)題的數(shù)學(xué)模型。二、基本假設(shè)（1）僅考慮公汽線(xiàn)路時(shí)，換乘只發(fā)生在兩條公汽線(xiàn)路的公共站點(diǎn)處。（2）對(duì)題目中基本參數(shù)設(shè)定進(jìn)行補(bǔ)充：同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間通過(guò)地鐵站換乘的平均耗時(shí)為11分鐘（其中步行時(shí)間8分鐘）。（3）根據(jù)實(shí)際情況，環(huán)行線(xiàn)的公交車(chē)到達(dá)始發(fā)站時(shí)不需要清人，所以始發(fā)站與其它站點(diǎn)可認(rèn)為是沒(méi)有區(qū)別的。上下行線(xiàn)路的公交車(chē)到達(dá)上行線(xiàn)的終點(diǎn)站（即下行線(xiàn)的始發(fā)站）時(shí)不需要清人，因此上行線(xiàn)的終點(diǎn)站（即下行線(xiàn)的始發(fā)站）與其他站點(diǎn)可認(rèn)為是沒(méi)有區(qū)別的。（4）環(huán)

6、行線(xiàn)的公交車(chē)是單方向行駛的。（5）所有站點(diǎn)之間都是相通的，即公交線(xiàn)路的實(shí)際地理圖是聯(lián)通圖。（6）設(shè)0-1變量fij為有向邊vivj中通過(guò)的流量，記f={fij}。當(dāng)fij=1時(shí)表明該有向邊vivj中有流量通過(guò)，即最佳路線(xiàn)包括邊vivj，當(dāng)fij=0時(shí)表明該有向邊vivj中沒(méi)有流量通過(guò)，即最佳路線(xiàn)不包括邊vivj。（7）所有有向邊的容量均為1.（8）對(duì)于問(wèn)題一、問(wèn)題二，假設(shè)線(xiàn)路長(zhǎng)度與經(jīng)過(guò)站點(diǎn)數(shù)成正比。（9）本文中提到的費(fèi)用率bij與費(fèi)用沒(méi)有必然聯(lián)系，而是指有向邊的權(quán)值。三、符號(hào)說(shuō)明31vi網(wǎng)絡(luò)圖中第i個(gè)頂點(diǎn)vivj網(wǎng)絡(luò)圖中連接站點(diǎn)i和j的有向邊cij各有向邊的容量，為常數(shù)1fij0-

7、1變量表示流量，fij=1表示流過(guò)有向邊vivj,fij=0表示沒(méi)有流過(guò)有向邊vivjuij0-1變量表示出行方式，uij=1表示從站點(diǎn)i到j(luò)采用步行wij0-1變量表示出行方式，wij=1表示從站點(diǎn)i到j(luò)采用乘車(chē)bij各有向邊的費(fèi)用率，分別可以表征費(fèi)用、換乘次數(shù)、時(shí)間等mij表征實(shí)際乘車(chē)費(fèi)用的各有向邊費(fèi)用率，可取1，2，3（單位：元）M常數(shù)，實(shí)際乘車(chē)費(fèi)用的上限約束α乘車(chē)費(fèi)用優(yōu)先因子，表示查詢(xún)者對(duì)乘車(chē)費(fèi)用的偏愛(ài)程度kij表征換乘次數(shù)的各有向邊費(fèi)用率，值為1或0K常數(shù)，