2015年五一數(shù)學建模a題不確定性下的最短路徑問題--cumt賴增強

1、2015 年暑期數(shù)學建模培訓第一次模擬 年暑期數(shù)學建模培訓第一次模擬承諾書 承諾書我們仔細閱讀了數(shù)學建模聯(lián)賽的競賽規(guī)則。我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與本隊以外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其它公開的資料（包括網(wǎng)上查到的資料） ，必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭

2、重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們愿意承擔由此引起的一切后果。我們授權數(shù)學建模聯(lián)賽賽組委會，可將我們的論文以任何形式進行公開展示（包括進行網(wǎng)上公示，在書籍、期刊和其他媒體進行正式或非正式發(fā)表等） 。我們參賽選擇的題號為（從 A/B/C 中選擇一項填寫）： 我們的參賽報名號為： 參賽組別（研究生或本科或?？疲罕究扑鶎賹W校（請?zhí)顚懲暾娜┲袊V業(yè)大學南湖校區(qū)參賽隊員 (

3、打印并簽名) ：1. 賴增強2. 蘭衛(wèi)旗3. 李康杰日期：2015 年 8 月 11 日獲獎證書郵寄地址：中國礦業(yè)大學南湖校區(qū)桃 4B5032 郵政編碼：221116收件人姓名：賴增強 聯(lián)系電話：183612308561不確定條件下的最優(yōu)路徑問題摘要本文針對如何在復雜的交通環(huán)境下尋找一條可靠、快速、安全的最優(yōu)路徑的問題，考慮到交通堵塞、惡劣天氣、路途成本等不確定因素對司機路徑選

4、擇的影響，建立多個不確定條件下的最優(yōu)路徑模型。 對于問題一，我們在各個路段所用時間服從正態(tài)分布 N(μ，δ2)的基礎上,建立了在不確定條件下求最短路的 NP 模型，給每個路段設定一個預留到達的時間 t，為了盡可能準確的到達目的地，選取 95%的概率，滿足 P{T≤t}?95%,那么最優(yōu)路徑的定義就是預留時間最小的那個路徑，將其轉換為標準的正態(tài)分 布，通過標準的正態(tài)分布得到了在不確定性條件下車輛從起點到終點預留時間的數(shù)學表達式：t=μ+

5、δ。計算得對應的 t（繞城）=34.645min，t（市區(qū)） Φ ? 1=54.675min，那么最優(yōu)路徑為繞城快速路。對于問題二，在第一問定義的基礎上進一步引入 Bool 系數(shù) ,在搜集得 β(a,k)到的具體的交通網(wǎng)絡中，建立了一個從起點到終點路徑為 的正 ∑na = 1β(a,k)Tlinka態(tài)分布，通過求最小預留時間 t(min)=E[ ]+,得出最優(yōu)路徑 Tpathk Φ ? 1 Var[Tpathk ]的算法。其中 E E[

6、 ]， = [TpathK ] = ∑na = 1β(a,k) Tlinka Var[Tpathk ] ∑na = 1β(a,k)Var[Tlink a，但 的根式不具有線性可加性。不能用經(jīng)典的 dijkstra 算法求解。 ] Var[Tpathk ]對此采用基于雙目標規(guī)劃的思路，利用第 K 短路徑算法，分別對 E[ ]， Tpathk Var[,運用 matlab 編程，找出各自前十條最短路徑。之后在其并集中找出最 Tpat

7、hk ]優(yōu)路徑：V1→V3→V4→V8。由此建立了求最短路的 NPK 模型。最后從時間的漸進性態(tài)上分析模型的復雜性和收斂性。對于問題三，我們只考慮各路段空間上的相關性，并用概率論中的協(xié)方差 來表示這種耦合關系，建立了 NPK 模型。得出可靠時間的數(shù)學表達式 t= E+ ；求解得最優(yōu)路徑： [TpathK ] Φ ? 1(ρ) ∑na = 1δ(a,k)Var[Tlinka + ∑na = 2cov(a ? 1,a)V1->V