1、公交轉(zhuǎn)車問題,南京郵電大學(xué)理學(xué)院楊振華制作 ,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,公交轉(zhuǎn)車問題,針對市場需求，某公司準(zhǔn)備研制開發(fā)一個解決北京市公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)。 為了設(shè)計這樣一個系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。 公交：指公共交通工具 ，包括公共汽車與地鐵。,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,公交轉(zhuǎn)車問題,1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站終到站之間的最佳路線 (1)S3359S1828 (2)S1557S0481 (3)S09

2、71S0485 (4)S0008S0073 (5)S0148S0485 (6)S0087S3676 2、同時考慮公汽與地鐵線路，解決以上問題。,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,基本參數(shù)設(shè)定,相鄰公汽站平均行駛時間(包括停站時間)： 3分鐘 相鄰地鐵站平均行駛時間(包括停站時間)： 2.5分鐘 公汽換乘公汽平均耗時： 5分鐘(其中步行時間2分鐘) 地鐵換乘地鐵平均耗時： 4分鐘(其中步行時間2分鐘) 地鐵換乘公汽平均耗時： 7分鐘(其中步行時間4分鐘) 公汽換乘地鐵平均耗時： 6分鐘(其中步行時間4分鐘) 公汽票價：分為單一票價與分段計價兩種，標(biāo)記于線路后；其中分段計價的票價為：020站：1元

3、；2140站：2元；40站以上：3元 地鐵票價：3元（無論地鐵線路間是否換乘） 注：以上參數(shù)均為簡化問題而作的假設(shè)，未必與實際數(shù)據(jù)完全吻合。,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,公汽線路信息,公汽運行方式 （1）環(huán)形 （2）上下行（有可能上下行路線一致） 公汽收費方式 （1）分段計價 （2）單一票制1元,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,公汽線路信息,文件列出了520條公汽線路，下面是其中的一條： L001 分段計價。 S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710

4、 該線路是分段計價，且上下行路線一致的。,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,地鐵線路信息,T1 票價3元，本線路使用，并可換乘T2。 D01-D02-D03-D04-D05-D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21-D22-D23 T2 票價3元，本線路使用，并可換乘T1。 環(huán)行：D24-D25-D26-D12-D27-D28-D29-D30-D31-D32-D18-D33-D34-D35-D36-D37-D38-D39-D24,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,地鐵T1線換乘公汽信息,D01：S0567，S

5、0042，S0025 D02：S1487 D03：S0303，S0302 D04：S0566 D05：S0436，S0438，S0437，S0435 D06：S0392，S0394，S0393，S0391 D07：S0386，S0388，S0387，S0385 D08：S3068，S0617，S0619，S0618，S0616 D09：S1279 D10：S2057，S0721，S0722，S0720 D11：S0070，S2361，S3721 D12：S0609，S0608 D13：S2633，S0399，S0401，S0400 D14：S3321，S2535，S2464 D15：S3329

6、，S2534 D16：S3506，S0167，S0168 D17：S0237，S0239，S0238，S0236，S0540 D18：S0668 D19：S0180，S0181 D20：S2079，S2933，S1919，S1921，S1920 D21：S0465，S0467，S0466，S0464 D22：S3457 D23：S2512,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,地鐵T2線換乘公汽信息,D24：S0537，S3580 D25：S0526，S0528，S0527，S0525 D26：S3045，S0605，S0607 D12：S0609，S0608 D27：S0087，S0088，S0

7、086 D28：S0855，S0856，S0854，S0857 D29：S0631，S0632，S0630 D30：S3874，S1426，S1427 D31：S0211，S0539，S0541，S0540 D32：S0978，S0497，S0498 D18：S0668 D33：S1894，S1896，S1895 D34：S1104，S0576，S0578，S0577 D35：S3010，S0583，S0582 D36：S3676，S0427，S0061，S0060 D37：S1961，S2817，S0455，S0456 D38：S3262，S0622 D39：S1956，S0289，S029

8、1,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,問題分析,從實際情況考慮，不同的查詢者有不同的要求。在數(shù)學(xué)上體現(xiàn)出目標(biāo)的不同。 一般可以考慮轉(zhuǎn)車次數(shù)、乘車費用、乘車時間這3個目標(biāo)。 問題可以歸結(jié)為多目標(biāo)優(yōu)化問題。,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,問題分析,如何處理上面的多個目標(biāo)？ 多目標(biāo)的處理最常用的方法是單目標(biāo)化，即采用加權(quán)平均等方法將多個目標(biāo)結(jié)合形成一個單一的目標(biāo)。 本問題中，單目標(biāo)化并不合適，比較適當(dāng)?shù)姆椒ㄊ菍γ總€目標(biāo)尋求最佳線路，然后讓乘客按照自己的需求進(jìn)行選擇。,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,模型建立,我們先僅考慮公汽線路的情況。 設(shè)N表示問題中的公汽站點數(shù),即N=3957, A0(a(

9、i,j,0)NN 是直達(dá)最小站數(shù)矩陣，當(dāng)存在公共汽車從站點直達(dá)站點時，表示從直達(dá)的最小站數(shù)。否則該元素取為+。,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,模型建立,令A(yù)m(a(i,j,m)NN是m次轉(zhuǎn)乘最小站數(shù)矩陣，其元素a(i,j,m)表示m次轉(zhuǎn)車情形下，從Si到Sj的最小站數(shù)。 顯然,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小轉(zhuǎn)車次數(shù)模型,對于給定的公汽站點Si與Sj ，最小轉(zhuǎn)車次數(shù)模型可以寫為,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型,轉(zhuǎn)車次數(shù)為m時，從Si到Sj的總時間為 5m+3a(i,j,m), （轉(zhuǎn)一次車5分鐘，每乘一站，用時3分鐘） 下面是最小乘車時間模型：,南京郵電大學(xué)數(shù)理學(xué)院

10、楊振華制作 ,最小乘車費用模型,最小乘車費用模型可以寫為如下的形式：,該模型是形式上的，對于求解沒有實質(zhì)性的作用。,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小轉(zhuǎn)車次數(shù)模型求解,對于給定的公汽站點Si與Sj ，只要逐次求出(a(i,j,m)，直到其為有限值即可。,在實際求解時，先根據(jù)公汽線路的數(shù)據(jù)將a(i,j,0)的數(shù)據(jù)存儲在矩陣A0中。,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小轉(zhuǎn)車次數(shù)模型求解,算法一（逐次查找） 對于給定的i,j, (1)若a(i,j,0)+,表明轉(zhuǎn)車次數(shù)為0,否則轉(zhuǎn)(2); (2)k從1到N進(jìn)行搜索,若a(i,k,0)+,a(k,j,0) +,則轉(zhuǎn)車次數(shù)為1,否則轉(zhuǎn)(3); (3

11、) k1, k2從1到N進(jìn)行搜索,若a(i,k1,0)+, a(k1,k2,0)+, a(k2,j,0) +,則轉(zhuǎn)車次數(shù)為2.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小轉(zhuǎn)車次數(shù)模型求解,逐次查找算法的復(fù)雜度 若只要轉(zhuǎn)一次車,則循環(huán)的步數(shù)為N; 若要轉(zhuǎn)2次車,循環(huán)的步數(shù)為N2; 若要轉(zhuǎn)3次車,循環(huán)的步數(shù)為N3 由于N=3957, N3 6.21010,普通計算機(jī)運行時間較長， 若要轉(zhuǎn)4次車，很難承受計算量!,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小轉(zhuǎn)車次數(shù)模型求解,算法二（存儲逐次查找） (1)若a(i,j,0)+,表明轉(zhuǎn)車次數(shù)為0,否則轉(zhuǎn)(2); (2) 求出矩陣A1(a(i,j,1)NN ,其每

12、個元素通過上面的表達(dá)式,用k從1到N循環(huán)求得.若對給定的i,j,有a(i,j,1)+,表明轉(zhuǎn)車次數(shù)為1; 類似可以計算多次轉(zhuǎn)車的情況 注:矩陣A0,A1等計算后存儲在計算機(jī)中,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小轉(zhuǎn)車次數(shù)模型求解,存儲逐次查找算法的復(fù)雜度 矩陣A1的計算: 一共計算N2個元素,每個元素的計算要循環(huán)N步,計算量為N3.運行時間依然較長。 優(yōu)點： 矩陣Am (m1)的計算工作量與A1一致! 有可能計算轉(zhuǎn)多次車.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小轉(zhuǎn)車次數(shù)模型求解,在前面的兩個算法中,每次循環(huán)都要進(jìn)行N次.事實上,對給定的i,滿足a(i,k,0)+的k是很少的,我們只要對這些k

13、進(jìn)行循環(huán). 在實際問題中,任何一個城市中,任何一個公汽站點所能到達(dá)的公汽站點只是城市中的一些“線”,相對于整個城市而言,數(shù)目是比較少的.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小轉(zhuǎn)車次數(shù)模型求解,算法三（有限搜索逐次查找） 給出矩陣B,其第i行記錄的是滿足a(i,k,0)+的所有的“k”. 將存儲逐次查找算法中的k從1到N循環(huán)改為正對矩陣B第i行中的“k”進(jìn)行循環(huán).,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小轉(zhuǎn)車次數(shù)模型求解,有限搜索逐次查找算法的復(fù)雜度 矩陣Am的計算: 一共計算N2個元素,每個元素的計算要循環(huán)的步數(shù)大大小于N,大約為N/10,計算量約為N3/10. 一般的計算機(jī)可以實現(xiàn).,南京郵

14、電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小轉(zhuǎn)車次數(shù)模型求解,對于題目中給出的六組公汽站點,其最小轉(zhuǎn)車次數(shù)分別為 (1)S3359S18281 (2)S1557S04812 (3)S0971S04851 (4)S0008S00731 (5)S0148S04852 (6)S0087S36761,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,轉(zhuǎn)車次數(shù),由于算法復(fù)雜性的問題,許多參賽隊都假設(shè)“最多轉(zhuǎn)2次車”,少數(shù)參賽隊考慮轉(zhuǎn)3次車,個別的參賽隊考慮轉(zhuǎn)4次車或更多. 由于所給的6組站點最小轉(zhuǎn)車次數(shù)為1或2,似乎假設(shè)最多轉(zhuǎn)2次車是合理的. 根據(jù)題目中的數(shù)據(jù),北京市的任意兩個公汽站點之間一般需轉(zhuǎn)幾次車?,南京郵電大學(xué)數(shù)理學(xué)院楊振

15、華制作 ,轉(zhuǎn)車次數(shù),N=3957,一共有N(N-1)=15653892對公汽站點,我們給出它們的最小轉(zhuǎn)車次數(shù),根據(jù)題目中的數(shù)據(jù),北京市的公汽站點轉(zhuǎn)5次車可以全部到達(dá).,根據(jù)表中的數(shù)據(jù),假設(shè)轉(zhuǎn)最多2次車是不合理的,假設(shè)轉(zhuǎn)最多3次車有一定的合理性.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車費用,左邊的表給出的時最小轉(zhuǎn)車次數(shù),即對應(yīng)的一種乘車方案的乘車費用.,關(guān)于最小乘車費用,其模型一般只有形式上的,對求解沒有直接的作用. 我們對具體的六對站點給出討論的結(jié)果.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車費用,易見,第二,四,五,六對站點對應(yīng)的費用是最小費用(為什么?),南京郵電大學(xué)數(shù)理學(xué)院楊振華制

16、作 ,最小乘車費用,對于第一個點對S3359S1828,如果換乘次數(shù)大于等于2,顯然費用至少為3. 若換乘次數(shù)為1,采用枚舉方法將乘車方案全部列出.一共由9種方案,其中8種費用為3元,一種費用為4元.因此, 最小乘車費用為3. 類似,第三個點對的換乘次數(shù)為1的11種方案的最小費用也是3.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型求解,根據(jù)上面的模型,若已知a(i,j,m)的值,則可以求出tS(i,j,m)關(guān)于m的最小值. 由于m的取值從0到無窮大,必須采用一定的技巧來求出最小值. 注:參賽隊一般選取m從0到2(或0到3),是不合理的,不過也“成功”避免了求解的困難.,南京郵電大學(xué)數(shù)理

17、學(xué)院楊振華制作 ,最小乘車時間模型求解,考慮第一對公汽站點 1)S3359S1828最小轉(zhuǎn)車次數(shù)為1, a(i,j,0) = , tS(i,j,0)=; a(i,j,1) = 32, tS(i,j,1)=101; 由于a(i,j,m) m+1,有tS(i,j,m) 8m+3. 若m13,則tS(i,j,m) 105tS(i,j,1). 因此,我們可以將m的范圍放在0到12內(nèi)求最優(yōu).,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型求解,若m的范圍過大,求解會有一定困難. 能否縮小m的范圍? 在上頁的討論中,不等式a(i,j,m) m+1的含義是總站數(shù)比轉(zhuǎn)車次數(shù)至少大一. 我們可以給出a(i,

18、j,m) 更好的下界,從而縮小m的范圍.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,兩站點之間的最小站數(shù),a(i,j,m)表示m次轉(zhuǎn)車下,從Si到Sj的最小站數(shù). 設(shè)nS(i,j)表示站點Si到Sj的最小站數(shù)(可以轉(zhuǎn)車任意次). 顯然a(i,j,m) nS(i,j) 我們有tS(i,j,m) = 5m+3a(i,j,m) 5m+3nS(i,j),南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,兩站點之間的最小站數(shù),將公汽站點設(shè)為有向圖中的結(jié)點.若Si乘公汽1站可以到達(dá)Sj ,我們就設(shè)一條有向邊從結(jié)點i指向結(jié)點j.對于每一條有向邊,指定其權(quán)為1,顯然求nS(i,j)就轉(zhuǎn)化為有向圖中結(jié)點到結(jié)點的最短路徑問題 . 對任意

19、給定的i,j,我們可以采用Dijkstra算法求得 nS(i,j).,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型求解,對于第一對公汽站點i=3359,j=1828, nS(i,j)=13,我們給出求解過程. a(i,j,0) = , tS(i,j,0)=; a(i,j,1) = 32, tS(i,j,1)=101; m 2時,tS(i,j,m) 52+313=49. 因此,最小乘車時間在區(qū)間49,101上. 為求精確的最優(yōu)解,必須接著求解.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型求解,a(i,j,2) = 18, tS(i,j,2)=64; m 3時,tS(i,j,m) 5

20、3+313=54. 最優(yōu)解位于區(qū)間54,64; a(i,j,3) = 18, tS(i,j,3)=69; m 4時,tS(i,j,m) 54+313=59. 最優(yōu)解位于區(qū)間59,64;,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型求解,a(i,j,4) = 17, tS(i,j,4)=71; m 5時,tS(i,j,m) 55+313=64. 重復(fù)上述過程:tS(i,j,0)=, tS(i,j,1)=101, tS(i,j,2)=64,tS(i,j,3)=69, tS(i,j,4)=71, m 5時,tS(i,j,m) 64. 可以看出,最小乘車時間為64,在轉(zhuǎn)2次車時可以在此時間到達(dá).

21、,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型求解算法,由上面的例子, 我們只要找到一個轉(zhuǎn)車次數(shù)m, 轉(zhuǎn)車次數(shù)不大于m時,最小乘車時間為 TS(i,j,m)=mintS(i,j,k) | km 轉(zhuǎn)車次數(shù)大于m時, 乘車時間的下界為 5(m+1)+3 nS(i,j) 若TS(i,j,m) 5(m+1)+3 nS(i,j), 則TS(i,j,m) 為最優(yōu)解.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型求解算法,Step1 用Dijkstra算法求出nS(i,j) ,令m=0; Step2 求出a(i,j,m),令tS(i,j,m) = 5m+3a(i,j,m); Step3 若 TS

22、(i,j,m)=mintS(i,j,k) | km 5(m+1)+3 nS(i,j), 則TS(i,j,m)即為最短乘車時間; 否則令m:=m+1，轉(zhuǎn)Step2.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型求解,第四對公汽站點S0008S0073的求解過程可以用下面的表格表示(nS(i,j)=13) :,最小乘車時間為59,需轉(zhuǎn)4次車. 其它答案參見評閱要點(該要點給出的答案中包含了起始的3分鐘),南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,綜合考慮公汽與地鐵,(1)最小轉(zhuǎn)車次數(shù) 將地鐵線路看成公汽線路. 最小轉(zhuǎn)車次數(shù)這一目標(biāo)的討論難度沒有增加,只是增加了幾條公汽線路. 對于題中給的六組站點,其

23、前5組站點都不在地鐵邊,因此增加地鐵后,最小乘車次數(shù)沒有變化,仍然是原來的1或2. 第6組2個站點都在地鐵線上,最小轉(zhuǎn)乘次數(shù)為0.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,綜合考慮公汽與地鐵,(2)最小乘車費用 對于一般的兩個站點之間的最小乘車費用,僅考慮公汽時討論就很復(fù)雜,增加了地鐵之后討論還是差不多復(fù)雜,要用枚舉法來求解. 也可以說,難度沒有增加. 對于題中給的六組站點,僅考慮公汽時,最小費用為2元或3元,因此在綜合考慮公汽與地鐵時依然是最優(yōu)解(乘一次地鐵3元),南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,綜合考慮公汽與地鐵,(3)最小乘車時間 增加了地鐵后乘車時間的討論變得相當(dāng)復(fù)雜. 注:如果假設(shè)換成次

24、數(shù)最多為2或3,會將問題大大簡化. 在此,為了將問題合理的簡化,我們首先研究這樣一個問題：在考慮時間最少時，線路中是否存在先乘地鐵，再轉(zhuǎn)公汽，再乘地鐵這樣的乘車方案？,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,地鐵-公汽-地鐵?,考察下面兩種方案 （A）從地鐵站Dk乘地鐵到地鐵站Dk1然后由公汽站Ss1乘到公汽站Ss2 ，再轉(zhuǎn)地鐵站Dl1，乘地鐵到地鐵站Dl； （B）直接乘地鐵由地鐵站Dk到Dl 。 直觀認(rèn)識:(A)的時間(B)的時間,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,地鐵-公汽-地鐵?,設(shè)tDB(i,j)表示乘地鐵由地鐵站Di到地鐵站Dj的最短時間，nSA(i,j)表示可以由地鐵站Di轉(zhuǎn)乘的公汽站乘

25、公汽到可以由地鐵站Dj轉(zhuǎn)乘的公汽站的最小公汽站數(shù)。 于是, TB = tDB(k,l) 如果(A)方案中沒有公汽轉(zhuǎn)車 TA = tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13 13表示換車時間 如果有公汽轉(zhuǎn)車,等號要換成大于等于號,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,地鐵-公汽-地鐵?,TA - TB tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13- tDB(k,l) = 3 nSA(k1,l1) +13- tDB(k1,l1) + tDB(k,k1) + tDB(k1,l1)+ tDB(l1,l)- tDB(k,l) 最后一個中括號中的式子是

26、非負(fù)的. 因此TA - TB 3 nSA(k1,l1) +13- tDB(k1,l1) 如果右式非負(fù),則有TA - TB 0.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,地鐵-公汽-地鐵?,3 nSA(k1,l1) +13- tDB(k1,l1) 0? 一共有39個地鐵站,我們通過計算機(jī)程序（k1,l1對從1到39進(jìn)行遍歷搜索）來判斷上式左邊的值,發(fā)現(xiàn)有四組地鐵站對應(yīng)的值為負(fù),分別是(13,30),(16,30),(30,15),(30,16),這四組站點對應(yīng)的nSA(k1,l1) 值均為1. 對這四組點,再觀察 TA - TB tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13

27、- tDB(k,l) 右端的值,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,地鐵-公汽-地鐵?,tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13- tDB(k,l) =tDB(k,k1)+ tDB(l1,l)+16- tDB(k,l) 對于前面四組k1,l1,對k,l進(jìn)行循環(huán)搜索,可以得到tDB(k,k1)+ tDB(l1,l)+16- tDB(k,l)的最小值都是2. 最終得到TA - TB 0. 結(jié)論:對于題中給的數(shù)據(jù),為了時間最省,不存在“地鐵-公汽-地鐵”這種換乘方案. 換言之:地鐵一次乘完!,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型,對于任意兩個公汽站點,不乘

28、地鐵的時間最小方案在問題一中已經(jīng)求得.下面考慮必須乘地鐵的方案: 乘p次（轉(zhuǎn)p-1次）公汽，再乘地鐵，最后乘次q（轉(zhuǎn)q-1次)公汽到達(dá)終點的方案，下面將這樣的方案記為pDq。 注:該方案包含了僅乘地鐵的情況(p=q=0).,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型,下面主要針對題中前5組站點進(jìn)行研究.這五組站點均不能由地鐵站直接轉(zhuǎn)乘,因此p,q1. 求任意公汽站點Si到公汽站點Sj在方案下的最短時間,即對任意的p,q,以及任意的地鐵站Dk,Dl,求出起點乘p次公汽到可以直接轉(zhuǎn)乘地鐵站Dk的公汽站的最短時間,加上Dk到Dl的最短時間,再加上可以由地鐵站Dl直接轉(zhuǎn)乘的公汽站乘q公汽次到達(dá)

29、終點公汽站的最短時間.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型,(1)站數(shù):N1(i,k,p-1),乘車時間: 3N1(i,k,p-1),轉(zhuǎn)車時間5(p-1),Si,Dk,Sj,Dl,(1)p次,(3)q次,(3)站數(shù):N2(l,j,q-1),乘車時間: 3N2(l,j,q-1),轉(zhuǎn)車時間5(q-1),(2),(2)乘車時間: tD(k,l),(4)公汽轉(zhuǎn)地鐵,地鐵轉(zhuǎn)公汽時間:13,總時間:tSDS(i,j,p,q,k,l)= 3N1(i,k,p-1)+ 5(p-1)+ tD(k,l)+3N2(l,j,q-1)+ 5(q-1)+13,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模

30、型,數(shù)學(xué)模型 mintSDS(i,j,p,q,k,l)|1p,q,1 k,l 39,kl 在tSDS(i,j,p,q,k,l)表達(dá)式中,地鐵乘坐時間tD(k,l)是很容易計算的. 若沒有轉(zhuǎn)車, tD(k,l)=2.5nD(k,l)(每站2.5分鐘) 若轉(zhuǎn)1次車, tD(k,l)=2.5nD(k,l)+4. 不存在轉(zhuǎn)2次以上的情況.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型求解,tSDS(i,j,p,q,k,l)= 3N1(i,k,p-1)+ 5(p-1)+ tD(k,l)+3N2(l,j,q-1)+ 5(q-1)+13 對于固定的i,j,我們要遍歷p,q,k,l來求上式的最小值. 對

31、于k,l進(jìn)行遍歷是比較簡單的. 為了縮小p,q的取值范圍,可以類似于問題一來給出站數(shù)(公汽與地鐵)的下界.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,下界,設(shè)nSDS(i,j)表示從Si乘車(公汽或地鐵,可以轉(zhuǎn)車任意次)到Sj的最小乘車站數(shù).我們可以用Dijkstra求最短路徑來求出這個數(shù). 記M=N1(i,k,p-1)+N2(l,j,q-1)為乘車方案中公汽的站數(shù).根據(jù)公汽的站數(shù)加地鐵站數(shù)不小于最小乘車站數(shù),有M+nD(k,l) nSDS(i,j).,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,下界,將M=N1(i,k,p-1)+N2(l,j,q-1) 代入tSDS(i,j,p,q,k,l)= 3N1(i,k

32、,p-1)+ 5(p-1)+ tD(k,l)+3N2(l,j,q-1)+ 5(q-1)+13 得tSDS(i,j,p,q,k,l)=3M+tD(k,l)+5(p+q)+3 由于tD(k,l)=2.5nD(k,l)或2.5nD(k,l)+4, 有tSDS(i,j,p,q,k,l) 3M+ 2.5nD(k,l) +5(p+q)+3 =0.5M+2.5M+ 2.5nD(k,l) +5(p+q)+3 M+nD(k,l) nSDS(i,j),南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,下界,tSDS(i,j,p,q,k,l) 0.5M+2.5M+ 2.5nD(k,l) +5(p+q)+3 再由M+nD(k,l) nSDS(i,j)得 tSDS(i,j,p,q,k,l) 0.5M+2.5nSDS(i,j)+ 5(p+q)+3 另外,M表示乘公汽的站數(shù),顯然Mp+q,(一共乘了p+q次公汽,每次至少一站). 我們最終得到 tSDS(i,j,p,q,k,l) 2.5nSDS(i,j)+ 5.5(p+q)+3 根據(jù)這一下界, 搜索不多的p,q就得到最小時間.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作 ,最小乘車時間模型求解,對第一個點對, i=3359, j=1828, nSDS(i,j)=12(由