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

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

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

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

4、出最優(yōu)路徑的定義和數(shù)學(xué)表達式。將這兩個目標相加合成單目標。利用MATLAB編程求解，將所建模型應(yīng)用到例子中，得出的結(jié)論是：選擇道路A。 對于問題二，在問題一定義的最優(yōu)路徑的基礎(chǔ)上，建立圖論模型，應(yīng)用Dijkstra算法，利用MATLAB編程，得出最優(yōu)路徑選擇結(jié)果為：成都工業(yè)學(xué)院CKG西南交通大學(xué)。 對與問題三，結(jié)合時間和空間上的相關(guān)性，采集足夠多的時刻的車流速度，用神經(jīng)網(wǎng)絡(luò)算法可以擬合出該條路時刻關(guān)于車流速度的函數(shù)，建立圖論模型分析時間和空間上的相關(guān)性。關(guān)鍵詞：多目標優(yōu)化 圖論模型 Dijkstra算法 1、問題重述 隨著我國交通運輸事業(yè)的迅速發(fā)展，交通擁擠和事故正越來越嚴重的困擾著城市交通。

5、在復(fù)雜的交通環(huán)境下，尋找一條可靠、快速、安全的最優(yōu)路徑，已成為所有駕駛員的共識。傳統(tǒng)最優(yōu)路徑問題的研究大多是基于“理想”交通狀況下分析的，景點的最優(yōu)路徑算法都是假設(shè)每段路的行駛時間是確定的。但是由于在現(xiàn)實生活中，行車會受到很多不確定性因素的影響，例如：交通事故、惡劣天氣、突發(fā)事件等，車輛的行駛時間存在著不確定性?；谶@種不確定性，討論以下問題： 1.建立數(shù)學(xué)模型，定量的分析車輛行駛時間的不確定性，然后給出在不確定性條件下車輛從起點到終點的最優(yōu)路徑的定義和數(shù)學(xué)表達式 。并將此模型運用到圖1例子中會選哪條路。2.根據(jù)第一問的定義，設(shè)計算法搜索最優(yōu)路徑，并將該算法應(yīng)用到具體交通網(wǎng)絡(luò)中，驗證算法的有效

6、性。3.交通路段之間的行駛時間的相關(guān)性分析。時間上的相關(guān)性，對于相同路段不同時間段的相關(guān)性；空間上的相關(guān)性，相同時間段不同路段的相關(guān)性。或者將時間和空間上的相關(guān)性綜合起來考慮。 2、模型假設(shè)1.假設(shè)題目所給數(shù)據(jù)是在大量實驗統(tǒng)計后得到的，數(shù)據(jù)真實可靠；2.假設(shè)題目給出數(shù)據(jù)所用的樣本容量大小相同；3.假設(shè)從起點到到終點時間消耗不超過1小時；4.假設(shè)同一路段上下行的期望時間和標準差時間相同；5.假設(shè)各不同路段的期望時間和標準差時間相對獨立。3、變量說明 ：表示從起點（成都工業(yè)學(xué)院）到終點（西南交通大學(xué)）期望時間； ：表示從起點（成都工業(yè)學(xué)院）到終點（西南交通大學(xué)）標準差時間； ：類指標中的第個指標；

7、 ：類指標的平均值； ：無量綱化后的指標； ：指標權(quán)重，改變期望時間和標準差時間重要性的系數(shù)； ：無量綱化后的指標； ：無量綱化后的指標； ：期望時間和標準差時間兩個指標合成的指標； ：頂點集，即題圖給出的AK的點； ：無向弧集； ：無向弧上的期望時間； ：無向弧上的標準差時間； :表示從起點到終點期望時間； :表示0，1變量，取1時，表示所選路徑經(jīng)過了節(jié)點到節(jié)點的路段；取0時，表示所選路徑?jīng)]有經(jīng)過節(jié)點到節(jié)點的路段。 ：從起點到終點標準差時間，其中0表示起點位置標號，k表示終點位置標號； ：是第種指標的第個量無量綱化后的量; ：第種指標的第個量; 表示第種指標的平均數(shù); :從第個節(jié)點到第個節(jié)點

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

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

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

11、.3模型求解 對于多目標，這里用相加合成為單目標，在這之前要進行無量綱化，這里用均值法無量綱化法，公式如下： 是類指標中的第個指標。是類指標的平均值，是無量綱化后的指標。 經(jīng)過無量綱后，就可以轉(zhuǎn)換成單目標。 是指標權(quán)重，改變期望時間和標準差時間重要性的系數(shù)，對于不同的人看重的不同，所以這里分別取0.2,0.5和0.8。是無量綱化后的指標，是無量綱化后的指標，是由期望時間和標準差時間兩個指標合成的指標。 合成的單目標就為：取0.2時，結(jié)果：選擇道路A.取0.5時，結(jié)果：選擇道路A.取0.8時，結(jié)果：選擇道路B.5.2問題2模型的建立與求解5.2.1建模建立 為了可以盡可能快速到達目的地，所以要求

12、這條路徑總期望時間要短，又考慮到不確定因素的影響，所以要求時間的波動最小，即這條路徑標準差要小。目標：總的期望時間最短，即： 表示從起點到終點期望時間，表示起點位置標號，k表示終點位置標號。 表示節(jié)點到節(jié)點的路段期望時間，表示0，1變量，取1時，表示所選路徑經(jīng)過了節(jié)點到節(jié)點的路段；取0時，表示所選路徑?jīng)]有經(jīng)過節(jié)點到節(jié)點的路段。 目標二：時間波動要小，即要求這個路徑的標準差要小。表示從起點到終點標準差時間，其中表示起點位置標號，k表示終點位置標號。這里表示節(jié)點到節(jié)點的路段標準差時間，表示0，1變量，取1時，表示所選路徑經(jīng)過了節(jié)點到節(jié)點的路段；取0時，表示所選路徑?jīng)]有經(jīng)過節(jié)點到節(jié)點的路段。約束一：

13、每個節(jié)點最多可以進入一次且最多只可以出去一次。約束二：由于這里的路徑不必要形成一個圈，所以起點只能出去一次，即進入零次，終點只能進入一次，即出去零次。 這里表示起點位置標號，k表示終點位置標號，表示從第個節(jié)點是否到起點的0,1變量，取0時表示第個節(jié)點不到起點，取1時表示第個節(jié)點要到起點，表示從終點是否到第個節(jié)點的0,1變量，取0時表示從終點不到第個節(jié)點，取1時表示從終點要到第個節(jié)點。 綜上：5.2.2模型優(yōu)化 對于多目標問題難以求解，通過一定關(guān)系把多目標合成一單目標，在這之前，先對這兩個指標進行無量綱化，采用均值法來無量綱化。即： 是第種指標的第個量無量綱化后的量，表示第種指標的第個量，表示第

14、種指標的平均數(shù)。經(jīng)過以上無量化公式可對，無量綱化，即： 是表示從第個節(jié)點到第個節(jié)點的期望時間，是表示從第個節(jié)點到第個節(jié)點的標準差時間，是無量綱化后的量，是無量綱化后的量，是所有的路段的期望時間平均值，是所有的路段的標準差時間平均值。經(jīng)過無量綱化后，就可把雙目標合成單目標，即： 是指標權(quán)重，改變期望時間和標準差時間重要性的系數(shù)，可根據(jù)不同人的需求，取不同的值。是由期望時間和標準差時間兩個指標合成的指標。 合成的單目標即為：這里的，其中表示起點位置標號，k表示終點位置標號，表示從起點到終點合成指標指數(shù)，要求最小。這里表示從起點到節(jié)點的最短標準差時間，表示從第個節(jié)點到第個節(jié)點的路段時間的標準差。綜上

15、：5.2.3模型求解這里是從成都工業(yè)學(xué)院到西南交通大學(xué)，為了方便描述我們對地圖上的節(jié)點標序號（見圖1）圖1 路線地圖簡圖根據(jù)圖1所示，即求最小權(quán)，節(jié)點（成都工業(yè)學(xué)院）到節(jié)點（西南交通大學(xué)）的最小權(quán)。我們用圖論模型求最小值，即：給定一個非空的簡單無向網(wǎng)絡(luò)圖，其中：為頂點集，；為有向弧集，為有向弧上的權(quán)值，即合成最優(yōu)指標，這里就可以用Dijkstr算法求的最小權(quán)值。下面計算權(quán)的鄰接矩陣，標準差和期望時間的鄰接矩陣。經(jīng)過公式無量綱化得和則可由下面公式（27）計算出的鄰接矩陣。是權(quán)重，表示決策者在標準差和期望時間更看重那一方面。對于不同的人看重的不同，所以這里分別取0.2,0.5和0.8。即為最優(yōu)路線

16、。用matlab程序（見附件1）計算出結(jié)果：為0.5時，結(jié)果：成都工業(yè)學(xué)院CKG西南交通大學(xué)。5.3問題3模型的建立與求解5.3.1建模思路 根據(jù)題的要求，結(jié)合時間和空間上的相關(guān)性考慮。采集每條路的車流速度。對于每一條路，采集足夠多的時刻的車流速度，用神經(jīng)網(wǎng)絡(luò)算法可以擬合出該條路時刻關(guān)于車流速度的函數(shù)。同理，擬合出每條路的時刻車流速度函數(shù)圖，可記著，表示第個節(jié)點到第個節(jié)點的那段路的關(guān)于時刻速度函數(shù)圖。這樣，根據(jù)擬合結(jié)果，就可以算出某條街某個時刻的車流速度。這樣就可以根據(jù)車流速度計算實時最省時間路線。5.3.2建模建立 根據(jù)歷史數(shù)據(jù)，時間上，根據(jù)對確定的一條路，對每一天的車流速度每十分鐘統(tǒng)計一次

17、的數(shù)據(jù)用神經(jīng)網(wǎng)絡(luò)算法可以擬合出時刻關(guān)于車流速度的函圖， 是第個節(jié)點到第個節(jié)點的那段街的關(guān)于時刻的函數(shù)值，即速度。是出發(fā)時刻距00:00時刻的分鐘數(shù)。對于空間上，統(tǒng)計了每條路的時間關(guān)于車流速度的函數(shù)圖。那么可以算出第個節(jié)點到第個節(jié)點的消耗時間。 是第個節(jié)點到第個節(jié)點的時間，是第個節(jié)點到第個節(jié)點的路程。根據(jù)每段路的時間 表示示起點0到終點的最短消耗時間。表示從第個節(jié)點到第個節(jié)點的路段時間。表示示起點0到終點的最短消耗時間。綜上：6、模型的分析、推廣與改進 路線選擇問題是一個多目標規(guī)劃問題，其中最主要的目標是路線長度最短和道路的暢通概率最大。Dijkstra算法是比較成熟的求非負權(quán)網(wǎng)絡(luò)最短路問題的算

18、法。 目前該模型還存在一些可以改進的方面。第一，不同路段的交通高峰到來的時間不一樣，可以統(tǒng)計出不同路段在不同時刻交通暢通的概率，可以把時間為該模型的一個函數(shù)；第二，這個系統(tǒng)與當(dāng)?shù)亟痪ш牭慕煌ㄖ笓]系統(tǒng)相連接，可以為某些特種車輛服務(wù)，在某路段遇到交通堵塞，可以通過交通管理系統(tǒng)控制信號燈等方式，完成交通調(diào)度，以最短的時間保證比如執(zhí)行緊急任務(wù)的特種車通過該路段。7、參考文獻1 葉宗裕，關(guān)于多指標綜合評價中指標正向化和無量綱化方法的選擇，8、附錄附件1；t=0 0.826 inf inf inf inf 1.37 inf inf inf inf;0.826 0 1.661 inf inf inf in

19、f inf inf inf inf;inf 1.661 0 1.242 inf 1.476 inf inf inf inf inf;inf inf 1.242 0 1.104 inf inf inf inf inf inf;inf inf inf 1.104 0 1.288 inf inf inf inf 2.44;inf inf 1.476 inf 1.288 0 1.586 inf 2.824 inf inf;1.37 inf inf inf inf 1.586 0 1.984 inf inf inf;inf inf inf inf inf inf 1.984 0 1.802 inf in

20、f;inf inf inf inf inf 2.824 inf 1.802 0 0.94 inf;inf inf inf inf inf inf inf inf 0.94 0 0.55;inf inf inf inf 2.44 inf inf inf inf 0.55 0;s=0 0.5 inf inf inf inf 0.4 inf inf inf inf;0.5 0 1 inf inf inf inf inf inf inf inf;inf 1 0 0.5 inf 0.8 inf inf inf inf inf;inf inf 0.5 0 0.6 inf inf inf inf inf inf;inf inf inf 0.6 0 0.5 inf inf inf inf 0.7;inf inf 0.8 inf 0.5 0 0.6 inf 0.7 inf inf;0.4 inf inf inf inf 0.6 0 0.7 inf inf inf;inf inf inf inf inf inf 0.7 0 0.3 inf inf;inf inf inf inf inf 0.7 inf 0.3 0 0.3 inf;inf inf inf inf inf inf inf inf 0.3 0 0.16;inf inf inf inf 0