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

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

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

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

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

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

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

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

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