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

1、 . 公交線路選擇的網(wǎng)絡(luò)優(yōu)化模型摘要本文針對城市公交線路選擇問題建立了相應(yīng)的數(shù)學(xué)模型。將查詢者尋找連接兩點(diǎn)的最佳線路的過程看作車輛將查詢者從起始站點(diǎn)運(yùn)輸?shù)侥康恼军c(diǎn)的過程，對于此類運(yùn)輸問題，可以建立網(wǎng)絡(luò)流模型來求解。對于問題一，將公汽站點(diǎn)看作頂點(diǎn)，3957個(gè)公汽站點(diǎn)再加上源點(diǎn)S和收點(diǎn)T就構(gòu)成了頂點(diǎn)集V。至于有向邊vivj，并不是公汽站點(diǎn)間的實(shí)際線路，而是表明任意兩站點(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中有流量通過，即最佳路線包括邊vivj，就可以建立最小費(fèi)用流模型來求解。由于源點(diǎn)S

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、路問題，具體程序見附錄中的程序.改進(jìn)的Dijkstra算法：求賦權(quán)有向圖G中從頂點(diǎn)u0到ut的最短路。記 S：具有永久標(biāo)號的頂點(diǎn)集。D：一次轉(zhuǎn)車可達(dá)的頂點(diǎn)集對每個(gè)頂點(diǎn)，定義三個(gè)標(biāo)記（l(v)，z(v)，zhuan(v)），其中：l(v)：表示從頂點(diǎn)u0到v的一條路的權(quán)；z(v)：v的父親點(diǎn)，用以確定最短路的路線；zhuan(v)：v的轉(zhuǎn)車次數(shù)，用以確定最短路中到達(dá)v點(diǎn)轉(zhuǎn)了幾次車。算法的過程就是在每一步改進(jìn)這三個(gè)標(biāo)記，使最終l(v)為從頂點(diǎn)u0到ut的最短路的權(quán)。輸入為帶權(quán)鄰接矩陣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 設(shè)v*是使l(v)取最小值D中的頂點(diǎn)，則令S=S v*, uv*.Step4 若且ut，轉(zhuǎn)（2）；否則，停止。 用上述算法求出的l(v)就是u0到ut的最短路的權(quán)，從ut的父親標(biāo)記z(ut)追溯到u0，就得到u0到ut的最短路的路線。根據(jù)以上算法，利用MATLAB編程，就能求出任意兩公汽站點(diǎn)的最佳線路。5.1.5.2求解結(jié)果三個(gè)目標(biāo)一共有六種排序，按不同的排序結(jié)果可

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

41、06年2靜、但琦，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)，：高等教育，2003年附 錄程序1：計(jì)算問題一模型一價(jià)格費(fèi)用率矩陣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 %單一價(jià) 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,: