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

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

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

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

4、市場需求，某公司準備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統。設計這樣一個系統的核心是線路選擇的模型與算法，應該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求?，F已給出某市公交線路與相關信息，請解決如下問題：1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數學模型與算法。并根據附錄數據，利用你們的模型與算法，求出以下6對起始站終到站之間的最佳路線（要有清晰的評價說明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同時考慮公汽與地鐵線路，

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

6、的，即公交線路的實際地理圖是聯通圖。（6）設0-1變量fij為有向邊vivj過的流量，記f =fij。當fij=1時表明該有向邊vivj中有流量通過，即最佳路線包括邊vivj，當fij=0時表明該有向邊vivj中沒有流量通過，即最佳路線不包括邊vivj 。（7）所有有向邊的容量均為1.（8）對于問題一、問題二，假設線路長度與經過站點數成正比。（9）本文中提到的費用率bij與費用沒有必然聯系，而是指有向邊的權值。 三、 符號說明vi網絡圖中第i個頂點vivj網絡圖中連接站點i和j的有向邊cij各有向邊的容量，為常數1fij0-1變量表示流量，fij=1表示流過有向邊vivj , fij=0表示沒

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

8、鐘）P常數，步行出行時間的上限約束tij表征總出行時間的各有向邊費用率tij = wij qij +uij pij（單位：分鐘）T常數，總的出行時間的上限約束出行時間優(yōu)先因子，表示查詢者對出行時間的偏愛程度四、 問題分析本題是一個給出城市中任意兩站點，尋求其最佳線路方案的問題。考慮到查詢者的各種不同需求，本文認為所謂最佳線路，應該從乘車費用、換乘次數、出行時間三方面來理解。查詢者尋找連接兩點的最佳線路，可看作車輛將查詢者從起始站點運輸到目的站點，對于此類運輸問題，可以建立網絡流模型來求解。而題目中的三個問題，其實是逐步考慮了公汽、地鐵、步行三種交通方式后的線路選擇問題，而評判某一線路方案好壞的

9、原則是不變的，仍舊是花費、換乘次數與時間，因此三個問題都可以用網絡流模型來求解?？紤]到不同查詢者對三個目標的偏愛程度不同，而實際生活中人們更習慣于優(yōu)先考慮某一目標，然后再考慮次要的目標，比如：當兩個線路選擇方案所用時間一樣時，再考慮哪一個方案費用更低。也就是說不同情況下三個目標的優(yōu)先級不同，因此可以引入優(yōu)先因子來區(qū)分各目標的優(yōu)先級，得出滿足查詢者不同需求的最佳線路。五、 模型的建立與求解5.1問題一：僅考慮公汽線路5.1.1模型準備：構造容量費用網絡N=(V,E,C,B)。1b12b13b14b23b24b34234圖1設兩個虛擬點作為網絡流的源點S（source）、匯點T（terminal）

10、，題目中給出的3957個公交站點與S、T共同構成頂點集V 。由于題目要求給出任意兩站點之間線路選擇問題的一般數學模型與算法，不妨考慮任意兩站點M到N的線路選擇問題。在S與M、N與T之間分別添加有向邊，這兩條邊的容量為1、流量也都是1.對于網絡中各點間的有向邊，并不是實際中的公汽線路，而是表明任意兩站點i與j之間能否直達的有向弧，如圖1所示：圖1表示某一條公汽線路，圖中標出了部分站點1、2、3、4，其中站點1為起始站。乘坐該線路的公交車，從站點1直達到站點2形成有向弧為v1v2 ，從站點2直達到站點4形成有向弧為v2v4 ，依次類推，這樣給每條線路都畫上有向弧，即為有向邊，所有的有向邊vivj構

11、成邊集E.圖中各有向邊上的數據b12 、b13等稱為各有向邊的費用率，所有費用率bij構成集合B=bij|vivjE。所有邊的容量都為1，即cij=1.所有的 cij構成集合C。設0-1變量fij為有向邊vivj過的流量，記f =fij,當fij=1時表明該有向邊vivj中有流量通過，即最佳路線包括邊vivj，當fij=0時表明該有向邊vivj中沒有流量通過，即最佳路線不包括邊vivj 。題目中公汽線路可分為兩種：上下行、環(huán)路。下面本文將詳細說明網絡圖中畫有向邊的規(guī)則：126圖21）對于環(huán)路上的任意兩點，都有兩種連有向邊的方式，但要考慮環(huán)線的車輛行駛方向。如圖2，站點1為環(huán)路的始發(fā)站，若該環(huán)路

12、的車輛行駛方向為順時針方向，則有向邊v2v6必須按順時針方向計算，不能按照逆時針方向計算。2）對于上下行路線站點均一樣的情況，由于上行線的終點站（即下行線的始發(fā)站）與其他站點可認為是沒有區(qū)別的，可將下行線逆序接到上行線之后，看作一條線路，這樣某些站點之間也有兩種連邊方式，但只有經過站點較少的邊才是許可的。(見圖3)1324321上行線下行線b32b23圖3：1為始發(fā)站，4為上行終點站（下行始發(fā)站），中間兩條弧均是不允許的。3）對于上下行線站點不同的情況，仍將下行線逆序接到上行線之后，看作一條線路（見圖4）。乘客如果想從站點3到站點5，可以乘坐公交從站點3直達站點5，畫出有向邊v3v5 ，其費用

13、率為b35；但如果乘客想從站點5到站點3（僅考慮圖中這一條線路），則必須走52123，此時認為乘客走了兩條線路，即在站點1處“換乘”，因而不能畫有向邊v5v31324521上行線下行線b35圖4：1為始發(fā)站，4為上行終點站（下行始發(fā)站）5.1.2目標函數的構成結合實際情況，本文選擇最佳線路時考慮了三個目標：出行花費、換乘次數、出行時間。針對不同的目標，各有向邊的費用率bij均不一樣，表征出行花費、換乘次數、出行時間的費用率分別可以記作mij、kij、tij 。對于公汽線路，三者的計算方法如下：1）乘車費用mij從站點i直達到站點j的實際乘車費用為mij。所有公汽線路可分為兩種：環(huán)行、上下行。根

14、據假設，環(huán)行線上的各站點都是沒有區(qū)別的。公汽線路中共有22條環(huán)路，其中采取分段計價的線路有：L017、L027、L152、L290、L296、L296、L485.這些線路上mij的值可取1，2，3. 分別對應乘客乘坐了020站、2140站、40站以上。其余的環(huán)路都是單一票制1元，故mij=1. 對于上下行線路，上行線的終點站（下行線的始發(fā)站）與其他中間站點可認為是沒有區(qū)別的。若采取分段計價，乘客乘車經過上行線的終點站后只要繼續(xù)數站點數即可，乘客乘坐了 020站：mij=1；2140站：mij=2；40站以上：mij=3 .若采取單一票制，那么不論乘客是否乘車經過的上行線的終點站，mij都等于1

15、.2）換乘次數kij模型中令所有有向邊的kij =1，則對某一線路方案的kij求和減1就是該方案實際換乘的次數。3） 出行時間qij出行時間qij代表公交車從站點i直達到站點j的平均行駛時間。但是由于我們的最佳路線是由網絡圖中不少于一條邊銜接而成，每次銜接時即是公汽換乘，而公汽換乘公汽平均耗時5分鐘，因此可以把這5分鐘算到qij中，可得qij=3×經過站數+5（單位：分鐘）。利用MATLAB編程可得出所有qij的值，程序代碼見附錄中的程序，由于數據量大在此不便給出qij.4） 優(yōu)先因子這三個目標性質不同，量綱不同，查詢者對其偏愛程度也不同?？紤]到實際生活中人們更習慣于優(yōu)先考慮某一目標

16、，然后再考慮次要的目標，比如：當兩個線路選擇方案所用時間一樣時，再考慮哪一個方案費用更低。因此不能將三者簡單的動態(tài)加權為一綜合目標，而應分情況討論，不同情況下三個目標的優(yōu)先順序不同。為達到以上目的，本文引入優(yōu)先因子表示不同查詢者對乘車費用、換乘次數、出行時間三個目標的不同喜好程度，通過巧妙設置的值來區(qū)分各單目標的優(yōu)先級，從而建立類似目標規(guī)劃的網絡流模型，如：令=1，=0.01，=0.00001，表示查詢者優(yōu)先選擇乘車費用最少的線路，當乘車費用一樣時，再優(yōu)先選擇換乘次數較少的，當換乘次數也一樣時，再考慮出行時間。 5.1.3約束條件分析本文建立網絡流模型解決此問題。首先，網絡中中間點的出度應等于

17、入度其次，源點S的出度與匯點T的入度均為1第三，各邊的流量fij不能超過邊的容量cij，并且fij是0-1變量 ，第四，M、K、T都是常數，分別作為對乘車費用、換乘次數、出行時間的上限約束，具體數值視情況而定。因為當某一目標達到最優(yōu)時，如果其它目標的值很差，也是沒有實際意義的。5.1.4最小費用流模型的建立 本小問中取K = 3，M = 10，Q = 150作為約束。 5.1.5模型求解5.1.5.1求解算法改進的Dijkstra算法由于源點S的出度和匯點T的入度均為1，且所有有向邊的容量cij=1，此最小費用流問題便轉化為從vs到vt的最短路徑問題，本文采用改進的Dijkstra算法求解最短

18、路問題，具體程序見附錄中的程序.改進的Dijkstra算法：求賦權有向圖G中從頂點u0到ut的最短路。記 S：具有永久標號的頂點集。D：一次轉車可達的頂點集對每個頂點，定義三個標記（l(v)，z(v)，zhuan(v)），其中：l(v)：表示從頂點u0到v的一條路的權；z(v)：v的父親點，用以確定最短路的路線；zhuan(v)：v的轉車次數，用以確定最短路中到達v點轉了幾次車。算法的過程就是在每一步改進這三個標記，使最終l(v)為從頂點u0到ut的最短路的權。輸入為帶權鄰接矩陣WStep1 賦初值：令,，zhuan(v)=0.且zhuan(v)<=2,令，z(v)=u0,uu0Step

19、2 更新l(v)、z(v) 、zhuan(v)：且zhuan(v)<=2，若l(v)> l(u)+W(u,v),則令l(v)= l(u)+W(u,v)，z(v)=u，zhuan(v)= zhuan(u)+1；Step3 設v*是使l(v)取最小值D中的頂點，則令S=S v*, uv*.Step4 若且ut，轉（2）；否則，停止。 用上述算法求出的l(v)就是u0到ut的最短路的權，從ut的父親標記z(ut)追溯到u0，就得到u0到ut的最短路的路線。根據以上算法，利用MATLAB編程，就能求出任意兩公汽站點的最佳線路。5.1.5.2求解結果三個目標一共有六種排序，按不同的排序結果可

20、以分別給出相應的優(yōu)先因子取值，然后計算最佳線路。針對題目中給出的6對起始站終到站，本文將分別給出其在這六種情況下的最佳線路。1）優(yōu)先考慮乘車費用，然后再考慮換乘次數，最后考慮出行時間，即令模型中=1，=0.001，=0.00001，結果見表1.（備注：表中給出的最佳線路中的站點即是公汽換乘站點，表格后面還接著給出了最佳線路的詳細信息，橫線上表示公交線路，橫線下的數字表示兩者之間的站點數。以后的表格與之類似，不再注明。）表1：優(yōu)先考慮乘車費用，然后再考慮換乘次數起始站終到站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S1784S182831101S1557S0481S155

21、7S1919S3186S048132106S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621652）優(yōu)先考慮乘車費用，然后再考慮出行時間，最后考慮換乘次數，即令模型中=1，=0.00001，=0.001，結果見表2.表2：優(yōu)先考慮乘車費用，然后再考慮出行時間起始站終到站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S1784S18283273S1557S0481S1557S1919S3

22、186S048132106S0971S0485S0971S1609S048532106S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621653）優(yōu)先考慮換乘次數，然后再考慮乘車費用，最后考慮出行時間，即令模型中=0.001，=1，=0.00001，結果見表3.表3：優(yōu)先考慮換乘次數，然后再考慮乘車費用起始站終到站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S1784S182831101S1557S0481S1557S1919S3186S048

23、132106S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621654）優(yōu)先考慮換乘次數，然后再考慮出行時間，最后考慮乘車費用，即令模型中的 =0.00001，=1，=0.001，結果見表4.表4：優(yōu)先考慮換乘次數，然后再考慮出行時間起始站終到站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S1784S182831101S1557S0481S1557S1919S3186S04813210

24、6S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621655）優(yōu)先考慮出行時間，然后再考慮乘車費用，最后考慮換乘次數，即令模型中=0.01，=0.0001，=1，結果見表5.表5：優(yōu)先考慮出行時間，然后再考慮乘車費用起始站終到站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S2903S1671S18283273S1557S0481S1557S1919S3186S048132106S097

25、1S0485S0971S1609S2654S048532106S0008S0073S0008S0630S2650S00733270S0148S0485S0148S0036S3351S048532106S0087S3676S0087S0088S0427S367632466）優(yōu)先考慮出行時間，然后再考慮換乘次數，最后再考慮乘車費用，即令模型中 =0.0001，=0.01，=1，結果見表6.表6：優(yōu)先考慮出行時間，然后再考慮換乘次數起始站終到站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S2903S1671S18283273S1557S0481S1557S1919S3186S0

26、48132106S0971S0485S0971S1609S2654S048532106S0008S0073S0008S0630S2650S00733270S0148S0485S0148S0036S3351S048532106S0087S3676S0087S0088S0427S367632465.2問題二：同時考慮公汽與地鐵線路5.2.1模型準備：構造容量費用網絡圖N=(V,E,C,B)問題二仍舊可以利用網絡流模型來求解，其容量費用網絡圖N=(V,E,C,B)比問題一中的網絡圖增加了以下三方面的容：1） 地鐵線路上的站點所構成的新頂點 vi | i=3958, 3996.2） 同一地鐵線路上各站

27、點之間的有向邊。3） 考慮到同一地鐵站對應的任意兩個公汽站之間可以通過地鐵站換乘，因而增加了不同公汽站點之間換乘的有向邊。（如圖5）公交線路1公交線路2地鐵站地鐵站1234b14b41圖5：公汽站點1與地鐵站4之間存在有向邊v1v4、v4v1，費用率分別為b14、b415.2.2目標函數的構成1）乘車費用mij從站點i直達到站點j的實際乘車費用為mij，其中可能包括兩部分：公汽與地鐵。公汽線路費用計算方法與問題一一樣。對于地鐵：T1、T2兩條線路的票價都是3元，當乘客從一條地鐵線路換乘到另一條時要花費3元；如果乘客乘地鐵后換乘公汽，然后又換乘地鐵，即使他乘坐的還是同一條地鐵線路，也要重新買票；

28、同一地鐵站對應的任意兩個公汽站之間通過地鐵站換乘時，無需支付地鐵費（圖5）。2）換乘次數kij模型中令所有有向邊的kij=1，則對某一線路方案的kij求和減1就是該方案實際換乘的次數，但對于像圖5所示的情況，k14 = k43 =0，即從143記作換乘0次。kij具體計算函數如下：5） 出行時間qij出行時間qij代表乘客從站點i直達到站點j的平均出行時間，包括公汽或地鐵行駛時間、換乘時間。對于圖5中v1v4 這類邊，由于地鐵換乘地鐵時費時4分鐘，公汽換乘地鐵時費時6分鐘，故本文中設乘客從v1到v4費時2分鐘，即q14=2，q43的設置類似。對于不同的換乘情況，qij的值不同，其計算方法見下式

29、，其中n代表公交車或地鐵已行駛的站點數，即各自的有向邊vivj覆蓋的站數-1。6） 優(yōu)先因子優(yōu)先因子的定義與計算方法與問題一中的一樣。5.2.3約束條件分析: 約束條件與問題一一樣。5.2.4建立最小費用流模型本小問中取K = 3，M = 10，Q = 150作為約束。5.2.5模型算法與求解考慮了地鐵線路后，問題仍能轉化為最短路徑問題，仍舊分6種情況，根據改進的Dijkstra算法用MATLAB求解。本小問中取K = 3，M = 10，Q = 150作為約束。1）優(yōu)先考慮乘車費用，然后再考慮換乘次數，最后考慮出行時間，即令模型中=1，=0.001，=0.00001，結果見表7.表7：優(yōu)先考慮

30、乘車費用，然后再考慮換乘次數起始站終到站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S1784S182831101S1557S0481S1557S1919S3186S048132106S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621652）優(yōu)先考慮乘車費用，然后再考慮出行時間，最后考慮換乘次數，即令模型中=1，=0.00001，=0.001，結果見表8.表8 ：優(yōu)先考慮乘車費用，然

31、后再考慮出行時間起始站終到站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S2903S1671S18283273S1557S0481S1557S1919S3186S048132106S0971S0485S0971S1609S2654S048532106S0008S0073S0008S0400S00732183S0148S0485S0148S0036S3351S048532106S0087S3676S0087S3496S367621653）優(yōu)先考慮換乘次數，然后再考慮乘車費用，最后考慮出行時間，即令模型中=0.001，=1，=0.00001，結果見表9.表9 ：優(yōu)先考慮換乘次

32、數，然后再考慮乘車費用起始站終到站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S1784S182831101S1557S0481S1557S1919S3186S048132106S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S1487S0466S04855287.5S0087S3676S0087S367630254）優(yōu)先考慮換乘次數，然后再考慮出行時間，最后考慮乘車費用，即令模型中=0.00001，=1，=0.001，結果見表10.表10 ：優(yōu)先考慮換乘次數，然后再考慮出

33、行時間起始站終到站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S1784S182831101S1557S0481S1557S1919S3186S048132106S0971S0485S0971S2184S048531128S0008S0073S0008S0400S00732183S0148S0485S0148S1487S0466S04855287.5S0087S3676S0087S367630255）優(yōu)先考慮出行時間，然后再考慮乘車費用，最后考慮換乘次數，即令模型中=0.001，=0.00001，=1，結果見表11.表11 ：優(yōu)先考慮出行時間，然后再考慮乘車費用起始站終到

34、站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S2903S1671S18283273S1557S0481S1557S1919S3186S048132106S0971S0485S0971S0567S0466S04855296S0008S0073S0008S2534S0609S00735265.5S0148S0485S0148S1487S0466S04855287.5S0087S3676S0087S367630256）優(yōu)先考慮出行時間，然后再考慮換乘次數，最后再考慮乘車費用，即令模型中=0.00001，=0.001，=1，結果見表12.表12：優(yōu)先考慮出行時間，然后再考慮換乘

35、次數起始站終到站最佳線路費用（元）換乘次數時間（分）S3359S1828S3359S2903S1671S18283273S1557S0481S1557S1919S3186S048132106S0971S0485S0971S0567S0466S04855296S0008S0073S0008S2534S0609S00735265.5S0148S0485S0148S1487S0466S04855287.5S0087S3676S0087S367630255.3問題三：所有站點之間的步行時間已知5.3.1問題分析： 將步行看作獨立于公汽、地鐵的第三種交通方式，仍利用問題二中的網絡圖，不再增加有向邊，假設

36、步行只能沿已有的有向邊行進。對于目標函數，如果分別考慮乘車費用、換乘這些單目標時，繼續(xù)沿用問題二中的約束條件，而不附加任何限制，將得不到最佳線路的解。（比如：只考慮乘車費用時，由于步行沒有任何費用，這樣將得到全程步行這樣一個沒有意義的解。）為了解決這個問題，本文首先定義了0-1變量uij 、wij來區(qū)分從站點i到j所采用的出行方式，采用步行時，uij=1，wij=0；采用乘車時，uij=0，wij=1 。此時出行總時間tij = wij qij +uij pij 。然后在約束條件中加上了步行時間的上限約束：對于最佳線路，分別考慮步行時間、出行總時間、換乘次數、乘車費用四個單目標下的最優(yōu)解。網絡

37、流模型中的其它約束條件與問題二的一樣。 5.3.2模型建立5.3.2.1模型一：步行時間最少目標函數為：沿用問題二中的約束條件，就能求出步行時間最短的線路。由于有乘車費用、換乘次數、和乘車時間的上限約束，故避免了全程乘車步行時間為0的情況，從而使得考慮步行時間最短的單目標有意義。5.3.2.2模型二：換乘次數最少目標函數為：但在考慮換乘次數最少這個目標時，應加入步行時間、總出行時間的上限約束，來避免全程步行這樣沒有意義的解。此時的約束條件為5.3.2.3模型三：乘車費用最低目標函數：但在考慮乘車費用最低這個目標時，應加入步行時間、總出行時間的上限約束，來避免全程步行這樣沒有意義的解。因此只需將

38、（5.3.2.2）中對乘車費用的約束條件改為對換乘次數的約束即可，即5.3.2.4模型四：總出行時間最少目標函數為求總時間最少：此時考慮總出行時間最少，就不用分別對步行時間、乘車時間增加上限約束。約束條件如下：5.3.3模型四的解的預測與分析1）該問題中的步行時間參數pij沒有給出具體的數值，因此沒法求出具體的解，本文只對解的情況進行了簡單的預測分析：b34圖6b451b132345參見圖6，在約束圍，假設求點1到點4的最優(yōu)路線，依據模型求出的解可能是1到3步行，3到4乘地鐵，4到5乘公汽。總之，當兩點之間的乘車時間大于步行時間時，就選擇步行。2）問題三模型四在求總出行時間最短時，將步行時間和

39、乘車時間分開表示，因此在求出最佳線路后，可分別得出步行時間為，乘車時間為。六、 模型的改進與評價6.1模型評價優(yōu)點：1） 引入優(yōu)先因子，通過巧妙設置優(yōu)先因子的值來區(qū)分三個目標的優(yōu)先級，建立了類似目標規(guī)劃的網絡流模型，求解得到滿足乘客不同需求的最優(yōu)線路。2） 網絡流模型適用面廣（可用于解決資源配置、運輸、路徑選擇等一系列問題），靈活多變，通過對費用率的不同設置，既可以求出單目標最優(yōu)解，又可以對多目標進行動態(tài)加權后求解，結果精確。另外網絡流理論研究已相當成熟，非常復雜的問題也能利用計算機在有限的時間解決。缺點：1) 本文沒有對網絡流模型進行有效性證明，如果給予足夠時間，我們將改正這一缺點。2) 模

40、型求解時，我們把流量為1的費用流問題轉化成最短路徑問題，根據改進的Dijkstra算法用MATLAB編程求解，由于費用率矩陣規(guī)模很大，故求解比較慢。3) 針對網絡流模型沒有提出效率更高的求解算法。6.2其他建議題目中提到某公司要研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統，而一個較好的查詢系統應該是智能化的，與查詢者的互動性強?？紤]到查詢者有各種不同需求，僅僅是出行花費、換乘次數、出行時間這三個方面在不同查詢者心中就占有不同的權重，因此在建立綜合模型時可以將權值改為由查詢者自行輸入，然后系統再給出最佳路線方案。參 考 文 獻1 省大學生數學建模競賽專家組，數學建模，：華中科技大學，20

41、06年2靜、但琦，數學建模與數學實驗，：高等教育，2003年附 錄程序1：計算問題一模型一價格費用率矩陣mijclc;clear;x=load('C:Documents and Settingswly桌面新建文件夾1bB2007dataw1checi.txt');w=inf(3957,3957);for k=1:929 clear xx; if x(k,2)=1 %單一價 if x(k,3)=0 %往返 xx=x(k,4:last(x(k,:) fliplr(x(k,4:last(x(k,:)-1); l=length(xx(1,:); q=1; for i=1:(l-1) f

42、or j=(i+1):l if w(xx(1,i),xx(1,j)>q w(xx(1,i),xx(1,j)=q; end end end elseif x(k,3)=1 %上行 xx=x(k,4:last(x(k,:) x(k+1,4+1:last(x(k+1,:); l=length(xx(1,:); q=1; for i=1:(l-1) for j=(i+1):l if w(xx(1,i),xx(1,j)>q w(xx(1,i),xx(1,j)=q; end end end elseif x(k,3)=2 %下行 elseif x(k,3)=3 %環(huán)線 xx=x(k,4:las

43、t(x(k,:)-1) x(k,4:last(x(k,:)-1); l=length(xx(1,:)/2; for i=1:l j=1; while i+j<=length(xx(1,:) if w(xx(1,i),xx(1,i+j)>1 w(xx(1,i),xx(1,i+j)=1; end j=j+1; end end end elseif x(k,2)=0 %分段 if x(k,3)=0 %往返 xx=x(k,4:last(x(k,:) fliplr(x(k,4:last(x(k,:)-1); l=length(xx(1,:); for i=1:(l-1) j=1; while

44、 i+j<=l if j<=20 && w(xx(1,i),xx(1,i+j)>1 w(xx(1,i),xx(1,i+j)=1; elseif j<=40 && w(xx(1,i),xx(1,i+j)>2 w(xx(1,i),xx(1,i+j)=2; elseif w(xx(1,i),xx(1,i+j)>3 w(xx(1,i),xx(1,i+j)=3; end j=j+1; end end elseif x(k,3)=1 %上行 xx=x(k,4:last(x(k,:) x(k+1,4+1:last(x(k+1,:); l=l

45、ength(xx(1,:); for i=1:(l-1) j=1; while i+j<=l if j<=20 && w(xx(1,i),xx(1,i+j)>1 w(xx(1,i),xx(1,i+j)=1; elseif j<=40 && w(xx(1,i),xx(1,i+j)>2 w(xx(1,i),xx(1,i+j)=2; elseif w(xx(1,i),xx(1,i+j)>3 w(xx(1,i),xx(1,i+j)=3; end j=j+1; end end elseif x(k,3)=2 %下行 elseif x(k,3)=3 %環(huán)線 xx=x(k,4:last(x(k,: