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

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

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

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

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

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

1.1 模型假設(shè)

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 符號(hào)說明

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

1.3 模型建立

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

交通需求可達(dá)率表示從給定起點(diǎn)到終點(diǎn)的已分配交通量中，實(shí)際到達(dá)目的地的交通量比例。其計(jì)算公式為：

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

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

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

其中，是起點(diǎn)和終點(diǎn)對(duì)的期望可達(dá)率。

并有以下約束條件：

（1）交通量守恒：

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

（3）路徑選擇約束：

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

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

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

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

2 模型求解

2.1 求解步驟說明

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

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

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

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

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

3 模型拓展

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

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

我們?cè)谠械募s束條件中加入路段容量限制，確保各路段上的交通量不超過其容量上限。

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

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

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

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

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

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

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

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

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

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

4 模型分析

4.1 靈敏度分析

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

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

4.2 誤差分析

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

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

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

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

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

5 模型改進(jìn)與推廣

5.1 模型改進(jìn)

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

5.2 模型推廣

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

6 結(jié)語

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

參考文獻(xià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ò)可達(dá)性評(píng)價(jià)方法研究[J].現(xiàn)代城市軌道交通，2022（04）：66-71.

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