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

公交轉車問題 南京郵電大學理學院楊振華制作yangzhenhua 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 公交轉車問題 針對市場需求 某公司準備研制開發(fā)一個解決北京市公交線路選擇問題的自主查詢計算機系統(tǒng) 為了設計這樣一個系統(tǒng) 其核心是線路選擇的模型與算法 應該從實際情況出發(fā)考慮 滿足查詢者的各種不同需求 公交 指公共交通工具 包括公共汽車與地鐵 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 公交轉車問題 1 僅考慮公汽線路 給出任意兩公汽站點之間線路選擇問題的一般數(shù)學模型與算法 并根據(jù)附錄數(shù)據(jù) 利用你們的模型與算法 求出以下6對起始站 終到站之間的最佳路線 1 S3359 S1828 2 S1557 S0481 3 S0971 S0485 4 S0008 S0073 5 S0148 S0485 6 S0087 S36762 同時考慮公汽與地鐵線路 解決以上問題 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 基本參數(shù)設定 相鄰公汽站平均行駛時間 包括停站時間 3分鐘相鄰地鐵站平均行駛時間 包括停站時間 2 5分鐘公汽換乘公汽平均耗時 5分鐘 其中步行時間2分鐘 地鐵換乘地鐵平均耗時 4分鐘 其中步行時間2分鐘 地鐵換乘公汽平均耗時 7分鐘 其中步行時間4分鐘 公汽換乘地鐵平均耗時 6分鐘 其中步行時間4分鐘 公汽票價 分為單一票價與分段計價兩種 標記于線路后 其中分段計價的票價為 0 20站 1元 21 40站 2元 40站以上 3元地鐵票價 3元 無論地鐵線路間是否換乘 注 以上參數(shù)均為簡化問題而作的假設 未必與實際數(shù)據(jù)完全吻合 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 公汽線路信息 公汽運行方式 1 環(huán)形 2 上下行 有可能上下行路線一致 公汽收費方式 1 分段計價 2 單一票制1元 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 公汽線路信息 文件列出了520條公汽線路 下面是其中的一條 L001分段計價 S0619 S1914 S0388 S0348 S0392 S0429 S0436 S3885 S3612 S0819 S3524 S0820 S3914 S0128 S0710該線路是分段計價 且上下行路線一致的 南京郵電大學數(shù)理學院楊振華制作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 環(huán)行 D24 D25 D26 D12 D27 D28 D29 D30 D31 D32 D18 D33 D34 D35 D36 D37 D38 D39 D24 南京郵電大學數(shù)理學院楊振華制作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 南京郵電大學數(shù)理學院楊振華制作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 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 問題分析 從實際情況考慮 不同的查詢者有不同的要求 在數(shù)學上體現(xiàn)出目標的不同 一般可以考慮轉車次數(shù) 乘車費用 乘車時間這3個目標 問題可以歸結為多目標優(yōu)化問題 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 問題分析 如何處理上面的多個目標 多目標的處理最常用的方法是單目標化 即采用加權平均等方法將多個目標結合形成一個單一的目標 本問題中 單目標化并不合適 比較適當?shù)姆椒ㄊ菍γ總€目標尋求最佳線路 然后讓乘客按照自己的需求進行選擇 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 模型建立 我們先僅考慮公汽線路的情況 設N表示問題中的公汽站點數(shù) 即N 3957 A0 a i j 0 N N是直達最小站數(shù)矩陣 當存在公共汽車從站點直達站點時 表示從直達的最小站數(shù) 否則該元素取為 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 模型建立 令Am a i j m N N是m次轉乘最小站數(shù)矩陣 其元素a i j m 表示m次轉車情形下 從Si到Sj的最小站數(shù) 顯然 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小轉車次數(shù)模型 對于給定的公汽站點Si與Sj 最小轉車次數(shù)模型可以寫為 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車時間模型 轉車次數(shù)為m時 從Si到Sj的總時間為5m 3a i j m 轉一次車5分鐘 每乘一站 用時3分鐘 下面是最小乘車時間模型 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車費用模型 最小乘車費用模型可以寫為如下的形式 該模型是形式上的 對于求解沒有實質(zhì)性的作用 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小轉車次數(shù)模型求解 對于給定的公汽站點Si與Sj 只要逐次求出 a i j m 直到其為有限值即可 在實際求解時 先根據(jù)公汽線路的數(shù)據(jù)將a i j 0 的數(shù)據(jù)存儲在矩陣A0中 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小轉車次數(shù)模型求解 算法一 逐次查找 對于給定的i j 1 若a i j 0 表明轉車次數(shù)為0 否則轉 2 2 k從1到N進行搜索 若a i k 0 a k j 0 則轉車次數(shù)為1 否則轉 3 3 k1 k2從1到N進行搜索 若a i k1 0 a k1 k2 0 a k2 j 0 則轉車次數(shù)為2 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小轉車次數(shù)模型求解 逐次查找算法的復雜度若只要轉一次車 則循環(huán)的步數(shù)為N 若要轉2次車 循環(huán)的步數(shù)為N2 若要轉3次車 循環(huán)的步數(shù)為N3 由于N 3957 N3 6 2 1010 普通計算機運行時間較長 若要轉4次車 很難承受計算量 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小轉車次數(shù)模型求解 算法二 存儲逐次查找 1 若a i j 0 表明轉車次數(shù)為0 否則轉 2 2 求出矩陣A1 a i j 1 N N 其每個元素通過上面的表達式 用k從1到N循環(huán)求得 若對給定的i j 有a i j 1 表明轉車次數(shù)為1 類似可以計算多次轉車的情況注 矩陣A0 A1等計算后存儲在計算機中 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小轉車次數(shù)模型求解 存儲逐次查找算法的復雜度矩陣A1的計算 一共計算N2個元素 每個元素的計算要循環(huán)N步 計算量為N3 運行時間依然較長 優(yōu)點 矩陣Am m 1 的計算工作量與A1一致 有可能計算轉多次車 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小轉車次數(shù)模型求解 在前面的兩個算法中 每次循環(huán)都要進行N次 事實上 對給定的i 滿足a i k 0 的k是很少的 我們只要對這些k進行循環(huán) 在實際問題中 任何一個城市中 任何一個公汽站點所能到達的公汽站點只是城市中的一些 線 相對于整個城市而言 數(shù)目是比較少的 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小轉車次數(shù)模型求解 算法三 有限搜索逐次查找 給出矩陣B 其第i行記錄的是滿足a i k 0 的所有的 k 將存儲逐次查找算法中的k從1到N循環(huán)改為正對矩陣B第i行中的 k 進行循環(huán) 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小轉車次數(shù)模型求解 有限搜索逐次查找算法的復雜度矩陣Am的計算 一共計算N2個元素 每個元素的計算要循環(huán)的步數(shù)大大小于N 大約為N 10 計算量約為N3 10 一般的計算機可以實現(xiàn) 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小轉車次數(shù)模型求解 對于題目中給出的六組公汽站點 其最小轉車次數(shù)分別為 1 S3359 S18281 2 S1557 S04812 3 S0971 S04851 4 S0008 S00731 5 S0148 S04852 6 S0087 S36761 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 轉車次數(shù) 由于算法復雜性的問題 許多參賽隊都假設 最多轉2次車 少數(shù)參賽隊考慮轉3次車 個別的參賽隊考慮轉4次車或更多 由于所給的6組站點最小轉車次數(shù)為1或2 似乎假設最多轉2次車是合理的 根據(jù)題目中的數(shù)據(jù) 北京市的任意兩個公汽站點之間一般需轉幾次車 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 轉車次數(shù) N 3957 一共有N N 1 15653892對公汽站點 我們給出它們的最小轉車次數(shù) 根據(jù)題目中的數(shù)據(jù) 北京市的公汽站點轉5次車可以全部到達 根據(jù)表中的數(shù)據(jù) 假設轉最多2次車是不合理的 假設轉最多3次車有一定的合理性 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車費用 左邊的表給出的時最小轉車次數(shù) 即對應的一種乘車方案的乘車費用 關于最小乘車費用 其模型一般只有形式上的 對求解沒有直接的作用 我們對具體的六對站點給出討論的結果 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車費用 易見 第二 四 五 六對站點對應的費用是最小費用 為什么 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車費用 對于第一個點對S3359 S1828 如果換乘次數(shù)大于等于2 顯然費用至少為3 若換乘次數(shù)為1 采用枚舉方法將乘車方案全部列出 一共由9種方案 其中8種費用為3元 一種費用為4元 因此 最小乘車費用為3 類似 第三個點對的換乘次數(shù)為1的11種方案的最小費用也是3 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車時間模型求解 根據(jù)上面的模型 若已知a i j m 的值 則可以求出tS i j m 關于m的最小值 由于m的取值從0到無窮大 必須采用一定的技巧來求出最小值 注 參賽隊一般選取m從0到2 或0到3 是不合理的 不過也 成功 避免了求解的困難 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車時間模型求解 考慮第一對公汽站點1 S3359 S1828最小轉車次數(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) 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車時間模型求解 若m的范圍過大 求解會有一定困難 能否縮小m的范圍 在上頁的討論中 不等式a i j m m 1的含義是總站數(shù)比轉車次數(shù)至少大一 我們可以給出a i j m 更好的下界 從而縮小m的范圍 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 兩站點之間的最小站數(shù) a i j m 表示m次轉車下 從Si到Sj的最小站數(shù) 設nS i j 表示站點Si到Sj的最小站數(shù) 可以轉車任意次 顯然a i j m nS i j 我們有tS i j m 5m 3a i j m 5m 3nS i j 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 兩站點之間的最小站數(shù) 將公汽站點設為有向圖中的結點 若Si乘公汽1站可以到達Sj 我們就設一條有向邊從結點i指向結點j 對于每一條有向邊 指定其權為1 顯然求nS i j 就轉化為有向圖中結點到結點的最短路徑問題 對任意給定的i j 我們可以采用Dijkstra算法求得nS i j 南京郵電大學數(shù)理學院楊振華制作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 因此 最小乘車時間在區(qū)間 49 101 上 為求精確的最優(yōu)解 必須接著求解 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車時間模型求解 a i j 2 18 tS i j 2 64 m 3時 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時 tS i j m 5 4 3 13 59 最優(yōu)解位于區(qū)間 59 64 南京郵電大學數(shù)理學院楊振華制作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次車時可以在此時間到達 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車時間模型求解算法 由上面的例子 我們只要找到一個轉車次數(shù)m 轉車次數(shù)不大于m時 最小乘車時間為TS i j m min tS i j k k m 轉車次數(shù)大于m時 乘車時間的下界為5 m 1 3nS i j 若TS i j m 5 m 1 3nS i j 則TS i j m 為最優(yōu)解 南京郵電大學數(shù)理學院楊振華制作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 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車時間模型求解 第四對公汽站點S0008 S0073的求解過程可以用下面的表格表示 nS i j 13 最小乘車時間為59 需轉4次車 其它答案參見評閱要點 該要點給出的答案中包含了起始的3分鐘 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 綜合考慮公汽與地鐵 1 最小轉車次數(shù)將地鐵線路看成公汽線路 最小轉車次數(shù)這一目標的討論難度沒有增加 只是增加了幾條公汽線路 對于題中給的六組站點 其前5組站點都不在地鐵邊 因此增加地鐵后 最小乘車次數(shù)沒有變化 仍然是原來的1或2 第6組2個站點都在地鐵線上 最小轉乘次數(shù)為0 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 綜合考慮公汽與地鐵 2 最小乘車費用對于一般的兩個站點之間的最小乘車費用 僅考慮公汽時討論就很復雜 增加了地鐵之后討論還是差不多復雜 要用枚舉法來求解 也可以說 難度沒有增加 對于題中給的六組站點 僅考慮公汽時 最小費用為2元或3元 因此在綜合考慮公汽與地鐵時依然是最優(yōu)解 乘一次地鐵3元 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 綜合考慮公汽與地鐵 3 最小乘車時間增加了地鐵后乘車時間的討論變得相當復雜 注 如果假設換成次數(shù)最多為2或3 會將問題大大簡化 在此 為了將問題合理的簡化 我們首先研究這樣一個問題 在考慮時間最少時 線路中是否存在先乘地鐵 再轉公汽 再乘地鐵這樣的乘車方案 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 地鐵 公汽 地鐵 考察下面兩種方案 A 從地鐵站Dk乘地鐵到地鐵站Dk1然后由公汽站Ss1乘到公汽站Ss2 再轉地鐵站Dl1 乘地鐵到地鐵站Dl B 直接乘地鐵由地鐵站Dk到Dl 直觀認識 A 的時間 B 的時間 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 地鐵 公汽 地鐵 設tDB i j 表示乘地鐵由地鐵站Di到地鐵站Dj的最短時間 nSA i j 表示可以由地鐵站Di轉乘的公汽站乘公汽到可以由地鐵站Dj轉乘的公汽站的最小公汽站數(shù) 于是 TB tDB k l 如果 A 方案中沒有公汽轉車TA tDB k k1 3nSA k1 l1 tDB l1 l 1313表示換車時間如果有公汽轉車 等號要換成大于等于號 南京郵電大學數(shù)理學院楊振華制作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 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 地鐵 公汽 地鐵 3nSA k1 l1 13 tDB k1 l1 0 一共有39個地鐵站 我們通過計算機程序 k1 l1對從1到39進行遍歷搜索 來判斷上式左邊的值 發(fā)現(xiàn)有四組地鐵站對應的值為負 分別是 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 右端的值 南京郵電大學數(shù)理學院楊振華制作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進行循環(huán)搜索 可以得到tDB k k1 tDB l1 l 16 tDB k l 的最小值都是2 最終得到TA TB 0 結論 對于題中給的數(shù)據(jù) 為了時間最省 不存在 地鐵 公汽 地鐵 這種換乘方案 換言之 地鐵一次乘完 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車時間模型 對于任意兩個公汽站點 不乘地鐵的時間最小方案在問題一中已經(jīng)求得 下面考慮必須乘地鐵的方案 乘p次 轉p 1次 公汽 再乘地鐵 最后乘次q 轉q 1次 公汽到達終點的方案 下面將這樣的方案記為pDq 注 該方案包含了僅乘地鐵的情況 p q 0 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車時間模型 下面主要針對題中前5組站點進行研究 這五組站點均不能由地鐵站直接轉乘 因此p q 1 求任意公汽站點Si到公汽站點Sj在方案下的最短時間 即對任意的p q 以及任意的地鐵站Dk Dl 求出起點乘p次公汽到可以直接轉乘地鐵站Dk的公汽站的最短時間 加上Dk到Dl的最短時間 再加上可以由地鐵站Dl直接轉乘的公汽站乘q公汽次到達終點公汽站的最短時間 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車時間模型 1 站數(shù) N1 i k p 1 乘車時間 3N1 i k p 1 轉車時間5 p 1 Si Dk Sj Dl 1 p次 3 q次 3 站數(shù) 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 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 最小乘車時間模型 數(shù)學模型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次以上的情況 南京郵電大學數(shù)理學院楊振華制作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的取值范圍 可以類似于問題一來給出站數(shù) 公汽與地鐵 的下界 南京郵電大學數(shù)理學院楊振華制作yangzhenhua 下界 設nSDS i j 表示從Si乘車 公汽或地鐵 可以轉車任意次 到Sj的最小乘車站數(shù) 我們可以用Dijkstra求最短路徑來求出這個數(shù) 記M N1 i k p 1 N2 l j q 1 為乘車方案中公汽的站數(shù) 根據(jù)公汽的站數(shù)加地鐵站數(shù)不小于最小乘車站數(shù) 有M nD k l nSDS i j 南京郵電大學數(shù)理學院楊振華制作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 南京郵電大學數(shù)理學院楊振華制作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ù)理學院楊振華制作yangzhenhua 最小乘車時間模型求解 對第一個點對 i 3359 j 1828 nSDS i j 12 由于增加了地鐵 最小站數(shù)小了 1 p