版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
公交轉(zhuǎn)車(chē)問(wèn)題南京郵電大學(xué)理學(xué)院楊振華制作yangzhenhua@公交轉(zhuǎn)車(chē)問(wèn)題針對(duì)市場(chǎng)需求,某公司準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決北京市公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)。為了設(shè)計(jì)這樣一個(gè)系統(tǒng),其核心是線路選擇的模型與算法,應(yīng)該從實(shí)際情況出發(fā)考慮,滿足查詢者的各種不同需求。公交:指公共交通工具,包括公共汽車(chē)與地鐵。南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@公交轉(zhuǎn)車(chē)問(wèn)題1、僅考慮公汽線路,給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù),利用你們的模型與算法,求出以下6對(duì)起始站→終到站之間的最佳路線(1)S3359→S1828(2)S1557→S0481(3)S0971→S0485(4)S0008→S0073(5)S0148→S0485(6)S0087→S36762、同時(shí)考慮公汽與地鐵線路,解決以上問(wèn)題。南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@基本參數(shù)設(shè)定相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間):3分鐘相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間):2.5分鐘公汽換乘公汽平均耗時(shí):5分鐘(其中步行時(shí)間2分鐘)地鐵換乘地鐵平均耗時(shí):4分鐘(其中步行時(shí)間2分鐘)地鐵換乘公汽平均耗時(shí):7分鐘(其中步行時(shí)間4分鐘)公汽換乘地鐵平均耗時(shí):6分鐘(其中步行時(shí)間4分鐘)公汽票價(jià):分為單一票價(jià)與分段計(jì)價(jià)兩種,標(biāo)記于線路后;其中分段計(jì)價(jià)的票價(jià)為:0~20站:1元;21~40站:2元;40站以上:3元地鐵票價(jià):3元(無(wú)論地鐵線路間是否換乘)注:以上參數(shù)均為簡(jiǎn)化問(wèn)題而作的假設(shè),未必與實(shí)際數(shù)據(jù)完全吻合。南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@公汽線路信息公汽運(yùn)行方式(1)環(huán)形(2)上下行(有可能上下行路線一致)公汽收費(fèi)方式(1)分段計(jì)價(jià)(2)單一票制1元南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@公汽線路信息文件列出了520條公汽線路,下面是其中的一條:L001分段計(jì)價(jià)。S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710該線路是分段計(jì)價(jià),且上下行路線一致的。南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@地鐵線路信息T1票價(jià)3元,本線路使用,并可換乘T2。D01-D02-D03-D04-D05-D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21-D22-D23T2票價(jià)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é)院楊振華制作yangzhenhua@地鐵T1線換乘公汽信息D01:S0567,S0042,S0025D02:S1487D03:S0303,S0302D04:S0566D05:S0436,S0438,S0437,S0435D06:S0392,S0394,S0393,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,S1919,S1921,S1920D21:S0465,S0467,S0466,S0464D22:S3457D23:S2512南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@地鐵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,S0498D18:S0668D33:S1894,S1896,S1895D34:S1104,S0576,S0578,S0577D35:S3010,S0583,S0582D36:S3676,S0427,S0061,S0060D37:S1961,S2817,S0455,S0456D38:S3262,S0622D39:S1956,S0289,S0291南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@問(wèn)題分析從實(shí)際情況考慮,不同的查詢者有不同的要求。在數(shù)學(xué)上體現(xiàn)出目標(biāo)的不同。一般可以考慮轉(zhuǎn)車(chē)次數(shù)、乘車(chē)費(fèi)用、乘車(chē)時(shí)間這3個(gè)目標(biāo)。問(wèn)題可以歸結(jié)為多目標(biāo)優(yōu)化問(wèn)題。南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@問(wèn)題分析如何處理上面的多個(gè)目標(biāo)?多目標(biāo)的處理最常用的方法是單目標(biāo)化,即采用加權(quán)平均等方法將多個(gè)目標(biāo)結(jié)合形成一個(gè)單一的目標(biāo)。本問(wèn)題中,單目標(biāo)化并不合適,比較適當(dāng)?shù)姆椒ㄊ菍?duì)每個(gè)目標(biāo)尋求最佳線路,然后讓乘客按照自己的需求進(jìn)行選擇。南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@模型建立我們先僅考慮公汽線路的情況。設(shè)N表示問(wèn)題中的公汽站點(diǎn)數(shù),即N=3957,A0=(a(i,j,0))N×N是直達(dá)最小站數(shù)矩陣,當(dāng)存在公共汽車(chē)從站點(diǎn)直達(dá)站點(diǎn)時(shí),表示從直達(dá)的最小站數(shù)。否則該元素取為+∞。南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@模型建立令A(yù)m=(a(i,j,m))N×N是m次轉(zhuǎn)乘最小站數(shù)矩陣,其元素a(i,j,m)表示m次轉(zhuǎn)車(chē)情形下,從Si到Sj的最小站數(shù)。顯然南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小轉(zhuǎn)車(chē)次數(shù)模型對(duì)于給定的公汽站點(diǎn)Si與Sj,最小轉(zhuǎn)車(chē)次數(shù)模型可以寫(xiě)為南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型轉(zhuǎn)車(chē)次數(shù)為m時(shí),從Si到Sj的總時(shí)間為5m+3a(i,j,m),(轉(zhuǎn)一次車(chē)5分鐘,每乘一站,用時(shí)3分鐘)下面是最小乘車(chē)時(shí)間模型:南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)費(fèi)用模型最小乘車(chē)費(fèi)用模型可以寫(xiě)為如下的形式:該模型是形式上的,對(duì)于求解沒(méi)有實(shí)質(zhì)性的作用。南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小轉(zhuǎn)車(chē)次數(shù)模型求解對(duì)于給定的公汽站點(diǎn)Si與Sj,只要逐次求出(a(i,j,m)),直到其為有限值即可。在實(shí)際求解時(shí),先根據(jù)公汽線路的數(shù)據(jù)將a(i,j,0)的數(shù)據(jù)存儲(chǔ)在矩陣A0中。南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小轉(zhuǎn)車(chē)次數(shù)模型求解算法一(逐次查找)對(duì)于給定的i,j,(1)若a(i,j,0)<+∞,表明轉(zhuǎn)車(chē)次數(shù)為0,否則轉(zhuǎn)(2);(2)k從1到N進(jìn)行搜索,若a(i,k,0)<+∞,a(k,j,0)<+∞,則轉(zhuǎn)車(chē)次數(shù)為1,否則轉(zhuǎn)(3);(3)k1,k2從1到N進(jìn)行搜索,若a(i,k1,0)<+∞,a(k1,k2,0)<+∞,a(k2,j,0)<+∞,則轉(zhuǎn)車(chē)次數(shù)為2.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小轉(zhuǎn)車(chē)次數(shù)模型求解逐次查找算法的復(fù)雜度若只要轉(zhuǎn)一次車(chē),則循環(huán)的步數(shù)為N;若要轉(zhuǎn)2次車(chē),循環(huán)的步數(shù)為N2;若要轉(zhuǎn)3次車(chē),循環(huán)的步數(shù)為N3……由于N=3957,N3≈6.2×1010,普通計(jì)算機(jī)運(yùn)行時(shí)間較長(zhǎng),若要轉(zhuǎn)4次車(chē),很難承受計(jì)算量!南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小轉(zhuǎn)車(chē)次數(shù)模型求解算法二(存儲(chǔ)逐次查找)(1)若a(i,j,0)<+∞,表明轉(zhuǎn)車(chē)次數(shù)為0,否則轉(zhuǎn)(2);(2)求出矩陣A1=(a(i,j,1))N×N,其每個(gè)元素通過(guò)上面的表達(dá)式,用k從1到N循環(huán)求得.若對(duì)給定的i,j,有a(i,j,1)<+∞,表明轉(zhuǎn)車(chē)次數(shù)為1;類似可以計(jì)算多次轉(zhuǎn)車(chē)的情況注:矩陣A0,A1等計(jì)算后存儲(chǔ)在計(jì)算機(jī)中,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小轉(zhuǎn)車(chē)次數(shù)模型求解存儲(chǔ)逐次查找算法的復(fù)雜度矩陣A1的計(jì)算:一共計(jì)算N2個(gè)元素,每個(gè)元素的計(jì)算要循環(huán)N步,計(jì)算量為N3.運(yùn)行時(shí)間依然較長(zhǎng)。優(yōu)點(diǎn):矩陣Am(m>1)的計(jì)算工作量與A1一致!有可能計(jì)算轉(zhuǎn)多次車(chē).南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小轉(zhuǎn)車(chē)次數(shù)模型求解在前面的兩個(gè)算法中,每次循環(huán)都要進(jìn)行N次.事實(shí)上,對(duì)給定的i,滿足a(i,k,0)<+∞的k是很少的,我們只要對(duì)這些k進(jìn)行循環(huán).在實(shí)際問(wèn)題中,任何一個(gè)城市中,任何一個(gè)公汽站點(diǎn)所能到達(dá)的公汽站點(diǎn)只是城市中的一些“線”,相對(duì)于整個(gè)城市而言,數(shù)目是比較少的.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小轉(zhuǎn)車(chē)次數(shù)模型求解算法三(有限搜索逐次查找)給出矩陣B,其第i行記錄的是滿足a(i,k,0)<+∞的所有的“k”.將存儲(chǔ)逐次查找算法中的k從1到N循環(huán)改為正對(duì)矩陣B第i行中的“k”進(jìn)行循環(huán).南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小轉(zhuǎn)車(chē)次數(shù)模型求解有限搜索逐次查找算法的復(fù)雜度矩陣Am的計(jì)算:一共計(jì)算N2個(gè)元素,每個(gè)元素的計(jì)算要循環(huán)的步數(shù)大大小于N,大約為N/10,計(jì)算量約為N3/10.一般的計(jì)算機(jī)可以實(shí)現(xiàn).南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小轉(zhuǎn)車(chē)次數(shù)模型求解對(duì)于題目中給出的六組公汽站點(diǎn),其最小轉(zhuǎn)車(chē)次數(shù)分別為(1)S3359→S1828 1(2)S1557→S0481 2(3)S0971→S0485 1(4)S0008→S0073 1(5)S0148→S0485 2(6)S0087→S3676 1南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@轉(zhuǎn)車(chē)次數(shù)由于算法復(fù)雜性的問(wèn)題,許多參賽隊(duì)都假設(shè)“最多轉(zhuǎn)2次車(chē)”,少數(shù)參賽隊(duì)考慮轉(zhuǎn)3次車(chē),個(gè)別的參賽隊(duì)考慮轉(zhuǎn)4次車(chē)或更多.由于所給的6組站點(diǎn)最小轉(zhuǎn)車(chē)次數(shù)為1或2,似乎假設(shè)最多轉(zhuǎn)2次車(chē)是合理的.根據(jù)題目中的數(shù)據(jù),北京市的任意兩個(gè)公汽站點(diǎn)之間一般需轉(zhuǎn)幾次車(chē)?南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@轉(zhuǎn)車(chē)次數(shù)N=3957,一共有N(N-1)
=15653892對(duì)公汽站點(diǎn),我們給出它們的最小轉(zhuǎn)車(chē)次數(shù)轉(zhuǎn)車(chē)次數(shù)站點(diǎn)對(duì)數(shù)03965351587599328274263310866064203855110根據(jù)題目中的數(shù)據(jù),北京市的公汽站點(diǎn)轉(zhuǎn)5次車(chē)可以全部到達(dá).根據(jù)表中的數(shù)據(jù),假設(shè)轉(zhuǎn)最多2次車(chē)是不合理的,假設(shè)轉(zhuǎn)最多3次車(chē)有一定的合理性.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)費(fèi)用左邊的表給出的時(shí)最小轉(zhuǎn)車(chē)次數(shù),即對(duì)應(yīng)的一種乘車(chē)方案的乘車(chē)費(fèi)用.點(diǎn)對(duì)換乘次數(shù)費(fèi)用(元)S3359→S182813S1557→S048123S0971→S048513S0008→S007312S0148→S048523S0087→S367612關(guān)于最小乘車(chē)費(fèi)用,其模型一般只有形式上的,對(duì)求解沒(méi)有直接的作用.我們對(duì)具體的六對(duì)站點(diǎn)給出討論的結(jié)果.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)費(fèi)用易見(jiàn),第二,四,五,六對(duì)站點(diǎn)對(duì)應(yīng)的費(fèi)用是最小費(fèi)用(為什么?)點(diǎn)對(duì)換乘次數(shù)費(fèi)用(元)S3359→S182813S1557→S048123S0971→S048513S0008→S007312S0148→S048523S0087→S367612南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)費(fèi)用對(duì)于第一個(gè)點(diǎn)對(duì)S3359→S1828,如果換乘次數(shù)大于等于2,顯然費(fèi)用至少為3.若換乘次數(shù)為1,采用枚舉方法將乘車(chē)方案全部列出.一共由9種方案,其中8種費(fèi)用為3元,一種費(fèi)用為4元.因此,最小乘車(chē)費(fèi)用為3.類似,第三個(gè)點(diǎn)對(duì)的換乘次數(shù)為1的11種方案的最小費(fèi)用也是3.點(diǎn)對(duì)換乘次數(shù)費(fèi)用(元)S3359→S182813S0971→S048513南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型求解根據(jù)上面的模型,若已知a(i,j,m)的值,則可以求出tS(i,j,m)關(guān)于m的最小值.由于m的取值從0到無(wú)窮大,必須采用一定的技巧來(lái)求出最小值.注:參賽隊(duì)一般選取m從0到2(或0到3),是不合理的,不過(guò)也“成功”避免了求解的困難.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型求解考慮第一對(duì)公汽站點(diǎn)1)S3359→S1828最小轉(zhuǎn)車(chē)次數(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.若m≥13,則tS(i,j,m)≥105>tS(i,j,1).因此,我們可以將m的范圍放在0到12內(nèi)求最優(yōu).南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型求解若m的范圍過(guò)大,求解會(huì)有一定困難.能否縮小m的范圍?在上頁(yè)的討論中,不等式a(i,j,m)≥m+1的含義是總站數(shù)比轉(zhuǎn)車(chē)次數(shù)至少大一.我們可以給出a(i,j,m)更好的下界,從而縮小m的范圍.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@兩站點(diǎn)之間的最小站數(shù)a(i,j,m)表示m次轉(zhuǎn)車(chē)下,從Si到Sj的最小站數(shù).設(shè)nS(i,j)表示站點(diǎn)Si到Sj的最小站數(shù)(可以轉(zhuǎn)車(chē)任意次).顯然 a(i,j,m)≥nS(i,j)我們有tS(i,j,m) =5m+3a(i,j,m)
≥5m+3nS(i,j)南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@兩站點(diǎn)之間的最小站數(shù)將公汽站點(diǎn)設(shè)為有向圖中的結(jié)點(diǎn).若Si乘公汽1站可以到達(dá)Sj,我們就設(shè)一條有向邊從結(jié)點(diǎn)i指向結(jié)點(diǎn)j.對(duì)于每一條有向邊,指定其權(quán)為1,顯然求nS(i,j)就轉(zhuǎn)化為有向圖中結(jié)點(diǎn)到結(jié)點(diǎn)的最短路徑問(wèn)題.對(duì)任意給定的i,j,我們可以采用Dijkstra算法求得nS(i,j).南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型求解對(duì)于第一對(duì)公汽站點(diǎn)i=3359,j=1828,nS(i,j)=13,我們給出求解過(guò)程.a(i,j,0)=∞,tS(i,j,0)=∞;a(i,j,1)=32,tS(i,j,1)=101; m
≥2時(shí),tS(i,j,m)≥5×2+3×13=49.因此,最小乘車(chē)時(shí)間在區(qū)間[49,101]上.為求精確的最優(yōu)解,必須接著求解.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型求解a(i,j,2)=18,tS(i,j,2)=64; m
≥3時(shí),tS(i,j,m)≥5×3+3×13=54.最優(yōu)解位于區(qū)間[54,64];a(i,j,3)=18,tS(i,j,3)=69; m
≥4時(shí),tS(i,j,m)≥5×4+3×13=59.最優(yōu)解位于區(qū)間[59,64];南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型求解a(i,j,4)=17,tS(i,j,4)=71; m
≥5時(shí),tS(i,j,m)≥5×5+3×13=64.重復(fù)上述過(guò)程: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時(shí),tS(i,j,m)≥64.可以看出,最小乘車(chē)時(shí)間為64,在轉(zhuǎn)2次車(chē)時(shí)可以在此時(shí)間到達(dá).南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型求解算法由上面的例子,我們只要找到一個(gè)轉(zhuǎn)車(chē)次數(shù)m,轉(zhuǎn)車(chē)次數(shù)不大于m時(shí),最小乘車(chē)時(shí)間為T(mén)S(i,j,m)=min{tS(i,j,k)|k≤m}轉(zhuǎn)車(chē)次數(shù)大于m時(shí),乘車(chē)時(shí)間的下界為5(m+1)+3nS(i,j)若TS(i,j,m)≤5(m+1)+3nS(i,j),則TS(i,j,m)為最優(yōu)解.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型求解算法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)=min{tS(i,j,k)|k≤m}≤5(m+1)+3nS(i,j),則TS(i,j,m)即為最短乘車(chē)時(shí)間;否則令m:=m+1,轉(zhuǎn)Step2.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型求解第四對(duì)公汽站點(diǎn)S0008-S0073的求解過(guò)程可以用下面的表格表示(nS(i,j)=13):m01234ts(i,j,m)∞83676359Ts(i,j,m)∞836763595(m+1)+3ns(i,j)
4449545964最小乘車(chē)時(shí)間為59,需轉(zhuǎn)4次車(chē).其它答案參見(jiàn)評(píng)閱要點(diǎn)(該要點(diǎn)給出的答案中包含了起始的3分鐘)南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@綜合考慮公汽與地鐵(1)最小轉(zhuǎn)車(chē)次數(shù)將地鐵線路看成公汽線路.最小轉(zhuǎn)車(chē)次數(shù)這一目標(biāo)的討論難度沒(méi)有增加,只是增加了幾條公汽線路.對(duì)于題中給的六組站點(diǎn),其前5組站點(diǎn)都不在地鐵邊,因此增加地鐵后,最小乘車(chē)次數(shù)沒(méi)有變化,仍然是原來(lái)的1或2.第6組2個(gè)站點(diǎn)都在地鐵線上,最小轉(zhuǎn)乘次數(shù)為0.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@綜合考慮公汽與地鐵(2)最小乘車(chē)費(fèi)用對(duì)于一般的兩個(gè)站點(diǎn)之間的最小乘車(chē)費(fèi)用,僅考慮公汽時(shí)討論就很復(fù)雜,增加了地鐵之后討論還是差不多復(fù)雜,要用枚舉法來(lái)求解.也可以說(shuō),難度沒(méi)有增加.對(duì)于題中給的六組站點(diǎn),僅考慮公汽時(shí),最小費(fèi)用為2元或3元,因此在綜合考慮公汽與地鐵時(shí)依然是最優(yōu)解(乘一次地鐵3元)南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@綜合考慮公汽與地鐵(3)最小乘車(chē)時(shí)間增加了地鐵后乘車(chē)時(shí)間的討論變得相當(dāng)復(fù)雜.注:如果假設(shè)換成次數(shù)最多為2或3,會(huì)將問(wèn)題大大簡(jiǎn)化.在此,為了將問(wèn)題合理的簡(jiǎn)化,我們首先研究這樣一個(gè)問(wèn)題:在考慮時(shí)間最少時(shí),線路中是否存在先乘地鐵,再轉(zhuǎn)公汽,再乘地鐵這樣的乘車(chē)方案?南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@地鐵-公汽-地鐵?考察下面兩種方案(A)從地鐵站Dk乘地鐵到地鐵站Dk1然后由公汽站Ss1乘到公汽站Ss2,再轉(zhuǎn)地鐵站Dl1,乘地鐵到地鐵站Dl;(B)直接乘地鐵由地鐵站Dk到Dl。直觀認(rèn)識(shí):(A)的時(shí)間>(B)的時(shí)間南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@地鐵-公汽-地鐵?設(shè)tDB(i,j)表示乘地鐵由地鐵站Di到地鐵站Dj的最短時(shí)間,nSA(i,j)表示可以由地鐵站Di轉(zhuǎn)乘的公汽站乘公汽到可以由地鐵站Dj轉(zhuǎn)乘的公汽站的最小公汽站數(shù)。于是,TB=tDB(k,l)如果(A)方案中沒(méi)有公汽轉(zhuǎn)車(chē)TA=tDB(k,k1)+3nSA(k1,l1)+tDB(l1,l)+1313表示換車(chē)時(shí)間如果有公汽轉(zhuǎn)車(chē),等號(hào)要換成大于等于號(hào)南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@地鐵-公汽-地鐵?TA-TB
≥
tDB(k,k1)+3nSA(k1,l1)+tDB(l1,l)+13-tDB(k,l)=[3nSA(k1,l1)+13-tDB(k1,l1)]+[tDB(k,k1)+tDB(k1,l1)+tDB(l1,l)-tDB(k,l)]最后一個(gè)中括號(hào)中的式子是非負(fù)的.因此TA-TB
≥3nSA(k1,l1)+13-tDB(k1,l1)如果右式非負(fù),則有TA-TB
≥0.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@地鐵-公汽-地鐵?3nSA(k1,l1)+13-tDB(k1,l1)≥0?一共有39個(gè)地鐵站,我們通過(guò)計(jì)算機(jī)程序(k1,l1對(duì)從1到39進(jìn)行遍歷搜索)來(lái)判斷上式左邊的值,發(fā)現(xiàn)有四組地鐵站對(duì)應(yīng)的值為負(fù),分別是(13,30),(16,30),(30,15),(30,16),這四組站點(diǎn)對(duì)應(yīng)的nSA(k1,l1)值均為1.對(duì)這四組點(diǎn),再觀察TA-TB
≥
tDB(k,k1)+3nSA(k1,l1)+tDB(l1,l)+13-tDB(k,l)右端的值南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@地鐵-公汽-地鐵?tDB(k,k1)+3nSA(k1,l1)+tDB(l1,l)+13-tDB(k,l)=tDB(k,k1)+tDB(l1,l)+16-tDB(k,l)對(duì)于前面四組k1,l1,對(duì)k,l進(jìn)行循環(huán)搜索,可以得到tDB(k,k1)+tDB(l1,l)+16-tDB(k,l)的最小值都是2.最終得到TA-TB
≥0.結(jié)論:對(duì)于題中給的數(shù)據(jù),為了時(shí)間最省,不存在“地鐵-公汽-地鐵”這種換乘方案.換言之:地鐵一次乘完!南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型對(duì)于任意兩個(gè)公汽站點(diǎn),不乘地鐵的時(shí)間最小方案在問(wèn)題一中已經(jīng)求得.下面考慮必須乘地鐵的方案:乘p次(轉(zhuǎn)p-1次)公汽,再乘地鐵,最后乘次q(轉(zhuǎn)q-1次)公汽到達(dá)終點(diǎn)的方案,下面將這樣的方案記為pDq。注:該方案包含了僅乘地鐵的情況(p=q=0).南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型下面主要針對(duì)題中前5組站點(diǎn)進(jìn)行研究.這五組站點(diǎn)均不能由地鐵站直接轉(zhuǎn)乘,因此p,q≥1.求任意公汽站點(diǎn)Si到公汽站點(diǎn)Sj在方案下的最短時(shí)間,即對(duì)任意的p,q,以及任意的地鐵站Dk,Dl,求出起點(diǎn)乘p次公汽到可以直接轉(zhuǎn)乘地鐵站Dk的公汽站的最短時(shí)間,加上Dk到Dl的最短時(shí)間,再加上可以由地鐵站Dl直接轉(zhuǎn)乘的公汽站乘q公汽次到達(dá)終點(diǎn)公汽站的最短時(shí)間.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型(1)站數(shù):N1(i,k,p-1),乘車(chē)時(shí)間:3N1(i,k,p-1),轉(zhuǎn)車(chē)時(shí)間5(p-1)SiDkSjDl(1)p次(3)q次(3)站數(shù):N2(l,j,q-1),乘車(chē)時(shí)間:3N2(l,j,q-1),轉(zhuǎn)車(chē)時(shí)間5(q-1)(2)(2)乘車(chē)時(shí)間:tD(k,l)(4)公汽轉(zhuǎn)地鐵,地鐵轉(zhuǎn)公汽時(shí)間:13總時(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南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型數(shù)學(xué)模型min{tSDS(i,j,p,q,k,l)|1≤p,q<∞,1≤k,l≤39,k≠l}在tSDS(i,j,p,q,k,l)表達(dá)式中,地鐵乘坐時(shí)間tD(k,l)是很容易計(jì)算的.若沒(méi)有轉(zhuǎn)車(chē),tD(k,l)=2.5nD(k,l)(每站2.5分鐘)若轉(zhuǎn)1次車(chē),tD(k,l)=2.5nD(k,l)+4.不存在轉(zhuǎn)2次以上的情況.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(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對(duì)于固定的i,j,我們要遍歷p,q,k,l來(lái)求上式的最小值.對(duì)于k,l進(jìn)行遍歷是比較簡(jiǎn)單的.為了縮小p,q的取值范圍,可以類似于問(wèn)題一來(lái)給出站數(shù)(公汽與地鐵)的下界.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@下界設(shè)nSDS(i,j)表示從Si乘車(chē)(公汽或地鐵,可以轉(zhuǎn)車(chē)任意次)到Sj的最小乘車(chē)站數(shù).我們可以用Dijkstra求最短路徑來(lái)求出這個(gè)數(shù).記M=N1(i,k,p-1)+N2(l,j,q-1)為乘車(chē)方案中公汽的站數(shù).根據(jù)公汽的站數(shù)加地鐵站數(shù)不小于最小乘車(chē)站數(shù),有M+nD(k,l)≥nSDS(i,j).南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@下界將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)南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@下界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ù),顯然M≥p+q,(一共乘了p+q次公汽,每次至少一站).我們最終得到tSDS(i,j,p,q,k,l)≥2.5nSDS(i,j)+5.5(p+q)+3根據(jù)這一下界,搜索不多的p,q就得到最小時(shí)間.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型求解對(duì)第一個(gè)點(diǎn)對(duì),i=3359,j=1828,nSDS(i,j)=12(由于增加了地鐵,最小站數(shù)小了).(1)p+q=2,p=1,q=1t=84.5,p+q
≥3時(shí),下界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時(shí),下界2.5nSDS(i,j)+5.5(p+q)+3=55南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(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時(shí),下界2.5nSDS(i,j)+5.5(p+q)+3=60.5南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(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時(shí),下界2.5nSDS(i,j)+5.5(p+q)+3=66p+q≤5時(shí),t*=62,p+q
≥6時(shí),t≥66因此,最優(yōu)解在p=q=2時(shí)取得.南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua@最小乘車(chē)時(shí)間模型求解Step1用Dijkstra算法求出nSDS(i,j),令h=2;Step2計(jì)算下界 A(h+1,i,j)=2.5nSDS(i,j)+5.5(h+1)+3;Step3p從1到h-1循環(huán),q=h-p,計(jì)算tSDS(i,j,p,q,k,l),對(duì)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 總裝技能提升練習(xí)卷附答案
- 專升本金融基礎(chǔ)知識(shí)題庫(kù)單選題100道及答案解析
- 平安校園創(chuàng)建會(huì)議記錄
- 語(yǔ)文統(tǒng)編版(2024)一年級(jí)上冊(cè)第一單元快樂(lè)讀書(shū)吧 教案
- 高中英語(yǔ)語(yǔ)法復(fù)習(xí)之構(gòu)詞法
- 高中英語(yǔ)語(yǔ)法大全 精講教程
- 第1章 信息系統(tǒng)基礎(chǔ)課件
- 2024屆上海市風(fēng)華中學(xué)高三下學(xué)期三校五測(cè)數(shù)學(xué)試題試卷
- 4.3 多邊形和圓的初步認(rèn)識(shí) 北師版七年級(jí)上冊(cè)數(shù)學(xué)課件
- 三年級(jí) 美麗的小興安嶺說(shuō)課稿
- Unit 3 What would you like?Part A(教學(xué)設(shè)計(jì))-2023-2024學(xué)年人教PEP版英語(yǔ)五年級(jí)上冊(cè)
- 2024入團(tuán)知識(shí)題庫(kù)(含答案)
- 25題戰(zhàn)略規(guī)劃崗位常見(jiàn)面試問(wèn)題含HR問(wèn)題考察點(diǎn)及參考回答
- 中外政治思想史-形成性測(cè)試三-國(guó)開(kāi)(HB)-參考資料
- 中華民族共同體概論課件專家版9第九講 混一南北和中華民族大統(tǒng)合(元朝時(shí)期)
- 電梯日管控、周排查、月調(diào)度內(nèi)容表格
- 個(gè)人理財(cái)理論與實(shí)務(wù)李杰輝課后參考答案
- HCCDP 云遷移認(rèn)證理論題庫(kù)
- 《戰(zhàn)爭(zhēng)與和平法》讀書(shū)筆記思維導(dǎo)圖
- 人防工程設(shè)計(jì)課件(75頁(yè)P(yáng)PT)
- (完整版)六宮格數(shù)獨(dú)100題
評(píng)論
0/150
提交評(píng)論