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

2、S1828(2)S1557S0481(3)S0971S0485(4)S0008S0073(5)S0148S0485(6)S0087S36762、同時(shí)考慮公汽與地鐵線路，解決以上問題。,南京郵電大學(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)記于線路后；

3、其中分段計(jì)價(jià)的票價(jià)為：020站：1元；2140站：2元；40站以上：3元地鐵票價(jià)：3元（無論地鐵線路間是否換乘）注：以上參數(shù)均為簡(jiǎ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-S

4、3524-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ù)理

5、學(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，S0400D1

6、4：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：S06

7、09，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：S19

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

9、考慮公汽線路的情況。設(shè)N表示問題中的公汽站點(diǎn)數(shù),即N=3957,A0(a(i,j,0)NN是直達(dá)最小站數(shù)矩陣，當(dāng)存在公共汽車從站點(diǎn)直達(dá)站點(diǎn)時(shí)，表示從直達(dá)的最小站數(shù)。否則該元素取為+。,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,模型建立,令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é)院楊振華制作yangzhenhua,最小轉(zhuǎn)車次數(shù)模型,對(duì)于給定的公汽站點(diǎn)Si與Sj，最小轉(zhuǎn)車次數(shù)模型可以寫為,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,最小乘車時(shí)間模型,轉(zhuǎn)車次數(shù)為m時(shí)，從Si到Sj

10、的總時(shí)間為5m+3a(i,j,m),（轉(zhuǎn)一次車5分鐘，每乘一站，用時(shí)3分鐘）下面是最小乘車時(shí)間模型：,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,最小乘車費(fèi)用模型,最小乘車費(fèi)用模型可以寫為如下的形式：,該模型是形式上的，對(duì)于求解沒有實(shí)質(zhì)性的作用。,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,最小轉(zhuǎn)車次數(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)車次數(shù)模型求解,算法一（逐次查找）對(duì)于給定的

11、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)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é)院楊振華制作yangzhenhua,最小轉(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,N36.21010,普通計(jì)算機(jī)運(yùn)行時(shí)間較長(zhǎng)，若要轉(zhuǎn)4次車，很難承受計(jì)算量!,南京郵電大學(xué)數(shù)理學(xué)院楊振華

12、制作yangzhenhua,最小轉(zhuǎn)車次數(shù)模型求解,算法二（存儲(chǔ)逐次查找）(1)若a(i,j,0)+,表明轉(zhuǎn)車次數(shù)為0,否則轉(zhuǎn)(2);(2)求出矩陣A1(a(i,j,1)NN,其每個(gè)元素通過上面的表達(dá)式,用k從1到N循環(huán)求得.若對(duì)給定的i,j,有a(i,j,1)1)的計(jì)算工作量與A1一致!有可能計(jì)算轉(zhuǎn)多次車.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,最小轉(zhuǎn)車次數(shù)模型求解,在前面的兩個(gè)算法中,每次循環(huán)都要進(jìn)行N次.事實(shí)上,對(duì)給定的i,滿足a(i,k,0)(B)的時(shí)間,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,地鐵-公汽-地鐵?,設(shè)tDB(i,j)表示乘地鐵由地鐵站Di到地

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

14、,l)最后一個(gè)中括號(hào)中的式子是非負(fù)的.因此TA-TB3nSA(k1,l1)+13-tDB(k1,l1)如果右式非負(fù),則有TA-TB0.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,地鐵-公汽-地鐵?,3nSA(k1,l1)+13-tDB(k1,l1)0?一共有39個(gè)地鐵站,我們通過計(jì)算機(jī)程序（k1,l1對(duì)從1到39進(jìn)行遍歷搜索）來判斷上式左邊的值,發(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-TBtDB(k,k1)+3nSA(k1,l1)+tDB(l1,l)+1

15、3-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-TB0.結(jié)論:對(duì)于題中給的數(shù)據(jù),為了時(shí)間最省,不存在“地鐵-公汽-地鐵”這種換乘方案.換言之:地鐵一次乘完!,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,最小乘車時(shí)間模型,對(duì)于任意兩個(gè)公汽站

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

17、的公汽站乘q公汽次到達(dá)終點(diǎn)公汽站的最短時(shí)間.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,最小乘車時(shí)間模型,(1)站數(shù):N1(i,k,p-1),乘車時(shí)間:3N1(i,k,p-1),轉(zhuǎn)車時(shí)間5(p-1),Si,Dk,Sj,Dl,(1)p次,(3)q次,(3)站數(shù):N2(l,j,q-1),乘車時(shí)間:3N2(l,j,q-1),轉(zhuǎn)車時(shí)間5(q-1),(2),(2)乘車時(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é)院

18、楊振華制作yangzhenhua,最小乘車時(shí)間模型,數(shù)學(xué)模型mintSDS(i,j,p,q,k,l)|1p,q,1k,l39,kl在tSDS(i,j,p,q,k,l)表達(dá)式中,地鐵乘坐時(shí)間tD(k,l)是很容易計(jì)算的.若沒有轉(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é)院楊振華制作yangzhenhua,最小乘車時(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,我們要

19、遍歷p,q,k,l來求上式的最小值.對(duì)于k,l進(jìn)行遍歷是比較簡(jiǎn)單的.為了縮小p,q的取值范圍,可以類似于問題一來給出站數(shù)(公汽與地鐵)的下界.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,下界,設(shè)nSDS(i,j)表示從Si乘車(公汽或地鐵,可以轉(zhuǎn)車任意次)到Sj的最小乘車站數(shù).我們可以用Dijkstra求最短路徑來求出這個(gè)數(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é)院楊振華制作yangzhenhua,下界,將M=N1(i,k,p-1)+N2(l

20、,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

21、(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就得到最小時(shí)間.,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,最小乘車時(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

22、+q3時(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+q4時(shí),下界2.5nSDS(i,j)+5.5(p+q)+3=55,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,最小乘車時(shí)間模型求解,(3)p+q=4,p=1,q=3,t=76;p=2,q=2,t=62;p=3,q=1,t=80.5p+q5時(shí),下界2.5nSDS(i,j)+5.5(p+q)+3=60.5,南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua,最小乘車時(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+q6時(shí),下界2.5nSDS(i,j)+5.5(p+q)+3=66p+q5時(shí),t*=62,p+q6時(shí),t66