2002高教社杯全國大學(xué)生數(shù)學(xué)建模競賽題目

1、壹2016江西財經(jīng)大學(xué)數(shù)學(xué)建模競賽（A題）基于車流量分析的城市交通管理參賽隊員：王嚴(yán)康、蔡姬、熊苗苗參賽隊編號：20160302016年5月20日5月25日貳20162016江西財經(jīng)大學(xué)數(shù)學(xué)建模競賽承諾書我們仔細(xì)閱讀了江西財經(jīng)大學(xué)數(shù)學(xué)建模競賽的競賽章程。我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng) 上咨詢等）與隊外的任何人研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的 ，如果引用別人的成果或其他公開的 資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參 考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正

2、、公平性。如有違反競賽規(guī) 則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號 是（從A/B/C中選擇一項填寫）： _A我們的參賽隊編號 為 2016030 參賽隊員（打印并簽名）：隊員1.姓名王嚴(yán)康專業(yè)班級14計算機一班隊員2.姓名蔡姬專業(yè)班級14計算機一班隊員3.姓名熊苗苗專業(yè)班級14計算機一班日期：2016 年5月25 日叁20162016江西財經(jīng)大學(xué)數(shù)學(xué)建模競賽編號和閱卷專用頁參賽隊編號：參賽隊 員姓名所有數(shù)學(xué)類與計算機類課程成績 （意愿參加全國競賽者填寫）是否選 修建模 課程是否愿 參加全 國競賽在校獲 獎項目王嚴(yán)康高數(shù)1:90 ;高數(shù)2:90 ;線代：93; C+: 83; C語言：7

3、1;數(shù)據(jù)結(jié)構(gòu)：79； Python : 67是是無蔡姬高數(shù)1:95 ;高數(shù)2:94 ;線代：92; C+: 90; C語言：74;數(shù)據(jù)結(jié)構(gòu)：85; Python : 76是是無參賽隊員填寫熊苗苗高數(shù)1:79 ;高數(shù)2:67 ;線代：60; C+: 80; C語言：70;數(shù)據(jù)結(jié)構(gòu)：70; Python : 79是是無評分（百分制）評閱人最終得分小組評價負(fù)責(zé)人閱卷 專家 評語閱卷填寫，參賽者不得填寫備注1、是否選修數(shù)學(xué)建模：指本學(xué)期是否選修了數(shù)學(xué)建模課程2、是否有意愿參加全國競賽 ：指參加今年的全國大學(xué)生數(shù)學(xué)建模競賽，一經(jīng)選定，不得退賽，否則將建議學(xué)生所在學(xué)院給予處分。培訓(xùn)時間：2016年8月5日

4、開始。江西財經(jīng)大學(xué)數(shù)學(xué)建模競賽組委會20162016年5 5月1515日制定1基于車流量分析的城市交通管理摘 要根據(jù)問題城市私家車數(shù)量越來越多，交通管理技術(shù)跟不上導(dǎo)致交通擁堵狀況嚴(yán)重， 日益增長的交通需求與城市道路基礎(chǔ)建設(shè)之間的矛盾已成為目前城市交通的主要矛盾。 由于交通問題已經(jīng)開始影響人們的正常生產(chǎn)生活。本篇論文從道路的實時車流量變化來控制車的行車路線，減少行車壓力大的路口的 壓力，提高機動車到達(dá)目的地的效率。一、車流量監(jiān)控模型我們分析采用路段平均行程速度、交通流量、路段飽和度、三個評價指標(biāo)來綜合放 映道路擁堵情況。我們選取八一廣場周圍為例，為了避免數(shù)據(jù)的不完整性導(dǎo)致對應(yīng)時事 件結(jié)果的不確定

5、性，綜合考慮我們采用模糊綜合平價模型來對問題進(jìn)行分析和求解。列出非常順暢、順暢、緩慢、擁堵和嚴(yán)重?fù)矶挛鍌€評判標(biāo)準(zhǔn)來綜合評價。確定出其隸屬度rx，通過已確定的模糊評價矩陣 R得出擁擠度系數(shù)B。二、最優(yōu)子結(jié)構(gòu)優(yōu)化路線模型基于模型一所求擁擠系數(shù)B,與道路長度綜合分析，算出有關(guān)行車時間權(quán)值t，通過 建立多段圖模型，求解到達(dá)目的地的最優(yōu)路線即權(quán)值之和最?。倳r間T）的結(jié)果。在n個路口之間建立連通路線，最多設(shè)置n（n-1）/2條線路，最少需n-1條線路使起 點到達(dá)終點，所以可將問題轉(zhuǎn)化為：在可能的線路中選擇 n-1條，求得起始路口到目的 路口的最短加權(quán)值，使得所耗費的總時間（各邊權(quán)值之和）最短。本算法綜合

6、考慮整體城市的交通網(wǎng)絡(luò)情況，此時的交通狀態(tài)是一種不斷變化的動態(tài) 過程，具有很強的隨機性和偶然性。而交通擁堵的潛伏、發(fā)展和產(chǎn)生與具有連貫性和相關(guān)性的特點，交通阻塞的發(fā)生與它 的過去和現(xiàn)狀緊密相關(guān)，因此，有可能通過對交通狀態(tài)的現(xiàn)狀和歷史進(jìn)行綜合分析。對不 確定或不精確的知識或信息中做出推理。模型假設(shè)在每輛機動車都設(shè)有道路實時監(jiān)控的狀況，會采取算法給出的建議?！娟P(guān)鍵字】：交通管理模糊模型評價多段圖最優(yōu)子結(jié)構(gòu)動態(tài)算法2一、問題重述1.1問題背景（ 1）機動車數(shù)量持續(xù)增長。隨著我國經(jīng)濟(jì)社會持續(xù)快速發(fā)展，群眾購車剛性需求旺盛，汽車保有量繼續(xù)呈快速 增長趨勢， 2015 年新注冊登記的汽車達(dá) 2385 萬輛

7、，保有量凈增 1781萬輛，均為歷史最 高水平。汽車占機動車的比率迅速提高，近五年汽車占機動車比率從47.06%提高到61.82%，群眾機動化出行方式經(jīng)歷了從摩托車到汽車的轉(zhuǎn)變，交通出行結(jié)構(gòu)發(fā)生了根本 性變化。（ 2）私家車保有量上升。2015 年，小型載客汽車達(dá) 1.36 億輛，其中，以個人名義登記的小型載客汽車（私 家車）達(dá)到 1.24 億輛，占小型載客汽車的 91.53%。與 2014 年相比，私家車增加 1877 萬輛，增長 17.77%。全國有 40 個城市的汽車保有量超過百萬輛，北京、成都、深圳、 上海、重慶、天津、蘇州、鄭州、杭州、廣州、西安 11 個城市汽車保有量超過 200

8、萬 輛。全國平均每百戶家庭擁有 31 輛私家車，北京、成都、深圳等大城市每百戶家庭擁 有私家車超過 60 輛。（3）交通問題日益突出。 隨著城市人口以及城市交通流的增加，城市特別是大城市的交通問題普通成為焦點 問題。路網(wǎng)不暢、設(shè)施不足、交通擁堵等問題越來越突出；行車難、停車難、交通秩序 混亂等問題日益突顯，對城市交通管理造成的沖擊和壓力越來越大。城市道路交通擁擠 堵塞問題已成為制約經(jīng)濟(jì)發(fā)展、降低人民生活質(zhì)量、削弱經(jīng)濟(jì)活力的瓶頸之一。解決交通堵塞問題勢在必行。據(jù)美國得克薩斯州運輸研究所 2006年底公布的數(shù)據(jù)顯示， 被稱為“汽車王國” 的美 國每年因交通堵塞造成的經(jīng)濟(jì)損失高達(dá) 1000億美元。

9、2007年中國社科院數(shù)量經(jīng)濟(jì)與技 術(shù)經(jīng)濟(jì)研究所測算， 北京市每天因為堵車造成的社會成本達(dá)到 4000 萬元，每年損失 146 億元。對于交通堵塞這個世界性難題，各國政府和民間都在為解決這個問題進(jìn)行廣泛的 研究。1.2問題提出在經(jīng)濟(jì)發(fā)展越來越快，私家車數(shù)量越來越多，交通為題日益突出的大背景下，如何 解決交通擁堵問題成為我們研究的主要問題。根據(jù)近幾年來各地的道路現(xiàn)狀，我們可以看到，即使是在道路不斷拓寬新建的條件下，交通壓力仍持續(xù)增大，機動車的增長帶來了越來越多的問題。這時候，在現(xiàn)有交通3問題分析條件下提高交通管理技術(shù)就顯得尤為重要。本次數(shù)學(xué)建模大賽題目就致力于為交通管理技術(shù)提供新方法，提出算法，建

10、立數(shù)學(xué) 模型，設(shè)計出更優(yōu)良的交通管理技術(shù)，提供更智能的技術(shù)和方法。主要分為兩個過程如下：1：我們主要目的是求得各個路口的實時的車流量信息，首先選取的實體地點是八一廣場附近的路線，由于路口較復(fù)雜，我們只監(jiān)測部分路口的相關(guān)時段的實時車流量，再 利用模糊模型評價方法對車流量設(shè)置評價標(biāo)準(zhǔn)，分出非常順暢，順暢，緩慢，擁堵，非 常擁堵五個等級。對于所得的數(shù)據(jù)進(jìn)行處理，建立數(shù)學(xué)模型，畫出擁堵曲線，得到各個 路口的擁堵指數(shù)bk。2：我們的主要目的是求得到達(dá)目的地的最短時間的最優(yōu)結(jié)果，首先將各個路口抽象為點，路抽象成連接點之間的線段，建立數(shù)學(xué)模型多段圖表示我們的問題。根據(jù)所求的擁堵指數(shù)bk結(jié)合各個路口之間的距離

11、構(gòu)成多段圖的權(quán)值， 在起始路口和 目的路口的n個路口之間選擇最有路線，利用貪心算法和最優(yōu)子結(jié)構(gòu)算法計算多段圖的 最優(yōu)解，使得所耗費的總時間（各邊權(quán)值之和）最短，求得道路交通管理建議最優(yōu)路線， 實現(xiàn)智能管理交通。三、模型假設(shè)（1）假設(shè)無交通事故發(fā)生，無惡劣天氣、自然災(zāi)害等的影響。（2）機動車的型號大小、行能等完全相同， 忽略其他影響不大的交通模型，所有道 路都是相同的類型。（3）各個路口規(guī)模相同，擁堵情況只集中在早晚高峰期間。（4）只考慮機動車，忽略其他自行車等各種車輛。（5）各個機動車速度都只受到車流量的影響，排除個人因素。四、符號設(shè)計符號符號說明X評價因素集Z五種服務(wù)標(biāo)準(zhǔn)評判集W各項指標(biāo)所占

12、權(quán)重Y交通狀態(tài)變量集bk交通擁堵指數(shù)V車流速度A路段占有率K車流密度T到達(dá)總時間S路程五、模型的建立和求解45.1車流量監(jiān)控模型5.1.1問題分析根據(jù)題設(shè)要求，我們?nèi)“艘粡V場周圍為研究對象，如圖所示,5.1.2問題評價標(biāo)準(zhǔn)按照道路擁堵程度的不同劃分為五個級別，分別為非常暢通、暢通、緩慢、擁堵和 嚴(yán)重?fù)矶?。通過浮動車數(shù)據(jù)的回歸擬合分析，并參考相關(guān)的標(biāo)準(zhǔn)，分別確定三個評價指 標(biāo)不同評價等級的閾值。（1）路段不同時段平均行程速度評判標(biāo)準(zhǔn)為了確定路段不同時段平均行程速度的評判標(biāo)準(zhǔn)，根據(jù)車速調(diào)查相關(guān)理論1和交通 流參數(shù)之間的關(guān)系可得出主干道平均行程速度的評判標(biāo)準(zhǔn)（見表1）。服務(wù)等級非常順暢順暢緩慢擁堵嚴(yán)

13、重?fù)矶轮鞲傻?45，+x)(35,45 )(25,35)(15,25 )(0,15)表一平均行程速度評判標(biāo)準(zhǔn)單位：km/h（2）車流量評判標(biāo)準(zhǔn)由于車流量取決于路段平均行程速度和自由流速度，為使評價結(jié)果具有一致性，利 用浮動車調(diào)查數(shù)據(jù)進(jìn)行平均行程速度回歸擬合分析。主干道的回歸擬合方程如下：bk=7.665e-8xA2-0/000047328x+1.00009 （ 程序見附件 1）5data 1quadratic4000500090000.9 0.B -0.70.6 0.5 -0.4 ”0.3、丿0,2 I-1-1-01 00020003000（上圖反應(yīng)了車流量與擁堵系數(shù)之間的數(shù)量關(guān)系）依據(jù)平均行

14、程速度評判標(biāo)準(zhǔn)的劃分，確定不同的車流量擁堵級別，具體結(jié)果如表 所示。服務(wù)等級;非常順暢順暢緩慢擁堵嚴(yán)重?fù)矶轮鞲傻?000:(4000,5000)(3000,4000)(2000,3000)表nrbJ = s gj式中，。令取值為0,1, 越接近1,道路越堵；反之，道路 越順暢。其中擁堵指數(shù)與擁堵程度的對應(yīng)關(guān)系如下圖所示：擁堵指數(shù)與擁堵對應(yīng)關(guān)系評價指標(biāo)非常順暢順暢緩慢擁堵嚴(yán)重?fù)矶聯(lián)矶轮笖?shù)0,0.20.2,0.40.4,0.60.6,0.80.8,15.1.4 模型的求解根據(jù)檢測的數(shù)據(jù)，我們將其分為0:00 5:00,5:00-7:00,7:00-9:00 等9個階段來分 析(見表格111)8求得

15、到達(dá)目的地的系數(shù)作為無向連通圖邊的權(quán)值, 最短的情況為最優(yōu)路線結(jié)果.表格1110:005:007:009:0011:0013:0016:0018:0020:00時 間5:007:009:0011:0013:0016:008:0020:0023:00實施刖 擁擠度0.150.20.80.910.750.890.950.450.38評價非常 順暢順暢嚴(yán)重 擁堵嚴(yán)重 擁堵嚴(yán)重 擁堵嚴(yán)重 擁堵嚴(yán)重 擁堵緩慢順暢實施后 擁擠度0,150.17 0.680.840.590.780.770.350.36評價非常 順暢非常 順暢擁堵嚴(yán)重 擁堵緩慢擁堵?lián)矶马槙稠槙?.2最優(yōu)子結(jié)構(gòu)優(yōu)化路線5.2.1冋題分析根據(jù)5

16、.1所求的擁堵指數(shù)和道路長度綜合分析，求解到達(dá)目的地的最優(yōu)路線。在n個路口之間建立連通路線，最多設(shè)置n（n-1）/2條線路，最少需n-1條線路使起 點到達(dá)終點，所以可將問題轉(zhuǎn)化為：在可能的線路中選擇 n-1條，求得起始路口到目的 路口的最短加權(quán)值，使得所耗費的總時間（各邊權(quán)值之和）最短。5.2.2評價標(biāo)準(zhǔn)S t根據(jù)公式（1-bk）v總時間 T=t1+t2+tn5.2.3模型建立為確定帶權(quán)重的有向圖的最優(yōu)子結(jié)構(gòu)，我們根據(jù)動態(tài)規(guī)劃算法抽象出數(shù)學(xué)模型如下:9cost（ i, j）=0=i=k-21、 頂點-表示路口2、邊一一各個路口連通的道路3、邊的權(quán)到達(dá)目的地的系數(shù)t問題可以理解為在此網(wǎng)中找一條最

17、短路徑，它的每條邊上的權(quán)值之和是所有路徑中 最小的-最優(yōu)子結(jié)構(gòu)。每一點最優(yōu)都是上一點最優(yōu)加上這段長度 即當(dāng)前最優(yōu)只與上一步有關(guān)。Us 初始值，uj第j段的最優(yōu)值。5.2.4模型求解（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；即在各條路線中找出最權(quán)值t相加最小的值。出發(fā)點為0，目的地為9 即根據(jù)公式cost（k,t）=0min c（j, P） cost（i i, p）, jV,P V 1, JpUE（2）遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；以自底向上的方式計算出最優(yōu)值；根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。步驟1-3是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形, 步驟4可以省略，步驟

18、3中記錄的信息也較少；若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟 4,步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。即：（3）用一個數(shù)組costn作為存儲子問題解的表格costi 表示從頂點 i 到終點 n-1 的最短路徑，數(shù)組 pathn 存儲狀態(tài)， pathi 表 示從頂點 *10i 到終點 n-1 的路徑上頂點 i 的下一個頂點。則：costi=mincij+costj(i j i&k=0; i-)2.1對頂點 i 的每一個鄰接點 j ，根據(jù)式 6.7 計算 costi;2.2根據(jù)式 6.8 計算 pathi;輸出最短路徑長度 cost0; 輸出最短路徑經(jīng)過的頂點：4.1i=0 4.2 循

19、環(huán)直到 pathi=n-14.2.1輸出 pathi; 4.2.2 i=pathi;( 6)形象描述如下：(2)由于多段圖將頂點劃分為氐個互不相交的子集.所以，多 段圖劃分為Jt段，每一段包含頂點的一個子集口不失一般 性，將多段圖的頂點按照段的順序進(jìn)行編號，同一段內(nèi) 頂點的相互順序無關(guān)緊要。假設(shè)圖中的頂點個數(shù)為從 則源點的編號為0,終點啲編號為刃亠并且，對圖中的 任何一條邊（血V）,頂點M的編號小于頂點卩的編號。下面考慮多段圖的最短路徑問題的填表形式.用一個數(shù)組costn作為存儲子問題解的表格，表示 從頂點i到終點ml的最短路徑，數(shù)組pathn存儲狀態(tài)，pathfi 表示從頂點i到終點n-1的

20、路徑上頂點i的下一個頂點。則動態(tài)規(guī)劃函數(shù)為：costEQarnlnlCij+costU (ijn且頂點j是頂點i的鄰接點)(1)pathi=使 Cij+costj瑕小的 j 12對多段圖的邊価“)，用q”表示邊上的權(quán)值，將從源點s到終 點t的最短路徑記為船矢紐 則從源點0到終點9的最短路徑 tf(O, 9)由下式確定：川(0, 9)=minc01+ d(l9), %+ d( (2f 9), c03+ (3, 9)這是最后一個階段的決策，它依賴于d(l, 9). d9) 和(3, 9)的計算結(jié)果，而(1, 9)二min%十“ 9), 口打十(59)必2, 9) =minc24+d(4, 9),

21、c25+7(5,9), c2,+rf(6, 9)rf(3, 9) =min(t35+d(5, 9), c3fr+rf(9)再向前推導(dǎo)，有：d(6, 9)=minc67+rf(7, 9), c礎(chǔ)+d(8, 9)=min6+7, 5+3=8(68)d(59 9)=minc57+rf(7,9), csg+d(8,9)=min8+7, 6+3=9(5 8)13rf(4, 9)=mine47+rf(7,鄉(xiāng)),c+rffS, 9) )=min5+7, 6+3=9(48)rf(3, 9)=minq5+rf(5, 9), c36+J(6, 9)=min4+9, 7+8=13(3-5)rf(2,9), c2-+

22、rf(5, 9), c26+d(6, 9)=min6+9, 7+9,8+8=15(2-4)rf(l, 9)=minc14+rf(4, 9), cl5+rf(5, 9)=min9+9, 8+9=17(15)rf(O, 9)=minrftl+rf(l, 9), c”+d(2, 9),弘+rf(3, 9)=min4+17, 2+15,3+13=16(0-3)最后，得到最短路徑為03589?長度為16。14附件 2c+：#include#include#include#include#defineMAX 100#definen 12 /* 頂點數(shù) */#definek 5/* 段數(shù) */int cnn

23、;void init(int cost) / 初始化圖int i,j;for(i=0;i13;i+) for(j=0;ja=500 1000 3000 4500 6000;0.9 0.45 0.3 0.45 0.9; y=polyfit(a (1，：)， a(2,:),2);y=7.6615e-8 -0.000473328 1.00009 poly2str(y)ans=7.665e-8xA2-0.000047328x+1.00009c14=3; c15=2;15c26=4; c27=2;c28=1; c36=2;c37=7; c48=11;c57=11; c58=8;c69=6; c610=5;c79=4; c710=3;c810=5; c811=6;c912=4; c1012=2;c1112=5;void fgraph(int cost,int path,int d) / 使用向前遞推算法求多段 圖的最短路徑int r,j,temp,min ；for(j=0