基于Dijkstra算法的交通需求規(guī)劃與最佳可達率問題研究

摘 要：隨著城市化進程加快和自動駕駛技術(shù)發(fā)展，交通規(guī)劃在新興城市建設(shè)中愈發(fā)重要。本文以2024年第二十一屆五一數(shù)學(xué)建模競賽題目B為背景，研究基于Dijkstra算法的交通需求規(guī)劃與最佳可達率問題。通過構(gòu)建數(shù)學(xué)模型來計算不同情況下的交通網(wǎng)絡(luò)期望可達率，給出優(yōu)化路線，為現(xiàn)實交通問題提供解決方案，同時為未來新城自動駕駛汽車路線優(yōu)化提供參考。研究結(jié)果表明，通過合理分配交通需求并優(yōu)化路徑選擇，可顯著提升交通網(wǎng)絡(luò)的可達率，確保其在突發(fā)狀況下仍能高效運行。

關(guān)鍵詞：交通需求 交通可達率 Dijkstra算法

自動駕駛技術(shù)的快速發(fā)展為城市交通帶來了新的機遇與挑戰(zhàn)。研究表明，自動駕駛車輛將對交通網(wǎng)絡(luò)產(chǎn)生深遠(yuǎn)影響。在交通規(guī)劃中，滿足日益增長的交通需求并保持高可達率是核心目標(biāo)。可達率作為衡量交通系統(tǒng)性能的關(guān)鍵指標(biāo)，直接反映交通需求的實現(xiàn)程度。

然而，城市交通網(wǎng)絡(luò)常因突發(fā)狀況如事故或施工導(dǎo)致可達率降低，因此科學(xué)合理的交通規(guī)劃至關(guān)重要。盡管已有大量研究關(guān)注交通需求規(guī)劃和可達率問題，但將可達率引入交通需求規(guī)劃的文獻較少。因此本研究基于2024年第二十一屆五一數(shù)學(xué)建模競賽題目B的數(shù)據(jù)，建立數(shù)學(xué)模型，計算不同情況下的交通網(wǎng)絡(luò)期望可達率。引入Dijkstra算法和遺傳算法進行優(yōu)化，旨在為交通規(guī)劃提供更高效、更科學(xué)的解決方案，以應(yīng)對未來城市交通網(wǎng)絡(luò)中的復(fù)雜性和不確定性。

1 模型的假設(shè)與建立

1.1 模型假設(shè)

為了簡化模型，本文共提出以下六條假設(shè)。

（1）路段容量獨立性假設(shè)

假設(shè)網(wǎng)絡(luò)中每條路段的容量是獨立的，路段之間的交通量不會相互影響。

（2）路段失效概率假設(shè)

假設(shè)每條路段出現(xiàn)突發(fā)事故的概率相同，且這些事件是獨立的。

（3）交通量守恒假設(shè)

假設(shè)交通網(wǎng)絡(luò)中從起點到終點的總交通量等于該路徑上的所有交通需求的總和。

（4）路徑選擇假設(shè)

研究假設(shè)每個起點到終點對之間只能選擇最多五條路徑，并且路徑的選擇與交通量的分配是獨立的。

（5）新建路段容量假設(shè)

假設(shè)新建的路段容量足夠大，可以滿足所有交通需求，不會成為瓶頸。

（6）交通需求不變假設(shè)

假設(shè)交通需求在考慮新建路段時不會發(fā)生變化，即只考慮現(xiàn)有的交通需求分配情況。

1.2 符號說明

如表1所示，表中所說明的符號是本文研究中所使用的基本變量的展示。

1.3 模型建立

參照2024年第二十一屆五一數(shù)學(xué)建模競賽題目B中的問題，我們主要針對問題二進行了如下建模與分析。

交通需求可達率表示從給定起點到終點的已分配交通量中，實際到達目的地的交通量比例。其計算公式為：

的計算公式考慮了每條路徑上的交通量和總交通需求量。

每個路段的突發(fā)狀況概率相同且獨立。目標(biāo)是在任意一條路段出現(xiàn)突發(fā)狀況時，最大化所有交通需求的期望可達率。在計算交通需求可達率時，對每個起點-終點對，計算路徑集合。對于每一條路徑，計算其交通需求可達率。進而計算期望可達率，即為。

我們的目標(biāo)是最大化在所有可能的5條路段突發(fā)狀況組合下，所有起點和終點對的期望可達率。這可以表示為：

其中，是起點和終點對的期望可達率。

并有以下約束條件：

（1）交通量守恒：

（2）非負(fù)約束：

（3）路徑選擇約束：

其中，是表示路徑是否被選擇的二元變量。

（4）路徑規(guī)劃交通量約束：

其中是一個足夠大的正數(shù)，用來確保如果路徑?jīng)]有被選擇，那么對應(yīng)的交通量將為零。

通過以上模型，我們可以在考慮所有可能的5條路段突發(fā)狀況組合的情況下，最大化所有交通需求的期望可達率。

2 模型求解

2.1 求解步驟說明

求解模型時，首先對數(shù)據(jù)進行預(yù)處理，將交通需求量按照起點和終點匯總成字典格式，其中鍵為（起點，終點）的元組，值為需求量。計算最短路徑時，采用Dijkstra算法計算每個起點到終點的最短路徑，并將計算得到的路徑保存在字典中。對每個起點-終點對，隨機分配交通需求量，并進行歸一化處理，確保總需求量為1。

為了更好地去衡量可達率這一指標(biāo)，研究采用取反的方式，即計算不可達率。計算每個路段的交通負(fù)載，若負(fù)載超過容量，則產(chǎn)生不可達率。匯總所有路段的不可達率，得到整個網(wǎng)絡(luò)的期望不可達率。

優(yōu)化模型時，采用遺傳算法進行優(yōu)化，通過多次運行并比較期望不可達率，選擇最低的解作為最優(yōu)解。

2.2 數(shù)據(jù)處理

原數(shù)據(jù)一共提供100條數(shù)據(jù)，42個不同地點，且從不同起點至不同終點的交通需求量。針對交通需求量分布，運用Dijkstra算法計算每個起點到終點的最短路徑，采用遺傳算法進行優(yōu)化，最終得到交通需求量最優(yōu)分配圖，如圖1所示。

3 模型拓展

3.1 考慮路段容量限制下的交通需求分配

在實際生活中，每一條道路的容量是有限的，在建立模型的時候需要考慮到路段容量的限制。因此在模型中加入路段容量的限制，在有路段容量限制的情況下進行模型拓展。

我們在原有的約束條件中加入路段容量限制，確保各路段上的交通量不超過其容量上限。

其中，表示路段的容量上限。

其余約束條件以及目標(biāo)函數(shù)不變，求解以后得到以下的交通需求量最優(yōu)分配圖，如圖2所示。

3.2 考慮新建路段下的交通需求分配

隨著城市基礎(chǔ)設(shè)施建設(shè)的發(fā)展，在不同的節(jié)點之間可能會出現(xiàn)新建的路段，這些新建的路段會影響到城市交通網(wǎng)絡(luò)的可達率。同時新建路段不能跨越其他路段，只能在內(nèi)部修建。通過引入新的變量可以建立更加完善的交通分配模型。變量定義如下：

目標(biāo)函數(shù)也進行了相應(yīng)的修改以匹配新的變量。考慮新建路段下的交通需求分配的目標(biāo)函數(shù)如下：

其中：表示沒有發(fā)生突發(fā)事故的路段的交通分配量；

表示發(fā)生突發(fā)事故的路段的交通分配量。且恒為0；

表示該沒有發(fā)生突發(fā)事故的路段是否被選擇，為二元變量；

表示該發(fā)生突發(fā)事故的路段是否被選擇，為二元變量；

求解模型得到可達率最高的交通需求量分配。最優(yōu)交通網(wǎng)絡(luò)圖如圖3所示。

4 模型分析

4.1 靈敏度分析

通過改變交通需求量，可以增加或減少交通需求量或路段容量，觀察期望可達率的變化。結(jié)果如表2所示。

綜合分析這些結(jié)果，所建立的模型對交通需求量的波動表現(xiàn)出高度的敏感性。無論是交通需求量的增加還是減少，都會顯著影響整個交通網(wǎng)絡(luò)的期望可達率。

4.2 誤差分析

為了進一步了解模型的穩(wěn)健性，研究模擬了在交通需求量測量過程中可能出現(xiàn)的不同程度的誤差，并探討了這些誤差如何影響期望可達率的變化趨勢。

（1）原始交通需求量為100，實際測量值為105時，期望可達率保持在0.85，幾乎無變化，這顯示出模型在面對5%的正向測量誤差時展現(xiàn)了一定的魯棒性。

（2）初始交通需求量為120，實際測量值減少至115時，期望可達率下降至0.82，這表明模型對5%的負(fù)向誤差較為敏感。

（3）原始交通需求量為80，實際測量值增加至85后，期望可達率提升至0.88，這一增長再次證明模型對5%的正向誤差也較為敏感。

綜合上述分析，模型在面對測量誤差時表現(xiàn)出較強的魯棒性，并且對正向和負(fù)向誤差均保持了一定的敏感度。

5 模型改進與推廣

5.1 模型改進

為提升模型的實用性和準(zhǔn)確性，可從以下方面進行改進：一是引入更多影響交通網(wǎng)絡(luò)的因素，如交通擁堵情況、交通事故頻率等，以增強模型對復(fù)雜交通環(huán)境的適應(yīng)性；二是對遺傳算法等優(yōu)化方法進行改進，提高求解效率和結(jié)果質(zhì)量；三是通過實際數(shù)據(jù)對模型進行驗證，確保其準(zhǔn)確性和可靠性。

5.2 模型推廣

該模型具有廣泛的適用性，能夠滲透至多領(lǐng)域，為精細(xì)優(yōu)化和精準(zhǔn)決策提供堅實的支持。也可以為交通相關(guān)的企業(yè)提供至關(guān)重要的決策參考和技術(shù)支持，助力其實現(xiàn)更高效、科學(xué)地運營。也可以運用到運輸行業(yè)和物流行業(yè)，為相應(yīng)的運輸以及物流提供借鑒以及經(jīng)驗。

6 結(jié)語

本研究以2024年第二十一屆五一數(shù)學(xué)建模競賽題目B為背景，探討了基于Dijkstra算法的交通需求規(guī)劃與最佳可達率問題。通過構(gòu)建綜合模型并結(jié)合Dijkstra算法和遺傳算法，研究實現(xiàn)了交通網(wǎng)絡(luò)的高效優(yōu)化。結(jié)果表明合理分配交通需求和優(yōu)化路徑選擇可顯著提升交通網(wǎng)絡(luò)可達率，并確保其在突發(fā)狀況下仍能高效運行。本研究創(chuàng)新性地將可達率與交通需求規(guī)劃結(jié)合，為未來城市交通網(wǎng)絡(luò)的優(yōu)化提供了理論支持和實踐指導(dǎo)。盡管模型存在一定局限，但其在交通規(guī)劃、管理及智慧交通等領(lǐng)域具有廣泛的應(yīng)用前景，可為相關(guān)決策提供重要參考。

參考文獻：

[1]Fagnant， D. J.， amp; Kockelman， K. Preparing a nation for autonomous vehicles： opportunities， barriers and policy recommendations[J].Transportation Research Part A： Policy and Practice， 2015，77：167-181.

[2]馮柏盛，殷瑋川.基于層次分析法的城市交通網(wǎng)絡(luò)可達性評價方法研究[J].現(xiàn)代城市軌道交通，2022（04）：66-71.

[3]李崇楠.城市軌道交通網(wǎng)絡(luò)魯棒性評價與線網(wǎng)優(yōu)化[D].北京：北京交通大學(xué)，2023.