陳詩(shī)意 潘義勇 魏雙秋

摘要：為解決交通網(wǎng)絡(luò)最優(yōu)路徑問(wèn)題，提出改進(jìn)的行程時(shí)間估計(jì)模型，并設(shè)計(jì)基于該模型的最優(yōu)路徑算法。行程時(shí)間估計(jì)模型在分段截?cái)喽嗡俣溶壽E模型的基礎(chǔ)上進(jìn)行改進(jìn)，用路段節(jié)點(diǎn)的到達(dá)速度代替同一出發(fā)時(shí)刻下測(cè)得的速度，通過(guò)構(gòu)造在時(shí)間和空間上連續(xù)的速度軌跡來(lái)估計(jì)行程時(shí)間。首先，基于Yen′s KSP算法以路段距離為阻抗求解K條最短路徑;其次，分別用改進(jìn)的行程時(shí)間估計(jì)模型估計(jì)K條最短路徑的行程時(shí)間;最后，以行程時(shí)間為成本選擇最優(yōu)的路徑。通過(guò)Sioux Falls網(wǎng)絡(luò)的數(shù)值試驗(yàn)驗(yàn)證模型和算法的有效性和優(yōu)越性。試驗(yàn)結(jié)果表明：改進(jìn)的分段截?cái)喽嗡俣溶壽E模型相比于原始模型精度平均提高了65%;算法的最優(yōu)路徑結(jié)果能減少路徑經(jīng)過(guò)的交叉口數(shù)和縮短最優(yōu)路徑的總長(zhǎng)度，而且最優(yōu)路徑的行程時(shí)間估計(jì)結(jié)果與真實(shí)值的MAPE保持在3%內(nèi)。

關(guān)鍵詞：智能交通;行程時(shí)間;最優(yōu)路徑選擇;KSP

中圖分類號(hào)：U491.1+3 文獻(xiàn)標(biāo)志碼：A

本文引用格式：陳詩(shī)意，潘義勇，魏雙秋. 基于改進(jìn)行程時(shí)間估計(jì)模型的最優(yōu)路徑選擇[J]. 華東交通大學(xué)學(xué)報(bào)，2023，40（1）：60-66.

Optimal Path Selection Based on Improved Travel Time

Estimation Model

Chen Shiyi， Pan Yiyong， Wei Shuangqiu

（College of Automobile and Traffic Engineering， Nanjing Forestry University， Nanjing 210037， China）

Abstract：To solve the optimal path problem of the traffic network， an improved travel time estimation model was proposed， and an optimal path algorithm based on this model was designed. The travel time estimation model was improved on the basis of the segment truncated quadratic velocity trajectory model by replacing the velocity measured at the same departure moment with the arrival velocity of the road segment nodes， and the travel time was estimated by constructing a velocity trajectory that is continuous in time and space. The optimal path algorithm based on travel time estimation firstly solved K shortest paths based on Yen′s KSP algorithm with road section distance as impedance， then estimated the travel time of K shortest paths by the improved travel time estimation model respectively， and finally selected the optimal path with travel time as cost. The validity and superiority of the model and algorithm were verified by numerical experiments of Sioux falls network. The experimental results show that the improved segmented truncated quadratic speed trajectory model improves the accuracy by an average of 65% compared with the original model and the optimal path results based on the proposed algorithm can reduce the number of intersections the path passes through and shorten the total length of the optimal path. Moreover， the estimated results of the optimal path's travel time stay within 3% of the real value of MAPE. The results of this study may provide a theoretical basis for the optimal path method for traffic networks.

Key words： intelligent transportation; travel time; optimal path selection; KSP

Citation format：CHEN S Y，PAN Y Y，WEI S Q. Optimal path selection based on improved travel time estimation model[J]. Journal of East China Jiaotong University，2023，40（1）：60-66.

最優(yōu)路徑問(wèn)題是ITS系統(tǒng)子系統(tǒng)路徑誘導(dǎo)系統(tǒng)的核心，而可靠的行程時(shí)間估計(jì)是進(jìn)行路徑誘導(dǎo)的前提[1-2]?，F(xiàn)有的路徑誘導(dǎo)系統(tǒng)一般基于當(dāng)前或歷史數(shù)據(jù)提供路線方案，但由于缺少考慮交通信息的變化，導(dǎo)致決策的路徑無(wú)法有效避免擁堵[3-4]?；诮煌ňW(wǎng)絡(luò)動(dòng)態(tài)信息估計(jì)行程時(shí)間優(yōu)化路徑誘導(dǎo)算法，對(duì)提高出行效率具有重要意義。

現(xiàn)狀的交通網(wǎng)絡(luò)最優(yōu)路徑算法主要分為兩類：一類是基于Dijkstra算法的啟發(fā)式算法，另一類是基于行程信息的K最優(yōu)路徑算法。Wen等[5]提出了兩種基于傳統(tǒng)Dijkstra的啟發(fā)式算法：?jiǎn)l(fā)式算法一可以將Dijkstra算法求得的初始路徑解保存在中間節(jié)點(diǎn)的標(biāo)簽中;啟發(fā)式算法二和Huang等[6]提出的類似，使用時(shí)空擴(kuò)展網(wǎng)絡(luò)，將時(shí)間區(qū)間分成離散的幾個(gè)時(shí)間間隔，只有每個(gè)時(shí)間間隔的最小成本標(biāo)簽被保存在中間節(jié)點(diǎn)。在實(shí)際應(yīng)用中，路徑誘導(dǎo)系統(tǒng)需根據(jù)路阻隨時(shí)間的變化來(lái)計(jì)算路徑，故基于當(dāng)前靜態(tài)的交通信息計(jì)算的最優(yōu)路徑不能保證它是全局最優(yōu)的[7-8]。K最優(yōu)路徑（K shortest paths， KSP）算法可以提供K條路徑方案，彌補(bǔ)了靜態(tài)最優(yōu)路徑算法的缺陷，有部分學(xué)者采用K最優(yōu)路徑算法求解網(wǎng)絡(luò)最優(yōu)路徑問(wèn)題。Fu等[9]提出基于Shier的K最短路徑算法的啟發(fā)式算法，通過(guò)檢查參數(shù)K可以找到潛在最優(yōu)路徑而不需要枚舉所有路徑。段宗濤等[10]應(yīng)用了KSP算法獲得K條最優(yōu)路徑，通過(guò)對(duì)路徑集合按設(shè)計(jì)通行能力劃分等級(jí)，將交通流按權(quán)重分配到不同等級(jí)的K條路徑上，提高整個(gè)交通網(wǎng)絡(luò)的資源利用率。Hu等[11]提出了一種平衡重疊和行程時(shí)間偏差的K最短路徑算法，該算法包含實(shí)時(shí)更新信息的網(wǎng)絡(luò)模型，并通過(guò)懲罰函數(shù)和行程時(shí)間約束K條路徑，該算法可以有效篩選大量的K條最優(yōu)路徑的結(jié)果。綜上所述，啟發(fā)式最優(yōu)路徑算法計(jì)算時(shí)間長(zhǎng)，難以運(yùn)用于大型網(wǎng)絡(luò)中，而KSP算法魯棒性強(qiáng)，時(shí)間復(fù)雜度低。有必要結(jié)合KSP算法和行程時(shí)間估計(jì)模型來(lái)優(yōu)化交通網(wǎng)絡(luò)最優(yōu)路徑算法，以獲得有效的最優(yōu)路徑。

1 行程時(shí)間估計(jì)

行程時(shí)間一般可以通過(guò)區(qū)間檢測(cè)器直接獲得，但此方法容易累積設(shè)備的計(jì)數(shù)誤差，故目前研究中常將行程時(shí)間作為變量，通過(guò)其他交通相關(guān)變量構(gòu)造模型來(lái)估計(jì)行程時(shí)間[12]。而在眾多的交通變量中，速度相較于其他反映交通流特征的變量如交通流、密度更容易獲得。研究選擇構(gòu)建基于速度的行程時(shí)間估計(jì)模型。

經(jīng)典分段截?cái)喽嗡俣溶壽E模型[13]利用相鄰的3個(gè)路段節(jié)點(diǎn)速度構(gòu)造連續(xù)的、平滑的速度軌跡，如式（1）所示。該模型用各節(jié)點(diǎn)在同一出發(fā)時(shí)刻t的速度構(gòu)造速度軌跡，故存在速度軌跡在時(shí)間維度不連續(xù)的問(wèn)題，只適用于距離足夠短的路徑或交通運(yùn)行狀態(tài)良好的高速公路。針對(duì)該問(wèn)題，提出了改進(jìn)的分段截?cái)喽嗡俣溶壽E模型，模型考慮了行程中交通狀態(tài)變化對(duì)速度的影響，利用到達(dá)節(jié)點(diǎn)的速度v[ATm（t），xm]代替出發(fā)時(shí)刻速度v（t，xm），改進(jìn)模型如式（2）所示。改進(jìn)的模型不受限于通過(guò)路段的時(shí)間間隔足夠小，或要求路段的交通流是穩(wěn)定流的條件，符合實(shí)際交通網(wǎng)絡(luò)的應(yīng)用。

v（τ）≈v（t，x2m-1）l2m-1（τ）+v（t，x2m）l2m（τ）+v（t，x2m+1）l2m+1（τ）

（1）

v（τ）≈v[AT2m-1（t），x2m-1]l2m-1（τ）+v[AT2m（t），x2m]l2m（τ）+

v[AT2m+1（t），x2m+1]l2m+1（τ）（2）

式中：t為出發(fā)的時(shí)刻;v（τ）為相鄰2個(gè)路段的速度軌跡;v[AT2m-1（t），x2m-1]，v[AT2m（t），x2m]和v[AT2m+1（t），x2m+1]分別為到達(dá)第2m- 1個(gè)，第2m個(gè)和第2m+1個(gè)這3個(gè)相鄰路段節(jié)點(diǎn)處的速度;插值點(diǎn)τ∈[AT2m-1（t），AT2m+1（t）];x2m-1、x2m和x2m+1第2m-1個(gè)、第2m個(gè)和第2m+1個(gè)這3個(gè)相鄰路段節(jié)點(diǎn)的位置;l2m-1（τ），l2m（τ）和l2m+1（τ）均為拉格朗日二次基函數(shù)?；瘮?shù)為

l2m-1（τ）=

l2m（τ）=

l2m+1（τ）=

（3）

考慮到車(chē)輛在道路上的加減速行為，引入了?；瘮?shù)作為邊界速度限制，用歷史數(shù)據(jù)的85%最大最小值構(gòu)造常基函數(shù)vmax和vmin，當(dāng)超過(guò)該值時(shí)就被邊界速度代替。當(dāng)τ∈[AT2m-1（t），AT2m+1（t）]，通過(guò)相鄰3個(gè)路段節(jié)點(diǎn)時(shí)刻的速度與邊界速度值的關(guān)系為

v[AT2m-1（t），x2m-1]l2m-1（τ）+v[AT2m（t），x2m]l2m（τ）+

v[AT2m+1（t），x2m+1]l2m+1（τ）-vmax=0（4）

v[AT2m-1（t），x2m-1]l2m-1（τ）+v[AT2m（t），x2m]l2m（τ）+

v[AT2m+1（t），x2m+1]l2m+1（τ）-vmim=0（5）

式中：τ為取到最大速度vmax或最小速度值vmin的時(shí)刻。

根據(jù)上述改進(jìn)的分段截?cái)喽嗡俣溶壽E模型可以構(gòu)造時(shí)刻出發(fā)的車(chē)輛速度軌跡。假設(shè)OD節(jié)點(diǎn)之間共有M個(gè)節(jié)點(diǎn)，路段行程時(shí)間和OD點(diǎn)的行程時(shí)間可分別由式（6）和式（7）計(jì)算

TT（t;xm，xm+1）=ATm+1（t）-ATm（t）=（6）

TT（t;O，D）=ATM（t）-AT1（t）=TT（t，xm，xm+1）=

（7）

式中：TT（t;xm，xm+1）為路段的行程時(shí)間;TT（t;O，D）為OD節(jié)點(diǎn)間的行程時(shí)間;ATm（t）為到達(dá)第m個(gè)節(jié)點(diǎn)處的速度;v[τm（t）]為區(qū)間[ATm（t），ATm+1（t）]的平均速度。

2 交通網(wǎng)絡(luò)最優(yōu)路徑問(wèn)題

2.1 基于距離阻抗的交通網(wǎng)絡(luò)模型

在估計(jì)各路徑行程時(shí)間前，需求解起訖點(diǎn)之間所有可能的路徑，根據(jù)主要交叉口和道路之間的連接情況，建立基于路段距離的交通網(wǎng)絡(luò)模型。對(duì)于網(wǎng)絡(luò)圖G（V，A，L），V={V1，V2，…，VN}是交通網(wǎng)絡(luò)節(jié)點(diǎn)的集合;A是弧的集合，A?V×V，表示交通網(wǎng)絡(luò)中的路段;L是邊的集合，lij（lij∈L）表示邊Ak=（ViVj）的權(quán)值，是非負(fù)的實(shí)數(shù)，代表節(jié)點(diǎn)Vi和節(jié)點(diǎn)Vj之間的阻抗，如果lij=∞則表示節(jié)點(diǎn)Vi和Vj之間無(wú)邊相連。

在傳統(tǒng)的最優(yōu)路徑問(wèn)題中，通常假設(shè)網(wǎng)絡(luò)邊的權(quán)值不變，不能真實(shí)反映實(shí)際的交通網(wǎng)絡(luò)。為了描述交通網(wǎng)絡(luò)路段權(quán)值的變化，需結(jié)合行程時(shí)間估計(jì)模型估計(jì)路徑的耗時(shí)。

2.2 問(wèn)題描述

在實(shí)際出行中，出行者往往遵循“路徑行程時(shí)間最小化”目標(biāo)選擇路徑，故本研究的最優(yōu)路徑以行程時(shí)間作為費(fèi)用考慮。由于行程時(shí)間因不同的出發(fā)時(shí)刻而異，而且與路段的交通狀態(tài)有關(guān)，如果使用原始的分段截?cái)喽嗡俣溶壽E模型估計(jì)行程時(shí)間，即根據(jù)出發(fā)時(shí)刻下測(cè)得的各節(jié)點(diǎn)速度來(lái)構(gòu)造速度軌跡，相當(dāng)于在當(dāng)前的交通狀態(tài)下估計(jì)行程時(shí)間，故基于該行程時(shí)間的最優(yōu)路徑相當(dāng)于靜態(tài)的路徑[14-16]。改進(jìn)的行程時(shí)間估計(jì)模型由于考慮了速度在行程中的變化，構(gòu)造的速度在時(shí)間和空間上連續(xù)，故行程時(shí)間能接近真實(shí)值。當(dāng)獲得起訖點(diǎn)間所有可能的路徑，再用改進(jìn)的行程時(shí)間估計(jì)模型估計(jì)路徑的行程時(shí)間，以時(shí)間成本最少為選擇策略，就可以得到最優(yōu)路徑。綜上所述，基于行程時(shí)間估計(jì)的最優(yōu)路徑算法不需要考慮整個(gè)交通網(wǎng)絡(luò)所有的路段ViVj（ViVj∈A）的行程時(shí)間，只需確定路徑和路徑經(jīng)過(guò)的節(jié)點(diǎn)。

Yen′s KSP算法是典型的偏離路徑算法，適用于求解限定無(wú)環(huán)的K最優(yōu)路徑，與實(shí)際出行的要求相符。Yen′s KSP算法核心思想是循環(huán)使用Dijkstra：每次把前一條最短路徑Pk（k

對(duì)于K最短路徑集合中的路徑Pk（k=1，2，3，…，K），可以根據(jù)式（2）～式（5）用該路徑的節(jié)點(diǎn)到達(dá)速度來(lái)構(gòu)造改進(jìn)分段截?cái)喽嗡俣溶壽E，根據(jù)式（7）求解路徑起訖點(diǎn)之間的行程時(shí)間TT（t;O，D）。

以路徑行程時(shí)間為費(fèi)用，行程時(shí)間最小的路徑即最優(yōu)路徑，則t時(shí)刻從原點(diǎn)出發(fā)到達(dá)終點(diǎn)的最優(yōu)路徑Pk為

Pk=arg min{TT（t;O，D）}=arg min{TT（t;xm，xm+1）}

（8）

式中：Pk為行程時(shí)間費(fèi)用最小的路徑，k=1，2，3，…，K，K為最短路徑數(shù);TT（t;xm，xm+1）為路徑Pk的行程時(shí)間。

3 算法求解及算法復(fù)雜性分析

3.1 算法設(shè)計(jì)

為求解交通網(wǎng)絡(luò)最優(yōu)路徑，設(shè)計(jì)基于Yen′s KSP算法和改進(jìn)行程時(shí)間估計(jì)模型的最優(yōu)路徑算法。首先以路段距離作為權(quán)重，將試驗(yàn)網(wǎng)絡(luò)的路權(quán)以矩陣形式存儲(chǔ)，將OD點(diǎn)和網(wǎng)絡(luò)權(quán)重矩陣輸入Yen′s KSP算法，輸出K條最短路徑集合，而且集合內(nèi)的路徑按距離長(zhǎng)度由小到大排序。將輸出的前K條距離最短的路徑分別用改進(jìn)的分段截?cái)喽嗡俣溶壽E模型估計(jì)行程時(shí)間，確定出發(fā)時(shí)刻和K條最短路徑的各個(gè)節(jié)點(diǎn)的到達(dá)速度，用到達(dá)速度代替出發(fā)時(shí)刻速度，構(gòu)造在時(shí)間和空間域連續(xù)的速度軌跡，最后以時(shí)間成本為決策，選擇耗時(shí)最短的路徑作為最優(yōu)路徑。具體算法步驟如下。

第1步 用Yen′s KSP算法計(jì)算K條距離最短路徑。確定試驗(yàn)網(wǎng)絡(luò)，以路段距離為權(quán)重存儲(chǔ)網(wǎng)絡(luò)的權(quán)重矩陣，用Yen′s KSP算法搜索原點(diǎn)O到終點(diǎn)D的K條距離最短的初始路徑，輸出前K條距離最短的路徑集合。

第2步 用節(jié)點(diǎn)的到達(dá)速度構(gòu)造在時(shí)空域連續(xù)的速度軌跡。確定出發(fā)時(shí)刻t，分別確定第1步輸出的前K條距離最短的路徑Pk（k=1，2，3，…，K）各個(gè)節(jié)點(diǎn)的到達(dá)時(shí)刻速度，用到達(dá)節(jié)點(diǎn)時(shí)刻的速度v[ATm（t），xm]輸入改進(jìn)的分段截?cái)喽嗡俣溶壽E模型，由拉格朗日二次插值基函數(shù)和?；瘮?shù)構(gòu)造在時(shí)間上連續(xù)的速度軌跡v（τ）。

第3步 分別估計(jì)K條最短路徑的行程時(shí)間。對(duì)這K條路徑Pk（k=1，2，3，…，K）分別求速度軌跡v（τ）在子路段的平均速度v[τm（t）]，m=1，2，3，…，M-1，最后根據(jù)式（7）估計(jì)路徑的行程時(shí)間TT（t;O，D）。

第4步 對(duì)K條路徑的行程時(shí)間成本按從小到大排序。

第5步 將行程時(shí)間耗時(shí)最少的路徑作為最優(yōu)路徑。以路徑行程時(shí)間為費(fèi)用，行程時(shí)間最小的路徑Pk即最優(yōu)路徑。

3.2 算法復(fù)雜性分析

在不考慮數(shù)據(jù)結(jié)構(gòu)的前提下，算法復(fù)雜性表現(xiàn)為時(shí)間復(fù)雜度。Dijkstra算法計(jì)算兩點(diǎn)間的最優(yōu)路徑時(shí)間復(fù)雜度為O（m+nlogn）;每條候選路徑Pk+1最多包含n個(gè)節(jié)點(diǎn)，求解每個(gè)節(jié)點(diǎn)到目的節(jié)點(diǎn)偏離路徑時(shí)間的復(fù)雜度是O（n×（m+nlogn））;假設(shè)結(jié)果列表中最多有K條無(wú)環(huán)路徑，把新的偏離路徑放入候選路徑集中的算法復(fù)雜度是O（logK）;從候選路徑集pk+1中最多有n條路徑，從中選擇最短的路徑時(shí)間復(fù)雜度是O（n）;用改進(jìn)的分段截?cái)喽魏瘮?shù)估計(jì)行程時(shí)間的算法復(fù)雜度是O（（i×j）+2i），其中，i是插值數(shù)，j是節(jié)點(diǎn)數(shù)[17-18]。綜上，基于行程時(shí)間估計(jì)的最優(yōu)路徑算法的復(fù)雜度為O（K（nm+n2logn）+logK+n+i（j+2））。

4 對(duì)比試驗(yàn)

4.1 試驗(yàn)網(wǎng)絡(luò)

為了檢驗(yàn)基于行程時(shí)間估計(jì)最優(yōu)路徑算法的可行性，針對(duì)Sioux Falls（SF）網(wǎng)絡(luò)開(kāi)展數(shù)值試驗(yàn)。Sioux Falls（SF）網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖如圖1所示，該網(wǎng)絡(luò)由24個(gè)節(jié)點(diǎn)和76條路段組成，圖中各路段權(quán)值代表路段的長(zhǎng)度，路段雙向的權(quán)值相等。其中，道路網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)在不同時(shí)間間隔內(nèi)的速度如表1所示，t是從原點(diǎn)出發(fā)的時(shí)刻，Δt是獲取速度數(shù)據(jù)的間隔，Δt取5 min。

4.2 K最短路徑集

用Yen′s KSP算法按路徑長(zhǎng)度搜索節(jié)點(diǎn)的前5條最短路徑，起訖點(diǎn)為1→24，3→20和7→13情景下的前5條最短路徑按長(zhǎng)度增序排列，結(jié)果如表2所示。

4.3 試驗(yàn)結(jié)果的對(duì)比與分析

4.3.1 行程時(shí)間估計(jì)誤差分析

在3種不同起訖點(diǎn)情景下，以最短路徑P1為例，分別用改進(jìn)的分段截?cái)喽嗡俣溶壽E模型和原始模型估計(jì)最短路徑的行程時(shí)間，結(jié)果如圖2所示。改進(jìn)的分段截?cái)喽嗡俣溶壽E模型估計(jì)路徑的行程時(shí)間更接近真實(shí)值，而原始模型估計(jì)的行程時(shí)間容易出現(xiàn)高估的情況。進(jìn)一步計(jì)算兩種模型的平均絕對(duì)百分比誤差（MAPE），得到量化模型的擬合效果，如表3所示。改進(jìn)的行程時(shí)間估計(jì)模型擬合度較高，MAPE值均保持在5%以內(nèi)，有效地提高了原始模型的精度，精度平均提高65%。

4.3.2 最優(yōu)路徑結(jié)果分析

將基于改進(jìn)行程時(shí)間估計(jì)模型和基于原始模型的最優(yōu)路徑結(jié)果進(jìn)行對(duì)比和分析，最優(yōu)路徑結(jié)果如表3中所示。為了評(píng)價(jià)上述兩種算法的性能，分別設(shè)置3種起訖點(diǎn)（1→24，3→20和7→13）情景，以路徑耗時(shí)、路徑長(zhǎng)度和與真實(shí)時(shí)間的MAPE作為評(píng)價(jià)指標(biāo)。數(shù)值試驗(yàn)結(jié)果顯示兩種算法下計(jì)算的行程時(shí)間最優(yōu)路徑不完全相同，由試驗(yàn)結(jié)果分析可以得到以下結(jié)論。

1） 從路徑經(jīng)過(guò)的節(jié)點(diǎn)數(shù)看，當(dāng)起訖點(diǎn)為1→24時(shí)，兩種算法計(jì)算的最優(yōu)路徑不相同，基于改進(jìn)模型的最優(yōu)路徑比基于原始模型的最優(yōu)路徑經(jīng)過(guò)的節(jié)點(diǎn)數(shù)減少30%。

2） 從行程時(shí)間耗時(shí)看，通過(guò)考慮路況速度的變化，用到達(dá)節(jié)點(diǎn)的速度代替出發(fā)時(shí)刻下的同一速度構(gòu)造速度軌跡，估計(jì)的行程時(shí)間更符合實(shí)際。當(dāng)起訖點(diǎn)為3→20和7→13時(shí)，盡管兩種算法的最優(yōu)路徑結(jié)果相同，但行程時(shí)間不同：基于改進(jìn)行程時(shí)間估計(jì)的最優(yōu)路徑比基于原始模型的最優(yōu)路徑更接近真實(shí)時(shí)間，MAPE值分別為0.25%和2.96%。

3） 從行程的軌跡看，以上3種起訖點(diǎn)下基于改進(jìn)行程時(shí)間估計(jì)模型的最優(yōu)路徑結(jié)果與距離最短路徑結(jié)果相同。而且起訖點(diǎn)為1→24時(shí)，雖然基于行程時(shí)間估計(jì)的最優(yōu)路徑耗時(shí)僅比基于原始模型的最優(yōu)路徑多1.7%，但路徑總長(zhǎng)比基于原始模型的最優(yōu)路徑縮短3.1%。

綜上所述，基于行程時(shí)間估計(jì)的最優(yōu)路徑算法更具有實(shí)際意義且更有效。

5 結(jié)論

1） 改進(jìn)的行程時(shí)間估計(jì)模型擬合度平均比原始模型提高了65%。

2） 基于本文模型估計(jì)的最優(yōu)路徑時(shí)間成本不總是少于原始模型，但更接近真實(shí)值，與真實(shí)值的MAPE均保持在3%以內(nèi)。

3） 基于本文算法的最優(yōu)路徑結(jié)果能減少路徑經(jīng)過(guò)的交叉口數(shù)和縮短最優(yōu)路徑的總長(zhǎng)度，路徑總長(zhǎng)比基于原始模型的最優(yōu)路徑縮短3.1%。

參考文獻(xiàn)：

[1] 閆茂德，常楠楠，張昌利. 城市快速路網(wǎng)行程時(shí)間計(jì)算與最優(yōu)路徑選擇算法[J]. 西南交通大學(xué)學(xué)報(bào)，2014，49（5）：811-816.

YAN M D，CHANG N N，ZHANG C L. Travel time computation and optimal path selection algorithm of urban expressway network[J]. Journal of Southwest Jiaotong University，2014，49（5）：811-816.

[2] 智路平，周溪召. 基于動(dòng)態(tài)行程時(shí)間可靠性的單車(chē)輛路徑選擇算法研究[J]. 公路交通科技，2018，35（9）：8.

ZHI L P，ZHOU X Z. Study on single vehicle routing algorithm based on dynamic travel time reliability[J]. Journal of Highway and Transportation Research and Development，2018，35（9）：8.

[3] KIM J，HAN W S，OH J，et al. Processing time-dependent shortest path queries without pre-computed speed information on road networks[J]. Information Sciences，2014，255： 135-154.

[4] 姚麗亞，關(guān)宏志，魏連雨，等. 基于實(shí)時(shí)交通信息的行程時(shí)間估算及路徑選擇分析[J]. 公路交通科技，2006（11）：86-89.

YAO L Y，GUAN H Z，WEI L Y，et al. Study on link travel time estimation and route selection method based on real-time traffic information[J]. Journal of Highway and Transportation Research and Development，2006（11）：86-89.

[5] WEN L，CATAY B，EGLESE R，et al. Finding a minimum cost path between a pair of nodes in a time-varying road network with a congestion charge[J]. European Journal of Operational Research，2014，236（3）：915-923.

[6] HUANG Y，ZHAO L，VAN W，et al. Time-dependent vehicle routing problem with path flexibility[J]. Transportation

Research Part B：Methodological，2017，95：169-195.

[7] FARO A，GIORDANO D. Algorithms to find shortest and alternative paths in free flow and congested traffic regimes- ScienceDirect[J]. Transportation Research Part C： Emerging Technologies，2016，73：1-29.

[8] 楊兆升. 城市交通流誘導(dǎo)系統(tǒng)理論與模型[M]. 北京：人民交通出版社，2000.

YANG Z S. Theory and model of urban traffic flow induction system[M]. Beijing：China Communication Press，2000.

[9] FU L P，RILETT L R. Expected shortest paths in dynamic and stochastic traffic networks[J]. Transportation Research Part B：Methodological，1998，32（7）：499-516.

[10] 段宗濤，WANG W X，康軍，等. 面向城市交通網(wǎng)絡(luò)的K最短路徑集合算法[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2014，14（3）：194-200.

DUAN Z T，WANG W X，KANG J，et al. K shortest path set algorithm for urban traffic network[J]. Journal of

Transportation Systems Engineering and Information Technology，2014，14（3）：194-200.

[11] HU X，CHIU Y C. A constrained time-dependent K shortest paths algorithm addressing overlap and travel time deviation[J]. International Journal of Transportation Science & Technology，2015，4（4）：371-394.

[12] MORI U，MENDIBURU A，ALVAREZ M，et al. A review of travel time estimation and forecasting for advanced traveller information systems[J]. Transportmetrica，2015，11（1/2）：119-157.

[13] SUN L，YANG J，MAHMASSANI H. Travel time estimation based on piecewise truncated quadratic speed trajectory[J]. Transportation Research Part A Policy & Practice，2008，42（1）：173-186.

[14] 潘義勇. 動(dòng)態(tài)隨機(jī)交通網(wǎng)絡(luò)環(huán)境下耗時(shí)最可靠路徑研究[D]. 南京：東南大學(xué)，2014.

PAN Y Y. Study on the optimal-reliable routing in stochastic and dynamic traffic network[D]. Nanjing：Southeast University，2014.

[15] ICHOUA S，GENDREAU M，POTVIN J Y. Vehicle dispatching with time-dependent travel times[J]. European

Journal of Operational Research，2003，144（2）：379-396.

[16] 鄭長(zhǎng)江，陳宜恒，沈金星. 基于地鐵的地上地下閉環(huán)物流配送路徑優(yōu)化[J]. 華東交通大學(xué)學(xué)報(bào)，2022，39（1）：89-98.

ZHENG C J，CHEN Y H，SHEN J X. Distribution routing optimization of ground-underground closed-loop logistics based on metro network[J]. Journal of East China Jiaotong University，2022，39（1）：89-98.

[17] 徐濤，丁曉璐，李建伏. K最短路徑算法綜述[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（11）：8.

XU T，DING X L，LI J F. Review on K shortest paths algorithm[J]. Computer Engineering and Design，2013，34（11）：8.

[18] 李臣波. 網(wǎng)絡(luò)的K最短路算法研究[D]. 哈爾濱：哈爾濱理工大學(xué)，2008.

LI C B. Algorithm rearch on K shortest path of networks[D]. Harbin： Harbin University of Science and Technology，2008.