乘公交看奧運2019Bppt課件_第1頁
乘公交看奧運2019Bppt課件_第2頁
乘公交看奧運2019Bppt課件_第3頁
乘公交看奧運2019Bppt課件_第4頁
乘公交看奧運2019Bppt課件_第5頁
已閱讀5頁,還剩28頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、全國競賽全國競賽B B題評講題評講主講主講: : 龔劬龔劬2021.52021.520192019年年B B題題: : 乘公交,看奧運乘公交,看奧運 問題問題 競賽總體情況競賽總體情況 幾種典型模型幾種典型模型 幾種典型求解方法幾種典型求解方法 模型和方法的評價模型和方法的評價 B B題概況題概況主要內容主要內容 部分部分B B題題高等教育學費標準探討 (2019B)乘公交,看奧運2019B) DVD在線租賃 (2019B)電力市場的輸電阻塞管理問題2019B)露天礦生產的車輛安排 (2019B)公交車調度 (2019B) 鋼管訂購和運輸 (2000B) 鉆井布局優(yōu)化問題2019B) 災情巡視

2、路線 (2019B)2019年年B題題: 乘公交,看奧運乘公交,看奧運 問題問題 競賽總體情況競賽總體情況 幾種典型模型幾種典型模型 幾種典型求解方法幾種典型求解方法 模型和方法的評價模型和方法的評價 乘公交,看奧運乘公交,看奧運 公交線路選擇問題的自主查詢計算機系統(tǒng):核心是公交線路選擇問題的自主查詢計算機系統(tǒng):核心是線路選擇的模型與算法線路選擇的模型與算法 應該從實際情況出發(fā)考慮,滿足查詢者的各種不同應該從實際情況出發(fā)考慮,滿足查詢者的各種不同需求需求 1. 1. 僅考慮公汽線路,給出任意兩公汽站點之間線僅考慮公汽線路,給出任意兩公汽站點之間線路選擇問題的一般數(shù)學模型與算法路選擇問題的一般數(shù)

3、學模型與算法 2. 2. 同時考慮公汽與地鐵線路,解決以上問題同時考慮公汽與地鐵線路,解決以上問題 3. 3. 假設又知道所有站點之間的步行時間,給出任假設又知道所有站點之間的步行時間,給出任意兩站點之間線路選擇問題的數(shù)學模型意兩站點之間線路選擇問題的數(shù)學模型 【附錄1】基本參數(shù)設定相鄰公汽站平均行駛時間(包括停站時間): 3分鐘相鄰地鐵站平均行駛時間(包括停站時間): 2.5分鐘公汽換乘公汽平均耗時: 5分鐘(其中步行時間2分鐘)地鐵換乘地鐵平均耗時: 4分鐘(其中步行時間2分鐘)地鐵換乘公汽平均耗時: 7分鐘(其中步行時間4分鐘)公汽換乘地鐵平均耗時: 6分鐘(其中步行時間4分鐘)公汽票價

4、:分為單一票價與分段計價兩種,標記于線路后;其中分段計價的票價為:020站:1元;2140站:2元;40站以上:3元地鐵票價:3元無論地鐵線路間是否換乘)推論:換乘公汽等待分鐘,換乘地鐵等待分鐘【附錄2】公交線路及相關信息 (見數(shù)據(jù)文件)模型的目標模型的目標 多目標優(yōu)化問題至少考慮三方面)多目標優(yōu)化問題至少考慮三方面) 換乘次數(shù)最少換乘次數(shù)最少(N)(N)、費用最省、費用最省(M)(M)、時間最短、時間最短(T)(T) 從該問題的實際背景來看,加權不太合適從該問題的實際背景來看,加權不太合適 不少同學用層次分析法確定權不少同學用層次分析法確定權 不少同學計算時間的價值平均收入工作時間)不少同學

5、計算時間的價值平均收入工作時間) 不同目標組合的模型不同目標組合的模型 三個目標按優(yōu)先級排序,組合成六個模型三個目標按優(yōu)先級排序,組合成六個模型 也可將某些目標作為約束也可將某些目標作為約束多數(shù)隊僅采用搜索法多數(shù)隊僅采用搜索法70-80%?) 直達;直達; 一次換乘;一次換乘; 二次換乘;二次換乘;ststs t 求出所有線路;評價其目標求出所有線路;評價其目標(容易計算容易計算);選優(yōu);選優(yōu)同學論文中存在的主要問題同學論文中存在的主要問題2. 目標不當,或不完整目標不當,或不完整 1. 幾乎沒有模型,只有算法一般是搜索法)幾乎沒有模型,只有算法一般是搜索法)3. 算法使用不當算法使用不當4.

6、 對第問,幾乎是沒有多少時間來認真進行討論對第問,幾乎是沒有多少時間來認真進行討論和建模和建模5. 全文表達不太清楚,思路混亂全文表達不太清楚,思路混亂問題一:公汽站點之間線路選擇模型: 通暢、便利目標: 換乘次數(shù)最少 不同的行程需求: 行程耗時最少; 行程費用最少.人性化查詢設計: 轉乘站點是否為始發(fā)站提示; 站點負載壓力提示.問題一:公汽站點之間線路選擇模型:1.數(shù)據(jù)處理,將三種公汽線路進行處理;2.建立可查詢兩站之間直達線路的“公汽直達數(shù)據(jù)庫Q”;3.建立基于有向賦權圖與最短路理論的0-1 規(guī)劃模型;4.針對模型分別使用不同方法求解,得到多種適合不同用戶的方案集。1.數(shù)據(jù)處理三種公汽線路

7、抽象處理(1) 下行線、上行線原路返回(2) 線路為環(huán)行線(3) 下行線與上行線經過站點不同2. “公汽直達數(shù)據(jù)庫Q的建立查詢系統(tǒng)內部應設有任兩站點的直達線路表,以方便查詢時優(yōu)先快速查詢是否有直達車,若有,則直接輸出所有直達車輛;若無,再搜索換乘路線。本題共有3957 個站點, 元胞結構3. 模型分析與建立當輸入起訖點后,系統(tǒng)內部通過Q 查詢無結果時,系統(tǒng)內部應自動搜尋換乘次數(shù)最少的路線,若換乘次數(shù)相同時有多種轉乘方案,則系統(tǒng)應顯示所有轉乘路線方案包括轉乘次數(shù)、行程總時間、途徑總站點數(shù)、轉乘站點及路線、是否始發(fā)、行程總費用、轉乘站點負載壓力供查詢者自主選擇。系統(tǒng)應向查詢者推薦“時間最短”,“費

8、用最省”,“轉乘站始發(fā)站最多”,“負載壓力最小的不同目標下的最佳路線?;诓煌繕说膸嘤邢驁D定義基于不同目標的帶權有向圖定義 建立一個帶權有向圖,節(jié)點表示站點,有向弧表示建立一個帶權有向圖,節(jié)點表示站點,有向弧表示前一站前一站 點能夠直達后一站點,弧上的權表示前一站點直達后一點能夠直達后一站點,弧上的權表示前一站點直達后一站點所需付出的代價站點所需付出的代價( (時間時間, ,費用等費用等) )時間:時間:費用:費用:始發(fā):始發(fā):負載:負載: 最少換乘次數(shù)的確定統(tǒng)計Q 中各元素長度,可得任意兩站點的直達線路數(shù)。由此可構造表示兩兩站點間直達路線數(shù)目的直達線路數(shù)矩陣通過矩陣的冪運算可得到任兩站點

9、間換乘線路數(shù)矩陣,進而得到任兩站點間的最少換乘次數(shù)矩陣 從而可得任兩站間所需的最少換乘次數(shù)。 最少換乘次數(shù)的確定最少換乘次數(shù)的確定1.1.直達線路數(shù)矩陣直達線路數(shù)矩陣2. 2. 換乘線路數(shù)矩陣的建立換乘線路數(shù)矩陣的建立 矩陣矩陣A A 的的2 2 次冪中元素表示任兩站點間通過次冪中元素表示任兩站點間通過1 1 次轉乘次轉乘的路線數(shù),即的路線數(shù),即 如如: A2 : A2 的第的第1 1 行第行第2 2 列元素列元素 以以An An 表示方陣表示方陣A A 的的n n 次冪,次冪, A kj A kj 為站點為站點k j k j 的的直達路線數(shù),那么:直達路線數(shù),那么: 3.3.最少換乘次數(shù)矩陣

10、的建立最少換乘次數(shù)矩陣的建立引入矩陣引入矩陣B =( bij )B =( bij ),其矩陣元素,其矩陣元素b ij b ij 為使得為使得aijn 0 aijn 0 的的n n 的最小值,的最小值, n1,) n1,) , 那么那么: : b ij -1 b ij -1 表示從站點表示從站點i j i j 必要的最少換乘必要的最少換乘次數(shù),以矩陣次數(shù),以矩陣C=(cij) C=(cij) 表示最少換乘次數(shù)矩陣,表示最少換乘次數(shù)矩陣, 那么:那么: cij=bij-1 ( cij=bij-1 (當當ijij時時) )基于最短路理論的模型分析目標一:換乘次數(shù)最少;目標二:行程時間最短;目標三:行

11、程費用最少;目標四:轉乘車輛始發(fā)最多;目標五:站點負載壓力最小。目標一:換乘次數(shù)最少引入0-1 決策變量xij 表示弧( i, j) 是否在起點與終點的路上目標二:行程總時間最短時間權值行程總時間=乘車時間+換乘時間+起始站等待時間 目標三:行程總費用最少 直達費用權目標四:轉乘車輛始發(fā)最多 引入0-1 變量 目標五:站點負載壓力最小以ri 表示第i 個站點的負載壓力權 約束分析1) 換乘次數(shù)約束2最短路起訖點約束 多目標最短路線性規(guī)劃模型 關聯(lián)矩陣是全么模關聯(lián)矩陣是全么模矩陣,因此矩陣,因此0-10-1決策決策變量可以松弛為區(qū)變量可以松弛為區(qū)間間0,10,1中的實數(shù)中的實數(shù) 不含負圈,變量直

12、不含負圈,變量直接松弛為所有非負接松弛為所有非負實數(shù)實數(shù)xij xij 可以不限定為可以不限定為00,1 (0-11 (0-1規(guī)劃規(guī)劃) ?) ?模型求解的模型求解的4 4 種方法種方法方法一、修正方法一、修正Floyd-WarshallFloyd-Warshall算法算法 在線路選擇問題中,當從i可直達j時,定義弧(i,j);其上的權為lij表示由i直達j付出的代價,可以為時間或費用等 (多條線路可達時只保留最小代價)初始等車時間2(3)min也不包括在內,最后結果可加上.(0)0ijijijaijl站點往 站點無直達車否則dij(0)=ddij(0)=dijij最小費用或時間最小費用或時間

13、 定義矩陣算子“”如下:設A、B均為n階方陣, C = A B (考慮換乘代價), ,min1,2,ijikkji j kcabkn當考慮費用矩陣之間的運算時,, ,i j k表示在k的換乘時間 當考慮時間矩陣之間的運算時,, ,i j k D(k)= D(k-1) D 表示k次換乘的最低代價(費用或時間) 該算法大體相當于求最短路的Floyd-Warshall算法,但考慮了換乘因素 類似地,通過修改Dijkstra算法求解也可方法二方法二 修正修正DijkstraDijkstra算法算法kijijijwuuSTEP1. 若S=V, 則uj為節(jié)點s到節(jié)點j的最短路路長(最短路可以通過數(shù)組pre

14、d所記錄的信息反向追蹤獲得),終了.否則繼續(xù). STEP0. (初始化) 令S= , =V, ;對V 中的頂點j(j s), 令初始距離標號 . S0)(, 01spreduusjuSTEP2. 從 中找到距離標號最小的節(jié)點i,把它從 刪除,加入S. 對于所有從i出發(fā)的弧 , 假設,其中k=pres(i),則令 ,轉STEP1. SSAji),(特點:1. 算法求出從起點s到所有點的最短路長(時間等) 2. 每點給一對標號 (uj, predj),uj是從s到j的最短路長;pred(j)是從s到j的最短路中j點的前一點 3. 輸入權矩陣W=(wij)(時間或費用或其他)ijpredwuukij

15、ijij)(,方法三、基于數(shù)據(jù)庫方法三、基于數(shù)據(jù)庫Q 的的“鄰接搜索算法求解鄰接搜索算法求解 Step 1:輸入乘車始點:輸入乘車始點i 終點終點j ,(注:,(注: 為最少換乘為最少換乘次數(shù)矩陣)次數(shù)矩陣)若若cij =0, 則有直達線路,輸出則有直達線路,輸出Q中所有直達信息,結束程序,中所有直達信息,結束程序,若若cij =1, 則有轉乘則有轉乘1次線路,轉次線路,轉Step 2 ,若若cij = 2 , 則有轉乘則有轉乘2次線路,轉次線路,轉Step 4,若若cij 2, 則存在轉乘則存在轉乘cij次線路,但全局計算時間復雜度較次線路,但全局計算時間復雜度較高,終止鄰接算法,采用高,終

16、止鄰接算法,采用Lingo求解;求解; Step 2:求線路:求線路s(i)的直達站點的直達站點E(i,U),及線路及線路t(j)的直達站的直達站點點F(j,V); Step 3:若存在:若存在E(i,U)=F(j,V) ,線路,線路s(i)、t(i)可能不止一可能不止一種,即為一次轉車的線路種,即為一次轉車的線路,保存隊列保存隊列U1,轉,轉Step6; Step 4:求經過:求經過E(i,U)的線路的線路r(K)求線路求線路r(K)的站點的站點G(K,W); Step 5:若存在:若存在G(K,W)=F(j,V) ,線路,線路s(i)、t(j) 、r(K)可可能不止一種,即為兩次轉車的線路

17、,保存隊列能不止一種,即為兩次轉車的線路,保存隊列U2,轉,轉Step6; Step 6:修改隊列:修改隊列U1、U2 中的成員,按其屬性中的成員,按其屬性(路過的站路過的站點數(shù),乘坐的車輛點數(shù),乘坐的車輛)根據(jù)不同目標計算總行程時間、費用根據(jù)不同目標計算總行程時間、費用等等. 方法四、使用方法四、使用Lingo Lingo 軟件求解無轉乘次數(shù)限軟件求解無轉乘次數(shù)限制的方案針對不同目標分別求解)制的方案針對不同目標分別求解)模型的評價模型的評價1 1 鄰接算法評價鄰接算法評價 1) 1) 建立在圖基礎下能夠求解出轉乘次數(shù)不超過建立在圖基礎下能夠求解出轉乘次數(shù)不超過兩次時的所有可行方案,并可根據(jù)

18、公眾的不同需兩次時的所有可行方案,并可根據(jù)公眾的不同需求,給出最佳需要方案,從此角度考慮,模型實求,給出最佳需要方案,從此角度考慮,模型實用性較強;用性較強; 2) 2) 模型求解基于直達隊列模型求解基于直達隊列Q Q,采用空間換取時間,采用空間換取時間思想,適合查詢系統(tǒng)設計標準能夠較強的適應工思想,適合查詢系統(tǒng)設計標準能夠較強的適應工程應用;程應用; 3) 3) 在轉乘次數(shù)超過兩次的情況下,運用本算法在轉乘次數(shù)超過兩次的情況下,運用本算法求解計算過程復雜,計算量過大求解計算過程復雜,計算量過大. .故本模型存在故本模型存在一定的局限性。一定的局限性。模型的評價模型的評價2. 圖論的最短路徑算

19、法評價圖論的最短路徑算法評價 1) 修正修正 Floyd-Warshall算法和修正算法和修正Dijkstra算法均可以求得不限制最小轉乘數(shù)時的全算法均可以求得不限制最小轉乘數(shù)時的全局最優(yōu)路線局最優(yōu)路線(單目標單目標),這是其他所有算法無,這是其他所有算法無法達到的;法達到的; 2) 修正修正 Floyd-Warshall算法可以求得在限算法可以求得在限制最小轉乘數(shù)時與鄰接算法同樣的方案,制最小轉乘數(shù)時與鄰接算法同樣的方案,表明模型的通用性較強表明模型的通用性較強 3) 從理論角度分析,最優(yōu)化模型規(guī)劃角度可從理論角度分析,最優(yōu)化模型規(guī)劃角度可解具有很強的實際意義,例如從全國范圍解具有很強的實際

20、意義,例如從全國范圍考慮求解,那么轉車考慮求解,那么轉車34 次也是可以接受次也是可以接受的,只要耗時足夠短;的,只要耗時足夠短; 4) 只要增加一些記錄只要增加一些記錄, 修正修正 Floyd-Warshall算法和修正算法和修正Dijkstra算法還能求解出多種方算法還能求解出多種方案,實用性強。案,實用性強。模型的評價模型的評價3 0-1 規(guī)劃規(guī)劃Lingo 求解方案評價求解方案評價 1) 在不限制最小轉乘數(shù)時可以求得全局最優(yōu)在不限制最小轉乘數(shù)時可以求得全局最優(yōu)解,這是其他所有算法無解,這是其他所有算法無 法達到的,例如法達到的,例如在第在第2、4、5 條線路上其轉車次數(shù)為條線路上其轉車次數(shù)為3、4、3,但是耗時相對轉,但是耗時相對轉2 次的要節(jié)省許多;次的要節(jié)省許多; 2) 在限制最小轉乘數(shù)時可以求得與鄰接算法在限制最小轉乘數(shù)時可以求得與鄰接算法同樣的方案,表明模型的通用性較強,但同樣的方案,表明模型的通用性較強,但無法像鄰接算法一樣求解多種方案是用戶無法像鄰接算法一樣求

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論