公交轉車問題(數(shù)學建模)

1、公交轉車問題南京郵電大學理學院楊振華制作南京郵電大學理學院楊振華制作南京郵電大學數(shù)理學院楊振華制作 公交轉車問題針對市場需求，某公司準備研制開發(fā)一個解針對市場需求，某公司準備研制開發(fā)一個解決北京市公交線路選擇問題的自主查詢計算決北京市公交線路選擇問題的自主查詢計算機系統(tǒng)。機系統(tǒng)。為了設計這樣一個系統(tǒng)，其核心是線路選擇為了設計這樣一個系統(tǒng)，其核心是線路選擇的模型與算法，應該從實際情況出發(fā)考慮，的模型與算法，應該從實際情況出發(fā)考慮，滿足查詢者的滿足查詢者的各種不同需求各種不同需求。公交：指公共交通工具公交：指公共交通工具 ，包括公共汽車與地，包括公共汽車與地鐵。鐵。南京郵電大學數(shù)理學院楊振華制作

2、公交轉車問題1、僅考慮公汽線路，給出任意兩公汽站點之、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學模型與算法。并間線路選擇問題的一般數(shù)學模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下出以下6對起始站對起始站終到站之間的最佳路線終到站之間的最佳路線 (1)S3359S1828 (2)S1557S0481 (3)S0971S0485 (4)S0008S0073 (5)S0148S0485 (6)S0087S3676 2、同時考慮公汽與地鐵線路，解決以上問題。、同時考慮公汽與地鐵線路，解決以上問題。南京郵電大學數(shù)理學院楊振華制作 基本

3、參數(shù)設定 相鄰公汽站平均行駛時間相鄰公汽站平均行駛時間(包括停站時間包括停站時間)： 3分鐘分鐘相鄰地鐵站平均行駛時間相鄰地鐵站平均行駛時間(包括停站時間包括停站時間)： 2.5分鐘分鐘公汽換乘公汽平均耗時：公汽換乘公汽平均耗時： 5分鐘分鐘(其中步行時間其中步行時間2分鐘分鐘)地鐵換乘地鐵平均耗時：地鐵換乘地鐵平均耗時： 4分鐘分鐘(其中步行時間其中步行時間2分鐘分鐘)地鐵換乘公汽平均耗時：地鐵換乘公汽平均耗時： 7分鐘分鐘(其中步行時間其中步行時間4分鐘分鐘)公汽換乘地鐵平均耗時：公汽換乘地鐵平均耗時： 6分鐘分鐘(其中步行時間其中步行時間4分鐘分鐘)公汽票價：分為單一票價與分段計價兩種，

4、標記于線路后；公汽票價：分為單一票價與分段計價兩種，標記于線路后；其中分段計價的票價為：其中分段計價的票價為：020站：站：1元；元；2140站：站：2元；元；40站以上：站以上：3元元地鐵票價：地鐵票價：3元（無論地鐵線路間是否換乘）元（無論地鐵線路間是否換乘）注：以上參數(shù)均為簡化問題而作的假設，未必與實際數(shù)據(jù)完注：以上參數(shù)均為簡化問題而作的假設，未必與實際數(shù)據(jù)完全吻合。全吻合。南京郵電大學數(shù)理學院楊振華制作 公汽線路信息 公汽運行方式公汽運行方式（1）環(huán)形）環(huán)形（2）上下行（有可能上下行路線一致）上下行（有可能上下行路線一致）公汽收費方式公汽收費方式（1）分段計價）分段計價（2）單一票制）

5、單一票制1元元南京郵電大學數(shù)理學院楊振華制作 公汽線路信息文件列出了文件列出了520條公汽線路，下面是其中的一條：條公汽線路，下面是其中的一條：L001分段計價。分段計價。S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710該線路是分段計價，且上下行路線一致的。該線路是分段計價，且上下行路線一致的。南京郵電大學數(shù)理學院楊振華制作 地鐵線路信息T1票價票價3元，本線路使用，并可換乘元，本線路使用，并可換乘T2。D01-D02-D03-D04-D05-D06-D07-D08

6、-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21-D22-D23T2票價票價3元，本線路使用，并可換乘元，本線路使用，并可換乘T1。環(huán)行：環(huán)行：D24-D25-D26-D12-D27-D28-D29-D30-D31-D32-D18-D33-D34-D35-D36-D37-D38-D39-D24南京郵電大學數(shù)理學院楊振華制作 地鐵T1線換乘公汽信息D01：S0567，S0042，S0025D02：S1487D03：S0303，S0302D04：S0566D05：S0436，S0438，S0437，S0435D06：S0392，S0394，S

7、0393，S0391D07：S0386，S0388，S0387，S0385D08：S3068，S0617，S0619，S0618，S0616D09：S1279D10：S2057，S0721，S0722，S0720D11：S0070，S2361，S3721D12：S0609，S0608D13：S2633，S0399，S0401，S0400D14：S3321，S2535，S2464D15：S3329，S2534D16：S3506，S0167，S0168D17：S0237，S0239，S0238，S0236，S0540D18：S0668D19：S0180，S0181D20：S2079，S2933，S

8、1919，S1921，S1920D21：S0465，S0467，S0466，S0464D22：S3457D23：S2512南京郵電大學數(shù)理學院楊振華制作 地鐵T2線換乘公汽信息D24：S0537，S3580D25：S0526，S0528，S0527，S0525D26：S3045，S0605，S0607D12：S0609，S0608D27：S0087，S0088，S0086D28：S0855，S0856，S0854，S0857D29：S0631，S0632，S0630D30：S3874，S1426，S1427D31：S0211，S0539，S0541，S0540D32：S0978，S0497，S

9、0498D18：S0668D33：S1894，S1896，S1895D34：S1104，S0576，S0578，S0577D35：S3010，S0583，S0582D36：S3676，S0427，S0061，S0060D37：S1961，S2817，S0455，S0456D38：S3262，S0622D39：S1956，S0289，S0291南京郵電大學數(shù)理學院楊振華制作 問題分析從實際情況考慮，不同的查詢者有不同的要從實際情況考慮，不同的查詢者有不同的要求。在數(shù)學上體現(xiàn)出目標的不同。求。在數(shù)學上體現(xiàn)出目標的不同。一般可以考慮轉車次數(shù)、乘車費用、乘車時一般可以考慮轉車次數(shù)、乘車費用、乘車時間這

10、間這3個目標。個目標。問題可以歸結為多目標優(yōu)化問題。問題可以歸結為多目標優(yōu)化問題。南京郵電大學數(shù)理學院楊振華制作 問題分析如何處理上面的多個目標？如何處理上面的多個目標？多目標的處理最常用的方法是單目標化，即多目標的處理最常用的方法是單目標化，即采用加權平均等方法將多個目標結合形成一采用加權平均等方法將多個目標結合形成一個單一的目標。個單一的目標。本問題中，單目標化并不合適，比較適當?shù)谋締栴}中，單目標化并不合適，比較適當?shù)姆椒ㄊ菍γ總€目標尋求最佳線路，然后讓乘方法是對每個目標尋求最佳線路，然后讓乘客按照自己的需求進行選擇?？桶凑兆约旱男枨筮M行選擇。 南京郵電大學數(shù)理學院楊振華制作 模型建立我們

11、先我們先僅考慮公汽線路的情況僅考慮公汽線路的情況。設設N表示問題中的公汽站點數(shù)表示問題中的公汽站點數(shù),即即N=3957,A0(a(i,j,0)NN是直達最小站數(shù)矩陣，當存在公共汽車從站是直達最小站數(shù)矩陣，當存在公共汽車從站點直達站點時，表示從直達的最小站數(shù)。否點直達站點時，表示從直達的最小站數(shù)。否則該元素取為則該元素取為+。 南京郵電大學數(shù)理學院楊振華制作 模型建立令令Am(a(i,j,m)NN是是m次轉乘最小站數(shù)矩次轉乘最小站數(shù)矩陣，其元素陣，其元素a(i,j,m)表示表示m次轉車情形下，從次轉車情形下，從Si到到Sj的最小站數(shù)。的最小站數(shù)。顯然顯然 ,1 | ) 1,()0 ,(min),

12、(jkikNkmjkakiamjia南京郵電大學數(shù)理學院楊振華制作 最小轉車次數(shù)模型對于給定的公汽站點對于給定的公汽站點Si與與Sj ，最小轉車次數(shù)模，最小轉車次數(shù)模型可以寫為型可以寫為),(|minmjiam南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型轉車次數(shù)為轉車次數(shù)為m時，從時，從Si到到Sj的總時間為的總時間為5m+3a(i,j,m),（轉一次車（轉一次車5分鐘，每乘一站，用時分鐘，每乘一站，用時3分鐘）分鐘）下面是最小乘車時間模型：下面是最小乘車時間模型：),(35),(min0mjiammjitSm南京郵電大學數(shù)理學院楊振華制作 最小乘車費用模型最小乘車費用模型可以寫為如下的形

13、式：最小乘車費用模型可以寫為如下的形式：,|),(),(),(min21211互不相等nnmmnnnnkkkjikkfjkfkif該模型是形式上的，對于求解沒有實質性的該模型是形式上的，對于求解沒有實質性的作用。作用。南京郵電大學數(shù)理學院楊振華制作 最小轉車次數(shù)模型求解對于給定的公汽站點對于給定的公汽站點Si與與Sj ，只要逐次求出，只要逐次求出(a(i,j,m)，直到其為有限值即可。，直到其為有限值即可。),(|minmjiam,1 | ) 1,()0 ,(min),(jkikNkmjkakiamjia在實際求解時，先根據(jù)公汽線路的數(shù)據(jù)將在實際求解時，先根據(jù)公汽線路的數(shù)據(jù)將a(i,j,0)的

14、數(shù)據(jù)存儲在矩陣的數(shù)據(jù)存儲在矩陣A0中。中。南京郵電大學數(shù)理學院楊振華制作 最小轉車次數(shù)模型求解算法一（逐次查找）算法一（逐次查找）對于給定的對于給定的i,j,(1)若若a(i,j,0)+,表明轉車次數(shù)為表明轉車次數(shù)為0,否則轉否則轉(2);(2)k從從1到到N進行搜索進行搜索,若若a(i,k,0)+,a(k,j,0) +,則轉車次數(shù)為則轉車次數(shù)為1,否則轉否則轉(3);(3) k1, k2從從1到到N進行搜索進行搜索,若若a(i,k1,0)+, a(k1,k2,0)+, a(k2,j,0) +,則轉車次數(shù)為則轉車次數(shù)為2.,1 | ) 1,()0 ,(min),(jkikNkmjkakiamj

15、ia),(|minmjiam南京郵電大學數(shù)理學院楊振華制作 最小轉車次數(shù)模型求解逐次查找算法的復雜度逐次查找算法的復雜度若只要轉一次車若只要轉一次車,則循環(huán)的步數(shù)為則循環(huán)的步數(shù)為N;若要轉若要轉2次車次車,循環(huán)的步數(shù)為循環(huán)的步數(shù)為N2;若要轉若要轉3次車次車,循環(huán)的步數(shù)為循環(huán)的步數(shù)為N3由于由于N=3957, N3 6.21010,普通計算機運行普通計算機運行時間較長，時間較長，若要轉若要轉4次車，很難承受計算量次車，很難承受計算量!南京郵電大學數(shù)理學院楊振華制作 最小轉車次數(shù)模型求解算法二（存儲逐次查找）算法二（存儲逐次查找）(1)若若a(i,j,0)+,表明轉車次數(shù)為表明轉車次數(shù)為0,否則

16、轉否則轉(2);(2) 求出矩陣求出矩陣A1(a(i,j,1)NN ,其每個元素通其每個元素通過上面的表達式過上面的表達式,用用k從從1到到N循環(huán)求得循環(huán)求得.若對給若對給定的定的i,j,有有a(i,j,1)1)的計算工作量與的計算工作量與A1一致一致!有可能計算轉多次車有可能計算轉多次車.南京郵電大學數(shù)理學院楊振華制作 最小轉車次數(shù)模型求解在前面的兩個算法中在前面的兩個算法中,每次循環(huán)都要進行每次循環(huán)都要進行N次次.事實上事實上,對給定的對給定的i,滿足滿足a(i,k,0)+的的k是很少是很少的的,我們只要對這些我們只要對這些k進行循環(huán)進行循環(huán).在實際問題中在實際問題中,任何一個城市中任何一

17、個城市中,任何一個公汽任何一個公汽站點所能到達的公汽站點只是城市中的一些站點所能到達的公汽站點只是城市中的一些“線線”,相對于整個城市而言相對于整個城市而言,數(shù)目是比較少的數(shù)目是比較少的.,1 | ) 1,()0 ,(min),(jkikNkmjkakiamjia南京郵電大學數(shù)理學院楊振華制作 最小轉車次數(shù)模型求解算法三（有限搜索逐次查找）算法三（有限搜索逐次查找）給出矩陣給出矩陣B,其第其第i行記錄的是滿足行記錄的是滿足a(i,k,0)tS(i,j,1).因此因此,我們可以將我們可以將m的范圍放在的范圍放在0到到12內(nèi)求最優(yōu)內(nèi)求最優(yōu).),(35),(min0mjiammjitSm南京郵電大學

18、數(shù)理學院楊振華制作 最小乘車時間模型求解若若m的范圍過大的范圍過大,求解會有一定困難求解會有一定困難.能否縮小能否縮小m的范圍的范圍?在上頁的討論中在上頁的討論中,不等式不等式a(i,j,m) m+1的含義的含義是總站數(shù)比轉車次數(shù)至少大一是總站數(shù)比轉車次數(shù)至少大一.我們可以給出我們可以給出a(i,j,m) 更好的下界更好的下界,從而縮小從而縮小m的范圍的范圍.南京郵電大學數(shù)理學院楊振華制作 兩站點之間的最小站數(shù)a(i,j,m)表示表示m次轉車下次轉車下,從從Si到到Sj的最小站數(shù)的最小站數(shù).設設nS(i,j)表示站點表示站點Si到到Sj的最小站數(shù)的最小站數(shù)(可以轉車可以轉車任意次任意次).顯然

19、顯然a(i,j,m) nS(i,j)我們有我們有tS(i,j,m) = 5m+3a(i,j,m) 5m+3nS(i,j)南京郵電大學數(shù)理學院楊振華制作 兩站點之間的最小站數(shù)將公汽站點設為有向圖中的結點將公汽站點設為有向圖中的結點.若若Si乘公汽乘公汽1站可以到達站可以到達Sj ,我們就設一條有向邊從結點我們就設一條有向邊從結點i指指向結點向結點j.對于每一條有向邊對于每一條有向邊,指定其權為指定其權為1,顯然顯然求求nS(i,j)就轉化為有向圖中結點到結點的最短就轉化為有向圖中結點到結點的最短路徑問題路徑問題 .對任意給定的對任意給定的i,j,我們可以采用我們可以采用Dijkstra算法求算法

20、求得得 nS(i,j).南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型求解對于第一對公汽站點對于第一對公汽站點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ū)間最小乘車時間在區(qū)間49,101上上.為求精確的最優(yōu)解為求精確的最優(yōu)解,必須接著求解必須接著求解.南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型求解a(i,j,2) = 18, tS(i,j,2)=64; m 3時

21、時,tS(i,j,m) 53+313=54.最優(yōu)解位于區(qū)間最優(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ū)間最優(yōu)解位于區(qū)間59,64;南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型求解a(i,j,4) = 17, tS(i,j,4)=71; m 5時時,tS(i,j,m) 55+313=64.重復上述過程重復上述過程: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.可以看

22、出可以看出,最小乘車時間為最小乘車時間為64,在轉在轉2次車時可次車時可以在此時間到達以在此時間到達.南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型求解算法由上面的例子由上面的例子, 我們只要找到一個轉車次數(shù)我們只要找到一個轉車次數(shù)m,轉車次數(shù)不大于轉車次數(shù)不大于m時時,最小乘車時間為最小乘車時間為TS(i,j,m)=mintS(i,j,k) | km轉車次數(shù)大于轉車次數(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)解為最優(yōu)解.南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模

23、型求解算法Step1 用用Dijkstra算法求出算法求出nS(i,j) ,令令m=0;Step2 求出求出a(i,j,m),令令tS(i,j,m) = 5m+3a(i,j,m);Step3 若若TS(i,j,m)=mintS(i,j,k) | km 5(m+1)+3 nS(i,j), 則則TS(i,j,m)即為最短乘車時間即為最短乘車時間;否則令否則令m:=m+1，轉，轉Step2.南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型求解第四對公汽站點第四對公汽站點S0008S0073的求解過程可的求解過程可以用下面的表格表示以用下面的表格表示(nS(i,j)=13) : m01234ts(i,

24、j,m)83676359Ts(i,j,m)836763595(m+1)+3ns(i,j) 4449545964最小乘車時間為最小乘車時間為59,需轉需轉4次車次車.其它答案參見評閱要點其它答案參見評閱要點(該要點給出的答案中該要點給出的答案中包含了起始的包含了起始的3分鐘分鐘)南京郵電大學數(shù)理學院楊振華制作 綜合考慮公汽與地鐵(1)最小轉車次數(shù)最小轉車次數(shù)將地鐵線路看成公汽線路將地鐵線路看成公汽線路.最小轉車次數(shù)這一目標的討論難度沒有增加最小轉車次數(shù)這一目標的討論難度沒有增加,只只是增加了幾條公汽線路是增加了幾條公汽線路.對于題中給的六組站點對于題中給的六組站點,其前其前5組站點都不在地組站點

25、都不在地鐵邊鐵邊,因此增加地鐵后因此增加地鐵后,最小乘車次數(shù)沒有變化最小乘車次數(shù)沒有變化,仍然是原來的仍然是原來的1或或2.第第6組組2個站點都在地鐵線上個站點都在地鐵線上,最小轉乘次數(shù)為最小轉乘次數(shù)為0.南京郵電大學數(shù)理學院楊振華制作 綜合考慮公汽與地鐵(2)最小乘車費用最小乘車費用對于一般的兩個站點之間的最小乘車費用對于一般的兩個站點之間的最小乘車費用,僅僅考慮公汽時討論就很復雜考慮公汽時討論就很復雜,增加了地鐵之后討增加了地鐵之后討論還是差不多復雜論還是差不多復雜,要用枚舉法來求解要用枚舉法來求解.也可以說也可以說,難度沒有增加難度沒有增加.對于題中給的六組站點對于題中給的六組站點,僅考

26、慮公汽時僅考慮公汽時,最小費最小費用為用為2元或元或3元元,因此在綜合考慮公汽與地鐵時因此在綜合考慮公汽與地鐵時依然是最優(yōu)解依然是最優(yōu)解(乘一次地鐵乘一次地鐵3元元)南京郵電大學數(shù)理學院楊振華制作 綜合考慮公汽與地鐵(3)最小乘車時間最小乘車時間增加了地鐵后乘車時間的討論變得相當復雜增加了地鐵后乘車時間的討論變得相當復雜.注注:如果假設換成次數(shù)最多為如果假設換成次數(shù)最多為2或或3,會將問題大會將問題大大簡化大簡化.在此在此,為了將問題合理的簡化為了將問題合理的簡化,我們首先研究這我們首先研究這樣一個問題：在考慮時間最少時，線路中是樣一個問題：在考慮時間最少時，線路中是否存在先乘地鐵，再轉公汽，

27、再乘地鐵這樣否存在先乘地鐵，再轉公汽，再乘地鐵這樣的乘車方案？的乘車方案？ 南京郵電大學數(shù)理學院楊振華制作 地鐵-公汽-地鐵?考察下面兩種方案考察下面兩種方案（A）從地鐵站）從地鐵站Dk乘地鐵到地鐵站乘地鐵到地鐵站Dk1然后由然后由公汽站公汽站Ss1乘到公汽站乘到公汽站Ss2 ，再轉地鐵站，再轉地鐵站Dl1，乘地鐵到地鐵站乘地鐵到地鐵站Dl； （B）直接乘地鐵由地鐵站）直接乘地鐵由地鐵站Dk到到Dl 。直觀認識直觀認識:(A)的時間的時間(B)的時間的時間南京郵電大學數(shù)理學院楊振華制作 地鐵-公汽-地鐵?設設tDB(i,j)表示乘地鐵由地鐵站表示乘地鐵由地鐵站Di到地鐵站到地鐵站Dj的的最短時

28、間，最短時間，nSA(i,j)表示可以由地鐵站表示可以由地鐵站Di轉乘的轉乘的公汽站乘公汽到可以由地鐵站公汽站乘公汽到可以由地鐵站Dj轉乘的公汽轉乘的公汽站的最小公汽站數(shù)。站的最小公汽站數(shù)。于是于是, TB = tDB(k,l)如果如果(A)方案中沒有公汽轉車方案中沒有公汽轉車TA = tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+1313表示換車時間表示換車時間如果有公汽轉車如果有公汽轉車,等號要換成大于等于號等號要換成大于等于號南京郵電大學數(shù)理學院楊振華制作 地鐵-公汽-地鐵?TA - TB tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13-

29、tDB(k,l)= 3 nSA(k1,l1) +13- tDB(k1,l1)+ tDB(k,k1) + tDB(k1,l1)+ tDB(l1,l)- tDB(k,l)最后一個中括號中的式子是非負的最后一個中括號中的式子是非負的.因此因此TA - TB 3 nSA(k1,l1) +13- tDB(k1,l1)如果右式非負如果右式非負,則有則有TA - TB 0.南京郵電大學數(shù)理學院楊振華制作 地鐵-公汽-地鐵?3 nSA(k1,l1) +13- tDB(k1,l1) 0?一共有一共有39個地鐵站個地鐵站,我們通過計算機程序（我們通過計算機程序（k1,l1對從對從1到到39進行遍歷搜索）來判斷上式

30、左邊的值進行遍歷搜索）來判斷上式左邊的值,發(fā)現(xiàn)有發(fā)現(xiàn)有四組地鐵站對應的值為負四組地鐵站對應的值為負,分別是分別是(13,30),(16,30),(30,15),(30,16),這四組站點對應的這四組站點對應的nSA(k1,l1) 值均為值均為1.對這四組點對這四組點,再觀察再觀察TA - TB tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13- tDB(k,l)右端的值右端的值南京郵電大學數(shù)理學院楊振華制作 地鐵-公汽-地鐵?tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13- tDB(k,l)=tDB(k,k1)+ tDB(l1,l)+16- t

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

32、下面考慮必須乘地鐵的方案鐵的方案:乘乘p次（轉次（轉p-1次）公汽，再乘地鐵，最后乘次）公汽，再乘地鐵，最后乘次次q（轉（轉q-1次次)公汽到達終點的方案，下面將公汽到達終點的方案，下面將這樣的方案記為這樣的方案記為pDq。注注:該方案包含了僅乘地鐵的情況該方案包含了僅乘地鐵的情況(p=q=0).南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型下面主要針對題中前下面主要針對題中前5組站點進行研究組站點進行研究.這五這五組站點均不能由地鐵站直接轉乘組站點均不能由地鐵站直接轉乘,因此因此p,q1.求任意公汽站點求任意公汽站點Si到公汽站點到公汽站點Sj在方案下的最在方案下的最短時間短時間,即對任意

33、的即對任意的p,q,以及任意的地鐵站以及任意的地鐵站Dk,Dl,求出起點乘求出起點乘p次公汽到可以直接轉乘地次公汽到可以直接轉乘地鐵站鐵站Dk的公汽站的最短時間的公汽站的最短時間,加上加上Dk到到Dl的最的最短時間短時間,再加上可以由地鐵站再加上可以由地鐵站Dl直接轉乘的公直接轉乘的公汽站乘汽站乘q公汽次到達終點公汽站的最短時間公汽次到達終點公汽站的最短時間.南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型(1)站數(shù)站數(shù):N1(i,k,p-1),乘車時間乘車時間: 3N1(i,k,p-1),轉車時間轉車時間5(p-1)SiDkSjDl(1)p次(3)q次(3)站數(shù)站數(shù):N2(l,j,q-1),

34、乘車時間乘車時間: 3N2(l,j,q-1),轉車時間轉車時間5(q-1)(2)(2)乘車時間乘車時間: tD(k,l)(4)公汽轉地鐵公汽轉地鐵,地鐵轉公汽時間地鐵轉公汽時間: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南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型數(shù)學模型數(shù)學模型mintSDS(i,j,p,q,k,l)|1p,q,1 k,l 39,kl在在tSDS(i,j,p,q,k,l)表達式中表達式中,地鐵乘坐時間地鐵乘坐時間tD(k,l)是很容易計算的是很容易計算的

35、.若沒有轉車若沒有轉車, tD(k,l)=2.5nD(k,l)(每站每站2.5分鐘分鐘)若轉若轉1次車次車, tD(k,l)=2.5nD(k,l)+4.不存在轉不存在轉2次以上的情況次以上的情況.南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型求解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來求上式的最來求上式的最小值小值.對于對于k,l進行遍歷是比較簡單的進行遍歷是比較簡單的.為了縮小為了縮小p,q的取值范圍的取值范圍,可以類似于問

36、題一來可以類似于問題一來給出站數(shù)給出站數(shù)(公汽與地鐵公汽與地鐵)的下界的下界.南京郵電大學數(shù)理學院楊振華制作 下界設設nSDS(i,j)表示從表示從Si乘車乘車(公汽或地鐵公汽或地鐵,可以轉車可以轉車任意次任意次)到到Sj的最小乘車站數(shù)的最小乘車站數(shù).我們可以用我們可以用Dijkstra求最短路徑來求出這個數(shù)求最短路徑來求出這個數(shù).記記M=N1(i,k,p-1)+N2(l,j,q-1)為乘車方案中公汽的站為乘車方案中公汽的站數(shù)數(shù).根據(jù)公汽的站數(shù)加地鐵站數(shù)不小于最小乘車站數(shù)根據(jù)公汽的站數(shù)加地鐵站數(shù)不小于最小乘車站數(shù),有有M+nD(k,l) nSDS(i,j).南京郵電大學數(shù)理學院楊振華制作 下界

37、將將M=N1(i,k,p-1)+N2(l,j,q-1) 代入代入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得得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)+3M+nD(k,l) nSDS(i,j)南京郵電大學數(shù)理學院楊振華制作 下界tSDS(i,

38、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ù)表示乘公汽的站數(shù),顯然顯然Mp+q,(一共乘一共乘了了p+q次公汽次公汽,每次至少一站每次至少一站).我們最終得到我們最終得到tSDS(i,j,p,q,k,l) 2.5nSDS(i,j)+ 5.5(p+q)+3根據(jù)這一下界根據(jù)這一下界, 搜索不多的搜索不多的p,q就得到最小時間就得到最小時間.南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型求解對

39、第一個點對對第一個點對, i=3359, j=1828, nSDS(i,j)=12(由由于增加了地鐵于增加了地鐵,最小站數(shù)小了最小站數(shù)小了).(1)p+q=2,p=1,q=1t=84.5,p+q 3時時,下界下界2.5nSDS(i,j)+ 5.5(p+q)+3=49.5(2) p+q=3,p=1,q=2,t=71; p=2,q=1,t=75.5p+q 4時時,下界下界2.5nSDS(i,j)+ 5.5(p+q)+3=55南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型求解(3) p+q=4,p=1,q=3,t=76;p=2,q=2,t=62;p=3,q=1,t=80.5p+q 5時時,下界下界

40、2.5nSDS(i,j)+ 5.5(p+q)+3=60.5南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型求解(3) p+q=5,p=1,q=4,t=77;p=2,q=3,t=67;p=3,q=2,t=67p=4,q=1,t=85.5p+q 6時時,下界下界2.5nSDS(i,j)+ 5.5(p+q)+3=66p+q 5時時,t*=62, p+q 6時時,t 66因此因此,最優(yōu)解在最優(yōu)解在p=q=2時取得時取得.南京郵電大學數(shù)理學院楊振華制作 最小乘車時間模型求解Step1 用用Dijkstra算法求出算法求出nSDS(i,j) ,令令h=2;Step2 計算下界計算下界A(h+1,i,j)=

41、2.5nSDS(i,j)+ 5.5(h+1)+3;Step3 p從從1到到h-1循環(huán)循環(huán),q=h-p,計算計算tSDS(i,j,p,q,k,l),對對k,l遍歷求出遍歷求出f(p,h)= min tSDS(i,j,p,q,k,l) | 1k,l39,kl TSDS(i,j,h)=min f(p,r) |2 r h ;Step4 若若TSDS(i,j,h) A(h+1,i,j)停止停止;否則令否則令h:=h+1，轉轉Step3.南京郵電大學數(shù)理學院楊振華制作 求解結果用上述算法用上述算法,針對題中的數(shù)據(jù)進行求解針對題中的數(shù)據(jù)進行求解,除去第除去第二對站點二對站點,計算到計算到p+q=5時可以求出

42、最優(yōu)解時可以求出最優(yōu)解.對第二對站點對第二對站點,可以加大搜索量求得最優(yōu)解可以加大搜索量求得最優(yōu)解.另另外還可以求得更好的下界來壓縮搜索范圍外還可以求得更好的下界來壓縮搜索范圍,比比如考慮起點到整個地鐵線的最小站數(shù)如考慮起點到整個地鐵線的最小站數(shù),這樣這樣M的取值相應的增加的取值相應的增加,從而下界增大從而下界增大.再結合不乘再結合不乘地鐵的情況地鐵的情況,對第二對站點對第二對站點,也只要搜索到也只要搜索到p+q=5就可以了就可以了.南京郵電大學數(shù)理學院楊振華制作 求解結果僅考慮公汽時的求解過程和結果僅考慮公汽時的求解過程和結果點對ts(i,j,m)m*ns(i,j)5(m*+1)+3ns(i,j)T*1234563359182810164697141364641