公交轉(zhuǎn)車問題(數(shù)學(xué)建模).ppt

公交轉(zhuǎn)車問題 南京郵電大學(xué)理學(xué)院楊振華制作yangzhenhua 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 公交轉(zhuǎn)車問題 針對市場需求 某公司準(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對起始站 終到站之間的最佳路線 1 S3359 S1828 2 S1557 S0481 3 S0971 S0485 4 S0008 S0073 5 S0148 S0485 6 S0087 S36762 同時(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)記于線路后 其中分段計(jì)價(jià)的票價(jià)為 0 20站 1元 21 40站 2元 40站以上 3元地鐵票價(jià) 3元 無論地鐵線路間是否換乘 注 以上參數(shù)均為簡化問題而作的假設(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 問題分析 從實(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ù)姆椒ㄊ菍γ總€(gè)目標(biāo)尋求最佳線路 然后讓乘客按照自己的需求進(jìn)行選擇 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 模型建立 我們先僅考慮公汽線路的情況 設(shè)N表示問題中的公汽站點(diǎn)數(shù) 即N 3957 A0 a i j 0 N N是直達(dá)最小站數(shù)矩陣 當(dāng)存在公共汽車從站點(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)車情形下 從Si到Sj的最小站數(shù) 顯然 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小轉(zhuǎn)車次數(shù)模型 對于給定的公汽站點(diǎn)Si與Sj 最小轉(zhuǎn)車次數(shù)模型可以寫為 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車時(shí)間模型 轉(zhuǎn)車次數(shù)為m時(shí) 從Si到Sj的總時(shí)間為5m 3a i j m 轉(zhuǎn)一次車5分鐘 每乘一站 用時(shí)3分鐘 下面是最小乘車時(shí)間模型 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車費(fèi)用模型 最小乘車費(fèi)用模型可以寫為如下的形式 該模型是形式上的 對于求解沒有實(shí)質(zhì)性的作用 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小轉(zhuǎn)車次數(shù)模型求解 對于給定的公汽站點(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ù)模型求解 算法一 逐次查找 對于給定的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 N3 6 2 1010 普通計(jì)算機(jī)運(yùn)行時(shí)間較長 若要轉(zhuǎn)4次車 很難承受計(jì)算量 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小轉(zhuǎn)車次數(shù)模型求解 算法二 存儲(chǔ)逐次查找 1 若a i j 0 表明轉(zhuǎn)車次數(shù)為0 否則轉(zhuǎn) 2 2 求出矩陣A1 a i j 1 N N 其每個(gè)元素通過上面的表達(dá)式 用k從1到N循環(huán)求得 若對給定的i j 有a i j 1 表明轉(zhuǎn)車次數(shù)為1 類似可以計(jì)算多次轉(zhuǎn)車的情況注 矩陣A0 A1等計(jì)算后存儲(chǔ)在計(jì)算機(jī)中 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小轉(zhuǎn)車次數(shù)模型求解 存儲(chǔ)逐次查找算法的復(fù)雜度矩陣A1的計(jì)算 一共計(jì)算N2個(gè)元素 每個(gè)元素的計(jì)算要循環(huán)N步 計(jì)算量為N3 運(yùn)行時(shí)間依然較長 優(yōu)點(diǎn) 矩陣Am m 1 的計(jì)算工作量與A1一致 有可能計(jì)算轉(zhuǎn)多次車 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小轉(zhuǎn)車次數(shù)模型求解 在前面的兩個(gè)算法中 每次循環(huán)都要進(jìn)行N次 事實(shí)上 對給定的i 滿足a i k 0 的k是很少的 我們只要對這些k進(jìn)行循環(huán) 在實(shí)際問題中 任何一個(gè)城市中 任何一個(gè)公汽站點(diǎn)所能到達(dá)的公汽站點(diǎn)只是城市中的一些 線 相對于整個(gè)城市而言 數(shù)目是比較少的 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小轉(zhuǎn)車次數(shù)模型求解 算法三 有限搜索逐次查找 給出矩陣B 其第i行記錄的是滿足a i k 0 的所有的 k 將存儲(chǔ)逐次查找算法中的k從1到N循環(huán)改為正對矩陣B第i行中的 k 進(jìn)行循環(huán) 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小轉(zhuǎn)車次數(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)車次數(shù)模型求解 對于題目中給出的六組公汽站點(diǎn) 其最小轉(zhuǎn)車次數(shù)分別為 1 S3359 S18281 2 S1557 S04812 3 S0971 S04851 4 S0008 S00731 5 S0148 S04852 6 S0087 S36761 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 轉(zhuǎn)車次數(shù) 由于算法復(fù)雜性的問題 許多參賽隊(duì)都假設(shè) 最多轉(zhuǎn)2次車 少數(shù)參賽隊(duì)考慮轉(zhuǎn)3次車 個(gè)別的參賽隊(duì)考慮轉(zhuǎn)4次車或更多 由于所給的6組站點(diǎn)最小轉(zhuǎn)車次數(shù)為1或2 似乎假設(shè)最多轉(zhuǎn)2次車是合理的 根據(jù)題目中的數(shù)據(jù) 北京市的任意兩個(gè)公汽站點(diǎn)之間一般需轉(zhuǎn)幾次車 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 轉(zhuǎn)車次數(shù) N 3957 一共有N N 1 15653892對公汽站點(diǎn) 我們給出它們的最小轉(zhuǎn)車次數(shù) 根據(jù)題目中的數(shù)據(jù) 北京市的公汽站點(diǎn)轉(zhuǎn)5次車可以全部到達(dá) 根據(jù)表中的數(shù)據(jù) 假設(shè)轉(zhuǎn)最多2次車是不合理的 假設(shè)轉(zhuǎn)最多3次車有一定的合理性 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車費(fèi)用 左邊的表給出的時(shí)最小轉(zhuǎn)車次數(shù) 即對應(yīng)的一種乘車方案的乘車費(fèi)用 關(guān)于最小乘車費(fèi)用 其模型一般只有形式上的 對求解沒有直接的作用 我們對具體的六對站點(diǎn)給出討論的結(jié)果 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車費(fèi)用 易見 第二 四 五 六對站點(diǎn)對應(yīng)的費(fèi)用是最小費(fèi)用 為什么 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車費(fèi)用 對于第一個(gè)點(diǎn)對S3359 S1828 如果換乘次數(shù)大于等于2 顯然費(fèi)用至少為3 若換乘次數(shù)為1 采用枚舉方法將乘車方案全部列出 一共由9種方案 其中8種費(fèi)用為3元 一種費(fèi)用為4元 因此 最小乘車費(fèi)用為3 類似 第三個(gè)點(diǎn)對的換乘次數(shù)為1的11種方案的最小費(fèi)用也是3 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車時(shí)間模型求解 根據(jù)上面的模型 若已知a i j m 的值 則可以求出tS i j m 關(guān)于m的最小值 由于m的取值從0到無窮大 必須采用一定的技巧來求出最小值 注 參賽隊(duì)一般選取m從0到2 或0到3 是不合理的 不過也 成功 避免了求解的困難 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車時(shí)間模型求解 考慮第一對公汽站點(diǎn)1 S3359 S1828最小轉(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 若m 13 則tS i j m 105 tS i j 1 因此 我們可以將m的范圍放在0到12內(nèi)求最優(yōu) 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車時(shí)間模型求解 若m的范圍過大 求解會(huì)有一定困難 能否縮小m的范圍 在上頁的討論中 不等式a i j m m 1的含義是總站數(shù)比轉(zhuǎn)車次數(shù)至少大一 我們可以給出a i j m 更好的下界 從而縮小m的范圍 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 兩站點(diǎn)之間的最小站數(shù) a i j m 表示m次轉(zhuǎn)車下 從Si到Sj的最小站數(shù) 設(shè)nS i j 表示站點(diǎn)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é)院楊振華制作yangzhenhua 兩站點(diǎn)之間的最小站數(shù) 將公汽站點(diǎn)設(shè)為有向圖中的結(jié)點(diǎn) 若Si乘公汽1站可以到達(dá)Sj 我們就設(shè)一條有向邊從結(jié)點(diǎn)i指向結(jié)點(diǎn)j 對于每一條有向邊 指定其權(quán)為1 顯然求nS i j 就轉(zhuǎn)化為有向圖中結(jié)點(diǎn)到結(jié)點(diǎn)的最短路徑問題 對任意給定的i j 我們可以采用Dijkstra算法求得nS i j 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車時(shí)間模型求解 對于第一對公汽站點(diǎn)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時(shí) tS i j m 5 2 3 13 49 因此 最小乘車時(shí)間在區(qū)間 49 101 上 為求精確的最優(yōu)解 必須接著求解 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車時(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 最小乘車時(shí)間模型求解 a i j 4 17 tS i j 4 71 m 5時(shí) tS i j m 5 5 3 13 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時(shí) tS i j m 64 可以看出 最小乘車時(shí)間為64 在轉(zhuǎn)2次車時(shí)可以在此時(shí)間到達(dá) 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車時(shí)間模型求解算法 由上面的例子 我們只要找到一個(gè)轉(zhuǎn)車次數(shù)m 轉(zhuǎn)車次數(shù)不大于m時(shí) 最小乘車時(shí)間為TS i j m min tS i j k k m 轉(zhuǎn)車次數(shù)大于m時(shí) 乘車時(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 最小乘車時(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 即為最短乘車時(shí)間 否則令m m 1 轉(zhuǎn)Step2 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車時(shí)間模型求解 第四對公汽站點(diǎn)S0008 S0073的求解過程可以用下面的表格表示 nS i j 13 最小乘車時(shí)間為59 需轉(zhuǎn)4次車 其它答案參見評閱要點(diǎn) 該要點(diǎn)給出的答案中包含了起始的3分鐘 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 綜合考慮公汽與地鐵 1 最小轉(zhuǎn)車次數(shù)將地鐵線路看成公汽線路 最小轉(zhuǎn)車次數(shù)這一目標(biāo)的討論難度沒有增加 只是增加了幾條公汽線路 對于題中給的六組站點(diǎn) 其前5組站點(diǎn)都不在地鐵邊 因此增加地鐵后 最小乘車次數(shù)沒有變化 仍然是原來的1或2 第6組2個(gè)站點(diǎn)都在地鐵線上 最小轉(zhuǎn)乘次數(shù)為0 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 綜合考慮公汽與地鐵 2 最小乘車費(fèi)用對于一般的兩個(gè)站點(diǎn)之間的最小乘車費(fèi)用 僅考慮公汽時(shí)討論就很復(fù)雜 增加了地鐵之后討論還是差不多復(fù)雜 要用枚舉法來求解 也可以說 難度沒有增加 對于題中給的六組站點(diǎn) 僅考慮公汽時(shí) 最小費(fèi)用為2元或3元 因此在綜合考慮公汽與地鐵時(shí)依然是最優(yōu)解 乘一次地鐵3元 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 綜合考慮公汽與地鐵 3 最小乘車時(shí)間增加了地鐵后乘車時(shí)間的討論變得相當(dāng)復(fù)雜 注 如果假設(shè)換成次數(shù)最多為2或3 會(huì)將問題大大簡化 在此 為了將問題合理的簡化 我們首先研究這樣一個(gè)問題 在考慮時(shí)間最少時(shí) 線路中是否存在先乘地鐵 再轉(zhuǎn)公汽 再乘地鐵這樣的乘車方案 南京郵電大學(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 方案中沒有公汽轉(zhuǎn)車TA tDB k k1 3nSA k1 l1 tDB l1 l 1313表示換車時(shí)間如果有公汽轉(zhuǎn)車 等號要換成大于等于號 南京郵電大學(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è)中括號中的式子是非負(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è)地鐵站 我們通過計(jì)算機(jī)程序 k1 l1對從1到39進(jìn)行遍歷搜索 來判斷上式左邊的值 發(fā)現(xiàn)有四組地鐵站對應(yīng)的值為負(fù) 分別是 13 30 16 30 30 15 30 16 這四組站點(diǎn)對應(yīng)的nSA k1 l1 值均為1 對這四組點(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 對于前面四組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ù) 為了時(shí)間最省 不存在 地鐵 公汽 地鐵 這種換乘方案 換言之 地鐵一次乘完 南京郵電大學(xué)數(shù)理學(xué)院楊振華制作yangzhenhua 最小乘車時(shí)間模型 對于任意兩個(gè)公汽站點(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í)間模型 下面主要針對題中前5組站點(diǎn)進(jìn)行研究 這五組站點(diǎn)均不能由地鐵站直接轉(zhuǎn)乘 因此p q 1 求任意公汽站點(diǎn)Si到公汽站點(diǎn)Sj在方案下的最短時(shí)間 即對任意的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 最小乘車時(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é)院楊振華制作yangzhenhua 最小乘車時(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ì)算的 若沒有轉(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對于固定的i j 我們要遍歷p q k l來求上式的最小值 對于k l進(jì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 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 最小乘車時(shí)間模型求解 對第一個(gè)點(diǎn)對 i 3359 j 1828 nSDS i j 12 由于增加了地鐵 最小站數(shù)小了 1 p