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

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

【附錄1】基本參數(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)識(shí)于線路后；其中分段計(jì)價(jià)票價(jià)為：0～20站：1元；21～40站：2元；40站以上：3元地鐵票價(jià)：3元（不論地鐵線路間是否換乘）推論：換乘公汽等候３分鐘，換乘地鐵等候２分鐘

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

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

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

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

為站點(diǎn)k→j直達(dá)路線數(shù)，則：

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

≠0

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

bij

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

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

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

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

乘公交看奧運(yùn)B第21頁目標(biāo)五：站點(diǎn)負(fù)載壓力最小以ri

表示第i個(gè)站點(diǎn)負(fù)載壓力權(quán)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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