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

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

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

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

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

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

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

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

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