交通路網(wǎng)中最優(yōu)路徑算法的道路權(quán)重選擇

［摘 要］在交通路網(wǎng)中，尋找任意兩點(diǎn)間最優(yōu)路徑是出行導(dǎo)航的基本功能。除了最優(yōu)路徑算法自身性能外，道路權(quán)重的選擇也直接決定了尋徑結(jié)果的優(yōu)劣?，F(xiàn)有最優(yōu)路徑算法通常以通行能力為道路權(quán)重，其可能導(dǎo)致不合理的尋徑結(jié)果，同時(shí)也不具有全局負(fù)載均衡的能力。因此本文以Dijkstra算法為例，引入可達(dá)性概念作為道路權(quán)重，從而彌補(bǔ)以通行能力為道路權(quán)重的缺陷。

［關(guān)鍵詞］Dijkstra算法；道路權(quán)重；通行能力；可達(dá)性

doi:10.3969/j.issn.1673-0194.2009.15.017

［中圖分類(lèi)號(hào)］C931；U412.37［文獻(xiàn)標(biāo)識(shí)碼］A［文章編號(hào)］1673-0194（2009）15-0054-03

1 引 言

在交通路網(wǎng)中，兩點(diǎn)間最優(yōu)路徑算法的優(yōu)劣主要受到兩個(gè)因素的影響，即所使用的通用最短路徑算法和所選擇的道路權(quán)重。通用最短路徑算法是最優(yōu)路徑選擇的搜索工具，決定了如何在龐大的路網(wǎng)數(shù)據(jù)庫(kù)中找到最優(yōu)（或者最滿(mǎn)意）的可行路徑。道路權(quán)重則是最優(yōu)路徑選擇的搜索指標(biāo)，它的標(biāo)定決定了通用最短路徑算法搜索的依據(jù)。所謂最優(yōu)路徑選擇就是使用通用最短路徑算法搜索道路權(quán)重最高（或者局部最高）的可行路徑。因此，通用最短路徑的選擇直接影響到最優(yōu)路徑選擇的效率和優(yōu)化度，而道路權(quán)重直接影響到最優(yōu)路徑選擇的合理性。

其中，研究人員普遍關(guān)注所選用的通用最短路徑算法。為解決這個(gè)問(wèn)題，現(xiàn)在已有多種優(yōu)秀的最優(yōu)路徑算法，如Dijkstra算法、Floyd算法、A*算法等。但是，研究人員常常忽視了道路權(quán)重問(wèn)題，提供給出行者的道路權(quán)重選擇沒(méi)有貼近出行者的實(shí)際出行習(xí)慣，并不能真正滿(mǎn)足出行者的需求。……