乘公交看奧運B市公開課一等獎省賽課獲獎?wù)n件

全國競賽B題評講主講:龔劬乘公交看奧運B第1頁B題:乘公交，看奧運問題競賽總體情況幾個經(jīng)典模型幾個經(jīng)典求解方法模型和方法評價B題概況主要內(nèi)容乘公交看奧運B第2頁部分B題高等教育學(xué)費標準探討(B)乘公交，看奧運（B)DVD在線租賃(B)電力市場輸電阻塞管理問題（B)露天礦生產(chǎn)車輛安排(B)公交車調(diào)度(B)鋼管訂購和運輸(B)鉆井布局優(yōu)化問題（1999B)災(zāi)情巡視路線(1998B)乘公交看奧運B第3頁B題:乘公交，看奧運問題競賽總體情況幾個經(jīng)典模型幾個經(jīng)典求解方法模型和方法評價乘公交看奧運B第4頁乘公交，看奧運公交線路選擇問題自主查詢計算機系統(tǒng)：關(guān)鍵是線路選擇模型與算法應(yīng)該從實際情況出發(fā)考慮，滿足查詢者各種不一樣需求1.僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題普通數(shù)學(xué)模型與算法2.同時考慮公汽與地鐵線路，處理以上問題3.假設(shè)又知道全部站點之間步行時間，給出任意兩站點之間線路選擇問題數(shù)學(xué)模型乘公交看奧運B第5頁

【附錄1】基本參數(shù)設(shè)定相鄰公汽站平均行駛時間(包含停站時間)：3分鐘相鄰地鐵站平均行駛時間(包含停站時間)：2.5分鐘公汽換乘公汽平均耗時：5分鐘(其中步行時間2分鐘)地鐵換乘地鐵平均耗時：4分鐘(其中步行時間2分鐘)地鐵換乘公汽平均耗時：7分鐘(其中步行時間4分鐘)公汽換乘地鐵平均耗時：6分鐘(其中步行時間4分鐘)公汽票價：分為單一票價與分段計價兩種，標識于線路后；其中分段計價票價為：0～20站：1元；21～40站：2元；40站以上：3元地鐵票價：3元（不論地鐵線路間是否換乘）推論：換乘公汽等候３分鐘，換乘地鐵等候２分鐘

【附錄2】公交線路及相關(guān)信息（見數(shù)據(jù)文件）乘公交看奧運B第6頁模型目標多目標優(yōu)化問題（最少考慮三方面）換乘次數(shù)最少(N)、費用最省(M)、時間最短(T)從該問題實際背景來看，加權(quán)不太適當不少同學(xué)用層次分析法確定權(quán)不少同學(xué)計算時間價值（平均收入／工作時間）不一樣目標組合模型三個目標按優(yōu)先級排序，組合成六個模型也可將一些目標作為約束乘公交看奧運B第7頁多數(shù)隊僅采取搜索法（70-80%?）直達；一次換乘；二次換乘；…ststst求出全部線路；評價其目標(輕易計算)；選優(yōu)乘公交看奧運B第8頁同學(xué)論文中存在主要問題2.目標不妥，或不完整1.幾乎沒有模型，只有算法（普通是搜索法）3.算法使用不妥4.對第３問，幾乎是沒有多少時間來認真進行討論和建模5.全文表示不太清楚，思緒混亂乘公交看奧運B第9頁問題一:公汽站點之間線路選擇模型:通暢、便利目標：換乘次數(shù)最少不一樣行程需求：行程耗時最少；行程費用最少.人性化查詢設(shè)計：轉(zhuǎn)乘站點是否為始發(fā)站提醒；站點負載壓力提醒.乘公交看奧運B第10頁問題一:公汽站點之間線路選擇模型:1.數(shù)據(jù)處理，將三種公汽線路進行處理；2.建立可查詢兩站之間直達線路“公汽直達數(shù)據(jù)庫Q”；3.建立基于有向賦權(quán)圖與最短路理論0-1規(guī)劃模型；4.針對模型分別使用不一樣方法求解，得到各種適合不一樣用戶方案集。乘公交看奧運B第11頁1.數(shù)據(jù)處理——三種公汽線路抽象處理(1)下行線、上行線原路返回(2)線路為環(huán)行線(3)下行線與上行線經(jīng)過站點不一樣乘公交看奧運B第12頁2.“公汽直達數(shù)據(jù)庫Q”建立查詢系統(tǒng)內(nèi)部應(yīng)設(shè)有任兩站點直達線路表，以方便查詢時優(yōu)先快速查詢是否有直達車，若有，則直接輸出全部直達車輛；若無，再搜索換乘路線。本題共有3957個站點,元胞結(jié)構(gòu)乘公交看奧運B第13頁3.模型Ⅰ分析與建立當輸入起訖點后，系統(tǒng)內(nèi)部經(jīng)過Q查詢無結(jié)果時，系統(tǒng)內(nèi)部應(yīng)自動搜尋換乘次數(shù)最少路線，若換乘次數(shù)相同時有各種轉(zhuǎn)乘方案，則系統(tǒng)應(yīng)顯示全部轉(zhuǎn)乘路線方案（包含轉(zhuǎn)乘次數(shù)、行程總時間、路徑總站點數(shù)、轉(zhuǎn)乘站點及路線、是否始發(fā)、行程總費用、轉(zhuǎn)乘站點負載壓力）供查詢者自主選擇。系統(tǒng)應(yīng)向查詢者推薦“時間最短”，“費用最省”，“轉(zhuǎn)乘站始發(fā)站最多”，“負載壓力最小”不一樣目標下最正確路線。乘公交看奧運B第14頁基于不一樣目標帶權(quán)有向圖定義建立一個帶權(quán)有向圖，節(jié)點表示站點，有向弧表示前一站點能夠直達后一站點，弧上權(quán)表示前一站點直達后一站點所需付出代價(時間,費用等)時間：費用：始發(fā)：負載：

乘公交看奧運B第15頁最少換乘次數(shù)確實定統(tǒng)計Q中各元素長度，可得任意兩站點直達線路數(shù)。由此可結(jié)構(gòu)表示兩兩站點間直達路線數(shù)目標直達線路數(shù)矩陣經(jīng)過矩陣冪運算可得到任兩站點間換乘線路數(shù)矩陣，進而得到任兩站點間最少換乘次數(shù)矩陣

從而可得任兩站間所需最少換乘次數(shù)。

乘公交看奧運B第16頁最少換乘次數(shù)確實定1.直達線路數(shù)矩陣2.換乘線路數(shù)矩陣建立矩陣A2次冪中元素表示任兩站點間經(jīng)過1次轉(zhuǎn)乘路線數(shù)，即如:A2第1行第2列元素以An表示方陣An次冪，Akj

為站點k→j直達路線數(shù)，則：

乘公交看奧運B第17頁3.最少換乘次數(shù)矩陣建立引入矩陣B=(bij)，其矩陣元素bij為使得aijn

≠0

n最小值，n∈[1,∞)，則:

bij

-1表示從站點i→j必要最少換乘次數(shù)，以矩陣C=(cij)

表示最少換乘次數(shù)矩陣，則：cij=bij-1(當i≠j時)乘公交看奧運B第18頁基于最短路理論模型分析目標一：換乘次數(shù)最少；目標二：行程時間最短；目標三：行程費用最少；目標四：轉(zhuǎn)乘車輛始發(fā)最多；目標五：站點負載壓力最小。乘公交看奧運B第19頁目標一：換乘次數(shù)最少引入0-1決議變量xij

表示弧(i,j)是否在起點與終點路上目標二：行程總時間最短時間權(quán)值行程總時間=乘車時間+換乘時間+起始站等候時間

乘公交看奧運B第20頁目標三：行程總費用最少直達費用權(quán)目標四：轉(zhuǎn)乘車輛始發(fā)最多引入0-1變量

乘公交看奧運B第21頁目標五：站點負載壓力最小以ri

表示第i個站點負載壓力權(quán)

乘公交看奧運B第22頁約束分析1)換乘次數(shù)約束2）最短路起訖點約束

乘公交看奧運B第23頁多目標最短路線性規(guī)劃模型

關(guān)聯(lián)矩陣是全么模矩陣，所以0-1決議變量能夠松弛為區(qū)間[0,1]中實數(shù)不含負圈，變量直接松弛為全部非負實數(shù)xij能夠不限定為{0，1}(0-1規(guī)劃)?乘公交看奧運B第24頁模型求解4種方法方法一、修正Floyd-Warshall算法

在線路選擇問題中，當從i可直達j時,定義弧(i,j)；其上權(quán)為lij表示由i直達j付出代價，可認為時間或費用等(多條線路可達時只保留最小代價)初始等車時間2(3)min也不包含在內(nèi)，最終結(jié)果可加上.dij(0)=dij乘公交看奧運B第25頁最小費用或時間定義矩陣算子“⊙”以下：設(shè)A、B均為n階方陣，C=A⊙B(考慮換乘代價)當考慮費用矩陣之間運算時，表示在k換乘時間

當考慮時間矩陣之間運算時，＝０D(k)=D(k-1)⊙D表示k次換乘最低代價(費用或時間)該算法大致相當于求最短路Floyd-Warshall算法，但考慮了換乘原因類似地,經(jīng)過修改Dijkstra算法求解也可乘公交看奧運B第26頁方法二修正Dijkstra算法STEP1.若S=V,則uj為節(jié)點s到節(jié)點j最短路路長(最短路能夠經(jīng)過數(shù)組pred所統(tǒng)計信息反向追蹤取得),結(jié)束.不然繼續(xù).STEP0.(初始化)令S=，=V，；對V中頂點j(js),令初始距離標號.STEP2.從中找到距離標號最小節(jié)點i，把它從刪除，加入S.對于全部從i出發(fā)弧,若,其中k=pres(i),則令,轉(zhuǎn)STEP1.特點：1.算法求出從起點s到全部點最短路長(時間等)2.每點給一對標號(uj,predj)，uj是從s到j(luò)最短路長；pred(j)是從s到j(luò)最短路中j點前一點3.輸入權(quán)矩陣W=(wij)(時間或費用或其它)乘公交看奧運B第27頁方法三、基于數(shù)據(jù)庫Q“鄰接搜索算法”求解

Step1：輸入乘車始點i終點j，（注：為最少換乘次數(shù)矩陣）若cij

=0,則有直達線路，輸出Q中全部直達信息，結(jié)束程序，若cij

=1,則有轉(zhuǎn)乘1次線路，轉(zhuǎn)Step2，若cij

=2,則有轉(zhuǎn)乘2次線路，轉(zhuǎn)Step4，若cij

>2,則存在轉(zhuǎn)乘cij次線路，但全局計算時間復(fù)雜度較高，終止鄰接算法，采取Lingo求解；Step2：求線路s(i)直達站點E(i,U),及線路t(j)直達站點F(j,V)；Step3：若存在E(i,U)=F(j,V)，線路s(i)、t(i)可能不止一個，即為一次轉(zhuǎn)車線路,保留隊列U1，轉(zhuǎn)Step6；Step4：求經(jīng)過E(i,U)線路r(K)求線路r(K)站點G(K,W)；Step5：若存在G(K,W)=F(j,V)，線路s(i)、t(j)、r(K)可能不止一個，即為兩次轉(zhuǎn)車線路，保留隊列U2，轉(zhuǎn)Step6;Step6：修改隊列U1、U2中組員，按其屬性(途經(jīng)站點數(shù)，乘坐車輛)依據(jù)不一樣目標計算總行程時間、費用等.

乘公交看奧運B第28頁方法四、使用Lingo軟件求解無轉(zhuǎn)乘次數(shù)限制方案（針對不一樣目標分別求解）乘公交看奧運B第29頁模型評價1鄰接算法評價

1)建立在圖基礎(chǔ)下能夠求解出轉(zhuǎn)乘次數(shù)不超出兩次時全部可行方案，并可依據(jù)公眾不一樣需求，給出最正確需要方案，從此角度考慮，模型實用性較強；2)模型求解基于直達隊列Q，采取空間換取時間思想，適合查詢系統(tǒng)設(shè)計標準能夠較強適應(yīng)工程應(yīng)用；3)在轉(zhuǎn)乘次數(shù)超出兩次情況下，利用本算法求解計算過程復(fù)雜，計算量過大.故本模型存在一定不足。乘公交看奧運B第30頁模型評價2.圖論最短路徑算法評價

1)修正Floyd-Warshall算法和修正Dijkstra算法均能夠求得不限制最小轉(zhuǎn)乘數(shù)時全局最優(yōu)路線(單目標)，這是其它全部算法無法到達；

2)修正Floyd-Warshall算法能夠求得在限制最小轉(zhuǎn)乘數(shù)時與鄰接算法一樣方案，表明模型通用性較強

3)從理論角度分析，最優(yōu)化模型規(guī)劃角度可解含有很強實際意義，比如從全國范圍考慮求解，那么轉(zhuǎn)車3~4次也是能夠接收，只要耗時足夠短；

4)只要增加一些統(tǒng)計,修正Floyd-Warshall算法和修正Dijkstra算法還能求解出各種方案，實用性強。乘公交看奧運B第31頁模型評價30-1規(guī)劃Lingo求解方案評價

1)在不限制最小轉(zhuǎn)乘數(shù)時能夠求得全局最優(yōu)解，這是其它全部算法無法到達，比如在第2、4、5條線路上其轉(zhuǎn)車次數(shù)為3、4、3，不過耗時相對轉(zhuǎn)2次要節(jié)約許多；

2)在限制最小轉(zhuǎn)乘數(shù)時能夠求得與鄰接算法一樣方案，表明模型通用性較強，但無法像鄰接算法一樣求解各種方案是用戶所不能接收

3)從理論角度分析，最優(yōu)化模型規(guī)劃角度可解含有很強實際意義，比如從全國范圍考慮求解，那么轉(zhuǎn)車3~4次也是能夠接收，只要耗時足夠短；

4)從計算時間來分析，盡管需要20分鐘，但大部分