05年美國大學(xué)生數(shù)學(xué)建模競賽B題特等獎?wù)撐姆g.pdf

2005 年年 B 題題 公路收費(fèi)亭的設(shè)置公路收費(fèi)亭的設(shè)置 諸如美國新澤西州的風(fēng)景區(qū)干道 95 號州際公路等交通繁忙的收費(fèi) 公路都是多車道的交通干線 每隔一定距離設(shè)有過路費(fèi)收費(fèi)區(qū) 由于 收取過路費(fèi)一般是不得人心的 因此通過限制由于過路費(fèi)收費(fèi)區(qū)造成 的交通混亂把駕車人的煩惱減到極小是很值得做的 通常 收費(fèi)區(qū)內(nèi) 收費(fèi)亭的數(shù)目遠(yuǎn)多于進(jìn)入過路費(fèi)收費(fèi)區(qū)的車道數(shù) 進(jìn)入過路費(fèi)收費(fèi)區(qū) 時 車流扇形散開分流 分別在各個收費(fèi)亭交費(fèi) 離開收費(fèi)區(qū)時 車 流又會匯合到和進(jìn)入收費(fèi)區(qū)時一樣多的車道離開 因此 在交通繁忙 時 通行的車輛會在離開收費(fèi)區(qū)時出現(xiàn)擁塞 更嚴(yán)重的時候 收費(fèi)站 的入口也會出現(xiàn)擁堵 1 g 試構(gòu)建一個模型 用來決定攔路過路費(fèi)收費(fèi)區(qū)內(nèi)收費(fèi)亭的最優(yōu)數(shù) 目的配置 明確考慮如下情景 即在進(jìn)來的每個車道恰好只有一個收 費(fèi)亭 在什么情況下你制訂的方案要比現(xiàn)有的方案效率多少要高一點 注意 最優(yōu) 的定義要由你自己來決定 論文 論文 收費(fèi)亭為誰而收費(fèi)收費(fèi)亭為誰而收費(fèi) 一 一 摘要摘要 我們運(yùn)用排隊理論和元胞自動機(jī)的結(jié)合 對收費(fèi)站附近的交通情 況進(jìn)行建模 從而決定收費(fèi)亭的最優(yōu)數(shù)量 我們假設(shè)到達(dá)收費(fèi)站的汽 車數(shù)量服從泊松分布 并且汽車離開收費(fèi)站的概率是無記憶的 這使 得我們能夠把等待收費(fèi)窗口開放的車輛作為 MIMIn 隊列進(jìn)行完整的 分析和描述 然后我們使用改進(jìn)的 NS 細(xì)胞自動機(jī)方案為等待進(jìn)入收 費(fèi)站和離開收費(fèi)站回到高速公路上的汽車構(gòu)建模型 該模型得到了非 常一致的結(jié)果 并對模擬的結(jié)論進(jìn)行了驗證 我們用 NS 模型測量了 車輛在收費(fèi)站等待的平均時間 并根據(jù)這個結(jié)果證實了一個通過選擇 收費(fèi)亭數(shù)目使得等待時間最少的一般方法 對 于 2 通道的高速公路來 說 收費(fèi)亭的最優(yōu)數(shù)量是 4 對于 3 通道的高速公路來說 最優(yōu)數(shù)量 是 6 對于更多通道的高速公路 結(jié)果取決于車輛到達(dá)率 我們的模型建立在大量的理論和實驗基礎(chǔ)上 其一致性表明它是 準(zhǔn)確和強(qiáng)大的 排隊論得到的結(jié)果和 NS 模型得到的結(jié)果也具有高度 的一致性 并且我們 NS 模型結(jié)果的一些特殊案例在一些文獻(xiàn)中的經(jīng) 驗數(shù)據(jù)中得到了證實 此外 改變收費(fèi)站等待時間的分布和改變隨機(jī) 制動的概率 并不會有效的改變我們的方案建議 這為我們的模型和 一般方法提供了一個令人信服的證明 二 二 簡介簡介 收費(fèi)站通過兩種方式使車輛減速 1 如果沒有足夠多的收費(fèi)亭 車輛就會形成排隊的情況 2 如果收費(fèi)站過多 車輛合并到窄的高速公路時又會造成擁堵 我們用排隊論來預(yù)測車輛在得到一個收費(fèi)亭服務(wù)之前需要等待多長 時間 通過用元胞自動機(jī)構(gòu)建單個車輛模型 我們證實了對等待時間 的預(yù)測 車輛 水平模型被用來預(yù)測車輛離開收費(fèi)站后如何合流 三 三 初始假設(shè)初始假設(shè) 1 最佳系統(tǒng)使得平均等待時間最少 我們不考慮收費(fèi)亭運(yùn)作時的時 間損耗 2 車輛到達(dá)收費(fèi)站在時間上符合一致性 并且時間間隔服從參數(shù)為 的指數(shù)分布 交通高峰時間段我們可以變動參數(shù) 3 車輛在收費(fèi)亭前的等待時間是無記憶性的 服從參數(shù)為 的指數(shù)分 布 這個假設(shè)在海爾對收費(fèi)站的研究中得到證實 4 汽車之間不加以區(qū)分 所有車輛具有相同的長度和最大速度 5 收費(fèi)站附近沒有斜坡或出口 我們不考慮額外車輛進(jìn)入的可能性 只考慮已經(jīng)在主道路上的車輛 雙向公路等同于兩條獨立的公路 我們只考慮已經(jīng)劃分好的公路 四 四 由于收費(fèi)亭由于收費(fèi)亭太少而造成的延遲太少而造成的延遲 1 符合符合 M M n 隊列隊列的收費(fèi)亭的收費(fèi)亭 當(dāng)一輛汽車到達(dá)收費(fèi)站時 有 n 個收費(fèi)亭可供選擇為自己服務(wù) 車輛趨向于可到達(dá)的最短的隊列 我們通過假設(shè)所有車輛形成一個單 一的隊列來簡化排隊行為 當(dāng) n 個收費(fèi)亭中的一個可用時隊列中的下 一輛車馬上就會到達(dá) 然而真實系統(tǒng)的效率是比較低的 因此我們要 在一個更詳細(xì)的仿真模擬中預(yù)測多次 我們假設(shè)車輛在一個均勻分布 的時間里到達(dá) 另外 我們假設(shè)服務(wù)時間的分布服從指數(shù)分布 這類 模型被稱為無記憶到達(dá) 無記憶服務(wù)時間 n 個收費(fèi)亭提供服務(wù)獲或 者稱之為 M M n 隊列 圖 1 M M n 隊列 車輛到達(dá)率為 服務(wù)率為 p 我們定義 X t 為在時間 t 的時候正在隊伍中等待或正在收費(fèi)亭的 汽車數(shù)目 我們還定義了固定的概率 pk 就是在固定的狀態(tài)下 隊伍具有長度 k 的概率為 pk 通過 M M n 隊列的輸入輸出關(guān)系 固定概率必須滿足 此系統(tǒng)的解決方法是 其中 令隨機(jī)變量 W 為一輛汽車在這個系統(tǒng)中花費(fèi)的時間 排隊時間 在收費(fèi)亭停留的時間 W 的期望值分布如下 這個結(jié)果描述了這個一般問題的第一部分 汽車如何排隊取決于 收費(fèi)亭的數(shù)目 n 為了建立通過收費(fèi)亭后車輛合流的模型 描述汽車 如何離開 M M n 隊列顯得尤為重要 此隊列的輸出時間服從以 為參數(shù)的指數(shù)分布 并且輸出過程和 輸入過程具有相同的分布 根據(jù)無記憶概率的性質(zhì) 離開時間間隔是 相互獨立的 我們定義 D 為在時間間隔 t 內(nèi)離開收費(fèi)廳的汽車數(shù)量 那么 d 輛汽車在這個時間段內(nèi)離開的概率為 其中 是在 t 時間段內(nèi)到達(dá)收費(fèi)亭的汽車的平均數(shù) M M n 隊列提供了一個簡單并且成熟的收費(fèi)站模型 尤其是可 以知道平均等待時間和輸出過程 并且允許我們變動仿真結(jié)果 2 M M n 隊列的局限性隊列的局限性 雖然有用 但 M M n 隊列是不完整的 并且過分簡化了問題 雖 然隊列可以讓我們簡單的找到車輛離開的時間分布 但它的假設(shè)條件 導(dǎo)致它不會是一個完整的解決辦法 通過使用單隊列理論 我們假設(shè) 任何車輛可以到達(dá)任何一個收費(fèi)亭 這樣就顯得過分樂觀啦 尤其是 當(dāng)交通流量比較大的時候 我們希望我們的預(yù)測對低密度車流是行之 有效的 或許 最重要的是 隊列只是模擬了問題的一半 在收費(fèi)亭 前等待的時間 五 五 用元寶自動機(jī)構(gòu)建交通模型用元寶自動機(jī)構(gòu)建交通模型 1 概述概述 復(fù)雜的交通系統(tǒng)可以根據(jù)簡單的自動機(jī)進(jìn)行建模 我們在一個微 觀的層面上用元胞自動機(jī)構(gòu)建交通流模型 在這個方案里 我們在離 散的空間和時間里引進(jìn)汽車依據(jù)一些細(xì)小的規(guī)則運(yùn)作的情況 元胞自動機(jī)在進(jìn)行一些具體問題的仿真時很適合 因為在收費(fèi)站 有很多單獨的車輛 他們之間都在相互作用 連續(xù)的或宏觀的模型無 法捕捉到它們之間的相互作用 并且也無法知道它們在到達(dá)收費(fèi)亭之 前和離開收費(fèi)亭之后自發(fā)形成的交通堵塞所扮演的角色 我們首先構(gòu)建了一個單通道高速公路模型 然后把支付通行費(fèi)所 造成的時間耽擱加進(jìn)去 在單車道的仿真中 我們可以讓沒有通過的 車輛在停止的車輛之后聚集并且排成隊列 我們可以把這個模型擴(kuò)展 到多車道的系統(tǒng)模型 在道路進(jìn)入或離開一個收費(fèi)站的多車道系統(tǒng)中 車道的數(shù)量是不連續(xù)的 2 單車道單車道 NS 交通模型交通模型 大多數(shù)用來仿真交通的自動機(jī)是 NS 元胞自動機(jī)模型的一般化 NS 模型是用來仿真交通流的標(biāo)準(zhǔn)工具 并且也已經(jīng)被證實和實際結(jié) 果相吻合 我們使用這種自動機(jī)創(chuàng)建一個數(shù)值模型來證明排隊理論的預(yù)測 在 NS 模型中 一輛汽車被一個整數(shù)位置 x 和整數(shù)速度 v 代表 這些 汽車的移動情況由它們的速度 xn xn vn來決定 該系統(tǒng)通過以下的程 序發(fā)展 3 NS 算法算法 圖 2 NS 算法的規(guī)律 1 加速 如果汽車能夠在不超過最大速度 vmax的情況下加速 那 么他的速度增加單位一 vn vn 1 否則該汽車具有一個恒定的速 vn 2 防止碰撞 如果前車和后車之間的距離 dn小于或等于 vn 那么 第 n 輛車如果不減速的話將會發(fā)生碰撞 然后 vn dn 1 3 隨機(jī)減速 汽車經(jīng)常會因為一些非交通因素減速 如接電話 打翻了咖啡杯 甚至是筆記本電腦 這時候司機(jī)會做一些非理性的 選擇 我們假設(shè)這種情況發(fā)生的概率為 pbrake 導(dǎo)致速度 vn vn 1 假 設(shè) vn 0 4 車輛嘗試合并 如果它的正向路徑受阻擋 dR 0 車輛隨機(jī) 選擇預(yù)定的方向 向左或者向右 如果該預(yù)定的方向上被阻止 這輛 車在另一個方向上移動 除非兩個方向都被阻止 汽車被包圍 這 是符合邊界限制的 也和李凱爾特等人所提出的規(guī)則是一致的 1996 我們選擇的單元格大小為 7 5m 以匹配 NS 模型 因為一般汽 車所具有的最大速度位于 30 35m s 簡單起見 我們還使用了周期性 的邊界條件 我們選擇 Vmax 5 m s 以使得耽擱時間段接近于 1s 然 后我們放棄了這些邊界條件 因為開放條件下的泊松發(fā)生器和接收器 和 M M n 隊列相吻合 此外 研究結(jié)果表明周期性邊界可能過分簡 化了汽車的分布情況 我們在一個給定車輛密度的初始狀態(tài)下應(yīng)用了這個算法 這個系 統(tǒng)是在給定每個單元格被占用的概率為 c 的條件下創(chuàng)建的 也就是汽 車密度參數(shù) 這和格林和格里菲斯的方法相吻合 NS 模型所得到的結(jié)果和哈利所援引的典型案例比較相似 在圖 3 中 系統(tǒng)在時間段 i 的狀態(tài)被畫在第 i 列 白色像素處表示有汽車 黑色像素處是開放的空間 這兩幅圖都顯示了被擁堵的車輛打斷的一 般的連續(xù)汽車流 a NS 模型的結(jié)果 c 0 2 p 0 25 b 喬杜里的結(jié)果 圖 3 兩個模型的典型結(jié)果 4 NS 模型的性能及支持模型的性能及支持 單車道 NS 模型是前后一致 靈活的 并符合已知的經(jīng)驗數(shù)據(jù) NS 模型的一些屬性是可以預(yù)測分析的 內(nèi)格爾赫爾曼 1993 年 我們使用這些信息以及實驗結(jié)果來測試我們的模型 在極限情況下的 隨機(jī)制動概率為零 這對車輛巡航是可能的 在這種狀態(tài)下車輛總是 以最大速度運(yùn)動 相應(yīng)的流量為 J cvmax 只有空間足夠時這才是有 可能的 一旦 孔的密度 或者給剩余空間賦予 1 c 值 小于這個流 量的時候 自由空間的缺乏就會限制車輛的速度 流量和密度之間的 關(guān)系式為 J c min cvmax 1 c 1 其中 J 是的汽車的流量 即單位時間內(nèi)通過一個單元格的汽車數(shù)量 c 是汽車的密度 我們在 pbrake 0 的條件下讓 NS 自動機(jī)運(yùn)行 20 次 在 平均值和理論值之間達(dá)到良好的一致性 如圖 4 這個圖雖然美觀 但它只是表明該模型是一致的并且可以近似 得到 并不表明它能代表一個真實的系統(tǒng) 我們查閱了車流量的經(jīng)驗 數(shù)據(jù) 如圖 5b 顯然 NS 模型是已知數(shù)據(jù)的準(zhǔn)確近似 另外 也可以使用平均場理論來描述 NS 模型 即使 Pbrake 0 Vmax 1 的情況用這項技術(shù)也可以得到解決 對于我們的系統(tǒng) Vmax 5 這使得計算上比較困難 5 添加延遲添加延遲 延遲防止周期性邊界條件的使用 為了模擬與收費(fèi)站的遭遇 我們必須增加一個延遲的通暢系統(tǒng) 西蒙和內(nèi)格爾針對堵塞情況構(gòu)建了 NS 模型 但只有一個固定的延遲 時間概率 我們假設(shè)服務(wù)時間服從指數(shù)分布 概率為 1 exp t 任何一個收費(fèi)站在 t 時間內(nèi)能夠完成服務(wù) 所以我們也使用這個假 設(shè)在我們的 NS 模型中描述延遲的情況 引進(jìn)這種延遲時創(chuàng)建了一個不對稱的問題 屏障右側(cè)的車輛必須 繞一圈才能夠到達(dá) 收費(fèi)亭 而左邊的車輛將會立即影響它 因此 我們在車道的四分之一和四分之三行車線上測量汽車流量 如圖 6 圖 6 中的基本關(guān)系圖 證實了我們關(guān)于汽車流量和瓶頸 收費(fèi)亭 的相互關(guān)系的直覺 因為相對較低的車流密度 和四分之三行車線處 相比較四分之一行車線處的車流量出現(xiàn)下滑 這超越了瓶頸 因此 繁忙的交通流入 使得車輛比在通過收費(fèi)亭后更快的聚集成隊列 這些基本的關(guān)系圖顯示周期邊界條件并不適合這種計算 在周期 邊界的情況下 隊列的輸入速率受限制于環(huán)繞在其右側(cè)的車輛 較小 流量 這并不代表真實的交通堵塞 在沒有周期邊界的條件下 堵塞 無法影響他們上游的車輛流量 六 六 模擬完整系統(tǒng)模擬完整系統(tǒng) 1 多車道多車道情況情況 通過對單車道自動機(jī)添加一個新的規(guī)則 我們可以建立多車道公 路模型 我們使用單車道模型以確保我們的自動機(jī)是現(xiàn)實世界的一個 合適代表 但實際問題是多車道的 雙車道模型的研究比單車道模型 要少 多車道模型更加罕見 喬杜里 2000 年 納格爾 1998 年凱爾 特 1996 年 我們通過擴(kuò)展自動機(jī)的規(guī)則設(shè)置來描述車道的變化情況 使用增加了一個規(guī)則的單車道 NS 模型來研究多車道模型 2 改變公路形狀改變公路形狀 通過使用多車道自動機(jī) 我們可以建立具有現(xiàn)實中車道變換行為 的多車道公路模型 然而 這仍然不能實現(xiàn)公路與收費(fèi)亭的數(shù)量之間 的過渡 若要建立收費(fèi)站 我們引入多個邊界強(qiáng)制自動機(jī)來改變車道 以 避免觸及邊界 邊界勾勒出從高速公路延伸出往返于一個更大的收費(fèi) 站的斜坡邊緣的輪廓 圖 8 這是這種模式不一般的惟一方面 通過引入不同的邊界 我們可以輕松地模擬不同的問題 為了模擬在 收費(fèi)亭的等待情況 就像在單車道情況中那樣 我們還在中心位置添 加了一個延遲 以前的模型假設(shè)路面的寬度是固定的 也就是說車道數(shù)量不會 改變 通過限制道路的幾何形狀來表示收費(fèi)站 請注意圖 8 中的 鉆 石 形狀 并引入從收費(fèi)站離開合流的行為 我們在沒有做額外假設(shè) 的前提下增加了模型的靈活性 七 七 MIMIn 隊列和隊列和 NS 模型的一致性模型的一致性 MIMIn 隊列是一種理想化的系統(tǒng) 它預(yù)測的時間比實際收費(fèi)站 的等待時間短 因為它沒有考慮隊列 圖 9 中效率低下的問題 但 是 MIMIn 隊列能夠預(yù)測正確的分配 此外 MIMIn 隊列的穩(wěn)定性和 NS 模型的穩(wěn)定性也有很大的不同 如果 n MIMIn 隊列可以達(dá) 到穩(wěn)定狀態(tài) 為到達(dá)率 為服務(wù)率 n 為收費(fèi)亭的數(shù)量 我們注 意到在對 NS 模型進(jìn)行仿真模擬的時候 收費(fèi)站前的車輛會積累的越 來越多 甚至相應(yīng)的 MIMIn 隊列處于穩(wěn)定狀態(tài)時也是如此 盡管存在這些明顯的不一致 但是在排隊論預(yù)測和觀測的結(jié)果之 間存在著非常強(qiáng)有力的一致性 從排隊論分析 我們知道離開收費(fèi)站 的汽車數(shù)量的概率分布為 P D d e t d t d 這個方程提供了關(guān)于隊列的大量信息 并且這個概率在元胞自動機(jī)模 型中可以很容易的被測量出來 我們比較圖 10 中的模擬和理論概率 的分布 這兩個分布是非常相似的 他們的差異會變得越來越小 在 經(jīng)過104次的迭代后要比 NS 模型的小 2 八 八 時間自動機(jī)模型預(yù)測時間自動機(jī)模型預(yù)測 1 收費(fèi)亭收費(fèi)亭的最優(yōu)數(shù)量的最優(yōu)數(shù)量 收費(fèi)亭的最優(yōu)配置能最大限度地減少等待時間 所以為了確定正 確的收費(fèi)亭數(shù)量 我們需要測量車輛進(jìn)入收費(fèi)站排隊等候然后離開收 費(fèi)站重新回到告訴公路上的平均時間 我們通過跟蹤自動機(jī)來確定從 進(jìn)入到離開該系統(tǒng)的平均時間 1 計算平均時間計算平均時間 通過我們系統(tǒng)所需的平均時間取決于到達(dá)率 控制擁堵 車 道 數(shù)量 以及收費(fèi)亭數(shù)量 我們認(rèn)為平均服務(wù)速率是固定的 為 5 秒 海爾使用 9 秒 1963 不過 雖然改變服務(wù)率確實改變平均時間的長 短 但這種變化并不影響 n 的最佳值 我們把進(jìn)入車道數(shù)固定為 k 并且搜索到收費(fèi)亭的數(shù)量 n 車輛到 達(dá)率為 對于不同的 n 和 值我們運(yùn)用元胞自動機(jī)模型計算平均等 待時間 并且我們是在一個比較長的時間段內(nèi)計算平均等待時間 以 消除瞬態(tài)效應(yīng) 不過 這些范圍應(yīng)該是什么 我們假定 n 不大于車道數(shù)的三或四 倍 我們之所以增加這個限制 是因為我們注意到當(dāng) n 遠(yuǎn)大于 1 的時 候等待時間會劇烈增加 的范圍應(yīng)該由常識性的限制來決定 如果 是在一個時間段內(nèi)到達(dá)的汽車的平均數(shù) 則 不應(yīng)超過交通流入的 車道數(shù)量 因為這是道路的物理容量 2 2 車道的最優(yōu)車道的最優(yōu)結(jié)果結(jié)果 我們允許 n 的范圍從 2 到 8 變化 的范圍從 0 到 2 變化 我們 在圖 11 中根據(jù) n 和 的值繪制了平均時間圖 在該圖中 最小值很明 確地落在 n 4 這條線上 即使對于不同的 值也是如此 這表明 即使對于不同的到達(dá)率 最優(yōu)的收費(fèi)亭數(shù)量也是 4 這是一個非常穩(wěn) 定的解決方案 不需要改變車輛流量率 至少對典型值來說是這樣的 雖然 4 是收費(fèi)亭的最佳數(shù)目 2 也非常接近最優(yōu) 但 3 這個結(jié)果非常 差 n 3 時 額外的增加的這個車道造成了更嚴(yán)重的交通堵塞 對 于小的n值 收費(fèi)亭數(shù)量比車道數(shù)多1時 等待時間是局部的最大值 3 3 車道的最優(yōu)結(jié)果車道的最優(yōu)結(jié)果 通過改變 從 0 6 至 2 7 和 n 從 3 9 我們發(fā)現(xiàn) 當(dāng)最小值出現(xiàn) 時 對再次獨立的 n 6 圖 12 圖 11 對于一個兩車道系統(tǒng) 設(shè)置 4 個收費(fèi)站時 時間最短 圖 圖 12 對于三車道系統(tǒng) 設(shè)置 6 個收費(fèi)站時 時間最短 2 多車道情況多車道情況 迄今為止的結(jié)果表明最優(yōu)的收費(fèi)亭數(shù)量總是兩倍于進(jìn)入車道的 數(shù)量 不幸的是 四條車道的情況推翻了這種猜測 對于不同的到達(dá) 率 最優(yōu)收費(fèi)亭數(shù)量會發(fā)生改變 對一個小的 來說 n 從 6 開始變 化 收費(fèi)亭的擁有者可以測量交通流量 然后根據(jù)需要開啟或關(guān)閉收 費(fèi)亭 歸納這些結(jié)果歸納這些結(jié)果 為了確定這些結(jié)果的穩(wěn)定性 我們還對隨機(jī)制動概率為 0 1 而不 僅僅是 0 的情況做了計算 對于每個 值 即使等待時間發(fā)生變化 收費(fèi)亭的最優(yōu)數(shù)量也不會變化 對于任何必要的設(shè)置變化 這個過程 都可以進(jìn)行重復(fù) 至此 我們已經(jīng)說明了確定收費(fèi)亭最優(yōu)數(shù)量的一般 方法 3 每條車道一個收費(fèi)站每條車道一個收費(fèi)站 如果汽車不允許變更車道 每條車道一個收費(fèi)亭的情況將會簡化 為 k 個相互獨立的單車道模型 這將相當(dāng)于我們的單車道高速公路 但是我們知道 事實并非如此 汽車會傾向于進(jìn)入隊列最短的車道 我們的結(jié)果中 n k 的情況是典型的非最佳 唯一的例外是雙 車道公路 在這里 n 2 時的時間只不過是勉強(qiáng)長于 n 4 時 然 而 這并不是因為 n k 時總是 壞的 而是因為通常能找到一個更好的 結(jié)果 隨著車道數(shù)目的增加 收費(fèi)亭的數(shù)量也會顯著增加 如