2007年全國(guó)生數(shù)學(xué)建模競(jìng)賽優(yōu)秀及題目一等獎(jiǎng)cumcm

1、摘線路查詢系統(tǒng)的線路選擇的模型與算法 可關(guān)鍵字：鄰接關(guān)系矩陣 滿意摘線路查詢系統(tǒng)的線路選擇的模型與算法 可關(guān)鍵字：鄰接關(guān)系矩陣 滿意度函數(shù) 節(jié)點(diǎn)帶權(quán)網(wǎng)目錄1問(wèn)題重2問(wèn)題分問(wèn)題一的分問(wèn)題二的分問(wèn)題三的分目錄1問(wèn)題重2問(wèn)題分問(wèn)題一的分問(wèn)題二的分問(wèn)題三的分3模型假問(wèn)題一的假問(wèn)題二的假問(wèn)題三的假和符號(hào)說(shuō).符號(hào)說(shuō)45問(wèn)題一的求模型一的建模型求基于鄰接矩陣的換乘搜索算法-準(zhǔn)則 1，2，3 的求基于廣度優(yōu)先換乘搜索算法-準(zhǔn)則 4 的求結(jié)果分問(wèn)題二的求對(duì)地鐵站附近的公汽站的處模型二：基于出行時(shí)間最短的線路搜索模模型三：節(jié)點(diǎn)帶權(quán)的網(wǎng)絡(luò)模6模型求結(jié)果分7問(wèn)題三的求8模型評(píng)優(yōu)缺9算法的穩(wěn)定性分參考文-11 問(wèn)題重2

2、9 8 場(chǎng)800 條以上，某公司準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決1 (5)、(6)、1 問(wèn)題重29 8 場(chǎng)800 條以上，某公司準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決1 (5)、(6)、22 問(wèn)題分2.1 問(wèn)題一的分?？紤]換一次車(chē)的方案；如果沒(méi)有換一次車(chē)的方案則又要考慮換兩次車(chē)到達(dá) B 的乘車(chē)方-22.2 問(wèn)題二的分2.3 問(wèn)題三的分3 模型假3.1 問(wèn)題一的假假設(shè)城市系統(tǒng)的線路信息都是已知的，即如果將每個(gè)站抽象為一2.2 問(wèn)題二的分2.3 問(wèn)題三的分3 模型假3.1 問(wèn)題一的假假設(shè)城市系統(tǒng)的線路信息都是已知的，即如果將每個(gè)站抽象為一2225（23.2 問(wèn)題二的假547鐘、611問(wèn)題三的假-33) 僅考慮地鐵和公汽的換乘時(shí)

3、間，其他方式如：步行換乘、步行換乘地鐵等所花4和符號(hào)說(shuō)4.2符號(hào)說(shuō)ij間有直達(dá)線路時(shí)d0為從ij3) 僅考慮地鐵和公汽的換乘時(shí)間，其他方式如：步行換乘、步行換乘地鐵等所花4和符號(hào)說(shuō)4.2符號(hào)說(shuō)ij間有直達(dá)線路時(shí)d0為從ij行駛時(shí)間，否則d0 (d(K)經(jīng)k；ns(0) 1表示站點(diǎn)ijs(0) 0站點(diǎn)ij (s(K)經(jīng)k；n可直達(dá)站點(diǎn)的線路序列矩陣即站點(diǎn)i和j間有直達(dá)線路時(shí)為過(guò)i、j的線路序號(hào)，否則 0-4 (l(K)經(jīng)k；nn5 問(wèn)題一的求5.1 模型一的建的研究來(lái)確定模型的優(yōu)化 (l(K)經(jīng)k；nn5 問(wèn)題一的求5.1 模型一的建的研究來(lái)確定模型的優(yōu)化目標(biāo)和約束條件。根據(jù)楊新苗1 等K 、出

4、行費(fèi)用C 、出行距離T 。先考慮目標(biāo)函數(shù)1)minK；為了避免換乘的麻煩，部分乘客（如新的外來(lái)）minC；對(duì)于時(shí)間比較充?；蚴杖氩桓叩某丝停瑒t會(huì)選擇出行費(fèi)minT；有些乘客趕時(shí)間，不會(huì)考慮換乘次數(shù)和費(fèi)用的多少，將再考慮約束條件1)鄰接關(guān)系矩陣S (sij )nn 2)根據(jù)假設(shè)用兩站之間的平均行駛時(shí)間來(lái)衡量站點(diǎn)距離，則 該城市共有520條公汽線路（包括上下行和環(huán)形）和2條地鐵線路（環(huán)形L的所有元素4)站點(diǎn)i經(jīng)kj-5n s(k1) 0(s(k(k s(k1) 的意義是站點(diǎn)i 經(jīng)k 次換乘n s(k1) 0(s(k(k s(k1) 的意義是站點(diǎn)i 經(jīng)k 次換乘到達(dá) j 站點(diǎn)的換乘方式有s(k1)

5、種5.2 模型求乘客類(lèi)選擇最優(yōu)路線的優(yōu)先對(duì)應(yīng)準(zhǔn)K 出行費(fèi)用C 出行距離T出行費(fèi)用CK 出行距離T出行距離T K 出行費(fèi)用CK C T準(zhǔn)則KCTK最小的線路，如果不止一條，則選擇C最少的線路，仍然不止一條則選擇T 最短的線路。其他與此類(lèi)5.2.1 基于鄰接矩陣的換乘搜索算準(zhǔn)則1，2，3的求此算法以矩陣為基本數(shù)據(jù)結(jié)構(gòu)。在鄰接關(guān)系矩陣S D 是根據(jù)S（K）以準(zhǔn)則1為例，算法具體步驟如下Step1根據(jù)題目所給數(shù)據(jù)并分析網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，初始化S LDK 0K的上界supK K為整數(shù) KABStep2 :查網(wǎng)絡(luò)的S、L和D矩陣，計(jì)算出可直達(dá)關(guān)系矩陣S（0）、可直達(dá)的站點(diǎn)離矩陣和可直達(dá)站點(diǎn)的線路序列矩陣。若

6、入可行線路集合Z K K 1；轉(zhuǎn)到Step5Step3K K ，如果不滿足，轉(zhuǎn)到Step5。計(jì)算S S(0) S(0s 表示站點(diǎn)i和j -6S(0) Ss Ssn 1則站點(diǎn)A,B間經(jīng)一次轉(zhuǎn)乘有可達(dá)線路，根據(jù)s(1) 若ss(0) s 0的中轉(zhuǎn)站點(diǎn)hS(0) Ss Ssn 1則站點(diǎn)A,B間經(jīng)一次轉(zhuǎn)乘有可達(dá)線路，根據(jù)s(1) 若ss(0) s 0的中轉(zhuǎn)站點(diǎn)hL入可行線路集合Z K K 1；轉(zhuǎn)到Step5Step4K K ，如果不滿足，轉(zhuǎn)到Step5。按照Step3K入Z ，轉(zhuǎn)到Step5，否則轉(zhuǎn)到Step4Step5根據(jù)票價(jià)信息，計(jì)算Z 中各條線路的費(fèi)用C，C最小的為最優(yōu)線路，如果滿足最小的線路不

7、止一條，則選取線路距離T K 2， 2，3(1) S3359下 13準(zhǔn)則S3359下 13準(zhǔn)則S3359下 13準(zhǔn)則(2)S1557下 S1919下S1557下 S1919下準(zhǔn)則23 23準(zhǔn)則 23準(zhǔn)則-7(3) S0971下 準(zhǔn)則13S0971下 準(zhǔn)則13S0971下 13準(zhǔn)則(4) 下上S準(zhǔn)則12S可以為 S0400 S2633 下(3) S0971下 準(zhǔn)則13S0971下 準(zhǔn)則13S0971下 13準(zhǔn)則(4) 下上S準(zhǔn)則12S可以為 S0400 S2633 下上S準(zhǔn)則12S可以為 S2683 S0291 S3614 下上S12準(zhǔn)則S為S2263S3917(5)S0148上 S0036上S

8、可以S221S333S3351S23準(zhǔn)則S0148上 S0036上S可以S221S333S3351S準(zhǔn)則23S0148上 S0036上S可以S221S333S3351S準(zhǔn)則23(6) 上12準(zhǔn)則準(zhǔn)則 上12準(zhǔn)則 上12說(shuō)明：時(shí)間和費(fèi)用min 和yuan -8基于廣度優(yōu)先目標(biāo)函數(shù)換乘搜索算準(zhǔn)則4的求用U(K,iK )(K supK K為整數(shù)，iK為整數(shù))表示第K 次換乘的iK基于廣度優(yōu)先目標(biāo)函數(shù)換乘搜索算準(zhǔn)則4的求用U(K,iK )(K supK K為整數(shù)，iK為整數(shù))表示第K 次換乘的iK 條可行線的集合。當(dāng)綜合考慮這三個(gè)指標(biāo)時(shí)，面對(duì)iK K是指標(biāo)TK F (C,T,K一個(gè)更實(shí)用的目標(biāo)函數(shù)先將

9、各指標(biāo)抽象成同質(zhì)1) 出行費(fèi)用指標(biāo)標(biāo)準(zhǔn)化根據(jù)初始模型，出行費(fèi)用指標(biāo)是越小目標(biāo)越優(yōu)，應(yīng)用模糊數(shù)學(xué)3 中隸屬度的定義1，max(Ci )Cmax(C )min(C 2) 出行距離指標(biāo)標(biāo)準(zhǔn)化max(Ti )Tmax(T )min(T K與C、T KK 1F (w1Cw2TK 足w1 w2 1KF K基于廣度優(yōu)先換乘搜索算Step1ABK的上界supK K為整數(shù) KStep2網(wǎng)絡(luò)的鄰接關(guān)系矩陣SDL為X(i)(i A線Yjj b,b為整數(shù)-91Step3 x(i) y( j，將滿足條件的存入直達(dá)線路集合Z0X(i即Y( j為從站點(diǎn)A到站點(diǎn)B的直達(dá)線路，如圖1所示K K 1Step3 x(i) y( j

10、，將滿足條件的存入直達(dá)線路集合Z0X(i即Y( j為從站點(diǎn)A到站點(diǎn)B的直達(dá)線路，如圖1所示K K 1Step4K K ，如果不成立，停止；否則查詢SDLX(i交站點(diǎn)存換乘矩陣O(i,u)(u 線路Y( j站點(diǎn)存換乘矩陣P( j,v)(v f, f為整數(shù)Step5搜索O(iuP( jv，判斷是否有o(iu) p( jv1，則站點(diǎn)o(iupjv為從站點(diǎn)A到站點(diǎn)B路集合Z1X(i),Y( j為換乘一次的最優(yōu)路線，如圖2K K 1Step6K supK K為整數(shù)，如果不成立，停止；否則搜索SLD為R(k)(k 1,2,3, g為整數(shù))，點(diǎn)o(iu) R(k) G(kh)(h 換乘矩陣O(iu) Ste

11、p7p( jv) g(khZ2Z21g(kh) p( jv為從站點(diǎn)A到站點(diǎn)BX(iR(k),Y( j為換乘二次的最優(yōu)路線，如圖3K K 1Step8K K ，圖1.點(diǎn)A,B直達(dá)的搜索線-10o(1,2) o(2,2) 圖2. 換乘1次時(shí)站點(diǎn)A,B的搜索線g(2,3) g圖3. 換乘2次時(shí)站o(1,2) o(2,2) 圖2. 換乘1次時(shí)站點(diǎn)A,B的搜索線g(2,3) g圖3. 換乘2次時(shí)站點(diǎn)A,B的搜索線K 2K，出行費(fèi)用C和出行距離T (1) W1 W2 S3359下 13W1 W2 S3359下 13W1 W2 S3359下 13-11(2) W1 W2 23 (2) W1 W2 23 W1

12、 W2 23S1557下 S1919下S1557下 S1919下W1 12W2 W1 W2 S0971下 13W1 W2 S0971下 13W1 W2 S0971下 13 S 12W2 S可以為 S0400 S2633 W1 W2 S12S可以為 S0400 S2633 SW1 W2 12S可以為 S0400 S2633 -12(5) S0148上 S0036上S可以,S221S333S3351W1 W2 S23S0148上 S0036上S可以(5) S0148上 S0036上S可以,S221S333S3351W1 W2 S23S0148上 S0036上S可以,S221S333S3351 S2

13、3S0148上 S0036上S可以,S221S333S3351S 23W1 W2 上12W1 W2 上12W1 W2 上125.3 結(jié)果分轉(zhuǎn)乘才能到達(dá)目的地而6 問(wèn)題二的求6.1 對(duì)地鐵站附近的公汽站的處汽。所以，A、B11-13圖4. 同一地鐵對(duì)應(yīng)的任意兩站點(diǎn)的換乘情的6.1 模型二：基于出行時(shí)間最短的線路搜索模2.2（即出行距離T 改進(jìn)的基于廣圖4. 同一地鐵對(duì)應(yīng)的任意兩站點(diǎn)的換乘情的6.1 模型二：基于出行時(shí)間最短的線路搜索模2.2（即出行距離T 改進(jìn)的基于廣度優(yōu)先換乘搜索算Dk(k 為在地鐵站k Step2ADk(k 1.39為X(i)(i a,a 交為Y(j)(j b,b為整數(shù)Ste

14、p3 Step4Step5搜索O(iu) P( jv，判斷是否有o(iu) p( jv，如果存在，則站點(diǎn)o(iup( jv為從站點(diǎn)A到站點(diǎn)B的一次換乘站點(diǎn)；再判斷是否有o(iup( jvDp(p1.39且p kp mDp為從站點(diǎn)A到站點(diǎn)BX(i),Y( j-14入一次轉(zhuǎn)乘線路集合Z1。若存在o(iuDk(k 1.39Dk素添加到O(iu) 線路Y( jPjv)(v 1,2,3f, f為整數(shù)入一次轉(zhuǎn)乘線路集合Z1。若存在o(iuDk(k 1.39Dk素添加到O(iu) 線路Y( jPjv)(v 1,2,3f, f為整數(shù)pjvDk(k 1.39P( jvK K 1Step6K supK K為整數(shù)，

15、如果不成立，停止；否則搜索SLD為R(k)(k 1,2,3, g為整數(shù))，點(diǎn)o(iu) R(k) G(kh)(h 換乘矩陣O(iu) Step7p( jv) g(kh，如果有滿足條件的線路且該線路沒(méi)有在Z1g(kh) p( jv為從站點(diǎn)A到站點(diǎn)BX(iR(k),Y( j為換乘二次的最優(yōu)路線；再判斷是否有一對(duì)o(iup( jvDpDq 中，如果有滿足條件的線路且該線路沒(méi)有在Z1中出現(xiàn)，則DpDq為從站點(diǎn)A到站點(diǎn)B乘線路集合Z2中， K K 1Step8僅以出行時(shí)間（出行距離）(1) 換乘次數(shù) 時(shí)間S3359下S1784 S3359下 13(2) S1557下 S1919下S1557下 S1919

16、下23-15換乘次數(shù) 時(shí)間S0971下 13 SS可以為 S0400 S2633 下?lián)Q乘次數(shù) 時(shí)間S0971下 13 SS可以為 S0400 S2633 下上S，2S可以為 S2683 S0291 下上SSS2263, S3917, 換乘次數(shù) 時(shí)間S0148下 D02 上S0466下 S0148下 S1487D02 上D21 S0464 下 S048525 146.2 模型三：節(jié)點(diǎn)帶權(quán)的網(wǎng)絡(luò)模6.3.1模型的建通網(wǎng)絡(luò)圖45 G(V , E) ，由于每一上下行或環(huán)線組成，故G(VE鐵和其附近站點(diǎn)合并成一個(gè)節(jié)點(diǎn)，所有節(jié)點(diǎn)用集合V v1,v2,.,vn；-16E vi vj vi vj V表示站點(diǎn)v

17、i 和vj vi 和vE vi vj vi vj V表示站點(diǎn)vi 和vj vi 和vj E vivjk,lk 1,2分別表地鐵;l為線f (vi vj k，可以表示為兩頂點(diǎn)間距離，或者途中所經(jīng)過(guò)的時(shí)間，或者交設(shè)起始站點(diǎn)為vS ，目地站點(diǎn)為vT ，交通圖G(VEf (vi ,v j , k f圖5. 同時(shí)考慮公汽和地鐵線路的網(wǎng)絡(luò)示意圖（僅標(biāo)出單向站的平均行使時(shí)間3min2.5minif k if k ,k)f (v ,2.5入邊是公汽線路，出邊是公汽線路（在同一站換乘入邊是公汽線路，出邊是公汽線路（在地鐵站換乘-17ei入 公汽線路，ei出為公汽線路（在同一公汽車(chē)站換乘5公汽線路，e 為公汽線路

18、（在同地鐵站換乘iiei入 地鐵線路，ei出為地ei入 公汽線路，ei出為公汽線路（在同一公汽車(chē)站換乘5公汽線路，e 為公汽線路（在同地鐵站換乘iiei入 地鐵線路，ei出為地鐵線f2(ei入，ei出地鐵線路，e 為公汽線ii公汽線路，e 為地鐵線iiei入和ei出為同一線”，提出“節(jié)”的方法對(duì)上述模型進(jìn)行改進(jìn)的節(jié)點(diǎn)分列成N 個(gè)虛擬節(jié)點(diǎn)（N 與相交線路的條數(shù)相關(guān)），組成所以將D 點(diǎn)分解成六邊形。如圖7所示：圖6.節(jié)點(diǎn)的連接B7. 節(jié)方法的示意圖7中當(dāng)D 節(jié)設(shè)起始站點(diǎn)為vS ，目地站點(diǎn)為vT ，問(wèn)題可轉(zhuǎn)化成求vS 到vT -18接vS 與vT 的目的是求出vS 到vT 轉(zhuǎn)化為求從vS 到vT 的

19、最短路問(wèn)6.3.2模型求可以用 Dijstra 算法57 （或其他算法）進(jìn)行求解。結(jié)果如下(1) 換乘次數(shù) 時(shí)間 費(fèi)用S3359下 接vS 與vT 的目的是求出vS 到vT 轉(zhuǎn)化為求從vS 到vT 的最短路問(wèn)6.3.2模型求可以用 Dijstra 算法57 （或其他算法）進(jìn)行求解。結(jié)果如下(1) 換乘次數(shù) 時(shí)間 費(fèi)用S3359下 13(2) S1557 下 S1919 下 23換乘次數(shù) 時(shí)間 13S0008 下S3053 上12S0148 下 S1487 轉(zhuǎn)地S0466 下 25轉(zhuǎn)-19(6) 換乘次數(shù) 時(shí)間 費(fèi)用14轉(zhuǎn)地 6.3 結(jié)果分相對(duì)于問(wèn)題一的結(jié)果而言， S3359S1828、S155

20、7S0481、S0971S0485(6) 換乘次數(shù) 時(shí)間 費(fèi)用14轉(zhuǎn)地 6.3 結(jié)果分相對(duì)于問(wèn)題一的結(jié)果而言， S3359S1828、S1557S0481、S0971S0485、S0008 S0073而且它們均不在地鐵站周?chē)?，甚至連換乘站也不在地鐵站周?chē)?。S0148S0485、 S0087S3676 這兩種行車(chē)路線都給出了換乘地鐵的路徑，相對(duì)問(wèn)題一的解來(lái)說(shuō)運(yùn)行時(shí)間大大減低了。其中，S0148S0485 比問(wèn)題一中的節(jié)少了約分鐘，這是因?yàn)閮蓚€(gè)S1487 D02， S0466 挨著 D21。S0087S3676 少S0087S3676S3676均在地鐵站附近。7 問(wèn)題三的求模型四：改進(jìn)的網(wǎng)絡(luò)流模新網(wǎng)絡(luò)圖G(VEE vi vj klk 1,2,3分別表地鐵,步行;l為線路標(biāo)號(hào)f (vi vj kl仍用時(shí)間表示邊權(quán) f (vi ,vj ,k,l) ，則：t地if k if k if k f (v ,v ,k,l) 步 3m