行程時間不確定環境下的可靠最短路徑算法研究

《行程時間不確定環境下的可靠最短路徑算法研究》是依託武漢大學，由陳碧宇擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：行程時間不確定環境下的可靠最短路徑算法研究
• 項目類別：青年科學基金項目
• 項目負責人：陳碧宇
• 依託單位：武漢大學

項目摘要

在擁堵的城市網路中，行程時間具有高度的不確定性。大量實證表明：出行者在行程時間不確定的情況下更傾向於選擇可靠度高的路徑，即可靠最短路徑。因此，很有必要研究隨機網路中的可靠最短路徑問題。由於可靠最短路徑具有不可加性(即路徑阻抗不等於路段阻抗之和)，不能直接採用傳統的最短路徑算法求解。針對可靠最短路徑的不可加性難題，本項目將可靠最短路徑問題表述為多目標最佳化問題，研究其多目標支配條件。在此基礎上，提出一種隨機網路的層次模型,減小可靠最短路徑計算的規模，高效地查找超大型網路中的可靠最短路徑。將問題進一步擴展到動態隨機網路中，研究路段時間的隨機先進先出特性，提出有效的動態可靠最短路徑算法。最後，結合實際交通數據，對理論成果進行綜合實驗驗證和分析。可靠最短路徑算法考慮了出行者在行程時間不確定環境下的風險決策行為，可提高導航套用的可靠性，有效地指導公眾出行，對緩解交通擁堵具有十分重要的意義。

結題摘要

在擁堵的城市網路中，行程時間具有高度的不確定性。大量實證表明：出行者在行程時間不確定的情況下更傾向於選擇可靠度高的路徑，即可靠最短路徑。本課題針對隨機網路中的可靠最短路徑問題，主要研究：①基於浮動車數據研究行程時間分布估計方法，定量分析行程時間不確定性；②建立動態隨機網路中的多目標支配條件，證明動態隨機網路中行程時間的隨機先進先出和不可逆特性；③提出多目標A*算法和雙階段搜尋算法，高效地求解大規模網路中的正向和逆向可靠最短路徑問題；④進一步研究可靠最短路徑成果在出行行為分析和物流配送中的套用。項目研究進展順利，目前已發表論文9篇（其中SCI/SSCI文章8篇，EI論文1篇），授權2項國家專利；培養了畢業博士生1名，碩士生4名；資助成員和學生參加了5個國際/國內會議。通過該項目的研究能夠為提高導航套用的可靠性，有效地指導公眾出行，提供理論支撐和決策依據。