數(shù)學建模最優(yōu)路徑設計

1、2015高教社杯全國大學生數(shù)學建模競賽承諾書我們仔細閱讀了全國大學生數(shù)學建模競賽章程和全國大學生數(shù)學建模競賽參賽規(guī)則（以下簡稱為“競賽章程和參賽規(guī)則”，可從全國大學生數(shù)學建模競賽網(wǎng)站下載）。我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽章程和參賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽章程和參賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽章程和參賽規(guī)則

2、的行為，我們將受到嚴肅處理。我們授權全國大學生數(shù)學建模競賽組委會，可將我們的論文以任何形式進行公開展示（包括進行網(wǎng)上公示，在書籍、期刊和其他媒體進行正式或非正式發(fā)表等）。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）：A我們的參賽報名號為（如果賽區(qū)設置報名號的話）：所屬學校（請?zhí)顚懲暾娜麉①愱爢T（打印并簽名）：1_2指導教師或指導教師組負責人（打印并簽名廣（論文紙質版與電子版中的以上信息必須一致，只是電子版中無需簽名。以上內容請仔細核對，提交后將不再允許做任何修改。如填寫錯誤，論文可能被取消評獎資格。）日期：2015年7月27日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：編號專用頁

3、賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：從成都工業(yè)學院到西南交通大學最優(yōu)路徑設計摘要本文對現(xiàn)在生活中行車時間的不確定性進行了分析，并給出了最優(yōu)路徑的定義，即：行車所需期望時間最短且該路段行車時間的標準差最小。在將時間期望值和時間標準差值兩個決策變量合成為一個決策變量時，為消除不同指標帶來的不可公度性，我們對這兩個指標進行了無量綱化。對于問題一，建立雙目標優(yōu)化模型，給出最優(yōu)路徑的定義和數(shù)學表達式。將這兩個目標相加合成單目標。利用MATLAB程求解，將所建模

4、型應用到例子中，得出的結論是：選擇道路A。對于問題二，在問題一定義的最優(yōu)路徑的基礎上，建立圖論模型，應用Dijkstra算法，利用MATLA褊程，得出最優(yōu)路徑選擇結果為：成都工業(yè)學院-C-K-G"西南父通大學。對與問題三，結合時間和空間上的相關性，采集足夠多的時刻的車流速度，用神經(jīng)網(wǎng)絡算法可以擬合出該條路時刻關于車流速度的函數(shù)，建立圖論模型分析時間和空間上的相關性。關鍵詞：多目標優(yōu)化圖論模型Dijkstra算法1、問題重述隨著我國交通運輸事業(yè)的迅速發(fā)展，交通擁擠和事故正越來越嚴重的困擾著城市交通。在復雜的交通環(huán)境下，尋找一條可靠、快速、安全的最優(yōu)路徑，已成為所有駕駛員的共識。傳統(tǒng)最優(yōu)

5、路徑問題的研究大多是基于“理想”交通狀況下分析的，景點的最優(yōu)路徑算法都是假設每段路的行駛時間是確定的。但是由于在現(xiàn)實生活中，行車會受到很多不確定性因素的影響，例如：交通事故、惡劣天氣、突發(fā)事件等，車輛的行駛時間存在著不確定性?；谶@種不確定性，討論以下問題：1 .建立數(shù)學模型，定量的分析車輛行駛時間的不確定性，然后給出在不確定性條件下車輛從起點到終點的最優(yōu)路徑的定義和數(shù)學表達式。并將此模型運用到圖1例子中會選哪條路。2 .根據(jù)第一問的定義，設計算法搜索最優(yōu)路徑，并將該算法應用到具體交通網(wǎng)絡中，驗證算法的有效性。3 .交通路段之間的行駛時間的相關性分析。時間上的相關性，對于相同路段不同時間段的相

6、關性；空間上的相關性，相同時間段不同路段的相關性?；蛘邔r間和空間上的相關性綜合起來考慮。2、模型假設1 .假設題目所給數(shù)據(jù)是在大量實驗統(tǒng)計后得到的，數(shù)據(jù)真實可靠;2 .假設題目給出數(shù)據(jù)所用的樣本容量大小相同；3 .假設從起點到到終點時間消耗不超過1小時；4 .假設同一路段上下行的期望時間和標準差時間相同；5 .假設各不同路段的期望時間和標準差時間相對獨立。3、變量說明T.表示從起點（成都工業(yè)學院）到終點（西南交通大學）期望時間；,表示從起點（成都工業(yè)學院）到終點（西南交通大學）標準差時間;Xi：x類指標中的第i個指標；x：x類指標的平均值；X：Xi無量綱化后的指標；:指標權重，改變期望時間和

7、標準差時間重要性的系數(shù)；t:t無量綱化后的指標；:無量綱化后的指標；w:期望時間和標準差時間兩個指標合成的指標；V：頂點集，即題圖給出的AK的點；E：無向弧集；T：無向弧上的期望時間；S：無向弧上的標準差時間；tOk:表示從起點到終點期望時間；為：表示0,1變量，Xj取1時，表示所選路徑經(jīng)過了節(jié)點i到節(jié)點j的路段;不取0時，表示所選路徑?jīng)]有經(jīng)過節(jié)點i到節(jié)點j的路段。ok：從起點到終點標準差時間，其中0表示起點位置標號，k表示終點位置標號；%.是第i種指標的第j個量無量綱化后的量；為：第i種指標的第j個量；Xi表示第i種指標的平均數(shù)；%:從第i個節(jié)點到第j個節(jié)點的期望時間；0:從第i個節(jié)點到第j

8、個節(jié)點的標準差時間；%:%無量綱化后的量；j:ij無量綱化后的量；t:所有的路段的期望時間平均值;一:所有的路段的標準差時間平均值;Wj:由期望時間和標準差時間兩個指標合成的指標。uijd:第i個節(jié)點到第個節(jié)點的那段街的關于d時刻的函數(shù)值，即速度。Tok：表示起點0到j點的最短消耗時間。4、模型準備對最優(yōu)路徑的理解影響實際問題的因素很多，要解決實際問題就要建立適當?shù)臄?shù)學模型，即要把建模對象所涉及的次要因素忽略掉，否則所得模型會因為結構太復雜而失去可解性同時又不能把與實質相關的因素忽略掉，而造成所得模型因為不能足夠正確反映實際情況而失去可靠性。因此需要對實際問題進行抽象、簡化、確定變量和參數(shù)，并

9、應用某些“規(guī)律”建立起變量、參數(shù)間確定的數(shù)學模型。影響路線選擇的因素很多，譬如瞬時車流量、是否有交通事故、車輛狀況等，而實際要解決的是從成都工業(yè)學院到西南交通大學的時間最省路徑，因此車流量和路徑長度成為影響解決本問題的主要因素，而是否有交通事故發(fā)生和車輛狀況等次要因素均可忽略掉。所以最優(yōu)路徑可定義為：實際行車路徑所需期望時間最短且該路徑行車時間的總標準差最小。5、模型的建立與求解問題1模型的建立與求解5.1.1 建模思路問題1要求給出在不確定條件下車輛從起點到終點最優(yōu)路徑的定義和數(shù)學表達式并將此模型應用于例子中，說明選擇哪條路。建立雙目標優(yōu)化模型，再建立優(yōu)化模型，將兩個目標綜合起來考慮，使之變

10、為一個目標。對于問題一和問題二我們在不考慮時間相關性和空間相關性的情況下，我們假設各路段行車的標準差時間相互獨立，由概率的基礎知識可以得知，多個隨機變量相互獨立，多個隨機變量和的標準差就等于各自標準差的和。所以在解決問題一和問題二的時候，在假設標準差時間是相互獨立的情況下，我們將各標準差時間相加作為和的標準差是合理的處理方式。5.1.2 模型建立最優(yōu)路徑的定義：行車所需期望時間最短且該路段行車時間的標準差最小，考慮建立雙目標決策：目標一：總的期望時間最短，即：minT(1)t表示從起點到終點期望時間。目標二：時間波動要小，即要求這個路徑的總標準差要小。min(2)表示從起點到終點標準差時間。5

11、.1.3 模型求解對于多目標，這里用相加合成為單目標，在這之前要進行無量綱化，這里用1均值法無量綱化法，公式如下：Xi二XXi是x類指標中的第i個指標。X是x類指標的平均值，Xi是Xi無量綱化后的指標。經(jīng)過無量綱后，就可以轉換成單目標。w1t(4)這里是指標權重，改變期望時間和標準差時間重要性的系數(shù)，對于不同的人看重的不同，所以這里分別取，和。是無量綱化后的指標，t是t無量綱化后的指標，w是由期望時間和標準差時間兩個指標合成的指標。合成的單目標就為：minw(5)取時，結果：選擇道路A.取時，結果：選擇道路A.取時，結果：選擇道路B.問題2模型的建立與求解5.2.1 建模建立為了可以盡可能快速

12、到達目的地，所以要求這條路徑總期望時間t要短，又考慮到不確定因素的影響，所以要求時間的波動最小，即這條路徑標準差要小。目標一：總的期望時間最短，即：min。；(6)£k表示從起點到終點期望時間，o表示起點位置標號，k表示終點位置標號。NNtoktijxij(7)tj表示節(jié)點i到節(jié)點j的路段期望時間，Xj表示0,1變量，Xj取1時，表示所選路徑經(jīng)過了節(jié)點i到節(jié)點j的路段；Xj取0時，表示所選路徑?jīng)]有經(jīng)過節(jié)點i到節(jié)點j的路段。目標二：時間波動要小，即要求這個路徑的標準差要小。minok;(8)ok表示從起點到終點標準差時間，其中o表示起點位置標號，k表示終點位置標號okij %這里j表示

13、節(jié)點i到節(jié)點j的路段標準差時間，xj表示0,1變量，為取1時,表示所選路徑經(jīng)過了節(jié)點i到節(jié)點j的路段；飛取0時，表示所選路徑?jīng)]有經(jīng)過節(jié)點i到節(jié)點j的路段。約束一：每個節(jié)點最多可以進入一次且最多只可以出去一次。Nxj1(10)Nxj1(11)約束二：由于這里的路徑不必要形成一個圈，所以起點只能出去一次，即進入零次，終點只能進入一次，即出去零次。NXio0(12)NXkj0(13)這里o表示起點位置標號，k表示終點位置標號，Xio表示從第i個節(jié)點是否到起點o的0,1變量，Xio取0時表示第i個節(jié)點不到起點0,Xio取1時表示第i個節(jié)點要到起點o,Xkj表示從終點k是否到第j個節(jié)點的0,1變量，Xk

14、j取0時表示從終點k不到第j個節(jié)點，Xkj取1時表示從終點k要到第j個節(jié)點。min 加；N Ntj Xjmin ok；(14)(15)(16)(17)NNokijXijwokwj Xj(24)Xj1NXj1s.tN(18)Xio0NXkj05.2.2 模型優(yōu)化對于多目標問題難以求解，通過一定關系把多目標合成一單目標，在這之1前，先對這兩個指標進行無量綱化，采用均值法來無量綱化。即：yj(19)yj是第i種指標的第j個量無量綱化后的量，為表示第i種指標的第j個量,X表示第i種指標的平均數(shù)。經(jīng)過以上無量化公式可對t, s無量綱化，即:tijt ljt(20)(21)tj是表示從第i個節(jié)點到第j個節(jié)

15、點的期望時間,是表示從第i個節(jié)點到第j個節(jié)點的標準差時間，tj是tj無量綱化后的量，j是j無量綱化后的量，t是所有的路段的期望時間平均值，是所有的路段的標準差時間平均值。經(jīng)過無量綱化后，就可把雙目標合成單目標，即：wijij1tij(22)這里是指標權重，改變期望時間和標準差時間重要性的系數(shù)，可根據(jù)不同人的需求，取不同的值。wj是由期望時間和標準差時間兩個指標合成的指標。合成的單目標即為：minwok；(23)這里的Wok,其中o表示起點位置標號，k表示終點位置標號，Wok表示從起點到終點合成指標指數(shù)，要求最小。這里Wok表示從起點o到節(jié)點k的最短標準差時間，wj表示從第i個節(jié)點到第j個節(jié)點的

16、路段時間的標準差minwok；（25）NNwokwjXj（26）5.2.3 模型求解這里是從成都工業(yè)學院到西南交通大學，為了方便描述我們對地圖上的節(jié)點標序號（見圖1）圖1路線地圖簡圖根據(jù)圖1所示，即求w°k最小權，節(jié)點o（成都工業(yè)學院）到節(jié)點k（西南交通大學）的最小權。我們用圖論模型求w0k最小值，即：給定一個非空的簡單無向網(wǎng)絡圖G（V,E,W）,其中：V為頂點集，VVi,V2|vn；E為有向弧集，EVi,V2,V2,V3,|）|,V,Vj,W為有向弧上的權值，即合成最優(yōu)指標Wwj1111,這里就可以用Dijkstr算法求W的最小權值。下面計算權W%1111的鄰接矩陣，標準差j111

17、1和期望時間Ttj1111的鄰接矩陣。經(jīng)過公式無量綱化得j和tj則可由下面公式（27）計算Wj1111的鄰接矩陣Wjj1tij(27)這里是權重，表示決策者在標準差j和期望時間tj更看重那一方面。對于不同的人看重的不同，所以這里分別取，和。即為最優(yōu)路線。用matlab程序(見附件1)計算出結果：為時，結果：成都工業(yè)學院一C-K-GA西南交通大學。問題3模型的建立與求解5.3.1 建模思路根據(jù)題的要求，結合時間和空間上的相關性考慮。采集每條路的車流速度。對于每一條路，采集足夠多的時刻的車流速度，用神經(jīng)網(wǎng)絡算法可以擬合出該條路時刻關于車流速度的函數(shù)。同理，擬合出每條路的時刻一車流速度函數(shù)圖，可記著

18、ujd,表示第i個節(jié)點到第j個節(jié)點的那段路的關于時刻d速度函數(shù)圖。這樣，根據(jù)擬合結果，就可以算出某條街某個時刻的車流速度。這樣就可以根據(jù)車流速度計算實時最省時間路線。5.3.2 建模建立根據(jù)歷史數(shù)據(jù)，時間上，根據(jù)對確定的一條路，對每一天的車流速度每十分鐘統(tǒng)計一次的數(shù)據(jù)用神經(jīng)網(wǎng)絡算法可以擬合出時刻關于車流速度的函圖，Ujf(d)(28)ujd是第i個節(jié)點到第j個節(jié)點的那段街的關于d時刻的函數(shù)值，即速度。d是出發(fā)時刻距00:00時刻的分鐘數(shù)。對于空間上，統(tǒng)計了每條路的時間關于車流速度的函數(shù)圖。那么可以算出第i個節(jié)點到第j個節(jié)點的消耗時間。(29)5Ujdtj是第i個節(jié)點到第j個節(jié)點的時間, 根據(jù)每

19、段路的時間向是第i個節(jié)點到第j個節(jié)點的路程。TokN Nt- x j xj(30)min Tok(31)tij表示從第i個節(jié)點到第j個節(jié)點minTok表示示起點0到終點k的最短消耗時間。的路段時間。minTok表示示起點0到終點k的最短消耗時間。(32)(33)(34)(35)minTokNNtijsijUijdToktijxijujf(d)6、模型的分析、推廣與改進路線選擇問題是一個多目標規(guī)劃問題，其中最主要的目標是路線長度最短和道路的暢通概率最大。Dijkstra算法是比較成熟的求非負權網(wǎng)絡最短路問題的算法。目前該模型還存在一些可以改進的方面。第一，不同路段的交通高峰到來的時間不一樣，可以

20、統(tǒng)計出不同路段在不同時刻交通暢通的概率，可以把時間為該模型的一個函數(shù)；第二，這個系統(tǒng)與當?shù)亟痪ш牭慕煌ㄖ笓]系統(tǒng)相連接，可以為某些特種車輛服務，在某路段遇到交通堵塞，可以通過交通管理系統(tǒng)控制信號燈等方式，完成交通調度，以最短的時間保證比如執(zhí)行緊急任務的特種車通過該路段。7、參考文獻1葉宗裕，關于多指標綜合評價中指標正向化和無量綱化方法的選擇，&CurRec=1&recid=&filename=ZJTJ8&dbname=CJFD2003&dbcode=CJFQ&pr=&urlid=&yx=&v=MDAyODhZT1JuRnl

21、2aFc3L01QeWZmWkxHNEh0TE1xNDlGYklSOGVYMUx1eFlTN0RoMVQzcVRyV00xRnJDVVJMK2Y=8、附錄附件1;t=0infinfinfinfinfinfinfinf;0infinfinfinfinfinfinfinf;inf0infinfinfinfinfinf;infinf0infinfinfinfinfinf;infinfinf0infinfinfinf;infinfinf0infinfinf;infinfinfinf0infinfinf;infinfinfinfinfinf0infinf;infinfinfinfinfinf0inf;infinfinfinfinfinfinfinf0;infinfinfinfinfinfinfinf0;s=0infinfinfinfinfinfinfinf;01infinfinfinfinfinfinfinf;inf10infinfinfinfinfinf;infinf0infinfinfinfinfinf;infinfinf0infinfinfinf;infinfinf0infinfinf;infin