公交轉車問題南京郵電大學理學院楊振華制作yangzhenhua@公交轉車問題針對市場需求，某公司準備研制開發一個解決北京市公交線路選擇問題的自主查詢計算機系統。為了設計這樣一個系統，其核心是線路選擇的模型與算法，應該從實際情況出發考慮，滿足查詢者的各種不同需求。公交：指公共交通工具，包括公共汽車與地鐵。南京郵電大學數理學院楊振華制作yangzhenhua@公交轉車問題1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數學模型與算法。并根據附錄數據，利用你們的模型與算法，求出以下6對起始站→終到站之間的最佳路線(1)S3359→S1828(2)S1557→S0481(3)S0971→S0485(4)S0008→S0073(5)S0148→S0485(6)S0087→S36762、同時考慮公汽與地鐵線路，解決以上問題。南京郵電大學數理學院楊振華制作yangzhenhua@基本參數設定相鄰公汽站平均行駛時間(包括停站時間)：3分鐘相鄰地鐵站平均行駛時間(包括停站時間)：2.5分鐘公汽換乘公汽平均耗時：5分鐘(其中步行時間2分鐘)地鐵換乘地鐵平均耗時：4分鐘(其中步行時間2分鐘)地鐵換乘公汽平均耗時：7分鐘(其中步行時間4分鐘)公汽換乘地鐵平均耗時：6分鐘(其中步行時間4分鐘)公汽票價：分為單一票價與分段計價兩種，標記于線路后；其中分段計價的票價為：0～20站：1元；21～40站：2元；40站以上：3元地鐵票價：3元（無論地鐵線路間是否換乘）注：以上參數均為簡化問題而作的假設，未必與實際數據完全吻合。南京郵電大學數理學院楊振華制作yangzhenhua@公汽線路信息公汽運行方式（1）環形（2）上下行（有可能上下行路線一致）公汽收費方式（1）分段計價（2）單一票制1元南京郵電大學數理學院楊振華制作yangzhenhua@公汽線路信息文件列出了520條公汽線路，下面是其中的一條：L001分段計價。S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710該線路是分段計價，且上下行路線一致的。南京郵電大學數理學院楊振華制作yangzhenhua@地鐵線路信息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-D23T2票價3元，本線路使用，并可換乘T1。環行：D24-D25-D26-D12-D27-D28-D29-D30-D31-D32-D18-D33-D34-D35-D36-D37-D38-D39-D24南京郵電大學數理學院楊振華制作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南京郵電大學數理學院楊振華制作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南京郵電大學數理學院楊振華制作yangzhenhua@問題分析從實際情況考慮，不同的查詢者有不同的要求。在數學上體現出目標的不同。一般可以考慮轉車次數、乘車費用、乘車時間這3個目標。問題可以歸結為多目標優化問題。南京郵電大學數理學院楊振華制作yangzhenhua@問題分析如何處理上面的多個目標？多目標的處理最常用的方法是單目標化，即采用加權平均等方法將多個目標結合形成一個單一的目標。本問題中，單目標化并不合適，比較適當的方法是對每個目標尋求最佳線路，然后讓乘客按照自己的需求進行選擇。南京郵電大學數理學院楊振華制作yangzhenhua@模型建立我們先僅考慮公汽線路的情況。設N表示問題中的公汽站點數,即N=3957,A0＝(a(i,j,0))N×N是直達最小站數矩陣，當存在公共汽車從站點直達站點時，表示從直達的最小站數。否則該元素取為+∞。南京郵電大學數理學院楊振華制作yangzhenhua@模型建立令Am＝(a(i,j,m))N×N是m次轉乘最小站數矩陣，其元素a(i,j,m)表示m次轉車情形下，從Si到Sj的最小站數。顯然南京郵電大學數理學院楊振華制作yangzhenhua@最小轉車次數模型對于給定的公汽站點Si與Sj，最小轉車次數模型可以寫為南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型轉車次數為m時，從Si到Sj的總時間為5m+3a(i,j,m),（轉一次車5分鐘，每乘一站，用時3分鐘）下面是最小乘車時間模型：南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車費用模型最小乘車費用模型可以寫為如下的形式：該模型是形式上的，對于求解沒有實質性的作用。南京郵電大學數理學院楊振華制作yangzhenhua@最小轉車次數模型求解對于給定的公汽站點Si與Sj，只要逐次求出(a(i,j,m))，直到其為有限值即可。在實際求解時，先根據公汽線路的數據將a(i,j,0)的數據存儲在矩陣A0中。南京郵電大學數理學院楊振華制作yangzhenhua@最小轉車次數模型求解算法一（逐次查找）對于給定的i,j,(1)若a(i,j,0)<+∞,表明轉車次數為0,否則轉(2);(2)k從1到N進行搜索,若a(i,k,0)<+∞,a(k,j,0)<+∞,則轉車次數為1,否則轉(3);(3)k1,k2從1到N進行搜索,若a(i,k1,0)<+∞,a(k1,k2,0)<+∞,a(k2,j,0)<+∞,則轉車次數為2.南京郵電大學數理學院楊振華制作yangzhenhua@最小轉車次數模型求解逐次查找算法的復雜度若只要轉一次車,則循環的步數為N;若要轉2次車,循環的步數為N2;若要轉3次車,循環的步數為N3……由于N=3957,N3≈6.2×1010,普通計算機運行時間較長，若要轉4次車，很難承受計算量!南京郵電大學數理學院楊振華制作yangzhenhua@最小轉車次數模型求解算法二（存儲逐次查找）(1)若a(i,j,0)<+∞,表明轉車次數為0,否則轉(2);(2)求出矩陣A1＝(a(i,j,1))N×N,其每個元素通過上面的表達式,用k從1到N循環求得.若對給定的i,j,有a(i,j,1)<+∞,表明轉車次數為1;類似可以計算多次轉車的情況注:矩陣A0,A1等計算后存儲在計算機中,南京郵電大學數理學院楊振華制作yangzhenhua@最小轉車次數模型求解存儲逐次查找算法的復雜度矩陣A1的計算:一共計算N2個元素,每個元素的計算要循環N步,計算量為N3.運行時間依然較長。優點：矩陣Am(m>1)的計算工作量與A1一致!有可能計算轉多次車.南京郵電大學數理學院楊振華制作yangzhenhua@最小轉車次數模型求解在前面的兩個算法中,每次循環都要進行N次.事實上,對給定的i,滿足a(i,k,0)<+∞的k是很少的,我們只要對這些k進行循環.在實際問題中,任何一個城市中,任何一個公汽站點所能到達的公汽站點只是城市中的一些“線”,相對于整個城市而言,數目是比較少的.南京郵電大學數理學院楊振華制作yangzhenhua@最小轉車次數模型求解算法三（有限搜索逐次查找）給出矩陣B,其第i行記錄的是滿足a(i,k,0)<+∞的所有的“k”.將存儲逐次查找算法中的k從1到N循環改為正對矩陣B第i行中的“k”進行循環.南京郵電大學數理學院楊振華制作yangzhenhua@最小轉車次數模型求解有限搜索逐次查找算法的復雜度矩陣Am的計算:一共計算N2個元素,每個元素的計算要循環的步數大大小于N,大約為N/10,計算量約為N3/10.一般的計算機可以實現.南京郵電大學數理學院楊振華制作yangzhenhua@最小轉車次數模型求解對于題目中給出的六組公汽站點,其最小轉車次數分別為(1)S3359→S1828 1(2)S1557→S0481 2(3)S0971→S0485 1(4)S0008→S0073 1(5)S0148→S0485 2(6)S0087→S3676 1南京郵電大學數理學院楊振華制作yangzhenhua@轉車次數由于算法復雜性的問題,許多參賽隊都假設“最多轉2次車”,少數參賽隊考慮轉3次車,個別的參賽隊考慮轉4次車或更多.由于所給的6組站點最小轉車次數為1或2,似乎假設最多轉2次車是合理的.根據題目中的數據,北京市的任意兩個公汽站點之間一般需轉幾次車?南京郵電大學數理學院楊振華制作yangzhenhua@轉車次數N=3957,一共有N(N-1)

=15653892對公汽站點,我們給出它們的最小轉車次數轉車次數站點對數03965351587599328274263310866064203855110根據題目中的數據,北京市的公汽站點轉5次車可以全部到達.根據表中的數據,假設轉最多2次車是不合理的,假設轉最多3次車有一定的合理性.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車費用左邊的表給出的時最小轉車次數,即對應的一種乘車方案的乘車費用.點對換乘次數費用（元）S3359→S182813S1557→S048123S0971→S048513S0008→S007312S0148→S048523S0087→S367612關于最小乘車費用,其模型一般只有形式上的,對求解沒有直接的作用.我們對具體的六對站點給出討論的結果.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車費用易見,第二,四,五,六對站點對應的費用是最小費用(為什么?)點對換乘次數費用（元）S3359→S182813S1557→S048123S0971→S048513S0008→S007312S0148→S048523S0087→S367612南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車費用對于第一個點對S3359→S1828,如果換乘次數大于等于2,顯然費用至少為3.若換乘次數為1,采用枚舉方法將乘車方案全部列出.一共由9種方案,其中8種費用為3元,一種費用為4元.因此,最小乘車費用為3.類似,第三個點對的換乘次數為1的11種方案的最小費用也是3.點對換乘次數費用（元）S3359→S182813S0971→S048513南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解根據上面的模型,若已知a(i,j,m)的值,則可以求出tS(i,j,m)關于m的最小值.由于m的取值從0到無窮大,必須采用一定的技巧來求出最小值.注:參賽隊一般選取m從0到2(或0到3),是不合理的,不過也“成功”避免了求解的困難.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解考慮第一對公汽站點1)S3359→S1828最小轉車次數為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內求最優.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解若m的范圍過大,求解會有一定困難.能否縮小m的范圍?在上頁的討論中,不等式a(i,j,m)≥m+1的含義是總站數比轉車次數至少大一.我們可以給出a(i,j,m)更好的下界,從而縮小m的范圍.南京郵電大學數理學院楊振華制作yangzhenhua@兩站點之間的最小站數a(i,j,m)表示m次轉車下,從Si到Sj的最小站數.設nS(i,j)表示站點Si到Sj的最小站數(可以轉車任意次).顯然 a(i,j,m)≥nS(i,j)我們有tS(i,j,m) =5m+3a(i,j,m)

≥5m+3nS(i,j)南京郵電大學數理學院楊振華制作yangzhenhua@兩站點之間的最小站數將公汽站點設為有向圖中的結點.若Si乘公汽1站可以到達Sj,我們就設一條有向邊從結點i指向結點j.對于每一條有向邊,指定其權為1,顯然求nS(i,j)就轉化為有向圖中結點到結點的最短路徑問題.對任意給定的i,j,我們可以采用Dijkstra算法求得nS(i,j).南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解對于第一對公汽站點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)≥5×2+3×13=49.因此,最小乘車時間在區間[49,101]上.為求精確的最優解,必須接著求解.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解a(i,j,2)=18,tS(i,j,2)=64; m

≥3時,tS(i,j,m)≥5×3+3×13=54.最優解位于區間[54,64];a(i,j,3)=18,tS(i,j,3)=69; m

≥4時,tS(i,j,m)≥5×4+3×13=59.最優解位于區間[59,64];南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解a(i,j,4)=17,tS(i,j,4)=71; m

≥5時,tS(i,j,m)≥5×5+3×13=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.可以看出,最小乘車時間為64,在轉2次車時可以在此時間到達.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解算法由上面的例子,我們只要找到一個轉車次數m,轉車次數不大于m時,最小乘車時間為TS(i,j,m)=min{tS(i,j,k)|k≤m}轉車次數大于m時,乘車時間的下界為5(m+1)+3nS(i,j)若TS(i,j,m)≤5(m+1)+3nS(i,j),則TS(i,j,m)為最優解.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解算法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)即為最短乘車時間;否則令m:=m+1，轉Step2.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解第四對公汽站點S0008－S0073的求解過程可以用下面的表格表示(nS(i,j)=13):m01234ts(i,j,m)∞83676359Ts(i,j,m)∞836763595(m+1)+3ns(i,j)

4449545964最小乘車時間為59,需轉4次車.其它答案參見評閱要點(該要點給出的答案中包含了起始的3分鐘)南京郵電大學數理學院楊振華制作yangzhenhua@綜合考慮公汽與地鐵(1)最小轉車次數將地鐵線路看成公汽線路.最小轉車次數這一目標的討論難度沒有增加,只是增加了幾條公汽線路.對于題中給的六組站點,其前5組站點都不在地鐵邊,因此增加地鐵后,最小乘車次數沒有變化,仍然是原來的1或2.第6組2個站點都在地鐵線上,最小轉乘次數為0.南京郵電大學數理學院楊振華制作yangzhenhua@綜合考慮公汽與地鐵(2)最小乘車費用對于一般的兩個站點之間的最小乘車費用,僅考慮公汽時討論就很復雜,增加了地鐵之后討論還是差不多復雜,要用枚舉法來求解.也可以說,難度沒有增加.對于題中給的六組站點,僅考慮公汽時,最小費用為2元或3元,因此在綜合考慮公汽與地鐵時依然是最優解(乘一次地鐵3元)南京郵電大學數理學院楊振華制作yangzhenhua@綜合考慮公汽與地鐵(3)最小乘車時間增加了地鐵后乘車時間的討論變得相當復雜.注:如果假設換成次數最多為2或3,會將問題大大簡化.在此,為了將問題合理的簡化,我們首先研究這樣一個問題：在考慮時間最少時，線路中是否存在先乘地鐵，再轉公汽，再乘地鐵這樣的乘車方案？南京郵電大學數理學院楊振華制作yangzhenhua@地鐵-公汽-地鐵?考察下面兩種方案（A）從地鐵站Dk乘地鐵到地鐵站Dk1然后由公汽站Ss1乘到公汽站Ss2，再轉地鐵站Dl1，乘地鐵到地鐵站Dl；（B）直接乘地鐵由地鐵站Dk到Dl。直觀認識:(A)的時間>(B)的時間南京郵電大學數理學院楊振華制作yangzhenhua@地鐵-公汽-地鐵?設tDB(i,j)表示乘地鐵由地鐵站Di到地鐵站Dj的最短時間，nSA(i,j)表示可以由地鐵站Di轉乘的公汽站乘公汽到可以由地鐵站Dj轉乘的公汽站的最小公汽站數。于是,TB=tDB(k,l)如果(A)方案中沒有公汽轉車TA=tDB(k,k1)+3nSA(k1,l1)+tDB(l1,l)+1313表示換車時間如果有公汽轉車,等號要換成大于等于號南京郵電大學數理學院楊振華制作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)]最后一個中括號中的式子是非負的.因此TA-TB

≥3nSA(k1,l1)+13-tDB(k1,l1)如果右式非負,則有TA-TB

≥0.南京郵電大學數理學院楊振華制作yangzhenhua@地鐵-公汽-地鐵?3nSA(k1,l1)+13-tDB(k1,l1)≥0?一共有39個地鐵站,我們通過計算機程序（k1,l1對從1到39進行遍歷搜索）來判斷上式左邊的值,發現有四組地鐵站對應的值為負,分別是(13,30),(16,30),(30,15),(30,16),這四組站點對應的nSA(k1,l1)值均為1.對這四組點,再觀察TA-TB

≥

tDB(k,k1)+3nSA(k1,l1)+tDB(l1,l)+13-tDB(k,l)右端的值南京郵電大學數理學院楊振華制作yangzhenhua@地鐵-公汽-地鐵?tDB(k,k1)+3nSA(k1,l1)+tDB(l1,l)+13-tDB(k,l)=tDB(k,k1)+tDB(l1,l)+16-tDB(k,l)對于前面四組k1,l1,對k,l進行循環搜索,可以得到tDB(k,k1)+tDB(l1,l)+16-tDB(k,l)的最小值都是2.最終得到TA-TB

≥0.結論:對于題中給的數據,為了時間最省,不存在“地鐵-公汽-地鐵”這種換乘方案.換言之:地鐵一次乘完!南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型對于任意兩個公汽站點,不乘地鐵的時間最小方案在問題一中已經求得.下面考慮必須乘地鐵的方案:乘p次（轉p-1次）公汽，再乘地鐵，最后乘次q（轉q-1次)公汽到達終點的方案，下面將這樣的方案記為pDq。注:該方案包含了僅乘地鐵的情況(p=q=0).南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型下面主要針對題中前5組站點進行研究.這五組站點均不能由地鐵站直接轉乘,因此p,q≥1.求任意公汽站點Si到公汽站點Sj在方案下的最短時間,即對任意的p,q,以及任意的地鐵站Dk,Dl,求出起點乘p次公汽到可以直接轉乘地鐵站Dk的公汽站的最短時間,加上Dk到Dl的最短時間,再加上可以由地鐵站Dl直接轉乘的公汽站乘q公汽次到達終點公汽站的最短時間.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型(1)站數:N1(i,k,p-1),乘車時間:3N1(i,k,p-1),轉車時間5(p-1)SiDkSjDl(1)p次(3)q次(3)站數:N2(l,j,q-1),乘車時間: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南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型數學模型min{tSDS(i,j,p,q,k,l)|1≤p,q<∞,1≤k,l≤39,k≠l}在tSDS(i,j,p,q,k,l)表達式中,地鐵乘坐時間tD(k,l)是很容易計算的.若沒有轉車,tD(k,l)=2.5nD(k,l)(每站2.5分鐘)若轉1次車,tD(k,l)=2.5nD(k,l)+4.不存在轉2次以上的情況.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解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的取值范圍,可以類似于問題一來給出站數(公汽與地鐵)的下界.南京郵電大學數理學院楊振華制作yangzhenhua@下界設nSDS(i,j)表示從Si乘車(公汽或地鐵,可以轉車任意次)到Sj的最小乘車站數.我們可以用Dijkstra求最短路徑來求出這個數.記M=N1(i,k,p-1)+N2(l,j,q-1)為乘車方案中公汽的站數.根據公汽的站數加地鐵站數不小于最小乘車站數,有M+nD(k,l)≥nSDS(i,j).南京郵電大學數理學院楊振華制作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)南京郵電大學數理學院楊振華制作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表示乘公汽的站數,顯然M≥p+q,(一共乘了p+q次公汽,每次至少一站).我們最終得到tSDS(i,j,p,q,k,l)≥2.5nSDS(i,j)+5.5(p+q)+3根據這一下界,搜索不多的p,q就得到最小時間.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解對第一個點對,i=3359,j=1828,nSDS(i,j)=12(由于增加了地鐵,最小站數小了).(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南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解(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時,下界2.5nSDS(i,j)+5.5(p+q)+3=60.5南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解(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因此,最優解在p=q=2時取得.南京郵電大學數理學院楊振華制作yangzhenhua@最小乘車時間模型求解Step1用Dijkstra算法求出nSDS(i,j),令h=2;Step2計算下界 A(h+1,i,j)=2.5nSDS(i,j)+5.5(h+1)+3;Step3p從1到h-1循環,q=h-p,計算tSDS(i,j,p,q,k,l),對